Clearance-based Pathfinding with Probabilistic Roadmaps

In my last two articles I discussed HAA*, a clearance-based pathfinding technique applicable to grid maps that efficiently computes paths for agents of different sizes and with distinct terrain traversal capabilities. Such problems are common in many modern video games and particularly in the real-time strategy and role-playing genres (Figure 1). The basic idea behind HAA* is really simple: for each tile in the grid, compute a clearance value to represent the maximal amount of free space at that location. By comparing the size of an arbitrary agent with a tile’s clearance value one can quickly determine which parts of the environment are traversable and which are not.

Figure 1. EA's Red Alert 3 features units with different shapes, sizes and terrain traversal capabilities. Units can be land-based, aquatic or amphibious.

But what happens when you can’t (or don’t want to) work with grids? More specifically, how do you deal with agent diversity in continuous environments? As it turns out this problem can be solved with a well known method from the field of robotics: the Probabilistic Roadmap (or PRM for short). PRMs are highly suited to capturing topographical information in complex multi-dimensional environments and have been effectively used for robot pathfinding since their inception in the mid 90s. 

In this article I want to describe a recent PRM method which partly inspired my work on HAA*; it’s based on a paper by [Niuwenhuisen, Kamphuis, Mooijekind and Overmars] that was presented at CGAIDE’04. This is a really neat piece of research which makes several contributions:

• It shows how to combine PRM construction with Voronoi diagrams. The effect is a roadmap in which every node maximises its distance from nearby obstacles. 
• It addresses the “ugly path” problem that many PRM methods suffer from by describing a nice method for producing smooth transitions between graph nodes.
• It describes how to combine PRMs with potential fields to achieve coherent group movement.

Since the scope is quite broad and my interest rather more narrow, I will only discuss the first aspect. If you’d like to know more, I recommend taking a look at the paper itself; it’s very well written and highly readable.

Point Sampling With Voronoi Diagrams

Traditional roadmap construction methods usually sample an environment by selecting a point and checking if it is collision-free for (some configuration of) a robot (Figure 2). The resultant PRM is thus only applicable to the robot for which is it was created (or one smaller in size). If we try to re-use the PRM for a larger robot there is no guarantee that any computed path will be valid (Figure 3). 

Figure 2. Random samples are taken from the environment. Only the points which are collision-free for some agent (shape) are kept.

Figure 3. A PRM constructed for a small agent. Trying to use the same PRM for a large tank agent results in an invalid path due to insufficient clearance in the red-highlighted area.

Figure 4. A simple map is divided into 6 Voronoi regions. Black areas are obstacles (which include the four map edges).

To solve this problem the authors propose a PRM construction method that uses the Voronoi diagram of the map as a guide. A Voronoi diagram is simply a division of a geometric space into regions in which every location is either closest to one particular obstacle or otherwise equidistant to several different obstacles (Figure 4).

The PRM construction method is very straightforward: 

1. Using random sampling select non-obstacle points in the environment and retract them to the edges of the nearby Voronoi regions. These form the nodes of the new PRM.
2. Connect all nodes to their nearest neighbours (for some value of “near”).
3. Retract any edges which are too close to nearby obstacles (so agents don’t graze the sides of obstacles).
4. Improve the roadmap by applying circular blends to smooth any jagged transitions between nodes (this could also be done on-the-fly for each agent rather than as a preprocessing step).

Figure 5. An example PRM produced by the method. Notice that all nodes (pink) are positioned to maximise distance from obstacles and all edges maintain a mimimum obstacle distance also.

Figure 5 illustrates a typical result. Notice that the roadmap always retains maximum clearance from all obstacles at all times. Each node on the PRM (or backbone path) is annotated with a clearance value that represents the radius of a maximal bounding sphere centred at that position. Because the nodes on the roadmap are close together they form an overlapping clearance corridor which can be used to answer pathfinding queries for (circular shaped) agents of arbitrary size. Pretty cool, huh?

Disadvantages of Probabilistic Roadmaps

Although I quite like PRMs there are some limitations to be aware of. Perhaps the biggest is that all PRMs suffer a common ailment: representational incompleteness. Simply put, if a path exists in the original map, there is no guarantee that it will be found using a PRM. Actually, to be more precise, PRMs are only probabilistically complete, which is a fancy way of saying that as the sampling coverage of the terrain approaches 100% so too does the probability that the PRM can be used to find any valid path present in the original environment. Despite this property, PRMs have been shown to work quite well in practice, solving a large number of problems in very complex environments. The key to building a good PRM is the sampling strategy; a sufficient number of points have to be selected to reasonably approximate the original environment. How much is “sufficient” will depend on the situation; there are no hard-and-fast rules.

Another disadvantage of PRMs is that they only represent the terrain traversal requirements for one capability (i.e. all areas are either traversable by all agents or obstacles for all agents). This is in stark contrast to other pathfinding approaches, like HAA*, which build abstractions that reflect traversal requirements for all possible capabilities. One way to solve this problem is to simply build several PRMs, one for each distinct terrain traversal capability.

So that about wraps it up for today. As always, please feel free to contact me with any questions, comments or corrections you might have regarding this article.

References

Dennis Nieuwenhuisen, Arno Kamphuis, Marlies Mooijekind, Mark H. Overmars,
Automatic Construction of Roadmaps for Path Planning in Games,
International Conference on Computer Games: Artificial Intelligence, Design and Education (2004) 
pages 285-292
(pdf)

Harabor D. & Botea, A.,
Hierarchical path planning for multi-size agents in heterogeneous environments,
IEEE Symposium on Computational Intelligence and Games (2008),
(pdf) (presentation)

Advertisement