anytime algorithm


Also found in: Wikipedia.

anytime algorithm

(algorithm)
An algorithm that returns a sequence of approximations to the correct answer such that each approximation is no worse than the previous one, i.e. the algorithm can be stopped at _any time_.

Newton-Raphson iteration applied to finding the square root of a number b is another example:

x = (x + b / x) / 2

Each new x is closer to the square root than the previous one.

Applications might include a real-time control system or a chess program that is allowed a fixed thinking time.
This article is provided by FOLDOC - Free Online Dictionary of Computing (foldoc.org)
References in periodicals archive ?
He coauthored the papers that coined the widely used terms anytime algorithm, performance profile, and conformant planning.
However, these algorithms can be grouped in many categories such as static algorithms, anytime algorithms, and replanning algorithms [4].
As one example of a well-motivated deterministic unsound algorithms, consider anytime algorithms [Zilberstein 1993; Zilberstein 1996]: While addressing a specific problem, these systems are required to produce an answer whenever requested, even before the system has run to completion.
Operational Rationality through Compilation of Anytime Algorithms. Tech.
1995], and specialized query languages that can selectively reorder operations for higher efficiency [Imielinski and Mannila 1996]; and (iii) efficient online reformulations of the basic technique also exist [Hidber 1999] that can terminate early, once results of the desired quality are achieved, and can be viewed as anytime algorithms [Ramakrishnan and Grama 1999] due to their interruptibility and the monotonic improvement of the quality of the answer with time.
The trade-off at the center of the article is to maximize the controller builder's response value by ensuring its timeliness, at the expense of some degradation in the quality of the controller produced, in the manner of anytime algorithms. The remaining trade-offs are to maximize the response value of the controller itself by minimizing controller response times (done by automatically decomposing controllers into multiple assimilation levels (i.e., occasionally tolerating some inattention; and to achieve this decomposition via the expenditure of additional processing power by the controller builder.
Anytime Algorithms for Multiagent Decision Making Using Coordination Graphs.
Optimal Schedules for Monitoring Anytime Algorithms. Artificial Intelligence 126(1-2): 63-108.
Monitoring and Control of Anytime Algorithms: A Dynamic Programming Approach.
His research interests include anytime algorithms, decision theory, design of autonomous agents, heuristic search, information gathering, principles of metareasoning, planning and scheduling, reinforcement learning, and resource-bounded reasoning.