Please use this identifier to cite or link to this item: doi:10.22028/D291-29339
Volltext verfügbar? / Dokumentlieferung
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
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:
Link to this record: hdl:20.500.11880/28337
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.