程序代写代做代考 concurrency prolog interpreter database BandLch14-15

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? …