SCRS Insights

Efforts made by a group of individuals are always superior to that of an individual. The reason for this is very simple: When a group of individuals works together to accomplish a task, an intelligence emerges which is usually referred to as collective intelligence or swarm intelligence or group intelligence. When the same work is done by an individual this intelligence is absent. Even if the same work is done by the same number of individuals one by one the output will not be better than if all those individuals work collectively and help each other.

Collective intelligence has been a great reason for the evolution and it can be seen in nature everywhere. Whether it is a group of ants, school of fishes, flock of birds or a group of monkeys, collective intelligence has helped them to compete with the environment and the predators.

Distributed Collective Intelligence is the swarm intelligence

In order to accomplish a task if all the members of a group are cooperating with each other then, in general, the emerged intelligence is known as collective intelligence. If members perform the task assigned to them and cooperate with each other then this distributed collective intelligence is referred to as swarm intelligence (SI). In other words, when individuals in a group work together having two properties: division of labor (DL) and self-organization (SO) then the emerged collective intelligence is known as the swarm intelligence.

Carrying a large payload by a group of ants is an excellent example of swarm intelligence.

Swarm intelligence is a particular kind of collective intelligence. Peer to peer learning, sharing of the information among each other and respecting the information received are the necessary properties for the collective intelligence. If the division of labor and self-organization is also included then the collective intelligence becomes swarm intelligence. In order to have DL and SO, it is necessary that all the members of the swarm are homogeneous. Monkeys and ants or ants and bees cannot make a swarm and therefore swarm intelligence cannot be expected from the group containing ants and monkeys. It should be noted that all the swarm intelligence algorithms are called nature-inspired algorithms and these are not the simulation of nature. Therefore, even if the hive of bees or the nest of ants have their queens, artificial bee colony (ABC) algorithm and ant colony optimization (ACO) do not have any concept of queen or the leader. In swarm intelligence algorithms, any member at any point of time is the best (in case of search, most close to the desired place) becomes the leader. This designation of the leader depends upon the performance and keep on changing from member to member.

Presence of swarm intelligence also exhibits that the members depend upon each other and follow DL and SO properties.

Drone Swarm

An interacting autonomous group of drones assigned to perform a/some task(s). In drone swarm (DS), it is expected that every drone has the same configuration and is able to perform a task which anybody else can do.

The objective of drone swarm is to develop an autonomous system consisting of

1. a group of drones (typically, 30 or more), //swarm size will be discussed in detail later.
2. connections among them, and
3. the ability to perform a well-defined task.

Here autonomous means the swarm of drones (DS) should not be controlled by the ground station but the direction and distance to be covered should be decided by the DS itself. This decision should be taken by the information shared with each other. A typical update equation is (let us call a drone by its position x)

x = x+h

Here ‘h’ is the term obtained by interaction of drone ‘x’ with other drones. Now the definition of h depends upon the topology of interaction. E.g. if we consider that every drone is interacting with each other and they have decided that a particular drone x_g is most close to the desired location then one simple position update equation will be

x = x + t(x_g — x)

t is the weight to the direction guided by the best drone. (x_g — x) is denoting the influence on x from x_g. If the objective is to make a cluster of all the drones in a given area, then (x_g — x) will be an ordinary difference of x and x_g.

Now the information sharing with all other drones may not be a practical idea and therefore a less connected structure may be thought of. Following are the few possible less connected information sharing topologies:

1. Every drone is connected with the 3 nearest drones, i.e. total 4 drones are communicating with each other. These 4 size neighbourhoods (nbd) are overlapping to each other and therefore the entire swarm is connected. I have done the experiments with various nbd sizes on a popular swarm intelligence algorithm, Particle Swarm Optimization and found that nbd size 4 is an optimal choice. The drawback of this strategy is that all the drones have to check the distances with other drones and to decide the nbd.

2. Another strategy, particularly for drones may be that a subgroup of drones (say, having 4 drones) are communicating with another subgroup via a designated drone, call it a node. For any subgroup, the communication with another subgroup will be decided based on the distances between nodes. i.e., whenever any node finds another node within its range it will start information sharing.

3. However, strategy 2, is good in terms of time and the energy consumed in information sharing, in this strategy, if the link between any two nodes is broken then the entire swarm may collapse. Therefore a slightly more connected but less than fully connected structure should be adopted. One solution is that instead of 1 node in each subgroup, it has two nodes. Both the nodes are linked with the other two nodes as shown below:

Other important features of the DS should be dispersion and aggregation. They should maintain a minimum inter-drone distance. They should also maintain the maximum distance between any two drones of the swarm so that they do not lose the connection with others. This is very necessary to be in the group.

If all the drones are flying in a particular predefined formation and are covering a fixed area then the exploration rate of the search region will be very slow. On the other way, if the distance between any two drones can vary between a lower and upper bound then the exploration ability will be increased.

Swarm Size

Swarm size (number of drones in DS) depends upon the number of decision variables. The number of decision variables depends upon the task assigned to the swarm. A large swarm size improves the performance of the swarm but up to a certain extent. After a threshold, increasing swarm size will only slow the communication process. However, there is no precise and universal formula to determine the optimal swarm size, many studies have been carried out which have recommended that if the swarm size is between 20–40, the performance of the swarm intelligence algorithm will be better [1].

Maurice Clerc [2] in his standard PSO proposed a formula to determine the swarm size

S = 10+2*sqrt(D)

Here D is the number of decision variables. The formula also suggests that in order to have swarm intelligence behaviour, minimum swarm size should be 12. In Spider Monkey Optimization (SMO) [4], I have experimented and found that below 10 swarm size is not even a swarm and of no use.

However, this formula is usually suggested when the number of decision variables is very large. But if the number of decision variables is around 10 then a fixed swarm size usually between 20–40 (mid value 30) is recommended. In [3], the number of decision variables is 11 and the swarm size is fixed to 30. Finally, there is no universal formula to determine the swarm size and can be fixed only based on the complexity of the problem. Considering the number of decision variables 11 or so for drone swarm, I recommend the optimal swarm size should be 30.

Reference:

[1] Lin Xueyan and Xu Zheng, “Swarm size and inertia weight selection of Particle Swarm Optimizer in system identification,” 2015 4th International Conference on Computer Science and Network Technology (ICCSNT), Harbin, 2015, pp. 1554–1556.

[2] http://clerc.maurice.free.fr/pso/

[3] Vásárhelyi, G., Virágh, C., Somorjai, G., Nepusz, T., Eiben, A. E., & Vicsek, T. (2018). Optimized flocking of autonomous drones in confined environments. Science Robotics, 3(20), eaat3536.

[4] Bansal JC, Sharma H, Jadon SS, Clerc M. Spider monkey optimization algorithm for numerical optimization. Memetic computing. 2014 Mar 1;6(1):31–47.