ECAI-2000 Conference Paper

[full paper]

Flexible Graphplan

Ian Miguel, Peter Jarvis, Qiang Shen

Traditionally, planning problems are cast in terms of imperative constraints that are either wholly satisfied or wholly violated. It is argued herein that this framework is too rigid to capture the full subtlety of many real problems. A new flexible planning problem is defined which supports the soft constraints often found in reality. A solution strategy using the Graphplan framework is described and it is shown how flexible plan extraction can be cast as the solution of a sequence of linked Dynamic Flexible Constraint Satisfaction Problems (DFCSPs). A recently developed DFCSP algorithm, Flexible Local Changes, is exploited to solve this sequence. For a given flexible problem, this framework can synthesise a range of plans that trade the compromises made in a plan versus plan length. The proposed technique is evaluated on a range of flexible problems and against leading boolean solvers on benchmark problems.

Keywords: Planning, Constraint Satisfaction

Citation: Ian Miguel, Peter Jarvis, Qiang Shen: Flexible Graphplan . In W.Horn (ed.): ECAI2000, Proceedings of the 14th European Conference on Artificial Intelligence, IOS Press, Amsterdam, 2000, pp.506-510.