Question

Assuming a house containing two rooms (Room_A, Room_B), each of which may or may not be dirty. A cleaning robot has been placed into Room_A. This robot has no sensors to detect if any dirt is in the room but knows in which room it is originally located. The following information is given:

Items to use for STATES and ACTION preconditions/effects:

IN(Room_A); IN(Room_B) ;IS_CLEAN(Room_A); IS_CLEAN(Room_B)

ACTIONS:

MOVE_RIGHT(Room_A) “in Room_A and move to Room_B"

MOVE_LEFT(Room_B) “in Room_B and move to Room_A"

VACUUM(Room_A) " in Room_A and vacuum room clean"

VACUUM(Room_B) '"n Room_B and vacuum room clean"

Initial State:

IN(Room_A)

Goal State:

IS_CLEAN(Room_A) ∧ IS_CLEAN(Room_B)

1- Using STRIPS:

a-) Specify the required preconditions and effects for each of the 4 actions

b-) Draw the connected hierarchy of actions (backward from the goal) that connects the goal state up to the start state using various actions. Show links from preconditions and effects necessary to satisfy the final plan. Address any issue of undoing or clobbering.

Answer 1

1. INTRODUCTION

This paper describes a new problem-solving program called STRIPS (STanford Research Institute Problem Solver). An initial version of the program has been implemented in LISP on a PDP-10 and is being used in conjunction with robot research at SRI. STRIPS is a member of the class of problem solvers that search a space of “world models” to find one in which a given goal is achieved. For any world model, we assume that there exists a set of applicable operators, each of which transforms the world model to some other world model. The task of the problem solver is to find some composition of operators that transforms a given initial world model into one that satisfies some stated goal condition.

This framework for problem solving has been central to much of the research in artificial intelligence . Our primary interest here is in the class of problems faced by a robot in re-arranging objects and in navigating, i.e., problems that require quite complex and general world models compared to those needed in the solution of puzzles and games. In puzzles and games, a simple matrix or list structure is usually adequate to represent a state of the problem. The world model for a robot problem solver, however, must include a large number of facts and relations dealing with the position of the robot and the positions and attributes of various objects, open spaces, and boundaries. In STRIPS, a world model is represented by a set of well-formed formulas (wffs) of the first-order predicate calculus.

Operators are the basic elements from which a solution is built. For robot problems, each operator corresponds to an action routine whose execution causes a robot to take certain actions. For example, we might have a routine that causes it to go through a doorway, a routine that causes it to push a box, and perhaps dozens of others.

Green implemented a problem-solving system that depended exclusively on formal theorem-proving methods to search for the appropriate sequence of operators. While Green's formulation represented a significant step in the development of problem-solvers, it suffered some serious disadvantages connected with the “frame problem” that prevented it from solving nontrivial problems.

In STRIPS, we surmount these difficulties by separating entirely the processes of theorem proving from those of searching through a space of world models. This separation allows us to employ separate strategies for these two activities and thereby improve the overall performance of the system. Theorem-proving methods are used only within a given world model to answer questions about it concerning which operators are applicable and whether or not goals have been satisfied. For searching through the space of world models, STRIPS uses a GPS-like means-end analysis strategy . This combination of means-ends analysis and formal theorem-proving methods allows objects (world models) much more complex and general than any of those used in GPS and provides more powerful search heuristics than those found in theorem-proving programs.

We proceed by describing the operation of STRIPS in terms of the conventions used to represent the search space for a problem and the search methods used to find a solution. We then discuss the details of implementation and present some examples.

2. THE OPERATION OF STRIPS

The Problem Space

The problem space for STRIPS is defined by the initial world model, the set of available operators and their effects on world models, and the goal statement.

As already mentioned, STRIPS represents a world model by a set of well-formed formulas (wffs). For example, to describe a world model in which the robot is at location LOC_A and boxes B and C are at locations LOC_B and LOC_C we would include the following wffs:

atr(LOC_A), at(B, LOC_B), at(C, LOC_C).

