Monitoring and control of anytime algorithms: A dynamic programming approach

Anytime algorithms offer a tradeoff between solution quality and computatio n time that has proved useful in solving time-critical problems such as pla nning and scheduling, belief network evaluation, and information gathering. To exploit this tradeoff, a system must be able to decide when to stop del iberation and act on the currently available solution. This paper analyzes the characteristics of existing techniques for meta-level control of anytim e algorithms and develops a new framework for monitoring and control. The n ew framework handles effectively the uncertainty associated with the algori thm's performance profile, the uncertainty associated with the domain of op eration, and the cost of monitoring progress. The result is an efficient no n-myopic solution to the meta-level control problem for anytime algorithms. (C) 2001 Elsevier Science B.V. All rights reserved.