Beating LM-Cut with h^max (Sometimes): Fork-Decoupled State Space Search

Abstract

Factored planning decouples planning tasks into subsets (factors) of state variables. The traditional focus is on handling complex cross-factor interactions. Departing from this, we introduce a form of target-profile factoring, forcing the cross-factor interactions to take the form of a fork, with several leaf factors and one potentially very large root factor. We show that forward state space search gracefully extends to such structure, by augmenting regular search on the root factor with maintenance of the cheapest compliant paths within each leaf factor. We analyze how to guarantee optimality. Connecting to standard heuristics, the performance improvements relative to A* are substantial, and sometimes dramatic: In four IPC benchmark domains, fork-decoupled state space search outperforms standard state space search even when using h^max in the former vs. LM-cut in the latter.