CSE 150 Lecture Notes, February 10, 2004

CSE150 LECTURE NOTES

February 10, 2004

ANNOUNCEMENTS

The deadline for the current project is Friday this week, in section at 2pm.

REASONING ABOUT ACTIONS AND THEIR EFFECTS

The traditional ontology for reasoning about action is called the situation calculus and is due to John McCarthy of Stanford. It involves three basic categories:

a "state" is a snapshot of the world,
a "fluent" is a changing relationship between objects, and
an "action" is an event that changes one state into another.

States, fluents, and actions can be represented by FOL terms built from constant-symbols and function-symbols:

a and b can be constants naming two blocks,
s_0 can be the name of the beginning state of the world
stack(a,b) can name the action of placing a on b,
do(s_0,stack(a,b)) can name the state resulting from doing this action in the initial state s_0.

We use a predicate named holds to connect fluents with states. For example:

holds( ontopof(a,b), do(s_0, stack(a,b)) )

THE YALE SHOOTING PROBLEM

This is a standard example domain used in research on reasoning about action. It is simpler than the blocks world, and called the Yale shooting problem because it was invented by Steve Hanks and Drew McDermott of Yale. There are

two objects (a turkey and a gun),
three fluents (loaded, alive, and dead), and
three actions (load, wait, and shoot).

Note that, because it is a single specific example, the Yale shooting problem is really a problem instance.

Some obvious axioms for this world are:

forall s holds(loaded,do(load,s))
forall s holds(loaded,s) -> holds(dead,do(s,shoot))
forall s holds(loaded,s) -> ~holds(alive,do(s,shoot))
forall s holds(loaded,s) -> ~holds(loaded,do(s,shoot)).

Unfortunately, the axioms above have many undesired models. In order to eliminate these, we must state many more axioms. Most of these additional axioms are about actions not changing the truth of fluents. For example:

forall s holds(alive,s) -> holds(alive,do(s,load))
forall s holds(alive,s) -> holds(alive,do(s,wait))
forall s holds(alive,s) & ~holds(loaded,s) -> holds(alive,do(s,shoot))

and many more.

In general, one axiom is needed for each pair of an action and a fluent, to state whether or not the action changes the fluent. Intuitively, we should only need to write down an axiom when an action does change a fluent, not otherwise.

THE FRAME PROBLEM AND A SOLUTION

In general, with a different actions and e fluents O(ae) axioms are needed. Intuitively, only O(a+e) axioms should be needed. The notorious frame problem is to escape the predicament of having to state so many axioms that should somehow be true by default.

One solution is as follows. We use three basic predicates: "holds", "causes", and "cancels", and we formalize some commonsense knowledge:

``A fluent holds in the state resulting from an action if and only if the action `causes' the fluent, or the fluent held before the action, and the action does not `cancel' it.''

In first-order logic, this knowledge is written as

forall a,s,p holds(p,do(s,a)) <-> causes(a,s,p) \/
[ holds(p,s) & ~cancels(a,s,p) ]

Only two more axioms are needed to describe the Yale shooting world:

forall a,s,p causes(a,s,p)    <->
       [ a=load & p=loaded] \/
       [ a=shoot & p=dead & holds(loaded,s)]
forall a,s,p cancels(a,s,p)    <->
       [ a=shoot & p=alive & holds(loaded,s)] \/
       [ a=shoot & p=loaded & holds(loaded,s)]