EECS 3401 — AI and Logic Prog. — Lecture 16
Adapted from slides of Brachman & Levesque (2005)
Vitaliy Batusov
vbatusov@cse.yorku.ca
York University
November 16, 2020
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 16 November 16, 2020 1 / 26
Today: Actions and Situations
Required reading: R & N Ch.11 (10 in 3-rd ed.)
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 16 November 16, 2020 2 / 26
Planning: more than search
Two strands in AI covered so far: Symbolic reasoning
knowledge representation & reasoning using FOL Static knowledge, complex but unchanging state
Search
Path-finding in large graphs over complex states Multiple states implies dynamics of some sort
Last time: planning as heuristic search
STRIPS is flawed, but contains the seeds of a great idea Knowledge base ⇒ world state
Logical theory changes from state to state???
Can we describe this change within the theory itself?
Actually, the idea is much older than STRIPS.
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 16 November 16, 2020 3 / 26
Aside
Trouble with describing change in logic using implication Implication: Cause → Effect
Equiv. to ¬Cause ∨ Effect
Still holds when Cause = false and Effect = true So, can have Effect without Cause
Let’s rule this out by disallowing this row in truth table Get Cause ↔ Effect
Can no longer distinguish between cause and effect The whole thing loses meaning
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 16 November 16, 2020 4 / 26
Planning: more than search
McCarthy, J. and Hayes, P.J., 1969. Some philosophical problems from the standpoint of AI, Machine Intelligence (Meltzer B. and Michie D., eds.), vol. 4. http://www-formal.stanford.edu/jmc/mcchay69.pdf
Fundamental work on the philosoply of AI; introduces situation calculus. Recommended reading of general interest.
Reiter, R., 2001. Knowledge in action: logical foundations for specifying and implementing dynamical systems. MIT press.
Combines many many refinements to McCarthy’s proposal into a robust formalism
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 16 November 16, 2020 5 / 26
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.
Many-sorted logic: has several domains, one for each sort. Each term is interpreted only within its own sort.
Situation calculus has sorts action, situation, and object
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 16 November 16, 2020 6 / 26
Actions and Situations
Actions: denoted by function terms of sort action, e.g., put(x,y) — put thing x on top of thing y walk(location) — walk to location location pickup(r,x) — robot r picks up thing x
Situations: world histories built using specialized symbols S0 and do(·,·) S0 — a constant, always denotes the initial situation
do(a,s) — a situation that results from doing action a in situation s
Example: do(put(A,B),do(put(B,C),S0))
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 16 November 16, 2020 7 / 26
Fluents
Already understand: predicates in FOL
Fluents: predicates whose values may vary from situation to
situation
Syntactically, a fluent is a predicate whose last argument is of sort
situation
Example: Holding(r, x, s) — robot r is holding thing x in situation s
Can also say things like ¬Holding(r, x, s) ∧ Holding(r, x, do(pickup(r, x, ), s))
Note: there is no distinguished “current” situation. A sentence can talk about many different situations, past, present, and future.
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 16 November 16, 2020 8 / 26
Poss
Also:
A distinguished predicate symbol Poss(a,s) is used to state that
action a is legal to carry out in situation s.
Poss(pickup(r,x),S0) — it is possible for robot r to pick up thing x in the initial
situation
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 16 November 16, 2020 9 / 26
Preconditions and effects
It is necessary to include in a KB not only facts about the initial situation, but also about world dynamics
I.e., a formal account of how and why things which are true (false) in one situation become false (true) in the next
Action preconditions and action effects
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 16 November 16, 2020 10 / 26
Preconditions and effects
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)
Free variables are assumed to be universally quantified from outside
Poss(repair(R,X),S) ↔ HasGlue(R,S) ∧ Broken(X,S) These are called precondition axioms
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 16 November 16, 2020 11 / 26
Preconditions and effects
Actions typically have effects: the fluents that change as the result of performing the action
Fragile(X) → Broken(X,do(drop(R,X),S))
¬Broken(X,do(repair(R,X),S)) These are called effect axioms
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 16 November 16, 2020 12 / 26
The Frame Problem
Effect axioms only describe what changes. To fully describe how the world works, need to specify what fluents are unaffected by what actions.
Colour(X,C,S) → Colour(X,C,do(drop(R,X),S)) ¬Broken(X,S)∧[X ̸=Y ∨¬Fragile(X)]→¬Broken(X,do(drop(R,Y),S))
These are called frame axioms
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 16 November 16, 2020 13 / 26
Frame Problem
Problem! There will always be a vast number of frame axioms. An object’s colour is unaffected by picking things up, opening a door, calling a friend, turning on a light, weather patterns in China, etc.
In building a KB, need to include 2 × |A| × |F | facts about what doesn’t change, and then reason efficiently with them
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 16 November 16, 2020 14 / 26
The Frame Problem
Suppose we have a complete set of effect axioms (non-trivial dynamics, written down by a specialist)
Can we maybe generate the frame axioms mechanically? And, hopefully, in some compact form
Yes, under some assumptions (later)
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 16 November 16, 2020 15 / 26
The Projection Task
What is the situation calculus good for?
Projection task: Given a sequence of actions, determine what would
be true in the situation that results from performing that sequence
More formally: Suppose R(S) is a formula with a free situation variable S. To find out if R(S) would be true after performing actions ⟨a1 , . . . , an ⟩ in the initial situation, we determine whether or not
KB |= R(do(an, do(an−1, . . . , do(a1, S0) . . .)))
Example: using axioms above, it follows that ¬Broken(b,S) would hold after executing the sequence
⟨pickup(a), pickup(B), drop(B), repair(B), drop(A)⟩
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 16 November 16, 2020 16 / 26
Legality / Executability
Projection does not test for whether the sequence of actions is legal (wrt precondition axioms)
We call a situation legal is it is the initial situation or the result of performing an action whose preconditions are satisfied starting in a legal situation
Legality task: task of determining whether a sequence of actions leads to a legal situation
More formally: 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 all 1 ≤ i ≤ n.
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 16 November 16, 2020 17 / 26
Limitations of Situation Calculus
(as presented)
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
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 internal structure to actions, conditional actions, iterative actions, etc.
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 16 November 16, 2020 18 / 26
A Solution to Frame Problem
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)) Can equivalently rewrite these as
∃R{A = drop(R,X) ∧ Fragile(X)} ∨∃B{A = explode(B)∧NextTo(B,X,S)} → Broken(X,do(A,S))
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 16 November 16, 2020 19 / 26
A Solution to Frame Problem
Similarly for the negative effect axiom: ¬Broken(X,do(repair(R,X),S))
can be rewritten as
∃R{A = repair(R,X)} → ¬Broken(X,do(A,S))
Note how nice the right-hand sides are starting to look. This is called the normal form for effect axioms. (One positive NF axiom, one negative NF axiom.)
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 16 November 16, 2020 20 / 26
A Solution to Frame Problem
In general, for any fluent F, we can rewrite all the effect axioms 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)
Next, make a completeness assumption regarding these:
Assume that (1) and (2) characterize ALL the conditions under which an action A changes the value of fluent F
Formally, this is captured by explanation closure axioms: ¬F (X ̄ , S ) ∧ F (X ̄ , do (A, S )) → PF (X ̄ , A, S )
F (X ̄ , S ) ∧ ¬F (X ̄ , do (A, S )) → NF (X ̄ , A, S )
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 16 November 16, 2020
(3) (4)
21 / 26
A Solution to Frame Problem
In fact, axioms (3) and (4) are, in fact, disguised versions of the 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 ))
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 16 November 16, 2020 22 / 26
A Solution to Frame Problem
Need some additional assumptions:
Integrity of effect axioms: can’t have PF(X ̄,A,S) and NF(X ̄,A,S)
hold at the same time—this must be provable from KB Unique names for actions—some standard axioms
With these and some effort, it can be shown that, in the models of the KB, the axioms (1)–(4) 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.
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 16 November 16, 2020 23 / 26
Example
Example of a SSA:
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 )}
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 16 November 16, 2020 24 / 26
A simple solution to the frame problem
This simple solution is due to Raymond Reiter yields the following axioms:
one SSA per fluent
one precondition axiom per action unique name axioms for actions
Note: the length of a SSA is roughly proportional to the number of actions which affect the truth value of the fluent
The conciseness of the solution relies on quantification over actions, the assumption that relatively few actions affect each fluent, and the completeness assumption (also, assumption of determinism)
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 16 November 16, 2020 25 / 26
End of Lecture
Next time: GOLOG and Planning in Situation Calculus
Vitaliy Batusov vbatusov@cse.yorku.ca (YorkU) EECS 3401 Lecture 16 November 16, 2020 26 / 26