A Mobile Automaton: An Application of Artificial Intelligence Techniques

I Introduction

At the Stanford Research Institute we are im­ plementing a facility for the experimental study of robot systems. The facility consists of a time­ shared SDS-940 computer, several core-loads of pro­ grams , a robot vehicle, and special interface equipment.

A MOBILE AUTOMATON: AN APPLICATION OF ARTIFICIAL INTELLIGENCE TECHNIQUES

by

Nils J. Nilsson Stanford Research Institute Menlo Park, California

Several earlier reports 1 and papers 2 - 4 de­ scribing the project have been written; in this paper we shall describe its status as of ear ly 1969 and discuss some of our future plans.

The robot vehicle itse lf is shown in Fig. l. It is propelled by two stepping motors independent­ ly driving a wheel on e ither side of the vehi c le. It carri es a vidicon television camera and optica l range-finder in a movable "head ." Control logic on board the vehicle routes commands from the computer to the appropriate act ion sites on the vehicle. In addition to the drive motors, there are motors to control the camera focus and iris settings and the tilt angle of the head. (A motor to pan the head is not yet used by present programs. ) Other compute r commands arm or disarm interrupt l ogic , control power switches, and request readings of the status of various registers on the vehicle. Besides the television camera and range-finder sensors, several "cat-whisker" touch-sensors are attached to the vehicle's perimeter. These touch sensors enable t he vehicle to know when it bumps into something. Commands from the SDS-940 computer to the vehicle and informat ion from the vehicle to the computer are sent over two special radio links, one for narrow-band telemetering and one for trans­ mission of the TV video from the vehic l e to the computer.

The purpose of our robot research at SRI is to study processes for the real-time contro l of a robot system that interacts with a complex environ­ ment. We want the vehicle to be able to perform various tasks that require it to move about in its environment or to rearrange objects. In order to accomplish a wide variety of tasks rather than a few specific ones, a robot system must have very general methods. What is required is the integra­ tion in one system of many of the abilities that are usually found separately in individual Artifi ­ c ial Intelligence programs.

We can group most of the needed abilities into three broad classes: (l) problem-solving, (2) mod­ elling, and (3) perception:

(1) Problem-Solving

A robot system accomplishes the tasks given i t by performing a sequence of primitive actions, such as wheel motions and camera readings. For effi ­ ciency, a task should first be ana lyzed into a sequence of primitive actions cal cu l ated to have the desired effect. This process of task ana lysis is often called planning, because it is accom­ plished before the robot begins to act. Obviously, in order to plan, a robot system must "know" about the effects of its act ions.

(2) Modelling

A body of knowledge about the effects of ac­ tions is a type of model of the world, A robot problem-solving system uses the information stored in the model to ca l culate what sequence of actions will cause the world to be in a desired state. As the world changes, either by the robot's own ac­ t ions or for other reasons, the model must be up­ dated to record these changes. Also, new informa ­ tion learned about the world should be added to the model.

(3) Perception

Sensors are necessary to give a robot sys tem new information about the world. By far the most important sensory system is vision, since it al­ lows direct perception of a good sized piece of the wor ld beyond the range of touch. Since we as­ sume that a robot system will not a lways have stored in its model every detail of the exact con­ figuration of its world and thus cannot know pre­ cisely the effects of its every action, it also needs sensors with whi ch to check predicted con­ sequences against reality a s it executes its plans.

The integrat ion of such abilities into a smoothly-running, efficient system presents both import ant conceptual problems and serious practica l challenges. For example, it would be infeasible for a single problem-solving system (using a single model) to attempt to calculate the long chains of primitive actions needed to perform lengthy t asks. A way around th i s difficulty is to program a number of coordinating "action-units," each with its own problem-solving system and model, and each respon­ sible for planning a nd executing a specialized funct ion. In planning how to perform its p articu­ l ar function, each action-unit knows the effects of executing functions handled by various of the other action-units. With this knowledge it composes its plan as a sequence of other functions (wi t h the appropria te argument s ) and l eaves the planning re­ quired for each of these funct ions up to the action-unit s respons i b l e for executing them at the time they are to be executed .

