Euclidean Pathfinding with Compressed Path Databases
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.
Robotics: Motion and Path Planning
Heuristic Search and Game Playing: Heuristic Search