Planning in a Hierarchy of Abstraction Spaces

I Introduction

General purpose problem solvers, such as STRIPS 1 · 2 t or GPS, 3 must do their work using general purpose search heuristics. Unfortunately, by using such heuristics, it is not possible to solve any reasonably complex set of problems in a reasonably complex domain. Regardless of how good such heuristics are at dire cting search, attempts to traverse a complex problem space can be caught in a combinatorial quagmire .

This paper presents an approach to augmenting the power of the heuristic search process. The essence of this approach is to utilize a means for discriminating between important informat ion and details in the prob­ lem space. By planning in a hierarchy of abstraction spaces in which successive leve ls of detai l a r e intro­ duced , significant increases in problem-solving power

have· been achieved.

Section II sketches the hierarchica l planning ap­ proach and gives motivation for its use. Sections III and IV describe the definition and use of abstraction spaces by ABSTRIPS (Abstraction-Based STRIPS), a modi­ fication of the STRIPS problem-s~lving~m that in­ corporates this approach. Section V describes the per­ formance of the system. Section VI discusses the impli­ cations of this approach for problem solving and for

robotics.

* The work reported herein was sponsored by the Advanced Research Projects Agency of the Department of Defense under Contract DAHC04-72-C- 0008 with the U.S. Army

Research Office.

t References are li sted at the end of this paper .

by

Earl D. Sacerdoti Stanford Research Institute Artificial Intelligence Center Menlo Park, California 94025

II The Motivation for Using Abstraction Spaces in Problem Solving

It was not quite fair to assert in the previous sec­ tion that a complex problem domain is beyond the combi­ natorial capability of general purpose problem solvers. A problem solver deals not with the problem domain it­ self, but with some representat ion of that domain . So it would be more correct to state that a complex repre­ sentation exceeds the scope of general purpose problem

solvers.

Unfortunately, a straightforward transcription of a complex problem domain will yield a complex r epr esen­ tation. However , a well-chosen transcription can l ead to a simpler representation. By choosing such a simpli­ fying representation, one c a n have the problem solver do its work in a context that is simple enough for some useful problem solving to take place .

In other words, the heuristic search through the simplifying representation will be of sufficiently short duration that a goa l state in the problem space can be reached. Such a representation displays what McCarthy and Hayes 4 term "heuristic adequacy . "

Attempts to achieve simplifying representations, such as the "macro operator," or MACROP, of the STRIPS problem solver, 2 have heretofore tried to preserve, in McCarthy and Hayes' terminology, "epistemological ade ­ quacy"; that is, the simplifying representat ions had to preserve all the detail that was needed to solve the problem at hand. A MACROP simplifies the representation of a problem domain by providing a means of selecting at one time an entire sequence of primitive operators, linked in a semantica lly sensible manner. But it pre­ serves every detail of the preconditions and effects of its constituent operators.

Such simplifying representations can provide only limited enhancement to the power of a problem-solving system because of a somewhat dismaying fact: For a suf­ ficiently complex problem domain, no epistemologically adequate representation can be heuristica lly adequate.

Epistemological adequacy implies that every rele­ v a nt detail is properly dealt with. But attention to detail is precisely what defeats heuristic adequacy. A good heuristic evaluation function will e nable a prob­ l em solver to r eject most of the possible paths in a situation space. But if all the details are attended to, the evaluation function must be applied at all the nodes at which the detai ls are affected. The combina­ torics of the expanding search space will enable the problem solver to solve only rather simple problems.

A superior approach to problem solving would be to search first through an abstract ion space, a simplifying representation of the problem space in which unimportant details are ignored. When a solution to the problem in the abstraction space is discovered, all that remains is to account for the details of the linkup between the steps of the solution. This can be regarded as a se­ quence of subproblems in the original problem space. If they can be solved, a solution to the overall prob­ lem will have been achieved. If they cannot be solved, more planning in the abstraction space is required to discover an alternative solution.

Polya 5 cites the importance of this approach for human problem solving. It has been used by computer programs to find proofs in symbolic logic 6 (ignoring the nature of the connectives and the ordering of sym­ bols as details) and to detect edges in scenes 7 (using a shrunken picture with less detail).

The concept can readily be extended to a hierarchy of spaces, each dealing with fewer details than the ground space below it and with more details than the 1bstraction space above it. By considering details only when a successful plan in a higher level space gives strong evidence of their importance, a heuristic search process will investigate a greatly reduced por­ tion of the search space.

The process of abstraction defined in Section III is genera l in that it is not domain-dependent. But it is highly structured and very dependent on the syntax of .the problem domain. It is a first step, providing no capability for a "representational shift" that would restate a difficult problem in terms that render its solution markedly easier. Rather, it employs a series of representational nudges that increase the power of the heuristic search process over a problem space.

