Exploration is achieved by constructing a map called the generalized Voronoi graph (GVG). In the planar case, the GVG is the set of points equidistant to two obstacles. The robot plans a path using the GVG by first planning a path to the GVG, then along the GVG, and from the GVG to the goal. If the robot knows the GVG on an environment, then it can always plan a path between two points in the environment. Likewise, if the robot can construct the GVG, then it has in essense explored its environment because it can use the GVG for future excursions into the environment. The underlying math of this approach guarantees that the robot has in-fact explored and “seen” all locations of an unknown environment.

Unfortunately for robots working in the real world, mathematical justification and simulations are not enough. We must have experiments demonstrating the validity of our theory. Quickly after some initial experiments, we realized that the mobile robot in our lab suffers from a problem common to all robots — localization error. Nominally, a robot has encoders on its wheels which count the number of times the wheels rotate and after integrating this information, the robot determines its location. Due to slippage of the robot’s wheels on the floor, the robot accrues localization error. Motivated by my colleague Dr. Sebastian Thrun’s work in Computer Science, we are developing a technique to compensate for localization error. With this technique, the robot can exploit the topology of the GVG to locate itself on the GVG map with high accuracy, despite large amounts of wheel slippage.