Dynamic Multi-Robot Task Allocation under Uncertainty and Communication Constraints: A Game-Theoretic Approach

arXiv cs.RO / 4/15/2026

💬 OpinionSignals & Early TrendsIdeas & Deep AnalysisModels & Research

共有:

Key Points

The paper addresses dynamic multi-robot task allocation where tasks arrive online, must satisfy deadlines/time windows, and complete outcomes are uncertain.
It incorporates incomplete information via hub-based sensing regions (task visibility depends on where robots are) and a communication graph (limits how information is shared between hubs).
The authors propose a decentralized Iterative Best Response (IBR) policy where each agent greedily chooses the task that maximizes its marginal contribution to the locally observed welfare.
Experiments on a city-scale package-delivery simulation with up to 100 drones compare IBR to EDD, Hungarian assignment, and SCoBA across different task arrival patterns.
Results show that IBR performs competitively under both full and sparse communication while reducing computation time relative to the baselines.

Abstract

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.