| Stanford University | ||||
| latombe@cs.stanford.edu http://robotics.stanford.edu/~latombe |
| Is motion planning all about flipping coins? |
|
Part 1: Overview The goal of motion planning is to capture the connectivity of a certain space X (e.g., the collision-free subset of a robot's configuration space) as efficiently as possible. A powerful approach consists of sampling X at random. This approach is particularly attractive when it is impractical to compute an explicit representation of X. This happens when X has many dimensions (e.g., when a robot has many degrees of freedom) and when X is characterized by complex conditions like visibility conditions with range and incidence limitations. I will describe multiple examples of randomized planning techniques for many-dof robot path planning, motion planning with dynamic constraints, brain radiosurgery planning, exploration of new environments by mobile robots, and prediction of molecular motions. All these techniques and examples demonstrate both the power and the limits of flipping coins many times. Part 2: Key research issues Learning sampling strategies Finding narrow passages in complex high-dimensional spaces Termination criterion (when to stop sampling if no solution is found?) Formal analysis of non uniform sampling techniques Efficient distance computation Efficient visibility computation Generation of constrained motions (e.g., realistic motions of digital actors) Dealing with deformable objects (e.g., human tissue in robotic surgery) Part 3: Scenarios and benchmarks Diassembly of parts from complex assemblies (e.g., aircraft engine, automobile compartment) Planning realistic manipulation motion for a digital actor Motion planning with deformable obstacles |