Unchaining the Power of Partial Delete Relaxation, Part II: Finding Plans with Red-Black State Space Search

Unchaining the Power of Partial Delete Relaxation, Part II: Finding Plans with Red-Black State Space Search

Maximilian Fickert, Daniel Gnad, Joerg Hoffmann

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence
Main track. Pages 4750-4756. https://doi.org/10.24963/ijcai.2018/660

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.
Keywords:
Planning and Scheduling: Planning Algorithms
Heuristic Search and Game Playing: Heuristic Search
Planning and Scheduling: Search in Planning and Scheduling