Subgoal Graphs for Eight-Neighbor Gridworlds

Proceedings of the International Symposium on Combinatorial Search, 5

Volume

Vol. 5 No. 1 (2012): Fifth Annual Symposium on Combinatorial Search

Grid-Based Path Planning Competition

We propose a method for preprocessing an eight-neighbor gridworld to generate a subgoal graph and a method for using this subgoal graph to find shortest paths faster than A*, by first finding high-level paths through subgoals and then shortest low-level paths between consecutive subgoals on the high-level path.

10.1609/socs.v3i1.18253