A framework for the analysis of sophisticated control
Robert C. Whitehair · 1996
This dissertation addresses problems associated with the lack of design theories for AI problem solving systems. The principle focus of the work is the introduction and demonstration of a framework for the analysis of sophisticated search control architectures applied in complex problem domains. The thesis associated with this work is that real-world problem domains and problem solving architectures can be represented formally and that these representations can be used to analytically predict and explain a problem solver's performance. Further, the implications of this work are that useful approximations and abstractions can be derived from such formal representations and used to design sophisticated control mechanisms. The ultimate objective of this work is to use these representations as the basis of design theories for building problem solving architectures and dynamic control algorithms. The framework is based on two formalisms, the Interpretation Decision Problem (IDP), which models both the structure of a problem domain and the structure of a problem solving architecture, and the UPC formalism, which provides a general quantitative model of search spaces that can be used in the analysis of problem solving control. Using these models, the problem structures of disparate domains and the problem solving architectures constructed to exploit these structures can be viewed from a unified perspective where control and problem solving actions can be considered a single class of problem solving activity. Models built from this unified perspective offer advantages for describing, predicting and explaining the behavior of blackboard-based interpretation systems and for generalizing a specific problem solving architecture to other domains. Use of the IDP and UPC formalisms also supports the synthesis of new, more flexible problem solving architectures. This dissertation demonstrates how the framework can be applied by analyzing a vehicle monitoring interpretation problem domain and associated problem solving architectures, including a heuristic, multi-level blackboard-based system. Definitions, examples, and experimental results are given for general structures from interpretation problem domains and blackboard-based problem solving architectures. Design principles for general problem solving strategies that exploit the structures are discussed.