Please use this identifier to cite or link to this item:
Volltext verfügbar? / Dokumentlieferung
doi:10.22028/D291-29342
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: | SciDok - Der Wissenschaftsserver der Universität des Saarlandes |
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.