Anytime algorithm: Difference between revisions

Revision as of 14:19, 21 June 2016

Revision as of 12:06, 5 August 2016

Line 7:

== Goals ==

The goal of anytime algorithms are to give [[Hybrid intelligent system|intelligent systems]] the ability to make results of better quality in return for turn-around time.<ref name="Zilberstein">Zilberstein, Shlomo. "Using Anytime Algorithms in Intelligent Systems". http://rbr.cs.umass.edu/shlomo/papers/Zaimag96.pdf</ref> They are also supposed to be flexible in time and resources.<ref name="Grass">Grass, Joshua. "Reasoning about [[Computational resource|Computational Resource]] Allocation." http://www.acm.org/crossroads/xrds3-1/racra.html</ref> They are important because [[artificial intelligence]] or AI algorithms can take a long time to complete results. This algorithm is designed to complete in a shorter amount of time.<ref name="Grass"/> Also, these are intended to have a better understanding that the system is dependent and restricted to its agents and how they work cooperatively.<ref name="Grass"/> An example is the [[Newton-Raphson]] iteration applied to finding the square root of a number.<ref name="FOLDOC">[http://foldoc.org/?anytime+algorithm anytime algorithm from FOLDOC<!--Free BotOnline generatedDictionary titleof -->Computing (FOLDOC)]</ref> Another example that uses anytime algorithms is trajectory problems when you're aiming for a target; the object is moving through space while waiting for the algorithm to finish and even an approximate answer can significantly improve its accuracy if given early.<ref name="Grass"/>

What makes anytime algorithms unique is their ability to return many possible outcomes for any given input.<ref name="Zilberstein"/> An anytime algorithm uses many well defined quality measures to monitor progress in [[problem solving]] and [[distributed computing]] resources.<ref name="Zilberstein"/> It keeps searching for the best possible answer with the amount of time that it is given.<ref name="umich">[{{cite web|title=Anytime algorithms|url=http://ai.eecs.umich.edu/cogarch2/index.html|website=Cognitive architectures|publisher=University of Michigan Artificial Intelligence Laboratory|archiveurl=http://web.archive.org/web/20131213011435/http://ai.eecs.umich.edu/cogarch2/cap/anytime.plan|archivedate=13 AnytimeDec algorithm<!-- Bot generated title -->]2013}}</ref> It may not run until completion and may improve the answer if it is allowed to run longer.<ref name="elook">[{{cite web|title=Anytime algorithm - Computing Reference|url=http://www.elook.org/computing/anytime-algorithm.htm Anytime algorithm - Computing Reference - |website=eLook.org<!-|archiveurl=https://web.archive.org/web/20131212094200/http://www.elook.org/computing/anytime-algorithm.htm|archivedate=12 BotDec generated title -->]2013}}</ref>
This is often used for large decision set problems.<ref name="Horsch"/> This would generally not provide useful information unless it is allowed to finish.<ref name="Bender">Bender, Edward A. ''Mathematical Methods In Artificial Intelligence'', [[IEEE Computer Society]] Pres, 1996</ref> While this may sound similar to [[dynamic programming]], the difference is that it is fine-tuned through random adjustments, rather than sequential.

Anytime algorithms are designed so that it can be told to stop at any time and would return the best result it has found so far.<ref name="Grass"/> This is why it is called an interruptible algorithm. Anytime algorithms also maintain the last result, so that if they are given more time, they can continue from where they left off to obtain an even better result.<ref name="Grass"/>