# Team Coordination on Graphs: Problem, Analysis, and Algorithms

arXiv: https://arxiv.org/abs/2403.15946 · HTML: https://mlsanity.com/paper/2403.15946/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Mar 2024.

## Built on by (most cited first, 2 of 2)

- [Grounded Curriculum Learning](https://mlsanity.com/paper/2409.19816/) (2024)
- [GACL: Grounded Adaptive Curriculum Learning with Active Task and Performance Monitoring](https://mlsanity.com/paper/2508.02988/) (2025)

## Abstract (arXiv)

Team Coordination on Graphs with Risky Edges (TCGRE) is a recently emerged problem, in which a robot team collectively reduces graph traversal cost through support from one robot to another when the latter traverses a risky edge. Resembling the traditional Multi-Agent Path Finding (MAPF) problem, both classical and learning-based methods have been proposed to solve TCGRE, however, they lacked either computational efficiency or optimality assurance. In this paper, we reformulate TCGRE as a constrained optimization problem and perform a rigorous mathematical analysis. Our theoretical analysis shows the NP-hardness of TCGRE by reduction from the Maximum 3D Matching problem and that efficient decomposition is a key to tackle this combinatorial optimization problem. Furthermore, we design three classes of algorithms to solve TCGRE, i.e., Joint State Graph (JSG) based, coordination based, and receding-horizon sub-team based solutions. Each of these proposed algorithms enjoy different provable optimality and efficiency characteristics that are demonstrated in our extensive experiments.