A best-first search algorithm guided by a set-valued heuristic

Presents an algorithm, called A^G, for finding the least-cost path from start node to goal node set in an OR-graph, where arc costs are scalar-valued and the cost of each path is the sum of the concomitant arc costs. Search is guided by a set, H, of real-valued functions on the node set. Such a heuristic set can be a useful representation of knowledge acquired from human knowledge sources. If H={h: l⩽h} for given function l, then A^G essentially becomes A*. If H is bounded, then successors of the newly expanded node may not be placed on OPEN, the set of all generated nodes that are candidates for expansion. The authors address issues of termination, completeness, admissibility, and heuristic comparison. The authors then consider a less ambitious, and less numerically taxing, objective: find the first arc of a least-cost path from start node to goal node set. This objective is achieved by the algorithm 1A^G, a modification of A^G