The generalized A* architecture

We consider the problem of finding a lightest derivation of a global structure using a set of weighted rules. A large variety of inference problems in AI can be formulated within this framework. We generalize A * search, and heuristics derived from abstractions, to a broad class of lightest derivation problems. We also describe a new algorithm that searches for lightest derivations using a hierarchy of abstractions to guide the computation. We discuss how the algorithms described here can be used to address the pipeline problem — the problem of passing information back and forth between various stages of processing in a perceptual system. We consider examples in computer vision and natural language processing. We apply the hierarchical search algorithm to the problem of estimating the boundaries of convex objects in grayscale images and compare it to other search methods. A second set of experiments demonstrate the use of a new compositional curve model for finding salient curves in images. 1