Scope and Abstraction: Two Criteria for Localized Planning

Abstract

Localization is a general-purpose representational technique for partitioning problem requirements into subproblems. Localized search utilizes a partitioning by breaking the overall search space into several smaller search spaces, one for each subproblem. Unlike most methods of partitioning, localization allows for subproblems that overlap -- i.e., multiple search spaces may be involved in constructing shared pieces of the overall plan. In this paper we focus on two criteria for forming localizations: abstraction and scope. Abstraction-based localizations are motivated by activation relationships between problem requirements. In contrast, scope-based localizations are motivated by the relevance of problem requirements to specific portions of the overall plan. This paper also describes a method for automatically generating scope and abstraction-based localizations. Empirical results are provided that contrast their use in an office-building construction planning domain.