The investigator examines the interplay between topology and computation. In particular, issues in robot motion planning and computation with inexact data are studied in depth. Robots maneuver about in a configurations space of allowed configurations. The robot controller must have an internal model of its configuration space. As the robot learns more about the external world, its configuration space will change. Often these changes are of a fundamentally topological nature: a new obstacle appears; a new connection is found; a passage is too narrow to enter. Before one can design algorithms for robot motion, one must understand these topological changes and the manner of their occurrence. Algorithms for problems of a topological nature will also be studied. Problems such as "compute the degree of a map from one manifold to another," or "how many components are there in the complement of a polyhedron?" are of a fundamentally topological type and of interest in the field of computer graphics and combinatorial geometry. These problems are well understood from a theoretical and ideal perspective, but in practice there are several difficulties. Real world data comes with errors. These errors raise such issues as, How do we model data with errors? How does the presence of undetected errors affect the reliability of the algorithm? What is meant by general position in the presence of errors? Both robot motion planning and computational geometry with real world data, and real world data comes with errors. Operating an exact, digital machine with vague and uncertain data in a fundamental problem in robot control. The word "robot" is used here very generally. It could be anything from a parts arranger on an assembly line, to a mobile, self-contained exploratory vehicle. An understanding of the control issues dealt with in this project would have myriad consequences in any industry using such robots. The robots would be more reliable, flexible, and a utonomous.