III Automated Definition of Abstraction Spaces

The following sections describe the ABSTRIPS sys­ tem, a modification of the STRIPS problem solver. 1 ' 2 A brief description of the aspects of STRIPS that are relevant to the discussion to follow is presented be­ low.* The reader is encouraged to see Section II of Ref. 2 for a brief but thorough summary of the opera­ tion of STRIPS or Ref. l for a full description.

Briefly, the representation of a problem domain with which STRIPS deals consists of:

1. A World Model--The world model is a set of wffs in the predicate calculus, describing facts (e.g., CONNECTS(DOORl,ROOMl,ROOM2)) or laws (e.g. , VRx ,Ry ,Dx CONNECTS (Dx ,Rx ,Ry) <=> CONNECTS(Dx,Ry,Rx)) of the problem domain.

* In the interests of brevity and clarity, no further mention will be made of the MACROPs in the STRIPS sys­ tem. A MACROP is the result of generalizing a previ­ ously completed plan. Most of its valid subsequences of operators can be extracted for use in further plan­ ning. Each such subsequence could be treated by ABSTRIPS like a primitive operator.

1. A Set of Operator Descriptions--Each action in the problem domain is represented by an "operator" for changing one model into an­ other. An operator is defined by a precon­ dition wff, an add list, and a delete list. For an operator to be applicable in a given model, its precondition wff must be satisfied. The add and delete lists describe which wffs are changed when an application of the opera­ tor transforms the world model.

A problem is stated to STRIPS as a goal wff . STRIPS must develop a sequence of operator applications that wi ll lead to a world model in which the goal wff is true. A GPS-like means-ends analysis strategy 3 is employed to generate the operator sequence.

A "difference" between the initial model and the goal model is extracted. STRIPS determines which in­ stances of which operators would reduce the difference; the instance that most reduces the difference is se­ lected. If it is applicable in the initial state (i.e., its precondition wff is true in the initial world model), the operator is applied , and a new world model created. If the goal wff is true in the new model, STRIPS is done. If not, the difference between the new state and the goa l state is extracted, and the process continues.

If the operator instance that most reduced the difference is not applicable in the initial state (i.e., its precondition wff is not provable in the wor ld model), the precondition 1S set up as a subgoal wff, STRIPS will then try to develop a sequence of operator applications that will l ead to a wor ld model in which the subgoal wff is true. If the subgoal is achieved, the operator instance can be applied as before. If not, another operator instance is selected, and the process continues as before.

Abstraction Spaces in the STRIPS Context

For a practical problem-solving system, one wou ld like to have an abstraction space differ from its ground space enough to achieve a significant improve­ ment in problem-solving efficiency, but yet not so much as to make the mapping from abstraction space to ground space complex a nd time-consuming.

For the STRIPS system, this criterion is met by having the abstract ion spaces differ from their ground spaces only in the level of detail used to specify the preconditions of operators. Although the change in representation provided by this choice may seem intui­ tively insufficient, it satisfies the criterion we ll. The world model can remain unchanged; there is no need to delete unimportant details from it because they can simply be ignored. No operators need be deleted in their entirety; if all they do is achieve details, they will never be selected as relevant. Any change to the add or delete lists of the operators would cause the operators ' effects to be very different in different spaces. Since the applicability of a particular oper­ ator at some intermediate state might depend on any effects of any previously applied operators, the map­ ping of plans among spaces wou ld be rendered too com­ plex.

Thus, an abstraction space in the STRIPS context differs from its ground space only in the preconditions of its operators. The precondition wffs in an abstrac­ tion space will have fewer literals than those in its ground space. The literals omitted will be those that are "details" in the sense that a simple plan can be found to achieve them once the more "critical" literals have been achieved. For instance, consider a PUSHTHRUDR operator, which describes the effects of a robot push­ ing a particular object through a doorway into an adja­ cent room. In a high level abstraction space, the op­ erator would be applicable whenever the object was pushable and a doorway into the desired room existed . In a lower level space, it would also be required that the robot and the object be in the room connected by the doorway with the target room. In a still lower abstraction space, the door would also have to be open. Finally, in the original representation of the problem space, the robot would also have to be next to the box, and the box would have to be next to the door.

For ABSTRIPS to be able to discriminate among var­ ious levels of detail, each literal within the precon­ ditions of each operator in a problem domain is assigned a "criticality" value at the time the domain is first defined. Only the most critical literals will be in the highest abstraction space, whereas in lower spaces less critical ones will also appear.

Assigning Criticality to the Literals of a Precondition

