Composing Real-Time Systems

Stuart J. Russell and Shlomo Zilberstein. Composing Real-Time Systems. Proceedings of the Twelfth International Joint Conference on Artificial Intelligence (IJCAI), 212-217, Sydney, Australia, 1991.

Abstract

We present a method to construct real-time systems using as components anytime algorithms whose quality of results degrades gracefully as computation time decreases. Introducing computation time as a degree of freedom defines a scheduling problem involving the activation and interruption of the anytime components. This scheduling problem is especially complicated when trying to construct interruptible algorithms, whose total run-time is unknown in advance. We introduce a framework to measure the performance of anytime algorithms and solve the problem of constructing interruptible algorithms by a mathematical reduction to the problem of constructing contract algorithms, which require the determination of the total run-time when activated. We show how the composition of anytime algorithms can be mechanized as part of a compiler for a LISP-like programming language for real-time systems. The result is a new approach to the construction of complex real-time systems that separates the arrangement of the performance components from the optimization of their scheduling, and automates the latter task.

Bibtex entry:

@inproceedings{RZijcai91,
  author	= {Stuart J. Russell and Shlomo Zilberstein},
  title		= {Composing Real-Time Systems},
  booktitle     = {Proceedings of the Twelfth International Joint Conference on
                   Artificial Intelligence},
  year		= {1991},
  pages		= {212-217},
  address       = {Sydney, Australia},
  url		= {http://rbr.cs.umass.edu/shlomo/papers/RZijcai91.html}
}

shlomo@cs.umass.edu