Shortest Path

August 26, 2011

Fast Pathfinding via Symmetry Breaking

Filed under: pathfinding — dharabor @ 15:52
Tags: , ,
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.

About these ads

9 Comments »

  1. Thank you for this excellent work. I am currently finishing up the path finding system for my game.

    I use an approach similar to “Hierarchical Path Planning for Multi-Size Agents in Heterogeneous Environments.”

    Expect I have

    1: extended the abstraction part to multiple levels.

    2: used a version of bush fire that expands in multiple directions.

    3: Each node has a terrain cost for different terrain types

    4: nodes with low clearance values are more expensive.

    Grid maps are from a game development standpoint very important and often over looked. They are one of the best ways to convey different terrain types and for some game types particularly role playing games and real time strategy games the best option in my option.

    I am honestly loathed to go back and change my system. However I think these are very interesting and important papers. In a year or two when I plan to update / maintain my pathing system. I plan to read them rather intently.

    The biggest problem I see if you only allow nodes with uniform cost. It seems like you are giving up the biggest advantage of grid maps. Namely, the ability to have verging terrain types effect path finding. You do not need a large difference in node cost 1.0 vs 1.05 to add up to a path with very different total cost.

    It seems like you would be better served in uniform grid maps by preprocess the grid and eliminate open areas by reducing them to a single center node. You can do this in a way that is abstracted from the client program.

    Comment by Guest — August 26, 2011 @ 18:53

  2. Hi there! Thanks for posting.

    It sounds like you’re doing some pretty interesting stuff; I wouldn’t mind hearing more about your game when you decide to make it public.

    To answer your question: the current work is indeed specific to uniform cost maps. I chose to focus on this domain since it is simple to work with but also common enough that any results might be of interest to a reasonably large group of people. I agree however that a generalisation to weighted grids would make the current work more interesting. I hope to have some theoretical and empirical results on this very problem in the near future.

    For the present, one simple suggestion is the following: divide your map into a set of connected components, each of which is uniform-cost. For example: if you have a map involving plains, lakes and swamps, and each of these regions is uniform cost, you could simply apply either RSR or JPS to each region. In the case of JPS, simply stop the recursion when you find a tile that has a neighbour with a different terrain type. One small caveat: your speedup may not be very large if the size of each component is small. This is because both RSR and JPS exploit the fact that, when you cross a large uniform-cost region, there are many symmetric path segments that each contains nodes with similar f-costs.

    Regarding the centroid suggestion: that’s a nice idea. I believe Nathan Sturtevant implemented a similar system for the pathfinding system in Dragon Age: Origins. You can read about it in [9]. It is very fast and has low memory overheads but it is not, however, optimal. I think Nathan also needed to apply some clever refinement to the abstract path to prevent characters from navigating to the centre of large rooms before heading for the exit (this can look really weird if the movement introduces a large detour).

    Comment by dharabor — August 27, 2011 @ 10:49

  3. can i request for an algorithm or pseudocode for the dead- end heuristic ?

    Comment by Mark Catindig San Juan — September 4, 2011 @ 19:02

  4. Hi Mark,

    You can find a thorough description of that algorithm in the original paper (reference [1] at the end of this article). You can download an electronic version directly from the authors website here

    Comment by dharabor — September 5, 2011 @ 17:46

  5. [...] Fast Pathfinding via Symmetry Breaking (harablog.wordpress.com) [...]

    Pingback by A geek with a hat » Our intuitive understanding of distance fails us — September 7, 2011 @ 03:57

  6. [...] Fast Pathfinding via Symmetry Breaking (harablog.wordpress.com) [...]

    Pingback by C++ Link: A-star Shortest Path Algorithm (C++ recipe) « Keith M. Programming — November 24, 2011 @ 11:28

  7. [...] great pathfinding formula – to date I have find out about HPA* and A* with JPS, but to both I’ve not handled to locate an implementation, that is a problem since the [...]

    Pingback by Pathfinding for a lot of units, mostly random movement | Q&A System — July 1, 2012 @ 21:15

  8. Thanks on your marvelous posting! I truly enjoyed reading it, you
    happen to be a great author.I will always bookmark your blog and will come back in the future.
    I want to encourage yourself to continue your great
    job, have a nice afternoon!

    Comment by arizona.edu — August 11, 2013 @ 17:35

  9. Hello, i believe that i noticed you visited my blog so i got here to return the desire?.I
    am attempting to find issues to enhance my web site!I guess its good
    enough to make use of some of your ideas!!

    Comment by Evie — September 24, 2013 @ 21:05


RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

The Rubric Theme. Blog at WordPress.com.

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: