Anytime algorithm
Encyclopedia
In computer science
an anytime algorithm is an algorithm
that can return a valid solution to a problem even if it's interrupted at any time before it ends. The algorithm is expected to find better and better solutions the more time 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 the 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.
the ability to make results of better quality in return for turn-around time. They are also supposed to be flexible in time and resources. 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. Also, these are intended to have a better understanding that the system is dependent and restricted to its agents and how they work cooperatively. An example is the Newton-Raphson iteration applied to finding the square root of a number. 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.
What makes anytime algorithms unique is their ability to return many possible outcomes for any given input. An anytime algorithm uses many well defined quality measures to monitor progress in problem solving
and distributing computing resources. It keeps searching for the best possible answer with the amount of time that it is given. It may not run until completion and may improve the answer if it is allowed to run longer. This is often used for large decision set problems. This would generally not provide useful information unless it is allowed to finish. 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 to be predictable. Another goal is that someone can interrupt the process and the algorithm would give its most accurate result. This is why it is called an interruptible algorithm. Another goal of anytime algorithms are to maintain the last result so as they are given more time, they can continue calculating a more accurate result.
. 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. 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.
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. In this example, the performance profile is the mapping of time to the expected results. This quality can be measured in several ways:
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
an anytime algorithm is an algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
that can return a valid solution to a problem even if it's interrupted at any time before it ends. The algorithm is expected to find better and better solutions the more time 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 the 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 contact algorithms, which must declare a time in advance; in an anytime algorithm, a process can just announce that it is terminating.Goals
The goal of anytime algorithms are to give intelligent systemsHybrid intelligent system
Hybrid intelligent system denotes a software system which employs, in parallel, a combination of methods and techniques from artificial intelligence subfields as:* Neuro-fuzzy systems* hybrid connectionist-symbolic models* Fuzzy expert systems...
the ability to make results of better quality in return for turn-around time. They are also supposed to be flexible in time and resources. They are important because artificial intelligence
Artificial intelligence
Artificial intelligence is the intelligence of machines and the branch of computer science that aims to create it. AI textbooks define the field as "the study and design of intelligent agents" where an intelligent agent is a system that perceives its environment and takes actions that maximize its...
or AI algorithms can take a long time to complete results. This algorithm is designed to complete in a shorter amount of time. Also, these are intended to have a better understanding that the system is dependent and restricted to its agents and how they work cooperatively. An example is the Newton-Raphson iteration applied to finding the square root of a number. 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.
What makes anytime algorithms unique is their ability to return many possible outcomes for any given input. An anytime algorithm uses many well defined quality measures to monitor progress in problem solving
Problem solving
Problem solving is a mental process and is part of the larger problem process that includes problem finding and problem shaping. Consideredthe most complex of all intellectual functions, problem solving has been defined as higher-order cognitive process that requires the modulation and control of...
and distributing computing resources. It keeps searching for the best possible answer with the amount of time that it is given. It may not run until completion and may improve the answer if it is allowed to run longer. This is often used for large decision set problems. This would generally not provide useful information unless it is allowed to finish. While this may sound similar to dynamic programming
Dynamic programming
In mathematics and computer science, dynamic programming is a method for solving complex problems by breaking them down into simpler subproblems. It is applicable to problems exhibiting the properties of overlapping subproblems which are only slightly smaller and optimal substructure...
, the difference is that it is fine-tuned through random adjustments, rather than sequential.
Anytime algorithms are designed to be predictable. Another goal is that someone can interrupt the process and the algorithm would give its most accurate result. This is why it is called an interruptible algorithm. Another goal of anytime algorithms are to maintain the last result so as they are given more time, they can continue calculating a more accurate result.
Construction
Make an algorithm with a parameter that influences running timeAnalysis of algorithms
To analyze an algorithm is to determine the amount of resources necessary to execute it. Most algorithms are designed to work with inputs of arbitrary length...
. 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. 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.
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.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. The better the estimate, the sooner the result would be found. Some systems have a larger database that gives the probability that the output is the expected output. It is important to note that one algorithm can have several performance profiles. Most of the time performance profiles are constructed using mathematical statisticsMathematical statistics
Mathematical statistics is the study of statistics from a mathematical standpoint, using probability theory as well as other branches of mathematics such as linear algebra and analysis...
using representative cases. For example in the traveling salesman
Travelling salesman problem
The travelling salesman problem is an NP-hard problem in combinatorial optimization studied in operations research and theoretical computer science. Given a list of cities and their pairwise distances, the task is to find the shortest possible tour that visits each city exactly once...
problem, the performance profile was generated using a user-defined special program to generate the necessary statistics. In this example, the performance profile is the mapping of time to the expected results. This quality can be measured in several ways:
- certainty: where probability of correctness determines quality
- accuracy: where error bound determines quality
- specificity: where the amount of particulars determine quality
Algorithm prerequisites
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.- Growth direction: How the quality of the program's "output" or result, varies as a function of the amount of time ("run time")
- Growth rate: Amount of increase with each step. Does it change constantly, such as in a bubble sortBubble sortBubble sort, also known as sinking sort, is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which...
or does it change unpredictably? - End condition: The amount of runtime needed
Further reading
- 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.
- Zilberstein, S. 1993. Operational Rationality through Compilation of Anytime Algorithms. Ph.D. diss., Computer Science Division, University of California at Berkeley.
- Shlomo Zilberstein, Using Anytime Algorithms in Intelligent Systems, AI Magazine, 17(3):73-83, 1996