Dynamic Multi-Robot Task Allocation under Uncertainty and Communication Constraints: A Game-Theoretic Approach
Authors: Maria G. Mendoza, Pan-Yang Su, Bryce L. Ferguson, S. Shankar Sastry
Organizations: Department of Mechanical Engineering, University of California, Berkeley, Berkeley, CA, United States · Department of Electrical Engineering and Computer Science, University of California, Berkeley, Berkeley, CA, United States · Thayer School of Engineering, Dartmouth College, Hanover, NH, United States
We study dynamic multi-robot task allocation under uncertain task completion, time-window constraints, and incomplete information. Tasks arrive online over a finite horizon and must be completed within specified deadlines, while agents operate from distributed hubs with limited sensing and communication. We model incomplete information through hub-based sensing regions that determine task visibility and a communication graph that governs inter-hub information exchange. Using this framework, we propose Iterative Best Response (IBR), a decentralized policy in which each agent selects the task that maximizes its marginal contribution to the locally observed welfare. We compare IBR against three baselines: Earliest Due Date first (EDD), Hungarian algorithm, and Stochastic Conflict-Based Allocation (SCoBA), on a city-scale package-delivery domain with up to 100 drones and varying task arrival scenarios. Under full and sparse communication, IBR achieves competitive task-completion performance with lower computation time.
Figures & tables
Fig. 1 : Decentralized multi-hub architecture. Each hub acts as a local planner coordinating its assigned drones. Shaded regions represent hub-based sensing areas that determine task visibility. Overlapping sensing regions imply that certain tasks may be simultaneously visible to multiple hubs.
Fig. 2 : Package generation zones of varying size controlling task conflict density. (a) A large generation zone disperses tasks across the environment, reducing hub overlap and inter-agent conflict, but increasing expected travel times and task completion uncertainty. (b) A medium zone concentrates tasks in a region visible to multiple hubs, producing a moderate level of conflict and intermediate travel distances. (c) A small zone places nearly all tasks within the sensing regions of several hubs simultaneously, maximizing conflict but reducing travel time and stochastic execution uncertainty.
Fig. 3 : Directed and Undirected Graph Topologies.
Fig. 4 : System performance across four algorithms under full communication, each column varying one parameter (100 trials each). Top row: mean fraction of late packages. Bottom row: avg. computation time per planning step (log scale).
Fig. 5 : Distribution of the fraction of late packages across communication graph topologies for EDD, Hungarian, and IBR (100 trials, 5 depots, 15 drones).
Fig. 6 : Efficiency ratio of IBR across several parameter sweeps as a function of the communication graph structure. Scenarios include high request probability ( p=1.0 ), long service windows ( w=45 ), high spatial conflict, and a nominal configuration (5 depots, 15 drones).