Model-Accuracy Aware Anytime Planning with Simulation Verification for Navigating Complex Terrains

Abstract

Off-road and unstructured environments often contain complex patches of various types of terrain, rough elevation changes, deformable objects, etc. An autonomous ground vehicle traversing such environments experiences physical interactions that are extremely hard to model at scale and thus very hard to predict. Nevertheless, planning a safely traversable path through such an environment requires the ability to predict the outcomes of these interactions and generate some form of a traversability map that standard path planning algorithms can utilize.

This thesis proposes an algorithmic framework for planning to navigate complex terrains. The key challenge, as mentioned above, is to know what parts of the map are traversable as quickly as possible because the planning algorithm would require this information. The method to estimate traversability is generally slow, e.g., a physics-simulator. However, we do not need traversability information for the entire map; instead, it is sufficient to cover only the relevant regions for a path-planning problem involving a start and a goal state pair. Our work tightly couples the process of building the traversability map with the graph search involved in planning for a traversable path.

Firstly, we relate traversability to the validity of an edge in the planning graph. This allows us to look at lazy motion planning algorithms that are efficient with edge evaluation. We introduce two edge-evaluators, 1) a high-fidelity physics simulator which we assume to be always correct, and 2) a learned model which can make errors but has orders of magnitude faster inference time.

Secondly, we develop an anytime planning algorithm that is aware of the learned model's errors and utilizes it wherever possible instead of the slower simulation model to speed up planning. Our algorithm, which we call MA3, utilizes the simulator efficiently only to verify paths before returning and to correct the learned model's potential errors.

We provide a theoretical analysis of the algorithm, and its empirical evaluation shows a significant reduction in planning times against contemporary lazy planning algorithms. We believe that our contribution takes a step towards autonomous navigation in complex off-road environments.