Pavel Surynek's Academic Page | Doctoral Dissertation

Doctoral Dissertation

English version  |  Czech version     


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):

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

Copyright © 2003-2014