経路見通しに基づく優先順位付けによるマルチロボット経路衝突解消
Multi-Robot Path Deconfliction through Prioritization by Path Prospects
各ロボットが現在地から目標へ到達する経路の見通し（ホモロジー類の数）をオンラインで計算し、それを優先順位として分散経路計画の交渉に用いることで、衝突のない経路計画を実現する手法を提案した。
著者: Wenying Wu, Subhrajit Bhattacharya, Amanda Prorok
分類: cs.RO
原文アブストラクト
This work deals with the problem of planning conflict-free paths for mobile robots in cluttered environments. Since centralized, coupled planning algorithms are computationally intractable for large numbers of robots, we consider decoupled planning, in which robots plan their paths sequentially in order of priority. Choosing how to prioritize the robots is a key consideration. State-of-the-art prioritization heuristics, however, do not model the coupling between a robot's mobility and its environment. In this paper, we propose a prioritization rule that can be computed online by each robot independently, and that provides consistent, conflict-free path plans. Our innovation is to formalize a robot's path prospects to reach its goal from its current location. To this end, we consider the number of homology classes of trajectories, and use this as a prioritization rule in our decentralized path planning algorithm, whenever any robots enter negotiation to deconflict path plans. This prioritization rule guarantees a partial ordering over the robot set. We perform simulations that compare our method to five benchmarks, and show that it reaches the highest success rate (w.r.t. completeness), and that it strikes the best balance between makespan and flowtime objectives.
