SITUATION CALCULUS WITH ACTIONS AND OTHER EVENTS John McCarthy Computer Science Department Stanford University jmc@cs.stanford.edu http://www-formal.stanford.edu/jmc/ 2005 Nov 17

A slogan for AI: Whatever a person can do, he should be able to make a computer do for him.

Almost all of my papers are on the above-mentioned web page.

This lecture proposes Events Primary Sequential situation calculus, EPS sitcalc for short.

SITUATION CALCULUS

• Proposed 1963 for formalizing effects of actions.

• Improved 2002 to include occurrence axioms.

• http://www-formal.stanford.edu/jmc/sitcalc.html

ACTIONS ARE EVENTS

• In EPS situation calculus, events are primary and actions by actors are a kind of event. EPS is sequential.

• The logic is first order logic without causal operators. Second order formulas are used for circumscription.

• An event e has some effect axioms formalizing

<preconditions >→ Holds(fluent, Result(e, s))  (1)

• An internal event e also has an occurrence axiom

<preconditions >→ Occurs(e, s),  (2)

and an axiom for the next situation

Occurs(e, s) → Next(s) = Result(e, s).  (3)

• Some phenomena previously axiomatized with domain constraints are often more accurately and conveniently axiomatized by using internal events. When both vents are blocked the room becomes stuffy.

• We minimize change a situation at a time. A vent becoming blocked and the room becoming stuffy occur in different situations.

• When the theory is used for projection of the consequences of sequences of events, the nonmonotonic reasoning is done one situation at a time.

• When an event e is not governed by an occurrence axiom, we have branching time, i.e. non-determinism. When Occurs(e, s) holds, we have linear time.

• Processes that don’t settle down cannot be treated with state constraints. The buzzer is an example, and the stuffy room elaborated to buzz is another.

Result^{∗}, Next, Next^{∗}

• Result^{∗}(e, s) gives the situation resulting from e after the events formalized to occur have happened. For example, if vent1 is closed, then Result^{∗}(Block2, s) = Result(Getstuffy, Result(Block2, s)).

• When what occurs in a situation is determined, there is a next situation satisfying

Occurs(e, s) → Next(s) = Result(e, s).  (4)

• When other actions are asserted to occur Next^{∗}(s) is sometimes wanted. Result^{∗} and Next^{∗} are undefined when the system doesn’t settle down as in the buzzer or the buzzing stuffy room.

A BUZZER—1

A simple buzzer consists of a relay operating a break switch. When the relay isn’t energized, current can flow through the switch operating the relay. When the relay operates it opens the switch, cutting off the current through the relay. The system then oscillates, i.e. buzzes.

The buzzer has only internal events—four of them. Operating and releasing the relay, and operating and releasing the switch.

A BUZZER—2

Effect axioms:

\begin{matrix}Holds(On(R), Result(Onn(R), s)) \\ ¬Holds(On(R), Result(Offf (R), s)) \\ Holds(On(Sw), Result(Onn(Sw), s) \\ ¬Holds(On(Sw), Result(Offf (Sw), s)). \end{matrix}  (5)

Occurrence axioms:

\begin{matrix}¬Holds(On(Sw), s) ∧ Holds(On(R), s) \\ → Occurs(Offf (R), s) \\ Holds(On(Sw), s) ∧ ¬Holds(On(R), s) \\ → Occurs(Onn(R), s)) \\ Holds(On(R), s) ∧ Holds(On(Sw), s) \\ → Occurs(Offf (Sw), s) \\ ¬Holds(On(R), s) ∧ ¬Holds(On(Sw), s) \\ → Occurs(Onn(Sw), s) \end{matrix}  (6)

THE STUFFY ROOM

A room has two vents, vent1 and vent2. The vents can be opened or closed. When both vents are closed, the room is, or becomes stuffy. Matt Ginsberg proposed this scenario in 1988 to show that simply minimizing change gives an unintended model, namely a model in which when one vent is closed, the other opens, which avoids changing the stuffiness of the room.

We formalize this using the internal events of the room becoming stuffy or unstuffy.

We then elaborate the scenario to express that when the room is stuffy, Pat then opens a vent.

THE STUFFY ROOM—simple

Effect axioms:

\begin{matrix}Holds(Blocked1, Result(Block1, s)) \\ Holds(Blocked2, Result(Block2, s)) \\ ¬Holds(Blocked1, Result(Unblock1, s)) \\ ¬Holds(Blocked2, Result(Unblock2, s)) \\ Holds(Stuffy, Result(Getstuffy, s)) \\ ¬Holds(Stuffy, Result(Ungetstuffy, s)) \end{matrix}  (7)

Occurrence axioms:

\begin{matrix}Holds(Blocked1, s) ∧ Holds(Blocked2, s) \\ ∧¬Holds(Stuffy, s) \\ → Occurs(Getstuffy, s) \\ and \\ (¬Holds(Blocked1, s) ∨ ¬Holds(Blocked2, s)) \\ ∧Holds(Stuffy, s) \\ → Occurs(Ungetstuffy, s) \end{matrix}  (8)

ELABORATING THE STUFFY ROOM

The first elaboration says that when Pat finds the room stuffy he unblocks vent2. We have

Holds(Stuffy, s) → Occurs(Does(P at, Unblock2), s). (9)

