When searching through massive combinatorial spaces—whether in automated planning, theorem proving, or inductive logic programming—we face a fundamental bottleneck: the curse of dimensionality. To make search tractable, we must aggressively prune branches of the search tree. However, pruning introduces a dangerous risk: what if we accidentally discard the only valid solution, or the single optimal path?
The core insight of completeness-preserving pruning (also known as admissible pruning) is that we can drastically reduce the search space without sacrificing correctness. By establishing formal safety criteria, we can guarantee that if a solution exists in the original search space, at least one valid path to a solution (or an optimal solution) remains discoverable in the reduced space.
The Core Principle: Admissibility and Safety
What makes a pruning strategy "safe"? As Mark Drummond et al. established in Goal Ordering in Partially Ordered Plans, an admissible pruning strategy ensures that if a valid solution exists, at least one path to that solution is preserved. In cost-optimal settings, this requirement becomes even stricter: the pruning rules must never exclude actions or states that are necessary to achieve a globally optimal policy or minimum-cost plan (Using Domain-Configurable Search Control for Probabilistic Planning; Integrating Partial Order Reduction and Symmetry Elimination for Cost-Optimal Classical Planning).
To build intuition, imagine a maze where multiple paths lead to the exit. A completeness-preserving algorithm can block off entire hallways, provided it can mathematically prove that an equal or better path to the exit remains open elsewhere. If the pruning function is proven safe, the solver will converge to the exact same optimal solution while exploring only a fraction of the state space (On Weak Stubborn Sets in Classical Planning; Boosting Abductive Reasoning with Functional Literals).
Collapsing Redundancy via Symmetry and Equivalence
One of the most intuitive ways to safely prune a search space is by identifying redundancies caused by symmetric actions or states. If two actions achieve the exact same outcome, exploring both is a waste of computational effort.
In Action-Space Partitioning for Planning, Natalia Hernandez-Gardiol et al. partition the action space into sets of equivalent actions. Instead of expanding every possible ground action, the search tree only expands a single successor state for each equivalence class. Completeness is preserved because any plan reachable through a pruned action is guaranteed to have a functionally identical counterpart in the explored space.
Similarly, in classical planning, Martin Wehrle et al. integrate partial order reduction (which ignores redundant action sequences) with symmetry elimination (which treats identical states as one) via Symmetrical Strong Stubborn Sets (Integrating Partial Order Reduction and Symmetry Elimination for Cost-Optimal Classical Planning). By enforcing formal safety criteria, they combine these distinct reduction strategies without risking the loss of the minimum-cost plan.
Enforcing Plan Minimality to Break Infinite Loops
In plan-space planning, algorithms frequently suffer from the "looping" problem, where they get stuck in infinite search branches by repeatedly re-establishing the same preconditions. To resolve this, Subbarao Kambhampati introduced pruning strategies based on plan minimality (Admissible Pruning Strategies based on plan minimality for Plan-Space Planning).
The intuition is straightforward: an optimal or minimal plan should not contain redundant steps or steps that can be simplified away. By evaluating a partial plan and retaining only the preconditions that are necessarily true, the planner can detect if a branch is non-minimal. If a simplified representation reveals that a plan is redundant, the entire search branch can be safely discarded.
As shown by the authors of Raghavan Snntvasan and (ijcai 1995), extending this concept of minimality to incomplete partial plans allows the algorithm to terminate infinite loops before a complete, non-minimal solution is ever generated. However, they note a key nuance: while this strategy (such as Nsat-prune) is admissible for non-causal link planners, it can become inadmissible for causal link planners, highlighting how tightly pruning strategies are coupled to the underlying search architecture.
Pruning via Dominance and Relevance
Beyond exact symmetries, we can prune states that are strictly worse than others through dominance relations. In satisficing planning—where the goal is to find any valid plan quickly rather than the absolute cheapest—Álvaro Torralba defines a dominance relation focused entirely on preserving completeness (Completeness-Preserving Dominance Techniques for Satisficing Planning). This approach prunes states by identifying those that have achieved fewer serializable sub-goals, ensuring that unsolvable states never dominate solvable ones, thereby preventing the search from getting trapped in dead ends.
Another approach to pruning focuses on filtering out irrelevant knowledge or objects before the search even begins. In mechanical theorem proving, David A. Plaisted demonstrated that a knowledge base can be pruned by removing facts beyond a specific graph distance from the support set (An Efficient Relevance Criterion for Mechanical Theorem Proving). This preserves completeness by guaranteeing that if a proof of a certain length exists in the original set, a proof of equal or lesser length remains in the reduced subset.
A modern parallel appears in robotic Task and Motion Planning (TAMP). Hongyou Zhou et al. utilize deep vision models to identify which objects in a cluttered scene are relevant to a task, pruning the rest (Spatial Reasoning via Deep Vision Models for Robotic Sequential Manipulation). However, they highlight an inherent tension: over-aggressive filtering can lead to incompleteness if a necessary but non-obvious object is accidentally ignored.
The Fragility of Combined Pruning Rules
Designing a single safe pruning rule is challenging, but combining them is even harder. Geoffrey Chu et al. point out that when multiple dominance-breaking constraints are integrated into constraint programming, they risk interacting destructively and removing all optimal solutions (Dominance breaking constraints). Proving the compatibility of various pruning rules is essential to ensure the search remains both sound and complete.
Furthermore, as P. Alex Dow et al. observe in depth-first search for treewidth computation, aggressive duplicate avoidance can inadvertently cause inadmissibility (Duplicate Avoidance in Depth-First Search with Applications to Treewidth). This happens when pruning a node based on a specific path accidentally blocks all valid paths to a required child state.
To safely bypass these pitfalls, researchers rely on formal proofs of soundness. For instance, in database query rewriting, Mélanie König et al. highlight the need for a formally defined rewriting operator to avoid losing completeness when discarding redundant queries (Sound, Complete and Minimal UCQ-Rewriting for Existential Rules). Similarly, in inductive logic programming, Andrew Cropper et al. demonstrate "optimally sound pruning" by automatically extracting logical constraints from background knowledge, ensuring the search only discards rules that are guaranteed to be unsatisfiable or suboptimal (Learning Logic Programs by Discovering Where Not to Search).
Key Foundational Work
An Efficient Relevance Criterion for Mechanical Theorem Proving (1980) — contributed 3 concept elements to this direction.
Goal Ordering in Partially Ordered Plans (1989) — contributed 1 concept elements to this direction.