Domain-Independent Cost-Optimal Planning in ASP

• Author / Creator

  David Spies

• We examine various techniques in SAT-based (Satisfiability) planningand explore how they can be applied and further improved in the contextof ASP (Answer Set Programming). First, we look at the 2006 plannerSATPlan and show that their encoding, when translated directly intoASP, enjoys a significantly reduced search space over the very sameencoding in SAT. Next we tackle the problem of reducing the largeencoding size which prohibits the best SAT-based planners from handlingthe larger planning problems that appear in planning competitions.In particular we give a simple encoding for reducing the number ofexpressions required to handle action-mutex constraints. After thatwe tackle the problem of how to reduce the size of fluent-mutex constraintsand show that this can be done far more effectively than in previouswork by covering the mutex-graph with multicliques (complete multi-partitesubgraphs). Finally we address the problem of cost-optimal planningin ASP. While most attempts at planning in SAT have been either cost-agnosticor at best constrained to planning at a fixed-makespan, those thathave attempted to handle cost-optimal planning at any makespan introducesignificant space-overhead, to the point of prohibiting them fromtackling larger planning problems. We show that by exploiting stable modelsemantics, we can produce a far more space-efficient ASP-planner whichguarantees makespan-agnostic cost-optimality.Using lessons learned from this, we develop an entirely new anddifferent approach to planning, stepless planning which reduces the groundedproblem space even more and relies heavily on stable model semantics for itscorrectness.

• Subjects / Keywords

  • answer set programming
  • planning
  • cost-optimal

• Graduation date

  Spring 2019

• Type of Item

  Thesis

• Degree

  Master of Science

• DOI

  https://doi.org/10.7939/r3-c0mg-n910

• License

  Permission is hereby granted to the University of Alberta Libraries to reproduce single copies of this thesis and to lend or sell such copies for private, scholarly or scientific research purposes only. Where the thesis is converted to, or otherwise made available in digital form, the University of Alberta will advise potential users of the thesis of these terms. The author reserves all other publication and other rights in association with the copyright in the thesis and, except as herein before provided, neither the thesis nor any substantial portion thereof may be printed or otherwise reproduced in any material form whatsoever without the author's prior written permission.