University of Massachusetts Amherst
Department of Computer Science




Seminar in Resource-Bounded Reasoning

Fall 2002


Shlomo Zilberstein and Victor Lesser


Description: A central problem in artificial intelligence is how to develop computational models that allow decision-support systems or autonomous agents to react to a situation after performing the right amount of deliberation. Frequently, the complexity of problem solving makes it beneficial to use approximate solutions rather than try to compute the optimal answer. This seminar explores recently developed techniques to optimize the value of computation by replacing the basic components of a system with flexible methods that allow small quantities of computational resources, such as time, memory or information, to be traded for gains in the value of the results. The other aspect of resource-bounded systems is the ability to monitor progress and control the tradeoffs offered by the problem solver. Topics to be covered include: computational tradeoffs in inference, planning, and search; representation and measurement of computational tradeoffs; dependency of performance on problem instances; anytime algorithms and flexible computation; strategies for allocating resources among reasoning subproblems; myopic and non-myopic control; partitioning resources between meta-level and object-level reasoning; and applications of resource-bounded systems.

Meetings: Mondays, 1:25-3:25, CMPS 142

Prerequisites: An undergraduate artificial intelligence class or permission of instructors.

Shlomo Zilberstein,, 545-4189
Victor Lesser,, 545-1322

Requirements: Following introductory lectures by the instructors, we will discuss a few research papers in each meeting. The first half of the semester will be devoted to foundations, theoretical issues and algorithms. The second half will focus on the design of resource-bounded reasoning systems and applications. Each participant will be required to present and lead the discussion of selected papers. In addition, participants will be required to complete a project that may involve analysis and comparison of several resource-bounded reasoning techniques, or an implementation and evaluation of a particular approach, or an original research project solving an open problem in this area. Grades will be based on presentations, project report, and class participation.

© 2002 Shlomo Zilberstein.