**Constraint Programming in Planning**

**Abstract:** This thesis deals with *planning problems* and *Boolean satisfiability problems* that
represent major challenges for *artificial intelligence*.

*Planning problems* are stated as finding a sequence of actions that reaches certain goal.
One of the most successful techniques for solving planning problems is a concept of *planning graphs*
and the related *GraphPlan algorithm*. In the thesis we identified a weak point of the original
GraphPlan algorithm which is the search for actions that support certain goal. We proposed to model
this problem as a constraint satisfaction problem and we solve it by maintaining *arc-consistency*.
Several propagation variants for maintaining arc consistency in the model are proposed. The model
and its solving process were integrated into the general GraphPlan-based planning algorithm. The
performed experimental evaluation showed improvements in order of magnitude in several measured
characteristics (overall solving time, number of backtracks) compared to the standard version of the
GraphPlan algorithm.

Next we proposed a stronger consistency technique for pruning the search space during solving the
problem of finding supports. It is called *projection consistency* and it is based on disentangling
the structure of the problem formulation. If the problem of finding sup-porting actions is
interpreted as a graph then this graph is typically well structured - it consists of a small number
of relatively large complete sub graphs. We exploit this structural information to rule out actions
from further consideration using a special reasoning. This process reduces the search space
significantly. The performed experimental evaluation showed again significant improvements compared
to the previous method based on arc-consistency.

Finally, we proposed a special class of the problem of finding supporting actions that can be
solved in polynomial time. Thus if the problem satisfies certain conditions it becomes easy to
solve (it belongs to the *class of tractable problems* - *tractable class*). We also proposed
heuristics that guide the solving process and simplify the problem to become tractable in early stage
of the process. Experimental evaluation showed that the method based on preference of this class of
problems performs best of all the developed methods. Moreover, some of the planning problems were solved without
backtracking. The experiments also showed that this method is competitive with state-of-the-art
planners on certain problems.

The contribution of this thesis to solving Boolean satisfiability problems consists in developing
a special preprocessing method again based on disentangling the structural information encoded in
the problem. The developed method is called *clique consistency* - it is an adaptation of projection
consistency for the area of Boolean satisfiability. The preprocessing method either decides the
problem or passes the simplified problem to the general solving system. The performed experiments
showed that the clique consistency technique can improve the solving process of difficult classes
of Boolean satisfaction problems significantly in comparison with several state-of-the-art SAT
solvers.

Below you can **download** the full text of the doctoral dissertation (in English) and related materials (extended abstract in English,
PowerPoint presentation in English, and web presentation in English):

**Doctoral Dissertation** *(in English)*
**Extended Abstract** *(in English)*
**Web Presentation** *(in English)* [a separate web page]
**PowerPoint Presentation** *(in English)*

[PowerPoint 2007 format .pptx] [PowerPoint 2003 format .ppt]
**Attached Medium**

[compressed archive .zip] [browse individual files]

**Keywords:** AI planning, constraint programming, GraphPlan, planning graphs, projection consistency, clique consistency, CSP, SAT