Efficient Computation and Informative Estimation of h+ by Integer and Linear Programming

Masood Feyzbakhsh Rankooh, Jussi Rintanen

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussaConference contributionScientificvertaisarvioitu

Abstrakti

We investigate modeling cost optimal delete-free STRIPS Planning by Integer/Linear Programming (IP/LP). We introduce two IP models and their LP relaxations based on a recently formulated representation of relaxed plans, named causal relaxed plan representation. The new models are produced by enforcing acyclicity in so-called causal relation graphs using vertex elimination and time labeling methods. We empirically show that while the vertex elimination based method outperforms the time labeling based method and all previously introduced domain independent methods for computing the exact values of h+, the time labeling based LP model is faster to solve compared to its vertex elimination based alternative, making it more suitable for using as heuristic function for optimal planning. We also theoretically analyze the admissible heuristic functions obtained by solving our LP models, and prove that the vertex elimination based heuristic is at least as informative as the time labeling based heuristic. Moreover, our empirical analysis shows that our vertex elimination based heuristic, which is a novel admissible estimation of h+, often has information complementary to that of the LM-cut heuristic.
AlkuperäiskieliEnglanti
OtsikkoProceedings of the International Conference on Automated Planning and Scheduling (ICAPS)
ToimittajatAkshat Kumar, Sylvie Thiebaux, Pradeep Varakantham, William Yeoh
KustantajaAAAI PRESS
Sivut71-79
Sivumäärä9
ISBN (elektroninen)9781577358749
DOI - pysyväislinkit
TilaJulkaistu - 13 kesäk. 2022
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisuussa
TapahtumaInternational Conference on Automated Planning and Scheduling - Singapore, Singapore
Kesto: 13 kesäk. 202224 kesäk. 2022
Konferenssinumero: 32
https://icaps22.icaps-conference.org/

Julkaisusarja

NimiProceedings of the International Conference on Automated Planning and Scheduling
Vuosikerta32
ISSN (painettu)2334-0835
ISSN (elektroninen)2334-0843

Conference

ConferenceInternational Conference on Automated Planning and Scheduling
LyhennettäICAPS
Maa/AlueSingapore
KaupunkiSingapore
Ajanjakso13/06/202224/06/2022
www-osoite

Sormenjälki

Sukella tutkimusaiheisiin 'Efficient Computation and Informative Estimation of h+ by Integer and Linear Programming'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

Siteeraa tätä