Eliminating Redundant Actions in Automated Planning

57 concepts35 papers

Why do automated planners do extra work? Imagine a robot tasked with painting a wall. It picks up a brush, puts it down to open a paint can, picks up the brush again, stirs the paint with a stick, puts the brush down, and finally begins painting. The wall gets painted, but the sequence of actions is bloated and inefficient.

In AI planning, this phenomenon is known as plan redundancy. As explained by Mauricio Salerno et al. in Eliminating Redundant Actions from Plans Using Classical Planning, fast "satisficing" planners prioritize speed over optimality. This trade-off frequently introduces unnecessary loops, cyclical operations, or extraneous steps that increase execution costs without contributing to the final goal.

To formalize this intuition, Dennis F. Kibler et al. in Don't Be Stupid define an inefficient plan as any sequence of operations that contains a proper sub-plan capable of achieving the exact same goal. If you can delete a subset of actions from a plan and the remaining sequence still succeeds, those deleted actions are completely redundant.

Why Redundancy Creeps In

Redundancy is rarely a random error; it is usually an inherent byproduct of how planning problems are decomposed, relaxed, or parallelized.

  • Schema Constraints vs. Functional Necessity: Anthony Barrett in Task-Decomposition via Plan Parsing observes that top-down hierarchical planners often add actions simply because a high-level recipe or schema requires them, rather than because they are functionally necessary to achieve the specific goal state.
  • Uncoordinated Plan Merging: When a planner solves multiple subgoals independently and then stitches them together, it often duplicates effort. As shown by David E. Foulser et al. in A Quantitative Theory for Plan Merging, naive planners repeatedly acquire and release the same resource because they lack a mechanism to consolidate overlapping operations across sub-plans.
  • Relaxation and Parallelism Artifacts: Modern planners often use "delete relaxation" to estimate distances to a goal by assuming actions never undo progress. However, Michael Katz et al. in Red-Black Relaxed Plan Heuristics point out that these heuristics can inherit logical gaps from the relaxation, leading to estimated plans with cyclical actions. Similarly, when planners maximize parallel execution, they often introduce redundant actions that are temporally efficient but resource-wasteful, as observed by Miquel Bofill et al. in Relaxed Exists-Step Plans in Planning as SMT.

Detecting Redundancy via Justification and Relevance

To eliminate redundancy, we must first detect it. The most prominent framework for this is Action Justification Analysis.

In A Survey on Plan Optimization, Pascal Bercher et al. describe how justification analysis evaluates the necessity of plan steps by verifying whether their effects causally contribute to subsequent preconditions or the final goal. If an action’s effects are never consumed, or are overridden before they can be used, the action is unjustified and can be safely excised.

This concept is highly relevant even in complex, non-deterministic policies. Sarath Sreedharan et al. in Generalizing Action Justification and Causal Links to Policies discovered that even state-of-the-art planners generate policies where up to 25% of the actions are entirely unjustified, highlighting a massive opportunity for post-processing optimization.

Alternatively, we can analyze redundancy through Path Subsumption. Patrik Haslum et al. in Safe, Strong, and Tractable Relevance Analysis for Planning formalize a hierarchy where one sequence of transitions is deemed more general if it achieves the same goal with fewer requirements and no additional cost, allowing for the systematic pruning of redundant actions.

The Mechanics of Elimination

Once redundancy is detected, how do we remove it? Researchers have developed several elegant mathematical reformulations to clean up messy plans.

Planning as a Remedy for Planning

Instead of writing a custom optimization algorithm from scratch, the authors of Eliminating Redundant Actions from Plans Using Classical Planning reformulate redundancy removal as a secondary classical planning task.

Given an initial suboptimal plan, they construct a new state space where every action from the original plan is turned into a choice: the agent can either execute the action at its original cost, or skip it entirely at zero cost. An off-the-shelf optimal planner is then deployed in this new state space. Because the optimal planner seeks the absolute lowest cost, it naturally chooses to skip any action whose effects are not strictly required to reach the final goal.

MaxSAT and MaxSMT Encodings

Another approach compiles the plan into a logical formula where action inclusion is penalized. As demonstrated by Miquel Bofill et al. in Relaxed Exists-Step Plans in Planning as SMT and Christian Muise et al. in Optimally Relaxing Partial-Order Plans with MaxSAT, a hierarchical optimization strategy can be used.

The solver treats the plan's validity as a "hard constraint" (the goal must be reached) and the absence of actions as "soft constraints" (penalizing the inclusion of each step). The solver is forced to satisfy the goal constraints while minimizing the penalty, effectively pruning away redundant steps and minimizing ordering constraints to maximize execution flexibility.

Shortest Common Supersequence (SCS)

When the problem involves merging multiple independent plans into one cohesive sequence, David E. Foulser et al. in A Quantitative Theory for Plan Merging reduce the problem to the Shortest Common Supersequence problem. By mapping plan steps to characters in a string, they utilize string-matching dynamic programming to find the minimum sequence of actions required to satisfy multiple goals simultaneously.

Upstream Prevention: Pruning the Search Space

Cleaning up a plan after generation is effective, but preventing redundancy during the search phase avoids the "search space explosion" entirely.

Evaluating actions in large domains is computationally expensive because planners waste significant time on actions that are applicable but irrelevant to the goal (Sung‐Wook Yoon et al. in Improving Determinization in Hindsight for On-line Probabilistic Planning). To combat this, techniques like task scoping (Nishanth Kumar et al. in Task Scoping for Efficient Planning in Open Worlds (Student Abstract)) and partial grounding (Daniel Gnad 0001 et al. in Learning How to Ground a Plan - Partial Grounding in Classical Planning) isolate only the relevant parts of a planning task before search begins, preventing the planner from processing massive amounts of redundant operators.

Finally, Dennis F. Kibler et al. in Don't Be Stupid show that applying "negative heuristics"—rules that explicitly define what not to do—allows forward-chaining systems to navigate massive state spaces with almost no wasted search. By aggressively pruning strategically useless moves before they are even explored, the planner avoids generating redundant sub-sequences in the first place.

Key Foundational Work

A Quantitative Theory for Plan Merging (1991) — contributed 4 concept elements to this direction.
Don't Be Stupid (1981) — contributed 2 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_plan_redundancy_6ba884b9,
  title = {plan redundancy},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/plan-redundancy/rdr_6ba884b933ea4d7db04022febe65287c},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_plan_redundancy_6ba884b9_v1,
  title = {plan redundancy},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/plan-redundancy/rdr_6ba884b933ea4d7db04022febe65287c/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}

See something wrong? Report a mistake