Act Local, Think Global: Width Notions for Tractable Planning

Hubie Chen, Omer Gimenez

Many of the benchmark domains in AI planning are tractable on an individual basis. In this paper, we seek a theoretical, domain-independent explanation for their tractability. We present a family of structural conditions that both imply tractability and capture some of the established benchmark domains. These structural conditions are, roughly speaking, based on measures of how many variables need to be changed in order to move a state closer to a goal state.

Subjects: 1.11 Planning; 9.2 Computational Complexity

Submitted: Jun 27, 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.