Efficient Encodings of Cost Optimal Delete-Free Planning as SAT

Masood Feyzbakhsh Rankooh, Jussi Rintanen

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussaConference contributionScientificvertaisarvioitu

Abstrakti

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.
AlkuperäiskieliEnglanti
OtsikkoProceedings of the AAAI Conference on Artificial Intelligence
KustantajaAAAI PRESS
Sivut9910-9917
Sivumäärä8
ISBN (painettu)978-1-57735-876-3
DOI - pysyväislinkit
TilaJulkaistu - 28 kesäk. 2022
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisuussa
TapahtumaAAAI Conference on Artificial Intelligence - virtual conference, Virtual, Online
Kesto: 22 helmik. 20221 maalisk. 2022
Konferenssinumero: 36
https://aaai.org/Conferences/AAAI-22/

Julkaisusarja

NimiProceedings of the AAAI Conference on Artificial Intelligence
Numero9
Vuosikerta36
ISSN (painettu)2159-5399
ISSN (elektroninen)2374-3468

Conference

ConferenceAAAI Conference on Artificial Intelligence
LyhennettäAAAI
KaupunkiVirtual, Online
Ajanjakso22/02/202201/03/2022
www-osoite

Sormenjälki

Sukella tutkimusaiheisiin 'Efficient Encodings of Cost Optimal Delete-Free Planning as SAT'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

Siteeraa tätä