# Optimal and Bounded Suboptimal Any-Angle Multi-agent Pathfinding

arXiv: https://arxiv.org/abs/2404.16379 · HTML: https://mlsanity.com/paper/2404.16379/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 33 references that are in the map.
- First posted on arXiv 25 Apr 2024.

## Builds on (most cited first, 17 of 17)

- [Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks](https://mlsanity.com/paper/1906.08291/) (2019)
- [Searching with Consistent Prioritization for Multi-Agent Path Finding](https://mlsanity.com/paper/1812.06356/) (2018)
- [Lifelong Path Planning with Kinematic Constraints for Multi-Agent Pickup and Delivery](https://mlsanity.com/paper/1812.06355/) (2018)
- [Theta*: Any-Angle Path Planning on Grids](https://mlsanity.com/paper/1401.3843/) (2014)
- [Feasibility Study: Moving Non-Homogeneous Teams in Congested Video Game Environments](https://mlsanity.com/paper/1710.01447/) (2017)
- [Representation-Optimal Multi-Robot Motion Planning using Conflict-Based Search](https://mlsanity.com/paper/1909.13352/) (2019)
- [Optimal Multi-Robot Path Planning on Graphs: Complete Algorithms and Effective Heuristics](https://mlsanity.com/paper/1507.03290/) (2015)
- [Any-Angle Pathfinding for Multiple Agents Based on SIPP Algorithm](https://mlsanity.com/paper/1703.04159/) (2017)
- [Improving Continuous-time Conflict Based Search](https://mlsanity.com/paper/2101.09723/) (2021)
- [Conflict-based Search for Multi-Robot Motion Planning with Kinodynamic Constraints](https://mlsanity.com/paper/2207.00576/) (2022)
- [Multi-Agent Motion Planning with B'ezier Curve Optimization under Kinodynamic Constraints](https://mlsanity.com/paper/2311.14145/) (2023)
- [Prioritized Multi-agent Path Finding for Differential Drive Robots](https://mlsanity.com/paper/1911.10578/) (2019)
- [CL-MAPF: Multi-Agent Path Finding for Car-Like Robots with Kinematic and Spatiotemporal Constraints](https://mlsanity.com/paper/2011.00441/) (2020)
- [db-CBS: Discontinuity-Bounded Conflict-Based Search for Multi-Robot Kinodynamic Motion Planning](https://mlsanity.com/paper/2309.16445/) (2023)
- [Towards Time-Optimal Any-Angle Path Planning With Dynamic Obstacles](https://mlsanity.com/paper/2104.06681/) (2021)
- [Collision Detection for Agents in Multi-Agent Pathfinding](https://mlsanity.com/paper/1908.09707/) (2019)
- [Prioritized SIPP for Multi-Agent Path Finding With Kinematic Constraints](https://mlsanity.com/paper/2108.05145/) (2021)

## Built on by (most cited first, 2 of 2)

- [Solution Space Path Planning: A Real-Time Human-Centered Path Planning Algorithm for En-Route Air Traffic Control](https://mlsanity.com/paper/2607.00064/) (2026)
- [Optimal any-angle path planning in static and dynamic environments](https://mlsanity.com/paper/2607.00065/) (2026)

## Abstract (arXiv)

Multi-agent pathfinding (MAPF) is the problem of finding a set of conflict-free paths for a set of agents. Typically, the agents' moves are limited to a pre-defined graph of possible locations and allowed transitions between them, e.g. a 4-neighborhood grid. We explore how to solve MAPF problems when each agent can move between any pair of possible locations as long as traversing the line segment connecting them does not lead to a collision with the obstacles. This is known as any-angle pathfinding. We present the first optimal any-angle multi-agent pathfinding algorithm. Our planner is based on the Continuous Conflict-based Search (CCBS) algorithm and an optimal any-angle variant of the Safe Interval Path Planning (TO-AA-SIPP). The straightforward combination of those, however, scales poorly since any-angle path finding induces search trees with a very large branching factor. To mitigate this, we adapt two techniques from classical MAPF to the any-angle setting, namely Disjoint Splitting and Multi-Constraints. Experimental results on different combinations of these techniques show they enable solving over 30% more problems than the vanilla combination of CCBS and TO-AA-SIPP. In addition, we present a bounded-suboptimal variant of our algorithm, that enables trading runtime for solution cost in a controlled manner.