ABSTRACT
This chapter presents subgoal graphs, which are constructed by preprocessing maps that are represented as grids. Subgoal graphs use a small amount of memory and can be used to find shortest paths fast by ignoring most of the grid cells during search. The chapter describes several variants of subgoal graphs, each being a more sophisticated version of the previous one and each requiring more preprocessing time in return for faster searches. Even though subgoal graphs are specific to grids, the ideas behind them can be generalized to any graph representation of a map. The two-level subgoal graph entry was one of the nondominated entries in the Grid-Based Path Planning Competitions 2012 and 2013. To summarize, Simple subgoal graphs (SSGs) are constructed by placing subgoals at the corners of obstacles and adding edges between subgoals that are direct-h-reachable. Once an SSG has been constructed, it can be used to find shortest paths between any two cells on the grid.
