Optimal Sequencing of Contract Algorithms

Shlomo Zilberstein, Francois Charpillet, and Philippe Chassaing. Optimal Sequencing of Contract Algorithms. Annals of Mathematics and Artificial Intelligence, 39(1-2):1-18, 2003.

Abstract

We address the problem of building an interruptible real-time system using non-interruptible components. Some artificial intelligence techniques offer a tradeoff between computation time and quality of results, but their run-time must be determined when they are activated. These techniques, called contract algorithms, introduce a complex scheduling problem when there is uncertainty about the amount of time available for problem-solving. We show how to optimally sequence contract algorithms to create the best possible interruptible system with or without stochastic information about the deadline. These results extend the foundation of real-time problem-solving and provide useful guidance for embedding contract algorithms in applications.

Bibtex entry:

@article{ZCCamai03,
  author	= {Shlomo Zilberstein and Francois Charpillet and Philippe Chassaing},
  title		= {Optimal Sequencing of Contract Algorithms},
  journal	= {Annals of Mathematics and Artificial Intelligence},
  volume	= {39},
  number	= {1-2},
  year		= {2003},
  pages		= {1-18},
  url		= {http://rbr.cs.umass.edu/shlomo/papers/ZCCamai03.html}
}

shlomo@cs.umass.edu