Such a system of interdepende n t action-units implies certain add itiona l problems involving com­ munication of informat ion a nd transfer of control between units. When such a system i s implemented on a serial computer with limite d core memory, ob­ vious pract ica l difficulties a rise connected with swapping program segments in a nd out of core and hand ling interrupts in rea l t ime. The coordinated action-uni t scheme serves as a useful guide in ex­ plaining the operation of our system, even though practica l necessities have dictated occasional de­ v i at ions from this scheme in our implementat ion. In the next sect ion we shall discuss the problem­ sol ving processes a nd mode l s assoc i ated with some specif i c functions of the present SRI robot system.

II SOME SPECIFIC FUNCTIONS OF THE ROBOT SYSTEM AND THEIR ASSOCIATED PROBlEM­

• SOLVING PROCESSES AND MODELS

A. Low Level Functions

The robot system is capable of execut ing a number of func tions that vary in complexit y from the simple ability to turn the drive whee ls a cer­ tain number of steps to the ability to collect a number of boxes by pushing them to a common area of the room. The organization of these functional action-units is not strict ly hiera rchical, a l­ though for descriptive convenience we will divide them into t wo c l asses: low leve l and high l eve l functions.

Of the functions that we shall mention here, t h e simplest a re certain primitive assembly l an­ guage routines for moving the wheels, tilting t he head, reading a TV picture, and so on. Two ex­ amples of these are MOVE and TURN; MOVE causes the vehicle to roll in a straight line by turning both drive wheels in unison, a nd TURN causes the vehicle to rotate about its center by turning t he drive whee ls in opposite directions. The a r gument s of MOVE a nd TURN are the number of steps that the drive wheels a re to turn (each step resulting in a vehicle motion of 1/32 inch) and "status" argu­ ments that allow que ries to be made about whether or not the function has been completed.*

Once begun, the execution of a ny function proceeds either until it is completed in i ts norma l manner or unt il it is ha l ted by one of a number of "abnormal" c irc umst a nces , such as t he vehicle bumping into unexpected objects, overload conditions, resource exhaustion, and so on . Under ordinary operation, i f execution of MOVE resu l ts in a bump, motion is stopped a utomat i cally by a special mecha nism on the vehi c l e . Thi s mechanism can be overridde n by a special instruction from the computer, however, to enable the robot to push ob jects .

The prob l em-solving systems for MOVE and TURN are trivial ; they need only to ca l culate what sig­ na ls shall be sent to registers associated with t he motors in order to compl ete the desired number of ste ps.

At a l eve l just above MOVE a nd TURN is a func­ t ion whose execution causes the vehic l e to trave l directly to a point s pec i f i ed by a pair of (x, y ) coordinates . This function is implemented in the FORTRAN routine LEG. The model used by LEG con ­ tains informa tion about the robot 's present (x,y ) locat ion and heading relative to a g i ven coordinate sys tem a nd informat ion about how far the vehicle travels for each step a pplied to the stepping motors. This informa tion is stored a l ong wi th some other special const ants in a structure called t he PARAMETER MODEL. Thus for a g iven (x,y )

* Our impleme ntation a llows a program calling routines like MOVE or TURN to run in parallel with the motor funct i ons they initiate .

destination as an argument of LEG, LEG's problem­ solving system calculates appropriate arguments for a TURN and MOVE sequence and then executes this sequence. Predicted changes in the robot's locat ion a nd heading caused by execution of MOVE a nd TURN are used to update the PARAMETER MODEL.

Ascending one more level in our system , we en­ counter a group of FORTRAN "two-letter" routines whose execution can be initiated from the tele­ type. Our action-unit system ceases to be strict­ l y hierarchical at this point, since some o f the two-letter commands can cause others to be exe ­ cuted.

