Obstacle Course
Escape
Ramp Climb
Half-Pipe Climb
Narrow Hall

None

Did not finish Did not finish 4.4/340 Did not finish 11.2/220

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

11.0/2457

11.5/617

< 1/100 ~ 1.3/140

< 1/173

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.

Conclusion

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: http://robotics.stanford.edu/~latombe/cs326/2007/links.htm.

References

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 Automation. 1018–1023.

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/ %7Elatombe/cs326/2007/class14/bretl.pdf.

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
www.acm.org/crossroads
Site

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:// robotics.stanford.edu/~latombe/cs326/2007/class6/class6.ppt.

6. LaValle, S. M. and Kuffner, J. J. 2001. Randomized kinodynamic planning. Int. J. Robotics Resear. 20, 5. 378–400.

 

Biography Salik Syed ( ssyed@stanford.edu) 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.