These problems are made difficult by a number of inherent factors. Foremost among these are uncertainty and geometric complexity. Uncertainty arises from the fact that the actions of robots are subject to error. Geometric complexity reflects the fact that real-world task environments are often complex. If we want robot strategies that are both practical and robust, we must develop algorithms that successfully deal with uncertainty and complex geometry.
Much of the previous work in the area of task-level planning for robots fails to address at least one of these issues. Many theoretical approaches are algorithmically sophisticated, but do not handle uncertainty, and may be unimplementable in practice. On the other hand, real robot systems often employ simplistic strategies that do not take into account complex geometric interactions. This thesis seeks to bridge the gap between these two extremes. We present efficient planning algorithms for motion and sensing that are both practical and algorithmically sophisticated.
Our motion planning algorithm computes one-step motion strategies that guarantee reaching a specified goal in the plane. To deal with uncertainty in robot control, we employ a control model that allows the robot to slide along obstacle surfaces, or comply with the environment. Our analysis of this algorithm yields a precise characterization of the complexity of one-step compliant motion planning with uncertainty.
Sensors are needed within autonomous systems to provide execution-time feedback. In this thesis we develop a framework for planning sensing strategies in a principled way. In particular, we present algorithms for computing the set of placements from which a sensor can monitor a region within a task environment. This work has many applications in the areas of assembly planning, cooperating robots, and robot surveillance. We have demonstrated the practicality of our approach by building a system of robot surveillance with mobile robots employing our strategies for sensor planning.