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


Log in or register to write something here or to contact authors.