Characterizing and Computing All Delete-Relaxed Dead-ends

Authors

  • Christian Muise IBM Research

DOI:

https://doi.org/10.4114/intartif.vol21iss62pp67-74

Keywords:

deadends, dead-ends, knowledge compilation, d-DNNF, BDD, SDD

Abstract

Dead-end detection is a key challenge in automated planning, and it is rapidly growing in popularity. Effective dead-end detection techniques can have a large impact on the strength of a planner, and so the effective computation of dead-ends is central to many planning approaches. One of the better understood techniques for detecting dead-ends is to focus on the delete relaxation of a planning problem, where dead-end detection is a polynomial-time operation. In this work, we provide a logical characterization for not just a single dead-end, but for every delete-relaxed dead-end in a planning problem. With a logical representation in hand, one could compile the representation into a form amenable to effective reasoning. We lay the ground-work for this larger vision and provide a preliminary evaluation to this end

Downloads

Download data is not yet available.

Downloads

Published

2018-09-18

How to Cite

Muise, C. (2018). Characterizing and Computing All Delete-Relaxed Dead-ends. Inteligencia Artificial, 21(62), 67–74. https://doi.org/10.4114/intartif.vol21iss62pp67-74