This project is aimed at developing a decision-theoretic approach to building intelligent systems that can perform robustly a variety of real-time tasks. In performing such tasks as medical diagnosis, job scheduling, and robot navigation, the computation time required to select optimal actions degrades the system's overall utility. Therefore, such systems should be able to trade off decision quality for the cost of deliberation.

Over the past several years, work by Dean, Horvitz, Russell, Zilberstein and others has shown that anytime algorithms are a useful tool for real-time system design, since they allow computation time to be traded for decision quality. In order to construct complex systems, however, one needs to be able to compose larger systems from smaller, reusable anytime modules. Our solution to this problem is based on novel off-line compilation process and run-time monitoring that can maximize the overall utility of the system. The project covers the problem of constructing anytime algorithms, representation and manipulation of conditional performance profiles, and development of efficient compilation and monitoring procedures for systems composed of anytime algorithms.

Related Publications

• Using Anytime Algorithms in Intelligent Systems
  S. Zilberstein. AI Magazine, 17(3):73-83, 1996.

• Monitoring the Progress of Anytime Problem-Solving
  E. A. Hansen and S. Zilberstein. Proceedings of the 13th National Conference on Artificial Intelligence, pp. 1229-1234, Portland, Oregon, 1996.

• Optimal Composition of Real-Time Systems
  S. Zilberstein and S. J. Russell. Artificial Intelligence, 82(1-2):181-213, 1996.

• Optimizing Decision Quality with Contract Algorithms
  S. Zilberstein. Proceedings of the 14th International Joint Conference on Artificial Intelligence, pp. 1576-1582, Montreal, Canada, 1995.

• Approximate Reasoning Using Anytime Algorithms
  S. Zilberstein and S. J. Russell. In S. Natarajan (Ed.), Imprecise and Approximate Computation, Kluwer Academic Publishers, 1995.

• Operational Rationality through Compilation of Anytime Algorithms
  S. Zilberstein. Ph.D. dissertation, Computer Science Division, University of California at Berkeley, 1993.

• Efficient Resource-Bounded Reasoning in AT-RALPH
  S. Zilberstein and S. J. Russell. Proceedings of the First International Conference on AI Planning Systems, pp. 260-266, College Park, Maryland, 1992.

• Composing Real-Time Systems
  S. J. Russell and S. Zilberstein. Proceedings of the Twelfth International Joint Conference on Artificial Intelligence, pp. 212-217, Sydney, Australia, 1991.