RI: High Performance Algorithms for Probabilistic and Deterministic Graphical Models

RI：概率性和确定性图形模型的高性能算法

• 批准号: 0713118
• 负责人: Rina Dechter
• 金额: $ 44.97万
• 依托单位: University of California-Irvine
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2007
• 资助国家: 美国
• 起止时间: 2007-08-15 至 2012-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0713118&HistoricalAwards=false
• 关键词: RI; Performance; Algorithms; Probabilistic; Deterministic

Proposal 0713118"RI: High Performance Algorithms for Probablistic and Deterministic graphical ModelsPI: Rina DechterUniversity of California--IrvineABSTRACTThe goal of this project is to develop powerful algorithms that can help computer programs make sophisticated decisions when faced with real-life problems. The project's novelty is its specific focus on automated reasoning where the relevant information is a combination of certain (deterministic) and uncertain (probabilistic) information. The need to accommodate both types of information is motivated by many real world problems such as scheduling of operating rooms and the diagnosing the nature of a disease, where situation assessment, planning or decision-making often involve taking into consideration both hard constraints and probabilistic information. A unique aspect of the project is that its algorithms will be founded upon a single theoretical framework--AND/OR search, developed by the investigator--which is driven by the graphical representation of the problems and often results in exponentially reduced complexities. The guiding principle behind the algorithms is the exploitation of useful structural features of a given problem instance, such as decomposability, sub-problem equivalence, and sub-problem irrelevance. The work proposed here promises to enhance problem-solving knowledge not just in the field of artificial intelligence, but also in the scientific community in general. As they are completed, the new algorithms will be posted on a publicly available Web site.

提案 0713118“RI：概率性和确定性图形模型的高性能算法 PI：Rina Dechter 加州大学欧文分校 摘要 该项目的目标是开发强大的算法，可以帮助计算机程序在面对现实生活问题时做出复杂的决策。该项目的新颖性在于它特别关注自动推理，其中相关信息是某些（确定性）和 不确定（概率）信息。容纳这两种类型的信息的需要是由许多现实世界的问题引起的，例如手术室的调度和疾病的性质诊断，其中情况评估、规划或决策通常涉及考虑硬约束和概率信息。该项目的一个独特之处在于，其算法将建立在一个单一的理论框架之上——由研究者开发的 AND/OR 搜索——该框架是由研究人员开发的 通过问题的图形表示，通常会导致复杂性呈指数级降低。算法背后的指导原则是利用给定问题实例的有用结构特征，例如可分解性、子问题等价性和子问题不相关性。这里提出的工作有望增强解决问题的知识，不仅在人工智能领域，而且在整个科学界。当它们完成时， 新算法将发布在公开网站上。