Kinodynamic Motion Planning in Dynamic
     Environments

Overview 
The motion of physical objects is subject to kinematic and dynamic constraints. For example, a car cannot move sidewise; a bouncing ball must obey the laws of physics. These constraints compound the difficulty of motion planning. We have extended our sampling techniques for path planning to handle objects whose motion is described by a control system, which is a set of differential equations that captures diverse types of kinematic and dynamic constraints. In particular, our implemented algorithm is fast enough to deal with moving obstacles in "real-time".

Experiments in Simulated Environments 
We tested our algorithm on two different systems. The first one consists of two wheeled mobile robots that maintains a direct line of sight as well as a minimum and a maximum distance between them (see the movie below). The second system is a cylindrical robot propelled by eight air-thrusters. It operates on a "frictionless" granite table with moving obstacles and is subject to maximum acceleration bounds due to the limited actuating forces of air-thrusters. Despite the apparent differences in these two systems, our algorithm deals with them in a unified framework.

Quicktime movie showing R2-D2 robots executing 
motion computed by the motion planner
(2.5 MB). 
Download the Quicktime viewer.

Experiments on Real Robots 
We have also experiemented with a hardware implementation of our algorithm on the second system mentioned above at the Stanford University's Aerospace Robotics Laboratory. The robot floats "frictionlessly" on the granite table using air-bearing. The roughly circular objects on the granite table are moving obstacles. An overhead vision system detects the motion of obstacles. In reponse, the robot computes a collision-free trajectory to the goal state on the fly.
    The photos show the motion of the robot in an experiment, in which the robot attempts to move to the goal state at the front of the table.

initial state manuever to avoid the incoming obstacle  

moving toward the goal

   
 

wait for the obstacle to pass

goal state

Reference  

People   
    David Hsu
   Robert Kindel
   Jean-Claude Latombe 
 

back
 

Maintained by David Hsu     Last Modified: Wed Jan 9 10:33:59 EST 2002