There are many possible approaches to the assign­ ment of criticality values to the literals of an oper­ ator's precondition wff. They span a range from a manual assignment as part of the specification of the problem domain to a completely automatic assignment of cri ticali ties .

At one extreme, the definition of a problem domain could include an explicit specification of criticali­ ties, reflecting the definer's intuition about the do­ main. For example, if one were to define a "Turn on the lamp(Z)" operator, he might say it was essential that £ be a lamp. He might say it was very important to be in the room with the lamp, less important that the lamp's cord be plugged in, and still less important to be next to the lamp. Specifying the criticality value of a literal by a number preceding it in braces, one might define the precondition wff of the "Turn on the lamp" operator as

• {4}Type(£, lamp) 1\ :;rrx({3}Inroom(Me ,rx) 1\
• {3}Inroom(£,rx)) 1\ {2}Plugged-in(£) 1\

At the other extreme, a scheme can be developed to perform an exhaustive analysis of the n! possible order­ ings of the n literals in a precondition in order to determine which literals can be achieved once other literals are assumed to be true. The results of this analysis can be used to specify the criticality values for literals of the precondition.

For ABSTRIPS, an intermediate approach to critical­ ity assignment was adopted. A predetermined (partial) ordering of all the predicates used in describing the problem domain was used to specify an order for examin­ ing the literals of the precondition wffs . of all the operators in the domain. First, all literals whose truth value could not be changed by any operator in the domain were assigned a maximum criticality value. Then, each remaining literal was examined in an order deter­ mined by the partial ordering. If a short plan could be found to achieve a literal from a state in which all previously processed literals were assumed to be true, then the literal in question was said to be a detail and was assigned a criticality equal to its rank .in the par­ tial ordering. If no such plan could be found, the lit­ eral was assigneg a criticality greater than the highest rank in the partial order.

For the domain including the "Turn on the lamp(£) " operator, the partial ordering might look like the fol­ lowing:

"' /

The Type(£ ,Lamp) literal could not be changed by any operator in the domain, and so it would be assigned a maximum criticality (6, in this case). The two Inroom literals would be examined next (an arbitrary order can be chosen for literals whose predicates have equal rank in the partial ordering) . They cannot be achieved from a state in which Type(£ ,Lamp) is asserted, and so they would be assigned a criticality greater than the highest rank in the partial order, in this case 5. P!ugged-in (£ ) can be achieved from a state in which the Inroom literals and the Type literal are true. It can be achieved by a plan to go to the lamp cord, pick it up, bring it to a socket, and plug it in. So it would be assigned a criticality equal to its rank in the partial ordering, namely, 2 . Similarly, a plan can be found to achieve Nextto(Me,£) from a state in which the previously processed literals are true, and so it would be assigned a criticality of l .

Regardless of the method used to determine the criticality values, they define a hierarchy of abstrac­ tion spaces. The next section shows how such a hier­ archy can be used to aid the planning process.

IV Utilization of Abstraction Spaces in Planning

To take advantage of the hierarchical planning ap­ proach offered by the use of abstraction spaces, the ABSTRIPS system--whose flow of control is shown in Fig­ ure 1--has a recursive executive program. This program accepts two parameters. The first is a criticality value indicating the abstraction space in which planning is to occur. The second is a list of nodes from the search tree in the higher space, representing a skeleton plan. When a new problem is posed to ABSTRIPS, the external interface program sets the preconditions of a dummy operator to the goal wff , The domain's maximum criticality, which was determined when criticalities were assigned, is retrieved. The executive is called with the criticality set to the maximum and the skele­ ton consisting of the dummy operator.

Within the highest abstraction space, the execu­ tive plans to achieve the preconditions of the dummy step in the skeleton plan, i.e., the main goal. When a plan is found, the executive computes the criticality of the next lowest space in which planning is needed, and it builds a skeleton of nodes along the path of the successful plan. The executive then invokes itself re­ cursively. The new invocation solves in turn the sub­ problems of bridging the gaps between steps in the skeleton plan and of ensuring that the steps in the skeleton plan are still applicable at the appropriate points in the new plan. The final step in the skeleton is a lways the dummy operator, and so the final applica­ bility check ensures that the original goal has been reached. When all subproblems have been solved, the executive invokes itself for planning in a still lower space. This recursion continues until a complete plan is built up in the problem space itself.

This search strategy might be termed a "length­ first" search. It pushes the planning process in each abstraction space all the way to the original goal state before beginning to plan in a lower space. This enables the system to recognize as early as possible the steps that would lead to dead ends or very inefficient plans.

If any subproblem in a particular space cannot be solved, control is returned to the process in its ab­ straction space. The search tree is restored to its state prior to the selection of the node that led to failure in the ground space. That node is eliminated from consideration, and the search for a successful plan at the higher level continues.

