Additive Pattern Databases for Decoupled Search

ion heuristics are the state of the art in optimal classical planning asheuristic search. Despite their success for explicit-state search, though,abstraction heuristics are not available for decoupled state-space search, anorthogonal reduction technique that can lead to exponential savings by decomposingplanning tasks. In this paper, we show how to compute pattern database (PDB)heuristics for decoupled states. The main challenge lies in how to additively employmultiple patterns, which is crucial for strong search guidance of the heuristics. Weshow that in the general case, for arbitrary collections of PDBs, computing theheuristic for a decoupled state is exponential in the number of leaf components ofdecoupled search. We derive several variants of decoupled PDB heuristics that allowto additively combine PDBs avoiding this blow-up and evaluate them empirically.