RI:Small:Tractable Decision-Theoretic Planning Driven by Data

University Of Georgia Research Foundation Inc, Athens GA

Investigators

Abstract

Automated planning is about finding a sequence of actions that is expected to successfully complete the task at hand. Decision-theoretic planning approaches automated planning as a sequence of decisions, each of which optimizes the planner's combined immediate and longer-term preferences. This approach to automated planning allows for realistic actions whose outcomes are often uncertain and reasons with the planner's possibly inexact preferences in addition to precise goals. However, decision-theoretic planning relies on an accurate specification of the planning problem, which is often impractical and is computationally very costly. This research is addressing these challenges by investigating a new and meaningful planning problem representation that is learned directly from data, which alleviates the need for tedious specifications. The representation is designed to yield more efficient computation of solutions. Consequently, this research has the potential to transition automated planning to large pragmatic applications, such as in flow routing in high-density computer networks, which will be demonstrated in this project. The project will train graduate students for entering the workforce in an important area of artificial intelligence, and it will facilitate an international research collaboration between researchers in US and Canada. The PI will use the outcomes of this research to inform his classroom instruction, which will provide students with exposure to how automated planning can be useful to the society. The technical approach is merging two threads of previous progress toward developing a new graphical model called the dynamic sum-product-max network. In these previous threads, the PI generalized sum-product networks, which allow efficient probabilistic inference, in two directions. First, along the temporal dimension thereby allowing inference over a sequence of variables, and second, enabling efficient non-sequential decision making by including decision and utility variables. This research is reconciling the fundamental hardness of decision-theoretic planning with the efficiency of dynamic sum-product-max networks by studying which class of planning problems can be compactly represented by the new model. As these models can be directly learned from data, the research is also establishing the appropriate schema for the data and creating an evaluation testbed of datasets. A final thrust is developing a portfolio of methods for automatically learning both the structure and parameters of dynamic sum-product-max networks from appropriate data, with a focus on learning valid models. The research plan is expected to yield a new graphical representation and associated methods that allow efficient data-driven planning whose utility will be demonstrated by real-world applications in collaboration with industry. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.