تقرير
Team Coordination on Graphs: Problem, Analysis, and Algorithms
| العنوان: | Team Coordination on Graphs: Problem, Analysis, and Algorithms |
|---|---|
| المؤلفون: | Limbu, Manshi, Zhou, Yanlin, Stein, Gregory, Wang, Xuan, Shishika, Daigo, Xiao, Xuesu |
| سنة النشر: | 2024 |
| المجموعة: | Computer Science |
| مصطلحات موضوعية: | Computer Science - 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 computation efficiency or optimality assurance. In this paper, we reformulate TCGRE as a constrained optimization and perform 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. Further more, 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. Comment: 8 pages, 4 figures |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2403.15946 |
| رقم الأكسشن: | edsarx.2403.15946 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |