Fast Pathfinding via Symmetry Breaking

In this article, the first in a three-part series, I attempt to explain path symmetry: a property of uniform-cost grid maps and other regular search domains which can significantly slow down pathfinding. I describe how symmetry manifests itself and briefly discuss some approaches that other people have tried to improve things. Finally, I introduce two recent ideas from my doctoral research: Rectangular Symmetry Reduction (RSR) and Jump Point Search (JPS). Both are optimality-preserving techniques that explicitly identify and eliminate symmetry in order to speed up pathfinding by an order of magnitude and more.

In parts two and three I will give a technical overview of both RSR and JPS, discussing their strengths, weaknesses and observed performance on two popular video-game benchmarks kindly made available by Nathan Sturtevant and BioWare: Baldur’s Gate II and Dragon Age: Origins.

Please note: this work was developed in conjunction with my co-authors: Adi Botea, Alban Grastien and Philip Kilby. It forms part of my doctoral research into pathfinding at NICTA and The Australian National University. Electronic copies of the papers mentioned in this article are available from my homepage.

Path Symmetries

Often appearing as a pathfinding domain in areas such as robotics and video games, grid maps are a simple yet popular method for representing an environment. As it turns out, grids are also academically interesting for the following reason: between any given pair of locations, there usually exists many possible paths. Sometimes these paths represent alternative ways of reaching one location from the other but more often they are symmetric in the sense that the only difference between them is the order in which moves appear.

Figure 1: Symmetry.
A simple grid-based pathfinding problem. For simplicity (but not in general) we allow only straight moves and not diagonal. Many optimal length paths could be returned as the solution; we highlight only a few. Notice that each one is a permutation of all the others. In such cases we say that a symmetry exists between the paths.

Before proceeding further it is necessary to establish some precise terminology. For example: what exactly is a path? Traditionally, Computer Scientists define paths as ordered sequences of connected edges. The conjunction of these edges represents a walk in the search graph from some arbitrary start location to some arbitrary goal location. However this definition is too general to capture the idea of symmetry in grid maps. For that, we need a slightly different notion of a path:

Definition 1: Grid Path.
A path in a grid map is an ordered sequence of vectors, where each vector represents a single step from one node on the grid to an adjacent neighbouring node.

The distinction between edges and vectors is an important one as it allows us to distinguish between paths that are merely equivalent (i.e. of the same length) and those which are symmetric. But what, exactly, does it mean to have a symmetric relationship between paths?

Definition 2: Path Symmetry.
Two grid paths are symmetric if they share the same start and end point and one can be derived from the other by swapping the order of the constituent vectors.

As a clarifying example, consider the problem instance in Figure 1. Each highlighted path is symmetric to the others since they all have the same length and they all involve some permutation of 9 steps up and 9 steps right.

In the presence of symmetry a search algorithm such as A* is forced to explore virtually every location along each optimal path. In Figure 1, depending on how we break ties, A* might expand every node on the entire map before reaching the goal. Further, A* will usually consider many other nodes that appear promising but that are not on any optimal path. For example, each time A* expands a node from the fringe of the search, it has already likely found almost every symmetric shortest path leading to that node (again, depending on how we break ties when two nodes appear equally good). But this effort is in vain if these expansions do not lead the search closer to the goal and instead into a dead-end. Thus arises the question which I will attempt to answer in this article: how do we deal with symmetry when pathfinding on grid maps?

Existing Methods For Speeding Up Search

A large number of techniques have been proposed to speed up pathfinding. Most can be classified as variations on three themes:

1. Reducing the size of the search space through abstraction.

   Algorithms of this type are fast and use little memory but compute paths which are usually not optimal and must be refined via further search. Typical examples: HPA* [2], MM-Abstraction [9].

2. Improving the accurary of heuristic functions that guide search.

   Algorithms of this type usually pre-compute and store distances between key pairs of locations in the environment. Though fast and optimal, such methods can incur signficant memory overheads which is often undesirable. Typical examples: Landmarks [6], True Distance Heuristics [10].

3. Dead-end detection and other state-space pruning methods.

   Algorithms of this type usually aim to identify areas on the map that do not need to be explored in order to reach the goal optimally. Though not as fast as abstraction or memory heuristics, such methods usually have low memory requirements and can improve pathfinding performance by several factors. Typical examples: Dead-end Heuristic [1], Swamps [8], Portal Heuristic [7].

My work in this area can be broadly classified as a search space pruning technique. Where it differs from existing efforts is that, instead of trying to identify areas that do not have to be crossed during search, I aim to identify and prune symmetric nodes that prevent the fast exploration of an area. This idea nicely complements existing search-space reduction techniques and, as it turns out, also complements most grid-based abstraction methods and memory heuristic approaches.

Rectangular Symmetry Reduction and Jump Point Search

My co-authors and I have developed two distinct approaches for explicltly identifying and eliminating path symmetries on grid maps. I outline them here very briefly and in more detail in an upcoming post:

1. Rectangular Symmetry Reduction (RSR).

   RSR [4][5] can be described as a pre-processing algorithm which identifies symmetries by decomposing the grid map into empty rectangular regions. The central idea, then, is to avoid symmetries by only ever expanding nodes from the perimeter of each rectangle and never from the interior.

2. Jump Point Search (JPS).

   JPS [3] consists of two simple neighbour pruning rules that are applied recursively during search. Each rule considers the direction of travel to a given node from its parent (either a straight step or a diagonal step) in order to prune the set of local neighbours (tiles) around that node. The central idea is to avoid any neighbours that could be reached optimally from the parent of any given node. In this way we are able to identify and avoid, on-the-fly, large sets of symmetric path segments; such as those in Figure 1.

RSR can pre-process most maps in under a second and has a very small memory overhead: we need to keep only the id of the parent rectangle each node is associated with (and the origin and dimensions of each such rectangle). By comparison, JPS has no pre-processing requirements and no memory overheads. Both algorithms are optimal and both can speed up A* by an order of magnitude and more. Figure 2 shows a typical example; For reference, I also include a screenshot for vanilla A*. You can click on each image to make it larger.

(a) A*

(b) A* + RSR

(c) A* + JPS

Figure 2: Search Effort.
All nodes marked red must be expanded before the optimal path to the goal (marked in blue) is found. Notice that, in the case of A*, many nodes on the fringe of the search (i.e. on the edge of the red area) can only be reached by paths that cross large regions of empty space. These paths usually have many symmetric alternatives and considering them all can require a substantial number of node expansion operations. RSR and JPS can detect and eliminate such symmetries and both reach the goal much sooner.

Next time I will explain, in more depth, the mechanical details of both RSR and JPS. In the meantime, electronic copies of the research papers in which RSR [4][5] and JPS [3] were originally described are available from my homepage.

If you have any questions or comments on this work, I’d be glad to hear from you. Please leave a message below or, if you prefer, drop me an email instead (my contact details are on the About page).

Continue to Part 2.
Continue to Part 3.

References

[1] Y. Björnsson and K Halldörsson Improved Heuristics for Optimal Path-finding on Game Maps. In AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment (AIIDE), 2006.

[2] A. Botea, M. Müller, and J. Schaeffer. Near Optimal Hierarchical Path-finding. In Journal of Game Development (Issue 1, Volume 1), 2004.

[3] D. Harabor and A. Grastien. Online Graph Pruning for Pathfinding on Grid Maps. In National Conference on Artificial Intelligence (AAAI), 2011.

[4] D. Harabor, A. Botea, and P. Kilby. Path Symmetries in Uniform-cost Grid Maps. In Symposium on Abstraction Reformulation and Approximation (SARA), 2011.

[5] D. Harabor and A. Botea. Breaking Path Symmetries in 4-connected Grid Maps. In AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment (AIIDE), 2010.

[6] A. V. Goldberg and C. Harrelson. Computing The Shortest Path: A* Search Meets Graph Theory. In SIAM Symposium on Discrete Algorithms (SODA), 2005.

[7] M. Goldenberg, A. Felner, N. Sturtevant and J. Schaeffer. Portal-Based True-Distance Heuristics for Path Finding. In Symposium on Combinatorial Search (SoCS), 2010.

[8] N. Pochter, A. Zohar, J. S. Rosenschein and A. Felner.
Search Space Reduction Using Swamp Hierarchies. In National Conference on Artificial Intelligence (AAAI), 2010.

[9] N. R. Sturtevant. Memory-Efficient Abstractions for Pathfinding. In AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment (AIIDE), 2007.

[10] N. R. Sturtevant, A. Felner, M. Barrer, J. Schaeffer and N. Burch. Memory-Based Heuristics for Explicit State Spaces. In International Joint Conference on Artificial Intelligence (IJCAI), 2009.