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.