Planning Short Paths with Clearance using Explicit Corridors

Abstract
A central problem of applications dealing with virtual environments is planning a collision-free path for a character. Since environments and their characters are growing more realistic, a character’s path needs to be visually convincing, meaning that the path is smooth, short, has some clearance to the obstacles in the environment, and avoids other characters. Up to now, it has proved difficult to meet these criteria simultaneously and in real-time.

We introduce a new data structure, i.e. the Explicit Corridor Map, which allows creating the shortest path, the path that has the largest amount of clearance, or any path in between. Besides being efficient, the corresponding algorithms are surprisingly simple. By integrating the data structure and algorithms into the Indicative Route Method, we show that visually convincing short paths can be obtained in real-time.

Reference
Roland Geraerts. Planning Short Paths with Clearance using Explicit Corridors.
In IEEE International Conference on Robotics and Automation, pp. 1997-2004, 2010.
Full text: [pdf] | Presentation [ppt]

A smooth, short path with clearance inside an Explicit Corridor. Click on the image for finer details.
A smooth, short path with clearance inside an Explicit Corridor.

Note: We have created a multi-layered extention of this paper.

Movie
The steps of our algorithm are visualized in the movie below.



The Explicit Corridor
The Explicit Corridor facilitates creating the shortest path with a certain amount of minimum clearance.
Explicit Corridors facilitate creating the shortest path with a certain amount of minimum clearance.

Test environment
We have used the City environment (500x500m) in our experiments. Other environments can be found here. We created a corresponding footprint composed of 548 convex polygons. The Explicit Corridor Map was created in 0.6 seconds by using the GPU. This data structure consumes O(n) memory, where n is the number of vertices on the obstacles in the footprint.

City environment. Click on the image for finer details.     Footprint and Explicit Corridor Map. Non-convex polygons were decomposed into convex ones by a Minimum Convex Decomposition scheme. Click on the image for finer details.
City environment
    
Footprint and Explicit Corridor Map [closest pts]

The algorithm
The Explicit Corridor Map with its closest points on the obstacles.
     A corridor, together with its left and right closest points. These are used to obtain an explicit description of the corridor's boundaries.
Explicit Corridor Map with its closest points
    
Left/right closest points

A desired amount of minimum clearance to the obstacles is obtained by shrinking the Explicit Corridor.     The corridor is triangulated to obtain the shortest path.
Shrunk Explicit Corridor
    
Triangulation

The shortest path is computed in linear time in the number of disks in the corridor.     A smooth path is obtained by incorporating explicit corridors into the Indicative Route Method.
Shortest path
    
Smooth, short path with clearance


Experiments (a selection)
We extracted 1,000 random corridors from the map. The average running time for extracting an Explicit Corridor was 1.19ms. Shrinking the corridor added 0.54ms. Triangulating this corridor and computing the shortest path added another 1.83ms. Hence, on average, the total time for computing the shortest (minimum-clearance) path in a corridor was 3.56ms. By using the resulting shortest paths as control paths, smooth paths were obtained, increasing the total time to 4.14ms. By having an average traveled distance of 321m, the CPU-load was 0.002% for steering a single character. Consequently, the approach is suitable for steering many characters simultaneously, as occurs in a large crowd.