# 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

• Agents reason in time
• Agents reason about time
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:
• Static relations are those relations whose value does not depend on time.
• Dynamic relations are relations whose truth values depends on time. Either
• derived relations whose definition can be derived from other relations for each time,
• primitive relations whose truth value can be determined by considering previous times.

## Modeling the Delivery Robot World

Individuals: rooms, doors, keys, parcels, and the robot.
Actions:
• move from room to room
• pick up and put down keys and packages
• unlock doors (with the appropriate keys)
Relations: represent
• the robot's position
• the position of packages and keys and locked doors
• what the robot is holding

## Example Relations

• at(Obj,Loc) is true in a situation if object Obj is at location Loc in the situation.
• carrying(Ag,Obj) is true in a situation if agent Ag is carrying Obj in that situation.
• sitting_at(Obj,Loc) is true in a situation if object Obj is sitting on the ground (not being carried) at location Loc in the situation.
• unlocked(Door) is true in a situation if door Door is unlocked in the situation.
• autonomous(Ag) is true if agent Ag can move autonomously. This is static.
• opens(Key,Door) is true if key Key opens door Door. This is static.
• adjacent(Pos1,Pos2) is true if position Pos1 is adjacent to position Pos2 so that the robot can move from Pos1 to Pos2 in one step.
• between(Door,Pos1,Pos2) is true if Door is between position Pos1 and position Pos2. If the door is unlocked, the two positions are adjacent.

## Actions

• move(Ag,From,To): agent Ag moves from location From to adjacent location To. The agent must be sitting at location From.
• pickup(Ag,Obj) agent Ag picks up Obj. The agent must be at the location that Obj is sitting.
• putdown(Ag,Obj) the agent Ag puts down Obj. It must be holding Obj.
• unlock(Ag,Door) agent Ag unlocks Door. It must be outside the door and carrying the key to the door.

## Initial Situation

sitting_at(rob,o109).
sitting_at(parcel,storage).
sitting_at(k1,mail).

## Static Facts

between(door1,o103,lab2).
opens(k1,door1).
autonomous(rob).

## Derived Relations

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

# Chapter 8, Lecture 2

## STRIPS Representation

• State-based view of time.
• The actions are external to the logic.
• Given a state and an action, the STRIPS representation is used to determine
• whether the action can be carried out in the state
• what is true in the resulting state

## STRIPS Representation: Idea

• Predicates are primitive or derived.
• Use normal rules for derived predicates.
• The STRIPS representation is used to determine the truth values of primitive predicates based on the previous state and the action.
• Based on the idea that most predicates are unaffected by a single action.
• STRIPS assumption: Primitive relations not mentioned in the description of the action stay unchanged.

## 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)]

## 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)]

Example Transitions

{
 sitting_at(rob,o109). sitting_at(parcel,storage). sitting_at(k1,mail).
}
=> move(rob,o109,storage) {
 sitting_at(rob,storage). sitting_at(parcel,storage). sitting_at(k1,mail).
}
=> pickup(rob,parcel) {
 sitting_at(rob,storage). carrying(rob,parcel). sitting_at(k1,mail).
}

# Chapter 8, Lecture 3

## Situation Calculus

• State-based representation where the states are denoted by terms.
• A situation is a term that denotes a state.
• There are two ways to refer to states:
• init denotes the initial state
• do(A,S) denotes the state resulting from doing action A in state S, if it is possible to do A in S.
• A situation also encodes how to get to the state it denotes.

## Example Situations

• init
• do(move(rob,o109,o103), init)
•  do(move(rob,o103,mail), do(move(rob,o109,o103), init)).
•  do(pickup(rob,k1), do(move(rob,o103,mail), do(move(rob,o109,o103), init))).

## Using the Situation Terms

• Add an extra term to each dynamic predicate indicating the situation.
• Example Atoms:
at(rob,o109,init)
at(rob,o103,do(move(rob,o109,o103), init))
at(k1,mail,do(move(rob,o109,o103), init))

## Axiomatizing using the Situation Calculus

• You specify what is true in the initial state using axioms with init as the situation parameter.
• Primitive relations are axiomatized by specifying what is true in situation do(A,S) in terms of what holds in situation S.
• Derived relations are defined using clauses with a free variable in the situation argument.
• Static relations are defined without reference to the situation.

## Initial Situation

sitting_at(rob,o109,init).
sitting_at(parcel,storage,init).
sitting_at(k1,mail,init).

## Derived Relations

between(Door,P_1,P_2) &
unlocked(Door,S).
···

## When are actions possible?

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

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

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

## Axiomatizing Primitive Relations

Example: Unlocking the door makes the door unlocked:

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

Frame Axiom: No actions lock the door:

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

## Example: axiomatizing carried

Picking up an object causes it to be carried:

carrying(Ag,Obj,do(pickup(Ag,Obj),S)) <-
poss(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:
• it moved to that location:

sitting_at(Obj,Pos,do(move(Obj,Pos_0,Pos),S) ) <-
poss(move(Obj,Pos_0,Pos).

• it was put down at that location:

sitting_at(Obj,Pos,do(putdown(Ag,Obj),S) ) <-
poss(putdown(Ag,Obj),S) &
at(Ag,Pos,S).

• it was at that location before and didn't move and wasn't picked up.

## 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) <-
A=pickup(Ag,Obj).

which is equivalent to:

is_pickup_action(pickup(Ag,Obj),Obj).

## STRIPS and the Situation Calculus

• Anything that can be stated in STRIPS can be stated in the situation calculus.
• The situation calculus is more powerful. For example, the "drop everything" action.
• To axiomatize STRIPS in the situation calculus, we can use holds(C,S) to mean that C is true in situation S.

 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

## Planning

Given
• an initial world description
• a description of available actions
• a goal
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
 S=do(move(rob,mail,o103), do(pickup(rob,k1), do(move(rob,o103,mail), do(move(rob,o109,o103),init)))).

## Forward Planner

• Search in the state-space graph, where the nodes represent states and the arcs represent actions.
• Search from initial state to a state that satisfies the goal.
• A complete search strategy (e.g., A* or iterative deepening) is guaranteed to find a solution.
• Branching factor is the number of legal actions. Path length is the number of actions to achieve the goal.
• You usually can't do backward planning in the state space, as the goal doesn't uniquely specify a state.

## Planning as Resolution

• Idea: backward chain on the situation calculus rules or the situation calculus axiomatization of STRIPS.
• A complete search strategy (e.g., A* or iterative deepening) is guaranteed to find a solution.
• When there is a solution to the query with situation S=do(A,S1), action A is the last action in the plan.
• You can virtually always use a frame axiom so that the search space is largely unconstrained by the goal.

## Goal-directed searching

• Given a goal, you would like to consider only those actions that actually achieve it.
• Example:
? carrying(rob,parcel,S) & in(rob,lab2,S).
the last action needed is irrelevant to the left subgoal.

# Chapter 8, Lecture 5

## STRIPS Planner

• Divide and conquer: to create a plan to achieve a conjunction of goals, create a plan to achieve one goal, and then create a plan to achieve the rest of the goals.
• To achieve a list of goals:
• choose one of them to achieve.
• If it is not already achieved
• choose an action that makes the goal true
• achieve the preconditions of the action
• carry out the action
• achieve the rest of the goals.

## 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([],W_0,W_0).
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) <-
holds(G,W).
achieve(G,W_0,W_1) <-
clause(G,B) &
achieve_all(B,W_0,W_1).
achieve(G,W_0,do(Action,W_1)) <-
achieves(Action,G) &
preconditions(Action,Pre) &
achieve_all(Pre,W_0,W_1).

## Undoing Achieved Goals

Example: consider trying to achieve

[carrying(rob,parcel),sitting_at(rob,lab2)]
Example: consider trying to achieve
[sitting_at(rob,lab2),carrying(rob,parcel)]
• The STRIPS algorithm, as presented, is unsound.
• Achieving one subgoal may undo already achieved subgoals.

## Fixing the STRIPS Algorithm

Two ideas to make STRIPS sound:
• Protect subgoals so that, once achieved, until they are needed, they cannot be undone. Let remove return different choices.
• Reachieve subgoals that have been undone.
• Protecting subgoals makes STRIPS incomplete.
• Reachieving subgoals finds longer plans than necessary.

## Does protecting always work?

• Example Suppose the robot can only carry one item at a time. Consider the goal:
sitting_at(rob,lab2) & carrying(rob,parcel)
• We cannot consider the subgoals in isolation!

# Chapter 8, Lecture 6

## Regression

• Idea: don't solve one subgoal by itself, but keep track of all subgoals that must be achieved.
• Given a set of goals:
• If they all hold in the initial state, return the empty plan
• Otherwise, choose an action A that achieves one of the subgoals. This will be the last action in the plan.
• Determine what must be true immediately before A so that all of the goals will be true immediately after. Recursively solve these new goals.

## Regression as Path Finding

• The nodes are sets of goals. Arcs correspond to actions.
• A node labeled with goal set G has a neighbor for each action A that achieves one of the goals in G.
• The neighbor corresponding to action A is the node with the goals GA that must be true immediately before the action A so that all of the goals in G are true immediately after A. GA is the weakest precondition for action A and goal set G.
• Search can stop when you have a node where all the goals are true in the initial state.

## 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):

• wp(A,GL,WP) is false if any element of GL is on delete list of action A.
• Otherwise WP is
preconds(A) union { G in GL:G not in add_list(A)}.
where preconds(A) is the list of preconditions of action A and add_list(A) is the add list of action A.

## Weakest Precondition Example

The weakest precondition for

[sitting_at(rob,lab2),carrying(rob,parcel)]

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

[autonomous(rob),
sitting_at(rob,Pos),
carrying(rob,parcel)]

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) &
solve(NewGoalSet,W).

## Regression Search Space Example

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