Tom Costello

Formal Reasoning Group Computer Science Department

Stanford University

  costello@cs.Stanford.EDU
http://www-formal.Stanford.EDU/tjc/

1997 March 27^{th}

Challenge problems

• Questions need to test the common-sense abilities of the HPKB’s.

• Small amounts of reasoning compared to planning/scheduling.

• ”The Italian terrorists know that Clinton has broken his leg”.

• Common-sense differentiates HPKB’s from the “next generation expert systems”.

Representation

• Can’t represent ⇒ Can’t use.

• More expressive formalisms

• time, change, concepts, hueristics, defaults • What makes formalisms better?

Challenge Problem Suggestions

• Current Slogan: Elaboration Tolerance

• Two types of elaboration, add new facts, or change ontology.

• Strawman: MYCIN—no concept of time. Time could not be added.

• Varying a parameter that was assumed fixed is a common elaboration.

• 1: Temporalize a static ontology/domain. Toy Example: Blocksworld. Real Example: Route Planning

Challenge Problem Suggestions

• Concepts can be split.

• 2: Three notions of height in aircraft, (above ground, above sea-level, barometric).

• Can a HPKB with a single notion be changed to allow these three versions?

Composing different ontologies/contexts

• To define functions on ontologies/contexts we need to describe relationships between inputs/outputs.

• A higher context is needed to state the relationship.

• Should not encode translation procedurally.

• There should be a context/set of sentences describing the relationship.

•

\begin{matrix}∀o, x.at(o, L) → ist(c_{sea level}, height(o) = −250 + x) ≡ \\ ist(c_{above ground}, height(o) = x) \end{matrix}

Relating different ontologies/contexts

• The relationships between objects in different ontologies are not always one to one or one to many.

• Narrative 1:

Junior goes to a store and buys a box of Kleenex.

• Narrative 2: Junior goes to the shelf, picks up a box of Kleenex, brings it to the counter and pays the cashier.

• Neither narrative contains the other.

Relating ontologies/contexts

• The

\begin{matrix}go(shelf); pickup(Klennex); \\ bring(Kleenex, Counter); pay(Kleenex, Cashier) \end{matrix}

sequence in the second narrative realizes the single buy(Kleenex) action.

• They are not the same however.

buy(Kleenex) ≠ \begin{matrix}go(shelf); pickup(Klennex); \\ Bring(Kleenex, Counter); \\ pay(Kleenex, Cashier) \end{matrix}

• Another possible realization.

realizes(buy(Kleenex),

go(Counter); ask(Clerk, Kleenex); pay(Kleenex, Cashier))

Categorizing Systems by Elaboration Tolerance

• Measure systems by what changes can be made to them linear in the size of the addition.

• Example: Effect axioms in the situation calculus only allow preconditions to be removed, not added. A robot arm can move a clear block to a clear location.

\begin{matrix}∀xll′s.clear(x, s) ∧ clear(l, s) ∧ at(x, l′, s) → \\ at(x, l′, move(x, l, l′, s)) \end{matrix}

A stronger robot arm could move stacks of blocks. The description of this implies the above sentence. It can be added to remove the precondition.

\begin{matrix}∀xll′s.clear(l, s) ∧ at(x, l′, s) → \\ at(x, l′, move(x, l, l′, s)) \end{matrix}

Need for Concepts/Qualitative Reasoning about Uncertainty

• DMIF: From radar etc. deduce tracks of vehicles

• HPKB: From tracks deduce purpose of movement, or intention of opponent.

• Qualitatively Different Problems

• Discovering strategies involves finding concepts.

• New use for defaults.

• Needs something different from probability with partial knowledge of the numbers.

• This is related to phenomenal data-mining.