Decentralizedmulti-UAVtask allocation
Trajectory tasks, consensus instead of a coordinator, and what decentralization actually costs you.
The operation, not the benchmark
What a wilderness search actually demands of a planner.
Why multiple UAVs at all
Search and rescue is a race against a survival curve. Coverage rate is the whole game.
- Parallel coverage. A search area is covered faster when several UAVs fly it at once — that is the entire premise, and it holds.
- Terrain bias matters. Lost people are found near ditches, tree lines and water edges, not uniformly across a polygon.
- The operator is one person. Whatever the system needs, it cannot need a second specialist on the ground.
The constraint that shapes everything
Radio links between UAVs drop. Ground stations lose sight. Aircraft abort mid-mission and come home on low battery.
A planner that assumes a reliable central coordinator is a planner that assumes the easy case.
Coverage planning is mostly centralized
The results are strong. The deployment assumptions are optimistic.
Single point of failure
Lose the coordinator and the fleet has no plan and no way to make one.
Replanning is a round trip
Every change of circumstance has to travel to the centre and back before anyone acts.
Scaling is the coordinator's problem
Adding UAVs adds load and latency exactly where you can least afford it.
Tasks with a direction
One change to the task model does most of the work.
Trajectories, not points
A task is a path between two points — and which end you start from is part of what the allocator decides.
Generalizing CBBA
The consensus-based bundle algorithm, extended so a bid covers a directed trajectory.
- Bundle construction. Each UAV greedily builds a bundle of tasks it thinks it can serve cheaply, scoring both traversal directions.
- Consensus. Neighbours exchange bids and winning-bid timestamps; conflicts resolve locally, with no coordinator in the loop.
- Convergence. The fleet settles on a conflict-free allocation, and any UAV can leave or join and trigger a re-bid.
What stays the same
CBBA's convergence guarantees and its communication pattern.
What changes
The scoring function, which now optimizes traversal direction as it bids.
- Decentralized Multi-UAV Trajectory Task Allocation in Search and Rescue Applications · ICAR 2023
- TrajAllocPy — reference implementation
What it costs
Decentralization is a trade. Here is the bill.
Results on benchmark problems
Simulation experiments against a state-of-the-art centralized coverage planner.
Overhead vs centralized
Time to completion is essentially the same as the centralized planner — for that overhead cost.
Better than point allocation
Optimizing traversal direction beats treating the same coverage tasks as points.
Scales with fleet size
Performance holds as UAVs are added to the search effort — no coordinator to saturate.
- Decentralized Multi-UAV Trajectory Task Allocation in Search and Rescue Applications · ICAR 2023
- TrajAllocPy — reference implementation
Three things to take away
1 · Model the task properly
Direction was free information sitting outside the allocator. Moving it inside was worth 6%.
2 · Decentralization is cheap here
1.9% overhead against a centralized planner, and no coordinator to lose in the field.
3 · Field constraints come first
The comms assumption decides the architecture. Everything else follows from it.
Code & paper
github.com/kasperg3/trajallocpy
ICAR 2023, IEEE
grontved.xyz/publications.html