Resource-Bounded Reasoning
Shlomo Zilberstein
Course Description
Resource-bounded reasoning is an emerging field within artificial
intelligence that addresses one of its primary challenges: how to embed
complex reasoning components in real-world applications. The need to
employ resource-bounded reasoning techniques is based on a simple, but
general, observation. In many situations, the computational resources
required to reach an optimal decision reduce the overall utility of the
result. This observation covers a wide range of applications such as
automated diagnosis and treatment, signal interpretation, combinatorial
optimization, probabilistic inference, mobile robot navigation, visual
tracking, graphics, and information gathering. What is common to all
these problems is that it is not feasible (computationally) or desirable
(economically) to compute the optimal answer.
Moreover, taking the cost of computation into account is not an easy
task, since the "optimal" level of deliberation varies from situation to
situation.
A multitude of resource-bounded reasoning techniques have been developed
in recent years exploiting new computational techniques that allow small
quantities of computational commodities-such as time, memory, or
information-to be traded for gains in the value of computed results.
This tutorial will examine the benefits and limitations of recently
developed techniques including anytime algorithms, flexible computation,
memory-bounded search, imprecise computation, and design-to-time
scheduling. Topics which will be covered include: introduction and
historical background, types of computational tradeoffs in reasoning and
search, representation and measurement of computational tradeoffs,
embedding flexible computation components in large systems, run-time
assessment and prediction of solution quality, monitoring and control of
computational resources, performance evaluation of resource- bounded
reasoning systems, a brief survey of successful applications, and
current research directions.
This tutorial is designed for both researchers interested in fundamental
issues in resource- bounded reasoning and practitioners with a primary
interest in applications. The tutorial will be self-contained and
requires basic familiarity with AI (search and automated reasoning) and
probability theory.
About the Lecturers
Shlomo Zilberstein
is an Assistant Professor of Computer Science and the head of the
Resource-Bounded Reasoning Research Group at the University of
Massachusetts. He received his BA in Computer Science (1981) from Israel
Institute of Technology summa cum laude, and his Ph.D. in Computer
Science (1993) from the University of California at
Berkeley. Prof. Zilberstein has 15 years of experience in research and
development of real-time intelligent systems. He has published numerous
articles on resource-bounded reasoning and has presented his work at
major conferences. He has also organized several successful workshops in
this area including the IJCAI- 95 Workshop on Anytime Algorithms and
Deliberation Scheduling, the 1996 AAAI Fall Symposium on Flexible
Computation, and the AAAI-97 Workshop on Building Resource- Bounded
Reasoning Systems.
higuchi@etl.go.jp
Last modified: Thu Feb 20 13:55:55 JST 1997