Anytime Heuristic Search

By Eric A. Hansen, R. Zhou. Journal of Artificial Intelligence Research, 2011

298 citations recorded by the source corpus.

We describe how to convert the heuristic search algorithm A* into an anytime algorithm that finds a sequence of improved solutions and eventually converges to an optimal solution. The approach we adopt uses weighted heuristic search to find an approximate solution quickly, and then continues the weighted search to find improved solutions as well as to improve a bound on the suboptimality of the current solution. When the time available to solve a search problem is limited or uncertain, this creates an anytime heuristic search algorithm that allows a flexible tradeoff between search time and solution quality. We analyze the properties of the resulting Anytime A* algorithm, and consider its performance in three domains; sliding-tile puzzles, STRIPS planning, and multiple sequence alignment. To illustrate the generality of this approach, we also describe how to transform the memory-efficient search algorithm Recursive Best-First Search (RBFS) into an anytime algorithm.

Subfields: Artificial Intelligence, Computer Networks and Communications, Computer Vision and Pattern Recognition

View Paper: https://www.semanticscholar.org/paper/aa85b00aada6f2351a51b16ea5b85b9652ea47e8

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Computer Vision and Pattern Recognition

Citations in the corpus

The LAMA Planner: Guiding Cost-Based Anytime Planning with Landmarks (2010, methodology): “…performed notably better than all other tested methods, dominating similar algorithms based on weighted A∗ (Hansen, Zilberstein, & Danilchenko, 1997; Hansen & Zhou, 2007; Likhachev, Gordon, & Thrun, 2004; Likhachev et al., 2008), as well as other anytime approaches (Zhou & Hansen, 2005; Aine,…”
A Survey of Motion Planning and Control Techniques for Self-Driving Urban Vehicles (2016, background): “Anytime A* [111] uses a weighted heuristic to find the first solution and achieves the anytime behavior by continuing the search with the cost of the first path as an upper bound and the admissible heuristic as a lower bound, whereas Anytime Repairing A* (ARA*) [112] performs a series of searches wi”