Anytime algorithm: Difference between revisions

Revision as of 10:26, 27 January 2025

Latest revision as of 05:18, 6 June 2025

(4 intermediate revisions by 4 users not shown)

Line 8:

== 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">{{harvnb|Zilberstein|1996}} </ref> They are also supposed to be flexible in time and resources.<ref name="Grass">{{cite journal |first=J. |last=Grass |title= Reasoning about computational resource allocation. |journal=XRDS: Crossroads, |journal=Thethe ACM Magazine for Students |volume=3 |issue=1 |pages=16–20 |date=1996 |doi=10.1145/332148.332154 |s2cid=45448244 |doi-access=free }}</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 Free Online Dictionary of 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=https://web.archive.org/web/20131213011435/http://ai.eecs.umich.edu/cogarch2/cap/anytime.plan|archivedate=13 December 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|website=eLook.org|archiveurl=https://web.archive.org/web/20131212094200/http://www.elook.org/computing/anytime-algorithm.htm|archivedate=12 December 2013}}</ref>

Line 31:

*Growth rate: Amount of increase with each step. Does it change constantly, such as in a [[bubble sort]] or does it change unpredictably?

*End condition: The amount of runtime needed<ref name="Teije"/>

== Examples ==

There are many famous anytime algorithms in the literature. We list here some of them.

* PBVI (point-based value iteration) is an anytime algorithm for [[Automated planning and scheduling|automated planning]] in [[Partially observable Markov decision process|partially observable Markov decision processes]]<ref>{{Cite journal |last=Pineau |first=Joelle |last2=Gordon |first2=Geoff |last3=Thrun |first3=Sebastian |date=2003-08-09 |title=Point-based value iteration: an anytime algorithm for POMDPs |url=https://dl.acm.org/doi/10.5555/1630659.1630806 |journal=Proceedings of the 18th international joint conference on Artificial intelligence |series=IJCAI'03 |___location=San Francisco, CA, USA |publisher=Morgan Kaufmann Publishers Inc. |pages=1025–1030 |doi=10.5555/1630659.1630806}}</ref>.

==References==

Line 43 ⟶ 38:

{{refbegin}}

*{{cite conference |last1=Boddy |first1=M. |last2=Dean |first2=T. |title=Solving time-dependent planning problems |book-title=Proceedings of the 11th international joint conference on Artificial intelligence |volume=2 |date=1989 |isbn= |pages=979–984 |url=https://dl.acm.org/doi/abs/10.5555/1623891.1623912 |id=Brown University CS-89-03}}

* {{cite journal |last1=Grass |first1=J. |last2=Zilberstein |first2=S. |title=Anytime Algorithm Development Tools |journal=ACM SIGART Bulletin |volume=7 |issue=2 Special Issue on Anytime Algorithms and Deliberation Scheduling |pages= 20–27|date=1996 |doi=10.1145/242587.242592 |s2cid=7670055 |url=https://dl.acm.org/doi/abs/10.1145/242587.242592|url-access=subscription }}

* {{cite conference |arxiv=1301.7384 |last1=Horsch |first1=M.C. |last2=Poole |first2=D. |title=An anytime algorithm for decision making under uncertainty |book-title=Proceedings of the Fourteenth conference on Uncertainty in artificial intelligence |date=1998 |isbn=978-1-55860-555-8 |pages=246–255 |url=http://www.cs.ubc.ca/spider/poole/papers/randaccref.pdf}}

* {{cite tech report |first=E.J. |last=Horvitz |title=Reasoning about inference tradeoffs in a world of bounded resources |publisher=Medical Computer Science Group, Section on Medical Informatics, Stanford University |id=KSL-86-55 |date=March 1986 |url=}}