Team Coordination on Graphs: Problem, Analysis, and Algorithms
<|reference_start|>Team Coordination on Graphs: Problem, Analysis, and Algorithms: 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.<|reference_end|>
@article{zhou2024team,
    title={Team Coordination on Graphs: Problem, Analysis, and Algorithms},
    author={Yanlin Zhou, Manshi Limbu, Gregory J. Stein, Xuan Wang, Daigo
  Shishika, and Xuesu Xiao},
    journal={arXiv preprint arXiv:2403.15946},
    year={2024},
    archivePrefix={arXiv},
    eprint={2403.15946},
    primaryClass={cs.MA}
}