In my earlier article- Monarchy in the Swarm, I tried to answer the question, how to convert individual drones into a swarm. When there is a special drone that is developed especially for leading drone swarms, the problem is easier to solve. The leader starts discovery algorithm, and recursively, whole swarm is discovered. I highly suggest reading that article since I will not repeat myself in this article with basic knowledge given there.
A predetermined leader drone poses the single point of failure problem. If the leader drone malfunctions, the swarm will be mindless at that point and ineffective, if there are no countermeasures for such scenario. One solution would be adding redundant leader drones into the mix that are constantly monitoring the active leader’s health and taking the leader role whenever the active leader fails. But this is also not the final solution, the leader drones are the Achilles’ heel for the drone swarms.
But, what if every drone has the capability of leading swarm? That would be the final solution to our problem. The drone swarm would heal its control structure whenever the leader drone can not lead anymore. New elections are quickly held, and the swarm continues to its mission without significant delay or loss in capability.
Like real life, a leader must be the most capable one to lead in the population. But what would be the parameters for such capability? This question would require whole another article to answer. But for simplicity, let’s assume there are two important metrics that signify leadership capability;
We identified our parameters of leadership. Each drone can estimate its own remaining life. But how can it know how many drones it can communicate with. Let’s assume each drone keeps a connection list that stores a ID numbers of drones in its communication range.
For this, each drone should repeatedly broadcast its unique ID and nothing else with random periods. Broadcasts should be really short since our wireless medium is shared by all drones and transmissions happening at the same time may cause interference. Repeated broadcasts with random periods are necessary to reduce the chance of two drones interfering with each other at each repeated transmission. Of course this repetition count should be picked carefully since ee do not want too long broadcast process. Swarm’s size and distance between drones are the deciding factors for interference probability.
Whenever a drone receives broadcast of other drones, it should update its connection list with received ID, if it is not added already before. This way, each drone can fill its connection list before elections.
Connection List of a Drone(Representative)
At this moment, each drone has its connection list(and number of connections) and its own remaining lifetime. Formula below will be used to calculate leadership value(LV) of the drones. Each drone should calculate its LV before starting elections.
LV = NumberOfConnections x RemainingBatteryPercentage
For elections, we will use repeated broadcasts with random periods to cover as much of the swarm as possible. Each drone will broadcast its ID and its LV. Any receiving drone will compare the received LV with its own LV. If the received LV is higher, receiving drone will broadcast received ID and received LV-rebroadcasting. If the receiving drone has higher LV, it will broadcast its own ID and LV to its connection list. This process should continue until all drones in the swarm globally agree on the highest LV drone’s leadership.
Repetition count is important here. We want to make sure each drone in the swarm has the same information about leader’s identity. Each drone might have to broadcast more than once if it hears broadcast about another leader, which is better leader than it has. This algorithm might be modified to prevent excess broadcasts.This way, eventually all the drones will know the leader drone in the swarm.
At the start, our topology looks like this;
Drones and Their Communication Range
Each drone, its communication boundaries and line to those boundaries are the same color. Assuming each drone has the same battery level, we can see that C is the best candidate to lead. Repeated-randomized broadcasts are also ignored for this example. We will accept only one drone transmits at any time for simplicity, there is no interference. Let’s see how our algorithm works.
We assumed minimum amount of broadcasts that lead us to elect the most capable leader.
At this point, each drone in the swarm knows who is the leader. After this point, all we have to do form a swarm with techniques given in my first article-Monarchy in the Swarm.
Elections should be repeated when necessary, since we know every drone can fail or its battery runs out. There might be many tweaks to this given algorithm to reduce number of elections in a swarm. but that should be another article’s topic.
Autonomous drone swarms has its specific problems. They rely on communicating with each other,if the aim is operating as swarm instead of individual drones. They are vulnerable to targeted or area jamming, control loss due to leader malfunction. The leader of the swarm should not be seen dictator that sets actions of each swarm member also, it is just a coordinator that manages the swarm. Swarm members has their own mission data and plan.
A robust swarm should easily adapt to control loss and recover in such cases. Like insect swarm, a drone swarm who lost its leader or great portion of its members should continue its mission after recovery.