Complexity of nonholonomic motion planning

The complexity of motion planning amidst obstacles is a well modelled and understood notion. What is the increase of the complexity when the problem is to plan the trajectories of a nonholonomic robot? It is shown that this quantity 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 of them estimates are given which involve some ε-norm on the tangent space to the configuration space. Finally these results are applied to compute the complexity needed to park a car-like robot with trailers.