One of these two-letter commands, EX, t akes as a n argume nt a sequence of (x,y) coordinate posi­ t i ons. Execution of EX causes the robot to travel from i ts pre sent position directly to the first point in the sequence, thence directly to the second, and . so on until the robot reaches the last point in the sequence. The problem-solving system for EX simply needs to know the effect caused by execution of a LEG program a nd composes a chain of LEG r outines, each with arguments provided by the s uccess ive points specified in the sequence of points. Under ordinary operation, if one of these LEG routines is h a lted due to a bump, EX backs the veh i c l e up slightly and then halts. A special feature of our implementation is the ability to a rm a nd service interrupts (such as caused by bumps ) at the FORTRAN programming level.

Another two-letter command, PI , causes a pic ­ ture to be read after the TV camera has been a imed at a specified position on the floor. The problem­ sol v ing system for PI thus calculates the appro­ pr i ate arguments for a TURN routine and a head­ tilt ing routine; PI then c a uses these to be exe­ cuted, reads in a pic ture from the TV camera, and performs processing necessary to extract informa­ tion about empty areas on the floor. (Det a ils of the pic ture processing programs of the robot sys­ tem are desc ribed in Se c . III below.)

The ability to travel by the shortest route to a s peci f i e d goal position along a path calculated to avoid bumping into obstacles is provided by the two-letter c ommand TE. Execution of TE involves t h e calculation of a n appropriate sequence of points for EX a nd the execution of EX. This appro­ pr i ate sequence is calculated by a special problem­ so l ving system embodied in the two-le tter command PL.

The source of information about the world used by PL is a planar map of the room called the GRID MODEL. The GRID MODEL is a hierarchically orga­ nized system of four-by-four grid cells. Initially the "whole ·world" is represented by a four-by-four a rray of ce lls. A given cell can be either empty (of obstacles), full, partially full, or unknown. Each partia lly full cell is further subdivided into a four-by-four a rray of cells, and so on, until all parti a lly full cells represent area s of some suit­ abl y small size. (Our present system splits cells down to a depth of three levels, representing a sma llest area of about 12 inches.)

Special "model maint e nance" programs ins ure that the GRID MODEL is a utoma tica lly updated by informa tion about empty a nd full floor area s gained by either successful execution or inter­ ruption o f MOVE commands.

The PL prog ram first uses the GRID MODEL to compute a network or graph of "nodes." The nodes correspond to points in t he room opposite corner s of obstacles; the shortest path to a goal point will the n pass t hrough a sequence of a subset of these nodes. In Fig. 2 we show a complete GRID MODEL of a room cont a ining t hree objects. The robot's position, marked "R," and the goal posi­ tion, marked "G," together with the nodes A, B,C,D, E,F,H,I,J a nd K a re shown overlaid on the GRID MODEL. The program PL then determines that the shortest pa th is the sequence of point s, R,F,I, and G by employing an optimal graph-searching a l go­ rithm developed by Hart, et al.5

If the GRID MODEL map of the wor ld contains unknown space, PL must dec ide whether or not to treat this unknown space as full or empt y . Cur­ rently, PL multiplies t he l e ngth o f any s egment o f the route through unknown space by a parameter k. Thus if k=l, unknown space is treated as empty; values of k greater than unity cause routes through known empty space to be preferred to possibly shorter routes through unknown space.

Execution of TE is accompli shed by first read­ ing and processing a picture (using PI with the camera a imed at the goal position) a nd taking a range-finder reading. The information about full a nd empty floor areas thus gaine d is added to the GRID MODEL. A route based on the updated GRID MODEL is then planned using PL, and t he n EX is exe­ cuted using the arguments ca lculated by PL. If the EX called by TE is halted by a bump, a procedure attempts to manuever around the interfering ob­ stacle, and then TE is called to start over aga in. Thus, v ision is used only a t the beginning of a journey and when unexpected bumps occur a long the journey.

