Optimal schedules for monitoring anytime algorithms

Lev Finkelstein and Shaul Markovitch. Optimal schedules for monitoring anytime algorithms. Artificial Intelligence, 126:63-108 2001.

Abstract

Monitoring anytime algorithms can significantly improve their performance. This work deals with the problem of off-line construction of monitoring schedules. We study a model where queries are submitted to the monitored process in order to detect satisfaction of a given goal predicate. The queries consume time from the monitored process, thus delaying the time of satisfying the goal condition. We present a formal model for this class of problems and provide a theoretical analysis of the class of optimal schedules. We then introduce an algorithm for constructing optimal monitoring schedules and prove its correctness. We continue with distribution-based analysis for common distributions, accompanied by experimental results. We also provide a theoretical comparison of our methodology with existing monitoring techniques.

Keywords: Monitoring, Resource-Bounded Reasoning, Scheduling

Secondary Keywords:

Online version:

Bibtex entry:

 @article{Finkelstein:2001:OSM,
  Author = {Lev Finkelstein and Shaul Markovitch},
  Title = {Optimal schedules for monitoring anytime algorithms},
  Year = {2001},
  Journal = {Artificial Intelligence},
  Volume = {126},
  Pages = {63-108},
  Url = {http://www.cs.technion.ac.il/~shaulm/papers/pdf/Finkelstein-Markovitch-aij2001.pdf},
  Keywords = {Monitoring, Resource-Bounded Reasoning, Scheduling},
  Secondary-keywords = {Anytime Algorithms},
  Abstract = {
    Monitoring anytime algorithms can significantly improve their
    performance. This work deals with the problem of off-line
    construction of monitoring schedules. We study a model where
    queries are submitted to the monitored process in order to detect
    satisfaction of a given goal predicate. The queries consume time
    from the monitored process, thus delaying the time of satisfying
    the goal condition. We present a formal model for this class of
    problems and provide a theoretical analysis of the class of
    optimal schedules. We then introduce an algorithm for constructing
    optimal monitoring schedules and prove its correctness. We
    continue with distribution-based analysis for common
    distributions, accompanied by experimental results. We also
    provide a theoretical comparison of our methodology with existing
    monitoring techniques.
  }

  }