Building Bridges

That there is such a divide was tacitly recognised a decade ago, with the start of a move from mathematically perfect concepts such as configuration space, to more holistic approaches like the subsumption architecture. Essentially, one part of the robotics community gave up on the idea of building an internal model of the world, and decided to use the world as its own model instead. This is not to denigrate the subsumption architecture and those that have followed; they have supplied a whole set of practical solutions to practical problems. However if we want to be able to devise devices that are adaptable and that can ``think ahead'' then some model other than the world itself must be used.

One of the biggest bugbears of the perfect modelling approaches of ten years ago was speed, especially for motion planning. However by using smarter algorithms, by replacing concepts such as `completeness' by `probabilistic completeness', and by using today's computers, speed is no longer the major obstacle. There are several problems remaining though:

• Object Complexity. Robotics researchers have tended to build models of the world that are simple in both form and complexity. However real-world problems in, say, manufacturing, involve objects designed on CAD systems that have large numbers of geometric elements and specific form features (e.g., mating surfaces). The presence of such complexity often overwhelm current planners.

• Imperfect Models. Real-world objects do not agree with their models at every level of detail. Although this does not matter for some problems (e.g., gross motion planning), it is critical for others (e.g., peg-in-hole insertion).

• Run-Time Errors. Even if the plan and models were perfect, our robots are not. Planning researchers cannot continue to ignore the run-time environment.

In Oxford we have been looking at ways of closing this gap between theory and practise for many years. We started with relatively simple systems (mobile vehicles), and have been extending our ideas in a controlled manner to more complex systems (manipulators). I now believe that we have come up with an idea that is so simple that it might just work, and we are starting to build the tools to test the concept on a large scale. The idea has two parts, one of which is long-established principle of AI, and the other is one that attempts to deal with the problem of geometry:

• Problem Decomposition. This is a standard problem-solving strategy, whereby one has a hierarchy of scale, and you solve the problem at different levels and combine the results. As an example that we have studied previously: a task planner for mobile vehicles will first decide which vehicles will be assigned which tasks and in which order, based on positions only; this is followed by a coarse path planner, which generates rough paths based on a choice of approach directions; and finally a fine path planner generates trajectories based on detailed knowledge of the vehicle and load characteristics.

• Using Proximity. We wished to avoid overloading the planners with too much geometric detail, and have discovered a simple, but effective, method of doing so. We allow the planners to ask about the proximity of objects, with the answers being returned as a small vector of real numbers. Thus, for example, our vehicle planner asks about Euclidean distance (i.e., `what are the things close to me?'), and about distance to an obstacle in a particular direction (i.e., `how far can I move in a given direction?').

Using proximity in this way means that planning competence and geometric competence can be separated in an overall planning program. This makes the planners short, and easy to understand and to maintain; for example, our vehicle task planners use a rule-base of 10-100 rules. Furthermore, if the geometry gets more complex, then the code that computes the proximity measures may take longer, or need upgrading, but the planner can often stay the same.

Our earlier results showed the feasibility of this approach for robot vehicles, which of course have no more than three degrees-of-freedom. More recent results also show that the technique extends nicely to complex robot manipulators as well. Of course, there are always problems which really depend for their solution on an intimate knowledge of the robot and its environment: mating problems spring immediately to mind, and in our vehicle task planner we assume the existence of a low-level competence for docking that would be implemented using a run-time feedback loop. Even so, we claim that many planning problems in practical robotics could benefit from this separation of planning and geometry, even if only at the prototyping stage.

To demonstrate this further we are constructing a shell for building planners called OxSim, which contains a domain dependent low-level planner, an efficient routine for computing distances, and connects to a high-level planner (or planners) and to a geometric modelling system. We expect to eventually demonstrate this system constructing plans for the aerospace industry, in which a robot manipulator has to work within tight spaces in an environment that is geometrically complex (i.e., large numbers of curved facets).

Initially these experiments will deal with off-line planning only, but we believe that the same ideas also provide a convenient bridge to run-time systems. Sensors are, for the most part, devices that return range data to a greater or lesser degrees of accuracy. Thus by modifying our proximity measures slightly we should be able to take a reactive planning architecture, and use it for off-line planning; and by simulating uncertainty in the proximity measure, to produce plans off-line with some measure of certainty that they will execute off-line.