ResourceBounded 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 resourcebounded 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 realtime systems modularly from a library of reusable anytime algorithms. We have studied a range of research problems related to the construction, composition, and metalevel 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 "wellbehaved" anytime search algorithms, new ways to represent and measure computational tradeoffs, techniques for runtime 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), 12111217, 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(12):118, 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), 702706, 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(12):139157, 2001. [abs] [bib] [pdf]

Optimal Scheduling of Progressive Processing Tasks
S. Zilberstein and A.I. Mouaddib. International Journal of Approximate Reasoning, 25(3):169186, 2000. [abs] [bib] [pdf]

RealTime ProblemSolving with Contract Algorithms
S. Zilberstein, F. Charpillet, and P. Chassaing. Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence (IJCAI), 10081015, 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), 12681273, Stockholm, Sweden, 1999. [abs] [bib] [pdf]

A Heuristic Search Algorithm for Markov Decision Problems
E.A. Hansen and S. Zilberstein. BarIlan 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), 412418, 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 MetaLevel Control of Progressive
Processing
A.I. Mouaddib and S. Zilberstein. Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence (IJCAI), 12011207, Nagoya, Japan, 1997. [abs] [bib] [pdf]

Anytime Heuristic Search: First Results
E.A. Hansen, S. Zilberstein, and V.A. Danilchenko. Technical Report 9750, 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]

ResourceBounded Sensing and Planning in Autonomous Systems
S. Zilberstein. Autonomous Robots, 3:3148, 1996. [abs] [bib] [pdf]

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

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