CSE 150 Lecture Notes, February 10, 2004

CSE150 LECTURE NOTES

February 12, 2004

ANNOUNCEMENTS

The deadline for the reports for the current project is Friday this week, in section at 2pm. The deadline for the code is extended to Sunday at 8am, because we are late in publishing the detailed turn-in instructions. Sorry!

Please check your scores for the first assignment with GradeSource. Contact Piotr Dollar in case of concern, e.g. if we may have not found your report.

REASONING ABOUT ACTION

We write general knowledge about the three basic predicates "holds", "causes", and "cancels" 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)]

Some notes about this solution to the frame problem:

For each positive or negative effect of each action, we add one line to the causes or cancels axiom.
The fluent wait is axiomatized without mentioning it explicitly, because it has no effects.
Causing a fluent dominates canceling the same fluent.
An action whose preconditions are not satisfied can be performed, but it has no effect.

THE "ENTAILS" NOTATION

Suppose we write T |= A. The symbol |= is pronounced "entails."
This means that in every model of T, the sentence A is true. In other words, in every interpretation where each sentence of T is true, the sentence A is also true. For example:

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

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.

PLANNING PROBLEMS

Given information about the initial state, the planning task is to discover a sequence of actions such that certain fluents hold in the final state. Example: find P such that

T & holds(alive,s_0) |= holds(dead,P).

The answer is P = do(do(do(s_0,load),wait),shoot)

Solving a planning problem requires a logical reasoning system (i.e. a knowledge base manager or inference engine) that can return existential witnesses in addition to saying (yes, no, or unknown) whether or not a certain sentence is entailed by a given knowledge base.

Unfortunately, doing planning by general-purpose logical reasoning is just not efficient computationally.

The most successful planners today operate by translating a first-order knowledge base into propositional 3SAT clauses, then running a local search algorithm like WalkSat.

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.