Computational Intelligence

Online Slides

November 6, 2002

These are slides from Computational Intelligence, A Logical Approach, Oxford University Press, 1998. Copyright ©David Poole, Alan Mackworth, Randy Goebel and Oxford University Press, 1999-2002. You may prefer the pdf interface for which these slides were designed (you can read pdf files using the free acrobat reader).

Chapter 8, Lecture 1

Actions and Planning

Time passes as an agent acts and reasons.

Given a goal, it is useful for an agent to think about what it will do in the future to determine what it will do now.

Representing Time

Time can be modeled in a number of ways:
Discrete time Time can be modeled as jumping from one time point to another.
Continuous time You can model time as being dense.
Event-based time Time steps don't have to be uniform; you can consider the time steps between interesting events.
State space Instead of considering time explicitly, you can consider actions as mapping from one state to another.
You can model time in terms of points or intervals.

Time and Relations

When modeling relations, you distinguish two basic types:

The Delivery Robot World

Modeling the Delivery Robot World

Individuals: rooms, doors, keys, parcels, and the robot.
Relations: represent

Example Relations


Initial Situation


Static Facts


Derived Relations

at(Obj,Pos) <- sitting_at(Obj,Pos).
at(Obj,Pos) <- carrying(Ag,Obj) & at(Ag,Pos).
adjacent(P_1,P_2) <-
     between(Door,P_1,P_2) &

Chapter 8, Lecture 2

STRIPS Representation

STRIPS Representation: Idea

STRIPS Representation of an action

The STRIPS representation for an action consists of:
preconditions A list of atoms that need to be true for the action to occur
delete list A list of those primitive relations no longer true after the action
add list A list of the primitive relations made true by the action

STRIPS Representation of "pickup"

The action pickup(Ag , Obj) can be defined by:
preconditions [autonomous(Ag), Ag != Obj, at(Ag,Pos), sitting_at(Obj,Pos)]
delete list [sitting_at(Obj,Pos)]
add list [carrying(Ag,Obj)]

STRIPS Representation of "move"

The action move(Ag , Pos1,Pos2) can be defined by:
preconditions [autonomous(Ag), adjacent(Pos1,Pos2,S) , sitting_at(Ag,Pos1)]
delete list [sitting_at(Ag,Pos1)]
add list [sitting_at(Ag,Pos2)]

Example Transitions

=> move(rob,o109,storage) {
=> pickup(rob,parcel) {

Chapter 8, Lecture 3

Situation Calculus

Example Situations

Using the Situation Terms

Axiomatizing using the Situation Calculus

Initial Situation


Derived Relations

adjacent(P_1,P_2,S) <-
     between(Door,P_1,P_2) &

When are actions possible?

poss(A,S) is true if action A is possible in situation S.

poss(putdown(Ag,Obj),S) <-

poss(move(Ag,Pos_1,Pos_2),S) <-
     autonomous(Ag) &
     adjacent(Pos_1,Pos_2,S) &
     sitting_at(Ag,Pos_1,S) .

Axiomatizing Primitive Relations

Example: Unlocking the door makes the door unlocked:

unlocked(Door,do(unlock(Ag,Door),S)) <-

Frame Axiom: No actions lock the door:

unlocked(Door,do(A,S)) <-
     unlocked(Door,S) &

Example: axiomatizing carried

Picking up an object causes it to be carried:

carrying(Ag,Obj,do(pickup(Ag,Obj),S)) <-

Frame Axiom: The object is being carried if it was being carried before unless the action was to put down the object:

carrying(Ag,Obj,do(A,S)) <-
     carrying(Ag,Obj,S) &
     poss(A,S) &
     A != putdown(Ag,Obj).

Example: sitting_at

An object is sitting at a location if:

More General Frame Axioms

The only actions that undo sitting_at for object Obj is when Obj moves somewhere or when someone is picking up Obj.

sitting_at(Obj,Pos,do(A,S) ) <-
     poss(A,S) &
     sitting_at(Obj,Pos,S) &
     forall Pos_1 ~~ A != move(Obj,Pos,Pos_1) &
     forall Ag ~~ A != pickup(Ag,Obj) .

The last line is equivalent to:

      ~ exist Ag ~ A=pickup(Ag,Obj)

which can be implemented as

sitting_at(Obj,Pos,do(A,S) ) <-
     ··· & ··· & ··· &
      ~ is_pickup_action(A,Obj).

with the clause:

is_pickup_action(A,Obj) <-

which is equivalent to:


STRIPS and the Situation Calculus

holds(C,do(A,W) ) <-
     preconditions(A,P) &  The preconditions of
     holdsall(P,W) &  of A all hold in W.
     add_list(A,AL) & C is on the 
     member(C,AL) . addlist of A.
holds(C,do(A,W) ) <-
     preconditions(A,P) &  The preconditions of
     holdsall(P,W) &  of A all hold in W.
     delete_list(A,DL) & C isn't on the 
     notin(C,DL) & deletelist of A.
     holds(C,W). C held before A.

Chapter 8, Lecture 4


Given a plan is a sequence of actions that will achieve the goal.

Example Planning

If you want a plan to achieve Rob holding the key k1 and being at o103, you can issue the query

?carrying(rob,k1,S) & at(rob,o103,S).

This has an answer

Forward Planner

Planning as Resolution

Goal-directed searching

Chapter 8, Lecture 5

STRIPS Planner

STRIPS Planner Code

achieve_all(Gs, W1, W2) is true if W2 is the world resulting from achieving every element of the list Gs of goals from the world W1.

achieve_all(Goals,W_0,W_2) <-
     remove(G,Goals,Rem_Gs) &
     achieve(G,W_0,W_1) &
     achieve_all(Rem_Gs,W_1,W_2) .

achieve(G, W0, W1) is true if W1 is the resulting world after achieving goal G from the world W0.

achieve(G,W,W) <-
achieve(G,W_0,W_1) <-
     clause(G,B) &
achieve(G,W_0,do(Action,W_1)) <-
     achieves(Action,G) &
     preconditions(Action,Pre) &

Undoing Achieved Goals

Example: consider trying to achieve

Example: consider trying to achieve

Fixing the STRIPS Algorithm

Two ideas to make STRIPS sound:

Does protecting always work?

Chapter 8, Lecture 6


Regression as Path Finding

Weakest preconditions

wp(A,GL,WP) is true if WP is the weakest precondition that must occur immediately before action A so every element of goal list GL is true immediately after A.

For the STRIPS representation (with all predicates primitive):

Weakest Precondition Example

The weakest precondition for


to be true after move(rob,Pos,lab2) is that


is true immediately before the action.

A Regression Planner

% solve(GL , W) is true if every element of goal list GL is true
% in world W.

solve(GoalSet,init) <-
     holdsall(GoalSet,init) .
solve(GoalSet,do(Action,W) ) <-
     consistent(GoalSet) &
     choose_goal(Goal,GoalSet) &
     choose_action(Action,Goal) &
     wp(Action,GoalSet,NewGoalSet) &

Regression Search Space Example

©David Poole, Alan Mackworth, Randy Goebel and Oxford University Press, 1998-2002