VASC Seminar Announcement
            =========================

Date: Monday, 11/1/99
Time: 3:30-4:30
Place: Smith Hall 2nd Floor Common Area

Speaker:  Steven M. LaValle
	Department of Computer Science
	Iowa State University
	http://janowiec.cs.iastate.edu/~lavalle/

Title: Rapidly-Exploring Random Trees and Motion Strategy Algorithms

Abstract:

Efficient algorithms are needed that generate motion strategies in
many geometry-intensive applications, such as robotics, virtual
prototyping, computational chemistry, and virtual human generation.
This talk will focus mainly on computing collision-free paths for
bodies that have many degrees of freedom and might also be subjected
to differential constraints (nonholonomy and dynamics).  We present a
randomized data structure and algorithm, called a Rapidly-exploring
Random Tree (RRT), which is particularly suited for these kinds of
problems.  An RRT is expanded incrementally by applying control inputs
that extend carefully-chosen vertices toward randomly-selected points
in an underlying state space.  The RRT expansion is managed in a
simple way that yields rapid initial exploration of the space, and
eventual convergence to uniform coverage if a solution is not found;
however, general completeness is sacrificed.  Search algorithms based
on RRTs automatically satisfy differential constraints, and can
exploit recent incremental collision detection algorithms and fast
nearest-neighbor algorithms to greatly improve performance.  Computed
results will be presented that show collision-free trajectories
through cluttered environments for holonomic robots, virtual humans,
car-like robots, robots pulling trailers, automobiles with dynamics,
hovercrafts, and free-floating satellites, resulting in configuration
spaces and state spaces of up to twelve dimensions.  Our recent work
on other problems, such as a randomized approach to computing feedback
motion strategies, will also be briefly discussed.