Abstract
In parallel, multiagent environments, traditional AI planning faces significant computational hurdles, most notably the combinatorial frame problem. This paper introduces the Group Element Model (GEM) and its associated planner, GEMPLAN, which utilize the concept of "locality" to partition planning domains into encapsulated regions of activity. By localizing constraints and search spaces, GEMPLAN achieves efficient parallel planning without the exponential overhead typically associated with global interaction analysis.
Introduction: The Frame Problem in Parallel Domains
In the late 1980s, the "Frame Problem"—determining which world properties remain unchanged after an action—posed a major barrier to scaling AI planners. In a global, state-based model, every action could theoretically impact every property, making multiagent planning computationally explosive. While hierarchical planning offered some "divide-and-conquer" benefits, existing frameworks were often too rigid to handle overlapping activities or nuanced parallel interactions. The authors argue that the key to efficiency lies in "localizing" domain descriptions to minimize redundant interaction checks.
The Group Element Model (GEM)
The Group Element Model (GEM) shifts the focus from world states to an event-based representation. It organizes the domain into a hierarchy of regions:
- Elements: The most basic units representing sequential activity (e.g., a single student or oven). Events within an element are totally ordered.
- Groups: Clusters of elements or other groups that represent "causally encapsulated" regions. A group acts as a boundary; internal events generally cannot affect external properties unless they pass through designated Ports.
Constraints in GEM are expressed using first-order temporal logic but are applied locally. This structure ensures that if a property is associated with one group, and an event occurs in a disjoint group, the system inherently knows the property is unaffected, effectively solving the frame problem through architectural design.
GEMPLAN: Localized Planning and Search
GEMPLAN is a localized planner designed to mirror the structure of the GEM domain. Rather than maintaining a single, massive search tree, GEMPLAN operates as a network of "mini-planning systems" for each region.
When a constraint is violated (e.g., in "Kitchen 1"), the planner searches for a "fix" only within that region's local tree. Changes are only propagated to parent search spaces if the resolution involves an interaction point or port. This localized search is supported by an inheritance mechanism, where plan nodes store only the incremental changes from their parents, keeping the representation compact and efficient.
Key Insights and Results
The implementation of GEMPLAN in Prolog demonstrated several critical advantages:
- Non-interference Guarantees: The system exploits "guaranteed non-interference." Once a region's constraints are satisfied, adding events to disjoint regions cannot violate them, drastically reducing the number of constraints requiring re-verification.
- Parallelism: Unlike linear, state-based planners of the era, GEMPLAN can generate synchronized plans where multiple agents act simultaneously.
- Events over States: Using event relationships simplifies the description of complex synchronization, such as "first-come-first-served" access to shared resources like ovens.
Limitations and Future Work
While GEMPLAN proved successful in synthetic domains like the "Cooking-Class" and multiagent Blocks-World, the authors identified areas for further development. At the time of publication, the full potential of "ports" for complex interactions was not yet fully realized in the planner. Additionally, because solving arbitrary temporal logic is NP-hard, the system relied on "predefined fixes" (cognitive clichés) for common constraints. Future work aimed to extend these methods to real-world scheduling tasks and more complex industrial domains.
Summary updated