In this paper, we have considered a particular planning problem in which the states of both the initial and goal situations are completely determined. Interesting reasoning about strategic knowledge is concerned with classes of problems, instead of particular instances. The representation scheme and reasoning method proposed have however a broader scope. They can also be applied to entire classes of problems, provided these classes of problems are appropriately axiomatized.
The point of focusing on the study of a particular example was to illustrate potential applications of reasoning about declarative formalizations of strategies in a simple setting. We have seen, for example, that the techniques presented are useful to determine the computability and correctness of a particular strategy (or a class of strategies) with respect to a given problem (or a class of problems). We have also considered issues involved in updating and composing strategic knowledge from different sources, such as determining whether a set of heuristics improve, are inconsistent or redundant with a particular strategy (or a class of strategies). The possibility of reasoning about these issues, together with the natural compositionality of the declarative formalization of strategies proposed, allow a program to reflect on its own behavior, and improve its problem solving strategy by simple additions or substitutions of sentences, much in the same way it happens in natural language. This is perhaps the best feature of the language, its elaboration tolerance [McCarthy1988]. The flexibility of adapting smoothly to conceptual changes in the specification of a problem or its solution is a very important feature that procedural or dynamic logic languages do not have.
There are a number of interesting issues about the declarative formalization of strategies we have not considered. We have formalized only state-based strategies. An important number of strategies depend on chronological information, such as whether an action has been selected at a particular situation. The related problem of formalizing control information in the situation calculus is addressed by [Lin1997]. Derivations in logic programming are identified with situations, and a fluent accessible is defined in order to characterize those situations which correspond to derivations of Prolog programs including cut. Our work differs from [Lin1997] in two aspects: (1) the emphasis on representation, in particular, on proposing a representation scheme for the declarative formalization of strategies; and (2) the use of non-monotonic reasoning to achieve elaboration tolerance and reflection.
Planning is one of the most challenging problems. Humans are sometimes able to come up with heuristics such as those formalized here. A deeper understanding of a domain may allow programs to come up with them as well. Issues such as the safeness and postponability [McCarthy1990a] of certain actions and situations, with respect to the achievement of certain goals, underly the design of the heuristics formalized for the blocks world. Our hypothesis is that these issues may play a crucial role in the problem of automating the design of heuristics, which we have only begun to investigate.