The DOI matches its Crossref record; 28 of the 28 references it cites were found in a registry or an index.
Anytime Heuristic Search
Open accessAbstract
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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
A Formal Basis for the Heuristic Determination of Minimum Cost Paths
Hart, P., Nilsson, N., & Raphael, B. (1968) · IEEE Transactions on Systems Science and Cybernetics · doi:10.1109/tssc.1968.300136 · Cited by 12,738
Depth-first iterative-deepening
Korf, R. E. (1985) · Artificial Intelligence · doi:10.1016/0004-3702(85)90084-0 · Cited by 1,562
Heuristics: Intelligent search strategies for computer problem solving.
(1985) · Information Processing & Management · doi:10.1016/0306-4573(85)90100-1 · Cited by 1,430
Heuristics: Intelligent Search Strategies for Computer Problem Solving
(1986) · Telematics and Informatics · doi:10.1016/s0736-5853(86)80081-8 · Cited by 1,072
Generalized best-first search strategies and the optimality of A*
Dechter, R., & Pearl, J. (1985) · Journal of the ACM · doi:10.1145/3828.3830 · Cited by 1,071
Bonet, B., & Geffner, H. (2001) · Artificial Intelligence · doi:10.1016/s0004-3702(01)00108-4 · Cited by 959
Korf, R. E. (1990) · Artificial Intelligence · doi:10.1016/0004-3702(90)90054-4 · Cited by 917
Using anytime algorithms in intelligent systems
Shlomo Zilberstein, B. (1996) · doi:10.1609/aimag.v17i3.1232 · Cited by 680
Do the Right Thing: Studies in Limited Rationality
Russell, S., Wefald, E. H., Bobrow, D. G., Brady, M., & Davis, R. (1991) · The MIT Press eBooks · doi:10.7551/mitpress/2474.001.0001 · Cited by 655
ARA*: Anytime A* with Provable Bounds on Sub-Optimality
Likhachev, M. A., Gordon, G. J., & Thrun, S. (2003) · Cited by 574
The Multiple Sequence Alignment Problem in Biology
Carrillo-Calvet, H., & Lipman, D. J. (1988) · SIAM Journal on Applied Mathematics · doi:10.1137/0148063 · Cited by 526
Heuristic search viewed as path finding in a graph
Pohl, I. (1970) · Artificial Intelligence · doi:10.1016/0004-3702(70)90007-x · Cited by 433
LAO∗: A heuristic search algorithm that finds solutions with loops
Hansen, E. A., & Zilberstein, S. (2001) · Artificial Intelligence · doi:10.1016/s0004-3702(01)00106-0 · Cited by 388
Self-citationAdmissible heuristics for optimal planning
Haslum, P., & Geffner, H. (2000) · doi:10.1609/aimag.v21i4.1536 · Cited by 310
Linear-space best-first search
Korf, R. E. (1993) · Artificial Intelligence · doi:10.1016/0004-3702(93)90045-d · Cited by 305
The 3rd International Planning Competition: Results and Analysis
Long, D., & Fox, M. (2003) · Journal of Artificial Intelligence Research · doi:10.1613/jair.1240 · Cited by 289
Studies in Semi-Admissible Heuristics
Pearl, J., & Kim, J. H. (1982) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.1982.4767270 · Cited by 205
Depth-first iterative-deepening: An optimal admissible tree search
(1986) · Artificial Intelligence · doi:10.1016/0004-3702(86)90035-4 · Cited by 194
Pohl, I. (1973) · International Joint Conference on Artificial Intelligence · Cited by 134
Bidirectional Heuristic Search Reconsidered
Kaindl, H., & Kainz, G. (1997) · Journal of Artificial Intelligence Research · doi:10.1613/jair.460 · Cited by 132
Do the right thing: studies in limited rationality
(1992) · Choice Reviews Online · doi:10.5860/choice.29-5169 · Cited by 128
Parsons, S. (1994) · The Knowledge Engineering Review · doi:10.1017/s0269888900007050 · Cited by 118
Controlling the learning process of real-time heuristic search
Shimbo, M., & Ishida, T. (2003) · Artificial Intelligence · doi:10.1016/s0004-3702(03)00012-2 · Cited by 77
Search Algorithms Under Different Kinds of Heuristics—A Comparative Study
Bagchi, A., & Mahanti, A. (1983) · Journal of the ACM · doi:10.1145/322358.322359 · Cited by 75
The heuristic search under conditions of error
Harris, L. (1974) · Artificial Intelligence · doi:10.1016/0004-3702(74)90014-9 · Cited by 71
Admissibility of AO∗ when heuristics overestimate
Chakrabarti, P. P., Ghose, S., & DeSarkar, S. C. (1987) · Artificial Intelligence · doi:10.1016/0004-3702(87)90005-1 · Cited by 50
Do the right thing studies in limited rationality
Russell, S. J., & Wefald, E. H. (1991) · Cited by 29
Multiple-Goal Heuristic Search
Davidov, D., & Markovitch, S. (2006) · Journal of Artificial Intelligence Research · doi:10.1613/jair.1940 · Cited by 16
Metadata
- Authors
- Hansen, E. A., & Zhou, R.
- Venue
- Journal of Artificial Intelligence Research
- Publisher
- AI Access Foundation
- Published
- 2007-03-09
- Volume
- 28
- Pages
- 267-297
- ISSN
- 1076-9757 (ISSN-L)
- OpenAlex
- W1622225657
- Cited by
- 259
- References
- 28
- FWCI
- 14.97
- Type
- journal article
- Language
- en
- Open access
- diamond
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.