Complexity of nonholonomic motion planning

The complexity of motion planning amidst obstacles is a well modelled and u nderstood notion. What is the increase of the complexity when the problem i s to plan the trajectories of a nonholonomic robot? It is shown that this q uantity can be seen as a function of paths and of the distance between the paths and the obstacles. Various definitions of it are proposed, from both topological and metric points of view, and their values compared. For two o f them estimates are given which involve some epsilon -norm on the tangent space to the configuration space. Finally these results are applied to comp ute the complexity needed to park a car-like robot with trailers.