Pseudo-Boolean Proof Logging for Optimal Classical Planning
Simon Dold, Malte Helmert, Jakob Nordström, Gabriele Röger, Tanja Schindler · 2025
Read Pseudo-Boolean Proof Logging for Optimal Classical Planning by Simon Dold, Malte Helmert, Jakob Nordström, Gabriele Röger, Tanja Schindler (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-18443.txt.
Introduction
Simon Dold and four colleagues add proof logging to optimal classical planning, the task of finding the cheapest valid plan for a stated problem. A solver's claim that no plan exists, or that its plan is best, is usually taken on trust. Their work lets an outside party check the claim.
The framework issues lower-bound certificates built from pseudo-Boolean constraints. It does not depend on which planning algorithm produced the answer. As a case study, the team adapts the A-star search to log proofs of optimality at modest extra cost. They show the method for two standard heuristics, pattern databases and the h-max rule. Any heuristic whose steps fit the same logic can join in.
Catalog record
| CREATOR | Simon Dold, Malte Helmert, Jakob Nordström, Gabriele Röger, Tanja Schindler |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 103 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-18443
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Pseudo-Boolean Proof Logging for Optimal Classical Planning Simon Dold, Malte Helmert, Jakob Nordström, Gabriele Röger, Tanja Schindler Abstract We introduce lower-bound certificates for classical planning tasks, which can be used to prove the unsolvability of a task or the optimality of a plan in a way that can be verified by an independent third party. We describe a general framework for generating lower-bound certificates based on pseudo-Boolean constraints, which is agnostic to the planning algorithm used. As a case study, we show how to modify the A ∗ \textup{A}^{*} algorithm to produce proofs of optimality with modest overhead, using pattern database heuristics and h max h^{\textup{max}} as concrete examples. The same proof logging approach works for any heuristic whose inferences can be efficiently expressed as reasoning over pseudo-Boolean constraints. 1 University of Basel, {simon.dold, malte.helmert, gabriele.roeger, tanja.schindler}@unibas.ch, 2 University of Copenhagen, 3 Lund University [email protected] Introduction Optimal classical planning algorithms make three promises: that the plans they produce are correct, that no cheaper plans achieving the goal exist, and that any task reported as unsolvable actually is. As McConnell et al. ( 2011 ) argue in their seminal work on certifying algorithms , there are many good reasons not to accept such promises blindly. Instead, a certifying planning algorithm outputs some kind of proof (a certificate ) that an independent third party can use to verify the truthfulness of the planner’s claims. For the correctness of plans, such a verification is performed routinely: the generated plans themselves serve as certificates for this, and plan validation tools such as VAL ( Howey and Long 2003 ) or INVAL ( Haslum 2016 ) can be used to check that the produced plans are correct. For unsolvability, Eriksson et al. ( Eriksson, Röger, and Helmert 2017 ; Eriksson, Röger, and Helmert 2018 ; Eriksson and Helmert 2020 ) recently introduced two forms of unsolvability certificates that cover very diverse planning algorithms. Certifying the optimality of plans, in contrast, is still in its infancy. The only existing work in this direction is a paper by Mugdan, Christen, and Eriksson ( 2023 ) which describes two approaches: one based on a compilation to unsatisfiability, and one based on an extension of the unsatisfiability proof system of Eriksson, Röger, and Helmert ( 2018 ) . The first approach is in general not computationally feasible, as it requires a task reformulation that increases the number of state variables and actions exponentially in the size of the planning task. The second approach does not share this weakness, but is not sufficiently general to encompass a wide range of planning approaches. Mugdan, Christen, and Eriksson identify five essential properties for optimality certificates: soundness (if an optimality certificate is accepted by the verifier, then optimality holds), completeness (if a solution is optimal, then a certificate of its optimality exists), efficient generation (a non-certifying algorithm can be changed to produce certificates with reasonable, at most polynomial overhead), efficient verification (the verifier runtime is polynomial in the task and certificate size), and generality (certificates can be efficiently produced by a wide variety of different planning algorithms rather than being algorithm-specific). Mugdan, Christen, and Eriksson show that their approach is sound and complete, but critically comment that “the other three properties for practical usability do not have clear-cut answers”. Compared to the unsolvability proof system of Eriksson et al., their approach appears much more specific to heuristic forward search using heuristics that are themselves based on some kind of forward search, such as the h^{\textup{max}} heuristic ( Bonet and Geffner 2001 ) . For example, it is not at all clear how to certify heuristics computed in a backward direction, such as pattern databases ( Edelkamp 2001 ) or other abstraction heuristics without redoing the abstract state space exploration for every heuristic evaluation. While in the planning community the interest in certifying algorithms is quite recent, they are standard in the SAT community, where unsatisfiability certificates based on proof systems like DRAT ( Heule, Hunt, and Wetzler 2013 ) and LRAT ( Cruz-Filipe et al. 2017 ) are required for participating in SAT competitions and supported by formally verified checkers ( Tan, Heule, and Myreen 2023 ; Lammich 2020 ) . A recently proposed alternative are pseudo-Boolean proofs based on cutting planes, which are supported by the formally verified checker VeriPB ( Bogaerts et al. 2022 ) . Unlike the other proof systems mentioned, cutting planes are able to directly incorporate linear arithmetic, making them very appealing for optimization problems such as optimal classical planning. Indeed, VeriPB has been applied to a wide range of optimization problems such as MaxSAT ( Berg et al. 2023 ) , ILP presolving ( Hoen et al. 2024 ) , constraint programming ( Gocht, McCreesh, and Nordström 2022 ; McIlree and McCreesh 2023 ; McIlree, McCreesh, and Nordström 2024 ) , and dynamic programming ( Demirović et al. 2024 ) . Figure 1: Interaction of Components In this work, we propose to certify plan optimality by means of such pseudo-Boolean proofs. We claim that our optimality certificates have all five desirable properties discussed above: they are sound, complete, efficiently generatable, efficiently verifiable, and general. (For space reasons, the generality of the proof system must remain a conjecture for the time being, but at least we show that we can cover the techniques covered by Mugdan et al. as well as pattern database heuristics that their approach struggles with.) The overall concept is shown in Figure 1 . In addition to a plan, the certifying planning system produces an optimality certificate that proves that the input task has no cheaper solution. A plan validator such as VAL verifies that the plan solves the task and determines its cost. The optimality verifier has access to the original task, the plan cost determined by the validator, and the certificate from the planning system. On this basis it verifies that the plan is indeed optimal. The certificate is based on cutting planes proofs with reification ( Bogaerts et al. 2023 ) , in which the atomic pieces of knowledge are pseudo-Boolean constraints. Such constraints allow us to reason conveniently about costs of actions and bounds on costs to reach a state. Roughly speaking, the certificate describes an overapproximation of which states can be reached at which cost and shows that no goal state can be reached at a cost below the claimed optimal plan cost. The heart of the proof is a standard pseudo-Boolean proof that can be verified by an off-the-shelf proof checker such as the VeriPB system. The paper is structured as follows: we introduce the general framework for certifying plan optimality by providing an encoding of planning tasks as pseudo-Boolean constraints and defining lower-bound certificates. Next, we define heuristic certificates, which represent the concept of an admissible heuristic estimate as pseudo-Boolean constraints. We then show how heuristic certificates can be used to integrate proof-logging into \textup{A}^{*} , capturing the arguments for optimality of \textup{A}^{*} with an admissible heuristic on a given state space as pseudo-Boolean constraints. Finally, we describe how heuristic certificates for pattern database heuristics and h^{\textup{max}} can be generated, which amounts to proving the admissibility of these heuristics with pseudo-Boolean constraints. Background We first introduce the