Euclidean Pathfinding with Compressed Path Databases

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.

Authors

• Bojie Shen Monash university
• Muhammad Aamir Cheema Monash University
• Daniel Harabor Monash University
• Peter J. Stuckey Monash University

Keywords

• Heuristic Search and Game Playing: Heuristic Search
• Robotics: Motion and Path Planning