Heuristically guided constraint satisfaction for AI planning

  • Mark Judge

Student thesis: Doctoral Thesis

Abstract

Standard Planning Domain Definition Language (PDDL) planning problemdefinitions may be reformulated and solved using alternative techniques.One such paradigm, Constraint Programming (CP), has successfullybeen used in various planner architectures in recent years.The efficacy of a given constraint reformulation depends on the encodingmethod, search technique(s) employed, and the consequent amount ofpropagation.Despite advances in this area, constraint based planners have failed tomatch the performance of other approaches. One reason for this is thatthe structural information that is implicit in the domain / problem instancedescription is lost in the reformulation process.Hence, to achieve better performance, a constraint based planner shouldhave an appropriate encoding and a search procedure informed by thestructure of the original problem. This thesis describes a system that aimsto 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 reducesthe search space and better directs the search focus.The system also makes use of novel meta variable techniques for goallocking and resource assignment. These improve propagation and prunethe search space.This CP based planning architecture is shown to perform well on a range ofproblem instances taken from recent International Planning Competitions(IPCs).
Date of Award1 Apr 2011
LanguageEnglish
Awarding Institution
  • University Of Strathclyde
SponsorsEPSRC (Engineering and Physical Sciences Research Council)

Cite this