J.P. Laumond
LAAS-CNRS, Toulouse, France
Robot path planning via random sampling:
some remarks about controllability and combinatorial topology.
For small-time controllable systems moving among obstacles, the
existence of a collision-free path between two points is characterized
by the existence of a single connected component containing both
points in the collision-free space. Making this property effective
requires the use of (exact) steering methods (e.g., open loop
controls). Their choice is critical with respect to combinatorial
issues.
In this talk we introduce the so called "visibility roadmaps": they
are graphs tending to capture both coverage and connectness of the
collision-free space. In a first part we will see that the existence
of such roadmaps depends on the considered steering method. Then we
will present a probabilistic algorithm to compute them. We will
illustrate the performance of the algorithm for path planning via
Move3D, a software platform dedicated to path planning. Finally we
will conclude on open questions dealing with random sampling and
and percolation phenomena.
Abstract in Postscript
Back to program of MCR2000