Improving Plan Execution Flexibility using Block-Substitution

This paper introduces a novel approach to enhancing plan execution flexibility by substituting subplans within Block Decomposed Partial-Order (BDPO) plans with external actions and applying plan reduction strategies, demonstrating significant improvements on International Planning Competition benchmarks while maintaining efficiency.

The Gist

Imagine you are the director of a massive, complex play. You have a script (the plan) that tells your actors (the actions) exactly what to do and, crucially, in what order.

In the world of Artificial Intelligence (AI), this is called Planning. Usually, AI generates a script where every actor knows exactly when to enter and exit. But what if the stage lighting breaks? What if an actor gets sick? What if a prop is missing? If your script is too rigid, the whole show crashes.

This paper introduces a new way to make AI plans more flexible—like a script that allows actors to improvise without ruining the play.

Here is the breakdown of their method, FIBS (Flexibility Improvement via Block-Substitution), using simple analogies.

1. The Problem: The Rigid Script

Most AI planners create a "Total Order" plan. Think of this as a strict marching band routine:

• Step 1: March forward.
• Step 2: Turn left.
• Step 3: Play the trumpet.

If you try to play the trumpet before turning left, the routine fails. This is efficient, but it has zero flexibility. If the trumpet player is late, the whole band stops.

2. The First Upgrade: "Deordering" (Loosening the Script)

Researchers have long tried to fix this by Deordering. This is like telling the band: "You don't have to turn left immediately after marching. You can do it whenever, as long as you do it before the trumpet solo."

This creates a Partial-Order Plan (POP). It's a bit more flexible.

• The Old Way (EOG/Block Deordering): They would look at the script and group related actions into "blocks" (like a "Dance Sequence" or a "Musical Interlude"). They realized that if two blocks don't depend on each other, they can happen in any order.
• The Limit: This only works if you keep the exact same actors and props. You can't swap a trumpet for a drum, even if the drummer could do the job just as well.

3. The New Innovation: "Block-Substitution" (Swapping the Cast)

This paper introduces a bold new idea: Block-Substitution.

Imagine you have a block in your script called "Move the heavy sofa from the living room to the kitchen."

• The Old Plan: Uses two strong actors to carry it.
• The Problem: What if those two actors are busy?
• The New Idea: Instead of just saying "Do this whenever," the AI asks: "Is there a completely different way to move this sofa?"

Maybe there is a dolly (a different tool) or a third actor (a different resource) available in the building that wasn't in the original script. The AI finds a new mini-script (a subplan) that uses the dolly instead of the two actors.

Why is this a game-changer?

1. More Freedom: The new "dolly" method might not need the actors to be in a specific order with other tasks. It frees up the schedule.
2. Better Resources: It might use a tool that was sitting idle, making the whole show run smoother.
3. Cutting the Fat: Sometimes, the new method is so efficient that it makes the original "carrying" block completely unnecessary. The AI can delete those actors from the script entirely, saving time and energy.

4. How the Algorithm Works (The "FIBS" Process)

The authors built an algorithm called FIBS that acts like a smart, iterative editor:

1. Drafting: It starts with a strict script generated by a standard AI planner.
2. Grouping: It groups actions into "blocks" (like scenes).
3. The Swap (Substitution): It looks at every "scene" and asks, "Can I replace this scene with a different one that uses different actors or tools but gets the same result?"
   • If the new scene allows the rest of the play to happen in more random orders, it keeps the swap.
   • If the new scene makes the play less flexible, it throws it out.
4. Trimming: It checks for redundant actors (people doing nothing) and cuts them out.
5. Repeat: It does this over and over, getting the script looser and more efficient with every pass.

5. The Results: Why It Matters

The researchers tested this on hundreds of real-world planning problems (like moving elevators, organizing warehouses, or navigating robots).

• Flexibility: Their method created plans that were significantly more flexible than previous methods. In some cases, the "flexibility score" jumped from 0.20 to 0.32. That's a huge jump in the world of rigid logic.
• Speed: Unlike other methods that try to solve the whole puzzle at once using complex math (which takes hours or days), FIBS is like a "smart editor." It works quickly and keeps getting better the longer you let it run.
• Cost: By swapping in better resources and cutting out redundant steps, the plans were often cheaper (faster) to execute, too.

The Bottom Line

Think of traditional AI planning as writing a script where every line is locked in stone.

• Old methods tried to unlock the lines so they could be spoken in different orders.
• This paper (FIBS) says, "Why not rewrite the lines entirely if a better version exists?"

By allowing the AI to swap out chunks of the plan for better, more flexible alternatives, they created a system that can adapt to a chaotic world much better than before. It's the difference between a rigid military march and a jazz band that can improvise when the music changes.

Technical Summary

1. Problem Statement

In AI planning, Partial-Order Plans (POPs) are preferred over sequential plans because they allow for execution flexibility by delaying commitments to action orderings. This flexibility enables agents to adapt to dynamic environments (e.g., resource fluctuations or unexpected events) by choosing different valid linearizations of the plan.

However, existing methods to maximize plan flexibility have limitations:

• Plan Deordering: Removes unnecessary ordering constraints from a given plan but does not alter the set of actions.
• Plan Reordering: Modifies action orderings arbitrarily (often using MaxSAT) but typically cannot introduce new actions or replace existing action sets with different ones.
• Action Reinstantiation: Allows reassigning parameters to operators but cannot replace an operator with a completely different action name or size.

