Optimal Sequencing of Contract Algorithms
Shlomo Zilberstein
Francois Charpillet
Philippe Chassaing
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.
Download
[ps]
[pdf]