Anytime A*

Last updated

In computer science, anytime A* is a family of variants of the A* search algorithm. Like other anytime algorithms, it has a flexible time cost, can return a valid solution to a pathfinding or graph traversal problem even if it is interrupted before it ends, by generating a fast, non-optimal solution before progressively optimizing it. This ability to quickly generate solutions has made it attractive to Search-base sites and AI designs.

Contents

Background and history

Running the optimal A* algorithm to completion is too expensive for many purposes. A*'s optimality can be sacrificed in order to reduce the execution time by inflating the heuristic, as in weighted A* from 1970. [1] Iteratively reducing the degree the heuristic is "inflated" provides a naive anytime algorithm (ATA*, 2002), but this repeats previous work. [2] A more efficient and error-bounded version that reuses results, Anytime Repairing A* (ARA*), was reported in 2003. [3] [4] A dynamic (in the sense of D*) modification of ARA*, Anytime Dynamic A* (ADA*) was published in 2005. It combines aspects of D* Lite and ARA*. [5] Anytime Weighted A* (1997, 2007) is similar to weighted A*, except that it continues the search after finding the first solution. It finds better solutions iteratively and ultimately finds the optimal solution without repeating previous work and also provides error bounds throughout the search. [6] [7] Randomized Weighted A* (2021) introduced randomization into Anytime Weighted A* and demonstrated better empirical performance. [8]

Difference from A*

Weighted A* search that uses a heuristic that is w = 5.0 times a consistent heuristic and obtains a suboptimal path. Weighted A star with eps 5.gif
Weighted A* search that uses a heuristic that is w = 5.0 times a consistent heuristic and obtains a suboptimal path.

A* search algorithm can be presented by the function of f(n) = g(n) + h(n), where n is the last node on the path, g(n) is the cost of the path from the start node to n, and h(n) is a heuristic that estimates the cost of the cheapest path from n to the goal. Different than the A* algorithm, the most important function of Anytime A* algorithm is that, they can be stopped and then can be restarted at any time. Anytime A* family of algorithms typically build upon the weighted version of the A* search: where one uses fw(n) = g(n) + w × h(n), w > 1, and performs the A* search as usual, which eventually happens faster since fewer nodes are expanded. [1]

ATA* involves running weighted A* multiple times with w gradually lowering each time until w=1 when the search just becomes plain A*. Although this could work by calling A* repeatedly and discarding all previous memory, ARA* does this by introducing a way of updating the path. [4] The initial value of w determines the minimal (first-time) runtime of ATA*.

Anytime weighted A* turns weighted A* into an anytime algorithm as follows. [6] [7] Each goal test is done at node generation instead of node expansion, and the current solution becomes the best goal node so far. Unless the algorithm is interrupted, the search continues until the optimal solution is found. During the search, the error bound is the cost of the current solution c minus the least f-value in the open list. The optimal solution is detected when no more nodes with f(n) ≤ c remain open, and at that point the algorithm terminates with c as the cost of optimal solution. In 2021, it was discovered that given a search time-limit, Anytime weighted A* yields better solutions on average by simply switching the weight randomly after each node expansion than by using a fine-tuned static weight or by gradually lowering the weight after each solution. [8]

Related Research Articles

<span class="mw-page-title-main">Huffman coding</span> Technique to compress data

In computer science and information theory, a Huffman code is a particular type of optimal prefix code that is commonly used for lossless data compression. The process of finding or using such a code is Huffman coding, an algorithm developed by David A. Huffman while he was a Sc.D. student at MIT, and published in the 1952 paper "A Method for the Construction of Minimum-Redundancy Codes".

<span class="mw-page-title-main">Travelling salesman problem</span> NP-hard problem in combinatorial optimization

