Pathfinding with Lazy Successor Generation
This addresses pathfinding challenges in large-scale environments for robotics or AI applications, but it is incremental as it builds on existing search methods with a novel generation scheme.
The paper tackled the pathfinding problem with implicitly defined edges and massive locations by proposing LaCAS*, a complete and anytime algorithm that gradually generates successors using k-nearest neighbors on a k-d tree, solving complex instances quickly where conventional methods faltered.
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.