Heuristically guided constraint satisfaction for AI planning

Standard Planning Domain Definition Language (PDDL) planning problem definitions may be reformulated and solved using alternative techniques. One such paradigm, Constraint Programming (CP), has successfully been used in various planner architectures in recent years. The efficacy of a given constraint reformulation depends on the encoding method, search technique(s) employed, and the consequent amount of propagation. Despite advances in this area, constraint based planners have failed to match the performance of other approaches. One reason for this is that the structural information that is implicit in the domain / problem instance description is lost in the reformulation process. Hence, to achieve better performance, a constraint based planner should have an appropriate encoding and a search procedure informed by the structure of the original problem. This thesis describes a system that aims to improve planner performance by employing such methods. The planner uses a table-constraint encoding together with a new variable / value ordering heuristic. This ordered, goal oriented guidance reduces the search space and better directs the search focus. The system also makes use of novel meta variable techniques for goal locking and resource assignment. These improve propagation and prune the search space. This CP based planning architecture is shown to perform well on a range of problem instances taken from recent International Planning Competitions (IPCs).

Name dc:type.qualificationname

phd

Level dc:type.qualificationlevel

doctoral-pg

Grantor dc:publisher.institution

University of Strathclyde

Year dc:date.issued

2015

Author dc:creator

• Judge, Mark

DOI

10.48730/2vm4-4x70

Identifier

T14285

Author Identifier

200874995

OAI identifier oai:identifier

oai:strathclyde:2514nk51b