A structured approach to real-time problem-solving
C.J. Paul · 1993
Real-time problem solving is not only reasoning about time, it is also reasoning in time. This is becoming increasingly critical in systems that monitor and control complex processes in semi-autonomous, ill-structured, real-world environments. Many techniques, mostly ad-hoc, have been developed in both the Real-Time and the Artificial Intelligence research communities for solving problems within time constraints. But a coherent, wholistic picture does not exist. This thesis is an attempt to step back from the details, and examine the entire issue of real-time problem solving from first principles. The basic premise of this thesis is that there exists a structured approach to real-time problem solving, based on the fundamental degrees of freedom available in using domain knowledge to reduce execution time variations due to search, and to structure the search space and the search process to produce best-so-far solutions in limited time. The degrees of freedom are examined at two levels of problem solving search--at the problem-level search space and the rule-retrieval level search space. Existing real-time problem solving techniques are shown to be compositions of these fundamental degrees of freedom. System level issues were considered in providing temporal isolation between conventional hard real-time tasks and real-time problem solving tasks executing on a common computing platform. An AI Server was developed to facilitate the integration of real-time problem solving tasks into hard real-time systems. A real-time problem solving architecture, Concurrent Real-Time OPS5 (CROPS5), and two applications were developed to validate some aspects of the approach. CROPS5 is a real-time production system architecture implemented in C, supporting multiple problem-solving streams, a fast and predictable context switch mechanism, global working memory and a data handler for interface to the environment. It runs on the Chimera II and ARTS real-time operating systems. CROPS5 was used to implement an aircraft collision avoidance application and a dynamic scheduling and pacing system for steel mills.