協調的タイムドロードマップによる連続空間マルチエージェント経路計画
CTRMs: Learning to Construct Cooperative Timed Roadmaps for Multi-agent Path Planning in Continuous Spaces
複数エージェントの衝突回避と時間方向を考慮したロードマップ(CTRM)を生成モデルで学習・構築し、連続空間の経路計画を効率化した研究。
著者: Keisuke Okumura, Ryo Yonetani, Mai Nishimura, Asako Kanezaki
分類: cs.MA, cs.LG, cs.RO
原文アブストラクト
Multi-agent path planning (MAPP) in continuous spaces is a challenging problem with significant practical importance. One promising approach is to first construct graphs approximating the spaces, called roadmaps, and then apply multi-agent pathfinding (MAPF) algorithms to derive a set of conflict-free paths. While conventional studies have utilized roadmap construction methods developed for single-agent planning, it remains largely unexplored how we can construct roadmaps that work effectively for multiple agents. To this end, we propose a novel concept of roadmaps called cooperative timed roadmaps (CTRMs). CTRMs enable each agent to focus on its important locations around potential solution paths in a way that considers the behavior of other agents to avoid inter-agent collisions (i.e., "cooperative"), while being augmented in the time direction to make it easy to derive a "timed" solution path. To construct CTRMs, we developed a machine-learning approach that learns a generative model from a collection of relevant problem instances and plausible solutions and then uses the learned model to sample the vertices of CTRMs for new, previously unseen problem instances. Our empirical evaluation revealed that the use of CTRMs significantly reduced the planning effort with acceptable overheads while maintaining a success rate and solution quality comparable to conventional roadmap construction approaches.
関連論文
- 異種グラフニューラルネットワークを用いたマルチエージェント経路計画のための共有ロードマップ生成と評価マルチエージェント経路計画
- エレベーター付きマルチエージェント経路探索のための競合ベース探索マルチエージェント経路計画
- 可動障害物を含むマルチエージェント経路探索のための競合ベース探索と優先度計画マルチエージェント経路計画
- 階層型LA-MAPF:大規模エージェントMAPF問題の分解による解法高速化マルチエージェント経路計画
- 自動倉庫における実ロボットダイナミクスと相互依存タスクを考慮したマルチエージェント経路計画マルチエージェント経路計画
- 行き詰まりからの脱出:デッドロック回復アプローチマルチエージェント経路計画
