Autonomous robots have a far more difficult time than industrial robots. They must deal with time-varying environments containing unmodeled entities (humans) and with partial, inaccurate or outdated knowledge of their environment. While some researchers have nevertheless tackled the model-building problem for mobile robots (which leaves the robot with a classical motion planning problem on the map), others have sought simpler routes to navigation. These algorithms are typically online algorithms with limited state. In [95], robots navigating in the plane used local decision rules to provably reach the goal. These methods used performance measures derived from path length and were early examples of competitive ratios in path planning, [116].
Geometric models of uncertainty have been used, based on the existence of landmarks, which are uniquely recognizable features in the environment. In [90], a nearsighted robot with a bad compass wandered between ``islands'' of certainty near landmarks. In [77], a robot with better vision moved along corridors in space formed by aligning landmarks.
The argument is made below that the chief goals of autonomous robotics require a further understanding of geometric complexity. A central theme in this line of work is to determine what information is required to solve a task and how to direct a robot's actions to acquire that information. Another key question is to assess the capabilities of a robot in a given environment or class of environments.
These questions can be difficult. Structured environments, such as those found around industrial robots, contribute towards simplifying the robot's task because a great amount of information is implicitly encoded into both the environment and the robot's control program. One goal is to quantify the information encoded under the assumption that, say, the mechanics are quasi-static or the environment is not dynamic. Conversely, one might ask how much information must the control system or planner compute? Successful manipulation strategies often exploit properties of the (external) physical world (e.g., compliance) to reduce uncertainty and hence gain information. Often, such strategies exploit mechanical computation, in which the mechanics of the task circumscribes the possible outcomes of an action by dint of physical laws. Executing such strategies may require little or no computation; in contrast, planning or simulating these strategies may be computationally expensive. Since during execution one might witness very little ``computation'' in the conventional sense, traditional techniques from computer science have been difficult to apply in obtaining meaningful upper and lower bounds on the true task complexity. It is hoped that a theory can be developed to measure the sensitivity of plans to particular assumptions about the world, and to minimize those assumptions wherever possible.
Because geometry is the natural language for characterizing sensors, tasks, and the complexity of robotics operations, such an undertaking is inherently computational-geometric. More and more, robotics researchers are abandoning off-line models where a priori knowledge of the whole environment is assumed. For example, in the stereotypical off-line model, one might assume that the robot, on booting, reads a geometric model of the world from a disk and proceeds to plan. A preferred alternative now is to consider on-line paradigms where the robot investigates the world and incrementally builds data structures to the external environment. As time evolves, the task effectively forces the agent to move, sense, and update its model of the world. Certainly, from an on-line viewpoint, off-line questions such as ``what is the complexity of plan construction for a known environment, given an a priori world model?'' might often appear secondary, if not downright artificial.
While it is profitable to explore on-line paradigms for autonomous agents and sensorimotor systems, the framework remains to be extended in certain crucial directions. In particular, sensing has never been carefully considered or modeled in the on-line paradigm. The chief difficulty is the absence of tools for measuring the complexity of a robot. Just as complexity classes are characterized by the amount of resources available, one would hope to have relations between the computational power of a robot and its hardware. How much power is gained by adding an extra sensor?
Such questions have been overlooked. As a result, robot builders are able to make unverifiable claims about robot performance and resource consumption. What is missing from autonomous systems is both an accounting method to assess the capabilities of a robot and tools for arguing correctness and completeness for on-line autonomous robot algorithms. The inability to compare systems leads to redundant work and inhibits progress. Computational geometry has established a clear progress metric, while emphasizing completeness and correctness for control algorithms. But the systems for which it has explanatory power are far from real embedded systems. Yet such systems are probably best analyzed and characterized by using geometric methods. This is a direction in which computational geometry could have a significant impact.
Here is a concrete example of an on-line navigation. Some robots are purely reactive and plan their moves without retaining knowledge of their past interactions with the environment. Others build a map, ie, a geometric model of the world it encounters. The former are too weak, the latter are too slow. What are good intermediate strategies? Navigating in a graph with bounded storage is a well-studied problem in computer science. Interesting work in on-line navigation with uncertainty has already been done. To pursue this further and experiment with physical robots would be extremely useful.
The ``minimalist'' rationale of complexity theory (ie, using the minimum resources to achieve a given goal) has parallels in robotics. Resources are more diverse: they are measured by the number of sensors, sensor probes, actuators, agents, as well as by the amount of computation time and space and communication. In robotics, minimizing the use of resources has become an increasing preoccupation. It has been shown that walking/running machines could be built without static stability, that dextrous manipulation could be performed without sensing. Biped, kneed walker have been built without sensors, computers, or actuators.
Computational geometry is uniquely poised to demonstrate and prove minimalist solutions to robotics problems. Key questions include the following:
for classes of objects?
What on-line filters uses a minimum amount of sensing?
For example, with a distributed actuator system such as a MEMS
array device, one can create a
programmable vector-field for parts manipulation: First
one centers a part using a radial, inward-squeezing pattern, which
centers the part at the origin.
Next, one makes the array push in the left direction within
a narrow band around the x-axis. The rest of the array pushes in the
opposite. This strategy filters small parts to the left and
big parts to the right.