Although our present robot system does not have manipulators with which to pick up objects, it can move object s by pushing them. The funda­ mental ability to push objects from one place to another is programmed into another two-letter FORTRAN routine, called PU. Execution of PU causes the robot to push an object from one named position a long a straight line path to another named posi­ tion. The program PU takes five arguments: the (x ,y) coordinates of the object to be pushed, the " size" or maximum extent of the object about its center of g ravity, and the (x,y) coordinates of the spot to which the object is to be pushed. The problem-solving system for PU assembles an EX, a TURN, and t wo MOVE commands into a sequence whose execution will accomplish the desired push. First a location from which the robot must begin pushing the object is computed. Then PL is used to plan a route to this goal locat ion. The sequence of points along the route serves as the a rgument for EX that is then executed. (Should EX be stopped by a bump, PUis started over again.) Next, PU's problem-solving system (using the PARAMETER model) calculates an argument for TURN that will point the robot in the direction that the object is to be pushed, A large argument is provided for the first MOVE command so that when it is executed, it will bump into the object to be pushed and auto­ matically halt, After the bump and halt, the automatic stopping mechanism on the vehicle is overridden and the next MOVE command is executed with an argument calculated to push the object the desired distance,

B, Higher Level Functions

As we ascend to higher level functions, the required problem-solving processes must be more powerful and general, We want our robot system to have the ability to perform tasks possibly requir­ ing quite complex logical deductions, What is needed for this type of problem-solving is a gen­ eral language in which to state problems and a powerful search strategy with which to find solu­ tions. We have chosen the language of first-order predicate calculus in which to state high level problems for the robot. These problems are then solved by an adaptation of a "Question Answering System" QA-3, based on "resolution" theorem­ proving methods,6-9

As an example of a high level problem for the robot, consider the task of moving (by pushing) three objects to a common place, This task is an example of one that has been executed by our pres­ ent system. If the objects to be pushed are, say, OBl, OB2, and OB3, then the problem of moving them to a common place can be stated as a "conjecture"

for QA-3:

(~p,s)(POSITION (OBl,p,s)

A POSITION (OB2,p,s) A POSITION (OB3,p,s)}

(That is, "There exists a situation s and a place p, such that OBl, OB2, and OB3 are all at place pin situations,") The task for QA-3 is to "prove" that this conjecture follows from "axioms" that describe the present position of objects and

the effects of certain actions,

Our formulation of these problems for the theorem-prover involves specifying the effects of actions in terms of functions that map situations into new situations, For example, the function PUSH (x,p,s) maps the situation s into the situa­ tion resulting by pushing object x into place p, Thus two axioms needed by QA-3 to solve the push­ ing problem are:

(Vx,p,s)(POSITION (x,p, PUSH (x,p,s))}

and

The first of these axioms states that if in an arbitrary situation s, an arbitrary object x is pushed to an arbitrary place p, then a new situation, PUSH (x,p,s), will result in which the object x will be at position p, The second axiom states that any object will stay in its old place in the new situation resulting by pushing a dif­ ferent object.

In addition to the two axioms just mentioned, we would have others describing the present posi­ tions of objects, For example, if OBl is at co­ ordinate position (3,5) in the present situation, we would have:

POSITION (OBl, (3,5), PRESENT)

(This information is provided automatically by routines that scan the GRID MODEL, giving names to clusters of full cells and noting the locations of these clusters,)

In proving the truth of the conjecture, the theorem-prover used by QA-3 also produces the place p and situation s that exist. That is, QA-3 determines that the desired situation s is:

s =PUSH (OB3, (3,5), PUSH (OB2, (3,5), PRESENT)).

All of the information about the world used by QA-3 in solving this problem is stored in the form of axioms in a structure called the AXIOM MODEL. In general, the AXIOM MODEL will contain a large num­ ber of facts, more than are necessary for any given deduction,

Another LISP program examines the composition of functions calculated by QA-3 and determines those lower level FORTRAN two-letter commands needed to accomplish each of them, In our present example, a sequence of PU commands would be assem­ bled, In order to calculate the appropriate argu­ ments for each PU, QA-3 is called again, this time to prove conjectures of the form:

(~p,w)(POSITION (OB2,p,PRESENT) A SIZE (OB2,w)}

Again the proof produces the p and w that exist, thus providing the necessary position and size arguments for PU, (Size information is also auto­ matically entered into the AXIOM MODEL by routines that scan the GRID MODEL.)

In transferring control between LISP and FORTRAN (and also between separate large FORTRAN segments), use is made of a special miniature moni­ tor system called the VALET, The VALET handles the process of dismissing program segments and starting up new ones using auxiliary drum storage for transferring information between programs,

The QA-3 theorem-proving system allows us to pose quite general problems to the robot system, but further research is needed on adapting theorem­ proving techniques to robot problem-solving in order to increase efficiency.* The generality of theorem-proving techniques tempts us to use a single theorem-prover (and axiom set) as a problem­ solver (and model) for all high level robot abili­ ties. We might conclude;-however, that efficient operation requires a number of coordinating action­ unit structures, each having its own specialized t heorem-prover and axiom set and each responsible for relatively narrow classes of functions.

* We can easily propose less fortunate axiomatiza­

tions for the "collecting objects task" that would prevent QA-3 from being able to solve it.

Another LISP program enables commands stated in simple English to be executed.10,11 It also accepts simple English statements about the en­ vironment and translates them into predicate cal­ culus statements to be stored as axioms. English commands are ordinarily translated into predicate ca lculus conjectures for QA-3 to solve by produc­ ing an appropriate sequence of subordinate func­ tions. For some simple commands, the theorem­ prover is bypassed and lower level routines such as PU, TE, etc., are called directly.

The English program also accepts simple English questions that require no robot actions. For these , it uses QA-3 to discover the answer, and then it delivers this answer in English via the teletypewriter. (Task execution can also be reported by an appropriate English output.)

III VISUAL PERCEPTION

Vision is potentially the most effective means for the robot system to obtain information about its world. The robot lives in a rather antiseptic but nevertheless real world of simple objects-­ boxes, wedges, walls, doorways, etc. Its visual system extracts information about that world from a conventional TV picture. A complete scene analy­ s is would produce a description of the visual scene, inc luding the location and identification of all visible objects. Currently, we have two separate operating vision programs. One of these produces line drawings, and has been used for some time to identify empty floor space, regions on the floor into which the robot is free to move. The other, which is more recent, locates and identifies the major, non-overlapping objects. In this section we shall give brief descriptions of how these pro­ grams operate.

A. Line Drawing Program

The line drawing program produces a line draw­ ing representation of a scene by a series of essen­ tially local operations on a TV picture.* Fig. 3a shows a typical digitized picture, which is stored in the computer as a 120 x 120 array of 4-bit (16level) intensity values. The scene shown is fairly typical, and includes some of the problems of mild shadows and reflections, some faint edges, and ob­ jects not 'completely in the field of view.

* Most of these operations were adaptations of earlier work by Roberts.l2 Details of our pro­ cedures, together with a description of special hardware for doing them efficiently, are given in Refs. 1 and 4.

The first of the loca l operations is a digital differentiation used to find points where there are significant changes in light intensity. These changes usually occur at or near the boundaries of objects, as can be seen from Fig. 3b. The next step is to determine the local direction of these boundaries. This is done by systematically plac­ ing small masks over the differentiated picture , and looking for places where the masks line up we ll with the gradient. Fig. 3c shows the locations and orientations of masks that responded strongly.

The next step is to fit these short line seg­ ments with longer straight lines. This is done by first grouping the short line segments, and then fitting a single straight line to a ll of the seg­ ments in a group. Grouping is a systematic pro­ cedure in which short segments are linked i f they are sufficiently close in location and orientation . Fig. 3d shows the results of fitting longer lines to the segments in each group. The final step is to join the endpoints of these long lines to pro­ duce a connected line drawing. This is done by considering the endpoints one at a time and creat­ ing candidate connections--straight connections to neighboring endpoints, extrapolations to points of intersection, extrapolations toT-junctions, etc. The candidate that best fits the corresponding part of the derivative picture is the one selected. The final line drawing produced by this procedure is shown in Fig. 3e.

While the line drawing preserves much of the information in the quantized picture in a compact form, it often contains flaws due to missing or extra line segments that complicate its analysis. Currently, the only information we extract from the line drawing is a map of the open floor space. A program called floor boundary first finds a path along those line segments that bound the floor space in the picture. These lines are typically the places where the walls or objects meet the floor, or where sides of objects obscure our view of the floor. Fig. 3f shows the floor boundary extracted from the line drawing.

