Optimizing Decision Quality with Contract Algorithms

Shlomo Zilberstein. Optimizing Decision Quality with Contract Algorithms. Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence (IJCAI), 1576-1582, Montreal, Canada, 1995.


Contract algorithms offer a tradeoff between output quality and computation time, provided that the amount of computation time is determined prior to their activation. Originally, they were introduced as an intermediate step in the composition of interruptible anytime algorithms. However, for many real-time tasks such as information gathering, game playing, and a large class of planning problems, contract algorithms offer an ideal mechanism to optimize decision quality. This paper extends previous results regarding the meta-level control of contract algorithms by handling a more general type of performance description. The output quality of each contract algorithm is described by a probabilistic (rather than deterministic) conditional performance profile. Such profiles map input quality and computation time to a probability distribution of output quality. The composition problem is solved by an efficient off-line compilation technique that simplifies the run-time monitoring task.

Bibtex entry:

  author	= {Shlomo Zilberstein},
  title		= {Optimizing Decision Quality with Contract Algorithms},
  booktitle     = {Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence},
  year		= {1995},
  pages		= {1576-1582},
  address       = {Montreal, Canada},
  url		= {http://rbr.cs.umass.edu/shlomo/papers/Zijcai95.html}

UMass Amherst