協調タスク割当・順序決定とマルチエージェント経路探索の統合手法
Collaborative Task Assignment, Sequencing and Multi-agent Path-finding
複数エージェントが衝突せずにタスク地点を訪問する問題(TSPF)に対し、MILPによるタスク順序最適化とCBSによる経路計画を組み合わせた最適・完全アルゴリズムCBS-TSを提案し、既存手法より高い成功率と最適性を示した。
詳しい要約
1. どんなもの？
2. 先行研究と比べてどこがすごい？
3. 技術・手法の肝は？
4. どうやって有効だと検証した？
5. 議論はある？
6. 次に読むべき論文は？
※ AIが要旨から生成した要約です。正確性は原文をご確認ください。
著者: Yifan Bai, Shruti Kotpalliwar, Christoforos Kanellakis, George Nikolakopoulos
分類: cs.MA, cs.RO
原文アブストラクト
In this article, we address the problem of collaborative task assignment, sequencing, and multi-agent pathfinding (TSPF), where a team of agents must visit a set of task locations without collisions while minimizing flowtime. TSPF incorporates agent-task compatibility constraints and ensures that all tasks are completed. We propose a Conflict-Based Search with Task Sequencing (CBS-TS), an optimal and complete algorithm that alternates between finding new task sequences and resolving conflicts in the paths of current sequences. CBS-TS uses a mixed-integer linear program (MILP) to optimize task sequencing and employs Conflict-Based Search (CBS) with Multi-Label A* (MLA*) for collision-free path planning within a search forest. By invoking MILP for the next-best sequence only when needed, CBS-TS efficiently limits the search space, enhancing computational efficiency while maintaining optimality. We compare the performance of our CBS-TS against Conflict-based Steiner Search (CBSS), a baseline method that, with minor modifications, can address the TSPF problem. Experimental results demonstrate that CBS-TS outperforms CBSS in most testing scenarios, achieving higher success rates and consistently optimal solutions, whereas CBSS achieves near-optimal solutions in some cases. The supplementary video is available at https://youtu.be/QT8BYgvefmU.
