RI: High Performance Algorithms for Probabilistic and Deterministic Graphical Models

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

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.