Elaboration tolerance

The Stanford Formal Reasoning Group is currently working on the logical approach to AI. Elaboration tolerance is one of our major research topics. Elaboration tolerance is a phrase introduced by McCarthy [MA96] to capture the notion that certain theories are more easily modified, while others are more brittle. The less brittle a theory is, the more easily it can be adapted to slightly different situations, the more elaboration tolerant the theory is. Obviously the simplest case of a modification is conjoining new information. Thus a theory that can capture a large variety of new phenomena by conjoining new information is more elaboration tolerant that one that cannot.

We have taken the well trodden missionaries and cannibals problem as our Drosophila.

Three missionaries and three cannibals come to a river and find a boat that holds two. If the cannibals ever outnumber the missionaries on either bank, the missionaries will be eaten.

The problem posed is ``How shall they cross?''. Consider the following elaborations:

1. One person can row the boat with one oar, but two oars are needed to carry two people. There is an oar on each bank of the river.
2. The missionaries can't row--We must then show that the problem is unsolvable.
3. There are four missionaries and four cannibals--This also makes the problem unsolvable.
4. Only one missionary and one cannibal can row.
5. If the biggest cannibal is isolated with the smallest missionary, the latter will be eaten.
6. There is an island--This permits solving the problem with an arbitrary number of missionaries and cannibals.

A human has no trouble with these elaborations, but when humans design formalisms for computer representation, usually the representation chosen precludes most of the elaborations without starting over completely. For the above problem, most programs will have to be changed top to bottom.

Amarel [Ama68] suggested the following representation of the problem. Every state is represented as a three tuple, the number of missionaries, cannibals and boats on the left hand side of the river. Thus the starting state is (3,3,1) and the final state if (0,0,0). If we wish to add the first elaboration, that there are also oars, we need to move to a four tuple--the number of missionaries, cannibals, boats and oars on the left side of the river.

This change is not a simply a piece of non-monotonic reasoning. We have changed more than just what we think the valid conclusions are, we have also changed the representation of the puzzle itself.

• Language Non-monotonicity