Characterizing and Computing All Delete-Relaxed Dead-ends


  • Christian Muise IBM Research



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


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


Download data is not yet available.




How to Cite

Muise, C. (2018). Characterizing and Computing All Delete-Relaxed Dead-ends. Inteligencia Artificial, 21(62), 67–74.