The travelling salesman problem (TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?" It is an NP-hard problem in combinatorial optimization, important in theoretical computer science and operations research.

<span class="mw-page-title-main">Minimum spanning tree</span> Least-weight tree connecting graph vertices

A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. That is, it is a spanning tree whose sum of edge weights is as small as possible. More generally, any edge-weighted undirected graph has a minimum spanning forest, which is a union of the minimum spanning trees for its connected components.

<span class="mw-page-title-main">Dijkstra's algorithm</span> Graph search algorithm

Dijkstra's algorithm is an algorithm for finding the shortest paths between nodes in a weighted graph, which may represent, for example, road networks. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years later.

A* is a graph traversal and path search algorithm, which is used in many fields of computer science due to its completeness, optimality, and optimal efficiency. One major practical drawback is its space complexity, as it stores all generated nodes in memory. Thus, in practical travel-routing systems, it is generally outperformed by algorithms that can pre-process the graph to attain better performance, as well as memory-bounded approaches; however, A* is still the best solution in many cases.

Best-first search is a class of search algorithms, which explores a graph by expanding the most promising node chosen according to a specified rule.

In computer science, local search is a heuristic method for solving computationally hard optimization problems. Local search can be used on problems that can be formulated as finding a solution maximizing a criterion among a number of candidate solutions. Local search algorithms move from solution to solution in the space of candidate solutions by applying local changes, until a solution deemed optimal is found or a time bound is elapsed.

Branch and bound is a method for solving optimization problems by breaking them down into smaller sub-problems and using a bounding function to eliminate sub-problems that cannot contain the optimal solution. It is an algorithm design paradigm for discrete and combinatorial optimization problems, as well as mathematical optimization. A branch-and-bound algorithm consists of a systematic enumeration of candidate solutions by means of state space search: the set of candidate solutions is thought of as forming a rooted tree with the full set at the root. The algorithm explores branches of this tree, which represent subsets of the solution set. Before enumerating the candidate solutions of a branch, the branch is checked against upper and lower estimated bounds on the optimal solution, and is discarded if it cannot produce a better solution than the best one found so far by the algorithm.

In computer science, beam search is a heuristic search algorithm that explores a graph by expanding the most promising node in a limited set. Beam search is an optimization of best-first search that reduces its memory requirements. Best-first search is a graph search which orders all partial solutions (states) according to some heuristic. But in beam search, only a predetermined number of best partial solutions are kept as candidates. It is thus a greedy algorithm.

Iterative deepening A* (IDA*) is a graph traversal and path search algorithm that can find the shortest path between a designated start node and any member of a set of goal nodes in a weighted graph. It is a variant of iterative deepening depth-first search that borrows the idea to use a heuristic function to conservatively estimate the remaining cost to get to the goal from the A* search algorithm. Since it is a depth-first search algorithm, its memory usage is lower than in A*, but unlike ordinary iterative deepening search, it concentrates on exploring the most promising nodes and thus does not go to the same depth everywhere in the search tree. Unlike A*, IDA* does not utilize dynamic programming and therefore often ends up exploring the same nodes many times.

<span class="mw-page-title-main">Pathfinding</span> Plotting by a computer application

Pathfinding or pathing is the plotting, by a computer application, of the shortest route between two points. It is a more practical variant on solving mazes. This field of research is based heavily on Dijkstra's algorithm for finding the shortest path on a weighted graph.

In computer science, specifically in algorithms related to pathfinding, a heuristic function is said to be admissible if it never overestimates the cost of reaching the goal, i.e. the cost it estimates to reach the goal is not higher than the lowest possible cost from the current point in the path.

In mathematical optimization and computer science, heuristic is a technique designed for solving a problem more quickly when classic methods are too slow for finding an approximate solution, or when classic methods fail to find any exact solution. This is achieved by trading optimality, completeness, accuracy, or precision for speed. In a way, it can be considered a shortcut.

In computer science, B* is a best-first graph search algorithm that finds the least-cost path from a given initial node to any goal node. First published by Hans Berliner in 1979, it is related to the A* search algorithm.

D* is any one of the following three related incremental search algorithms:

Capacitated minimum spanning tree is a minimal cost spanning tree of a graph that has a designated root node and satisfies the capacity constraint . The capacity constraint ensures that all subtrees incident on the root node have no more than nodes. If the tree nodes have weights, then the capacity constraint may be interpreted as follows: the sum of weights in any subtree should be no greater than . The edges connecting the subgraphs to the root node are called gates. Finding the optimal solution is NP-hard.

<span class="mw-page-title-main">Any-angle path planning</span> Algorithm to find Euclidean shortest paths

Any-angle path planning algorithms are pathfinding algorithms that search for a Euclidean shortest path between two points on a grid map while allowing the turns in the path to have any angle. The result is a path that cuts directly through open areas and has relatively few turns. More traditional pathfinding algorithms such as A* either lack in performance or produce jagged, indirect paths.

In computer science, an optimal binary search tree (Optimal BST), sometimes called a weight-balanced binary tree, is a binary search tree which provides the smallest possible search time (or expected search time) for a given sequence of accesses (or access probabilities). Optimal BSTs are generally divided into two types: static and dynamic.

<span class="mw-page-title-main">Shlomo Zilberstein</span>

Shlomo Zilberstein is an Israeli-American computer scientist. He is a Professor of Computer Science and Associate Dean for Research and Engagement in the College of Information and Computer Sciences at the University of Massachusetts, Amherst. He graduated with a B.A. in Computer Science summa cum laude from Technion – Israel Institute of Technology in 1982, and received a Ph.D. in Computer Science from University of California at Berkeley in 1993, advised by Stuart J. Russell. He is known for his contributions to artificial intelligence, anytime algorithms, multi-agent systems, and automated planning and scheduling algorithms, notably within the context of Markov decision processes (MDPs), Partially Observable MDPs (POMDPs), and Decentralized POMDPs (Dec-POMDPs).

References

  1. 1 2 Pohl, Ira (1970). "First results on the effect of error in heuristic search". Machine Intelligence 5. Edinburgh University Press. pp. 219–236. ISBN   978-0-85224-176-9. OCLC   1067280266.
  2. ↑ Zhou, R.; Hansen, E.A. (2002). Multiple sequence alignment using A* (PDF). Eighteenth national conference on Artificial intelligence. pp. 975–976. ISBN   978-0-262-51129-2.
  3. ↑ Likhachebv, Maxim; Gordon, Geoff; Thrun, Sebastian. ARA*: formal analysis (PDF) (Technical report). School of Computer Science, Carnegie Mellon University. Retrieved 24 July 2018.
  4. 1 2 Likhachebv, Maxim; Gordon, Geoff; Thrun, Sebastian. ARA*: Anytime A* with Provable Bounds on Sub-Optimality (PDF) (Technical report). School of Computer Science, Carnegie Mellon University. Retrieved 24 April 2018.
  5. ↑ Krause, Alex (2005). "Anytime Dynamic A*: An Anytime, Replanning Algorithm". Proceedings of the Fifteenth International Conference on International Conference on Automated Planning and Scheduling. pp. 262–271. ISBN   978-1-57735-220-4.
  6. 1 2 Hansen, E.A.; Zilberstein, S.; Danilchenko, V.A. (1997). Anytime Heuristic Search: First Results (Technical report). Computer Science Department, University of Massachusetts Amherst. 97-50.
  7. 1 2 Zhou, R.; Hansen, E.A. (2007). "Anytime Heuristic Search". Journal of Artificial Intelligence Research. 28: 267–297. arXiv: 1110.2737 . doi:10.1613/jair.2096. S2CID   9832874.
  8. 1 2 Bhatia, Abhinav; Svegliato, Justin; Zilberstein, Shlomo. "On the Benefits of Randomly Adjusting Anytime Weighted A*". Proceedings of the Fourteenth International Symposium on Combinatorial Search. Retrieved 21 July 2021.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.