Reference: Hayes-Roth, B. & Collinot, A. Scalability of Real-Time Reasoning in Intelligent Agents. Knowledge Systems Laboratory, Janury, 1991.
Abstract: An intelligent agent must interact with dynamic entities in real time. Because it cannot predict all events that will occur, it must notice and respond to important unanticipated events. However, insuring execution of the best possible operation at each point in time conflicts with meeting deadlines, especially as event rate and number of known operations increase. Rather than engineer agents to meet deadlines under particular parameter values, we aim to build agents whose real-time performance scales up over increases in parameter values. The scalability problem is: How can an agent with limited resources execute high-quality operations in bounded time, despite increases in event rate and number of known operations? We propose a satificing algorithm. To bound response time, it triggers on a limited number is operations and interrupts triggering to execute the best one available whenever it triggers a "good enough" operation or a deadline occurs. To insure that it can execute high-priority operations when interrupts occur, it uses dynamic control plans to trigger operations roughly "best-first." In this paper, we describe the satificing algorithm, informally analyze its behavior, and present experimental results.