Anytime algorithm: Difference between revisions

Revision as of 07:08, 24 May 2019

Latest revision as of 05:18, 6 June 2025

(21 intermediate revisions by 15 users not shown)

Line 1:

{{short description|Algorithm that can return a valid solution to a problem even if interrupted}}
In [[computer science]], an '''anytime algorithm''' is an [[algorithm]] that can return a valid solution to a [[Problem#ProblemComputational solvingproblem|problem]] even if it is interrupted before it ends. The algorithm is expected to find better and better solutions the longer it keeps running.

Most algorithms run to completion: they provide a single answer after performing some fixed amount of computation. In some cases, however, the user may wish to terminate the algorithm prior to completion. The amount of computation required may be substantial, for example, and computational resources might need to be reallocated. Most algorithms either run to completion or they provide no useful solution information. Anytime algorithms, however, are able to return a partial answer, whose quality depends on the amount of computation they were able to perform. The answer generated by anytime algorithms is an approximation of the correct answer.

==Names==

An anytime algorithm may be also called an "interruptible algorithm". They are different from contract algorithms, which must declare a time in advance; in an anytime algorithm, a process can just announce that it is terminating.<ref name="Hendler">Hendler,{{cite book |editor-first=James A., ''|editor-last=Hendler |title=Artificial Intelligence Planning Systems'',: Proceedings of the First Conference (AIPS 92) |publisher=Elsevier |orig-date=1992 |date=2014 |isbn=978-0-08-049944-4 |url={{GBurl|tgujBQAAQBAJ|pg=PR5}}}}</ref>

== 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, Shlomo. "Using Anytime Algorithms in Intelligent Systems". http://rbr.cs.umass.edu/shlomo/papers/Zaimag96.pdf|1996}}</ref> They are also supposed to be flexible in time and resources.<ref name="Grass">Grass,{{cite Joshuajournal |first=J. |last=Grass |title= "Reasoning about [[Computationalcomputational resource allocation|Computationaljournal=XRDS: Resource]]Crossroads, Allocation."the ACM Magazine for http://www.acm.org/crossroads/xrds3-Students |volume=3 |issue=1/racra.html {{Webarchive|urlpages=https://web16–20 |date=1996 |doi=10.archive.org/web/20071212193158/http:/1145/www332148.acm.org/crossroads/xrds3-1/racra.html332154 |dates2cid=200745448244 |doi-12-12access=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-RaphsonNewton–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 DecDecember 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 DecDecember 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,{{cite book |first=Edward A. ''|last=Bender |title=Mathematical Methods In Artificial Intelligence'', [[IEEE|publisher=Wiley Computer|date=1996 Society]]|isbn=978-0-8186-7200-2 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. AnytimeCertain 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"/>

== Decision trees ==

When the decider has to act, there must be some ambiguity. Also, there must be some idea about how to solve this ambiguity. This idea must be translatable to a state to action diagram.<ref name="Horsch">{{harvnb|Horsch, Michael C., |Poole, David "An Anytime Algorithm for Decision Making under Uncertainty" http://www.cs.ubc.ca/spider/poole/papers/randaccref.pdf|1998}}</ref>

== Performance profile ==

The performance profile estimates the quality of the results based on the input and the amount of time that is allotted to the algorithm.<ref name="Grass"/> The better the estimate, the sooner the result would be found.<ref name="Grass"/> Some systems have a larger database that gives the probability that the output is the expected output.<ref name="Grass"/> It is important to note that one algorithm can have several performance profiles.<ref name="Teije">{{cite conference |last1=Teije, Annette|first1=A.T. ten,|last2=van Harmelen, Frank|first2=F. "|title=Describing Problemproblem Solvingsolving Methodsmethods using Anytimeanytime Performanceperformance Profiles"profiles |book-title=Proceedings of the 14th European Conference on Artificial Intelligence |publisher= |___location= |date=2000 |isbn= |pages=181–5 |url=https://core.ac.uk/download/pdf/43408018.pdf }}</ref> Most of the time performance profiles are constructed using [[mathematical statistics]] using representative cases. For example, in the [[Travelling salesman problem|traveling salesman]] problem, the performance profile was generated using a user-defined special program to generate the necessary statistics.<ref name="Hendler"/> In this example, the performance profile is the mapping of time to the expected results.<ref name="Hendler"/> This quality can be measured in several ways:

*certainty: where probability of correctness determines quality<ref name="Hendler"/>

Line 36 ⟶ 37:

== Further reading ==

{{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}}

* Boddy, M, Dean, T. 1989. ''Solving Time-Dependent Planning Problems''. Technical Report: CS-89-03, Brown University

* {{cite journal |last1=Grass, |first1=J., and |last2=Zilberstein, |first2=S. 1996. |title=Anytime Algorithm Development Tools. ''|journal=ACM SIGART Bulletin'' (|volume=7 |issue=2 Special Issue on Anytime Algorithms and Deliberation Scheduling) 7(2)|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}}

* Michael C. Horsch and David Poole, An Anytime Algorithm for Decision Making under Uncertainty, In Proc. 14th Conference on Uncertainty in Artificial Intelligence (UAI-98), Madison, Wisconsin, USA, July 1998, pages 246-255.

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

* {{cite journal |last1=Wallace, |first1=R., and |last2=Freuder, |first2=E. 1995. |title=Anytime Algorithms for Constraint Satisfaction and SAT Problems. Paper|journal= presentedACM atSIGART theBulletin IJCAI-95|volume=7 Workshop|issue=2 on|pages=7–10 Anytime|date=1995 Algorithms|doi=10.1145/242587.242589 and|s2cid=8250394 Deliberation|doi-access=free Scheduling, 20 August, Montreal, Canada.}}

* Zilberstein,{{cite thesis |first=S. 1993.|last=Zilberstein ''|title=Operational Rationality through Compilation of Anytime Algorithms''. Ph.D. diss., |publisher=Computer Science Division, University of California at Berkeley |type=PhD |date=1993 |url=https://dl.acm.org/doi/abs/10.5555/193131 |id=UMX GAX94-08166}}

*{{cite journal |first=Shlomo |last=Zilberstein, |title=Using Anytime Algorithms in Intelligent Systems, ''|journal=AI Magazine'', |volume=17( |issue=3):73-83, |pages=73–83 |date=1996 |doi= |url=http://rbr.cs.umass.edu/shlomo/papers/Zaimag96.pdf}}

{{refend}}

{{DEFAULTSORT:Anytime Algorithm}}

[[Category:Artificial intelligence engineering]]

[[Category:Search algorithms]]