Hi, I noticed in the past there have been questions on this forum about how to do pathfinding for variable-size agents, particularly on gridmaps. I wrote a two part article on this topic recently and I thought I'd share it here. It's based on a paper I presented last month at CIG'08 which describes the Hierarchical Annotated A* algorithm. HAA* is useful if you're working with grid-based maps and need to add support for classes of differently sized agents; each with distinct terrain traversal capabilities. The basic idea is that you build a single hierarchical graph to pathfind for all kinds of units (like small infantry, large amphibious vehicles etc). It's based on HPA* so it's straightforward to apply and, being hierarchical, answers queries quite fast. Anyway, if you have any questions, thoughts or comments on this topic or the article, please post them here; I'll do my best to try and answer them. EDIT: For those not interested in working with grid maps, I've written a third article (!) describing how to pathfind for different-size units using a Probabilistic Roadmap approach. [Edited by - pithlit on February 11, 2009 8:26:17 AM]

Quite neat.

It looks easy to extend for different shapes as well.

I can sort of see how you would do this for continuous maps -- you'd end up with sort of an onion-shell of pathing volumes?

Quote: Original post by NotAYakk
Quite neat.

It looks easy to extend for different shapes as well.

In principle, yes. You can calculate clearance for any agent shape but things get a little tricky when you use non-symmetrical bounding volumes. For instance, an agent that has a shape longer than it is wider will encounter difficulties turning without hitting obstacles in the environment.

Let me highlight this with an example: Imagine a T intersection between two one-lane roads. A long but narrow vehicle (say, 3x1) can happily navigate either of these roads but turning at the intersection is difficult unless its shape is flexible.

Using a symmetrical 3x3 bounding volume would solve this issue (you avoid very narrow roads altogether) but there's definitely a class of problems here that can't be nicely solved. To the best of my knowledge however, this is beyond the current state of the art for hierarchical path planners.

Quote: I can sort of see how you would do this for continuous maps -- you'd end up with sort of an onion-shell of pathing volumes?

Sort of. I think the best approach would be to try and maximise the size of your bounding volume at different parts of the environment. One nice technique I've seen to do this is the Corridor Map Method (this work partly inspired HAA*; see here for details). The CMM works by randomly sampling the environment to get an idea of the amount of free space and using that information to build a roadmap. Each node on the roadmap has a clearance value which you can consult to see if the location is traversable or not. The way to add nodes to the roadmap is to notice if the amount of clearance is changing (increasing or decreasing).

Quote:

Quote: Original post by NotAYakk
Quite neat.

It looks easy to extend for different shapes as well.

In principle, yes. You can calculate clearance for any agent shape but things get a little tricky when you use non-symmetrical bounding volumes. For instance, an agent that has a shape longer than it is wider will encounter difficulties turning without hitting obstacles in the environment.

Let me highlight this with an example: Imagine a T intersection between two one-lane roads. A long but narrow vehicle (say, 3x1) can happily navigate either of these roads but turning at the intersection is difficult unless its shape is flexible.

Ah yes. Well you could create a phase space in the 3rd dimension.

Break the orientation down to, say, 32 angles, each representing a range of the arc, plus the 'pure' angle ones (to deal with narrow, strait roads).

Then you can phase change between angles by moving "up/down" in phase space.

The corner would then fail on a 3x1 truck because the intermediate phase-adjacent rotation versions of the truck wouldn't fit there.

Of course, that blows up the storage costs of your path finding. And the granularity of angle matters.

As a fun side effect, I think that method could find the 'three point turn' solution. :-)

Quote:

Quote: I can sort of see how you would do this for continuous maps -- you'd end up with sort of an onion-shell of pathing volumes?

Sort of. I think the best approach would be to try and maximise the size of your bounding volume at different parts of the environment. One nice technique I've seen to do this is the Corridor Map Method (this work partly inspired HAA*; see here for details). The CMM works by randomly sampling the environment to get an idea of the amount of free space and using that information to build a roadmap. Each node on the roadmap has a clearance value which you can consult to see if the location is traversable or not. The way to add nodes to the roadmap is to notice if the amount of clearance is changing (increasing or decreasing).

Nodes, or paths between nodes, would have clearance?

...

On a slightly different note, do you happen to know if there is a better-than-O(n^2)-storage, O(n lg n) resolution cost, method for perfectly solving paths in a mostly planar grid (ie, one that works without the high-quality hint function, that A* requires)?

Quote: Original post by NotAYakk
Ah yes. Well you could create a phase space in the 3rd dimension.
..
Of course, that blows up the storage costs of your path finding. And the granularity of angle matters.

Yes, I suppose you could. As you point out though, the memory overhead might be a problem.

Quote: Nodes, or paths between nodes, would have clearance?

In the CMM implementation I liked to earlier the nodes are annotated directly. I believe this is part of the reason the method can't cope with multi-terrain maps. OTOH, the CMM has other neat features, like localised potential fields that allows groups of units to move as a cohesive whole. It's quite a nice paper :)

Quote: On a slightly different note, do you happen to know if there is a better-than-O(n^2)-storage, O(n lg n) resolution cost, method for perfectly solving paths in a mostly planar grid (ie, one that works without the high-quality hint function, that A* requires)?

You're looking for an algorithm that requires less space than A* but without using a heuristic function? Hmm.. I can't think of anything (efficient) off the top of my head.
I do know there was a nice paper at CIG'05 describing Fringe Search; it's a iterative deepening A* derivative (so it requires less memory than standard A*) but at each timestep they only retain the nodes on the frontier of the search. From memory, their results thump IDA* quite nicely :) Here's a link.

So, to those following this thread, I've written part 2 of my article describing HAA*. This time I discuss how to take a map annotated with clearance values and build a space-efficient abstraction that can be re-used by any agent of arbitrary size and capability.

Hopefully it's easy enough to follow. Feel free to post here any questions you might have.

I'll update the original post too so it's easier to find.

One more update for those following this thread.
I decided to write a third article in this series talking about how one can pathfind in continuous environments.

The basic question this article poses is thus: HAA* is limited to grid environments but what about if you don't want to work with grids? I discuss how solve this issue using a clearance-based Probabilistic Roadmap (PRM) approach. This technique is straight from the field of robotics and offers quite a nice alternative to traditional navigation mesh methods. PRMs are conceptually simple to apply and can produce very nice paths.

I'll update the first post too I think.