Efficient Encodings of Cost Optimal Delete-Free Planning as SAT

Masood Feyzbakhsh Rankooh, Jussi Rintanen

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Abstract

We introduce a novel method for encoding cost optimal delete-free STRIPS Planning as SAT. Our method is based on representing relaxed plans as partial functions from the set of propositions to the set of actions. This function can map any proposition to a unique action that adds the proposition during execution of the relaxed plan. We show that a relaxed plan can be produced by maintaining acyclicity in the graph of all causal relations among propositions, represented by the mentioned partial function. We also show that by efficient encoding of action cost propagation and enforcing a series of upper bounds on the total costs of the output plan, an optimal plan can effectively be produced for a given delete-free STRIPS problem. Our empirical results indicate that this method is quite competitive with the state of the art, demonstrating a better coverage compared to that of competing methods on standard STRIPS planning benchmark problems.
Original languageEnglish
Title of host publicationProceedings of the AAAI Conference on Artificial Intelligence
PublisherAAAI PRESS
Pages9910-9917
Number of pages8
ISBN (Print)978-1-57735-876-3
DOIs
Publication statusPublished - 28 Jun 2022
MoE publication typeA4 Article in a conference publication
EventAAAI Conference on Artificial Intelligence - virtual conference, Virtual, Online
Duration: 22 Feb 20221 Mar 2022
Conference number: 36
https://aaai.org/Conferences/AAAI-22/

Publication series

NameProceedings of the AAAI Conference on Artificial Intelligence
Number9
Volume36
ISSN (Print)2159-5399
ISSN (Electronic)2374-3468

Conference

ConferenceAAAI Conference on Artificial Intelligence
Abbreviated titleAAAI
CityVirtual, Online
Period22/02/202201/03/2022
Internet address

Fingerprint

Dive into the research topics of 'Efficient Encodings of Cost Optimal Delete-Free Planning as SAT'. Together they form a unique fingerprint.

Cite this