異種タスク所要時間を考慮したマルチエージェント組合せ経路探索
Multi-Agent Combinatorial Path Finding with Heterogeneous Task Duration
複数エージェントが中間目標を訪問する組合せ経路探索において、エージェントと目標ごとに異なるタスク所要時間を考慮する2手法を提案し、最大20エージェント・50目標で有効性を示した。
著者: Yuanhang Zhang, Xuemian Wu, Hesheng Wang, Zhongqiang Ren
分類: cs.RO
原文アブストラクト
Multi-Agent Combinatorial Path Finding (MCPF) seeks collision-free paths for multiple agents from their initial locations to destinations, visiting a set of intermediate target locations in the middle of the paths, while minimizing the sum of arrival times. While a few approaches have been developed to handle MCPF, most of them simply direct the agent to visit the targets without considering the task duration, i.e., the amount of time needed for an agent to execute the task (such as picking an item) at a target location. MCPF is NP-hard to solve to optimality, and the inclusion of task duration further complicates the problem. This paper investigates heterogeneous task duration, where the duration can be different with respect to both the agents and targets. We develop two methods, where the first method post-processes the paths planned by any MCPF planner to include the task duration and has no solution optimality guarantee; and the second method considers task duration during planning and is able to ensure solution optimality. The numerical and simulation results show that our methods can handle up to 20 agents and 50 targets in the presence of task duration, and can execute the paths subject to robot motion disturbance.
