Efficient flexible planning via dynamic flexible constraint satisfaction

Ian Miguel*, Qiang Shen, Peter Jarvis

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

13 Citations (Scopus)


Recent advances in AI planning have centred upon the reduction of planning to a constraint satisfaction problem (CSP) enabling the application of the efficient search algorithms available in this area. This paper continues this approach, presenting a novel technique which exploits (restriction/relaxation-based) dynamic CSP (rrDCSP) in order to further improve planner performance. Using the standard Graphplan framework, it is shown how significant efficiency gains may be obtained by viewing plan extraction as the solution of a hierarchy of such rrDCSPs. Furthermore, by using flexible constraints as a formal foundation, it is shown how the traditional boolean notion of planning can be extended to incorporate prioritised and preference-based information. Plan extraction in this context is shown to generalise the Boolean rrDCSP approach, being systematically supported by the recently developed solution techniques for dynamic flexible CSPs (DFCSPs). The proposed techniques are evaluated via benchmark boolean problems and a novel flexible benchmark problem. Results obtained are very encouraging.

Original languageEnglish
Pages (from-to)301-327
Number of pages27
JournalEngineering Applications of Artificial Intelligence
Issue number3
Publication statusPublished - Jun 2001


Dive into the research topics of 'Efficient flexible planning via dynamic flexible constraint satisfaction'. Together they form a unique fingerprint.

Cite this