Conformant plans and beyond: Principles and complexity Export

@article{citeulike:6076181, abstract = {Conformant planning is used to refer to planning for unobservable (non-deterministic) problems whose solutions, like classical planning, are linear sequences of operators called linear plans. The term 'conformant' is automatically associated with both the unobservable planning model and with linear plans, partly because the only possible solutions for unobservable problems are linear plans. In this paper we show that linear plans are not only meaningful for unobservable problems but for partially-observable problems as well. In such case, the execution of a linear plan generates observations from the environment which are collected by the agent during the execution of the plan and that are used at the end in order to determine whether the goal had been achieved or not; this is the typical case in problems of diagnosis in which all the actions are knowledge-gathering actions. There are substantial differences about linear plans for the case of unobservable and fully-observable problems, and for the case of partially-observable problems: while linear plans for the former model must must conform with properties in state space, linear plans for partially-observable problems must conform with properties in belief space. This differences surface when the problems are allowed to express epistemic goals and conditions using modal logic, and place the plan-existence decision problem in different complexity classes. Linear plans is one extreme point in a discrete spectrum of solution forms for planning problems. The other extreme point is contingent plans in which there is a branch point for every possible observation at each time step, and thus the number of branch points is not bounded a priori. In the middle of the spectrum, there are plans with a bounded number of branch points. Thus, linear plans are plans with zero branch points and contingent plans are plans with unbounded number of branch points. In this paper, we lay down foundations and principles for the general treatment of linear plans and plans of bounded branching, and provide exact complexity results for novel decision problems. We also show that linear plans for partially-observable problems are not only of theoretical interest since some challenging real-life problems can be dealt with them.}, author = {Bonet, Blai}, citeulike-article-id = {6076181}, citeulike-linkout-0 = {http://dx.doi.org/10.1016/j.artint.2009.11.001}, citeulike-linkout-1 = {http://linkinghub.elsevier.com/retrieve/pii/S0004370209001234}, day = {03}, doi = {10.1016/j.artint.2009.11.001}, issn = {00043702}, journal = {Artificial Intelligence}, month = {November}, posted-at = {2009-11-05 19:13:10}, title = {Conformant plans and beyond: Principles and complexity}, url = {http://dx.doi.org/10.1016/j.artint.2009.11.001}, year = {2009} }

TY - JOUR ID - citeulike:6076181 L3 - citeulike-article-id:6076181 N2 - Conformant planning is used to refer to planning for unobservable (non-deterministic) problems whose solutions, like classical planning, are linear sequences of operators called linear plans. The term ‘conformant’ is automatically associated with both the unobservable planning model and with linear plans, partly because the only possible solutions for unobservable problems are linear plans. In this paper we show that linear plans are not only meaningful for unobservable problems but for partially-observable problems as well. In such case, the execution of a linear plan generates observations from the environment which are collected by the agent during the execution of the plan and that are used at the end in order to determine whether the goal had been achieved or not; this is the typical case in problems of diagnosis in which all the actions are knowledge-gathering actions. There are substantial differences about linear plans for the case of unobservable and fully-observable problems, and for the case of partially-observable problems: while linear plans for the former model must must conform with properties in state space, linear plans for partially-observable problems must conform with properties in belief space. This differences surface when the problems are allowed to express epistemic goals and conditions using modal logic, and place the plan-existence decision problem in different complexity classes. Linear plans is one extreme point in a discrete spectrum of solution forms for planning problems. The other extreme point is contingent plans in which there is a branch point for every possible observation at each time step, and thus the number of branch points is not bounded a priori. In the middle of the spectrum, there are plans with a bounded number of branch points. Thus, linear plans are plans with zero branch points and contingent plans are plans with unbounded number of branch points. In this paper, we lay down foundations and principles for the general treatment of linear plans and plans of bounded branching, and provide exact complexity results for novel decision problems. We also show that linear plans for partially-observable problems are not only of theoretical interest since some challenging real-life problems can be dealt with them. JF - Artificial Intelligence SN - 00043702 TI - Conformant plans and beyond: Principles and complexity AU - Bonet, Blai PY - 2009/11/03/ UR - http://dx.doi.org/10.1016/j.artint.2009.11.001 ER -