Spline templates for fast path planning in unstructured environments

This paper addresses the problem of navigating a heavyweight robot autonomously across unstructured environments. The data of a 3D laser range finder are partitioned in real time into equidistant grid cells to locate obstacles and to classify the negotiability of the surface terrain. In addition to the distinction between obstacles or free space, ground measurements are examined to determine the local terrain roughness for each cell. We present a novel path planning algorithm operating on these classified grid cells. The algorithm is able to avoid positive and negative obstacles (cells without ground measurements), as well as regarding the roughness of the terrain. By applying a cost function, the robot is able to prefer routes across smooth terrain, like streets or trails, over routes across rough and muddy areas. We can determine the necessarily free terrain cells for each spline in the forefront because the splines and the dimensions of the robot are set. In this way we can access the resulting spline templates during runtime and connect them very fast for the path planning. The key feature of this approach is the low computation cost compared to existing approaches.