On representing planning domains under uncertainty
Felipe Rech Meneguzzi, Yuqing Tang, Katia P. Sycara, Simon Parsons · 2010
Abstract—Planning is an important activity in military coali-tions and the support of an automated planning tool could help military planners by reducing the cognitive burden of their work. Current AI planning paradigms use two different types of formalism to represent the planning problem. Each of these formalisms entails different inference algorithms and representation of results. On the one hand plans in non-stochastic domains are rep-resented using declarative logic-based formalisms, an example of which is Hierarchical Task Networks (HTNs). In HTNs, domains are represented in terms of task decompositions of increased detail in relation to the actions that must be carried out. In general, declarative formalisms are easier for humans to understand. On the other hand, stochastic planning is often rep-resented in terms of large probability functions that exhaustively specify the likelihood of relevant world changes when actions are executed, as exemplified by Markov Decision Processes (MDPs). Stochastic domain specifications can easily become challenging to a human designer as the problem size increases, worse still, solver algorithms degrade quickly with increased domain size. In order to facilitate domain modeling for planning under uncertainty, we propose a method of deriving stochastic domain specifications in the MDP formalism from a description using the HTN formalism. This method can reduce the resulting MDP state-space through an intermediate representation using Binary Decision Diagrams (BDDs). The benefits of the approach are twofold: (a) the reduction of the state space, and consequent re-duction of computational burden is beneficial since it enables the representation and solving of realistic planning problems, and (b) starting from a declarative representation makes planning more comprehensible to humans, while extending the representation to stochastic domains. I.