Unchaining the Power of Partial Delete Relaxation, Part II: Finding Plans with Red-Black State Space Search
Abstract
Red-black relaxation in classical planning allows to interpolate between delete-relaxed and real planning. Yet the traditional use of relaxations to generate heuristics restricts relaxation usage to tractable fragments. How to actually tap into the red-black relaxation's interpolation power? Prior work has devised red-black state space search (RBS) for intractable red-black planning, and has explored two uses: proving unsolvability, generating seed plans for plan repair. Here, we explore the generation of plans directly through RBS. We design two enhancements to this end: (A) use a known tractable fragment where possible, use RBS for the intractable parts; (B) check RBS state transitions for realizability, spawn relaxation refinements where the check fails. We show the potential merits of both techniques on IPC benchmarks.
Cite
Text
Fickert et al. "Unchaining the Power of Partial Delete Relaxation, Part II: Finding Plans with Red-Black State Space Search." International Joint Conference on Artificial Intelligence, 2018. doi:10.24963/IJCAI.2018/660Markdown
[Fickert et al. "Unchaining the Power of Partial Delete Relaxation, Part II: Finding Plans with Red-Black State Space Search." International Joint Conference on Artificial Intelligence, 2018.](https://mlanthology.org/ijcai/2018/fickert2018ijcai-unchaining/) doi:10.24963/IJCAI.2018/660BibTeX
@inproceedings{fickert2018ijcai-unchaining,
title = {{Unchaining the Power of Partial Delete Relaxation, Part II: Finding Plans with Red-Black State Space Search}},
author = {Fickert, Maximilian and Gnad, Daniel and Hoffmann, Jörg},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2018},
pages = {4750-4756},
doi = {10.24963/IJCAI.2018/660},
url = {https://mlanthology.org/ijcai/2018/fickert2018ijcai-unchaining/}
}