[ CogSci Summaries home | UP | email ]
http://www.jimdavies.org/summaries/

Amarel, S. (1968). On representations of problems of reasoning about actions, Machine Intelligence, (3), 131--171

@InCollection{Amarel:1968,
  author =       "Saul Amarel",
  year =         "1968",
  title =        "On representations of problems of reasoning about
                 actions",
  booktitle =    "Machine Intelligence~3",
  editor =       "Donald Michie",
  publisher =    "Elsevier/North-Holland",
  address =      "Amsterdam, London, New York",
  volume =       "3",
  pages =        "131--171",
  note =         "\iindex{Amarel, S.}",
}

Author of the summary: David Furcy, 1999, dfurcy@cc.gatech.edu

Cite this paper for:

Summary

This paper can be summarized by this extracted sentence: "... the choice of appropriate representations is capable of having spectacular effects on problem solving efficiency" (p. 21, top right). Therefore, "... it is an important function of the problem solver to find the most appropriate representation for [...] its problem." (p. 19, bottom right). This paper investigates the choice of a good representation using the Missionaries and Cannibals (MC) problem as an example. This paper, however, does NOT provide any way of automating this analysis, which is performed by the author on paper. This is a worthwile first step, because "[i]n general, the problem of choosing a representation of [the] state space, and of discovering useful regularities in solution trajectories in this representation require much more study." (p21, middle left). Different ways of improving a representation (with respect to the efficiency its allows during problem solving) are explored in the context of the specific example (see below).

Detailed outline

This paper discusses 5 increasingly efficient representations for the MC problem. Starting from the initial formulation of the problem in English (F1), F2 is first built as the most intuitive way of formalizing the problem from F1, namely, using as many entities are there are people (missionaries plus cannibals), and the actions are (un)loading people into (from) the boat and crossing the river in both directions. The main constraints on the actions are the non-cannibalism condition (#m >= #c on each bank and on the boat) and the boat capacity. However, it can be easily proved that if the non-cannibalism property holds on the bank before and after a crossing, then it must also hold on the boat during the crossing. Therefore, it is unnecessary to consider the crossing itself. Consequently, F2 is simplified by considering as distinct states only situations where the boat is on one bank. The crossing is abstracted away and therefore there are only two types of actions needed, crossing from one bank to the other and vice-versa. Thus, one way to increase problem solving power is to eliminate redundant conditions and to reformulate the state space accordingly, i.e. reduction of the state space.

F2 is modified into F3 by realizing that it is not necessary to distinguish between individuals. For the purpose of the problem, whether M! and M2 and C1 are on the left bank is no different from M2 and M3 and C2 being on the left bank. The only thing that matters is the number of people of both types, not their identity. Thus, F3 represents a state by a simple vector of three numbers: {#M on the left bank, #C on the left bank and a flag (0/1) for the current position of the boat}. The solutions now amounts to finding a sequence of vector operations from say {3,3,1} to {0,0,0}.

Formulations F2 and F3 used systems of productions. In F4, a state becomes a problem state (P-state) of the form: {s1 => s2}, which means that s2 is attainable (e.g. provable) from s1 and s1 and s2 are vectors of F3. The initial P-state is: { {3,3,1} => {0,0,0} }. An operator consists of the application of (standard) operators to the left side of a P-state. E.g., P1 = { s1 => s2 } can transition to P2 = { s3 => s2 } if there exists an operator to go from s1 to s3. The reduction procedure stops when it reaches a P-state { s => s}. So far, this reduction approach is equivalent to the generative procedures of the previous formulations.

However, one can notice that solutions in F4 are symmetric with respect to time reversal. Therefore, a new formulation, F5 can be used to take advantage of this and to cut the search effort in two, except for some overhead in determining that the middle of the solution trajectory has been reached.

Finally in F6, a new, collapsed state space is proposed, namely a square matrix, in which the permissible territory (defined by the non-cannibalism constraint) is reduced to a Z-shaped region. After creating appropriate macro-actions to traverse this new space (i.e. traversing the horizontal bars and the diagonal and jumping from one to the other), a solution to the MC problem can be found with virtually no search at all.

In conclusion, ways of reducing the amount of search includes carefully choosing the level at which a state is defined (to reduce the number of states and possible actions), abstracting as much as possible, using macro-actions, and identifying/eliminating redundant conditions.

Summary author's notes:

Back to the Cognitive Science Summaries homepage
Cognitive Science Summaries Webmaster:
JimDavies ( jim@jimdavies.org )
Last modified: Thu Sep 23 13:08:18 EDT 1999