In the simplest terms, an anytime algorithm is an algorithm that can be
interrupted at any time and will always return a solution. The idea
of an anytime algorithm was originally presented by Thomas Dean and Mark
Boddy in their 1988 AAAI paper An Analysis of Time Dependant
Planning. The concept of an anytime algorithm has been developed further
by Shlomo Zilberstein, among others.
To make anytime algorithms into useful tools for problem solving, a number
of constraints must be placed upon them. First, they must be able to return a
solution at any time during their processing time. For example,
searching for your car keys is not an anytime algorithm. Either you've found
your keys, or you haven't, there is no inbetween answer. Pouring
water into a bath is an anytime algorithm as there is always some water in
the bath after you start the process. The second constraint on the processing
behaviour of an anytime algorithm is that the quality of the results it returns
must increase monotonically with respect to processing time. This allows a
process controlling an anytime algorithm to trade-off processing time against
result quality (this wouldn't be possible if the quality varied wildly). This is
usually done using a performance profile (a representation of how the result
quality increases with processing time) to predict how the result will improve
in the future. This relies on being able to measure the quality of any
arbitrary solution produced by the algorithm. Other constraints have been
suggested by the anytime algorithm literature, but they are not as critical
as these two.
Anytime algorithms have been used in many fields, including AI planning,
search, databases, and agent communication and negotiation
.