Shortest Path

February 5, 2009

Hierarchical Clearance-based Pathfinding

Filed under: pathfinding — dharabor @ 17:23

In my last article I discussed Annotated A*, a search algorithm able to solve pathfinding problems for variable-sized agents with heterogeneous terrain traversal capabilities. Such problems are encountered in many modern video games which often feature different classes of units, each with distinct physical characteristics and navigational capabilities.

The story so far

Annotated A* operates on a grid map which is annotated with clearance values. A clearance value is simply a distance-to-obstacle metric that provides us with a useful indicator of how much traversable space there is at a given location. We can use clearances to quickly work out which parts of a map are traversable for an arbitrary agent by simply comparing the agent’s size with the clearance value associated with a particular location. Figures 1-3 show the associated clearance value annotations for 3 capabilities  on a small map with 2 traversable terrains: Ground (white tiles) and Water (blue tiles). A capability is defined as a set of terrains used to specify which parts of the environment are traversable for an agent.

Figure 7. True clearance annotations for the {Ground} capability (only white tiles are traversable).

Figure 1. Clearance value annotations for the {Ground} capability (only white tiles are traversable).

Figure 8. True clearance annotations for the {Water} capability (only blue tiles are traversable).

Figure 2. Clearance value annotations for the {Water} capability (only blue tiles are traversable).

Figure 9. True clearance annotations for the {Ground, Water} capability (both white and blue tiles are traversable).

Figure 3. Clearance value annotations for the {Ground, Water} capability (both white and blue tiles are traversable).

The problem at hand

In this second piece I want to discuss how to take this simple pathfinding system and speed it up significantly through the use of hierarchical abstraction. The main problem here is that a multi-terrain map annotated with clearance values contains lots of topographical information but abstraction methods can only hope to approximate the original. Thus, the goal is to build an abstraction which is representationally complete i.e. if a path between two points can be found on the original annotated map, we should be able to also find it using only the abstract map. To achieve this we’re going to attack the problem in 3 steps:

  1. First, we divide our annotated map into a set of adjacent Clusters connected by Entrances. We will show that the resultant graph produced by this process is infact representationally complete but contains redundant and duplicated information.
  2. Second, we compact the graph produced in the previous step using dominance techniques which identify and prune unnecessary nodes and edges. The resultant abstraction is shown to contain a minimal set of nodes and edges yet still retains the representational completeness properties of the original map.
  3. Third, we describe the Hierarchical Annotated A* algorithm (HAA*) which we use to efficiently answer queries for a wide variety of agents with different sizes and terrain traversal capabilities. HAA* is shown to produce very high quality (i.e. near optimal) paths with comparatively little search effort vs. Annotated A*.

Clusters and Entrances

In order to create an an abstract representation of an annotated map we follow Botea et al and divide the environment into a series of discrete square-sized areas called clusters. Figure 4 shows the result of this step on our running example using clusters of size 5×5.

Figure 4. The map is divided into four 5x5 clusters.

Figure 4. The map is divided into four 5x5 clusters.

Figure 5. (a) Three entrances are identified between clusters C1 and C3, one for each possible capability. (b) Each transition point (denoted by a strong dark line) maximises clearance for a particular capability.

Figure 5. (a) Three entrances are identified between clusters C1 and C3, one for each possible capability. (b) Each transition point (denoted by a strong dark line) maximises clearance for a particular capability.

Next, we identify entrances between each pair of adjacent clusters. An entrance is defined as an obstacle-free area of maximal size that exists along the border between two clusters (Figure 5a). Each entrance has associated with it a transition point which reflects the fact that an agent can traverse from one cluster to the other. To this end we select from each entrance a pair of adjacent tiles, one from each cluster, which maximise clearance (Figure 5b). Each transition point is represented in the abstract graph by two nodes connected with a single inter-edge of weight 1.0.  The inter-edge is also annotated with the corresponding capability and clearance value that reflect the traversability requirements of the transition point.

Figure 6. A complete initial abstraction.

Figure 6. A complete initial abstraction.

Finally, we complete the abstraction by finding all possible ways to traverse each cluster. We achieve this by running Annotated A*  (AA*) between each pair of abstract nodes inside a cluster; one search for each combination of possible agent sizes and capabilities. Every time AA* successfully finds a path we add a new intra-edge between the start and goal nodes. The weight of the edge is equal to the length of the path and we further annotate it with the size and capability parameters used by AA* to reflect the traversability requirements of the path. This approach is highly effective at capturing all pertinent topographical details of the original map. Infact,  it is easy to see that the resultant graph (which is termed an initial abstraction) is representationally complete since we’ve identified all possible transitions between each pair of adjacent clusters and all possible ways to traverse each cluster (Figure 6).

