Local Visibility Roadmaps in Continous Multi-agent Path Finding
Organizations: Czech Technical University in Prague, Faculty of Information Technology, Thákurova 9, 160 00 Praha 6, Czechia
Abstract
We address the problem of smooth continuous multi-agent path finding (SC-MAPF), where agents move in a continuous environment along smooth curves in continuous time. The paths for individual agents are searched in local visibility roadmaps that consider obstacles and other agents. A new algorithm is proposed in this work, which combines the previous algorithm CE-CBS for high-level search with any-angle path finding for local single-agent planning, where agents are to avoid obstacles, both static and other agents. The new algorithm is tested and compared to CE-CBS, the algorithm building individual paths using RRT, and SMT-CCBS algorithm, an algorithm for MAPF. Experimental results show various advantages of the new algorithm over CE-CBS and SMT-CCBS in comparable settings.
Figures & tables
| Instance | VR-CBS SOC | CE-CBS SOC |
|---|---|---|
| Figure 5 - 4 agents | 1992.2 | 2025 |
| Figure 6 - maze | 2034.5 | 2062 |
| Figure 7 - switch | 1553.6 | 1632 |
Multi-Agent Path Finding
Multi-agent path finding (MAPF) plans collision-free routes for multiple agents sharing an environment.
See all 100 papers