Planning smooth paths for mobile robots

The authors consider the problem of planning paths for a robot which has a minimum turning radius. This is a first step towards accurately modeling a robot with the kinematics of a car. The technique used is to define a set of canonical trajectories which satisfy the nonholonomic constraints imposed. A configuration space can be constructed for these trajectories in which there is a simple characterization of the boundaries of the obstacles generated by the workspace obstacles. The authors describe a graph search algorithm which divides the configuration space into sample trajectories. The characterization of the boundaries makes it possible to calculate an approximate path in time O(n/sup 3// delta log n+Alog (n/ delta )), where n is the number of obstacle vertices in the environment, A is the number of free trajectories, and delta describes the robustness of the generated path and the closeness of the approximation. The authors also describe a plane sweep for computing the configuration space obstacle for a trajectory segment. They use this to generate robust paths using a quadtree based algorithm in time O(n/sup 4/log n+(n/ delta /sup 2/)).>