Fast Near-Optimal Path Planning on State Lattices with Subgoal Graphs

Proceedings of the International Symposium on Combinatorial Search, 11

Volume

Vol. 11 No. 1 (2018): Eleventh Annual Symposium on Combinatorial Search

Full Papers

Subgoal graphs can be constructed on top of graphs during a preprocessing phase to speed-up shortest path queries. They have an undominated query-time/memory trade-off in the Grid-Based Path Planning Competitions. While grids are useful for path planning, other kinds of graphs, such as state lattices, have to be used for motion planning. While state lattices are regular graphs like grids, subgoal graphs improve query times by a much smaller factor on state lattices than on grids. In this paper, we present a new version of subgoal graphs that forfeits its optimality guarantee for smaller query times. It guarantees completeness, and our experimental results on state lattices suggest that it can find paths that are close to optimal.

10.1609/socs.v9i1.18446