.png){kind=icon}
.png){kind=icon}
Return
A Bounded Sub-Optimal Approach for Multi-Agent Combinatorial Path Finding
.png){kind=icon}
PRE
AI
DOI：10.1109/TASE.2024.3466183.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Multi-Agent Path Finding () seeks collision-free paths for multiple agents from start to goal locations. This paper considers a generalization of called Multi-Agent Combinatorial Path Finding () where agents must collectively visit a set of intermediate target locations before reaching their goals. 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 () is developed to solve to optimality, which, however, does not scale well when the number of agents or targets is large (e.g. 50 targets). While 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 for target sequencing (A for Approximation and K* for K-best), which leverages approximation algorithms for traveling salesman problems. is motivated by, but is a standalone method that can solve K-best routing problems in general. We prove that has worst-case polynomial runtime complexity and finds bounded sub-optimal solutions. With, we develop two variants that find bounded sub-optimal paths for . Our results verify the fast running speeds of our methods with up to 200 targets.
Keywords:
Approximation algorithms
Sequential analysis
Runtime
Collision avoidance
Planning
Partitioning algorithms
Traveling salesman problems
Polynomials
Routing
Mobile robots
Path planning
multi-robot systems
traveling salesman problems
Journal
IF:
6.4
Papers:
4.9K
Citations:
1.6W