Please use this identifier to cite or link to this item:
Volltext verfügbar? / Dokumentlieferung
doi:10.22028/D291-29339
Title: | Critical-Path Dead-End Detection versus NoGoods : Offline Equivalence and Online Learning |
Author(s): | Steinmetz, Marcel Hoffmann, Jörg |
Editor(s): | Barbulescu, Laura Frank, Jeremy Mausam Smith, Stephen F. |
Language: | English |
Title: | Proceedings of the Twenty-Seventh International Conference on Automated Planning and Scheduling |
Startpage: | 283 |
Endpage: | 287 |
Publisher/Platform: | AAAI Press |
Year of Publication: | 2017 |
Title of the Conference: | ICAPS 2017 |
Place of the conference: | Pittsburgh, Pennsylvania USA |
Publikation type: | Conference Paper |
Abstract: | One traditional use of critical-path heuristic functions is as effective sufficient criteria for unsolvability. To employ this for dead-end detection, the heuristic function must be evaluated on every new state to be tested, incurring a substantial runtime overhead. We show herein that the exact same dead-end detector can be captured through a nogood, a formula phiOFF computed once prior to search. This is mostly of theoretical interest, as phiOFF is large. We obtain practical variants by instead incrementally generating a stronger nogood psi, that implies phiOFF, online during search, generalizing from already tested states to avoid future heuristic-function evaluations. |
URL of the first publication: | https://aaai.org/ocs/index.php/ICAPS/ICAPS17/paper/view/15642 |
Link to this record: | hdl:20.500.11880/28337 http://dx.doi.org/10.22028/D291-29339 |
ISSN: | 2334-0835 |
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.