Problem

It may be a leaderless swarm, but tasks must be assigned efficiently and dependably.

Background

Much computer science - and most classic military thinking- is based on a top-down hierarchy of control. Orders emanate from a central point and descend through a command structure to those who execute them. Using this model, our swarm would have a leader plane who controls, perhaps through delegates, the actions of each plane.

But in social insects, a very different process dominates. The queen bee has no authority at all. Rather each insect directs his own actions according to simple rules. These simple decisions, when repeated enough, result in sophisticated high-order decision-making.

The heart of our project is to evaluate command and control structures for the SWARM UAVs and 'swarm intelligence' is a prime candidate.

Part of considering the value of this approach is a serious attempt to understand how the concept would actually work. 

This topic examines the assignment of various roles in a complex mission. How do the tasks get assigned if nobody is giving orders?

Solution 

We need volunteers.

Each of the planes in the formation follows the same set of simple rules. They are programmed to recognize the needs of the group and to ascertain their own fitness for each task, and to volunteer for the appropriate ones.

We envision a system of bidding, to select the fittest volunteer.

Example Implementation

When the formation flies away from its base, it needs to leave a string of relay communications planes. Nominally these are stationed in pairs every 20 miles. But there is no need for a group commander to assign planes from the main group to fall behind.

All the planes understand that when they are twenty miles past the last relay position, they need another relay pair. So as soon as they reach the 20 mile point they announce that they are going to drop back. 

If they all have identical programming they might all volunteer at the same time. But of course that won't work. The planes do not volunteer if someone else has already.

That is - unless they are better suited. In this example, a formation of identical planes might be deciding who will go to the relay point. Plane A might volunteer, but Plane B might volunteer instead, and announce that it is closer to the point. 

Essentially it is an auction, to see which plane is the most eager to take the assignment. 

Eagerness should be influenced by factors like -

• Proximity (closer is better)
• Fitness for other tasks (a radio sniffer that is needed at the front should not be wasted on relay tasks)
• Condition (maybe the radio sniff payload is broken.)

It will not be easy to build a system that weighs these types of variables (some unknowable) and ranks candidate planes according to their cost to the group's mission. 

But such an evaluation would need to be performed by a commander plane anyway. If all the planes use the same algorithms, their eagerness bids are perfectly fair comparable. The "eager volunteers" auction will come up with as good a result - or better - than the 'squadron leader' approach.  Since the calculations are being done in parallel by each plane, detailed decision making can happen very quickly. Most importantly, the bandwidth requirements of the auction are tremendously reduced, since each candidate plane needs to transmit only one value (eagerness) rather than the whole battery of statistics that were used to derive it (remaining fuel, physical condition,  position, etc, etc)

Further Work

Simulation

This 'eagerness auction' has not yet been put into code. Next month, we will simulate the process for a task like establishing the relay communications line with a single, simple metric of eagerness (like distance).

Later we will begin to establish methods to weigh various factors in various different domains. 

Delay and Backoff

Bandwidth efficiencies will occur when the bidding is minimized. This means that unlikely candidates should not bid early. If they are outbid before they even start,  they do not block up the channel. W e need good rules to help the planes determine their relative fitness (without calculating the eagerness of every swarm-mate) and to translate this estimate to an appropriate delay time.

Parties

Choosing  the best candidate for a simple one-plane task is not terribly difficult. But we expect to extend this technique to much more complicated tasks, one that require multiple planes taking responsibility for portions of a job - either sequential or simultaneous steps in a process.

Our goal, naturally, is to develop a sturdy method for coordinating these compound tasks. and to apply that technique for the entire mission.

Related Topics

Of course the bidding depends on a  sturdy network with good topology. But the establishment of the network itself can illustrate this basic principle.

A good evaluation of 'eagerness' will involve almost every other interesting  topic in this project, such as way finding, self-examination, hierarchy of needs, etc .