LP Heuristics over Conjunctions: Compilation, Convergence, Nogood Learning

LP Heuristics over Conjunctions: Compilation, Convergence, Nogood Learning

Marcel Steinmetz, Joerg Hoffmann

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

Two strands of research in classical planning are LP heuristics and conjunctions to improve approximations. Combinations of the two have also been explored. Here, we focus on convergence properties, forcing the LP heuristic to equal the perfect heuristic h* in the limit. We show that, under reasonable assumptions, partial variable merges are strictly dominated by the compilation Pi^C of explicit conjunctions, and that both render the state equation heuristic equal to h* for a suitable set C of conjunctions. We show that consistent potential heuristics can be computed from a variant of Pi^C, and that such heuristics can represent h* for suitable C. As an application of these convergence properties, we consider sound nogood learning in state space search, via refining the set C. We design a suitable refinement method to this end. Experiments on IPC benchmarks show significant performance improvements in several domains.
Keywords:
Planning and Scheduling: Planning Algorithms
Heuristic Search and Game Playing: Heuristic Search
Planning and Scheduling: Planning and Scheduling