Optimising Partial-Order Plans Via Action Reinstantiation

Max Waters, Lin Padgham, Sebastian SardiñaIJCAI 2020 · DOI

TL;DR

This paper introduces "action reinstantiation" – modifying variable bindings in AI plans, not just action orderings – to create more flexible plans. They propose a MAXSAT-based approach and show that while computationally more expensive, it can significantly increase plan flexibility, especially when standard methods struggle.

What Problem Does This Paper Address?

In Artificial Intelligence planning, a "partial-order plan" (POP) represents a sequence of actions where the exact order of some actions is left unspecified to allow for flexibility during execution. Traditionally, optimizing POPs has focused on rearranging these action orders (deordering and reordering). However, POPs also involve assigning specific objects (like robots or locations) to variables within actions. This paper argues that these variable bindings, if "over-committed" early on, can unnecessarily restrict the possible orderings of actions. The problem is to find ways to optimize POPs not just by changing action order but also by changing these variable bindings to achieve greater overall flexibility.

Methods

The core contribution is the concept of "action reinstantiation," which extends existing POP optimization techniques to allow modifications to variable bindings.

  • Optimality Criteria: The authors generalize existing definitions of minimal and minimum deordering/reordering to "reinstantiated" versions, explicitly allowing for changes in variable bindings.
  • MAXSAT Encoding: They adapt existing MAXSAT encodings (MD and MR) for POP optimization into new ones (MRD and MRR) that can handle reinstantiation. These encodings translate the problem of finding optimal POPs into a satisfiability problem that can be solved by a MAXSAT solver.
  • Optimizations: To manage the increased complexity, they introduce optimizations like removing redundant constraints and breaking symmetries, particularly those arising from object symmetries in the planning domain.

Datasets

The paper uses test cases generated by feeding first-order IPC STRIPS planning instances to three different planners: Dual-BFWS, LAMA, and Madagascar. These generated plans are then used to evaluate the proposed methods. No new benchmarks are introduced.

Key Insights and Ideas

  • Variable Bindings Matter for Flexibility: The most significant insight is that over-committing to specific variable bindings early in the planning process can severely limit the potential for action reordering, even if the plan is otherwise valid.
  • Reinstantiation as a Powerful Optimization: Allowing variable bindings to change (reinstantiation) can unlock significantly more flexible plans than just reordering actions, especially in domains where standard reordering methods struggle to find improvements.
  • Computational Cost Trade-off: While reinstantiation offers greater flexibility, it comes at a substantial computational cost, leading to larger MAXSAT instances and reduced coverage (fewer plans solved within the time limits).
  • Object Symmetries are a Challenge: The paper identifies object symmetries (e.g., multiple identical robots) as a key factor that complicates reinstantiation and contributes to the computational overhead.

Key Results

  • MRR provides significant flex increase: The MRR (Minimum Reinstantiated Reordering) approach, which allows both action reordering and variable binding changes, provides a mean flex increase of 20% over the baseline EOG (Explanation-Based Order Generalization) method.
  • Reinstantiation is most beneficial when standard methods fail: The benefits of MRR are most pronounced in domains where standard reordering (MR) offers little to no improvement. For example, MRR showed flex increases of 94% and 96% in "freecell" and "pipesworld" respectively, where MR provided only 2%.
  • Computational cost is high: MRR has a mean coverage of only 52%, indicating that it times out on nearly half of the problems. This is significantly lower than EOG (88% coverage) and MR (higher coverage).
  • Planner choice matters: The source of the initial plan influences flexibility. Plans generated by Madagascar (which are already somewhat parallel) benefit less from EOG but still see improvements from MRR, while sequential plans from Dual-BFWS and LAMA benefit more from both EOG and MRR.

Limitations and Future Work

  • Computational Complexity: The primary limitation is the significant computational cost associated with reinstantiation, leading to lower coverage and longer run times. The authors acknowledge that deciding optimality is NP-complete and finding a minimum reinstantiated de/reordering is NP-hard.
  • Object Symmetries: The paper suggests that object symmetries are a major hurdle for effective reinstantiation and proposes symmetry breaking as a promising area for future work.
  • MILP Encoding: The authors suggest exploring Mixed Integer Linear Programming (MILP) encodings for MRD and MRR as a potential avenue for improving execution time.
  • Generalizing Other Techniques: They also propose investigating whether generalizing other POP optimization techniques (like block decomposition) to allow reinstantiation could yield further benefits.

Summary updated

BibTeX
@inproceedings{waters2020optimising,
  author = {Max Waters and Lin Padgham and Sebastian Sardiña},
  title = {{Optimising Partial-Order Plans Via Action Reinstantiation}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.24963/ijcai.2020/573},
}
Figure