This research investigates methods for solving a broad class of problems that arise in perception and probabilistic reasoning. The work focuses on least-cost structure problems where the goal is to find a least-cost structure derivable under a set of compositional rules. This least-cost structure might be a parse tree, a match of a deformable model to an image, or an assignment of values to variables in a Markov random field. The algorithms investigated are based on a generalization of A* search and abstractions to arbitrary least-cost structure problems. Finding the least-cost abstract structure is typically vastly more efficient than finding the least-cost concrete structure. Furthermore, the least-cost abstract structure provides heuristic guidance, in the sense of A* search, in solving the concrete optimization problem. Generalized A* uses abstract structures spanning all levels of processing of a perceptual systems in guiding the search for more concrete structures in a hierarchy of abstraction spaces. This project is expected to have broad impact by providing new techniques and software tools for the design and implementation of vision systems, language processing systems and probabilistic reasoning systems in general.
