RI: Small: A New Approach to Integrating Graphical Models in Decision-Theoretic Planning

该项目解决了人工智能研究的核心问题之一：在不确定性和不完美信息下的规划或顺序决策问题。规划算法广泛用于工程和商业中的控制和决策问题，在机器人、过程控制、物流、用户自适应系统、资源管理以及决策自动化有用的相关问题中有许多实际应用。该项目考虑了两个广泛使用的决策理论框架下的规划不确定性和不完美的信息，这是部分可观察的马尔可夫决策过程和影响图，并整合这两个框架在一个新的方式，利用其互补优势。该项目通过展示如何推广求解影响图的算法，特别是经典的变量消除算法，将这两个框架集成在一起，以便使用算法技术来解决部分可观察马尔可夫决策过程（POMDPs），以提高可扩展性，并更紧凑地表示计划和策略。在这个项目中开发的广义变量消除算法可以表现得像传统的算法求解影响图，或像传统的算法求解POMDPs，这取决于变量被消除的顺序。从这个角度来看，影响图和POMDP的算法，一旦出现不同的可以被视为特殊情况下，相同的，更一般的算法。更重要的是，这种观点允许这些互补的算法技术以新的方式结合起来，从而使规划算法具有更好的性能，更广泛的适用性和更好的解释结果。 该项目的重点是几个相关的研究问题，将扩展这种方法，使其在实践中更有用，包括变量消除排序的新算法的发展，通过利用问题结构，包括特定于上下文的独立性，和开发一个综合的方法，有界误差近似，将允许计划质量和计算时间之间的权衡。虽然该项目侧重于有限时域规划问题，但该集成方法也可用于解决具有非马尔可夫结构的无限时域规划问题。除了这项研究的智力影响，该项目将有助于教育，学生辅导和推广。

This project addresses one of the central problems of research in Artificial Intelligence: the problem of planning, or sequential decision making, under uncertainty and imperfect information. Planning algorithms are widely-used for control and decision-making problems in engineering and business, with many practical applications in robotics, process control, logistics, user-adaptive systems, resource management, and related problems where automation of decision making is useful. This project considers two widely-used decision-theoretic frameworks for planning under uncertainty and imperfect information, which are partially observable Markov decision processes and influence diagrams, and integrates these two frameworks in a novel way that leverages their complementary advantages. The project integrates these two frameworks by showing how to generalize algorithms for solving influence diagrams, especially classic variable elimination algorithms, so that they use algorithmic techniques for solving partially observable Markov decision processes (POMDPs) to improve scalability, as well as to represent plans and strategies more compactly. The generalized variable elimination algorithms developed in this project can behave like traditional algorithms for solving influence diagrams, or like traditional algorithms for solving POMDPs, depending on the order in which variables are eliminated. From this perspective, algorithms for influence diagrams and POMDPs that once appeared dissimilar can be viewed as special cases of the same, more general algorithm. More importantly, this perspective allows these complementary algorithmic techniques to be combined in new ways, leading to planning algorithms with improved performance, wider applicability, and easier-to-interpret results. The project focuses on several related research problems that will extend this approach and make it more useful in practice, including the development of new heuristics for variable elimination ordering, the development of approaches to improving planner performance by leveraging problem structure, including context-specific independence, and the development of an integrated approach to bounded-error approximation that will allow tradeoffs between plan quality and computation time. Although the project focuses on finite-horizon planning problems, the integrated approach may also be used in solving infinite-horizon planning problems with non-Markovian structure. In addition to the intellectual impact of this research, the project will contribute to education, student mentoring, and outreach.