We might also include the wff:

(uxy){[at(u,x)  (x  y)]  at(u,y)}

to state the general rule that an object in one place is not in a different place. Using first-order predicate calculus wffs, we can represent quite complex world models and can use existing theorem-proving programs to answer questions about a model.

The available operators are grouped into families called schemata. Consider for example the operator goto for moving the robot from one point on the floor to another. Here there is really a distinct operator for each different pair of points, but it is convenient to group all of these into a family goto (m,n) parameterized by the initial position m and the final position n. We say that goto (m,n) is an operator schema whose members are obtained by substituting specific constants for the parameters m and n. In STRIPS, when an operator is applied to a world model, specific constants will already have been chosen for the operator parameters.

Each operator is defined by an operator description consisting of two main parts: a description of the effects of the operator, and the conditions under which the operator is applicable. The effects of an operator are simply defined by a list of wffs that must be added to the model and a list of wffs that are no longer true and therefore must be deleted. We shall discuss the process of calculating these effects in more detail later. It is convenient to state the applicability condition, or precondition, for an operator schema as a wff schema. To determine whether or not there is an instance of an operator schema applicable to a world model, we must be able to prove that there is an instance of the corresponding wff schema that logically follows from the model.

For example, consider the question of applying instances of the operator subschema goto (m, LOC_B) to a world model containing the wff atr(LOC_A), where LOC_A and LOC_B are constants. If the precondition wff schema of goto (m,n) is atr(m), then we find that the instance atr(LOC_A) can be proved from the world model. Thus, an applicable instance of goto(m, LOC_B) is goto(LOC_A, LOC_B).

It is important to distinguish between the parameters appearing in wff schemata and ordinary existentially and universally quantified variables that may also appear. Certain modifications must be made to theorem-proving programs to enable them to handle wff schemata; these are discussed later.

Goal statements are also represented by wffs. For example, the task Get Boxes B and C to Location LOC_A might be stated as the wff:

at(B, LOC_A)  at(C, LOC_A)

To summarize, the problem space for STRIPS is defined by three entities:

(1) An initial world model, which is a set of wffs describing the present state of the world.

(2) A set of operators, including a description of their effects and their precondition wff schemata.

(3) A goal condition stated as a wff.

The problem is solved when STRIPS produces a world model that satisfies the goal wff.

EXAMPLE PROBLEMS SOLVED BY STRIPS

STRIPS has been designed to be a general-purpose problem solver for robot tasks, and thus must be able to work with a variety of operators and with a world model containing a large number of facts and relations. This section describes its performance on three different tasks.

The initial world model for all three tasks consists of a corridor with four rooms and doorways .

Initially, the robot is in ROOM1 at location LOC_E. Also in ROOM1 are three boxes and a lightswitch: BOX1 at location LOC_A, BOX2 at location LOC_B, and BOX3 at location LOC_C; and a lightswitch, LIGHTSWITCH1 at location LOC_D. The lightswitch is high on a wall out of normal reach of the robot.

Formally, the initial world model is described by the list of axioms:

(xyz)[connects(x,y,z) => connects(x,z,y)],    inroom(BOX1,ROOM1),

connects(DOOR1,ROOM1,ROOM5),        inroom(BOX2,ROOM1),

connects(DOOR2,ROOM2,ROOM5),        inroom(BOX3,ROOM1),

connects(DOOR3,ROOM3,ROOM5),        inroom(ROBOT,ROOM1),

connects(DOOR4,ROOM4,ROOM5),        inroom(LIGHTSWITCH1,ROOM1),

locinroom(LOC_F,ROOM4),         pushable(BOX1), pushable(BOX2),

at(BOXl,LOC_A), at(BOX2,LOC_B), at(BOX3,LOC_C),        pushable(BOX3),

onfloor,

at(LIGHTSWITCH1,LOC_D),          status(LIGHTSWITCH1,OFF)

atrobot(LOC_E),              

type(BOX1,BOX), type(BOX2,BOX),

type(BOX3,BOX),            

