When an automated planner is tasked with finding a path from an initial state to a goal, its job is straightforward: search the state space until a valid sequence of actions is discovered. The moment a plan is found, the search terminates, and the plan itself serves as an easily verifiable proof of success.
But what happens when a goal is completely impossible to reach?
Proving that a plan does not exist is fundamentally more difficult than finding one. As Eleanor Gilbert Rieffel et al. observe, there is a stark performance asymmetry in automated planning: search strategies optimized for goal discovery often struggle or fail to terminate when confronted with unsolvable tasks. A local search algorithm might wander endlessly through an infinite or exponentially large state space, unable to definitively declare that the goal is unreachable.
To transition automated planning from a tool for discovery into a framework for formal verification, planners must be able to prove unsolvability. This requires moving away from exhaustive state enumeration and toward elegant, mathematically rigorous certificates of impossibility.
The Core Mechanism: Inductive Sets and Operator Closure
How do you prove a state is unreachable without exploring every single path? The answer lies in finding a "trap" within the state space—a region that is impossible to escape.
In formal verification, this trap is known as an inductive set. An inductive set is a collection of states governed by operator closure: if you start at any state within this set and apply any valid action (operator), the resulting state is guaranteed to remain inside the same set.
[ Initial State ] ---> ( State A ) ---> ( State B )
| ^ |
v | v
( State C ) <--------------+-------- [ Operator Closure Trap ]
|
X <-- [ Valid Action ]
|
[ Goal State ] (Outside the Trap)
The utility of this concept for proving unsolvability was established early on. Tom Bylander demonstrated in Complexity Results for Serial Decomposability that verifying operator closure is a significant computational bottleneck (specifically, PSPACE-complete). However, if such a set can be identified, it provides an ironclad guarantee of unreachability.
Gabriele Röger and Salomé Eriksson et al. formalized this into a unifying theoretical basis for classical planning. They showed that the existence of an inductive set is both a necessary and sufficient condition for a planning problem to be unsolvable, provided it satisfies two conditions:
- It must contain the initial state.
- It must exclude all goal states.
Because of operator closure, any sequence of actions starting from the initial state will perpetually cycle within this inductive set. Since the goal states sit outside this boundary, the task is mathematically proven to be unsolvable.
Scaling to Continuous and Temporal Domains
While defining inductive sets is clean in discrete, classical planning, real-world systems operate in continuous time with numeric variables (such as fuel levels, velocities, or strict deadlines). In these hybrid domains, the state space becomes infinite, making unsolvability proofs even more elusive.
To tackle this, researchers bridge the gap between AI planning and formal model checking. For example, Daniele Magazzeni et al. translate continuous planning problems (written in PDDL+) into Hybrid Automata. This allows planners to leverage powerful model checkers like SpaceEx to prove plan non-existence across continuous trajectories. Similarly, Michael Cashmore et al. compile PDDL+ problems into Satisfiability Modulo Theories (SMT) formulas, allowing SMT solvers to rapidly determine when goals are unreachable under tight temporal constraints.
When dealing with time, proving that a goal cannot be reached also requires knowing when to stop looking. Charles Gretton et al. address this by analyzing state-space acyclicity to derive exponentially tighter upper bounds on plan lengths. If a planner can prove that no plan can possibly exceed a certain number of steps, it can safely terminate and declare a problem unsolvable once that bound is reached.
For complex temporal planning under specific constraints—such as when actions cannot overlap with themselves—the authors of Deciding Unsolvability in Temporal Planning under Action Non-Self-Overlapping utilize symbolic model checking and heuristic search over normalized temporal regions. This approach successfully forces termination on over a hundred benchmark instances where traditional planners would otherwise diverge into infinite loops.
Making Unsolvability Verifiable and Explainable
If a planner runs an algorithm and outputs "Unsolvable," how can an external user trust that result? Planners are complex software systems prone to bugs; a "no solution" output could simply be the result of a missing pointer or an incorrect heuristic pruning.
To build trust, a planner must output an unsolvability certificate—an independent mathematical proof that can be verified by a separate, lightweight validator. Gabriele Röger pioneered this framework, establishing that certificates must be complete, efficiently generatable, and general enough to span different planning algorithms.
To achieve the absolute "gold standard" of trust, Lukas Koller et al. developed a formally verified plan validator using the Isabelle/HOL theorem prover. While validating a successful plan is straightforward, the authors highlight that verifying certificates of unsolvability remains the critical frontier for ensuring complete trust in automated reasoning.
However, a mathematically rigorous certificate (like a massive list of state invariants) is often completely indecipherable to humans. If an autonomous spacecraft planner determines a command sequence is impossible, the human operator needs to know why.
Sarath Sreedharan et al. bridged this gap by translating abstract unsolvability certificates into human-centric explanations. By computing hierarchical abstractions and identifying unreachable "landmarks" (essential subgoals that cannot be satisfied), their system can explain the specific limiting factors to a human operator, turning an abstract inductive set into an understandable justification.
The Dual Value of Unsolvability
The ability to prove a task is unsolvable is not just a defensive mechanism to prevent infinite loops; it is a powerful tool that can be leveraged to solve entirely different classes of problems.
1. Multi-Agent Safety and Social Laws
In multi-robot systems, researchers design "social laws"—robust coordination rules that prevent robots from colliding or causing deadlocks. To verify that a social law is truly robust, you must prove that no sequence of actions can ever lead to a failure state.
As Ronen Nir et al. demonstrate, this verification problem can be compiled directly into a temporal planning task where a "successful plan" represents a system failure. Therefore, proving that a social law is safe is mathematically identical to proving that the compiled planning task is completely unsolvable. When moving to complex numeric settings, Ronen Nir et al. show that the bottleneck for multi-agent safety verification rests entirely on the capacity of state-of-the-art numeric planners to generate these difficult unsolvability proofs.
2. Certifying Top-Quality Planning
In many applications, users do not just want one optimal plan; they want a set of the top-$k$ alternative plans to account for unmodeled preferences. But how can a planner certify that its list of alternative plans is complete and that no higher-quality plan was missed?
Michael Katz et al. established a formal equivalence between plan set certification and restricted task unsolvability. Once the top plans are discovered, a new, restricted planning task is formulated where those discovered plans are blocked. If the planner can prove that this new, restricted task is entirely unsolvable, it serves as a definitive certificate that the original set of plans was complete and of the highest possible quality.
Ultimately, whether verifying the safety of interacting robots, validating the completeness of a plan search, or ensuring an autonomous system fails gracefully, the underlying engine remains the same: the systematic, verifiable proof of operator closure over an inductive set.
Key Foundational Work
Parametrized Families of Hard Planning Problems from Phase Transitions (2014) — contributed 3 concept elements to this direction.
Complexity Results for Serial Decomposability (1992) — contributed 2 concept elements to this direction.
Planning as Model Checking in Hybrid Domains (2014) — contributed 1 concept elements to this direction.