Analysis and design of on-line decision-making solutions for time-critical planning and scheduling under uncertainty
Lloyd G. Greenwald · 1997
This thesis addresses the problems of designing a system to interact with a dynamic, uncertain environment such that the system must make quick decisions about how to respond to situations in the environment, yet has limited on-line time and space resources to employ in decision making. We provide methods for understanding the inherent tradeoffs in this design problem, and for evaluating how various design-time choices impact execution-time behavior. The class of problems in which these tradeoffs arise includes those of time-critical planning and scheduling under uncertainty. This dissertation conceptually models on-line decision making as a hierarchical storage problem, and formulates and analyzes on-line decision-making solutions as time-critical control systems with specific time/space tradeoffs. Time/space tradeoffs are evaluated with respect to a characterization of predictable temporal patterns in the interaction of control system and environment. These patterns capture design-time understanding of short-term and long-term interactions in which later situations of the environment are dependent upon earlier actions of the control system. The utility of the framework of this thesis is demonstrated through the development of a new approach to the design and analysis of real-time avionics systems. This approach may be generalized to posing and solving a variety of scheduling problems in hard real-time environments under uncertainty. The practical application of the framework and techniques of this thesis is evaluated through the development and implementation of a careful empirical study. This study provides evidence of the practicality of the design-time analytical techniques of this thesis with respect to the design and analysis of real-time avionics systems.