Structural Patterns of Tractable Sequentially-Optimal Planning

Michael Katz, Carmel Domshlak

We study the complexity of sequentially-optimal classical 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 technique 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 heuristics. We discuss the prospects of this direction along a principled extension of pattern-database heuristics to "structural patterns" of unlimited dimensionality.

Subjects: 1.11 Planning; 9.2 Computational Complexity

Submitted: Jun 25, 2007

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.