Page 367 - Introduction to AI Robotics

350
9 Topological Path Planning
a. Program the robot to visit each landmark in any order specified by a user.
b. Place the landmarks at different locations. Implement Dijkstra’s single source
shortest path algorithm to compute the shortest path between two points specified
by a user.
c. Implement a minimal spanning tree algorithm to allow the robot to visit all way-
points efficiently.

9.8 End notes

Of batteries and topological navigation.
The CSM entry did not place due to massive hardware failures with the power supply
on Clementine. At one point, the team was using the car battery from the school
van parked outside the Seattle Convention Center. We’d drive up, park, I’d take the
battery out in the open, and walk into the convention center, and we’d return it to the
van to drive to their housing in the wee hours of the morning. No security guard or
policeman ever said a word. See the Summer 1995 issue of AI Magazine for an article
on the winners.
Topological navigation examples.
The figures and printouts of the topological navigation system used by the CSM team
were prepared by Paul Wiebe.