Publication

Z. Ren, S. Rathinam and H. Choset. A Bounded Sub-Optimal Approach for Multi-Agent Combinatorial Path Finding. IEEE Transactions on Automation Science and Engineering, 1-16, 2024.

Abstract: Multi-Agent Path Finding (MAPF) seeks collisionfree 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 (CBSS) 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 AK* for target sequencing (A for Approximation and K* for K-best), which leverages approximation algorithms for traveling salesman problems. AK* is motivated by MCPF, but is a standalone method that can solve K-best routing problems in general. We prove that AK* has worst-case polynomial runtime complexity and finds bounded sub-optimal solutions. With AK*, we develop two CBSS variants that find bounded sub-optimal paths for MCPF. Our results verify the fast running speeds of our methods with up to 200 targets.

Download the paper in pdf.