Automated planners are increasingly asked to say "no": no schedule of machines, robots or batteries can meet a deadline, or a safety rule can never be violated. In classical planning, where actions are instantaneous, a planner's "no" can be backed by an inductive certificate. This is a set of states that contains the start state, contains no goal state, and is closed under every action, so no plan can ever leave it. A small independent program can check such a certificate without trusting the planner. Temporal planning is the harder setting: actions last for a duration, carry conditions that must hold throughout, and sometimes must overlap for any plan to work ("required concurrency"). Here the best systems can now decide that a task is unsolvable, but they produce no artifact anyone else can check. The user has to trust a model checker, a translation into it, and the floating-point and timing tricks inside a search engine.
We propose inductive certificates of unsolvability for temporal planning with required concurrency, together with a checker that is formally verified against an already-formalized semantics of temporal planning. The core move is to split each durative action into a start event, an end event and an "open" period in which its invariant must hold. Closure is then stated over states that record which actions are currently open and a zone, meaning a convex set of possible values for those actions' running clocks. A certificate is a set of such states closed under starting an action, ending one, and letting time pass while respecting every open invariant. This turns the temporal decision procedures of Deciding Unsolvability in Temporal Planning under Action Non-Self-Overlapping into proofs that a third party can check.
Core Claim
Unsolvability of a temporal planning task with required concurrency can be certified by a finite, compact object whose validity is checked in time polynomial in its size, with soundness proved directly against PDDL 2.1 semantics rather than against any planner's internal encoding. The roles of the three directions are uneven. Operator closure verification supplies the notion of proof. Required concurrency is the regime that makes the problem non-trivial: When is Temporal Planning Really Temporal? showed that without it, temporal planning reduces to classical STRIPS, where certificates already exist. Temporal action decomposition into snap actions is the mechanism that makes closure expressible at all.
To make this precise, a certificate state is a triple $(s, O, Z)$. Here $s$ is the set of true facts, $O$ is the set of currently open durative actions, and $Z$ is a zone over one clock per open action. A certificate $C$ is a finite set of such triples, and it is valid when four conditions hold. The initial state, with no actions open and the clocks fixed at zero, lies in $C$. No triple in $C$ satisfies the goal with $O$ empty. For every triple in $C$, the successors under start events, end events and time elapse are covered by $C$:
$$ \mathrm{Post}_{\vdash}(C) \cup \mathrm{Post}_{\dashv}(C) \cup \mathrm{Post}_{\delta}(C) \subseteq C . $$
In this condition, $\mathrm{Post}_{\vdash}$ applies an applicable start event and adds a fresh clock. $\mathrm{Post}_{\dashv}$ applies an end event only where the action's duration bound is satisfiable within $Z$. $\mathrm{Post}_{\delta}$ lets the clocks advance only while the invariants of all actions in $O$ remain true in $s$. "Covered" means subsumed: some certificate triple has the same discrete part and a zone containing the successor zone.
The invariant restriction on time elapse is the ingredient missing from both prior formalisms. Inductive Certificates of Unsolvability for Domain-Independent Planning checks closure under atomic operators only. Formal Semantics and Formally Verified Validation for Temporal Planning checks invariants only along a single given trace. The file itself flags this gap: no existing work checks inductive closure over partially executed combinations of open actions.
Research Program
The work has three parts.
The first part is the certificate format and its soundness theorem. We formalize the four conditions above in Isabelle/HOL, on top of the boundary-event and invariant-interval semantics of Abdulaziz and Koller. That paper refines PDDL 2.1 temporal semantics into an executable validator with exact rational arithmetic and explicitly leaves unsolvability certificates as future work. We then prove that a valid certificate implies no valid plan exists. The delicate step is the $k$-normalization that Panjkovic et al. use to keep the number of zones finite: clock values above a constant $k$ are lumped together. Normalization over-approximates, which is harmless for a proof of non-existence only if the lumped states really do behave identically. We will prove this lemma inside the theorem prover instead of inheriting it from the search engine.
The second part is certificate generation. The cheapest generator records the fully explored, subsumption-closed state set of the TAMER-CTP search from Panjkovic et al. and emits it as an explicit list of discrete-state/zone pairs. A raw dump is likely to be large, so we add two compaction steps. The first merges triples whose zones are subsumed. The second lifts the discrete part to a symbolic set: a Binary Decision Diagram (BDD), a compact graph representation of a Boolean function, is attached to each (open-action set, zone) pair, in the style of the BDD certificates of Eriksson et al. Following the composite-certificate idea from the same paper, we also allow the certificate to project away facts irrelevant to the unreachable goal.
The third part, which is exploratory, goes beyond the no-self-overlap assumption. Checking a certificate does not need decidability, so the checker stays sound when the same action may run several times at once. Generating certificates in that setting is the open part. We will try a counting abstraction in which overlapping copies of one action share a clock pattern bounded by its duration. We will test it on self-overlapping domains of the kind CRIKEY3 targets in Planning with Problems Requiring Temporal Coordination. Failure in this part does not undermine the first two.
The vision and motion-synthesis work on phase decomposition, such as Structured Segment Networks, shares the start/course/end vocabulary but has no closure notion. We do not build on it.
Baselines
The naive reference point is the current practice: trust the decider's verdict with no certificate. On the unsolvable benchmark set of Panjkovic et al., OPTIC proves only 6 instances, and the paper attributes even these mostly to simple heuristic pruning. This anchors how little existing satisficing planners offer.
The strongest existing deciders come from the same paper. The authors report "nuXmv solved 151 unsolvable instances" and "TAMER-CTP solved 110." nuXmv is the strongest competitor on raw coverage. It translates the task into a timed transition system, and its verdict depends on that translation being correct. Our system runs TAMER-CTP plus certificate emission and checking on the same instances, the same machine and the same per-instance time limit. Certificate emission is charged to the generation time, and checking is reported separately. We beat the deciders in the sense that matters if we certify a large majority of the 110 TAMER-CTP verdicts, with checking time well below search time, and with zero certificates that the verified checker rejects. Any rejection would itself be an important finding: it would mean either a bug in the decider or an unsound normalization.
Three ablations isolate the key ingredients. The first drops the invariant restriction on time elapse and treats snap actions as classical operators. We expect the resulting "certificates" either to fail closure or to be accepted on instances where that acceptance is unsound. We will demonstrate the latter on hand-built required-concurrency instances that have a known plan. The second removes the subsumption-based covering and requires exact zone membership. The third removes the BDD lifting, to measure how much compaction contributes to certificate size.
Why not just…?
Why not just use the inductive invariant that nuXmv's model checker already computes? IC3-style model checking does produce invariants, and this is the most serious alternative. Such an invariant is closed under the translated timed transition system, so it certifies the translation, not the planning task. Our checker is grounded in the Isabelle semantics of Abdulaziz and Koller, which removes the translation from the trusted base. We will test whether this matters empirically by extracting nuXmv invariants where possible and comparing their size and check time with our certificates. If nuXmv invariants turn out comparably small, the right contribution narrows to a verified translation plus invariant re-checking, and we will report that honestly.
Why not just compile to classical planning and reuse classical certificates? The TP compilation of Jiménez Celorrio et al. fixes a concurrency bound $K$, so a classical certificate proves only that no plan exists with at most $K$ overlapping actions. Their TPSHE compilation covers only nested envelopes. We will count how many benchmark instances fall inside the envelope fragment, where this route gives a full proof. On all other instances it gives only a weaker, bounded claim.
Why not just dump TAMER-CTP's explored states and call that the certificate? This dump is in fact our first generator. On its own, though, it is neither checkable against planning semantics nor justified with respect to $k$-normalization. The verified checker and the normalization lemma are what turn it into a proof. The compaction ablation will show whether the raw dump is already small enough to be practical.
Why not just use plan-length bounds? Abdulaziz et al. bound plan length in classical state spaces. With continuous time there is no comparable finite bound on the number of events without first constructing the same zone abstraction, so this route reduces to ours.
Proposed Experiments
The main experiment uses the ANSO unsolvability benchmarks of Panjkovic et al.. These include MAJSP, PAINTER, and IPC domains made unsolvable through impossible battery or synchronization requirements. We report certified coverage, certificate size before and after compaction, generation overhead relative to plain TAMER-CTP, and verified check time. We also compare against the 151 instances nuXmv decides, to see which proofs only a model checker currently reaches.
For solvable sanity checks we use the 200-instance optimal-temporal set of Panjkovic and Micheli. There we certify that no plan exists with makespan below a bound, by adding a deadline. We compare the result against their abstract-step optimality argument, for which the file reports 110 of 200 instances solved versus 41 for OPTIC.
The decisive check is a soundness stress test. We inject known bugs into the generator, including wrong duration bounds, a dropped invariant, and an off-by-one in normalization, and confirm that the verified checker rejects every corrupted certificate. In addition, the invariant-free ablation must accept at least one false certificate on a hand-built instance whose only valid plan requires concurrency. If certification succeeds on most TAMER-CTP verdicts at modest overhead and the stress test behaves as expected, temporal planners will be able to issue a checkable "no" for the first time.
References
- Deciding Unsolvability in Temporal Planning under Action Non-Self-Overlapping
- When is Temporal Planning Really Temporal?
- Inductive Certificates of Unsolvability for Domain-Independent Planning
- Formal Semantics and Formally Verified Validation for Temporal Planning
- Planning with Problems Requiring Temporal Coordination
- Temporal Action Detection with Structured Segment Networks
- Temporal Planning With Required Concurrency Using Classical Planning
- A State-Space Acyclicity Property for Exponentially Tighter Plan Length Bounds
- Expressive Optimal Temporal Planning via Optimization Modulo Theory