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—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: 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.
Introduction
Traditional AI planners often struggle with the "state-space explosion" problem: as the number of possible actions and requirements grows, the search space becomes mathematically unmanageable. While researchers have long used abstraction—solving a simplified version of the problem first and then filling in details—to mitigate this, traditional abstraction is often too rigid. It typically forces a linear hierarchy of levels that does not reflect the messy, overlapping nature of real-world tasks.
This paper introduces localization as a technique for scaling AI planning by partitioning complex problems into smaller, overlapping "regions of interaction." By automatically generating these regions based on two criteria—scope and abstraction—we demonstrate that localized search can significantly outperform traditional global planners and standard abstraction-based methods in complex domains.
Localized Planning via Regions
The core of the localization approach is the partitioning of a planning problem into Regions. Each region contains a subset of action types and the constraints relevant to them. Unlike standard partitioning, localization explicitly allows search spaces to overlap. This is crucial for real-world problems where a single action (like building a wall) might satisfy requirements for multiple sub-problems (such as electrical and structural requirements).
Criteria for Localization: Scope and Abstraction
We explore two primary criteria for partitioning a problem into regions:
- Abstraction-Based Localization: This adapts existing methods to group constraints into hierarchical levels. If satisfying constraint A might require satisfying constraint B, they are grouped or ordered accordingly to create a vertical hierarchy of detail.
- Scope-Based Localization: This groups constraints based on their functional relevance to specific portions of the plan, such as all painting-related activities or all tasks within a specific room. This provides a horizontal partitioning of the problem space.
The COLLAGE Planner and LOC Generator
Our implementation utilizes a planner called COLLAGE, which treats planning as a constraint-satisfaction problem (CSP). Unlike older STRIPS-based planners that focus on state-based goals, COLLAGE uses action-based constraints (e.g., "you must paint the wall before you insert the socket").
To automate the creation of these regions, we developed the LOC localization generator. LOC automatically partitions a problem into regions based on the chosen criteria. The localized search architecture allows the planner to flow back and forth between these regional search spaces, maintaining consistency without needing to backtrack through a global hierarchy.
Empirical Evaluation
We evaluated these methods using an office-building construction domain involving tasks for various contractors (painters, electricians, plumbers) across multiple floors. We compared COLLAGE using localized search against SIPE-2, a well-known hierarchical task network (HTN) planner.
Key Results
- Scope Trumps Abstraction: One of the most significant findings was that partitioning by scope (functional relevance) often provided better search reduction than partitioning by abstraction (levels of detail).
- Scalability: COLLAGE using scoped localization scaled much more gracefully than SIPE-2. As the number of floors increased, the runtime for SIPE-2 grew exponentially, while the COLLAGE curves remained significantly flatter.
- Efficiency: Scoped localization outperformed even the "global abstracted" version. This is because localization limits expensive temporal closure calculations to small, regional plan fragments, drastically reducing computational overhead.
- Validation of LOC: The automatically generated scoped localization performed nearly identically to hand-crafted user-specified localizations, proving the viability of the LOC generator.
Conclusion
Localization offers a powerful alternative to rigid hierarchical abstraction. By allowing for overlapping regions and focusing on functional scope, planners can manage complex interdependencies more efficiently. Future work will explore dynamic analysis to refine regions during runtime and the application of localization to other complex domains like scheduling and large-scale software verification.
Summary updated