Subgoal Graphs for Eight-Neighbor Gridworlds
Tansel Uras, Sven Koenig, Carlos Hernández · Proceedings of the International Symposium on Combinatorial Search · 2021
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.