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, bo...

Full description

Saved in:
Bibliographic Details
Main Authors: Zhou, Yanlin, Limbu, Manshi, Stein, Gregory J., Wang, Xuan, Shishika, Daigo, Xiao, Xuesu
Format: Conference Proceeding
Language:English
Subjects:
Computational efficiency
Costs
Intelligent robots
Learning systems
Mathematical analysis
Optimization
Robot kinematics
Three-dimensional displays
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 enjoys different provable optimality and efficiency characteristics that are demonstrated in our extensive experiments.
ISSN:2153-0866
DOI:10.1109/IROS58592.2024.10802095