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

RI：小型：在决策理论规划中集成图形模型的新方法

• 批准号: 1718384
• 负责人: Eric Hansen
• 金额: $ 42.7万
• 依托单位: Mississippi State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2017
• 资助国家: 美国
• 起止时间: 2017-08-15 至 2023-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1718384&HistoricalAwards=false
• 关键词: RI; Small; New; Approach; Integrating

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.

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

项目成果

Strategy Representation and Compression for Influence Diagrams

影响图的策略表示和压缩

• 发表时间: 2018-01
• 期刊: 15th International Symposium on Artificial Intelligence and Mathematics
• 作者: Shi, Jinchuan;Hansen, Eric A.
• 通讯作者: Hansen, Eric A.

Improved Vector Pruning in Exact Algorithms for Solving POMDPs

求解 POMDP 的精确算法中改进的向量剪枝

• 发表时间: 2020-08
• 期刊: PMLR
• 作者: Hansen, Eric A.;Bowman, Thomas
• 通讯作者: Bowman, Thomas

Strategy Graphs for Influence Diagrams

影响图的策略图

• DOI: 10.1613/jair.1.13865
• 发表时间: 2022-09
• 期刊: Journal of Artificial Intelligence Research
• 影响因子: 5
• 作者: Hansen, Eric A.;Shi, Jinchuan;Kastrantas, James
• 通讯作者: Kastrantas, James

Strategy Representation and Compression for Influence Diagrams

影响图的策略表示和压缩

• 发表时间: 2018-01
• 期刊: Fifteenth International Symposium on Artificial Intelligence and Mathematics
• 作者: Shi, Jinchuan;Hansen, Eric A.
• 通讯作者: Hansen, Eric A.

An integrated approach to solving influence diagrams and finite-horizon partially observable decision processes

求解影响图和有限范围部分可观察决策过程的集成方法

• DOI: 10.1016/j.artint.2020.103431
• 发表时间: 2021-05
• 期刊: Artificial Intelligence
• 影响因子: 14.4
• 作者: Hansen; Eric A.
• 通讯作者: Eric A.