Operational Rationality through Compilation of Anytime Algorithms

Shlomo Zilberstein. Operational Rationality through Compilation of Anytime Algorithms. Ph.D. dissertation, Computer Science Division, University of California Berkeley, 1993.

Abstract

An important and largely ignored aspect of real-time decision making is the capability of agents to factor the cost of deliberation into the decision making process. I have developed an efficient model that creates this capability. The model uses as basic components anytime algorithms whose quality of results improves gradually as computation time increases. The main contribution of this work is a compilation process that extends the property of gradual improvement from the level of single algorithms to the level of complex systems.

In standard algorithms, the fixed quality of the output allows for composition to be implemented by a simple call-return mechanism. However, when algorithms have resource allocation as a degree of freedom, there arises the question of how to construct, for example, the optimal composition of two anytime algorithms, one of which feeds its output to the other. This scheduling problem is solved by an off-line compilation process and a run-time monitoring component that together generate a utility maximizing behavior. The crucial meta-level knowledge is kept in the anytime library in the form of conditional performance profiles. These profiles characterize the performance of each elementary anytime algorithm as a function of run-time and input quality. The compilation process therefore extends the principles of procedural abstraction and modularity to anytime computation. Its efficiency is significantly improved by using local compilation that works on a single program structure at a time. Local compilation is proved to yield global optimality for a large set of program structures.

Compilation produces contract algorithms which require the determination of the total run-time when activated. Some real-time domains require interruptible algorithms whose total run-time is unknown in advance. An important result of this work is a general method by which an interruptible algorithm can be constructed once a contract algorithm is compiled. Finally, the notion of gradual improvement of quality is extended to sensing and plan execution and the application of the model is demonstrated through a simulated robot navigation system. The result is a modular approach for developing real-time agents that act by performing anytime actions and make decisions using anytime computation.

Bibtex entry:

@phdthesis{Zshort93,
  Author =      {Shlomo Zilberstein},
  Title =       {Operational Rationality through Compilation of Anytime Algorithms},
  Year =        {1993},
  School =      {Computer Science Division, University of California Berkeley},
  url =         {http://rbr.cs.umass.edu/shlomo/papers/Zshort93.html}
}

shlomo@cs.umass.edu
UMass Amherst