Anytime algorithm: Difference between revisions

Revision as of 11:19, 9 November 2009

Revision as of 17:02, 24 December 2010

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://anytime.cs.umass.edu/shlomo/papers/aimag96.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<!-- Bot generated title -->]</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 [[distributing 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">[http://ai.eecs.umich.edu/cogarch2/cap/anytime.plan Anytime algorithm<!-- Bot generated title -->]</ref> It may not run until completion and may improve the answer if it is allowed to run longer.<ref name="elook">[http://www.elook.org/computing/anytime-algorithm.htm Anytime algorithm - Computing Reference - eLook.org<!-- Bot generated title -->]</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.

Line 40:

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

* Grass, J., and Zilberstein, S. 1996. Anytime Algorithm Development Tools. ''SIGART Bulletin'' (Special Issue on Anytime Algorithms and Deliberation Scheduling) 7(2)

* 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.

* E.J. Horvitz. ''Reasoning about inference tradeoffs in a world of bounded resources''. Technical Report KSL-86-55, Medical Computer Science Group, Section on Medical Informatics, Stanford University, Stanford, CA, March 1986

* Wallace, R., and Freuder, E. 1995. Anytime Algorithms for Constraint Satisfaction and SAT Problems. Paper presented at the IJCAI-95 Workshop on Anytime Algorithms and Deliberation Scheduling, 20 August, Montreal, Canada.

Line 46:

* Shlomo Zilberstein, Using Anytime Algorithms in Intelligent Systems, ''AI Magazine'', 17(3):73-83, 1996

{{DEFAULTSORT:Anytime Algorithm}}

[[Category:Artificial intelligence]]