cs.LOOct 11, 2025
SaveFormally Verified Certification of Unsolvability of Temporal Planning Problems
Organizations: King’s College London
Abstract
We present an approach to unsolvability certification of temporal planning. Our approach is based on encoding the planning problem into a network of timed automata, and then using an efficient model checker on the network followed by a certificate checker to certify the output of the model checker. Our approach prioritises trustworthiness of the certification: we formally verify our implementation of the encoding to timed automata using the theorem prover Isabelle/HOL and we use an existing certificate checker (also formally verified in Isabelle/HOL) to certify the model checking result.
Figures & tables
Figure 1: The planner architecture proposed by Abdulaziz and Kurz [ 3 ] , combining verified (solid) and unverified (dotted) modules. The input is a grounded planning problem, which is encoded into an automaton by a verified encoder, the automaton is checked by an efficient, unverified model checker, and the result is certified with a verified certificate checker.
Figure 3: The main automaton and an automaton for some action .
| Domain (#inst) | ours | T-CTP | T-FTP | OPTIC | nuXmv | UPPAAL | ||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| MatchCellar (9) | (5/1/0) | 3 | (2/5/0) | 2 | (7/0/0) | 2 | (0/6/0) | 3 | (7/0/0) | 2 | (6/0/0) | 3 |
| SYNC (8) | (5/0/0) | 3 | (3/0/0) | 5 | (0/8/0) | 0 | (2/6/0) | 0 | (2/0/0) | 6 | (4/0/0) | 4 |
| PAINTER (12) | (10/1/0) | 1 | (7/0/0) | 5 | (2/10/0) | 0 | (8/2/0) | 2 | (8/0/0) | 4 | (8/0/0) | 4 |
| MAJSP-1 (128) | (72/51/5) | 0 | (56/60/0) | 12 | (84/44/0) | 0 | (84/43/0) | 1 | (106/0/0) | 22 | (127/0/0) | 1 |
| MAJSP-2 (240) | (84/82/6) | 68 | (86/66/0) | 88 | (212/28/0) | 0 | (103/37/0) | 100 | (128/0/0) | 112 | (185/0/1) | 54 |
| Total (397) | (176/135/11) | 75 | (154/131/0) | 112 | (305/90/0) | 2 | (197/94/0) | 106 | (251/0/0) | 146 | (330/0/1) | 66 |
Table 1: For each domain/method pair: in parentheses the number of timeouts, memouts, and unknowns (crash or no verdict), followed by the number of instances proved unsolvable ( bold , right-aligned). Here, we have our pipeline (ours) and OPTIC run on PDDL; TAMER run on ANML [ 83 ] with their CTP (T-CTP) and FTP (T-FTP) algorithms; and nuXmv and UPPAAL run on the respective encodings emitted by TAMER.
Appendix figures & tables12 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 4: Automata for the actions of the plan in Figure 2 . Dashed edges are applied to simulate ( ) and solid ones to simulate ( ). The order is indicated with respect to each time point as .
Figure 5: Interfering actions of Example 2 . (a) The start snap actions of two mend actions both require and delete , so they interfere and cannot be scheduled at the same time point. (b) The second mend can start after the first has ended and added again.
Figure 6: Timeline (top) and partial state space (bottom) of Example 2 with transitions representing executions of durative actions and time delays , , . Each state is shown at its time point before the snap actions of that time point are applied. Starting at , when ends, is forbidden according to Definition 13 (hatched box in the timeline; in the state space, the pair of transitions from to ): adds , which requires, so the second mend can only start after a delay ( ).
Figure 7: Interfering actions in Example 4 . Two robots picking up the same block. Both starting snap actions are conditioned on and delete .
Figure 8: A timed automaton with named locations. The action transition checks the condition and the guard , applies the update , and resets .
Figure 9: Parts of candidate plans for Example 4 .
Figure 10: Examples of automata for actions from Figure 9 . Dashed edges are applied to simulate ( ) and solid ones to simulate ( ). The order is indicated with respect to each time point.
| Size of formalisation | |||||||
| Component | Lines of code (thousands) by attribution | ||||||
| Human | Human + AI | AI | Total | ||||
| Propositional | |||||||
| Abstract temporal planning semantics | 6.9 | (98 %) | 0.1 | ( 1 %) | 0.1 | (2 %) | 7.0 |
| Reduction in Section 3 | 1.1 | (97 %) | 0.1 | (3 %) | 0.1 | ( 1 %) | 1.1 |
| Technical setup for proofs | 4.1 | (95 %) | 0.2 | (5 %) | 0.1 | ( 1 %) | 4.3 |
Table 2: Size of formalisations (percentages rounded to sum to 100 %)
| Size of related formalisations | |
|---|---|
| Formalisation | Lines of code |
| Verified SAT-based planner [ 3 ] | |
| Formal semantics and a verified plan validator for temporal PDDL [ 2 ] | |
| Formal semantics and a verified plan validator for classical PDDL [ 4 ] | |
| Formal semantics of Markov Decision Processes (MDPs), a verified solver for MDPs and certificate checker for linear programming solutions [ 82 ] | |
| Verified MDP algorithms [ 81 ] | |
Figure 11: Locale extensions ( ) add and sublocales ( ) replace definitions and assumptions: timed automata ( ), planning problem ( ), plan ( {\mathop{{\pi}}\limits^{\vbox to-1.0pt{\kern-2.0pt\hbox{\scriptsize\rightarrow}\vss}}} ), abstract syntax ( ), unique naming functions ( ), executable definitions ( ), groundedness ( ), annotated actions as snap actions ( ), lists as sets ( ), machine integers as clock constraints ( ).
Figure 12: (a) Cumulative number of instances (of 397) proved unsolvable within a given wall time (timeout 1800 s); total in legend. (b) Per-stage times of our pipeline for the 75 certified-unsolvable instances, normalised per instance.
| tck-reach (s) | end-to-end (s) | certificate (MB) | |||||||
|---|---|---|---|---|---|---|---|---|---|
| Instance | covreach | aLU | covreach | aLU | covreach | aLU | |||
| MatchCellar 02 | 0.016 | 0.015 | 1.1 | 0.29 | 0.27 | 1.1 | 1 | 1 | – |
| MatchCellar 03 | 0.031 | 0.025 | 1.2 | 0.55 | 0.43 | 1.3 | 1 | 1 | – |
| MatchCellar 04 | 140 | 14.4 | 9.7 | 427 | 92 | 4.6 | 835 | 242 | 3.5 |
| SYNC 1_2 | 0.016 | 0.017 | 0.9 | 0.28 | 0.27 | 1.0 | 1 | 1 | – |
| SYNC 1_3 | 0.181 | 0.091 | 2.0 | 1.66 | 0.94 | 1.8 | 2 | 1 | 2.0 |
Table 3: The table shows the times for TChecker’s reachability check and the end-to-end pipeline, and the size of the emitted certificates. “covreach” here refers to TChecker not exploring states covered in the zone graph twice and aLU refers to detecting coverage using LU-abstracted zone graphs. Note that the end-to-end figure stops when the certificate is rejected for the aLU algorithm, which might overrepresent the time savings, but not by much, given the distribution of time taken for each stage (see Figure 12 ) and the clearly smaller state space to check.
Qualitative timeline-based planning models domains as sets of independent, but interacting, components whose behaviors over time, the timelines, are governed by sets of qualitative temporal constraints (ordering relations), called synchronization rules. Its plan-existence problem has been shown to be PSPACE-complete; in particular, PSPACE-membership has been proved via reduction to the nonemptiness problem for nondeterministic finite automata. However, nondeterministic automata cannot be directly used to synthesize planning strategies as a costly determinization step is needed. In this paper, we identify a fragment of qualitative timeline-based planning whose plan-existence problem can be directly mapped into the nonemptiness problem of deterministic finite automata, which can then synthesize strategies. In addition, we identify a maximal subset of Allen's relations that fits into such a deterministic fragment.
Planning Task Shielding: Detecting and Repairing Flaws in Planning Tasks through Turning them Unsolvable
Most research in planning focuses on generating a plan to achieve a desired set of goals. However, a goal specification can also be used to encode a property that should never hold, allowing a planner to identify a trace that would reach a flawed state. In such cases, the objective may shift to modifying the planning task to ensure that the flawed state is never reached, in other words, to make the planning task unsolvable. In this paper we introduce planning task shielding: the problem of detecting and repairing flaws in planning tasks. We propose three different approaches to solve these tasks, each aiming to minimize the number of modifications to the original actions that render the planning task unsolvable.
An Undecidability Proof for the Plan Existence Problem
The plan existence problem asks, given a goal in the form of a formula in modal logic, an initial epistemic state (a pointed Kripke model), and a set of epistemic actions, whether there exists a sequence of actions that can be applied to reach the goal. We prove that even in the case where the preconditions of the epistemic actions have modal depth at most 1, and there are no postconditions, the plan existence problem is undecidable. The (un)decidability of this problem was previously unknown.