Conformant Planning via Model Checking

@incollection{cimatti00conformant, abstract = {Conformant planning is the problem of finding a sequence of actions that is guaranteed to achieve the goal for any possible initial state and nondeterministic behavior of the planning domain. In this paper we present a new approach to conformant planning. We propose an algorithm that returns the set of all conformant plans of minimal length if the problem admits a solution, otherwise it returns with failure. Our work is based on the planning via model checking paradigm, and relies on symbolic techniques such as Binary Decision Diagrams to compactly represent and efficiently analyze the planning domain. The algorithm, called cmbp, has been implemented in the mbp planner. cmbp is strictly more expressive than the state of the art conformant planner sc cgp. Furthermore, an experimental evaluation suggests that cmbp is able to deal with uncertainties more efficiently than cgp.}, author = {Cimatti, Alessandro and Roveri, Marco }, citeulike-article-id = {3038749}, doi = {10.1007/10720246\_2}, journal = {Recent Advances in AI Planning}, keywords = {da, model-checking, planning, project-planning}, pages = {21--34}, posted-at = {2008-07-24 09:58:00}, priority = {2}, title = {Conformant Planning via Model Checking}, url = {http://dx.doi.org/10.1007/10720246\_2}, year = {2000} }

TY - CHAP ID - cimatti00conformant L3 - citeulike-article-id:3038749 TI - Conformant Planning via Model Checking JF - Recent Advances in AI Planning SP - 21 EP - 34 N2 - Conformant planning is the problem of finding a sequence of actions that is guaranteed to achieve the goal for any possible initial state and nondeterministic behavior of the planning domain. In this paper we present a new approach to conformant planning. We propose an algorithm that returns the set of all conformant plans of minimal length if the problem admits a solution, otherwise it returns with failure. Our work is based on the planning via model checking paradigm, and relies on symbolic techniques such as Binary Decision Diagrams to compactly represent and efficiently analyze the planning domain. The algorithm, called cmbp, has been implemented in the mbp planner. cmbp is strictly more expressive than the state of the art conformant planner sc cgp. Furthermore, an experimental evaluation suggests that cmbp is able to deal with uncertainties more efficiently than cgp. KW - da KW - model-checking KW - planning KW - project-planning AU - Cimatti, Alessandro AU - Roveri, Marco PY - 2000/// UR - http://dx.doi.org/10.1007/10720246_2 ER -