This failure mechanism is analogous to the auto­ matic backtracking feature of the PLANNER language. 8 It has the major defect that when a failure of a lower level process is reported, the process and the context in which the failure occurred are no longer around for analysis. So ABSTRIPS relies heavily on being able to produce good plans at the highest level.

This requirement has led to two modifications to the search a l gorithm originally employed by STRIPS. The first is an a lteration of the evaluation function used to select which node in the search tree to expand next. STRIPS emphasizes the estimated cost of achiev­ ing the goal from the given node and deemphasizes the cost of arriving at the node from the initial state. Thus, it has a tendency to find a slightly longer plan quickly, rather than the cheapest plan more slowly. But each extra step in a high abstraction space is likely to lead to many extra steps in the corresponding plan in the problem space. Thus, for ABSTRIPS, the evaluation function has itself been made a function of the level of abstraction. At the highest leve l, AB­ STRIPS gives equal weight to the cost of reaching a given node and to the estimated cost of reaching the goal from that node. This evaluation function changes incrementally as the level of abstraction decreases, until it reaches the old STRIPS function at the level of the problem space.

The second modification involves postponing the selection of one among several equivalent instances of a relevant operator. During the process of selecting relevant operators to reduce a particular difference, a partial instantiation of the operators' parameters may occur. For example, if the difference were that the robot was not in Room 3, then the operator "Go through a door into a room" might be selected and in­ stantiated to "Go through a door into Room 3 ." The pre­ conditions of this operator would then be analyzed by the theorem prover to determine which door to choose. If several choices seem equally good to STRIPS (i.e., the states in which the various choices can be applied are equally difficult to reach), then it would arbitrar­ ily pick a door.

For ABSTRIPS, alternative instantiations in an ab­ straction space might appear equivalent, and yet one choice might be substantially superior when further de­ tails are considered. So ABSTRIPS defers its decision when more than one equivalent "best choice" of a rele­ vant oper ator is found. The partially instantiated relevant operator (e.g., "Go through a door into Room 3") is used in planning. When subsequent analysis in a lower abstraction space reveals a preferred instantia­ tion, that instantiation is then chosen. If this selec­ tion should eventually lead to failure, the other in­ stantiations can still be chosen through the backtrack­ ing mechanism.

In summary, hierarchical planning using abstraction spaces in a "length-first" search technique postpones extending the search tree through the levels concerned with the detailed preconditions of an operator until it knows that doing so will be highly effectual in reaching the goal (because the operator lies along an a lmost cer­ tainly successful path). By avoiding work on fruitless branches of the search tree, the technique achieves sig­ nificant efficiencies in the formulation of complex plans.

V Examples of ABSTRIPS' Performance

To clarify the issues raised and the way in which the ABSTRIPS system works, the system's performance is traced through some examples below. The ABSTRIPS sys­ tem consists of some 370 BBN-LISP functions, which run as compiled code on a PDP-10 computer. All the examples presented were drawn from the environment of the Stan­ ford Research Institute mobile robot. The domain con­ sists of seven rooms interconnected by doorways. Oper­ ators have been defined that model the robot's ability to navigate to any object or location within a room, to push boxes within a room or through a doorway, to navi­ gate through a doorway, to block a doorway using a box, and to unblock a doorway. In addition, fictitious oper­ ators have been defined to model the opening and closing of doors; these actions are beyond the robot's capabili­ ties. In all, 167 predicate calculus wffs have been de­ fined as axioms to model the robot domain.

The definition of the domain is essentially iden­ tical to the one used for the exampl es in the latest report on the STRIPS system. 2

Definition of Abstraction Spaces

To enable the system to assign critica lity values properly to the literals of the preconditions of the operators, two additional axioms, representing laws about the world, were included in the world model:

Vx . PUSHABLE(x) ~ TYPE(x,OBJECT)

and Vx. STATUS(x,CLOSED) = -.STATUS(x,OPEN)

The criticality determination algorithm r equired approximately five minutes of running time. The result­ ing operator descriptions are listed below. The number in braces preceding each literal in the precondition wffs represents the criticality of the literal. The literal will appear in the precondition in abstraction spaces of criticality less than or equal to the number in braces .

GOTOB(bx) Go to object bx.

Preconditions:

(6 }TYPE(bx ,OBJECT),

