Operational Rationality through Compilation of Anytime Algorithms

AI Magazine

How can an artificial agent react to a situation after performing the correct amount of thinking? My Ph.D. dissertation (Zilberstein 1993)2 presents a theoretical framework and a programming paradigm that provide an answer to this question.


Using Anytime Algorithms in Intelligent Systems

AI Magazine

Anytime algorithms give intelligent systems the capability to trade deliberation time for quality of results. This capability is essential for successful operation in domains such as signal interpretation, real-time diagnosis and repair, and mobile robot control. What characterizes these domains is that it is not feasible (computationally) or desirable (economically) to compute the optimal answer. This article surveys the main control problems that arise when a system is composed of several anytime algorithms. These problems relate to optimal management of uncertainty and precision. After a brief introduction to anytime computation, I outline a wide range of existing solutions to the metalevel control problem and describe current work that is aimed at increasing the applicability of anytime computation. The term anytime algorithm was coined by Dean and Boddy in the mid-1980s in the context of their work on time-dependent planning (Dean and Boddy 1988; Dean 1987).


Using Anytime Algorithms in Intelligent Systems

AI Magazine

Anytime algorithms give intelligent systems the capability to trade deliberation time for quality of results. This capability is essential for successful operation in domains such as signal interpretation, real-time diagnosis and repair, and mobile robot control. What characterizes these domains is that it is not feasible (computationally) or desirable (economically) to compute the optimal answer. This article surveys the main control problems that arise when a system is composed of several anytime algorithms. These problems relate to optimal management of uncertainty and precision. After a brief introduction to anytime computation, I outline a wide range of existing solutions to the metalevel control problem and describe current work that is aimed at increasing the applicability of anytime computation.


Deliberation in Equilibrium: Bargaining in Computationally Complex Problems

AAAI Conferences

We develop a normative theory of interaction-- negotiation in particular--among self-interested computationally limited agents where computational actions are game-theoretically treated as part of an agent's strategy. We focus on a 2-agent setting where each agent has an intractable individual problem, and there is a potential gain from pooling the problems, giving rise to an intractable joint problem. At any time, an agent can compute to improve its solution to its problem, its opponent's problem, or the joint problem. At a deadline the agents then decide whether to implement the joint solution, and if so, how to divide its value (or cost). We present a fully normative model for controlling anytime algorithms where each agent has statistical performance profiles which are optimally conditioned on the problem instance as well as on the path of results of the algorithm run so far. Using this model, we analyze the perfect Bayesian equilibria of the games which differ based on whether the performance profiles are deterministic or stochastic, whether the deadline is known or not, and whether the proposer is known in advance.


Metareasoning and Bounded Rationality

AAAI Conferences

What role does metareasoning play in models of bounded rationality? We examine the various existing computational approaches to bounded rationality and divide them into three classes. Only one of these classes significantly relies on a metareasoning component. We explore the characteristics of this class of models and argue that it offers desirable properties. In fact, many of the effective approaches to bounded rationality that have been developed since the early 1980's match this particular paradigm. We conclude with some open research problems and challenges.