IJCAI-97 TUTORIALS

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.

Prerequisite Knowledge

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