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

Masood Feyzbakhsh Rankooh, Jussi Rintanen

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

Abstract

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.
Original languageEnglish
Title of host publicationProceedings of the International Conference on Automated Planning and Scheduling (ICAPS)
EditorsAkshat Kumar, Sylvie Thiebaux, Pradeep Varakantham, William Yeoh
PublisherAAAI PRESS
Pages71-79
Number of pages9
ISBN (Electronic)9781577358749
DOIs
Publication statusPublished - 13 Jun 2022
MoE publication typeA4 Article in a conference publication
EventInternational Conference on Automated Planning and Scheduling - Singapore, Singapore
Duration: 13 Jun 202224 Jun 2022
Conference number: 32
https://icaps22.icaps-conference.org/

Publication series

NameProceedings of the International Conference on Automated Planning and Scheduling
Volume32
ISSN (Print)2334-0835
ISSN (Electronic)2334-0843

Conference

ConferenceInternational Conference on Automated Planning and Scheduling
Abbreviated titleICAPS
Country/TerritorySingapore
CitySingapore
Period13/06/202224/06/2022
Internet address

Fingerprint

Dive into the research topics of 'Efficient Computation and Informative Estimation of h+ by Integer and Linear Programming'. Together they form a unique fingerprint.

Cite this