Collaborative Research: The Generalized A* Architecture for Perceptual Systems

协作研究：感知系统的通用 A* 架构

• 批准号: 0535174
• 负责人: David McAllester
• 金额: $ 15.55万
• 依托单位: Toyota Technological Institute at Chicago
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2006
• 资助国家: 美国
• 起止时间: 2006-03-01 至 2009-02-28
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0535174&HistoricalAwards=false
• 关键词: Collaborative; Research; Generalized; Architecture; Perceptual

Proposals 0535174 (Lead) and 0534820"Collaborative research: The Generalized A* Architecture for Perceptual Systems"PI: David McAllester (Lead)Toyota Technological Institute at ChicagoPI: Pedro FelzenswalbUniversity of ChicagoABSTRACTThis 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.

提案0535174(牵头)和0534820“协作研究：感知系统的通用A*架构”PI：David McAllester(牵头)芝加哥丰田技术研究所PI：Pedro Felzenswalb芝加哥大学。这项研究调查了解决感知和概率推理中出现的广泛问题的方法。这项工作集中在最低成本结构问题上，目标是找到一种在一套组成规则下可派生的最低成本结构。这种成本最低的结构可以是解析树、可变形模型与图像的匹配、或马尔可夫随机场中变量的赋值。所研究的算法是基于A*搜索的推广和对任意最小代价结构问题的抽象。寻找成本最低的抽象结构通常比寻找成本最低的具体结构效率高得多。此外，最小代价抽象结构在A*搜索的意义上提供了解决具体优化问题的启发式指导。广义A*使用跨越感知系统的所有处理级别的抽象结构来指导在抽象空间的层次中寻找更具体的结构。预计该项目将产生广泛影响，为设计和实施视觉系统、语言处理系统和概率推理系统提供新的技术和软件工具。