Planning over MDPs through Probabilistic HTNs

Yuqing Tang, Felipe Meneguzzi, Katia Sycara, Simon Parsons

Research output: Chapter in Book/Report/Conference proceedingPublished conference contribution


In this paper, we propose a new approach to using probabilistic hierarchical task networks (HTNs) as an effective method for agents to plan under conditions in which their problem-solving knowledge is uncertain, and the environment is non-deterministic. In such situations it is natural to model the environment as a Markov Decision Process (MDP). We show that using Earley graphs, it is possible to bridge the gap between HTNs and MDPs. We prove that the size of the Earley graph created for any given HTN is bounded by the total number of tasks in the HTNs and show that from the Earley graph we can construct a plan for a given task that has the maximum expected utility when it is executed in an MDP environment.
Original languageEnglish
Title of host publicationProceedings of the AAAI-11 Workshop on Generalized Planning
Number of pages8
Publication statusPublished - 2011
Externally publishedYes


Dive into the research topics of 'Planning over MDPs through Probabilistic HTNs'. Together they form a unique fingerprint.

Cite this