Thesis

Heuristically guided constraint satisfaction for AI planning

Creator
Rights statement
Awarding institution
  • University of Strathclyde
Date of award
  • 2015
Thesis identifier
  • T14285
Person Identifier (Local)
  • 200874995
Qualification Level
Qualification Name
Department, School or Faculty
Abstract
  • 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).
Resource Type
DOI
Date Created
  • 2015
Former identifier
  • 9912517291302996

Las relaciones

Elementos