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

doi:10.1109/TASE.2024.3466183

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

2024-01-01

0

PRE

AI

DOI：10.1109/TASE.2024.3466183

原文链接

原文求助

摘要

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.

Keyword:

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

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

摘要

期刊

机构

引用论文