Improving Plan Execution Flexibility using Block-Substitution
Summary: arXiv:2406.03091v2 Announce Type: replace
Abstract
Partial-order plans in AI planning facilitate execution flexibility due to their less-constrained nature. Maximizing plan flexibility has been studied through the notions of plan deordering, and plan reordering. Plan deordering removes unnecessary action orderings within a plan, while plan reordering modifies them arbitrarily to minimize action orderings. This study, in contrast with traditional plan deordering and reordering strategies, improves a plan’s flexibility by substituting its subplans with actions outside the plan for a planning problem.
Our methodology builds on block deordering, which eliminates orderings in a POP by encapsulating coherent actions in blocks, yielding a hierarchically structured plan termed a Block Decomposed Partial-Order (BDPO) plan. We consider the action blocks in a BDPO plan as candidate subplans for substitutions, and ensure that each successful substitution produces a plan with strictly greater flexibility.
Methodology
The innovative approach put forth in this study focuses on several key aspects:
- Block Deordering: This technique encapsulates coherent actions within blocks, effectively eliminating unnecessary orderings in the partial-order plan.
- Substitutions: The action blocks are considered for substitutions with actions that lie outside the original plan, enhancing flexibility.
- Plan Reduction: The methodology employs plan reduction strategies to eliminate redundant actions within a BDPO plan.
- MaxSAT-based Reorderings: The approach is evaluated in conjunction with MaxSAT-based reorderings to further enhance execution flexibility.
Results
The experimental results demonstrate a significant improvement in plan execution flexibility on benchmark problems from the International Planning Competitions (IPC). The findings indicate that the proposed methodology not only maintains good coverage but also optimizes execution time.
By analyzing the performance across various scenarios, it has been established that the introduction of block-substitution strategies leads to an effective increase in the flexibility of AI planning processes. The ability to substitute action blocks while maintaining coherence in the planning structure allows for a more adaptable and responsive execution framework.
Conclusion
In conclusion, the study presents a novel approach to enhancing plan execution flexibility through block-substitution methodologies. By integrating block deordering with strategic substitutions and plan reduction techniques, the research sets a new benchmark for flexibility in AI planning. Future work will aim to further refine these strategies and explore their applicability across a broader range of planning problems and scenarios.