BandLch14-15
KR & R © Brachman & Levesque 2005 237
14.
Actions
KR & R © Brachman & Levesque 2005 238
Situation calculus
The situation calculus is a dialect of FOL for representing
dynamically changing worlds in which all changes are the result of
named actions.
There are two distinguished sorts of terms:
• actions, such as
– put(x,y) put object x on top of object y
– walk(loc) walk to location loc
– pickup(r,x) robot r picks up object x
• situations, denoting possible world histories. A distinguished
constant S0 and function symbol do are used
– S0 the initial situation, before any actions have been performed
– do(a,s) the situation that results from doing action a in situation s
for example: do(put(A,B),do(put(B,C),S0))
the situation that results from
putting A on B after putting B
on C in the initial situation
KR & R © Brachman & Levesque 2005 239
Fluents
Predicates or functions whose values may vary from situation to
situation are called fluents.
These are written using predicate or function symbols whose last
argument is a situation
for example: Holding(r, x, s): robot r is holding object x in situation s
can have: ¬Holding(r, x, s) ∧ Holding(r, x, do(pickup(r,x),s))
the robot is not holding the object x in situation s, but is holding it in the situation
that results from picking it up
Note: there is no distinguished “current” situation. A sentence can
talk about many different situations, past, present, or future.
A distinguished predicate symbol Poss(a,s) is used to state that a
may be performed in situation s
for example: Poss(pickup(r,x), S0)
This is the entire language.
it is possible for the robot r to
pickup object x in the initial situation
KR & R © Brachman & Levesque 2005 240
Preconditions and effects
It is necessary to include in a KB not only facts about the initial
situation, but also about world dynamics: what the actions do.
Actions typically have preconditions: what needs to be true for the
action to be performed
• Poss(pickup(r,x), s) ≡ ∀z. ¬Holding(r,z,s) ∧ ¬Heavy(x) ∧ NextTo(r,x,s)
a robot can pickup an object iff it is not holding anything, the object is not too
heavy, and the robot is next to the object
Note: free variables assumed to be universally quantified
• Poss(repair(r,x), s) ≡ HasGlue(r,s) ∧ Broken(x,s)
it is possible to repair an object iff the object is broken and the robot has glue
Actions typically have effects: the fluents that change as the
result of performing the action
• Fragile(x) ⊃ Broken(x, do(drop(r,x),s))
dropping a fragile object causes it to break
• ¬Broken(x, do(repair(r,x),s))
repairing an object causes it to be unbroken
KR & R © Brachman & Levesque 2005 241
The frame problem
To really know how the world works, it is also necessary to know
what fluents are unaffected by performing an action.
• Colour(x,c,s) ⊃ Colour(x, c, do(drop(r,x),s))
dropping an object does not change its colour
• ¬Broken(x,s) ∧ [ x≠y ∨ ¬Fragile(x) ] ⊃ ¬Broken(x, do(drop(r,y),s)
not breaking things
These are sometimes called frame axioms.
Problem: need to know a vast number of such axioms. ( Few
actions affect the value of a given fluent; most leave it invariant. )
an object’s colour is unaffected by picking things up, opening a door, using
the phone, turning on a light, electing a new Prime Minister of Canada, etc.
The frame problem:
• in building KB, need to think of these ~ 2 × A × F facts about what
does not change
• the system needs to reason efficiently with them
KR & R © Brachman & Levesque 2005 242
What counts as a solution?
• Suppose the person responsible for building a KB has written down
all the effect axioms
for each fluent F and action A that can cause the truth value of F to
change, an axiom of the form [R(s) ⊃ ±F(do(A,s))], where R(s) is some
condition on s
• We want a systematic procedure for generating all the frame
axioms from these effect axioms
• If possible, we also want a parsimonious representation for them
(since in their simplest form, there are too many)
Why do we want such a solution?
• frame axioms are necessary to reason about actions and are not
entailed by the other axioms
• convenience for the KB builder
• for theorizing about actions
– modularity: only add effect axioms
– accuracy: no inadvertent omissions
KR & R © Brachman & Levesque 2005 243
The projection task
What can we do with the situation calculus?
We will see later that it can be used for planning.
A simpler job we can handle directly is called the projection task.
Given a sequence of actions, determine what would be true in the
situation that results from performing that sequence.
This can be formalized as follows:
Suppose that R(s) is a formula with a free situation variable s.
To find out if R(s) would be true after performing 〈a1,…,an〉 in the initial
situation, we determine whether or not
KB |= R(do(an,do(an-1,…,do(a1,S0)…)))
For example, using the effect and frame axioms from before, it
follows that ¬Broken(B,s) would hold after doing the sequence
〈pickup(A), pickup(B), drop(B), repair(B), drop(A)〉
KR & R © Brachman & Levesque 2005 244
The legality task
The projection task above asks if a condition would hold after
performing a sequence of actions, but not whether that sequence
can in fact be properly executed.
We call a situation legal if it is the initial situation or the result of
performing an action whose preconditions are satisfied starting in
a legal situation.
The legality task is the task of determining whether a sequence of
actions leads to a legal situation.
This can be formalized as follows:
To find out if the sequence 〈a1,…,an〉 can be legally performed in the
initial situation, we determine whether or not
KB |= Poss(ai, do(ai-1,…,do(a1,S0)…))
for every i such that 1 ≤ i ≤ n.
KR & R © Brachman & Levesque 2005 245
Limitations of the situation calculus
This version of the situation calculus has a number of limitations:
• no time: cannot talk about how long actions take, or when they
occur
• only known actions: no hidden exogenous actions, no unnamed
events
• no concurrency: cannot talk about doing two actions at once
• only discrete situations: no continuous actions, like pushing an
object from A to B.
• only hypotheticals: cannot say that an action has occurred or will
occur
• only primitive actions: no actions made up of other parts, like
conditionals or iterations
We will deal with the last of these below.
First we consider a simple solution to the frame problem …
KR & R © Brachman & Levesque 2005 246
Normal form for effect axioms
Suppose there are two positive effect axioms for the fluent Broken:
Fragile(x) ⊃ Broken(x,do(drop(r,x),s))
NextTo(b,x,s) ⊃ Broken(x,do(explode(b),s))
These can be rewritten as
∃r {a=drop(r,x) ∧ Fragile(x)} ∨ ∃b {a= explode(b) ∧ NextTo(b,x,s)}
⊃ Broken(x,do(a,s))
Similarly, consider the negative effect axiom:
¬Broken(x,do(repair(r,x),s))
which can be rewritten as
∃r {a=repair(r,x)} ⊃ ¬Broken(x,do(a,s))
In general, for any fluent F, we can rewrite all the effect axioms as
as two formulas of the form
PF(x, a ,s) ⊃ F(x, do(a,s)) (1)
NF(x, a ,s) ⊃ ¬F(x, do(a,s)) (2)
where PF(x, a ,s) and NF(x, a ,s)
are formulas whose free variables
are among the xi, a, and s.
KR & R © Brachman & Levesque 2005 247
Explanation closure
Now make a completeness assumption regarding these effect
axioms:
assume that (1) and (2) characterize all the conditions under which
an action a changes the value of fluent F.
This can be formalized by explanation closure axioms:
¬F(x, s) ∧ F(x, do(a,s)) ⊃ PF(x, a ,s) (3)
if F was false and was made true by doing action a
then condition PF must have been true
F(x, s) ∧ ¬F(x, do(a,s)) ⊃ NF(x, a ,s) (4)
if F was true and was made false by doing action a
then condition NF must have been true
These explanation closure axioms are in fact disguised versions
of frame axioms!
¬F(x, s) ∧ ¬PF(x, a ,s) ⊃ ¬F(x, do(a,s))
F(x, s) ∧ ¬NF(x, a ,s) ⊃ F(x, do(a,s))
KR & R © Brachman & Levesque 2005 248
Successor state axioms
Further assume that our KB entails the following
• integrity of the effect axioms: ¬∃ x, a, s. PF(x, a, s) ∧ NF(x, a, s)
• unique names for actions:
A(x1,…,xn) = A(y1,…,yn) ⊃ (x1=y1) ∧ …∧ (xn=yn)
A(x1,…,xn) ≠ B(y1,…,ym) where A and B are distinct
Then it can be shown that KB entails that (1), (2), (3), and (4)
together are logically equivalent to
F(x, do(a,s)) ≡ PF(x, a, s) ∨ (F(x, s) ∧ ¬NF(x, a,s))
This is called the successor state axiom for F.
For example, the successor state axiom for the Broken fluent is:
Broken(x, do(a,s)) ≡
∃r {a=drop(r,x) ∧ Fragile(x)}
∨ ∃b {a=explode(b) ∧ NextTo(b,x,s)}
∨ Broken(x, s) ∧ ¬∃r {a=repair(r,x)}
An object x is broken after doing action a
iff
a is a dropping action and x is fragile,
or a is a bomb exploding
where x is next to the bomb,
or x was already broken and
a is not the action of repairing itNote universal quantification: for any action a …
KR & R © Brachman & Levesque 2005 249
A simple solution to the frame problem
This simple solution to the frame problem (due to Ray Reiter)
yields the following axioms:
• one successor state axiom per fluent
• one precondition axiom per action
• unique name axioms for actions
Moreover, we do not get fewer axioms at the expense of
prohibitively long ones
the length of a successor state axioms is roughly proportional to the
number of actions which affect the truth value of the fluent
The conciseness and perspicuity of the solution relies on
• quantification over actions
• the assumption that relatively few actions affect each fluent
• the completeness assumption (for effects)
Moreover, the solution depends on the fact that actions always
have deterministic effects.
KR & R © Brachman & Levesque 2005 250
Limitation: primitive actions
As yet we have no way of handling in the situation calculus
complex actions made up of other actions such as
• conditionals: If the car is in the driveway then drive else walk
• iterations: while there is a block on the table, remove one
• nondeterministic choice: pickup up some block and put it on the floor
and others
Would like to define such actions in terms of the primitive actions,
and inherit their solution to the frame problem
Need a compositional treatment of the frame problem for complex
actions
Results in a novel programming language for discrete event
simulation and high-level robot control
KR & R © Brachman & Levesque 2005 251
The Do formula
For each complex action A, it is possible to define a formula of the
situation calculus, Do(A, s, s′), that says that action A when started
in situation s may legally terminate in situation s′.
Primitive actions: Do(A, s, s′) = Poss(A,s) ∧ s′=do(A,s)
Sequence: Do([A;B], s, s′) = ∃s′′. Do(A, s, s′′) ∧ Do(B, s′′, s′)
Conditionals: Do([if φ then A else B], s, s′) =
φ(s) ∧ Do(A, s, s′) ∨ ¬φ(s) ∧ Do(B, s, s′)
Nondeterministic branch: Do([A | B], s, s′) = Do(A, s, s′) ∨ Do(B, s, s′)
Nondeterministic choice: Do([πx. A], s, s′) = ∃x. Do(A, s, s′)
etc.
Note: programming language constructs with a purely logical
situation calculus interpretation
KR & R © Brachman & Levesque 2005 252
GOLOG
GOLOG (Algol in logic) is a programming language that
generalizes conventional imperative programming languages
• the usual imperative constructs + concurrency, nondeterminism, more…
• bottoms out not on operations on internal states (assignment statements,
pointer updates) but on primitive actions in the world (e.g. pickup a block)
• what the primitive actions do is user-specified by precondition and
successor state axioms
What does it mean to “execute” a GOLOG program?
• find a sequence of primitive actions such that performing them starting in
some initial situation s would lead to a situation s′ where the formula
Do(A, s, s′) holds
• give the sequence of actions to a robot for actual execution in the world
Note: to find such a sequence, it will be necessary to reason
about the primitive actions
A ; if Holding(x) then B else C
to decide between B and C we need to determine
if the fluent Holding would be true after doing A
KR & R © Brachman & Levesque 2005 253
GOLOG example
Primitive actions: pickup(x), putonfloor(x), putontable(x)
Fluents: Holding(x,s), OnTable(x,s), OnFloor(x,s)
Action preconditions: Poss(pickup(x), s) ≡ ∀z.¬Holding(z, s)
Poss(putonfloor(x), s) ≡ Holding(x, s)
Poss(putontable(x), s) ≡ Holding(x, s)
Successor state axioms:
Holding(x, do(a,s)) ≡ a=pickup(x) ∨
Holding(x,s) ∧ a≠putontable(x) ∧ a≠putonfloor(x)
OnTable(x, do(a,s)) ≡ a=putontable(x) ∨ OnTable(x,s) ∧ a≠pickup(x)
OnFloor(x, do(a,s)) ≡ a=putonfloor(x) ∨ OnFloor(x,s) ∧ a≠pickup(x)
Initial situation: ∀x.¬Holding(x, S0)
ΟnTable(x, S0) ≡ x=A ∨ x=B
Complex actions:
proc ClearTable : while ∃b.OnTable(b) do πb [OnTable(b)? ; RemoveBlock(b)]
proc RemoveBlock(x) : pickup(x) ; putonfloor(x)
KR & R © Brachman & Levesque 2005 254
Running GOLOG
To find a sequence of actions constituting a legal execution of a GOLOG
program, we can use Resolution with answer extraction.
For the above example, we have
KB |= ∃s. Do(ClearTable, S0, s)
The result of this evaluation yields
s = do(putonfloor(B), do(pickup(B), do(putonfloor(A), do(pickup(A),S0))))
and so a correct sequence is
〈 pickup(A), putonfloor(A), pickup(B), putonfloor(B)〉
When what is known about the actions and initial state can be expressed
as Horn clauses, the evaluation can be done in Prolog.
The GOLOG interpreter in Prolog has clauses like
do(A,S1,do(A,S1)) :- prim_action(A), poss(A,S1).
do(seq(A,B),S1,S2) :- do(A,S1,S3), do(B,S3,S2).
This provides a convenient way of controlling a robot at a high level.
KR & R © Brachman & Levesque 2005 255
15.
Planning
KR & R © Brachman & Levesque 2005 256
Planning
So far, in looking at actions, we have considered how an agent
could figure out what to do given a high-level program or complex
action to execute.
Now, we consider a related but more general reasoning problem:
figure out what to do to make an arbitrary condition true. This is
called planning.
• the condition to be achieved is called the goal
• the sequence of actions that will make the goal true is called the plan
Plans can be at differing levels of detail, depending on how we
formalize the actions involved
• “do errands” vs. “get in car at 1:32 PM, put key in ignition, turn key
clockwise, change gears,…”
In practice, planning involves anticipating what the world will be
like, but also observing the world and replanning as necessary…
KR & R © Brachman & Levesque 2005 257
Using the situation calculus
The situation calculus can be used to represent what is known
about the current state of the world and the available actions.
The planning problem can then be formulated as follows:
Given a formula Goal(s), find a sequence of actions a such that
KB |= Goal(do(a, S0)) ∧ Legal(do(a, S0))
where do(〈a1,…,an〉, S0) is an abbreviation for
do(an, do(an-1, …, do(a2, do(a1, S0)) …))
and where Legal(〈a1,…,an〉, S0) is an abbreviation for
Poss(a1, S0) ∧ Poss(a2, do(a1, S0)) ∧ … ∧ Poss(an, do(〈a1,…,an-1〉, S0))
So: given a goal formula, we want a sequence of actions such that
• the goal formula holds in the situation that results from executing the
actions, and
• it is possible to execute each action in the appropriate situation
KR & R © Brachman & Levesque 2005 258
Planning by answer extraction
Having formulated planning in this way, we can use Resolution
with answer extraction to find a sequence of actions:
KB |= ∃s. Goal(s) ∧ Legal(s)
We can see how this will work using a simplified version of a
previous example:
An object is on the table that we would like to have on the floor. Dropping
it will put it on the floor, and we can drop it, provided we are holding it. To
hold it, we need to pick it up, and we can always do so.
• Effects: OnFloor(x, do(drop(x),s))
Holding(x, do(pickup(x),s))
Note: ignoring frame problem
• Preconds: Holding(x, s) ⊃ Poss(drop(x), s)
Poss(pickup(x), s)
• Initial state: OnTable(B, S0)
• The goal: OnFloor(B, s)
KB
KR & R © Brachman & Levesque 2005 259
Deriving a plan
[¬OnFloor(B,s1), ¬Legal(s1), A(s1)]
[¬Legal(do(drop(B),s2)), A(do(drop(B),s2))]
[¬Legal(s2), ¬Poss(drop(B),s2), A(do(drop(B),s2))]
[¬Legal(s2), ¬Holding(B,s2), A(do(drop(B),s2))]
[A(do(drop(B),do(pickup(B),s3))), ¬Legal(do(pickup(B),s3))]
[¬Legal(s3), A(do(drop(B),do(pickup(B),s3))), ¬Poss(pickup(B),s3), ]
[¬Legal(s3), A(do(drop(B),do(pickup(B),s3)))]
[A(do(drop(B), do(pickup(B), S0)))]
Axiom 1
expand Legal
Axiom 3
Axiom 2
expand Legal
Axiom 4
Legal for S0
Negated query + answer predicate
Here is the plan: in the initial situation, pickup
block B, and in the resulting situation, drop B.
KR & R © Brachman & Levesque 2005 260
Using Prolog
Because all the required facts here can be expressed as Horn
clauses, we can use Prolog directly to synthesize a plan:
onfloor(X,do(drop(X),S)).
holding(X,do(pickup(X),S)).
poss(drop(X),S) :- holding(X,S).
poss(pickup(X),S).
ontable(b,s0).
legal(s0).
legal(do(A,S)) :- poss(A,S), legal(S).
With the Prolog goal ?- onfloor(b,S), legal(S).
we get the solution S = do(drop(b),do(pickup(b),s0))
But planning problems are rarely this easy!
Full Resolution theorem-proving can be problematic for a complex
set of axioms dealing with actions and situations explicitly…
KR & R © Brachman & Levesque 2005 261
The STRIPS representation
STRIPS is an alternative representation to the pure situation
calculus for planning.
from work on a robot called Shaky at SRI International in the 60’s.
In STRIPS, we do not represent histories of the world, as in the
situation calculus.
Instead, we deal with a single world state at a time, represented
by a database of ground atomic wffs (e.g., In(robot,room1))
This is like the database of facts used in procedural representations and
the working memory of production systems
Similarly, we do not represent actions as part of the world model
(cannot reason about them directly), as in the situation calculus.
Instead, actions are represented by operators that syntactically
transform world models
An operator takes a DB and transforms it to a new DB
KR & R © Brachman & Levesque 2005 262
STRIPS operators
Operators have pre- and post-conditions
• precondition = formulas that need to be true at start
• “delete list” = formulas to be removed from DB
• “add list” = formulas to be added to DB
Example: PushThru(o,d,r1,r2)
“the robot pushes object o through door d from room r1 to room r2”
• precondition: InRoom(robot,r1), InRoom(o,r1), Connects(d,r1,r2)
• delete list: InRoom(robot,r1), InRoom(o,r1)
• add list: InRoom(robot,r2), InRoom(o,r2)
initial world model, DB0 (list of ground atoms)
STRIPS problem space = set of operators (with preconds and effects)
goal statement (list of atoms)
desired plan: sequence of ground operators
KR & R © Brachman & Levesque 2005 263
STRIPS Example
In addition to PushThru, consider
GoThru(d,r1,r2):
precondition: InRoom(robot,r1), Connects(d,r1,r2)
delete list: InRoom(robot,r1)
add list: InRoom(robot,r2)
DB0:
InRoom(robot,room1) InRoom(box1,room2)
Connects(door1,room1,room2) Box(box1)
Connects(door2,room2,room3) …
Goal: [ Box(x) ∧ InRoom(x,room1) ]
ROBOT
BOX1
ROOM1 ROOM2
ROOM3
DOOR1
DOOR2
KR & R © Brachman & Levesque 2005 264
Progressive planning
Here is one procedure for planning with a STRIPS like
representation:
Input : a world model and a goal
Output : a plan or fail.
ProgPlan[DB,Goal] =
If Goal is satisfied in DB, then return empty plan
For each operator o such that precond(o) is satisfied in the current DB:
Let DB´ = DB + addlist(o) – dellist(o)
Let plan = ProgPlan[DB´,Goal]
If plan ≠ fail, then return [act(o) ; plan]
End for
Return fail
This depth-first planner searches forward from the given DB0 for
a sequence of operators that eventually satisfies the goal
DB´ is the progressed world state
(ignoring variables)
KR & R © Brachman & Levesque 2005 265
Regressive planning
Here is another procedure for planning with a STRIPS like
representation:
Input : a world model and a goal
Output : a plan or fail.
RegrPlan[DB,Goal] =
If Goal is satisfied in DB, then return empty plan
For each operator o such that dellist(o) ∩ Goal = {}:
Let Goal´ = Goal + precond(o) – addlist(o)
Let plan = RegrPlan[DB,Goal´]
If plan ≠ fail, then return [plan ; act(o)]
End for
Return fail
This depth-first planner searches backward for a sequence of
operators that will reduce the goal to something satisfied in DB0
Goal´ is the regressed goal
(ignoring variables)
KR & R © Brachman & Levesque 2005 266
Computational aspects
Even without variables, STRIPS planning is NP-hard.
Many methods have been proposed to avoid redundant search
e.g. partial-order planners, macro operators
One approach: application dependent control
Consider this range of GOLOG programs:
< any deterministic program > while ¬Goal do πa . a
In between, the two extremes we can give domain-dependent
guidance to a planner:
while ¬Goal do πa . [Acceptable(a)? ; a]
where Acceptable is formalized separately
This is called forward filtering .
fully specific about sequence
of actions required
any sequence such that Goal
holds at end
easy to execute as hard as planning!
pick an action
KR & R © Brachman & Levesque 2005 267
Hierarchical planning
The basic mechanisms of planning so far still preserve all detail
needed to solve a problem
• attention to too much detail can derail a planner to the point of uselessness
• would be better to first search through an abstraction space, where
unimportant details were suppressed
• when solution in abstraction space is found, account for remaining details
ABSTRIPS
precondition wffs in abstraction space will have fewer literals than those in
ground space
e.g., PushThru operator
– high abstraction: applicable whenever an object is pushable and a door exists
– lower: robot and obj in same room, connected by a door to target room
– lower: door must be open
– original rep: robot next to box, near door
predetermined partial order of predicates with “criticality” level
KR & R © Brachman & Levesque 2005 268
Reactive systems
Some suggest that explicit, symbolic production of formal plans is
something to be avoided (especially considering computational
complexity)
even propositional case is intractable; first-order case is undecidable
Just “react”: observe conditions in the world and decide (or look
up) what to do next
can be more robust in face of unexpected changes in the environment
⇒ reactive systems
“Universal plans”: large lookup table (or boolean circuit) that tells
you exactly what to do based on current conditions in the world
Reactive systems have impressive performance on certain low-
level problems (e.g. learning to walk), and can even look
“intelligent”
but what are the limitations? …