Probabilistic Hierarchical Planning over MDPs

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 in 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 given HTNs is bounded by the total number of tasks in the HTNs and show that from the Earley graph we can then construct a plan for a given task that has the maximum expected value when it is executed in an MDP environment.
Original languageEnglish
Title of host publicationProceedings of the Tenth International Conference on Autonomous Agents and Multiagent Systems
Number of pages2
Publication statusPublished - May 2011
Externally publishedYes

Bibliographical note

Acknowledgement: This research was sponsored by the U.S. Army Research Laboratory and the U.K. Ministry of Defence and was accomplished under Agreement Number W911NF-09-2-0053. The views and conclusions contained in this document are those of the author(s) and should not be interpreted as representing the official policies, either expressed or implied, of the U.S. Army Research Laboratory, the U.S. Government, the U.K. Ministry of Defence or the U.K. Government. The U.S. and U.K. Governments are authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation hereon.


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

Cite this