Paper: Optimization-Based Terrain Analysis and Path Planning in Unstructured Environments

February 21st, 2019

Optimization-Based Terrain Analysis and Path Planning in Unstructured Environments

Accurate environment representation is one of the key challenges in autonomous ground vehicle navigation in unstructured environments.

We propose a real-time optimization based approach to terrain modeling and path planning in offroad and rough environments. Our method uses an irregular, hierarchical, graph-like environment model.

A space-dividing tree is used to define a compact data structure capturing vertex positions and establishing connectivity. The same unique underlying data structure is used for both terrain modeling and path planning without memory reallocation.

Local plans are generated by graph search algorithms and are continuously regenerated for on-the-fly obstacle avoidance inside the scope of the local terrain map.

We show that implementing a hierarchical model over a regular space division reduces graph edge expansions by up to 84%. We illustrate the applicability of the method through experiments with an unmanned ground vehicle in both structured and unstructured environments.

Fig. 1. Top-down view of our terrain analysis and path planning approach in an off-road environment (top) and corresponding first person view (bottom). The hierarchical grid can be used both at full resolution and with an adaptive resolution (top left and top right, respectively). Mesh vertex colour from green to blue indicates cost to arrive (low to high), whereas gray indicates infinite or non-explored cost. The black path indicates the global plan, whose intersection with the local map in the top right corner is the only reference point the local planner is aware of. The red path indicates the local plan found in the graph. Both the white pole and the large vehicle are detected as obstacle regions as indicated by gray vertices.

Ueli Graf, Paulo Borges, Emili Hernandez, Roland Siegwart, and Renaud Dube. ICRA 2019.

To learn more, contact us.

Subscribe to our News via Email

Enter your email address to subscribe and receive notifications of new posts by email.