Over the past several years, we have developed a successful technique for resource-bounded reasoning based on compilation and monitoring of anytime algorithms -- algorithms whose output quality improves gradually as computation time increases. The new framework has produced the first results that show how real-time systems can be modularly built from a library of reusable anytime algorithms. This project extends these results by examining a wide 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. Specific research questions include the construction of "well-behaved" anytime search algorithms, representation and measurement of computational tradeoffs, run-time assessment and prediction of solution quality, and run-time allocation of computational resources.

Related Publications

• 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, Edmonton, Alberta, Canada, 2002.

• Optimal Sequencing of Contract Algorithms
  S. Zilberstein, F. Charpillet, and P. Chassaing. To Appear in Annals of Mathematics and Artificial Intelligence, 2002.

• Monitoring and Control of Anytime Algorithms: A Dynamic Programming Approach
  E.A. Hansen and S. Zilberstein. Artificial Intelligence, 126(1-2):139-157, 2001.

• Optimal Scheduling of Progressive Processing Tasks
  S. Zilberstein and A.I. Mouaddib. International Journal of Approximate Reasoning, 25(3):169--186, 2000.

• Real-Time Problem-Solving with Contract Algorithms
  S. Zilberstein, F. Charpillet, and P. Chassaing. Proceedings of the 16th International Joint Conference on Artificial Intelligence, Stockholm, Sweden, 1999.

• Reactive Control of Dynamic Progressive Processing
  S. Zilberstein and and A. I. Mouaddib. Proceedings of the 16th International Joint Conference on Artificial Intelligence, Stockholm, Sweden, 1999.

• Optimal Sequencing of Contract Algorithms
  S. Zilberstein, F. Charpillet, and P. Chassaing. Bar-Ilan Symposium on the Foundation of Artificial Intelligence, Ramat Gan, Israel, 1999.

• A Heuristic Search Algorithm for Markov Decision Problems
  E. A. Hansen and S. Zilberstein. Bar-Ilan Symposium on the Foundation of Artificial Intelligence, Ramat Gan, Israel, 1999.

• Heuristic Search in Cyclic AND/OR Graphs
  E. A. Hansen and S. Zilberstein. Proceedings of the 15th National Conference on Artificial Intelligence, Madison, Wisconsin, 1998.

• Satisficing and Bounded Optimality
  S. Zilberstein. AAAI Spring Symposium on Satisficing Models, Stanford, California, 1998.

• Handling Duration Uncertainty in Meta-Level Control of Progressive Processing
  A. I. Mouaddib and S. Zilberstein. Proceedings of the 15th International Joint Conference on Artificial Intelligence, Nagoya, Japan, 1997.

• Anytime Heuristic Search: First Results
  E. A. Hansen, S. Zilberstein, and V. A. Danilchenko. Technical Report 97-xx, Computer Science Department, University of Massachusetts, 1997.

• Formalizing the Notion of "Satisficing"
  S. Zilberstein. AAAI Spring Symposium on Qualitative Preferences in Deliberation and Practical Reasoning, Stanford, California, 1997.

• Resource-Bounded Sensing and Planning in Autonomous Systems
  S. Zilberstein. Autonomous Robots, 3:31-48, 1996.

• Models of Bounded Rationality
  S. Zilberstein. AAAI Fall Symposium on Rational Agency, Cambridge, Massachusetts, 1995.

• Knowledge-Based Anytime Computation
  A. I. Mouaddib and S. Zilberstein. Proceedings of the 14th International Joint Conference on Artificial Intelligence, pp. 775-781, Montreal, Canada, 1995.