"Unrolling" complex task models into MDPs
Robert P. Goldman, David J. Musliner, Mark Boddy, Edmund H. Durfee, Jianhui Wu · National Conference on Artificial Intelligence · 2007
Markov Decision Processes (MDPs) provide a unifying theoretical framework for reasoning about action under uncertainty. For some domains (e.g., navigation in discrete space), MDPs may even provide a direct path to implementing a solution. However, many AI approaches, such as domainindependent planning, rely on richly expressive task models. For such problems, one way to proceed is to provide a translation from more expressive task models into MDP representations. We have developed a technique for “unrolling” such task models into an MDP state space that can be solved for an (approximately) optimal policy. In this paper, we describe how we have built a decisiontheoretic agent that solves planning/scheduling problems formulated in a dialect of the TAEMS hierarchical task language. One problem with bridging from TAEMS (and other expressive languages) to MDPs is that these other languages may not make the same simplifying assumptions as those behind MDPs. For example TAEMS task models have nonMarkovian aspects in which actions taken have effects only after a delay period. The task of reformulating a TAEMS planning problem into an MDP is complicated by the fact that TAEMS actions must be scheduled against global time, and by the presence of non-Markovian constructs in TAEMS models (actions with delayed effects). In this paper we describe both how we translate these TAEMS features into MDPs and how we cope with the state space explosion that can result. TAEMS task problems translate into finite-horizonMDPs, and the utility of outcomes cannot, in general, be determined until reaching the final state; in this way they are goal-focused and offer limited traction to approaches that exploit interim reward information. We also describe several optimizations that make the planning problem easier, notably aggressive pruning of actions, collapsing together equivalent states in the state space, and lazy exploration of the state space.