Compacting the abstract graph

An interesting observation made during the abstraction-building process was that on many maps the same path was often returned by AA* when searching between the same pair of points with different sizes and capability parameters. This indicates that our abstract graph actually contains unnecessary or duplicated information (and is also needlessly large as a result). To solve this problem we’re going to apply two edge dominance approaches to prune unnecessary nodes an edges. I want to avoid describing these ideas formally (the details are in the paper) and instead focus on the intuition behind each one.

The first, termed strong dominance, states that if two edges, both of identical length,  connect the same pair of nodes and both are traversable by the same capability then we need only retain the one with the largest clearance. Figure 1 illustrates this idea. It is easy to see that using this approach preserves representational completeness; any agent able to traverse the edge with smaller clearance is also able to traverse the one with larger clearance. The resultant graph is termed a high-quality abstraction because we discard only duplicate information fromt the graph.

Figure 7. (a) Part of the initial abstraction for cluster C1. (b) Strong dominance removes edges E5 (dominated by E3) and E6 (dominated by E4).

Figure 7. (a) Part of the initial abstraction for cluster C1. (b) Strong dominance removes edges E5 (dominated by E3) and E6 (dominated by E4).

Figure 8. (a) An agent traveling from "u" to "x" via the path {E1, E2, E3} is also able to travel via {E4, E5, E6} so the former is weakly dominated. (b) The resultant graph after weak dominance is applied.

Figure 8. (a) A graph with two inter-edges, E2 and E5. An agent traveling from "u" to "x" via E2 must both swim and walk whereas traveling via E5 only requires walking. (b) The dominated inter-edge, E2, and its endpoints, are removed.

The second approach, termed weak dominance, is focused on minimising the number of transitions between clusters. To achieve this the algorithm analyses pairs of inter-edges that connect the same two clusters and attempts to prove that if one is removed the representational completeness of the graph is maintained. The effect is that only transitions which are traversable by the largest number of agents are retained. This is similar to the way motorists frequently prefer to travel between locations via freeways, which are traversable by many kinds of vehicles, instead of opting for more direct offroad travel. Figure 8 illustrates this idea; again, it is easy to see that the application of weak dominance also preserves representational completeness. The resultant graph is termed a low-quality abstraction, to reflect the fact that some connectivity information is lost in the process.

Figure 9. The abstract graph after weak dominance is applied. Note that the graph is almost half the size compared to Figure 6.

Figure 9. The abstract graph after weak dominance is applied. Note that the graph is almost half the size compared to Figure 6.

Choosing which dominance technique to use will depend on the exact requirements of the target application. Empirical results have shown that in both cases the amount of memory required to store the abstract graph can be a small fraction of that required by the original map. (though the exact number depends on a range of factors which are discussed in the paper). Comparatively speaking, low quality abstractions can be more than 50% smaller than their high quality counterparts but there is a small tradeoff. In particular, high quality abstractions produce, on average, paths with lengths 3-5% longer than optimal while low quality abstractions are in the 6-10% range.

Hierarchical Annotated A*

The process of finding a path using an abstract graph is a straightforward one that will be familiar to anyone who has come across the HPA* algorithm:

  1. Insert two temporary nodes into the abstract graph to represent the start and goal locations.  Connect these nodes to the rest of the graph by attempting to find a path to from the start/goal positions to every transition point in the local cluster.
  2. Using A*, find a shortest path from the start to the goal in the abstract graph. At the end of the search, remove the two temporary nodes.

As with Annotated A*, the search algorithm from Step 2 is modified slightly to accept two extra parameters: the agent’s size and capability. In addition, the search function is also also augmented so that before a node is added to A*’s open list we first verify that it is infact reachable. In this case, a node is reachable only if the edge connecting it to the current node is traversable for the given size and capability parameters. The resultant algorithm is termed Hierarchical Annotated A* (HAA* for short).

As with other hierarchical planners, HAA* is shown to be very fast. I analysed its performance on a large set of problems (over 140K) using both small and large maps from Bioware’s popular RPG Baldur’s Gate. Since there are no similar pathfinding algorithms to measure against, it was  contrasted with Annotated A*. In short, HAA* is an order of magnitude faster and, even with my naive, non-optimised implementation, it was able to find solutions to most problems in ~6ms on average (tested on my Core2 Duo 2.16GHz MacBook, running OSX 10.5.2 with 2GB of memory).

Questions, source code etc.