Now corresponding to any point in the picture is a ray going from the lens center of the camera through the picture point and out into space . This ray is the locus of all points that can produce the given picture point. If we follow the rays going through points on the floor boundary to the points at which they pierce the floor, we obtain an ir­ regular polygon on the floor that bounds space known to be empty. In this way the line drawing is used to identify empty floor space, and the vision system enters information about open area into the GRID MODEL.

B. Object Identification Program

Were the line drawing program able to produce a perfect line drawing, the analysis needed to locate and identify objects in the scene would be relatively straightforward . However, the line drawing often contains flaws that seriously com­ plicate its analysis. Some of these flaws could be corrected by more elaborate local processing.

However, there is a limit to how well local pro­ cessing can perform, and when significant edges cannot be told from insignificant edges on the basis of local criteria, the goal of producing a perfect line drawing in this way must be abandoned,

The object identification program locates and identifies non-overlapping objects by gathering and interpreting evidence supplied by local opera­ tors, The program consists of two parts: a reper­ toire of local operators and an executive. The local operators process the gradient picture to perform tests such as deciding whether or not there is a line between two points, or finding all lines leaving a given point. Each operator returns not a single answer, but a set of possible answers with associated confidences (ideally, probabilities) that each answer is in fact correct. The executive explores the scene by calling local operators and evaluating the results in the light of both prior test results and built-in knowledge of the world.

The executive program is organized as a deci­ sion tree. Each node in the tree specifies that a particular test is to be performed. The branches leaving a node correspond to the possible test out­ comes, and since each outcome has an associated confidence, these confidences are attached to the branches.

A given node in the tree can be thought of as representing a hypothesis about the contents of the scene. This hypothesis is simply that the scene is partially described by the test results specified by the path from the start node to the given node. The hypothesis is given a confidence by combining the confidences of these test results. The test called for at the given node is designed to provide an answer that will tend to confirm or infirm the hypothesis,

An analysis of a scene proceeds as a search of the decision tree described. At any stage in the search we have a partially expanded tree corres­ ponding to the tests already performed. The nodes at the tips of this partial tree, which we shall call open nodes, present us with a choice of pos­ sible next tests (or, alternatively, hypotheses to be further investigated). The open node with high­ est associated confidence is selected for expansion, i.e., the test called for by that particular node is performed. The search proceeds until the open node with highest confidence is a terminal node of the tree. A terminal node typically represents a complete description of at least a portion of the scene, and hence constitutes at least a partial "answer." (Certain terminal nodes correspond to impossible physical situations; in this event, the search is resumed at the next most confident node.) After returning a partial answer the portion of the scene containing the object found is deleted and the analysis begins again. Thus the tree search is iterated until the scene contains no further ob­ jects.

The decision tree itself embodies the strategy for searching the scene. The basic ideas behind this strategy are simple, and will be illustrated by following the operation of the program on the scene of Fig. 3a. The first operation called for is a search for vertical lines, since these are usually both reliably detectable and significant. Fig. 4a shows that the appropriate operator found three ver­ tical lines, which happened to rank in confidence as numbered.

Starting with the highest confidence line and checking to see that its lower endpoint was within the picture, the program next looked for other lines leaving that endpoint. A failure here would have led to the conclusion that something was strange, and therefore to a transfer to the next most confident node in the tree. However, a "spur" was detected, as shown in Fig. 4b. Hypotheses that the lower endpoint was connected to the lower end­ points of other verticals were rejected because the direction of the spur was not correct. Thus, at this point attention was shifted to the top of the vertical. A spur was found there, as expected, and that spur was followed to its endpoint as shown in Fig. 4c. The fact that its endpoint was on the picture, coupled with the fact that the program had failed in its attempt to connect the vertical to other verticals, provided strong evidence that a wedge had been found. A further check of the angle at the top of the vertical confirmed the wedge hy­ pothesis, and the same calculations used in the floor boundary program were used to locate the lower vertices.

