Anytime algorithm: Difference between revisions

Revision as of 14:46, 23 December 2007

Latest revision as of 05:18, 6 June 2025

(73 intermediate revisions by 55 users not shown)

Line 1:

{{short description|Algorithm that can return a valid solution to a problem even if interrupted}}

{{deadend|date=December 2007}}

In [[computer science]], an '''anytime algorithm''' is an [[algorithm]] that can return a valid solution to a [[Computational problem|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.

==Other Names==

An anytime algorithm is also called an interruptible algorithm, however it is different from a contact algorithm because in a contact algorithm the time must be declared in advanced. In a anytime algorithm, a process can just announce that time is up <ref>Hendler</ref>.

==IntroductionNames==

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

Most programs run for a while and then gives the user the values that they expect within a few seconds. However, sometimes the program can be so complicated that they might take years to figure out completely and the user might have to shut down the computer before the answer is complete. What would happen if someone was to shut down the computer. In most cases, the computer would leave the issue unresolved and not do a thing. However, in the case of anytime algorithms, it would approximate the best answer and return a partial answer to the user. In other words, if the problem was completed, the program would return the 100 percent answer. Should it only be half finished it would return the 50 percent answer.

== Goals ==

== Goal of Anytime Algorithm ==

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 supposesupposed 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, the 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<"/ref>. 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<"/ref>. An example the is Newton-Raphsonthe [[Newton–Raphson]] iteration applied to finding the square root of a number b .<ref name="FOLDOC">[http://foldoc.org/anytime+algorithm anytime algorithm from Free Online Dictionary of Computing (FOLDOC)]</ref>. Another example tatthat uses anytime algorithms is trajectory problems andwhen youryou'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<"/ref>.

What makes anytime algorithms unique is their ability to return many possible outcomes for any given output input.<ref> name="Zilberstein<"/ref>. ItAn anytime algorithm uses many well defined quality measures to monitor progress in [[problem solving]] and distributing[[distributed computing]] resources .<ref> name="Zilberstein<"/ref>. 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</ref">.{{cite Thisweb|title=Anytime isalgorithm often- usedComputing for large decision set problems <ref>Horsch<Reference|url=http://ref>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 This would generally not provide useful information unless it is allowed to finish <ref>Bender2013}}</ref>. While this may sound similar to dynamic programming, the difference is that it is fine tuned trough random adjustments, rather than sequential.

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">{{cite book |first=Edward A. |last=Bender |title=Mathematical Methods In Artificial Intelligence |publisher=Wiley |date=1996 |isbn=978-0-8186-7200-2 }}</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 toso bethat predictableit <ref>Grass</ref>.can Anotherbe goaltold isto thatstop someoneat canany interrupttime theand processwould andreturn the algorithmbest wouldresult giveit itshas mostfound accurate resultso far.<ref> name="Grass<"/ref>. This is why it is called an interruptible algorithm. Another goal ofCertain anytime algorithms are toalso maintain the last result, so asthat if they are given more time, they can continue copulatingfrom awhere morethey accurateleft resultoff to obtain an even better result.<ref> name="Grass<"/ref>.

== Decision trees ==

==Constructing an Anytime Algorithm==

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|Poole|1998}}</ref>.

Make an algorithm with a parameter that influences running time. For example, as time increases, this variable also increases. After for a period of time, the search is stopped without having the goal met. This is similar to Jeopardy when the time runs out <ref>Bender</ref>. The contestants have to represent what they believe is the closest answer, although they may not know it or come even close to figuring out what it could be. This is similar to an hour long test. Although the test questions are not in themselves limiting for time, the test must be completed within the hour. Likewise, the computer has to figure out how much time and resources to spend on each problem <ref>Bender</ref>.

== Performance Profileprofile ==

==Working with Decision Trees==

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<"/ref>. The better the estimate, the sooner the result would be found .<ref> name="Grass<"/ref>. Some systems have a larger database that gives the probability that the output is the expected output .<ref> name="Grass<"/ref>. It is important to note that one algorithm can have several performance profiles .<ref name="Teije">{{cite conference |last1=Teije |first1=A.T. |last2=van Harmelen |first2=F. |title=Describing problem solving methods using anytime performance 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<"/ref>. In this example, the performance profile is the mapping of time to the expected results .<ref> name="Hendler<"/ref>. This quality can be measured in several ways:

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>Horsch</ref>.

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

==Performance Profile==

*accuracy: where error bound determines quality <ref> name="Hendler<"/ref>

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>Grass</ref>. The better the estimate, the sooner the result would be found <ref>Grass</ref>. Some systems have a larger database that gives the probability that the output is the expected output <ref>Grass</ref>. It is important to note that one algorithm can have several performance profiles <ref>Teije</ref>. Most of the time performance profiles are constructed using mathematical statistics using representative cases. For example in the traveling salesman problem, the performance profile was generated using a user-defined special program to generate the necessary statistics <ref>Hendler</ref>. In this example, the performance profile is the mapping of time to the expected results <ref>Hendler</ref>. This quality can be measured in several ways:

*specificity: where the amount of particulars determine quality<ref name="Hendler"/>

==Algorithm prerequisites==

certainty: where probability of correctness determines quality <ref>Hendler</ref>

Initial behavior: While some algorithms start with immediate guesses, others take a more calculated approach and have a start up period before making any guesses .<ref> name="Teije<"/ref>

*Growth direction: How the quality of the program's changes"output" withor increasingresult, runtimevaries as a function of the amount of time ("run time")<ref> name="Teije<"/ref>

accuracy: where error bound determines quality <ref>Hendler</ref>

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

specificity*End condition: where theThe amount of particulars determine qualityruntime needed<ref>Hendler< name="Teije"/ref>

==What must be determined before an Anytime Algorithm can Start==

Initial behavior: While some algorithms start with immediate guesses, others take a more calculated approach and have a start up period before making any guesses <ref>Teije</ref>

Growth direction: How the quality of the program changes with increasing runtime <ref>Teije</ref>

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>Teije</ref>

==References==

{{reflist}}

== Further reading ==

Anytime Algorithm http://foldoc.org/?anytime+algorithm

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

Anytime Algorithm http://tarono.wordpress.com/2007/03/20/anytime-algorithm

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

http://ai.eecs.umich.edu/cogarch2/cap/anytime.plan Anytime Algorithm

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

* {{cite journal |last1=Wallace |first1=R. |last2=Freuder |first2=E. |title=Anytime Algorithms for Constraint Satisfaction and SAT Problems |journal= ACM SIGART Bulletin |volume=7 |issue=2 |pages=7–10 |date=1995 |doi=10.1145/242587.242589 |s2cid=8250394 |doi-access=free }}

Bender, Edward A. ''Mathematical Methods In Artificial Intelligence'', IEEE Computer Society Pres, 1996

* {{cite thesis |first=S. |last=Zilberstein |title=Operational Rationality through Compilation of Anytime Algorithms |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 |pages=73–83 |date=1996 |doi= |url=http://rbr.cs.umass.edu/shlomo/papers/Zaimag96.pdf}}

ELook http://www.elook.org/computing/anytime-algorithm.htm

{{refend}}

Grass, Joshua. "Reasoning about Computational Resource Allocation." http://www.acm.org/crossroads/xrds3-1/racra.html

Hendler, James A., ''Artificial Intelligence Planning Systems'', 1992

Horsch, Michael C., Poole, David "An Anytime Algorithm for Decision Making under Uncertainty" http://www.cs.ubc.ca/spider/poole/papers/randaccref.pdf

Teije, Annette ten, Harmelen, Frank. "Describing Problem Solving Methods using Anytime Performance Profiles".

Zilberstein, Shlomo. "Using Anytime Algorithms in Intelligent Systems". http://anytime.cs.umass.edu/shlomo/papers/aimag96.pdf

==Recommended Reading==

http://www.acm.org/crossroads/xrds3-1/racra.html

== Goal of {{DEFAULTSORT:Anytime Algorithm ==}}

{{Uncategorized|date=December 2007}}

[[Category:Artificial intelligence engineering]]

[[Category:Search algorithms]]