Page 391 - Introduction to AI Robotics

374
Exercise 10.12 10 Metric Path Planning
[Programming]
Obtain a copy of the Trulla simulator suitable for running under Windows. Model at
least three different scenarios and see what the path generated is.
Exercise 10.13 [Programming]
Program an A* path planner. Compare the results to the results for the Dijkstra’s
single source shortest path program from Ch. 9.

10.9 End Notes

For a roboticist’s bookshelf.
Robot Motion Planning by Jean-Claude Latombe of Stanford University is the best-
known book dealing with configuration space. 82

Voronoi diagrams.
Voronoi diagrams may be the oldest Cspace representation. Computational Geometry:
Theory and Applications 44 reports that the principles were first uncovered in 1850, al-
though it wasn’t until 1908 that Voronoi wrote about them, thereby getting his name
on the diagram.

On heuristic functions for path planning.
Kevin Gifford and George Morgenthaler have explored some possible formulations
of a heuristic function for path planning over different terrain types. Gifford also
developed an algorithm which can consider the energy savings or capture associated
with going downhill. 60
Trulla.
The Trulla algorithm was developed by Ken Hughes for integration on a VLSI chip.
Through grants from the CRA Distributed Mentoring for Women program, Eva Noll
and Aliza Marzilli implemented it in software. The algorithm was found to work fast
enough for continuous updating even on an Intel 486 processor. Dave Hershberger
helped write the display routines used in this book.