2025/09/18 by Walker Gosrich, Saurav Agarwal, Gosrich, Walker +11
Computer Science · Engineering · #Distributed Control Multi-Agent Systems #FOS: Computer and information sciences #Modular Robots and Swarm Intelligence #Reinforcement Learning in Robotics #Robotics (cs.RO)
paper · pdf · doi:10.48550/arxiv.2509.15052
openalex publication_date 2025/09/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We propose a new formulation for the multi-robot task allocation problem that incorporates (a) complex precedence relationships between tasks, (b) efficient intra-task coordination, and (c) cooperation through the formation of robot coalitions. A task graph specifies the tasks and their relationships, and a set of reward functions models the effects of coalition size and preceding task performance. Maximizing task rewards is NP-hard; hence, we propose network flow-based algorithms to approximate solutions efficiently. A novel online algorithm performs iterative re-allocation, providing robustness to task failures and model inaccuracies to achieve higher performance than offline approaches. We comprehensively evaluate the algorithms in a testbed with random missions and reward functions and compare them to a mixed-integer solver and a greedy heuristic. Additionally, we validate the overall approach in an advanced simulator, modeling reward functions based on realistic physical phenomena and executing the tasks with realistic robot dynamics. Results establish efficacy in modeling complex missions and efficiency in generating high-fidelity task plans while leveraging task relationships.