CSE 250A Lecture Notes, February 23, 2001

CSE 250A LECTURE NOTES

February 23, 2001

ANNOUNCEMENTS

Today's handout is Local search characteristics of incomplete SAT procedures by Dale Schuurmans and F. Southey, from Proceedings of the Seventeenth National Conference on Artificial Intelligence (AAAI-2000).

Next Monday I will hand out the description of the fourth and last project.

Next quarter, CSE 254 will meet on Mondays and Wednesdays, from 10:10am to 11:30am. This will be a Ph.D. level seminar on learning algorithms. CSE 250B will not be offered this year.

THE YALE SHOOTING PROBLEM

Some obvious axioms for the Yale shooting 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

In general, in a domain with a different actions and f fluents O(a*f) axioms are 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)]

Note that causing a fluent dominates canceling the same fluent, and an action whose preconditions are not satisfied has no effect.

KNOWLEDGE REPRESENTATION AND PHILOSOPHY

The general axiom above involving causes, cancels, and holds is a limited but formal theory of causation. The branch of philosophy known as analytic philosophy deals with understanding the basic concepts of everyday discourse, such as causation. Many of these concepts, including causation, have been excluded from most of science, because they are too complex and mysterious, i.e. resistant to formalization. Work in AI cannot avoid everyday concepts like causation because any artificial agent that communicates with humans must be able to use the concepts that humans naturally use.

In analytic philosophy and in knowledge representation, the most important choice is precisely what vocabulary to use, i.e. what ontology to adopt. This choice makes the actual statement of a theory easy or difficult. Given a vocabulary item like the predicate causes for a relationship, it is vital to understand exactly what arguments the relationship involves: what its arity is, and what semantic category each argument falls into.

Here, it is critical that we conceptualize causes as a three-way relationship between an action, a context, and an fluent. In everyday discourse we often forget that causation is not a two-way relationship between a 'cause' (i.e. an action) and an 'effect' (i.e. a fluent). In fact, a particular action can have different effects in different contexts, i.e. in different states of the world. In order to have any chance of capturing this knowledge, we must formalize causes, and also cancels, as a predicate with three arguments.

REASONING FORWARDS AND BACKWARDS IN TIME

Let T be the set of three axioms stated above. The original shooting problem is solvable:

T & holds(alive,s_0) |= holds(dead,do(do(do(s_0,load),wait),shoot)).

Suppose the turkey is known to be alive originally, but a shot was heard and the turkey was seen dead some time later. Whodunit? This murder mystery is also solvable:

T & holds(alive,s_0) & ~holds(alive,do(do(s_0,shoot),wait))
|= holds(loaded,s_0) & cancels(shoot,s_0,alive)

The frame axiom says that miracles never happen: if a fluent holds, then it must have just been caused by some action, or else it must have held immediately previously, and not been canceled.