At this point one object had been found and identified, and a search for other objects began, On the second iteration, the remaining verticals were successfully joined at their lower endpoints, as shown in Fig. 4d, and various spurs were found, as shown in Fig. 4e. A similar attempt to spot a wedge failed to produce strong evidence, as shown in Fig. 4f, and the final output indicated the ex­ istence and location of an object partly out of view without specifying what it was. At this point there were no more vertical lines, and the analysis was completed.

The object identification program is capable of locating and often identifying non-overlapping ob­ jects on the basis of partial information. There are a number of obvious ways in which it can be improved and extended, and further research will be devoted to these tasks. However, even as it stands it can provide the robot with much valuable infor­ mation about the robot's world.

IV CONCWSIONS

There are several key questions that our work has helped to put into focus, Given that a robot system will involve the successful integration of problem-solving, modelling, and perceptual abilities, there are many research questions concerning each 0f these. Let us discuss each in turn.

A. Problem-Solving

Our so~ewhat hierarchical organization of problem-solvers and models seems a natural, even if ad hoc, solution to organizing complex behavior. Are there alternatives? Will the use of theorem­ proving techniques provide enough generality to permit a single general-purpose problem-solver, or will several "specialist" theorem-provers be needed to gain the required efficiency?

Other questions concern the use of theorem­ proving methods for problem-solving, How do they compare with the "production methods" as used by the General Problem Solver (GPS) or with the pro­ cedural language approach as developed by Fikes? 13 Perhaps some combination of all of these will prove superior to any of them; perhaps more experience will show that they are only superficially dif­ ferent.

Another question is:. To what level of detail should behavioral plans be made before part of the plan is executed and the results checked against perceptual information? Although this question will not have a single answer, we need to know upon what factors the answer depends,

Our problem-solving research will also be directed at methods for organizing even more com­ plex robot behavior. We hope eventually to be able to design robot systems capable of performing complex assembly tasks requiring the 'intelligent use of tools and other materials,

B. Modelling

Several questions about models can be posed: Even if we continue to use a number of problem­ solvers, must each have its own model? To what extent can the same model serve several problem­ solvers? When a perceptual system discovers new information about the world, should it be entered directly into all models concerned? In what form should information be stored in the various models? Should provisions be made for forgetting old in­ formation? Can a robot system be given a simple model of its own problem-solving abilities? En­ suing research and experience with our present system should help us with these questions.

c. Visual Perception

The immediate vision problems involve includ­ ing more tests in the object identification program to complete unfinished analysis, and removing the restriction to non-overlapping objects. Beyond these improvements there are still longer range problems to be solved, The scene analysis programs implicitly store information about the world in their structure. Changes in the robot's world can require extensive changes to the whole program. What program organization would minimize these problems? How can the scene analysis program in­ terrogate and use facts stored in the model to advantage? Since "facts" obtained from either the model or the subroutines are subject to error, it is natural to accompany them by a confidence mea­ sure, How should these confidences be computed and how should they be combined, since, loosely speaking, we operate under conditions of strong statistical dependence? How can we augment the cur­ rent repertoire of subroutines with others to make use of such properties as color, texture and range? Future vision research will be devoted to answering questions such as these.

The main theme of the project has been, and will continue to be, the problem of system integra­ tion. In studying robot systems that interact with the real world, it seems extremely important to build and program a real system and to provide it with a real environment. Whereas much can be learned by simulating certain of the necessary f unc­ tions (we use this strategy regularly), many im­ portant issues are likely not to be anticipated at all in simulations, Thus questions regarding, say, the feasibility of a system of interacting action­ units for controlling a real robot can only be con­ fronted by actually attempting to control a real robot with such a system, Questions regarding the suitability of candidate visual processing schemes can most realistically be answered by experiments with a system that needs to "see" the real world. Theorem-proving techniques seem adequate for solv­ ing many "toy" problems; will the full generality of this approach really be exploitable for direct­ ing the automatic control of mechanical equipment in real-time?

The questions that we have posed in this sec­ tion are among those that must be answered in order to develop useful and versatile robot systems. Experimenting with a facility such as we have de­ scribed appears to be the best way to elicit the proper questions and to work toward their answers,