Structural patterns of tractable sequentially-optimal planning
Michael Katz, Carmel Domshlak · 2007
We study the complexity of sequentially-optimal clas-sical planning, and discover new problem classes for whose such optimization is tractable. The results are based on exploiting numerous structural characteristics of planning problems, and a constructive proof tech-nique that connects between certain tools from planning and tractable constraint optimization. In particular, we believe that structure-based tractability results of this kind may help devising new admissible search heuris-tics. We discuss the prospects of this direction along a principled extension of pattern-database heuristics to “structural patterns ” of unlimited dimensionality.