LaCAM: Search-Based Algorithm for Quick Multi-Agent Pathfinding

doi:10.1609/aaai.v37i10.26377

LaCAM: Search-Based Algorithm for Quick Multi-Agent Pathfinding

2023-06-26

0

OA

AI

DOI：10.1609/aaai.v37i10.26377

原文链接

原文求助

摘要

En 中文

We propose a novel complete algorithm for multi-agent pathfinding (MAPF) called lazy constraints addition search for MAPF (LaCAM). MAPF is a problem of finding collision-free paths for multiple agents on graphs and is the foundation of multi-robot coordination. LaCAM uses a two-level search to find solutions quickly, even with hundreds of agents or more. At the low-level, it searches constraints about agents' locations. At the high-level, it searches a sequence of all agents' locations, following the constraints specified by the low-level. Our exhaustive experiments reveal that LaCAM is comparable to or outperforms state-of-the-art sub-optimal MAPF algorithms in a variety of scenarios, regarding success rate, planning time, and solution quality of sum-of-costs.

LaCAM: Search-Based Algorithm for Quick Multi-Agent Pathfinding

摘要

期刊

机构

引用论文