Did not finish
Did not finish
Did not finish
Planner Tests (Time in seconds/Number of Milestones)
Distance Heuristic Only Complexity Sampling Distance + Complexity
Did not finish Did not finish 31.0/5232
Did not finish Did not finish Did not finish
12.3/843 34.4/4033 25.2/1701
Did not finish Did not finish 18.5/1917
3.8/105 9.8/1277 < 1/210
Distance + Complexity + Z reasoning
Table 1: Results from running the planner on various terrain. All tests were done on a dual-core 1. 8 GHz machine with 1 GB of
memory. Tests that did not finish exceeded either the time or memory limit.
sequence, this method quickly breaks down. Like many planning heuristics, the approach taken has environments in which the heuristics misguide the search. Fortunately, in most practical cases, these heuristics
work well. To improve performance, a multistage method similar to the
one used for climbing robots [ 2] may be useful in finding paths quickly.
After implementing the bulk of the methods, the planner worked fairly
well in simple dynamic environments. The skateboard robot was able
to properly go up and down a half-pipe and skate up and down ramps.
The planner was able to adapt quickly between regions that required
complex navigation and those that could be solved easily. For a final
test, the board was placed in a room where the only way to get out was
by climbing a ramp and jumping out, which the planner was able to do,
albeit with a highly non-optimal path. In the future, more robust methods will be needed, as the planner failed to produce results with problems that required utilizing more than two to three ramps. A multistage
planning approach may work better. For more information, see [ 2]. I
have presented only a glimpse at the field of motion planning as well as
a peek at simple methods for improving planner performance in constrained dynamic environments. There is a vast array of research on the
subjects of planning for humanoid robots, climbing robots, and more.
Interested readers can find more information at this Web page:
1. Boor, Overmars, M. H., and van der Stappen, A. F. 1999. The
Gaussian sampling strategy for probabilistic roadmap planners.
In Proceedings of IEEE International Conference on Robotics and
2. Bretl, T. 2006. Motion planning of multi-limbed robots subject to
equilibrium constraints: The free-climbing robot problem. Int. J.
Robotics Resear. 2, 4. 317–342. http://robotics.stanford.edu/
3. Hsu, D., Kindel, R., Latombe, J. C., and Rock, S. 2002. Randomized
kinodynamic motion planning with moving obstacles. Int. J. Robotics
Resear. 21, 3. 233–255.
Visit the NEW
4. Hsu, D., Latombe, J.C., and Kurniawati, H. 2006. On the probabilistic foundations of probabilistic roadmap planning. Int. J. Robotics
Resear. 25, 7. 627–643.
5.La tombe, J. C. Probabilistic roadmaps: Basic techniques lecture. http://
6. LaValle, S. M. and Kuffner, J. J. 2001. Randomized kinodynamic
planning. Int. J. Robotics Resear. 20, 5. 378–400.
Salik Syed ( firstname.lastname@example.org) is a sophomore at Stanford University majoring in computer science. His interests are robotics, computer
graphics, and artificial intelligence. He would like to thank Doug Green
and Jean-Claude Latombe for introducing him to robotics.