# Pathfinding with Lazy Successor Generation

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 37 references that are in the map.
- First posted on arXiv 27 Aug 2024.

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

- [Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks](https://mlsanity.com/paper/1906.08291/) (2019)
- [LaCAM: Search-Based Algorithm for Quick Multi-Agent Pathfinding](https://mlsanity.com/paper/2211.13432/) (2022)
- [Informed RRT*: Optimal Sampling-based Path Planning Focused via Direct Sampling of an Admissible Ellipsoidal Heuristic](https://mlsanity.com/paper/1404.2334/) (2014)
- [Theta*: Any-Angle Path Planning on Grids](https://mlsanity.com/paper/1401.3843/) (2014)
- [Improving LaCAM for Scalable Eventually Optimal Multi-Agent Pathfinding](https://mlsanity.com/paper/2305.03632/) (2023)
- [dRRT*: Scalable and Informed Asymptotically-Optimal Multi-Robot Motion Planning](https://mlsanity.com/paper/1903.00994/) (2019)
- [Finding a needle in an exponential haystack: Discrete RRT for exploration of implicit roadmaps in multi-robot motion planning](https://mlsanity.com/paper/1305.2889/) (2013)
- [A Unifying Formalism for Shortest Path Problems with Expensive Edge Evaluations via Lazy Best-First Search over Paths with Edge Selectors](https://mlsanity.com/paper/1603.03490/) (2016)
- [Densification Strategies for Anytime Motion Planning over Large Dense Roadmaps](https://mlsanity.com/paper/1611.00111/) (2016)
- [Fast Planning Over Roadmaps via Selective Densification](https://mlsanity.com/paper/2002.04941/) (2020)

## Abstract (arXiv)

We study a pathfinding problem where only locations (i.e., vertices) are given, and edges are implicitly defined by an oracle answering the connectivity of two locations. Despite its simple structure, this problem becomes non-trivial with a massive number of locations, due to posing a huge branching factor for search algorithms. Limiting the number of successors, such as with nearest neighbors, can reduce search efforts but compromises completeness. Instead, we propose a novel LaCAS* algorithm, which does not generate successors all at once but gradually generates successors as the search progresses. This scheme is implemented with k-nearest neighbors search on a k-d tree. LaCAS* is a complete and anytime algorithm that eventually converges to the optima. Extensive evaluations demonstrate the efficacy of LaCAS*, e.g., solving complex pathfinding instances quickly, where conventional methods falter.