Analysis of a Spline Based, Obstacle Avoiding Path Planning Algorithm

Abstract

The Overbot is one of the original DARPA Grand Challenge vehicles now being used as a platform for autonomous vehicle research. The vehicle, equipped with a complete actuator and sensor suite, provides for an extremely capable robotic platform with computing infrastructure and software framework already in place to create a reconfigurable testbed. For point to point navigation, calculating suitable paths is computationally difficult. Maneuvering an autonomous vehicle safely around obstacles is essential, and the ability to generate safe paths in a real time environment is crucial for vehicle viability. We previously presented a method for developing feasible paths through complicated environments using a baseline smooth path based on cubic splines. This method is able to iteratively refine the path to more directly compute a feasible path and thus find an efficient, collision free path in real time through an unstructured environment. This method, when implemented in a receding horizon fashion, becomes the basis for high level control. In this work we perform Monte Carlo simulations to validate algorithm performance. The algorithm demonstrates a high success rate for all but the toughest of environments.