David Hsu, Stanford University, Stanford, CA
Robert Kindel, Stanford University, Stanford, CA
Jean-Claude Latombe, Stanford University, Stanford, CA
Stephen Rock, Stanford University, Stanford, CA

A randomized motion planner is presented for robots that must avoid collision with moving obstacles under kinematic and dynamic constraints. This planner samples the robot's state time space by picking control inputs at random and integrating the equations of motion. The result is a probabilistic roadmap, i.e., a collection of sampled state time points, called milestones, connected by short admissible trajectories. The planner does not precompute the roadmap; instead, for each planning query, it generates a new roadmap to connect the input initial and goal state time points. This paper shows that the probability that the planner fails to find a trajectory when one exists quickly goes to 0 as the number of milestones grows. The planner has been tested successfully in both simulated and real environments. In the latter case, a vision module estimates the obstacle motions just before planning, and the planner is then allocated a small amount of time to compute a trajectory. If a change in obstacle motion is detected while the robot executes the planned trajectory, the planner re-computes a trajectory on the fly.