Euclidean Pathfinding with Compressed Path Databases

Euclidean Pathfinding with Compressed Path Databases

Bojie Shen, Muhammad Aamir Cheema, Daniel Harabor, Peter J. Stuckey

Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence
Main track. Pages 4229-4235. https://doi.org/10.24963/ijcai.2020/584

We consider optimal and anytime algorithms for the Euclidean Shortest Path Problem (ESPP) in two dimensions. Our approach leverages ideas from two recent works: Polyanya, a mesh-based ESPP planner which we use to represent and reason about the environment, and Compressed Path Databases, a speedup technique for pathfinding on grids and spatial networks, which we exploit to compute fast candidate paths. In a range of experiments and empirical comparisons we show that: (i) the auxiliary data structures required by the new method are cheap to build and store; (ii) for optimal search, the new algorithm is faster than a range of recent ESPP planners, with speedups ranging from several factors to over one order of magnitude; (iii) for anytime search, where feasible solutions are needed fast, we report even better runtimes.
Keywords:
Robotics: Motion and Path Planning
Heuristic Search and Game Playing: Heuristic Search