PhD Defense: Goal Decomposition for Probabilistic Planning

Automated planning is essential for many applications, such as autonomous systems, robotics, and intelligent decision support, where agents must make sequential decisions and execute actions to achieve defined goals. However, as planning domains grow in scale and complexity, classical planning techniques sometimes struggle to generate effective plans. Goal decomposition is an approach to classical planning that applies divide-and-conquer principles to break down planning problems into smaller, more manageable subproblems, allowing planning systems to reason about each subproblem incrementally. Even so, the classical planning paradigm assumes complete, deterministic information about the environment and the effects of actions—an assumption that often does not hold in dynamic, real-world scenarios.
This research builds upon two fundamental goal decomposition approaches from classical planning and extends them to probabilistic planning: (1) landmarks, which are intermediate conditions satisfied at some point along every solution plan, and (2) hierarchical goal networks, which provide methods for decomposing goals into structured sequences of subgoals. For each approach, we develop extensions to Monte Carlo tree search that leverage goal decomposition information to guide planning under uncertainty. A comparative analysis of these methods leads to a unified framework for goal-network-directed probabilistic planning, in which both planners emerge as specific instantiations of a more general algorithm. By bridging goal decomposition and probabilistic planning, this research develops more scalable planning techniques for complex, uncertain domains, improving the applicability of planning systems to real-world sequential-decision-making problems.