So that about wraps things up. If you have any questions or comments on anything described in this or the previous article, please feel free to contact me. I also suggest checking out the original HAA* paper and associated presentation slides which contain more indepth discussion of these ideas. If you’d like to play with a working implementation, you can download the source code I wrote to evaluate the algorithm. It’s written in C++ and based on the University of Alberta’s freely available pathfinding library, Hierarchical Open Graph (or HOG). HOG compiles on most platforms; I’ve personally tested it on both OSX and Linux and I’m told it works on Windows too. The classes most relevant to this article are probably AnnotatedCluster.cpp and AnnotatedClusterAbstraction.cpp which together are responsible for generating the abstract graph. Meanwhile, AnnotatedHierarchicalAStar.cpp provides a reference implementation of the HAA* algorithm.

Advertisements

6 Comments »

  1. […] (non-grid) Maps Filed under: Uncategorized — dharabor @ 00:06 In my last two articles I discussed HAA*, a clearance-based pathfinding technique applicable to grid maps that efficiently […]

    Pingback by Clearance-based Pathfinding On Continuous (non-grid) Maps « Shortest Path — February 12, 2009 @ 00:06

  2. […] Filed under: pathfinding, roadmaps — dharabor @ 00:06 In my last two articles I discussed HAA*, a clearance-based pathfinding technique applicable to grid maps that efficiently […]

    Pingback by Clearance-based Pathfinding with Probabilistic Roadmaps « Shortest Path — February 12, 2009 @ 00:15

  3. Thanks for the description of the algorithm.
    Do you also compact the abstract graph by removing the inter-edges?
    For example, I would preserve just the nodes on the left or upper end of an inter-edge.
    That would reduce the number of nodes to one half.

    The preserved node would get the intra-edges from the removed node.
    And the cost of the obtained edges would be increased by the number of removed
    nodes from the connection. That is:
    a) by 2 steps when the edge leads between left and top sides of the cluster.
    b) by 0 steps when the edge is between right and bottom sides.
    c) by 1 step otherwise

    It is clearer on a drawn diagram. Sorry.
    Does it make sense? Thanks.

    Comment by Ivo Danihelka — October 1, 2009 @ 03:44

  4. Hi Ivo,

    Thanks for your question.
    In short, yes, inter-edges are also removed as part of the graph compacting step. There is some discussion of this in the article (search for weak dominance) but I’ll attempt to expand on it.

    The approach is similar to what you propose:
    If two inter-edges connect the same pair of clusters we check if one weakly dominates the other by attempting to prove that if we remove one of the two the representational completeness of the abstract graph is preserved. The proof itself is straightforward; there is an example of its application in Figure 8 above. Notice that any agent able to reach and traverse edge E2 can also reach and traverse edge E5. This is sufficient to preserve representational completeness with the only difference being that the path through E5 is slightly longer.

    Notice also that there is now no need to preserve any intra-edges associated with the dominated transition :)

    There is a more formal description of the approach in the CIG paper (see Section VII and in particular Theorem 7 and its corollary).

    In the same paper I also provide an empirical analysis of the effect weak dominance both on the size of an abstract graph and also on path quality/optimality (see Table 1 and Figure 5 respectively in Section X). The effect is quite positive: graphs can be reduced by more than 50% in size and the resultant paths are only 6-10% away from optimal.

    Comment by dharabor — October 2, 2009 @ 11:41

  5. Thanks for the response.
    I probably explained my approach badly. I see it as a complement to weak dominance compacting.
    1) Weak dominance removes redundant paths.
    2) I would than collapse Node1-inter_edge-Node2 to just Node1.
    That could be made for every inter-edge. Even when there is only one inter-edge between two clusters.
    No optimality is lost by this collapsing of inter-edges. Because the length of the inter-edge is used to increase the lengths of the edges obtained from Node2.

    Comment by Ivo Danihelka — October 2, 2009 @ 17:19

  6. Hi Ivo,

    I see. I misunderstood your post entirely! Your observation is correct; you could compact the abstract graph further by only keeping one node per inter-cluster transition.

    I did think about this at one point but decided to leave it out of the paper as it complicates the start and goal insertion procedure. If I recall correctly the problem is that by removing one of the nodes of an inter-edge you effectively create overlapping clusters. In order to still be able to limit the scope of your searches during insertion (and path refinement for that matter) to the area inside one cluster you will need to resize your clusters and assign some tiles in both the low level and abstract map to 2 parent clusters.

    None of this is particularly hard mind you but the savings are minimal as the size of the abstract graph is dominated by the number of edges. There are really very few nodes in comparison so it becomes a matter of diminishing returns.

    If you are really memory constrained you could perhaps try increasing the size of your clusters. The savings would be more substantial but the relative optimality of your paths does take a small hit as a consequence.

    Comment by dharabor — October 3, 2009 @ 02:18


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

Blog at WordPress.com.

%d bloggers like this: