Online Multi-Robot Coordination and Cooperation with Task Precedence Relationships

Walker Gosrich, Saurav Agarwal, Kashish Garg, Siddharth Mayya · 2025

Read Online Multi-Robot Coordination and Cooperation with Task Precedence Relationships by Walker Gosrich, Saurav Agarwal, Kashish Garg, Siddharth Mayya (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-15052.txt.

Introduction

Walker Gosrich and six co-authors coordinate teams of robots whose tasks depend on each other in order, in a 2025 multi-robot systems paper. A task graph spells out precedence: some jobs must finish before others start. Robots may also team up in coalitions, and reward functions capture how coalition size and earlier task outcomes affect later success.

Maximizing total reward is NP-hard, so exact solutions are out of reach for large missions. The authors give network flow-based approximation algorithms instead. Their online algorithm reallocates tasks repeatedly as events unfold, which proves robust to task failures and modeling errors, beating offline plans fixed in advance. Tests span randomized missions, comparison with a mixed-integer solver and a greedy heuristic, and a realistic simulator with physics-based rewards.

Catalog record

CREATORWalker Gosrich, Saurav Agarwal, Kashish Garg, Siddharth Mayya
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE104 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-15052

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Online Multi-Robot Coordination and Cooperation with Task Precedence Relationships Thanks: The work was supported by ARL DCIST CRA W911NF-17-2-0181 and NSF Award 2415249. This material is based upon work supported by the National Science Foundation Graduate Research Fellowship. Thanks: W. Gosrich, S. Agarwal, K. Garg, M. Yim, and V. Kumar are with the GRASP Laboratory, University of Pennsylvania, Philadelphia, PA, USA. { gosrich , sauravag , kashg , yim , kumar }@seas.upenn.edu Thanks: S. Mayya is with Amazon Robotics, North Reading, MA, USA. Thanks: M. Malencia is with Zipline, San Francisco, CA, USA. Thanks: This work is not related to Amazon or Zipline. Walker Gosrich, Saurav Agarwal, Kashish Garg, Siddharth Mayya Abstract 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. I Introduction Fig. 1: The task graph ( bottom ) shows precedence relationships between tasks in a mission. Highlighted is a subset of tasks, showing coalition functions ( red ) on task nodes and precedence relationships ( blue ) on edges. For example, before transporting construction materials, robots may need to find or clear paths through a debris-filled construction site. The quality of these paths directly impacts the team’s ability to transport material. Furthermore, the performance of transporting materials, e.g., whether materials get damaged, impacts the quality and speed of a following construction task. Large-scale missions often comprise several tasks that have precedence relationships among them, i.e., the quality of a task’s execution may depend on how well a related task is executed, which need not be a simple binary relationship. Additionally, task outcomes are often uncertain products of complex interactions between robots and the environment. As an example, the illustration in Fig. 1 shows an autonomous construction mission where transport paths must be identified and cleared, and materials transported before construction takes place. In such a scenario, the quality with which prior tasks are completed impacts the ability of a robot coalition to complete future tasks, e.g., well-cleared paths will permit more agents to transport materials through. Furthermore, tasks such as collaborative carry require multiple robots to work together to complete the task when a single robot cannot, whereas other tasks, such as exploration for transport pathfinding, may see improved results from multiple robots working together. A fundamental challenge in such missions is to efficiently execute the tasks to maximize the cumulative reward, while respecting additional resource constraints such as time and robot availability. This optimization problem is NP-hard and belongs to a broader class of multi-robot task allocation (MRTA) problems. Approaches for such problems must compute robot coalitions to collaboratively execute individual tasks and an allocation of these coalitions to various tasks. Accomplishing this requires a model of the expected performance of a given coalition assigned to a task, and a model of the relationships among tasks, especially the influence of a preceding task on subsequent tasks. The complex relationships among tasks and robots are critical in real-world applications, but have not been addressed in the literature in a unified manner, owing to the modeling complexity and computational challenges. The second fundamental challenge in executing a mission is uncertainty due to the dynamic nature of the environment, inaccuracies in the mission model due to sim-to-real gaps, and robot failures. While an offline solution can be computed before the mission execution, it may not be robust to these uncertainties. On the other hand, an online solver that can re-plan in response to actual task outcomes is more robust to uncertainties and failures. For example, a task B may be highly dependent on the quality of the execution of a preceding task A. If task A fails or performs poorly, it may be advantageous to reallocate robot resources away from task B. However, as the problem is NP-hard, an optimal approach such as a mixed-integer non-linear program (MINLP) can be computationally expensive to execute in real time after every individual task completion. Hence, an online algorithm that effectively trades off solution quality and computational complexity for real-time execution while being adaptive to uncertainties and failures is desirable. This article presents a novel formulation for modeling large-scale multi-robot missions via precedence relationships among tasks, as well as coordination and cooperation among robots through coalitions. We present an online iterative algorithmic framework that leverages this model for allocating coalitions to tasks and adapting to task failures and uncertainty. The formulation is applicable to complex scenarios relevant to autonomous construction, precision agriculture, and industrial robotic applications. The contributions are: 1. A modular and expressive mission model defined over a task graph and a reward function ( Section III ). The task graph captures the precedence relationships among tasks. The reward function quantifies task utilities and is characterized by influence functions —modeling of relationships among tasks, aggregation functions —effect of all preceding tasks on a dependent task, and coalition functions —modeling of task execution efficacies with robot coalition size. 2. A non-linear network flow formulation along with offline and online iterative algorithms that efficiently form coalitions and allocate them to tasks while leveraging the task precedence relationships ( Section IV ). The online algorithm enables replanning in response to actual task outcomes, making it adaptive to task failures and inaccuracies in the mission model. 3. A new testbed for mission models to randomly generate task graphs with complex rewards and precedence relationships, which facilitates extensive evaluation of the proposed algorithms. The results show that the online algorithm computes solutions close to optimal (determined via the MINLP solver run for 12 hours) for small problem sizes and significantly outperforms baselines for large problem sizes with and without stochastic task failures and model inaccuracies. 4. A Unity-based testbed with four canonical tasks—coverage control, exploration, resource transportation, and collaborative carry—to form large-scale missions in realistic urban environments with large robot teams ( Section VI ). Test missions of varying sizes and numbers of agents show that the proposed formulation is able to accurately ( < 20% error) model task rewards in complex scenarios, and the online solver is able to leverage task reward feedback to provide robust mission performance. This article extends our work in [ 1 ] , which introduced the task graph mission model, greedy and non-linear programming (NLP) flow-based solution methods, and a mixed integer non-linear programming (MINLP) solution method. In particular, this article introduces an online iterative flow-based

Read the complete text