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

Mississippi State University, Mississippi State MS

Investigators

Abstract

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.