Rectangular Symmetry Reduction

This is the second of my three-part look into symmetry reduction algorithms for speeding up grid-based pathfinding.

In part one I introduced the notion of path symmetry: a property of uniform-cost grid maps which can significantly slow down optimal search. In this article I discuss Rectangular Symmetry Reduction (RSR for short): a new pre-processing algorithm that explicitly identifies and eliminates symmetries from uniform cost grid maps. RSR [1] [2] is simple to understand, quick to apply and has low memory overheads. When combined with a standard search algorithm, such as A*, RSR can speed up optimal pathfinding by anywhere from several factors to an order of magnitude. These characteristics make RSR highly competitive with, and in many cases better than, competing state-of-the-art search space reduction techniques.

Please note: this work was developed in conjunction with Adi Botea and Philip Kilby. It forms part of my doctoral research into pathfinding at NICTA and The Australian National University. Electronic copies of the papers in which these ideas were first described are available from my homepage.

The Algorithm

RSR speeds up optimal pathfinding by decomposing an arbitrary uniform-cost grid map into a set of empty rectangles. The idea is to avoid symmetries during search by only ever expanding nodes from the perimeter of each empty rectangle, and never from the interior. To ensure optimal travel through each rectangle we will also add a series of macro edges that allow units to “jump” from one side of a rectangle’s perimeter to the directly opposite side.

(This remainder of this section, and the next, give a mechanical overview of the algorithm and its properties. If you’re impatient, or don’t care about such things, you can skip ahead and check out some screenshots.)

RSR can be described in 3 simple steps. Steps 1 and 2 are applied offline; their objective is to identify and prune symmetry from the original grid map. The third step is an online node insertion procedure; its objective is to preserve optimality when searching for paths in the symmetry-reduced grid map.

RSR Step 1: Grid Decomposition

Decompose the grid map into a set of obstacle-free rectangles. The size of the rectangles can vary across a map, depending on the placement of the obstacles. Once the decomposition is complete, prune all nodes from the interior, but not the perimeter, of each empty rectangle.

RSR Step 2: Addition of Macro Edges

Add a series of macro edges that connect each node on the perimeter of a rectangle with other nodes from the perimeter. In a 4-connected map (shown here for simplicity) a single macro edge between nodes on opposite sides of each rectangle will suffice. If diagonal moves are allowed, a set of macro edges (as described in [1]) will be needed instead.

RSR Step 3: Online Insertion

When the start or goal is located in the interior of an empty rectangle, we use a temporary node re-insertion procedure. In a 4-connected map (shown here for simplicity) we connect the temporary node, online, to the 4 nearest perimeter nodes. A similar operation, involving sets of edges from each perimeter side, is used when diagonal moves are allowed.

Properties and Performance

RSR has several attractive properties:

1. It preserves optimality.
2. It has a small memory overhead in practice.
3. Node insertion (Step 3) can be performed in constant time.
4. It can speed up A* search by anywhere from several factors to an order of magnitude.

I will focus on points 2 and 4 in the remainder of this section. A thorough discussion of points 1 and 3 (including proofs) can be found in [1].

Memory Requirements:
In the most straightforward implement of RSR we need to store the id of the parent rectangle for each of the n traversable nodes in the original grid. We also need to store the origin and dimensions of each rectangle (macro edges can be identified on-the-fly and do not need to be stored explicitly). This means that, in the worst case, we might need to store up to 5n integers. In practice however we can usually do much better. For example: there is little benefit in storing or assigning nodes to rectangles with few or no interior nodes (1×1, 2×1, 2×2, 3×2, 3×3 etc.). We can also avoid the parent id overhead altogether and only store the set of identified rectangles. The only downside is that, during insertion (Step 3 above), we now need to search for the parent rectangle of the start and goal — instead of being able to identify it in constant time.

Performance:
We evaluated RSR on a number of benchmark grid map sets taken from Nathan Sturtevant’s freely available pathfinding library, Hierarchical Open Graph. One of the map sets is from the game Baldur’s Gate II: Shadows of Amn. The other two map sets (Rooms and Adaptive Depth) are both synthetic, though the latter could be described as semi-realistic. I will give only a short summary of our findings; full results and discussion is available in the following papers: [1] [2].

In short: we observed that in most cases RSR can consistently speed up A* search by a factor of between 2-3 times (Baldur’s Gate), 2-5 times (Adaptive Depth) and 5-9 times (Rooms). In some cases the gain can be much higher: up to 30 times.

We found that the extent of the speed gains will be dependent on the topography of the underlying grid map. On maps that feature large open areas or which can be naturally decomposed into rectangular regions, RSR is highly effective. When these conditions do not exist, the observed speed gains are more modest. This performance is competitive with, and often better than, Swamps [4]; another state-of-the-art search space reduction technique. We did not identify a clear winner (each algorithm has different strengths) but did notice that the two methods are orthogonal and could be easily combined.

Screenshots

Below are screenshots of A* + RSR in action. In each case tiles marked red must be explored in order to find the optimal solution (marked in blue). For comparison, I also show the number of tiles explored by vanilla A* when solving the same problem instances. I give one example problem from each benchmark set. You can click on each image to make it larger.

(a) A* (Baldur’s Gate)

(b) A* (Adaptive Depth)

(c) A* (Rooms)

(d) A* + RSR (Baldur’s Gate)

(e) A* + RSR (Adaptive Depth)

(f) A* + RSR (Rooms)

Figure 2: Search Effort.
Comparative pathfinding examples from our experimental results. Images (a) to (c) are total nodes expanded by A* in order to find the optimal path to the goal (marked blue). Images (d) to (f) are total nodes expanded by A* + RSR. The respective domains are (from left to right): Baldur’s Gate, Adaptive Depth and Rooms. Notice that A* + RSR ignores many symmetric path segments and typically reaches the goal with much less effort.

Next Time

In the final part of this series I will discuss Jump Point Search [3]: a similar-yet-different symmetry breaking technique which builds on some of the ideas introduced here. Like RSR, Jump Point Search is highly effective and simple to apply; unlike RSR it can be applied online and has no memory overhead and no pre-processing requirements. In most cases, JPS is also faster than RSR. Stay tuned for that!

Continue to Part 3.

References

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

[2] 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.

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

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

Advertisement