Navigating car-like robots in unstructured environments using an obstacle sensitive cost function

Abstract

We propose a method for navigating a car-like vehicle within an unstructured environment. Path planning is posed as a graph search problem. The search graph is set up in a way that implies derivation of a feed forward term for a downstream closed loop controller. An informed search algorithm is used that is guided by a heuristic cost function that accounts for both kinematic constraints of the vehicle and the topology of the vehiclepsilas free space. Configuration space obstacles are computed from an obstacle map acquired from a high definition laser range scanner and search is restricted to the collision free subset of the configuration space. The algorithm allows for solving all of the following problems: Precise parking maneuvers, narrow turns, long distance navigation. The system has been used successfully on board the autonomous car ANNIEWAY in the DARPA urban challenge competition of 2007.