UC Berkeley's IBR Beats Centralized Drone Planners While Running 100x Faster
A UC Berkeley team turns city-scale drone dispatch into a local best-response game, matching centralized planners at a fraction of the compute.
ProTakeaways
- Berkeley and Dartmouth propose Iterative Best Response, a decentralized policy for dynamic multi-robot task allocation.
- Each agent picks the task maximizing its marginal contribution to locally observed welfare.
- Tested on North San Francisco drone delivery with up to 100 drones and 10 depots.
- Matches centralized SCoBA completion rates at roughly 1/100th the compute time.
- Efficiency ratio stays above 0.98 until depots are fully isolated from each other.
- Current model assumes homogeneous drones and single-robot tasks; code release planned.
Coordinating a fleet of delivery drones sounds like a solved problem until the messy parts show up: packages appear at random times, travel takes an unpredictable amount of time, deadlines are tight, and depots cannot always talk to each other. A new paper from researchers at UC Berkeley and Dartmouth attacks that combination with a lightweight game-theoretic policy called Iterative Best Response (IBR), and shows it can match centralized planners while running roughly a hundred times faster.
The setup nobody wants to plan for
The authors study dynamic multi-robot task allocation under uncertain completion times, time-window constraints, and incomplete information. Jobs arrive online over a finite horizon and must be finished within specified deadlines, while agents operate from distributed hubs with limited sensing and communication. In plain terms, drones live at depots, see delivery requests only inside a local sensing radius, and can exchange plans only with the depots they are wired to talk to.
That last constraint is the interesting one. Game-theoretic coordination mechanisms appear in fewer than 3% of reviewed decentralized allocation works. Most prior systems assume that once a drone claims a package, everyone else instantly knows. In real cities, with multiple providers and patchy links, that assumption breaks.