next up previous
Next: CONCLUSIONS Up: The Heuristics Previous: Solution

Backtracking Actions

Backtracking actions are interesting for the study of reasoning strategies. The following axioms allow us to take into account backtracking actions within our formalization. Axiom gif describes two simple heuristics for determining the appropriateness of backtracking actions, i.e., for detecting dead-ends during the searching process. Backtracking actions are taken when: (1) the lengthgif of the mental situation explored is equal to some threshold N gif ; or (2) its length is smaller than N but there are no appropriate mental actions that can be applied to it.

  eqnarray258

   figure261
Figure: This figure illustrates the definition of Path(m) in axiom gif: tex2html_wrap_inline762 , tex2html_wrap_inline764 , tex2html_wrap_inline766 , and tex2html_wrap_inline768 .

It is possible to define more interesting heuristics for the appropriateness of backtracking actions, which detect early on unappropriate choices of the search strategy.

The path associated with a mental situation m describes the sequence of mental actions (including backtracking actions of the form Back) STRIPS needs to perform in order to find m (see figure gif for a graphical explanation).

   eqnarray270

Taking into account backtracking actions (i.e., including axioms gif, gif and gif) requires modifying the definition of goal stack derivation (axiom gif) as follows.

eqnarray279



Josefina Sierra
Tue Jul 21 09:26:01 PDT 1998