type(D1,DOOR), type(D2,DOOR),            

type(D3,DOOR), type(D4,DOOR),            

type(LIGHTSW1TCH1,LIGHTSWITCH),    

At the input of STRIPS the finite set of operators is given.

For convenience we define two goto operators, goto1 and goto2. The operator goto1(m) takes the robot to any coordinate location m in the same room as the robot. The operator goto2(m) takes the robot next to any item m (e.g., lightswitch, door, or box) in the same room as the robot. The operator pushto(m,n) pushes any pushable object m next to any item n (e.g., lightswitch, door or box) in the same room as the robot. Additionally, we have operators for turning on lightswitches, going through doorways, and climbing on and off boxes.

The precise formulation of the preconditions and the effects of these operators:

goto1(m) – robot goes to coordinate location m

pre = (onfloor)  (x)[inroom(ROBOT,x)  locinroom(m,x)]

del = {atrobot($), nextto(ROBOT,$)}

add = {atrobot(m)}

goto2(m) – robot goes next to item m.

pre = (onfloor)  [(x)[inroom(ROBOT,x)  inroom(m,x)] 

(x)( y) [inroom(ROBOT,x)  connects(m,x,y)] ]

del = {atrobot($), nextto(ROBOT,$)}

add = {nextto(ROBOT,m)}

pushto(m,n) – robot pushes object m next to item n

pre = pushable(m)  onfloor  nextto(ROBOT,m) 

((x)[inroom(m,x)  inroom(n,x)]  (x,y)[inroom(m,x)  connects(n,x,y)] )

del = {atrobot($), nextto(ROBOT,$), nextto($,m), at(m$), nextto (m$)}

add = {nextto(m,n), nextto(n,m), nextto(ROBOT,m)}

turnonlight(m) – robot turns on lightswitch m.

pre = ((n)[type(n,BOX)  on(ROBOT,n)  nexto(n,m)])  type(m,LIGHTSWITCH)

del = {status(m,OFF)}

add = {status(m,ON)}

climbonbox(m) – robot climbs up on box m.

pre = onfloor  type(m,BOX)  nextto(ROBOT,m)

del = {atrobot($), onfloor}

add = {on(ROBOT,m)}

climboffbox(m) – robot climbs off box m.

pre = type(m,BOX)  on(ROBOT,m)

del = {on(ROBOT,m)}

add = {onfloor}

gothrudoor (k,l,m) – robot goes through door k from room l into room m.

pre = nextto(ROBOT,k)  connects(k,l,m)  inroom(ROBOT,l)  onfloor

del = {atrobot($), nextto(ROBOT,$), inroom(ROBOT,$)}

add = {inroom(ROBOT,m)}

The first robot task is to turn on the lightswitch. The robot can solve this problem by going to one of the three boxes, pushing it to the lightswitch, climbing on the box and turning on the lightswitch.

The second task is to push the three boxes in ROOM1 together. This task is a more realistic elaboration of the three-box problem used as an example in the last section.

The third task is for the robot to go to a designated location, LOC_F, in ROOM4.

The goal wffs for the three tasks and the solutions obtained by STRIPS are following:

1. Turn on the lightswitch

Goal = status(LIGHTSWITCH1,ON)

Plan = (goto2(BOX1),climbonbox(BOX1),climboffbox(BOX1),

                pushto(BOX1,LIGHTSWITCH1),climbonbox(BOX1),

turnonlight(LIGHTSWITCH1))

2. Push three boxes together

Goal = nextto(BOX1,BOX2)  nextto(BOX2,BOX3)

Plan= (goto2(BOX2), pushto(BOX2,BOX1), goto2(BOX3), pushto (BOX3,BOX2))

3. Go to a location in another room

Goal = atrobot(LOC_F)

Plan = (goto2(DOOR1), gothrudoor(DOOR1,ROOM1,ROOM5),

goto2(DOOR4), gothrudoor(DOOR4,ROOM5,ROOM4), goto1(LOC_F) )