Scope and Abstraction Two Criteria for Localized Planning

TL;DR

This paper introduces "localization" as a powerful technique for partitioning complex planning problems into smaller, manageable subproblems. By defining two key criteria – scope and abstraction – for creating these localized regions, the authors demonstrate significant improvements in planning efficiency, particularly outperforming traditional abstraction-based methods in their experimental domain.

What Problem Does This Paper Address?

Traditional AI planning systems often struggle with the combinatorial explosion of search spaces, especially in complex, real-world domains. While abstraction has been a common strategy to tackle this by creating hierarchical levels of problem detail, it often leads to rigid structures and can cause problems to "collapse" into a single level if not carefully managed. The authors propose "localization" as a more flexible alternative. Localization partitions a planning problem into regions, where each region focuses on a subset of requirements and actions. Unlike strict abstraction levels, these regions can overlap and interact, allowing for a more dynamic and adaptive planning process. The core challenge addressed is how to automatically and effectively generate these localizations to improve planning performance.

Methods

The paper presents the COLLAGE planner, which utilizes localization as a core mechanism. COLLAGE differs from traditional planners by employing an action-based constraint satisfaction approach rather than state-based goals and preconditions.

The key novelties lie in the criteria for generating localizations:

  • Abstraction-Based Localization: This method adapts Knoblock's work on abstraction hierarchies. It analyzes the "activation relationships" between constraints (i.e., how satisfying one constraint might lead to satisfying another) to form regions. Regions are grouped based on these activation patterns, creating a hierarchy that aims to ensure monotonic consideration of domain requirements.
  • Scope-Based Localization: This criterion focuses on the "relevance" of constraints to specific parts of the plan. It involves defining regions based on the action types a constraint applies to. The authors introduce a localization generator called Loc, which uses a suite of transforms (Subsume, Merge, Create Hierarchy) to optimize these scope-based partitions by reducing overlap and unnecessary regions.

The paper also discusses how these localization strategies can be applied to STRIPS-based planning frameworks by drawing analogies between literals and operators, and constraints and action types.

Datasets

The experiments were conducted in an office-building construction domain. This domain was previously used in a study with the SIPE-2 planner, allowing for a comparative analysis. The authors describe problems involving buildings ranging in size from one to ten floors with identical floor plans.

Key Insights and Ideas

  • Flexibility of Localization: Localization offers a more flexible partitioning than traditional abstraction, allowing for overlapping regions and more dynamic interaction between subproblems. This is crucial for real-world problems that don't neatly fit into strict hierarchical levels.
  • Scope vs. Abstraction Trade-offs: While abstraction-based localizations aim for monotonic reasoning, scope-based localizations can achieve better performance by focusing on the direct relevance of constraints, even if it means sacrificing strict monotonicity.
  • The Power of "Less Collapse": The "scoped" localization performed best because it avoided excessive regional collapse. This meant smaller, more focused regions, leading to fewer expensive temporal closure operations in the domain.
  • Automatic Generation is Viable: The Loc generator demonstrates that effective localizations can be automatically generated, reducing the reliance on manual, intuition-based partitioning.
  • Action-Based Planning Efficiency: The results suggest that action-based planning, even with localization, can be significantly more efficient and scalable than STRIPS-based planning.

Key Results

  • The "scoped" localization strategy achieved the best performance in the office-building construction domain, outperforming abstraction-based and combined approaches.
  • The "abstracted" and "abstracted-scoped" localizations, while still localized, were hampered by a large merged region due to constraint activation, leading to higher costs for temporal closure.
  • "Global abstracted" (a single region with a heuristic ordering) outperformed the purely abstraction-based localizations in the long run, suggesting that the consistency maintenance overhead in localized abstraction can be detrimental.
  • The hand-crafted "user specified" localization was nearly identical in performance to the automatically generated "scoped" localization, validating Loc's effectiveness.
  • COLLAGE's planning curves showed a much slower increase in runtime compared to SIPE-2, highlighting the efficiency of action-based planning.

Limitations and Future Work

  • Consistency Maintenance Overhead: While localization offers benefits, maintaining consistency between interacting regions can be complex and costly. The paper notes a trade-off between fine-grained partitioning and consistency maintenance.
  • Heuristic Scope-Based Transforms: The paper mentions heuristic versions of Loc's transforms that can increase constraint scope to reduce overlap, but acknowledges the need for further evaluation criteria to control their use.
  • Future Work: The authors plan to feed planning process information back into Loc to improve localizations dynamically. This includes developing "splitting transforms" to apply constraints in narrower contexts and using feedback to guide heuristic scope-based transforms, particularly for regions with high consistency maintenance costs. They also aim to extend Loc to incorporate splitting transforms based on actual parameter bindings.

Summary updated

Abstract

Localization is a general-purpose representational technique for partitioning a problem into subproblems. A localized problem-solver searches several smaller search spaces, one for each subproblem Unlike most methods of partitioning, however, localization allows for subproblems that overlap - 1 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 scope and abstraction. We describe a method for automatically generating such localizations and provide empirical results that contrast their use in an office-building construction domain.
BibTeX
@inproceedings{1995scope,
  title = {{Scope and Abstraction Two Criteria for Localized Planning}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1995},
}
Figure