| Sign In to gain access to subscriptions and/or personal tools. |
Randomized Kinodynamic Motion Planning with Moving ObstaclesDepartment of Computer Science Stanford University Stanford, CA 94305, U.S.A., dyhsu{at}cs.stanford.edu
Department of Aeronautics & Astronautics Stanford University Stanford, CA 94305, U.S.A., kindel{at}sun-valley.stanford.edu
Department of Computer Science Stanford University Stanford, CA 94305, U.S.A., latombe{at}cs.stanford.edu
Department of Aeronautics & Astronautics Stanford University Stanford, CA 94305, U.S.A., rock{at}sun-valley.stanford.edu This paper presents a novel randomized motion planner for robots that must achieve a specified goal under kinematic and/or dynamic motion constraints while avoiding collision with moving obstacles with known trajectories. The planner encodes the motion constraints on the robot with a control system and samples the robot's state x time space by picking control inputs at random and integrating its equations of motion. The result is a probabilistic roadmap of sampled state xtime 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 an initial and a goal statextime point. The paper presents a detailed analysis of the planner's convergence rate. It shows that, if the statextime space satisfies a geometric property called expansiveness, then a slightly idealized version of our implemented planner is guaranteed to find a trajectory when one exists, with probability quickly converging to 1, as the number of milestones increases. Our planner was tested extensively not only in simulated environments, but also on a real robot. In the latter case, a vision module estimates obstacle motions just before planning starts. The planner is then allocated a small, fixed amount of time to compute a trajectory. If a change in the expected motion of the obstacles is detected while the robot executes the planned trajectory, the planner recomputes a trajectory on the fly. Experiments on the real robot led to several extensions of the planner in order to deal with time delays and uncertainties that are inherent to an integrated robotic system interacting with the physical world.
Key Words: motion planning • kinodynamic constraints • moving obstacles • probabilistic roadmaps • expansive space
The International Journal of Robotics Research, Vol. 21, No. 3,
233-255 (2002) This article has been cited by other articles:
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
 |
|
|
 |
|
Sign In to gain access to subscriptions and/or personal tools.
