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.

r2d2

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 towards the goal
Wait for the obstacle to pass Goal state

References

  • D. Hsu, R. Kindel, J.C. Latombe, and S. Rock. Randomized kinodynamic motion planning with moving obstacles. Int. J. Robotics Research, 21(3):233–255, 2002.
    PDF

  • D. Hsu, R. Kindel, J.C. Latombe, and S. Rock. Control-based randomized motion planning for dynamic environments. In B.R. Donald and others, editors, Algorithmic and Computational Robotics: New Directions—Proc. Workshop on the Algorithmic Foundations of Robotics (WAFR), pp. 247–264, A. K. Peters, Wellesley, MA, 2000.
    PDF

  • R. Kindel, D. Hsu, J.C. Latombe, and S. Rock. Kinodynamic motion planning amidst moving obstacles. In Proc. IEEE Int. Conf. on Robotics & Automation, pp. 537–543, 2000.
    PDF

People