CSE 250A Lecture Notes, February 21, 2001

CSE 250A LECTURE NOTES

February 21, 2001

ANNOUNCEMENTS

I'm returning the second project reports today. Here are some general comments on them.

There will be a makeup lecture on Friday this week, and no lecture on Wednesday next week because I'll be away.

REPRESENTING HOW THE WORLD CHANGES

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.

Note that do(s_0,a) where a is an action is very similar to succ(0) in Peano arithmetic.

Fluents cannot be represented as predicates because they are not simply true or false. Rather, they are true in some states and false in others.

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

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

SYNTACTIC, SEMANTIC, AND TYPE ERRORS IN FIRST-ORDER LOGIC

Why do we have a fluent dead? Why not just use -alivewhere - is negation? Answer: it is a syntax error to apply the negation connective to anything that is not a sentence. Syntactically, alive is a constant-symbol, a special case of a term.

We can write an axiom sentence such as forall x holds(dead,x) <-> -holds(alive,x). In this axiom holds(alive,x) is syntactically a sentence so applying negation to it is well-formed.

The error of writing -alive in FOL is similar to the error of writing x++ in C where x is a floating point variable. The meaning may be intuitively clear, but formally speaking, the syntax is not allowed.

The syntax of FOL does not protect us from semantic errors or type errors.

Given the intended interpretation of dead and alive, this sentence is a semantic error: exists x holds(dead,x) & holds(alive,x).
The following sentence is a type error: holds(dead,do(s₀,loaded)), because loaded is a fluent, not an action, and the signature ofdois intuitively state x action -> state.

Research in knowledge representation has provided variants of FOL that include typing, but we won't discuss these other logics further here.

Note that type errors are somewhere in between syntactic and semantic errors. How an error is classified is somewhat arbitrary. In C, is writing x++ a type mismatch, or a syntax error?

THE YALE SHOOTING PROBLEM

This is the 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, 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.