Improving Domain-Independent Planning via Critical Section Macro-Operators

Lukás Chrpa, Mauro VallatiAAAI 2019 · DOI

Abstract

Domain-independent automated planning relies heavily on heuristics to guide search through vast state spaces. However, in resource-constrained environments, standard delete-relaxation heuristics often provide misleading guidance, leading to significant performance degradation. This paper introduces Critical Section Macros, a novel technique that identifies action sequences where resources are locked, utilized, and subsequently released. By encapsulating these sequences into single macro-operators, the proposed method effectively bypasses problematic intermediate states and mitigates heuristic errors. Evaluation on International Planning Competition (IPC) benchmarks demonstrates that this approach significantly enhances the coverage and efficiency of state-of-the-art planners.

Introduction

The fundamental challenge in automated planning is the efficient exploration of state spaces to find a valid sequence of actions from an initial state to a goal. Macro-operators—pre-calculated sequences of actions—have long been used to provide "shortcuts" in the search process. While traditional macro-learning techniques focus on the frequency of action sequences in training data, they often suffer from the "utility problem," where an overabundance of macros increases the branching factor without providing meaningful guidance. Moreover, these methods fail to address the inherent limitations of modern heuristics, particularly delete-relaxation heuristics, which struggle to model resource contention accurately.

Methodology

The core contribution of this work is the concept of Critical Section Macros. Drawing inspiration from critical sections in parallel computing, the authors identify patterns of resource usage within plans.

The Core Idea

A resource (such as a robotic gripper or a specialized tool) is typically locked by one action (e.g., pickup), used for several intermediate actions (e.g., shake-cocktail), and then released (e.g., drop). The authors' algorithm identifies these patterns by categorizing actions as:

  • Lockers: Actions that delete a "free resource" state and add a "locked resource" state.
  • Releasers: Actions that do the opposite.
  • Users: Intermediate actions that require the resource to be locked.

Aggressive State Space Pruning

To further optimize search, the authors propose an aggressive configuration. In this mode, once a macro is successfully learned, the original locker and releaser operators are removed from the domain model entirely. This prevents the planner from ever exploring states where a resource is partially engaged, effectively reducing the depth and complexity of the search tree and preventing the heuristic from making incorrect estimations about resource availability.

Experimental Evaluation

The effectiveness of Critical Section Macros was evaluated using benchmarks from the IPC learning tracks (2008 and 2011). The test suite included diverse domains such as Barman, BlocksWorld, Gripper, and Sokoban. Six state-of-the-art planners, including LAMA, Probe, and Dual BFWS, were used as baselines to measure coverage, runtime (PAR10), and plan quality.

Results and Discussion

The empirical results highlight the transformative impact of the proposed macros on planner performance. As shown in the data, the inclusion of Critical Section Macros led to substantial increases in coverage across nearly all tested domains.

Comparative performance of various planners across IPC domains using original (O), conservative (C), and aggressive (AC) macro configurations.

In the Barman domain, which is characterized by complex resource management, the LAMA planner's coverage improved from a mere 2 solved problems to a perfect 30 out of 30 when using the macro-enhanced models. Similar trends were observed in speed; tasks that previously required hundreds of seconds were often solved in under one second.

The "aggressive" variant proved particularly potent. By removing original operators, it forced the planners to adopt the learned "shortcuts," which proved to be the optimal strategy in approximately 90% of applicable cases. This suggests that the primary benefit of these macros is not just providing a shortcut, but actively preventing the planner from entering "local minima" where heuristics provide incorrect distance estimates due to ignored negative effects.

Conclusion

Critical Section Macros offer a robust solution to the limitations of traditional macro-learning and heuristic search in resource-heavy planning domains. By focusing on the logical structure of resource usage rather than simple frequency, the method provides high-utility shortcuts that significantly improve planner performance. Future work will explore the application of this technique to temporal planning, where overlapping action durations further complicate resource management.

Summary updated

BibTeX
@inproceedings{chrpa2019improving,
  author = {Lukás Chrpa and Mauro Vallati},
  title = {{Improving Domain-Independent Planning via Critical Section Macro-Operators}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.1609/aaai.v33i01.33017546},
}
Figure