Please use this identifier to cite or link to this item: doi:10.22028/D291-29342
Volltext verfügbar? / Dokumentlieferung
Title: LP Heuristics over Conjunctions : Compilation, Convergence, Nogood Learning
Author(s): Steinmetz, Marcel
Hoffmann, Jörg
Editor(s): Lang, Jérôme
Language: English
Title: Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence
Startpage: 4837
Endpage: 4843
Publisher/Platform: International Joint Conferences on Artificial Intelligence
Year of Publication: 2018
Place of publication: Menlo Park, County of San Mateo, California
Title of the Conference: IJCAI-ECAI-18
Place of the conference: Stockholm, Sweden
Publikation type: Conference Paper
Abstract: Two strands of research in classical planning are LP heuristics and conjunctions to improve approximations. Combinations of the two have also been explored. Here, we focus on convergence properties, forcing the LP heuristic to equal the perfect heuristic h* in the limit. We show that, under reasonable assumptions, partial variable merges are strictly dominated by the compilation Pi^C of explicit conjunctions, and that both render the state equation heuristic equal to h* for a suitable set C of conjunctions. We show that consistent potential heuristics can be computed from a variant of Pi^C, and that such heuristics can represent h* for suitable C. As an application of these convergence properties, we consider sound nogood learning in state space search, via refining the set C. We design a suitable refinement method to this end. Experiments on IPC benchmarks show significant performance improvements in several domains.
DOI of the first publication: 10.24963/ijcai.2018/672
URL of the first publication: https://www.ijcai.org/proceedings/2018/672
Link to this record: hdl:20.500.11880/28339
http://dx.doi.org/10.22028/D291-29342
ISBN: 978-0-9992411-2-7
Date of registration: 21-Nov-2019
Third-party funds sponsorship: DFG “Critically Constrained Planning via Partial Delete Relaxation"; BMBF through funding for the Center for IT-Security, Privacy and Accountability (CISPA)
Sponsorship ID: DFG HO 2169/5-1; BMBF 16KIS0656
Faculty: MI - Fakultät für Mathematik und Informatik
Department: MI - Informatik
Professorship: MI - Prof. Dr. Jörg Hoffmann
Collections:UniBib – Die Universitätsbibliographie

Files for this record:
There are no files associated with this item.


Items in SciDok are protected by copyright, with all rights reserved, unless otherwise indicated.