AAAI Publications, Twenty-Third International Conference on Automated Planning and Scheduling

Font Size: 
Safe, Strong, and Tractable Relevance Analysis for Planning
Patrik Haslum, Malte Helmert, Anders Jonsson

Last modified: 2013-06-02

Abstract


In large and complex planning problems, there will almost inevitably be aspects that are not relevant to a specific problem instance. Thus, identifying and removing irrelevant parts from an instance is one of the most important techniques for scaling up automated planning. We examine the path-based relevance analysis method, which is safe (preserves plan existence and cost) and powerful but has exponential time complexity, and show how to make it run in polynomial time with only a minimal loss of pruning power.

Full Text: PDF