next up previous contents
Next: Space and Shape Representation Up: Spatial Representation and Reasoning Previous: Spatial Representation and Reasoning

Survey of Robot Reasoning in AI

Early AI projects in robotics included Minsky's ``hand-eye'' project at the Massachusetts Institute of Technology in 1966, McCarthy's ``computer with hands eyes and ears'' at Stanford University in 1968, and Rosen and Nilsson's ``intelligent automaton'' at the Stanford Research Institute in 1967. As one can deduce from the anthropomorphic titles of these projects, their overall aims were for computers to imitate human capabilities when acting in the real world, as a complement to the reasoning powers that were being developed under the auspices of AI research.

These projects were mainly concerned with investigating the technology required for a robot actuator guided by sensory data, but the techniques developed were soon applied to practical tasks - in particular the task of mechanical assembly. Robot assembly projects were soon under way at Stanford (assembling a water pump) in 1973, University of Edinburgh (assembling a toy car) in 1975, and Hitachi Central Research Lab (assembling objects from plan drawings) in 1972 [EUY+72].

These hand-eye assembly projects only had a primitive internal representation of the task they were performing. For example, the Edinburgh project, described in [ABB+75], used a camera looking from above onto a pile of white parts on a black table, and identified white areas which protruded from the general pile. A grasp at one of these positions would take hold of a single object. This object could then be pulled out of the pile, laying it flat on a clear area of the table, so that its shape could be matched against a known library of parts. Each identified part was then stored in a predefined place, so that the assembly subsystem (which used no visual information), could follow a set sequence of movements to incorporate it in the assembly.

A number of early AI programs operated on a problem domain where a robot arm was building piles of blocks on a tabletop. This problem domain became known as the ``blocks world''. Many of the programs that operated on the blocks world were not interfaced to an actual robot, or to sensing equipment. In these cases, the blocks world was simply a model in computer memory, which included only the information necessary to solve the questions that the program would be applied to. One example of such a blocks world program is the well-known SHRDLU, by Winograd, which responded to English language commands, and answered questions about the effects of its actions on the world model.

``Blocks world'' programs usually investigated reasoning capabilities which were seen as being useful to real robots. Fahlman's BUILD [Fah73] analysed the stability of piles of blocks, and planned ways in which it could build and dismantle piles without them falling over. Sussman's HACKER [Sus75] investigated machine learning by comparing the results of action plans to goals that it had formulated for those plans; it could acquire new ``skills'' by storing the debugged versions of successful plans.

Since these early projects robotics research has diversified, and now takes place at various levels of abstraction from the physical robot. Typical research topics (in order of increasing abstraction) are:

New manipulator, arm, and sensor designs.
Control of manipulators and arms, and the interpretation of sensors.
Description and specification of robot motion.
Automated motion planning.
Operation from task descriptions, rather than motion description.
Deriving assembly plans from a simple description of the assembly.

New manipulator developments include general purpose devices such as multi-fingered manipulators (e.g. [JWKB84] [LPD83]), as well as special purpose manipulators for handling unusual objects ([KTTP83] [BH82]). Arm designers experiment with different numbers of joints and different coordinate systems (spherical, cylindrical, and cartesian). New sensors include tactile and contact sensors, together with remote sensors such as sonar or optical devices (e.g. [Sie86] [RT82] [BDdRP83] [Ben83]).

Design of new actuators or sensors must consider control issues, but research continues even on the control of well-known devices. Robot arm kinematics is constantly under analysis, and the control of dextrous hands appears to be at least as complex as the design of the hand itself. The interpretation of visual images is also a very large field of research, although the methods of acquiring the images have not changed very much for 20 years.

The specification of robot motion is essential for programming robots, and a variety of techniques have been developed for describing such motion. These range from robot programming languages [GSCT83], to methods for guiding or leading the robot through a desired trajectory. All of them require methods for analysing and describing the motion of a robot arm (e.g. [Lyo85] [TPB81]).

If a robot is to plan motions for itself, it must be able to plan and evaluate possible paths. A considerable body of work has been devoted, for example, to the problem of collision avoidance for an arm moving in three dimensions [Bro83]. Motion planning issues also include compliance [LP85] - controlling the arm so that it exerts a specified force at the surface of a workpiece - and grasp analysis for manipulators [Ngu85b] [Lyo85].

An attractive goal for robot users is the ability to describe only the task that must be performed, while the robot works out for itself the details of the motions that it must carry out. This goal is called ``task-level programming'', as opposed to the ``robot-level programming'' that describes individual motions. Task-level programming languages include Lozano-Perez's LAMA [LP79] [LP76] and AUTOPASS by Lieberman and Wesley [LW77]. These languages describe tasks in terms of the workpiece, rather than in terms of the robot.

``Goal-level programming'' aims to have the robot carry out even more of the work necessary in deciding how to perform a task. A typical scenario in goal-level programming is that the programmer describes an assembly, then the robot works out for itself how to combine available parts to form the assembly. General discussions of goal-level robot programming are given by MacDonald [Mac87a] and Zhang [xZ87].

Industrial robot applications have mainly made use of developments from the first three levels of abstraction in the above list. The later three levels have only been investigated in a research context, and experimental task-level or goal-level systems often operate in a simulated ``blocks world'', rather than using real robots or workpieces. The integration of robot control across these varying levels of abstraction is an important research topic. One promising approach to this topic is hierachical integration, as proposed by Brooks [Bro85b] and Albus [Alb81].

Further progress in the more abstract levels of robot reasoning relies largely on the development of more sophisticated representations of the physical world, as has been pointed out by Brady [Bra85a]. The reasoning tasks carried out in high level robot control tend to involve qualitative rather than numerical data, as the reasoning moves further from exact motion description (this was noted by Ambler and Popplestone in developing the RAPT system for assembly goal specification [APK82] [PAB80] [AP75]). The qualitative representation for spatial reasoning described in this thesis developed from an investigation into qualitative, high-level representations for use by robots.

next up previous contents
Next: Space and Shape Representation Up: Spatial Representation and Reasoning Previous: Spatial Representation and Reasoning
Alan Blackwell