For an updated CIRCA website, go here.
Kang G. Shin, Professor of EECS
Ella Atkins, Graduate Student
Chip McVey, Graduate Student
Eric Miller, MS, now at Loral.
E. M. Atkins, E. H. Durfee, K. G. Shin, Expecting the Unexpected: Detecting and Reacting to Unplanned-for World States, Proceedings of AAAI-96, pp. ????, August 1996. (student abstract)
E. M. Atkins, E. H. Durfee, K. G. Shin, Detecting and Reacting to Unplanned-for World States, AAAI-96 Workshop on Theories of Action, Planning, and Robot Control: Bridging the Gap, pp. 7-14, August 1996.
E. M. Atkins, E. H. Durfee, K. G. Shin, Building a Plan with Real-Time Execution Guarantees, AAAI-96 Workshop on Structural Issues in Planning and Temporal Reasoning, pp. 1-6, August 1996.
E. M. Atkins, E. H. Durfee, K. G. Shin, Detecting and Reacting to Unplanned-for World States, to appear in AAAI-96 Fall Symposium on Plan Execution: Problems and Issues Technical Report, November 1996.
E. M. Atkins, E. H. Durfee, K. G. Shin, Achieving Fully-Automated Aircraft Flight with Limited Resources, to appear in AAAI-96 Fall Symposium on Flexible Computation in Intelligent Systems: Results, Issues, and Opportunities Technical Report, November 1996.
D. J. Musliner, J. A. Hendler, A. K. Agrawala, E. H. Durfee, J. K. Strosnider, and C. J. Paul, The Challenges of Real-Time AI, IEEE Computer, Vol 28 #1, January 1995. Also appears as University of Maryland Technical Report CS-TR-3290 (UMIACS-TR-94-69).
D. J. Musliner, Using Abstraction and Nondeterminism to Plan Reaction Loops, Proc. National Conf. on AI, pp. 1036-1041, Seattle WA, August 1994.
D. J. Musliner, Predictive Sufficiency and the Use of Stored Internal State, in Proc. Conf. on Intelligent Robotics in Field, Factory, Service, and Space, pp. 298-305, Houston TX, March 1994.
D. J. Musliner, E. H. Durfee, and K. G. Shin, World Modeling for the Dynamic Construction of Real-Time Control Plans, to appear in AI Journal, 1994.
D. J. Musliner, K. G. Shin, and E. H. Durfee, Automating the Design of Real-Time Reactive Systems, in Proc. Symposium on AI in Real-Time Control, 1994.
D. J. Musliner, E. H. Durfee, and K. G. Shin, CIRCA: A Cooperative Intelligent Real-Time Control Architecture IEEE Transactions on Systems, Man, and Cybernetics, Vol 23 #6, 1993.
D. J. Musliner, CIRCA: The Cooperative Intelligent Real-Time Control Architecture Ph.D. Thesis, The University of Michigan, Ann Arbor, MI, 1993.
D. J. Musliner, E. H. Durfee, and K. G. Shin, Integrating Intelligence and Real-Time Control into Manufacturing Systems, Working Notes of the SIGMAN Workshop on Intelligent Manufacturing Technology, July 1993.
D. J. Musliner, E. H. Durfee, and K. G. Shin, Any-Dimension Algorithms , in Proc. Workshop on Real-Time Operating Systems and Software, May 1992.
D. J. Musliner, E. H. Durfee, and K. G. Shin, Reasoning About Bounded Reactivity to Achieve Real-Time Guarantees, in Proc. AAAI Spring Symposium on Selective Perception, March 1992.
D. J. Musliner, E. H. Durfee, and K. G. Shin, Execution Monitoring and Recovery Planning with Time, in Proc. Conf. on Artificial Intelligence Applications, February 1991.
Edmund H. Durfee and Victor R. Lesser. Incremental Planning to Control a Time-Constrained, Blackboard-Based Problem Solver. IEEE Transactions on Aerospace and Electronic Systems, special issue on space telerobotics, 24(5):647-662, September 1988.
Victor R. Lesser, Jasmina Pavlin, and Edmund H. Durfee. Approximate Processing in Real-Time Problem Solving. AI Magazine, Vol. 9, No. 1, pages 49--61, Spring 1988.
Edmund H. Durfee. Towards Intelligent Real-Time Cooperative Systems. In AAAI Spring Symposium on Planning in Uncertain, Unpredictable, or Changing Environments , pages 29--33, Stanford, CA, March 1990.
Hard-wired control schemes using fixed algorithms are amenable to such performance analysis, but cannot address high-level problems such as reasoning about goals, resource restrictions, and recovery from unexpected failures. Unfortunately, many of the AI techniques and heuristics developed to solve these high-level problems are not suited to analyses that would provide guaranteed response times. For example, systems that learn are able to form new chains of inferences, resulting in changing performance characteristics that may defy worst-case bounding. Even when AI techniques can be shown to have predictable response times, the variance in these response times is typically so large that providing timeliness guarantees based on the worst-case performance would result in severe underutilization of the computational resources during normal operations.
Thus we perceive an apparent conflict between the nature of AI and the needs of real-world, real-time control systems. While AI methods are characterized by unpredictable or high-variance performance, real-time control systems require constant, predictable performance. Most research on ``real-time AI'' (RTAI) focuses either on restricted AI techniques that have predictable performance characteristics or on reactive systems that retain little of the power of traditional AI.
The AI Lab and the Real-Time Computing Lab are cooperating on a new branch of RTAI research here at the University of Michigan. To combine unrestricted AI techniques with the ability to make hard performance guarantees, we are investigating a Cooperative Intelligent Real-Time Control Architecture (CIRCA). In this architecture, an AI subsystem reasons about task-level problems that require its powerful but unpredictable reasoning methods, while a separate real-time subsystem uses its predictable performance characteristics to deal with control-level problems that require guaranteed response times. The key difficulty with this approach is allowing the subsystems to interact without compromising their respective performance goals. We have developed a scheduling module and a structured interface that allow the unconstrained AI subsystem to asynchronously direct the real-time subsystem without violating any response-time guarantees.
Realistic intelligent control systems must recognize their resource limitations and make tradeoffs in the quality of their control outputs, or responses. Many systems recognize resource limitations and trade off the precision, confidence, or timeliness of their responses. CIRCA extends this mechanism by allowing the system to explicitly trade off the completeness of its responses. CIRCA's AI subsystem and scheduler cooperatively reason about the real-time subsystem's execution resources, and choose a subset of responses that the real-time subsystem will guarantee. By manipulating the responses that the real-time subsystem is guaranteeing, the AI subsystem attempts to ensure that the real-time subsystem will meet hard deadlines and also achieve the overall system goals. CIRCA also provides mechanisms to utilize the time which becomes available when guaranteed mechanisms use less than their worst-case scheduled time allowance.
To achieve flexible control, CIRCA requires that the AI methods reason about the expected real-time demands of the environment and build control plans to guarantee meeting those demands. CIRCA does this using a formal graph-based model of agent/environment interactions, exploring a space of states that the system could be in due to its own actions, due to external events, and due to the passage of time. In constructing control plans, CIRCA determines what actions it must guarantee to take and how often it will be able to take them to ensure that the system does not enter a state where it could transition into failure (due to the passage of time). Currently, CIRCA is able to develop such control plans when possible, and when not possible CIRCA provides well-defined transformations to the graph model (based predominantly on eliminating or extending various types of transitions) that allow it to systematically relax requirements until it can guarantee the performance of a control plan. Our ongoing work is investigating how to choose from among candidate transformations to yield the best possible control plan. We are also investigating improved scheduling techniques for efficiently generating guaranteed control plans, using internal state in the real-time subsystem to reduce costly sensory actions, and strategies for transitioning among control plans. Application domains for CIRCA include manufacturing process control and mobile robotics.