Original title: Omezující podmínky v plánování
Translated title: Constraint Programming in Planning
Authors: Surynek, Pavel ; Barták, Roman (advisor) ; Vojtáš, Peter (referee) ; Štěpánková, Olga (referee)
Document type: Doctoral theses
Year: 2008
Language: eng
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 plan- ning 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-consis- tency 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...

Institution: Charles University Faculties (theses) (web)
Document availability information: Available in the Charles University Digital Repository.
Original record: http://hdl.handle.net/20.500.11956/84708

Permalink: http://www.nusl.cz/ntk/nusl-354523


The record appears in these collections:
Universities and colleges > Public universities > Charles University > Charles University Faculties (theses)
Academic theses (ETDs) > Doctoral theses