Overview

This paper presents a dynamic structure allowing to enrich any nonholonomic motion planner for car-like robots with the capacity of reactiveness to environment changes. It is based on a pavement of paths by star shaped domains computed in the singular metric of the car-like robot. The algorithms to build such pavements are presented and their complexity is analyzed. We then introduce an optimization routine consisting in following the negative gradient of an energy function, the energy being the result of a combination of repulsive forces (due to obstacles) and attractive forces (tending to shorten the path). The key point of the approach is to consider the configuration space as a metric space equipped with the nonholonomic metric.

Applications to nonholonomic path planning including reactivity to moving obstacles are presented.

1 Elastic Bands and Nonholonomic Metrics

About five years ago, Quinlan and Khatib [9] proposed a dynamic trajectory modification concept called the elastic band allowing to maintain a permanent flexible and deformable path between an initial and a final robot configuration. The key point of the concept lies on a pavement of the path with collision-free bubbles, whose size and shape present a simplified and practical image of the free space around the path. The sequence of bubbles that cover the path is called a bubble band. Applying contraction forces between bubbles and repulsion forces due to the obstacles transforms the bubble band into a...