Efficient Encoding of Cost Optimal Delete-Free Planning as SAT

Masood Feyzbakhsh Rankooh, Jussi Rintanen

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


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
Number of pages8
ISBN (Print)978-1-57735-876-3
Publication statusPublished - 28 Jun 2022
MoE publication typeA4 Conference publication
EventAAAI Conference on Artificial Intelligence - virtual conference, Virtual, Online
Duration: 22 Feb 20221 Mar 2022
Conference number: 36

Publication series

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


ConferenceAAAI Conference on Artificial Intelligence
Abbreviated titleAAAI
CityVirtual, Online
Internet address


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

Cite this