The core problem addressed is how to further improve plan execution flexibility by not just reordering or removing constraints, but by substituting subplans (blocks) with alternative subplans (potentially from outside the original plan) that achieve the same goals with fewer ordering constraints, while maintaining or reducing the plan cost.

2. Methodology

The authors propose a novel framework called Flexibility Improvement via Block-Substitution (FIBS). The methodology relies on Block Decomposed Partial-Order (BDPO) plans, where coherent actions are encapsulated into "blocks."

Key Components:

1. Block Decomposition:

   • The process starts with a sequential plan, converts it to a POP using Explanation-Based Order Generalization (EOG), and then applies Block Deordering.
   • Block Deordering clusters coherent operators into blocks, creating a hierarchical BDPO plan. This allows unordered blocks to be executed in any sequence.

2. Block-Substitution Algorithm:

   • The core innovation is the ability to replace a block ($b_x$) in a BDPO plan with a new block ($\hat{b}_x$) sourced from a subproblem solver.
   • Subproblem Formulation: To find a replacement for a block $b_j$, the algorithm constructs a subtask ($\Pi_{sub}$):
     • Initial State: Derived by progressing the original initial state through all blocks preceding $b_j$ (excluding the specific predecessor block being tested for removal).
     • Goal State: A combination of facts required by $b_j$'s successors and facts $b_j$ provides to the overall goal.
   • Generation: An off-the-shelf planner (e.g., LAMA) generates candidate subplans for $\Pi_{sub}$.
   • Validation: The candidate subplan is converted to a block and substituted into the main BDPO plan. The algorithm checks for:
     • Validity: All preconditions must be supported by causal links; all threats must be resolved (via promotion/demotion or internal substitution).
     • Flexibility/Cost: The new plan must have strictly greater flexibility ($flex$) and cost less than or equal to the original plan.

3. Threat Resolution:

   • The paper details specific strategies to resolve threats introduced by substitution, including Promotion (ordering the threat before the causal link source), Demotion (ordering the threat after the link sink), and Internal Block-Substitution (replacing the conflicting block with the new block if it becomes redundant).

4. Plan Reduction:

   • After substitution, the algorithm applies Backward Justification and Greedy Justification to eliminate redundant operators (blocks) that are no longer necessary, further reducing cost and potentially increasing flexibility.

5. The FIBS Algorithm Flow:

   • Phase 1 (EOG): Generate initial POP.
   • Phase 2 (SD1): Substitute primitive blocks (single operators) to remove orderings.
   • Phase 3 (BD): Apply Block Deordering to form compound blocks.
   • Phase 4 (SD2): Substitute both primitive and compound blocks to further minimize orderings.

3. Key Contributions

• Novel Substitution Strategy: Unlike previous works that only reorder or deorder, this paper introduces Block-Substitution, which allows replacing subplans with entirely different sets of actions (different names or sizes) to optimize flexibility.
• BDPO Integration: The method leverages the hierarchical structure of BDPO plans to define candidate subplans, making the search space for substitutions more manageable than blind search.
• Hybrid Optimization: The approach combines deordering, reordering, and substitution, and integrates plan reduction techniques (justification) to simultaneously optimize flexibility and cost.
• Theoretical Analysis: The authors provide formal proofs for the correctness (validity of the resulting plan) and incompleteness (limitations in finding all possible optimal substitutions due to greedy producer selection) of their algorithms.

4. Experimental Results

The authors evaluated FIBS on 3,826 plans from 32 domains in the International Planning Competitions (IPC).

• Flexibility Improvement:

  • FIBS achieved a 62% overall improvement in plan flexibility compared to EOG alone.
  • The Block Deordering (BD) phase contributed the most significant gains, followed by the substitution phases (SD1 and SD2).
  • FIBS outperformed MaxSAT-based Reordering (MR) and Minimum Reinstantiated Reordering (MRR) in 25 and 19 domains, respectively.
  • Average Flexibility: FIBS achieved a mean flexibility of 0.32, compared to 0.23 for MR and 0.25 for MRR.

• Efficiency and Scalability:

  • Execution Time: FIBS is significantly faster than MaxSAT approaches. The average execution time for FIBS was 106 seconds, whereas MR and MRR averaged 242 and 1039 seconds, respectively.
  • Coverage: FIBS maintained 100% coverage (solving all problems), while MRR coverage dropped to 54% for larger plans due to encoding size explosion.
  • Plan Size: FIBS showed superior performance on small-to-medium plans (up to ~250 operators). Performance gains diminished for very large plans, likely due to the overhead of substitution operations.

• Plan Reduction:

  • Integrating Greedy Justification with FIBS reduced plan costs by an average of 5.91%, outperforming the Minimal Plan Reduction (MPR) approach in several domains (e.g., elevator, logistics).

5. Significance

This paper represents a significant advancement in plan execution flexibility. By moving beyond simple reordering to block substitution, the authors demonstrate that flexibility can be maximized by fundamentally altering the plan's structure and action set, not just its sequence.

• Practical Impact: The method provides a computationally efficient alternative to expensive MaxSAT encodings, making high-flexibility planning feasible for larger, real-world problems.
• Robustness: The resulting plans are more robust to dynamic changes, as they offer more valid execution sequences.
• Future Directions: The authors suggest that the framework can be extended to explore random block formations, different initial planners, and applications in assumption-based planning and plan quality optimization.

In summary, the FIBS algorithm successfully bridges the gap between efficient sequential planning and highly flexible partial-order planning by introducing a mechanism to dynamically substitute subplans, achieving superior flexibility with competitive computational costs.