Problem Reduction Main Concepts of Problem Reduction Problematic Situations of the type (Io => Go) Set of NonTerminal Rules that transform problematic situations into two or more problematic situations that are presumed easier to solve than the original Set of Terminal Rules that completely resolve problematic situations Procedures for Control of Search, Move Application and Evaluation Pictorial Representation of Different Types and Patterns of Communication of Dependencies in a Partially Expanded Problem Reduction "And" Tree  The key to the right describes the various aspects of the "And" trees that are depicted. The term "SubArtifact" is used in place of the more usual term "situation". This term was chosen to emphasize the usefulness of the problem reduction architecture in design tasks as well as the more typical planning tasks. Note that we have distinguished three different sources of information about subproblem dependencies. The first source, depicted in blue, is termed "Declarative" to indicate that these are dependencies that are declared within the problem reduction rule that is applied to create the problem decomposition. The second source is termed "Plan-Derived" to indicate that these are dependencies discovered during the planning phase of the problem reduction method. Finally, "Solution-Derived Dependency" refers to dependencies that are discovered during the execution phase of the problem reduction method.      The tree above depicts the standard way in which subproblem dependencies are communicated in the a method of problem reduction where planning and execution are intimately linked as in the so-called linear planning methods. As terminal rules are encountered, the results are propagated to the parent nodes, but there is no explicit recognition of nor communication of subproblem dependencies beyond those declared in the non-terminal rules.      This next tree depicts the case where subproblem dependencies are explicitly recognized and communicated as a result of simulating the execution of the terminal rules that have been derived. In order to realize the advantage of this propagation of dependencies, the planning order must be the same as the execution order.     This final tree depicts the case where subproblem dependencies are explicitly recognized and communicated during the planning phase. In this case, these plan-derived dependencies can be recognized and communicated even if the planning order differs from the execution order. A paper entitled "On the Use of Problem Reduction Search for Automated Music Composition" is included to illlustrate the importance of these extensions to the method of problem reduction, partcularly in the area of design. Music composition provides an interesting point of comparison to the planning problems that are typically considered. A musical composition requires that the notes be linearly ordered for their execution (or performance). However, the notes themselves are typically grouped and the structure of the dependencies between these groups is typically quite articulated and nuanced. The "musical" example composed with the problem reduction system discussed in the paper is hardly interesting music. The "melody" composed by the system should be viewed as a kind of blocks-world problem. That is, the intent of the example is to help elucidate some of the important aspects of planning and complex design tasks.

	Planning - Table of Contents
© Charles F. Schmidt