(Erx)[(5}INROOM(bx,rx) 1\

(5} INROOM(ROBOT,rx)J

Deletions: At(ROBOT,$1,$2),NEXTTO(ROBOT,$1)

Additions: *NEXTTO(ROBOT,bx)

GOTOD(dx) Go to door dx.

Preconditions:

(6 }TYPE (dx ,DOOR), (Erx) (Ery)

[(5}INROOM(ROBOT,rx) 1\

(6}CONNECTS(dx,rx,ry)]

Delet i ons : At(ROBOT,$1,$2),NEXTTO(ROBOT,$1)

Additions: *NEXTTO(ROBOT,dx)

GOTOL(x,y) Go to coordinate location (x,y)

Preconditions: (Erx)[{5}rNROOM(ROBOT,rx) 1\

(6}LOCINROOM(x,y,rx)]

Deletions: At(ROBOT,$1,$2),NEXTTO(ROBOT,$1)

Additions: *At(ROBOT,x,y)

PUSHB(bx,by) Push bx to object by

Preconditions:

(6 lTYPE(by ,OBJECT), (6}PUSHABLE(bx),

(l}NEXTTO(ROBOT,bx),

(Erx)[(5}INROOM(bx,rx) 1\

(5}INROOM(by, rx) 1\ (5}rNROOM(ROBOT ,rx)]

Deletions: At(ROBOT,$1,$2),NEXTTO(ROBOT,$1),

At(bx,$1,$2),NEXTTO(bx,$l),NEXTTO($l,bx)

Additions: *NEXTTO(by,bx),*NEXTTO(bx,by),

NEXTTO(ROBOT,bx)

PUSHD(bx,dx) Push bx to door dx

Preconditions :

(6 }PUSHABLE(bx),(6}TYPE(dx,Door),

( l}NEXTTO(ROBOT,bx),

(Erx) (Ery) [(5}INROOM(ROBOT, rx) 1\

(5}INROOM(bx,rx) 1\ (6}CONNECTS(dx,rx,ry)]

Deletions: At(ROBOT,$1,$2),NEXTTO(ROBOT,$1),

At(bx,$1,$2),NEXTTO(bx,$l),NEXTTO($l,bx)

Additions: *NEXTTO(bx,dx),NEXTTO(ROBOT,bx)

PUSHL(bx,x,y): Push bx to coordinate location (x,y) Preconditions: (6 }PUSHABLE(bx), (1 }NEXTTO(ROBOT, bx), (Erx) [ (5 }INROOM(ROBOT ,rx) 1\

( 5}rNROOM(bx, rx) 1\ (6}LOCINROOM(x, y, rx))

Deletions: At(ROBOT,$1,$2),NEXTTO(ROBOT,$1)

At(bx,$1,$2),NEXTTO(bx,$l),NEXTTO($l,bx)

Additions: *At(bx,x,y),NEXTTO(ROBOT,bx)

GOTHRUDR(dx,rx): Go through door dx into room rx

Preconditions :

(6}TYPE(dx,DOOR),(6}TYPE(rx,ROOM),

{2}STATUS(dx,OPEN),

(Ery)[ (5} INROOM(ROBOT,ry) 1\

(6}CONNECTS(dx,ry,rx) J

Deletions: At(ROBOT,$1 ,$2 ),NEXTTO(ROBOT,$1),

INROOM(ROBOT,$1)

Additions: *INROOM(ROBOT,rx)

PUSHTHRUDR(bx ,dx,rx): Push bx through door dx into room rx

Preconditions:

(6}PUSHABLE(bx),(6}TYPE(dx,DOOR),

(6}TYPE(rx,ROOM),(2}STATUS(dx,OPEN),

( l }NEXTTO(bx,dx),(l}NEXTTO(ROBOT,bx),

(Ery)[(5}INROOM(bx,ry) 1\

(5}rNROOM(ROBOT, ry) 1\

(6}CONNECTS(dx,ry,rx)J

Deletions: At(ROBOT,$1,$2),NEXTTO(ROBOT,$1),

At(bx,$1,$2),NEXTTO(bx,$l),NEXTTO($l,bx),

INROOM(ROBOT ,$ l),INROOM(bx,$1)

Additions: *INROOM(bx,rx),INROOM(ROBOT,rx),

NEXTTO(ROBOT,bx)

OPEN(dx): Open door dx

Preconditions:

(6}TYPE(dx,DOOR),{5}STATUS(dx ,CLOSED),

(5}NEXTTO(ROBOT,dx)

Deletions: STATUS(dx,CLOSED)

Additions: *STATUS(dx,OPEN)

CLOSE(dx): Close door dx

Preconditions:

(6}TYPE(dx,DOOR), (5}STATUS(dx,OPEN),

(5}NEXTTO(ROBOT,dx)

Deletions: STATUS(dx,OPEN)

Additions: *STATUS(dx,CLOSED)

A Detailed Sample Problem

Figure 2 depicts the initial model that was defined for this problem. The robot is in Room RRIL. The door between RRIL and RCLK is closed. BOXl and BOX2 are both in RPDP. The problem is for the system to plan to achieve a state in which the two boxes are next to one another and the robot is 1n Room RUN!, as in Figure 3. The goal wff for this problem is: NEXTTO(BOXl,BOX2) 1\ INROOM(ROBOT,RUNI).

STRIPS was able to solve this problem without using abstraction spaces . However, its solution required the exploration of 119 nodes in the search tree, only 23 of which were on the successful path. This exploration took over 30 minutes of computer time. Figure 4(a) de­ picts the search tree.

* The addition clauses preceded by an asterisk are the primary additions of the operator. When STRIPS or ABSTRIPS searches for a relevant operator, it consid­ ers only primary addition clauses.

ABSTRIPS first examined the problem in an abstrac­ tion space in which the only precondition clauses con­ sidered were those whose truth value could never be altered by the robot. The difference between the ini­ tial state and the goal state was computed . The differ­ ence was the goa l wff itself . Five relevant operator instances were computed. The first of these, PUSHB (BOX2,BOX1), was examined. Its precondition wff in this abstraction space was true in the initial state; so the operator was applied. This resulted in a new state in which the robot, BOX!, and BOX2 were next to each other. The difference between this state and the goal state was computed and found to be INROOM{ROBOT, RUN!). Two relevant operator instances were found, and the first, GOTHRUDR{Parl2,RUNI), was examined. {Parl2 is an uninstantiated parameter.) Its precondition wff in this abstraction space, TYPE{RUNI,ROOM) A TYPE (Parl2,DOOR) 11 {Ery)CONNECTS(Parl2,ry,RUNI), was satis­ fied when Parl2 was instantiated to DUNIMYS. So GUTHRUDR{DUNIMYS,RUNI) was applied, and this generated a state in which the goal wff was true. Figure 4{b) depicts the search tree in the highest abstraction space. The positioning of the nodes suggests the cor­ respondence to the nodes in the STRIPS search tree.

A skeleton plan was built consisting of the nodes at which the two operators were applied. The plan was:

PUSHB{BOX2,BOX1); GOTHRUDR{DUNIMYS,RUNI)

Planning then began in the space of criticality 5,

The first subgoal was the precondition wff in this abstraction space of the first operator, PUSHB{BOXl, BOX2). The difference between the initial state and the one in which the wff was true was INROOM{ROBOT, RPDP). Operator instances relevant to reducing this difference were GOTHRUDR{Parl7,RPDP) and PUSHTHRUDR {ROBOT,Par20,RPDP). The precondition wff of the first was tested, but it was not completely satisfied, There were still differences INROOM{ROBOT,RMYS) or INROOM (ROBOT,RCLK) before GOTHRUDR(Parl7,RPDP) could be ap­ plied {i.e., the robot was not yet in a room adjoining RPDP). The PUSHTHRUDR operator was completely inappli­ cable because the robot is not a pushable object.

Then ABSTRIPS tried to reduce the differences that would render GOTHRUDR(Parl7,RPDP) applicable. Four relevant operators were found. The first was GOTHRUDR (Par22 ,RMYS), and its precondition wff was not satisfied either {the robot was not in a room adjoining RMYS). The second relevant operator was GOTHRUDR{Par22,RCLK), and its precondition wff ·was satisfied when Par22 was instantiated to DCLKRIL. So GOTHRUDR(DCLKRIL,RCLK) was applied, producing a state in which GOTHRUDR{DPDPCLK, RPDP) was applicable. That operator was applied, pro­ ducing a state in which the initial subgoal, the pre­ condition wff of PUSHB(BOX2,BOX1), was true. The PUSHB operator was then applied.

Then a new subgoal was set up , in which the precon­ ditions of GOTHRUDR{DUNIMYS,RUNI) in this space were true. The difference between the current state and the subgoal state was INROOM(ROBOT,RMYS). GOTHRUDR{Par27, RMYS) was selected as a relevant operator, and its pre­ conditions were satisfied when Par27 was bound to DMYSPDP, So GOTHRUDR{DMYSPDP,RMYS) was applied, pro­ ducing a state in which the subgoal was satisfied. The operator associated with this subgoal, GOTHRUDR{DUNIMYS, RUNI),was applied, and the goal state was again reached. Figure 4(c) shows the search trees in this space.

The following new skeleton plan was built up: GOTHRUDR(DCLKRIL,RCLK); GOTHRUDR{DPDPCLK,RPDP); PUSHB {BOX2,BOX1); GOTHRUDR(DMYSPDP,RMYS);GOTHRUDR(DUNIMYS, RUN!). The planning process was then reinvoked in an abstraction space of criticality 2.

The first subgoal, the precondition wff of the first step in the skeleton plan, GOTHRUDR(DCLKRIL,RCLK), was not satisfied in the initial model. The difference was STATUS(DCLKRIL,OPEN). An analysis showed that it could be eliminated by applying GOTOD(DCLKRIL) and then OPEN {DCLKRIL). This resulted in a state that satisfied the first subgoal. So GOTHRUDR(DCLKRIL,RCLK) was applied.

Each of the remaining subgoals of the process in this abstraction space were immediately satisfiable, and so each step of the skeleton plan was applied in turn, resulting in a state in which the original goal was satisfied. The skeleton plan produced was GOTOD (DCLKRIL); OPEN(DCLKRIL), followed by all the steps of the previous skeleton plan. Figure 4(d) shows the search trees in this space.

Finally, planning took place in the ground space, the space including literals of criticality 1. The first three steps of the skeleton plan were applied in turn. But the preconditions of GOTHRUDR(DPDPCLK,RPDP) were not satisfiable in a state in which the robot had just come through DCLKRIL. The difference was NEXTTO (ROBOT,DPDPCLK), and analysis indicated that it could be eliminated by applying GOTOD(DPDPCLK), enabling GOTHRUDR(DPDPCLK,RPDP) to be applied.

The next subgoal, the preconditions of PUSHB(BOX2, BOXl), was not satisfied at this point. The difference was NEXTTO(ROBOT,BOX2), which could be eliminated by an application of the first relevant operator selected, GOTOB(BOX2). After PUSHB(BOX2,BOX1) was applied, ~he next two subgoals failed because the robot was not next to the appropriate door. An analysis similar to the one that occurred with DPDPCLK was performed, enabling ABSTRIPS to finish the plan with an operator to go to and an operator to go through DMYSPDP and DUNIMYS.

Note that the planning in this space is just as if STRIPS were given seven small problems to solve consec­ utively, without the benefit of MACROPS . The search trees for the ground space are shown in Figure 4(e). The entire planning process for ABSTRIPS produced 60 nodes, 54 of which were on the successful path in one space or another. This process required 5:28 of com­ puter time. This is less than one-fifth of the time required by the nonhierarchical STRIPS.

Other Examples

The set of tasks from the most recent report on STRIPS 2 was run on ABSTRIPS. The running times and the search trees are compared with those from the STRIPS system in Table 1. Figure 5 plots the planning time as a function of plan length for STRIPS and ABSTRIPS on an extended set of problems from the robot domain.

Tab l e l

COMPARISON OF PLANNING TIMES AND SEARCH TREES

VI Further Imp l ications of the Use of Abstraction Spaces in Planning

This paper has shown how the represen.tation of a problem domain as a hierarchy of abstraction spaces dramatically improved the performance of a problem solver. This section brief l y considers the implication of such a hierarchical representation for some other problem areas in robotics and prob l em solving .

Learning Task-Specific Knowl edge

General-purpose problem solvers have tended to be weak problem solvers. Because the heuristics they use to guide the search through the prob l em space must be genera l ly applicable , they are not especially powerful in any particular task domain, On the other hand, spe­ cial purpose programs to solve probl ems in a particul ar domain have been notably successful . The HEURISTIC DEN DRAL program 9 and the game playing programs display far more probl em- sol ving power in their particu l ar domains of competence than a general purpose probl em solver coul d muster . This competence is derived to a large degree from the great amount of task- specific knowledge that has been incorporated into their search heuristics

Unfortunate l y, whi l e these special purpose program~ display intelligent behavior within their l imited domair they are worth l ittle i n any other domain . Can a more genera lly intelligent system be constructed that, when presented with task-specific knowl edge (basic to which is the description of the problem domain), can incor­ porate that knowledge into its search heuristics?

The process of automated definition of abstraction space offers a possible approach . By applying a general purpose problem solver to a particular domain in the most genera l manner described in Section III, a task­ specific detail h ierarchy can be built up. The ability of a system to discriminate important considerations from mere details is an important aspect of task­ specific knowledge.

A further aspect of task-specific knowledge is the facility for negotiating those areas of the search space that are easi ly traversible. In the hierarchical representation framework, easily traversible areas cor­ respond to subproblems of achieving details, once the more critical aspects of a problem have been solved.

a mobile robot. In the Stanford Research Institute robot system, the operator descriptions are models for actions that the robot can actually take . The actions modeled are termed "intermediate level actions" (!LAs). When they are executed, they invoke "low level actions" (LLAs), which are concerned with initiating and monitor ­ ing motion of the robot. These routines in turn pass commands to, and receive information from, a program in a PDP-15 computer, which communicates with the robot itself via a radio link.

The ground space as viewed by ABSTRIPS is in fact just another abstrac tion space from the point of view of plans built up from basic operations at lower l evels. The problem solver can be extended to handle success­ ively finer l evels of detail until a ground space is reached in which the only remaining details are to roll the robot around. This offers the enticing possibility of a fully integrated planning and execution system.

The ABSTRIPS system determines that a given literal But the interaction of planning and execution would r el em solvers.

is a detail when it has built a small plan to achieve a quire that the plans that such a system built be difstate in which it is true. That small plan can be saved fered from the traditional form of plan built by probas a MACROP, to be used as the first-choice relevent operator whenever the detail needs to be achieved. The r e lati vely small number of MACROPs formed in this way, when added to the set of basic operators, constitute a basic body of knowledge about how to solve problems in a particular task domain.

Planning with Multiple Outcome Operators

The use of a hierarchical representation can greatly simplify the process of creating conditional plans, plans with information gathering operators, and plans with loops. This is because the outcomes of these operators are uncertain only to a particular leve l of detail. Thus, in a higher abstraction space a simple specification can adequately model the preconditions and effects of the operators, although some of the ef­ fects may have to be described in terms of uninstanti­ ated parameters. A drawback to this approach is that, as noted in Section III, the mapping of plans among spaces becomes difficult when the effects of operators are abstracted. Nevertheless, the simplicity of repre­ sentation of these rather complex operators renders

this scheme attractive.

As an example, in planning to drive to the airport to catch a plane, one would use a "Park the car" opera­ tor. Such ·an operator might have the effect of "If Lot A is not full, park inside Lot A. Else if Lot B is not full, park inside Lot B. Else drive around, and then park the car." If one plans at a high level of abstrac­ tion to drive to the airport, he does not consider the "Park the c·ar" operator in its full complexity . Rather, he considers an image of the operator in an abstraction space in which no uncertainties exist. It might have the simple precondition At(Car,Airport) and might cause the clause Parked-in-lot (Car,Parameter37) to be added to the model. Further planning could continue without considering as separate cases states in which Parked-in­ lot(Car,Lot A) or Parked-in-lot(Car,Lot B) were true.

An Integrated Robot System

A primary motivation for building the STRIPS sys­ tem, and its offspring ABSTRIPS, was to build plans for For a system that deals with complex problems in a real world, as opposed to a simulated one, it is un­ desirable to solve an entire problem with an epistemo­ logically adequate plan. There are too many reasonably like ly outcomes for each real-world operation. The num­ ber of hypothetically possible states of the wor ld at­ tainable by a particular plan will grow exponent ially with the length of the plan. Most of the effort of such a system would be spent re~soning about wor ld states that would never be achieved, and very little of it would be spent moving the robot toward its goals.

It is desired that the system's planning efforts focus on reasoning about states of the world that are likely to be traversed in the course of robot execution. Thus, the overall planning should be roughed out in an abstraction space that ignores enough levels of detail so that the rough plan is fairly certain to succeed.

A few ste~s of the plan can be used as a skeleton, to which more detailed steps are added in a manner sim­ ilar to ABSTRIPS. These new steps are fairly certain to succeed at the l evel of detail to which they are specified. Even more detailed steps can be filled in for the beginning portion of this subplan, and the process can continue until a short subplan of l ow-level robot commands is built. These can be executed in se­ quence . Any deviations between the actual state of the world and the hypothesized results of the subplan wil l hopefully be mere details to the space that is an ab­ straction of the robot commands. Thus, the remaining steps of the plan in this space, as well as all higher spaces, are still on the solution path.

Further building and extending of the various sub­ plans can then take place, including a new bottom-level subplan to move the robot. This subplan will accurately reflect the precise results of previous execution, and so it will be fully appropri a te for achieving the ulti­ mate goal . The process of alternatively adding detailed steps to the plan and then actually executing some steps can continue until the goa l is achieved.

If a grievous failure occurs at some point in exe­ cution and nondetails in higher models no longer reflect the actual state of the world, subplans at affected levels of detail can propagate the failure up to an abstraction space in which the deviation from the pre­ dicted world model was a detail. Replanning can be initiated from this level of abstraction, thus reusing the results of as much as possible of the previous planning .

Therefore, by using a hierarchy of abstraction spaces to mask uncertainties in the real world effects of planned operations, an effectively integrated robot planning and executing system can be created. By deal­ ing with a hierarchy of short, simple plans, such a system will be able to cope effectively with truly com­ plex problems .

Acknowledgements

The author is indebted to Richard Fikes, Peter Hart, and Nils Nilsson for their enthusiastic encour­ agement and intellectual support. The research re­ ported in this paper was supported by the Advanced Research Projects Agency of the Department of Defense under Contract DAHC04-72-C-0008 with the U.S. Army Re ­ search Office.