VI
In the early 80’s, pioneering works showed how to describe the free config-
uration space by algebraic equalities and inequalities with integer coefficients
(i.e. as being a semi-algebraic set). Due to the properties of the semi-algebraic
sets induced by the Tarski-Seidenberg Theorem, the connectivity of the free
configuration space can be described in a combinatorial way. From there, the
road towards methods based on Real Algebraic Geometry was open. At the
same time, Computational Geometry has been concerned with combinatorial
bounds and complexity issues. It provided various exact and efficient meth-
ods for specific robot systems, taking into account practical constraints (like
environment changes).
More recently, with the 90’s, a new instance of the motion planning problem
has been considered: planning motions in the presence of kinematic constraints
(and always amidst obstacles). When the degrees of freedom of a robot sys-
tem are not independent (like e.g. a car that cannot rotate around its axis
without also changing its position) we talk about nonholonomic motion plan-
ning. In this case, any path in the free configuration space does not necessarily
correspond to a feasible one. Nonholonomic motion planning turns out to be
much more difficult than holonomic motion planning. This is a fundamental
issue for most types of mobile robots. This issue attracted the interest of an
increasing number of research groups. The first results have pointed out the
necessity of introducing a Differential Geometric Control Theory framework in
nonholonomic motion planning.
On the other hand, at the motion execution level, nonholonomy raises an-
other difficulty: the existence of stabilizing smooth feedback is no more guaran-
teed for nonholonomic systems. Tracking of a given reference trajectory com-
puted at the planning level and reaching a goal with accuracy require non-
standard feedback techniques.
Four main disciplines are then involved in motion planning and control.
However they have been developed along quite different directions with only
little interaction. The coherence and the originality that make motion plan-
ning and control a so exciting research area come from its interdisciplinarity.
It is necessary to take advantage from a common knowledge of the different
theoretical issues in order to extend the state of the art in the domain.
About the book
The purpose of this book is not to present a current state of the art in motion
planning and control. We have chosen to emphasize on recent issues which
have been developed within the 90’s. In this sense, it completes Latombe’s
book published in 1991. Moreover an objective of this book is to illustrate the
necessary interdisciplinarity of the domain: the authors come from Robotics,
