cs.LOOct 11, 2025

Formally Verified Certification of Unsolvability of Temporal Planning Problems

Authors: David Wang, Mohammad Abdulaziz

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

Appendix figures & tables12 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. Synthesis of timeline-based planning strategies avoiding determinization

    Jul 23, 2025Dario Della Monica, Angelo Montanari, Pietro SalaTemporal Planning

  2. Planning Task Shielding: Detecting and Repairing Flaws in Planning Tasks through Turning them Unsolvable

    Apr 8, 2026Alberto Pozanco, Pietro Totis, Marianela Morales +1

  3. An Undecidability Proof for the Plan Existence Problem

    Apr 24, 2026Antonis AchilleosSymbolic PlanningDynamic Epistemic Logic