Automatic Discovery of Heuristics for Nondeterministic Programs

1. INTI<ODUCTION

During the last few years, a number of relative­ ly effective Artificial Intelligence programs have been written incorp9rating considerable amounts of knowledge, and the problem of encod­ ing such knowledge in a useful form has emerged as one of the central problems of AI. Recently, attention has turned towards mechanisms which facilitate incorporating limited procedural or heuristic information into a primarily declara­ tive framework (for example, Rychener's approach [4] is to build. a rational "goal" structure into declarative rule-based systems, while Davis [2] favors a separate set of "meta­ rules", specifying control information). The problem of acquiring, debugging and extending control information has become increasingly important. We believe that there are a number of important areas in which it might be possible to deduce control information automatically from a declarative program. These include declaratively specified problems: (1) for which there exists a relatively simple algorithmic procedure·, or (2) whose performance can be improved in frequently occurring or particularly important special cases; or (3) in which parti­ cular subproblems can be solved by simple algorithmic procedures. This problem has been discussed by a number of previous workers in various forms (for example [1,3,7]); space does not permit a complete review here (see [5] for such a review and comparisons with the present work).

*This material is based upon work supported by the Office of Naval Research under Contra~t No. N00014-75-C-0571, (NR049-347).

2. APPI<OACH

In our experiments, we have been working on a (slightly idealized) jigsaw puzzle, in which each piece has an average color, and four sides described by unique integers (with side i fit­ ting side -i). A nondeterministic algorithm written in production language form for this problem can be found in [6).

The representation contains 33 productions, and is highly nondeterministic, and if executed would be hopelessly inefficient. It does not even "know" that it will find a solution (i.e. terminate) if it can repeat the production which puts a piece in the puzzle as frequently as possible, so even the crudest goal-subgoal structure is absent. (However, there is no production to remove a piece from the puzzle, which serves as a clue to an intelligent observer) · It is even possible for the program to pick up a piece and then put it down immedi­ ately without doing anything with it.

However, sufficient productions are present to permit simple sequencing heuristics to reflect the usual strategies used by experi-

anced puzzle-solvers:

• o work on the outside edges first (build a pile of outside edges); repeat the put-piece-in­ puzzle sequence until this pile is empty;
• 0 separate the pieces in the heap into piles of the same average color, and search the appropri­ ate pile first;
• o search first for pieces which have more than one neighbor of the same average color (e.g. work on the sky first);

It may appear that automatic detection of such heuristics is a task of great difficulty. Below we outline an approach to this problem which appears to be quite successful, describe a system which has been embedded in a production system language and give some experimental results.

Our prQcedure is as follows: we select a 'typical' input to the program and run the pro­ gram repeatedly on this input, recording the sequence of rules selected. This is repeated for other typical inputs. We then attempt to describe the better (i.e. shorter) successful sequences in a language, CRAPS, designed for this purpose and described in the next section. We then use this description to guide the pro­ gram's subsequent decisions. The analysis of the solution sequences also produces a set of meta-rules which are used to dynamically alter the sequencing in the event the description does not behave properly.

Inherent in this approach is the assumption that good decision-making procedures or heuristics can be inferred from the performance of the program on only selected inputs. In general, as suggested by work on inductive inference and information theory, we give preference to short CRAPS descriptions which will generate a high proportion of short successful solutions and few long or unsuccessful solutions. We .anticipate that the selection of inputs will be critical and that eventually we will want to be able to handle new inputs incrementally. Initially, however, we have concentrated on the simpler problem of getting a good solution for the non­ incremental case.

As suggested by sample experiments, the execu­ tion time of a completely declarative program will usually be too long to permit a solution except in the simpler cases. Accordingly, we run the program in "training mode" in which its decisions can be observed and if necessary corrected. In initial experiments this was done by a trainer who was aware of the structure of the program; subsequently we anticipate the necessity of using techniques similar to those of Davis [2], which will enable the trainer to deal only with the external behavior of the program.

It should be noted that we have deliberately chosen to exclude information about sequences which end in failure. It is clear that, as found by Winston [8], counterexamples will be extremely valuable. However, as the reader will note below, even this simpler problem poses considerable technical difficulties, and it was our feeling that a clearer picture would emerge from the simpler approach. Furthermore, the experiments suggest that useful results can be obtained without counterexamples.

3. THE CRAPS LANGUAGE

The CRAPS language provides a semantic framework with which to specify or describe sequences of rule applications in the execution of the non­ deterministic program. The operators of CRAPS are Concatenation, Repetition, Alternation and Permutation of Sequences, with enabling condi­ tions which are DNF expressions of rule applicability. Concatenation corresponds to sequential execution of statements, and repeti­ tion corresponds to iteration statements with 'while' and 'until' termination conditions. The alternation operator specifies alternative sequences of actions much like an ALGOL-68 'case' statement or LISP 'cond' expression. The permutation primitive represents a form of con­ current execution similar to the specification of collateral expressions in ALGOL-68.

The algorithms which compile CRAPS descriptions are based on standard optimization techniques and divide and conquer pattern recognition algo­ rithms. The input to the program consists of a sequence composed of the rules which were fired on each cycle together with the associated input/output information and the list of rules which were applicable on each cycle. The analy­ sis also produces a set of meta-rules whose objective is to suggest productions to fire in the event the CRAPS description is inappropri­ ate. Complete details of these algorithms can be found in [5,6].

4. EXPERIMENTS

The experiments were performed on 5 puzzles with 25-30 pieces. Over 400 productions were fired to solve a puzzle. The CRAPS description generated from a training session using one puzzle consisted of 75 concatenations and 15

repetitions. A total of 192 meta-rules were generated. The original puzzle used in the training session was easily solved using the CRAPS description; no meta-rules were needed. The second puzzle was solved in 10 1/2 minutes but r equired 5 meta-rule calls. The third puzzle failed to be solved because of an incorrect choice specified by the meta-rules afte r 193 cycles. A fourth puzzle was solved in 11 1/2 minutes with one meta-rule call. A fifth puzzle was run with the meta-rules alone and it failed to make correct decisions after 80 successful cycles were executed. Complete det~ils of these experiments can be found in [5~

5. CONCLUSION

It is believed by many researchers that an important quality of intelligent behavior is the ability to improve performance with experience, and that generalizing a concept is a critical aspect of learning. In CRAPS, a form of gener­ alization occurs when a repeating subsequence is collapsed into a repetition. Although quite restricted in scope, CRAPS shows how a system might learn procedures, a form of learning which we believe is very important. Although there are a number of very difficult technical problems, it seems to us that with more powerful pattern recognition techniques and more powerful generalizations of control statements, this approach could be very fruitful.

With less ambitious designs, CRAPS can be viewed as a programming aid for the designer and implementer of a large AI problem-solving knowledge base. The CRAPS approach might be useful in fine-tuning a declarative knowledge base as opposed to 'hand~compiling' control elements to effect competent performance in such a system.

The power of the descriptions produced is limited by both the expressive power of the CRAPS primitives, and the level of sophistica­ tion of the pattern recognition algorithms that have been developed. For example, during repe­ tition detection no notion of similar subsequence is used; furthermore, it is not poss ible ·for alternation to appear within repe­ titions. Despite this, the algorithms are powerful enough to detect interesting patterns and subsequently interesting heuristics.

Our expe riments suggest that this approach will have the best chance o f success when the encod­ ing of the knowledge of the problem domain is such that on any execution cycle a small number of productions and only one instantiation of e ach production is applicable. This suqgests one way in which CRAPS should evolve: the execution traces should include not only produc­ tions but also the instantiations of produc ­ tions (i.e. contextual or even goal information should be included). However, recognizing patterns in such sequences is much more diffi­ cult. We view our approach as an initial step in the understanding of this more general problem.