Browse Prior Art Database

GENERALIZED BEST-FIRST SEARCH STRATEGIES AND THE OPTIMALITY OF A

IP.com Disclosure Number: IPCOM000128346D
Original Publication Date: 1984-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 36 page(s) / 85K

Publishing Venue

Software Patent Institute

Related People

Rina Dechter: AUTHOR [+4]

Abstract

'This paper reports several properties of heuristic best-first search strategies whose scor-ing functions f depend on all the information available from each candidate path, not merely on the current cost g and the estimated completion cost h. We show that several known properties of A* retain their form (with the min-max of f playing the role of the optimal cost) which help establish general tests of admissibility and general conditions for node expansion for these strategies. Using this framework we then examine the computational optimality of A*, in the sense of never expanding a node that could be skipped by some other algorithm having access to the same heuristic information that A* uses. We define a hierarchy of four op-timality types, and consider three classes of algorithms and four domains of problem in-stances relative to which computational performances are appraised. For each class-domain combination, we then identify the strongest type of optimality that exists and the algorithm achieving it. Our main results relate to the class of algorithms which, like A*, return optimal solutions (i.e., admissible) when all cost estimates are optimistic (i.e., hsh*). On this class we show that A' is not optimal and that no optimal algorithm ex-ists, but if we confine the performance tests to cases where the estimates are also con-sistent, then A' is indeed optimal. Additionally, we show that A* is optimal over a sub-set of the latter class containing all best-first algorithms that are guided by path-dependent evaluation functions.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 6% of the total text.

Page 1 of 36

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

GENERALIZED BEST-FIRST SEARCH STRATEGIES AND THE OPTIMALITY OF A*

Rina Dechter Judea Pearl December 1984 Report No. CSD UCIA-CSD-84 June 1984 GEN'E,FALMFn BEST FIRST SEARCH MATEGIES AND THE OPTIMALtI'Y OF A'

Rina Dechter and Judea Pearl

Cognitive systems Laboratory computer science University of California

..... , Los Angelus, CA 90024 This work was supported in part by the National Science
Foundation, Grant FMCS 8114209

ABSTRACT

'This paper reports several properties of heuristic best-first search strategies whose scor-ing functions f depend on all the information available from each candidate path, not merely on the current cost g and the estimated completion cost h. We show that several known properties of A* retain their form (with the min-max of f playing the role of the optimal cost) which help establish general tests of admissibility and general conditions for node expansion for these strategies.

Using this framework we then examine the computational optimality of A*, in the sense of never expanding a node that could be skipped by some other algorithm having access to the same heuristic information that A* uses. We define a hierarchy of four op-timality types, and consider three classes of algorithms and four domains of problem in-stances relative to which computational performances are appraised. For each class-domain combination, we then identify the strongest type of optimality that exists and the algorithm achieving it. Our main results relate to the class of algorithms which, like A*, return optimal solutions (i.e., admissible) when all cost estimates are optimistic (i.e., hsh*). On this class we show that A' is not optimal and that no optimal algorithm ex-ists, but if we confine the performance tests to cases where the estimates are also con-sistent, then A' is indeed optimal. Additionally, we show that A* is optimal over a sub-set of the latter class containing all best-first algorithms that are guided by path- dependent evaluation functions.

1. INTRODUCTION AND PRELEWNARIES

Of all search strategies used in problem solving, one of the most popular methods of exploiting heuristic information to cut down search time is the informed best-first stra-tegy. The general philosophy of this strategy is to use the heuristic information to assess the "merit" latent in every candidate search avenue exposed during the search, then con-tinue the exploration along the direction of highest merit. Formal descriptions of this strategy are usually given in the context of path searching problems (Pearl, 1984), a for-mulation which represents many combinatorial problems such as routing, scheduling, speech recognition, scene analysis, and others.

Given a weighted directional graph G with a distinguished start node s and a set of goal nodes T, the optimal path problem is to find a least-cost path from s to any member of T where the

UCLA Page 1 Dec 31, 1984

Page 2 of 36

GENERAL...