KR&R
Situation Calculus
Second-Order Logic (SOL)
In FOL we quantify over individuals, but not over properties.
In FOL we can find the individuals of a property, but how can we
find the properties of an individual?
E.g. Suppose a simple knowledge base (KB): father(John).
:-? father (x).
KB|= x=John
But we can’t ask
:-? X (John).
KB|= X=father
Second-Order Logic (SOL)
SOL is extending FOL
Variables in predicate positions (rather than only in
individual positions in FOL)
Quantification over predicates
As a result, SOL has more “expressive power” than FOL does.
E.g. In FOL there is no way to say explicitly that
individuals a and b have at least a same property in
common, but in SOL we can say:
P ( P(a) P(b) )
Second-Order Logic (SOL)
Examples:
P P(John), “There is a property P that John is member of”
F F(John) ¬F(John) (principle of bivalence)
“For every property, either John has it or he doesn’t.”
Equality in SOL can be defined by:
x=y def P (P(x) P(y))
Situation Calculus : Overview
The Situation Calculus is a logic formalism designed for
representing and reasoning about dynamical domains.
McCarthy, Hayes 1969
Reiter 1991
In First-Order Logic, sentences are either true or false and
stay that way. Nothing is corresponding to any sort of
change.
SitCalc represents changing scenarios as a set of SOL
formulae.
Situation Calculus :Basic Elements
Actions that can be performed in the world
Actions can be quantified
Fluents that describe the state of the world
Situations represent a history of action occurrences
A dynamic world is modeled as progressing through a
series of situations as a result of various actions being
performed within the world
A finite sequence of actions
A situation is not a state, but a history
Situation Calculus
Actions
move(x, y): robot is moving to a new location (x, y)
pickup(o): robot picks up an object o
drop(o): robot drops the object o that holds
Situation Calculus
Situations
Initial situation S0: no actions have yet occurred
A new situation, resulting from the performance of
an action a in current situation s, is denoted using
the function symbol do(a, s).
do(move(2, 3), S0): denotes the new situation after the
performance of action move(2, 3) in initial situation S0.
do(pickup(Ball ), do(move(2, 3), S0))
do(a,s) is equal to do(a’,s’) s=s’ and a=a’
Situation Calculus
Fluents: “properties of the world”
Relational fluents
Statements whose truth value may change
They take a situation as a final argument
is_carrying(o, s): robot is carrying object o in situation s
E.g. Suppose that the robot initially carries nothing
is_carrying(Ball, S0) : FALSE
is_carrying(Ball, do(pickup(Ball ), S0)) : TRUE
Situation Calculus
Fluents (cont.)
Functional fluents
Functions that return a situation-dependent value
They take a situation as a final argument
location(s): returns the location (x, y) of the robot
in situation
Situation Calculus
Action Preconditions Axioms
Some actions may not be executable in a given
situation
Poss(a,s): special binary predicate
denotes the executability of action a in situation s
Examples:
Poss(drop(o),s) is_carrying(o,s)
Poss(pickup(o),s) (z ¬is_carrying(z,s) ¬heavy(o))
Situation Calculus
Action Effects Axioms
Specify the effects of an action on the fluents
Examples:
Poss(pickup(o),s) → is_carrying(o,do(pickup(o),s))
Poss(drop(o),s) fragile(o) → broken(o,do( drop(o),s))
Is that enough? No, because of the frame problem
Situation Calculus
The frame problem
How can we derive the non-effects of axioms?
E.g. How can we derive that after picking up an
object, the robot’s location remains unchanged?
This requires a formulae like
Poss(pickup(o),s) location(s) = (x,y) →
location(do(pickup(o),s)) = (x,y)
Problem: too many of such axioms, difficult to
specify all
Situation Calculus
The solution: Successor state axioms
Specify all the ways the value of a particular fluent can be
changed
Poss(a,s) γ+F(x,a,s) → F(x,do(a,s))
Poss(a,s) γ-F(x,a,s) → ¬F(x,do(a,s))
γ+F describes the conditions under which action a in situation s makes
the fluent F become true in the successor situation do(a,s) .
γ-F describes the conditions under which performing action a in
situation s makes fluent F false in the successor situation.
Situation Calculus
Successor state axioms (cont.)
Poss(a,s) → [F(x,do(a,s)) γ+F(x,a,s) (F(x,s) ¬γ-F(x,a,s))]
“Given that it is possible to perform a in s, the fluent F would be
true in the resulting situation do(a,s) iff performing a in s would
make it true, or it is true in s and performing a in s would not
make it false. ”
Example:
Poss(a,s) → [broken(o,do(a,s)) (a=drop(o) fragile(o))
(broken(o,s) a repair(o,s))]
Situation Calculus
Precondition Axioms
Poss(pickup(o),s) z ¬is_carrying(z,s) ¬heavy(o)
Poss(putonfloor(o),s) is_carrying(o,s)
Poss(putontable(o),s) is_carrying(o,s)
Successor State Axioms
is_carrying(o,do(a,s)) a=pickup(o) (is_carrying(o,s) a putontable(o) a
putonfloor(o) )
OnTable(o,do(a,s)) (OnTable(o,s) a pickup(o)) a = putontable(o)
OnFloor(o,do(a,s)) (OnFloor(o,s) a pickup(o)) a = putonfloor(o)
Initial state
¬is_carrying(o,S0)
OnTable(o, S0) o=A o=B
proc: RemoveBlock(o) : pickup(o) ; putonfloor(o) endProc;
proc: ClearTable : while o OnTable(o) do RemoveBlock(o) endWhile endProc;
KB |= s Do(ClearTable, S0, s).
s=do(putonfloor(B),do(pickup(B),do(putonfloor(A),do(pickup(A), S0))))
References
[Link] and [Link], Some Philosophical Problems from the
Standpoint of Artificial Intelligence, in Machine Intelligence 4, ed
[Link] and [Link], Edinburgh University Press (1969)
R. Reiter, On Specifying Database Updates, Journal of Logic Programming,
25(1):53–91, 1995.
ANY QUESTIONS?