RI: High Performance Algorithms for Probabilistic and Deterministic Graphical Models

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

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.