Resource-Bounded Reasoning in Intelligent Systems

Sponsored by:
National Science Foundation, Division of Information & Intelligent Systems

Shlomo Zilberstein, PI

Project Description

This project is concerned with the development of techniques for resource-bounded reasoning based on compilation and monitoring of anytime algorithms -- algorithms whose output quality improves gradually as computation time increases. This project has produced an effective framework for building real-time systems modularly from a library of reusable anytime algorithms. We have studied a range of research problems related to the construction, composition, and meta-level control of computational methods that allow small quantities of resources, such as time, memory, or information, to be traded for gains in the value of computed results. The outcomes of the project include new ways to create "well-behaved" anytime search algorithms, new ways to represent and measure computational tradeoffs, techniques for run-time assessment and prediction of solution quality, and ways to optimize the allocation of computational resources in systems composed of anytime algorithms.

Related Publications

  • Contract Algorithms and Robots on Rays: Unifying Two Scheduling Problems.

    D.S. Bernstein, L. Finkelstein, and S. Zilberstein. Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence (IJCAI), 1211-1217, Acapulco, Mexico, 2003. [abs] [bib] [pdf]

  • Optimal Sequencing of Contract Algorithms.

    S. Zilberstein, F. Charpillet, and P. Chassaing. Annals of Mathematics and Artificial Intelligence, 39(1-2):1-18, 2003. [abs] [bib] [pdf]

  • Scheduling Contract Algorithms on Multiple Processors

    D.S. Bernstein, T.J. Perkins, S. Zilberstein, and L. Finkelstein. Proceedings of the Eighteenth National Conference on Artificial Intelligence (AAAI), 702-706, Edmonton, Alberta, Canada, 2002. [abs] [bib] [pdf]

  • Monitoring and Control of Anytime Algorithms: A Dynamic Programming Approach

    E.A. Hansen and S. Zilberstein. Artificial Intelligence, 126(1-2):139-157, 2001. [abs] [bib] [pdf]

  • Optimal Scheduling of Progressive Processing Tasks

    S. Zilberstein and A.I. Mouaddib. International Journal of Approximate Reasoning, 25(3):169-186, 2000. [abs] [bib] [pdf]

  • Real-Time Problem-Solving with Contract Algorithms

    S. Zilberstein, F. Charpillet, and P. Chassaing. Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence (IJCAI), 1008-1015, Stockholm, Sweden, 1999. [abs] [bib] [pdf]

  • Reactive Control of Dynamic Progressive Processing

    S. Zilberstein and and A.I. Mouaddib. Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence (IJCAI), 1268-1273, Stockholm, Sweden, 1999. [abs] [bib] [pdf]

  • A Heuristic Search Algorithm for Markov Decision Problems

    E.A. Hansen and S. Zilberstein. Bar-Ilan Symposium on the Foundation of Artificial Intelligence (BISFAI), Ramat Gan, Israel, 1999. [abs] [bib] [pdf]

  • Heuristic Search in Cyclic AND/OR Graphs

    E.A. Hansen and S. Zilberstein. Proceedings of the Fifteenth National Conference on Artificial Intelligence (AAAI), 412-418, Madison, Wisconsin, 1998. [abs] [bib] [pdf]

  • Satisficing and Bounded Optimality

    S. Zilberstein. AAAI Spring Symposium on Satisficing Models, Stanford, California, 1998. [abs] [bib] [pdf]

  • Handling Duration Uncertainty in Meta-Level Control of Progressive Processing

    A.I. Mouaddib and S. Zilberstein. Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence (IJCAI), 1201-1207, Nagoya, Japan, 1997. [abs] [bib] [pdf]

  • Anytime Heuristic Search: First Results

    E.A. Hansen, S. Zilberstein, and V.A. Danilchenko. Technical Report 97-50, Computer Science Department, University of Massachusetts Amherst, 1997. [abs] [bib] [pdf]

  • Formalizing the Notion of "Satisficing"

    S. Zilberstein. AAAI Spring Symposium on Qualitative Preferences in Deliberation and Practical Reasoning, Stanford, California, 1997. [abs] [bib] [pdf]

  • Resource-Bounded Sensing and Planning in Autonomous Systems

    S. Zilberstein. Autonomous Robots, 3:31-48, 1996. [abs] [bib] [pdf]

  • Models of Bounded Rationality

    S. Zilberstein. AAAI Fall Symposium on Rational Agency, Cambridge, Massachusetts, 1995. [abs] [bib] [pdf]

  • Knowledge-Based Anytime Computation

    A.I. Mouaddib and S. Zilberstein. Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence (IJCAI), 775-781, Montreal, Canada, 1995. [abs] [bib] [pdf]

shlomo@cs.umass.edu
UMass Amherst