Resource-Bounded Reasoning in Intelligent Systems
Shlomo Zilberstein, PI
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.
- 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.
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
- Optimal Scheduling of Progressive Processing Tasks
- Real-Time Problem-Solving with Contract Algorithms
- Reactive Control of Dynamic Progressive Processing
- A Heuristic Search Algorithm for Markov Decision Problems
- Heuristic Search in Cyclic AND/OR Graphs
- Satisficing and Bounded Optimality
- Handling Duration Uncertainty in Meta-Level Control of Progressive Processing
- Anytime Heuristic Search: First Results
- Formalizing the Notion of "Satisficing"
- Resource-Bounded Sensing and Planning in Autonomous Systems
- Models of Bounded Rationality
- Knowledge-Based Anytime Computation