Multidemic: distributed tasking
Task allocation across multiple unmanned aerial vehicle (UAV) agents can be best achieved by considering ‘demes’, or groups, of possible solutions that can be obtained through UAVs interacting with close neighbours. A range limit of UAV task awareness and communication can also offer performance benefits by reducing competition for tasks among UAVs and keeping decisions simple.
Project team: Thomas Kent, Arthur Richards and Angus Johnson
The UAV travelling salesman
The capabilities of unmanned aerial vehicles (UAVs) make them highly attractive for search and rescue, package delivery, and surveillance. However, efficient operation requires that the allocated order of tasks for UAVs minimises their overall distance travelled. This is an example of the classic ‘travelling salesman’ problem.
Further complications arise from:
- Using multiple UAVs in the same area as this can result in them vying for the same tasks, leading to inefficiencies.
- New tasks appearing, which means task ordering lists for UAVs must be continually updated.
- The geography of the operational environment restricting communications between UAVs and a central control hub.
We have investigated practical ways of managing this challenging task allocation process using simulations of UAVs with realistic capabilities and limitations.
Demes: making tasks local
Evolutionary algorithms can improve task allocations held by agents by randomly swapping, reordering, and exchanging tasks in lists to find arrangements that improve performance. This can be computationally demanding, though, particularly in situations where new tasks continually appear.
We investigated whether a more lightweight computational approach might be achieved by creating segregated groupings, or demes, of possible mutations of task ordering that involve agents that were geographically close to each other. Evolutionary algorithms would then only consider new list mutations found within the same deme.
We simulated three methods of live task ordering:
- The standard approach of the entire task population considered together (no task demes) and centralised updates to task ordering
- Multiple solution demes and centralised task ordering
- Multiple solution demes and decentralised, local task ordering
The performance of each method was measured by the distance travelled by UAVs. The accompanying computational time to find a solution was also measured.
Geographically challenging environments were simulated in method 3 by limiting the UAV vision range over which they could see tasks appear, and the communication range between UAVs.
Demes for faster operation
For reasonable numbers of agents and tasks, multiple demes and decentralised control (method 3) offered similar performance to other methods but reduced computational run time significantly compared to when multiple demes were controlled centrally (method 2). However, method 3 operated fastest overall when considering its total run time divided across the multiple agents present.
This is a surprising result: segregating possible task-ordering solutions into demes and operating UAVs with limited vision and communication range offers improved computational performance over centralised control with unlimited oversight.
For moderate communication ranges, the decentralised, multi-deme approach also matched or outperformed the standard approach of method 1 in terms of UAV distance travelled.
Realistic capabilities keep things simple
The seemingly counterintuitive result that restricting UAV communication and vision when using demes of possible solutions can improve performance appears due to UAVs having a more limited set of options to consider and reducing task competition between UAVs.
The simple approaches used here avoid the need for cumbersome computation while maintaining agent performance. This outcome is good news for multi-agent UAV operations: the very limitations presented by geography and hardware can improve task allocation.