Team Coordination on Graphs: Problem, Analysis, and Algorithms
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866913472952926208 |
|---|---|
| author | Zhou, Yanlin Limbu, Manshi Stein, Gregory J. Wang, Xuan Shishika, Daigo Xiao, Xuesu |
| author_facet | Zhou, Yanlin Limbu, Manshi Stein, Gregory J. Wang, Xuan Shishika, Daigo Xiao, Xuesu |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_15946 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Team Coordination on Graphs: Problem, Analysis, and Algorithms Zhou, Yanlin Limbu, Manshi Stein, Gregory J. Wang, Xuan Shishika, Daigo Xiao, Xuesu Multiagent Systems 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. |
| title | Team Coordination on Graphs: Problem, Analysis, and Algorithms |
| topic | Multiagent Systems |
| url | https://arxiv.org/abs/2403.15946 |