Speeding-Up Any-Angle Path-Planning on Grids

Abstract

Simple Subgoal Graphs are constructed from grids by placing subgoals at the corners of obstacles and connecting them. They are analogous to visibility graphs for continuous terrain but have fewer edges and can be used to quickly find shortest paths on grids. The vertices of a Simple Subgoal Graph can be partitioned into different levels to create N-Level Subgoal Graphs, which can be used to find shortest paths on grids even more quickly by ignoring subgoals that are not relevant for the search, which significantly reduces the size of the graph being searched. Search using Two-Level Subgoal Graphs was a non-dominated entry in the Grid-Based Path Planning Competitions 2012 and 2013. In this paper, we take advantage of the similarities between Subgoal Graphs and visibility graphs to show that Subgoal Graphs can be used, with small modifications, to quickly find “any-angle” paths, thus extending their applicability. Any-angle paths are usually shorter and more realistic looking than grid paths since the movement along any-angle paths is not constrained to grid edges. Our algorithm has the advantage that it is a simple extension of searching Subgoal Graphs and is up to two orders of magnitude faster than Theta* and up to an order of magnitude faster than Block A* (using 5 × 5 blocks), two of the most well-known any-angle pathplanning algorithms, while still finding any-angle paths of comparable lengths.