A second elaboration in which Mike finds the room cold when there is an unblocked vent and blocks vent2 is expressed by

Holds(Unstuffy, s) → Occurs(Does(Mike, Block2), s). (10)

With both elaborations, we get an oscillation; Pat unblocks vent2 and Mike blocks it again.

NONMONOTONIC REASONING IN SITCALC

• Projection is the easy case of nonmonotonic reasoning about the effects of events.

• When we project, we can circumscribe in each situation successively. It gives the same results as Shoham’s chronological minimization but is much simpler technically. It doesn’t suit the stolen car scenario in which a fact about the future is given.

• We minimize the predicates Occurs, P revents, Changes, etc. Strictly speaking, we circumscribe (λe)Occurs(e, s) and (λf e)P revents(f, e, s), (λe f)Changes(e, f, s).

NONMONOTONIC REASONING—2

F oo′ ≤_{s} F oo ≡ (∀vars)(F oo′(vars, s) → F oo(vars, s)), (F oo′ <_{s} F oo) ≡ (F oo′ ≤_{s} F oo) ∧ ¬(F oo′ =_{s} F oo), F oo′ =_{s} F oo ≡ (∀vars)(F oo′(vars) ≡ F oo(vars, s)),

(11)

where vars stands for a list of the entities varied as F oo is minimized. Then the circumscription of F oo(vars, s) takes the form

\begin{matrix}Axiom(F oo, vars) ∧ (∀foo′ vars′)(Axiom(foo′, vars′) \\ → ¬(foo′ <_{s} F oo)). \end{matrix}

(12)

This spells out to

\begin{matrix}Axiom(F oo, vars) ∧ (∀foo′ vars′) \\ (Axiom(foo′, vars′) ∧ ((∀vars)(foo′(vars, s) \\ → F oo(vars, s)) \\ → (∀vars)(F oo(vars, s) ≡ foo′(vars, s)))). \end{matrix}  (13)

Call this formula Circ(Axiom; F oo; vars; s).

The general frame axioms are

¬Changes(e, p, s) → (Holds(p, Result(e, s)) ≡ Holds(p, s))

(14)

for propositional fluents and

¬Changes(e, f, s) → V alue(f, Result(e, s)) = V alue(f, s).

(15)

for general fluents.

NARRATIVES

• A narrative is a set of situations, event, and assertions about situations and maybe assertions about events.

• A simple narrative consists of two sequences (S_{1}, S_{2}, …) and (E_{1}, E_{2}, …), where S_{i+1} = Result(E_{i}, S_{i}) for each i.

• Unfortunately, real narratives, whether historical or fictional, are rarely if ever simple.

SOME PHILOSOPHY

• Assume a deterministic world—if you like with stochastic processes and quantum processes. That doesn’t give free will.

• Some entities, including people and chess programs, make choices.

• Making a choice involves considering the consequences of alternative actions, e.g. using a non-determinist theory like situation calculus. This is minimal free will.

• Thus deterministic entities use non-deterministic theories.

• Do the philosophy as you like, but this is how AI has to be done.

FREE WILL IN A DETERMINIST WORLD

• We can make our theory of a process more determinist by adding occurrence axioms. We can do it if we learn more or adopt rules for deciding on actions.

• Human free will may consist of using a non-determinist theory to decide deterministically on an action.

Here’s a minimal example of using a non-determinist theory within a determinist rule.

Occurs(Does(John,
if Prefers (John, Result(Does(John, a1), s),
Result(Does(John, a2), s))
then a1
else a2
), s).

(16)

• Here Prefers (John, s1, s2) is to be understood as asserting that John prefers situation s1 to s2.

• Do animals, even apes, make decisions based on comparing anticipated consequences? If not, can apes be trained to do it? Chess programs do. According to Dan Dennett, some recent experiments suggest that apes sometimes consider the consequences of alternate actions.

• We envisage an extended theory of free will that can treat whether an action was done freely and whether it merits blame or praise.

CONCLUSIONS AND REMARKS

• This formalism is preliminary. It needs to be elaborated to allow concurrent and continuous events.

• Sequential processes, as treated in EPS, are worth separate formalization, because most common sense narrative and planning fit within the sequential case.

• The eventual formalism must permit elaborating a sequential theory by adding a few or many concurrent or continuous processes. On the other hand, specialization to the sequential case also needs to be a simple operation on a theory allowing concurrent events.

• For the future: It would be more Newton-like to say that a proccess continues until something interrupts it.

OTHER WORK

Events that are not actions have been previously used—at least by Fangzhen Lin, Sheila McIlraith, and Javier Pinto.

Occurrence axioms are even more important in the treatment of concurrent events in situation calculus—to be the subject of another article. http://www-formal.stanford.edu/jmc/freewill2.html applies these ideas to formalizing simple deterministic free will.

This work benefited from discussions with Eyal Amir, Tom Costello, Ron Fadel, Hector Levesque, Vladimir Lifschitz, Fangzhen Lin, Sheila McIlraith, Leora Morgenstern, Aarati Parmar, Raymond Reiter, and Tran Son and the comments of three anonymous referees.

This research was partly supported by SRI Subcontract No. 34-000144 under SPAWAR Prime Contract No. N66001-00-C-8018.