Solving Sequential Planning Problems via Constraint Satisfaction

Issue title: Methodologies for Intelligent Systems

Article type: Research Article

Authors: Barták, Roman | Toropila, Daniel

Affiliations: Faculty of Mathematics and Physics, Charles University, Malostranské nám. 2/25, 118 00 Prague, Czech Republic. E-mail: Roman.Bartak@mff.cuni.cz | Computer Science Center, Charles University, Ovocný trh 5, 116 36 Prague, Czech Republic. E-mail: Daniel.Toropila@mff.cuni.cz

Abstract: Planning problems deal with finding a sequence of actions that transfer the initial state of the world into a desired state. Frequently such problems are solved by dedicated algorithms but there exist planners based on translating the planning problem into a different formalism such as constraint satisfaction or Boolean satisfiability and using a general solver for this formalism. The paper describes how to enhance existing constraintmodels of sequential planning problems by using techniques such as symmetry breaking (dominance rules), singleton consistency, nogoods, lifting, or techniques motivated by the partial-order planning.

Keywords: planning, constraint models, symmetry breaking, lifting, redundant constraints, search strategy

DOI: 10.3233/FI-2010-242

Journal: Fundamenta Informaticae, vol. 99, no. 2, pp. 125-145, 2010