A Bounded Sub-Optimal Approach for Multi-Agent Combinatorial Path Finding

摘要

Multi-Agent Path Finding (MAPF) seeks collision-free paths for multiple agents from start to goal locations. This paper considers a generalization of MAPF called Multi-Agent Combinatorial Path Finding (MCPF) where agents must collectively visit a set of intermediate target locations before reaching their goals. MCPF is challenging as it involves both planning collision-free paths for multiple agents and target sequencing, i.e., assigning targets to and computing the visiting order for each agent. A recent method Conflict-Based Steiner Search (<monospace xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">CBSS</monospace>) is developed to solve MCPF to optimality, which, however, does not scale well when the number of agents or targets is large (e.g. 50 targets). While MAPF research has developed methods to plan bounded sub-optimality paths for many agents, it remains unknown how to find bounded sub-optimal solutions in the presence of many targets. This paper fills this gap by developing a method <monospace xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">AK*</monospace> for target sequencing (A for Approximation and K* for K-best), which leverages approximation algorithms for traveling salesman problems. <monospace xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">AK*</monospace> is motivated by MCPF, but is a standalone method that can solve K-best routing problems in general. We prove that <monospace xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">AK*</monospace> has worst-case polynomial runtime complexity and finds bounded sub-optimal solutions. With <monospace xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">AK*</monospace>, we develop two <monospace xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">CBSS</monospace> variants that find bounded sub-optimal paths for MCPF. Our results verify the fast running speeds of our methods with up to 200 targets. Note to Practitioners—The motivation of this paper originates from the need to plan conflict-free paths for multiple mobile robots in cluttered environment in warehouse logistics, manufacturing and inspection. While existing methods for multi-agent planning typically consider finding paths from starts to goals, this paper investigates the case, where agents must collectively visit a set of intermediate target locations before reaching their goals, for the purpose of inspection, picking or placing parts, etc. To solve the problem, this paper first develops an algorithm to find K-best solutions for traveling salesman problems with bounded sub-optimality, which then leads to two multi-agent planners that can handle hundreds of targets and tens of agents. We provide a Gazebo simulation to showcase the usage of the planner in a warehouse like environment.