Efficient Planning by Graph Rewriting

AAAI 1996

TL;DR

This paper proposes a novel framework for AI planning that views planning as a graph rewriting process. By representing plans as graphs and using graph rewriting rules, the authors aim to create a more general and expressive planning approach that can subsume existing methods and offer new opportunities for efficient planning.

What Problem Does This Paper Address?

Traditional AI planning systems aim to generate a sequence of actions to achieve a goal from an initial state. While significant progress has been made, particularly in partial-order and hierarchical task network (HTN) planning, there's a continuous need for more general and efficient planning methods. The authors observe that in domains like distributed query processing and manufacturing operation planning, it's often easier to construct an initial, possibly suboptimal, plan and then transform it to improve its quality. This suggests a need for planning frameworks that can effectively represent and apply such plan transformations.

Methods

The core idea is to represent a plan as a labeled graph, where nodes are actions and edges represent constraints like ordering or causal links. Planning then becomes a process of applying graph rewriting rules to transform one partial plan into another. This framework is designed to be general enough to encompass existing planning techniques:

  • Partial-order planners: Adding new actions or linking existing ones to satisfy goals or resolve threats can be seen as graph transformations.
  • HTN planners: Substituting a high-level, non-primitive action with a partial plan is analogous to a graph rewriting step.

The authors suggest that this graph rewriting approach can facilitate "hill-climbing" search from an easily constructed initial plan, using expressive transformations to improve plan quality. This is expected to be efficient for many domains and offer users more control over the desired solution characteristics.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Planning as Graph Rewriting: This is the central paradigm shift. By abstracting plans into graphs and using rewriting rules, the authors create a unified view of various planning transformations.
  • Subsumption of Existing Methods: The framework is shown to naturally incorporate transformations found in partial-order and HTN planners, suggesting a more general underlying theory.
  • Leveraging Expressive Transformations: The paper highlights how domain-specific transformations (like join-swap or remote-eval in query processing) can be naturally integrated, leading to more efficient plans.
  • Hill-Climbing from Initial Plans: The approach favors constructing an initial, potentially inefficient plan and then refining it through graph rewriting, which can be more tractable than building an optimal plan from scratch.
  • User Control: The expressive nature of graph rewriting rules could allow users to guide the planning process towards specific types of solutions.

Key Results

The paper presents a conceptual framework and discusses its potential benefits. It does not present quantitative experimental results or specific performance metrics. The key "results" are the conceptual insights into how graph rewriting can unify and extend existing planning paradigms.

Limitations and Future Work

  • Lack of Empirical Evaluation: The paper is an abstract and does not include experimental validation of the proposed framework's efficiency or effectiveness compared to existing planners.
  • Defining Rewriting Rules: The process of defining appropriate and effective graph rewriting rules for specific domains is a key area for future work.
  • Completeness and Soundness: While the framework aims to subsume existing methods, formal proofs of completeness and soundness for the graph rewriting approach would be necessary.
  • Scalability: The scalability of graph rewriting for very large plans and complex domains needs to be investigated.

Summary updated

BibTeX
@inproceedings{1996efficient,
  title = {{Efficient Planning by Graph Rewriting}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1996},
}
Figure