Optimal Composition of Real-Time Systems

Shlomo Zilberstein and Stuart J. Russell. Optimal Composition of Real-Time Systems. Artificial Intelligence, 82(1-2):181-213, 1996.

Abstract

Real-time systems are designed for environments in which the utility of actions is strongly time-dependent. Recent work by Dean, Horvitz and others has shown that anytime algorithms are a useful tool for real-time system design, since they allow computation time to be traded for decision quality. In order to construct complex systems, however, we need to be able to compose larger systems from smaller, reusable anytime modules. This paper addresses two basic problems associated with composition: how to ensure the interruptibility of the composed system; and how to allocate computation time optimally among the components. The first problem is solved by a simple and general construction that incurs only a small, constant penalty. The second is solved by an off-line compilation process. We show that the general compilation problem is NP-complete. However, efficient local compilation techniques, working on a single program structure at a time, yield globally optimal allocations for a large class of programs. We illustrate these results with two simple applications.

Bibtex entry:

@article{ZRaij96,
  author	= {Shlomo Zilberstein and Stuart J. Russell},
  title		= {Optimal Composition of Real-Time Systems},
  journal	= {Artificial Intelligence},
  volume	= {82},
  number	= {1-2},
  year		= {1996},
  pages		= {181-213},
  url		= {http://rbr.cs.umass.edu/shlomo/papers/ZRaij96.html}
}

shlomo@cs.umass.edu