Logical Regression for Planning with Axioms

Logical Regression for Planning with Axioms Connor Little, Christian Muise { connor.little, christian.muise } @queensu.ca Queen’s University Kingston ON, Canada

arXiv:2607.21414v1 [cs.AI] 23 Jul 2026

Abstract In automated planning, logical regression is an operation that returns the most general condition necessary for an action to achieve a particular formula. It has many applications, such as allowing for more robust plan execution and providing compact policies for non-deterministic planning. Although relatively simple to calculate in basic planning settings, logical regression becomes significantly more complex when additional factors, such as axioms, are present. We introduce a methodology for approximating the logical regression of an action in a domain that includes axioms; an approximation that limits conditions to partial states. Our method produces minimal partial states while avoiding the recalculation of axioms. To demonstrate the impact of our methods, we embed our form of regression in an execution monitoring context, a well-established setting that can benefit greatly from logical regression. Our results show that this form of regression can dramatically generalize partial states across multiple domains, reducing the number of variables considered for execution monitoring by up to 70%, and demonstrate that the resulting execution monitor is robust enough to recover frequently in an environment with unexpected changes: several domains recover over 50% of the time in our tests.

1

Introduction

In classical planning, a planner begins with a complete initial state and one or more goal conditions. A plan is created by finding a sequence of actions from the initial state to a goal state. The aim of a planner is to generate a plan given a description of a domain. Many powerful language features and techniques have been proposed to help improve planner capabilities. One such language feature is the use of axioms). Axioms are rules that define the conditions in which a derived variable would be true. This distinguishes these variables from basic variables, which are assigned values through the application of operators. Axioms offer multiple benefits, such as allowing for more natural expressions of phenomena, and a jump in complexity that cannot be efficiently compiled away (Thiébaux, Hoffmann, and Nebel 2005). Axioms facilitate a smaller search space when exploring through best-first search algorithms and can be computed recursively. Despite this, many planners do not supCopyright © 2026, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

port them due to the complexity and additional implementation work they would entail. While the expressive power of axioms has been explored in the context of plan generation, other related settings in automated planning have had far less focus. We are specifically interested in bringing this expressive power to logical regression, a technique typically used for generalized execution monitoring (Fritz and McIlraith 2007) or richer planning settings (Muise, McIlraith, and Beck 2024). Logical regression is the calculation of the most general condition that ensures that an action achieves a given formula. Incorporating regression allows some planners, notably nondeterministic planners such as PR2, to become more generalized and more robust by permitting operators to be called on more than a single state. This can be useful when the environment in which the plan will be executed is unpredictable. If, during execution, the state changes unexpectedly, the agent must decide how to recover. Under these conditions, executing the plan exactly as given can lead to unexpected states and inevitably fail. Calculation of the complete regression formula is complex and expensive in many cases. As such, we introduce an approximation of this regression. The complete regression provides a formula that is biconditional: A formula will hold given a state after the execution of an action if and only if the regression of that formula over an action is entailed by that state. The approximation is less restrictive. It merely states that the formula will hold if the operator is applied. The form of approximation we consider is to restrict the regression to only be represented by partial states. We introduce a novel method to efficiently compute an approximate logical regression over actions in the presence of axioms. We look at a specialized case of regression in the form of partial states, as it maintains a computationally efficient representation for repeated regression. Our algorithm offers three different approaches for calculating the approximation with varying levels of granularity, from naive to a search based method. Additionally, we look into an exhaustive method and with full regression in the Appendix. To explore the benefits that this provides, we apply these methods to an execution monitoring framework. We found that in generating approximations of logical regression, we are able to greatly reduce the number of defined basic variables required to execute a plan in the presence of axioms.

The algorithm was able to generalize plans across all domains, with some domains being able to generalize states over 70% during a plan’s execution. We look to demonstrate that the execution monitor can recover in many scenarios without replanning. Overall, we offer three different approaches to approximating regression under the presence of axioms and explore the benefits of each method.

2

Related Work

Approximating regression has practical applications when designing planners. PRP and PR2 are examples (Muise, McIlraith, and Belle 2014; Muise, McIlraith, and Beck 2024). The authors restrict their regression approximation algorithm to only produce partial states and, as such, find the minimal information a state must have to apply the next action. This is useful in the context of the algorithm they use to solve Fully Observable Non-Deterministic (FOND) problems, as it allows partial solutions to generalize to many more explicit states than those explored. This form of regression is an approximation in the presence of conditional effects and is referred to as PRIMF (PRe-IMage Filter) (Muise, McIlraith, and Belle 2014). Regression has also been used in generalized planning to create state-of-the-art solvers by taking advantage of the generalization it enables. Chen et al. introduce MOOSE, a generalized planner that uses goal regression to generate a set of lifted rules (Chen et al. 2025). These lifted rules, given a partial state, inform the planner which action to take. The goal regression they use propogates backwards allowing for multiple rules to be generated. Their planner also incorporates axioms in addition to regression. They use axioms to encode the learned rules in order to help reduce the search space to allow for optimal planning. Their new planner was able to significantly improve upon state-of-the-art planners in many paradigms: satisficing, optimal, and numeric. Regression can be used to enable execution monitoring as seen in both Fritz and McIlraith (2007) and Muise, McIlraith, and Beck (2011). The former focuses on producing robust plans that are capable of handling uncertainty. Sensors, motors, and observations can all be imperfect, causing the perception of the state to differ. They introduce an execution monitoring system that aims to avoid needless replanning. Using regression, they can determine whether or not a plan can still achieve the goal, and that can inform the decision on whether further action is needed. Muise, McIlraith, and Beck (2011) focus on exploiting partial order plans (POPs) in their execution monitoring framework, also in imperfect and variable worlds. By approximating the regression of the POP, one can produce a policy that allows an execution monitoring framework to exploit this information and improve the robustness of plan execution. For work regarding axioms, some research has been done to make axioms more applicable in planning. Speck et al. (2019) incorporate axioms natively into symbolic search algorithms. They analyze three methods for encoding axioms: Action-based, Variable-based, and Symbolic Compilation. Axioms have also been used in domain construction to great success. Baier and McIlraith (2006) use axioms to help translate temporally extended goals into classical planning.

In a more granular sense, they use axioms to help represent parameterized nondeterministic finite automata. Their implementation was more concise, expressive, and solved faster than other methods. Giacomo, Favorito, and Fuggitti (2022) use axioms to help reduce Pure-Past Linear Temporal Logic goals into classical and FOND planning. They find that axioms provide an elegant solution to their model. Lastly, Ivankovic and Haslum (2015) demonstrate how axioms can help improve the expressivity of a problem and allow more concise definitions. They demonstrate this on multiple domains and conclude that the resultant domains are more natural and more efficiently searchable.

3

Preliminaries

Definition 3.1 (States). A state s is a function that maps all variables in a set to a defined value, and a partial state p is a partial function that maps some variables in set to a value. An assignment is a tuple (v, d) where v is the variable and d is the value the variable has. Any variables without an explicit assignment in a partial state are assumed to have the value ⊥, representing that it is undefined. As partial states do not exclude the possibility of a complete assignment, all states are also partial states. S is the set of all possible complete states, and P is the set of all possible partial states. We use the notation v ∈ s to be shorthand for v ∈ {v ′ ∈ V |s(v) ̸= ⊥}. We focus on an extension of fully-observable deterministic (FOD) planning problems to handle axioms. Our definition follows the work by Speck et al (Speck et al. 2019) and Helmert (Helmert 2006), extended where necessary. Definition 3.2 (FOD with Axioms). A fully observable deterministic planning problem with axioms is defined as Π = ⟨V, A, O, I, G⟩: V is a finite set of state variables. This set can be partitioned into two distinct sets Vb and Vd , where Vb contains only basic variables (variables affected by operators directly) and Vd contains only derived variables (variables whose values are determined by axioms). Each variable v ∈ Vb has a corresponding finite domain Dv . Following this, each variable d ∈ Vd has a corresponding domain {0, 1}. Derived variables can only take a value of true or false. A state is said to be extended if ∀v inVd , s(v) ̸= ⊥. A complete state is one in which all variables in Vb are defined. A is the set of axioms in the problem. Each axiom a ∈ A takes the form of the tuple ⟨conda , d⟩. conda is a partial state that represents the conditions that must hold for an axiom to be applicable over a given state. This is also known as the body of the axiom. d is the affected derived variable. This is also known as the head of the axiom and is the derived variable that is changed by the application of an axiom. A is typically stratified to allow for well-understood semantics (Thiébaux, Hoffmann, and Nebel 2005). This stratification produces an ordering A1 , A2 , ..., Ak and is based on the stratification of the derived variables. For each derived variable d, we can partition them into sets D1 , D2 , ..., Dk such that the following two rules hold. (1) If there exists an axiom a whose head is di and whose body contains the assignment dj = 1, where dj ∈ Vd , then

di ∈ Di , dj ∈ Dj and j ≤ i. (2) If there exists an axiom a whose head is di and whose body contains the assignment dj = 0, where dj ∈ Vd , then di ∈ Di , dj ∈ Dj and j < i. Following this, axioms are stratified such that an axiom is in Ai if the head of an axiom, d, is in Di . O is the set of operators in the problem. Each operator o takes the form of a tuple ⟨preo , effo ⟩. preo is a partial state that represents the set of preconditions, while effo is a set of tuples, or assignments, of the form ⟨v, d⟩ where v is a variable in Vb and d is a value in the domain of Dv . I is the initial state of the problem. This state is an extended state. G is a partial state that represents the goal of the planning problem

produces an extended state that entails the goal condition G. That is, the plan π, applied in the manner P rog(s0 , a1 ) = s1 , P rog(s1 , a2 ) = s2 , ..., produces states S∗ = [s1 , s2 , s3 , ..., sn ], where sn |= G. With the core definitions in hand, we now restate logical regression using our notation (this follows the common definition with respect to Reiter (2001)). Definition 3.6 (Logical Regression). The general regression of a formula ϕ over an action o is an arbitrary logical formula that defines what must hold prior to o, such that ϕ holds after executing o. Using P rog(p, o), letting ϕ be an arbitrary formula over Vb , the general regression Regr(ϕ, o) is defined such that:

Definition 3.3 (Logical Entailment). Given two logical formulae A and B, logical entailment (denoted by |=) states that if A |= B then for any model interpretation of A and B there is no case in which B is false and A is true. In other words, if A is satisfied, then B is also satisfied. Any partial state can be treated as a logical formula representing a conjunction of the variable assignments. Given two partial states p1 and p2, if p1 entails p2 then any variable with an assignment in p2 must have the same assignment in p1. p1 |= p2 iff ∀v ∈ V, (p2 (v) ̸= ⊥) → (p1 (v) = p2 (v)).

∀p ∈ P, P rog(p, o) |= ϕ iff p |= Regr(ϕ, o). We define logical regression over Vb and not V without loss of generality as any formula that contains derived variables can be compiled into one that only uses basic variables.

Definition 3.4 (Applicability). An operator o is applicable in partial state p if p |= preo . Applying an operator to a partial state produces a new partial state p′ . This partial state is constructed such that for all variables v ∈ V , if an assignment ⟨v, d⟩ exists in effo then p′ (v) = d else p′ (v) = p(v). Let the application of an operator o be denoted as o(s) Similarly, a single axiom ⟨conda , d⟩ is applicable in a partial state p if p |= conda . Applying an axiom to a partial state also produces a new partial state p′ . This new partial state has the assignments p′ (v) = 1 for d ∈ ⟨conda , d⟩, and p′ (v) = p(v) otherwise. Axioms are seldom evaluated in isolation. Instead, the entire set of axioms is evaluated. This is done by first assigning all derived variables the value false. Starting in the first stratum, all applicable axioms are applied to the partial state repeatedly until a fixed point is reached. Upon this happening, the next stratum of axioms are iteratively applied. This continues until no application of an axiom will change the state. Axioms follow negation-as-failure semantics, meaning that if the partial state does not entail the body of an axiom, then the derived variable must be false as a consequence. There are many ways to handle the calculation of axioms, with Speck et al. (Speck et al. 2019) covering various interpretations. Let A(s) denote the evaluation of axioms on a partial state producing an extended partial state p. Axioms are ecaluated in respect to a given partial state after each time an operator is applied.

4

Approximating Regression with Axioms

Approximate regression is a weakened version of regression. It provides a sufficient condition, but does not guarantee that it contains the necessary conditions. Our model of regression approximation follows a similar strategy to Muise, McIlraith, and Belle (2014). They use Pre-Image Filtering (PRIMF), which restricts regression to produce a partial state, such that when an action is applied, it satisfies ϕ. PRIMF works with problems with conditional effects. This is done by calculating a set of variables called Support, which is the union of the preconditions and variables which influence the conditions an action uses in its conditional effects. We similarly treat Support as the preconditions and variables that may influence the evaluation of axioms. To maintain the partial state representation of regressed conditions, we also rely on having a complete state available for the computation. This formula takes a state s and an action o. It also takes an extra partial state, p, such that the action o when applied to s takes you to a third state which entails p. In this formula, s would be called a context state. While PRIMF primarily uses this context state to understand which conditional effects are used, we use it to ensure that derived variables are handled correctly. Definition 4.1 (Approximate Regression). The approximate regression of an action is an arbitrary formula that defines the sufficient conditions of what must hold prior to an action, such that a condition is satisfied after executing said action. Using P rog(p, o), letting ϕ be an arbitrary formula over Vb , the approximate regression Regr′ (ϕ, o) is defined such that: ∀p ∈ P, if p |= Regr′ (ϕ, o) then P rog(p, o) |= ϕ

Definition 3.5 (Progression). The progression of a partial state with an operator o is the extended partial state produced after applying an operator, and then evaluating the axioms on the resulting partial state. P rog(p, o) = A(o(p)).

We will now introduce our representation of Support. Definition 4.2 (Support). Given a state s and an operator o that is applicable in s, Support(s, o) is a partial state that only contains assignments to basic variables such that s |= Support(s, o) and adheres to the following property:

A plan π = [o1 , o2 , ..., on ] is a sequence of operators which, when applied sequentially to an initial state,

∀d ∈ Vd ∩ preo , A(Support(s, o))(d) = preo (d)

This definition states that Support(s, o), when axioms are applied to it, contains all necessary assignments to allow an operator to be applicable. One interpretation of this is that Support(s, o) is a set of basic variables that are sufficient to ensure that the derived variables needed to apply an operator hold in s. Support(s, o) is a non-unique set of basic variables. There are many different partial states that satisfy the above condition. In the following sections, we will explore how to find different instantiations of Support(s, o) and evaluate them. This leads us to the following definition of our version of approximate regression, which we will call Axiom Aware Approximate Regression: Definition 4.3. (Axiom Aware Approximate Regression (AAAR)) Given a complete state s1 , a partial state p1 , and an action o ∈ O such that P rog(s1 , o) produces s2 |= p1 , we can produce a partial state AAAR(p1 , o, s1 ), which approximates regression, as follows: AAAR(p1 , o, s1 ) =   s1 (v)     Support(s1 , o)(v) ⊥    ⊥    p1 (v)

if preo (v) ̸= ⊥ and v ∈ / Vd else if Support(s1 , o)(v) ̸= ⊥ else if effo (v) ̸= ⊥ else if v ∈ Vd otherwise

In this definition, s1 is called the context. This context state is a known state in which operator o is applicable. In our partial state AAAR(p1 , o, s1 ), we want to use the context to determine which basic variables and their corresponding values are required to ensure the precondition is satisfied. Support(s1 , o) is used to determine which variables and values are required to ensure that the derived variables required are still derived appropriately. Lines 1 and 2 could be combined, but are separated out for clarity. Line 3 undefines all variables whose values are assigned by the application of an action. Line 4 undefines all derived variables. Lastly, for any variables not mentioned before, their values are given by p1 . In this case, p1 acts as the formula we wish to have satisfied after calculation. The main objective of this regression formula is to produce a partial state that is sufficient to entail the formula used in the full unapproximated regression. In our use case, this formula represents the values a state must have for a plan to be executable and to achieve the goal if this action were taken. We can guarantee this if we use a plan π to inform our choices of s1 and p1 . If we let p1 = G, with o being the last action of π, and s1 being the final state in produced by the execution of the plan, we can approximate regression where any state that entails AAAR(p1 , o, s1 ) will be sufficient to achieve the goal. This same argument works inductively for every preceding action in π, using the previous AAAR(p1 , o, s1 ) as p1 and the previous state produced by executing the plan as the context, repeated until we reach the initial state. This sequence of partial states is called P∗ This also means that the context should entail the approximated regression and the following propositions hold.

s1 |= AAAR(p1 , o, s1 )

(1)

AAAR(p1 , o, s1 ) |= Regr(p1 , o)

(2)

Lastly, we want to be able to talk about how different instantiations of Support(s, o) and different regressed partial states compare. To do this, we introduce generality. Definition 4.4 (Generality). Let undef (p) be a function that returns a set of variables in a partial state which are equal to ⊥, that is, all undefined variables. A partial state p2 is more general than another partial state p1 if and only if the following constraints hold: p1 |= p2 |undef (p1 )| < |undef (p2 )|.

(3) (4)

Likewise, a most general partial state p∗ is defined as: ∀px ∈ P s.t. px |= p∗ , |undef (px )| ≤ |undef (p∗ )|

(5)

Conditions (3)-(4) state that for a partial state to be more general than another partial state, it must be (3) entailed by the original state and (4) have more undefined variables in comparison to the other partial state. The most general partial state is not necessarily unique, leading to different states that satisfy the constraints. Two last considerations must be taken. The goal state may contain derived variables, and if it does, it cannot be used as the partial state in our regression formula. Therefore, we need to find a way to convert the goal into a usable partial state with only basic variables. To do this, we can define a special goal-achieving action. The action has the preconditions that we are in a goal state and the effect that the goal is achieved. We regress the goal state over this goal-achieving action to produce a state that is useful for the rest of the regression calculations. Secondly, some instantiation methods make additional assumptions. One of our methods does not work with stratified axioms due to the requirement of needing to know if a derived variable is false. This restriction is a soft restriction, as it is possible to convert the problem into one without stratification (Röger and Grundke 2024), but it is mentioned nonetheless.

4.1

Naive Method

The first version of Support(s, o) is a naive method: Support(s, o)(v) = s(v) ∀v ∈ Vb . This method ensures the same derived variables will be assigned through the application of axioms. This method produces the least general regressed states and likely contains redundant or irrelevant information, making it an ideal baseline.

4.2

Relevant Variables Method

The second method is to only have assignments in Support(s, o) for variables deemed to be relevant. These are variables which are directly (or indirectly) used in the calculation of relevant derived variables. This may be calculated recursively, as seen in Algorithm 1, which returns a set of variables whose assignments must be defined in Support(s, o). We first find the set of variables that are

Algorithm 1: Find Relevant Variables: find Input: Axioms axiomSet, Relevant Derived Variables DV (The initial DV will be given by the preconditions of action o) Output: Relevant Basic Variables RV 1: RV = ∅ 2: for ⟨conda , d⟩ in A such that d ∈ DV do 3: for v ∈ V such that conda (v) ̸= ⊥ do 4: if v ∈ Vd then 5: RV ← RV ∪ find (A, {v}) 6: else 7: RV ← RV ∪ {v} 8: end if 9: end for 10: end for 11: return RV

referenced by the required axioms, axioms which are mentioned in the preconditions of the action we wish to approximate regression with. Basic variables in the precondition are collected in a set, while derived variables have their referenced variables in their respective axioms calculated. This is repeated until only basic variables are returned. The end result is a set of all basic variables which influence the derivation of the required axioms. We can use this set to assign these variables in Support(s, o) from the context. This algorithm is likely to generate a more general partial state than the naive instantiation, but not the most general.

4.3

Post Processing Method

We can find alternative approximate regressions by improving the Support(s, o) found with the relevant variables method using a technique we refer to as post-processing. Afterwards, we perform a local search algorithm to find more general partial states. We perform this search by choosing variables systematically to undefine in the our approximated partial state. Algorithm 2 details this process. This algorithm uses an additional parameter (heuristic). This heuristic informs the order in which we select variables. We explored different heuristics for ordering, some arbitrary and others based on the domain size. While it can make a significant difference when using constructed examples, in practice this decision did not produce different results. Therefore, we use the order given by the planner for all subsequent results, called the “in-order” heuristic. This instantiation has additional restrictions that the previous methods do not. In order to employ this method, we must restrict the problem to not include preconditions of actions, or conditions of axioms which contain negated derived variables. This is to say, the stratification of axioms must only contain one stratum. This method implicitly selects specific axioms which must fire in order for the formula to be satisfied. To prove that a derived variable is false we have to be able to prove that every axiom which could theoretically make it true does not have the conditions satisfied. This is due to the closed world philosophy (Thiébaux, Hoffmann,

Algorithm 2: Post Process Support Input: Axioms A, Heuristic h, operator o, context s, partial state p Output: Support: Support(s, o) 1: 2: Support(s, o) = f ind(Axioms, preo ∩ Vd ) 3: r = AAAR(p, o, s) 4: Sort variables in V with heuristic h 5: for v ∈ V if v ∈ Support(s, o), r(v) ̸= ⊥ do 6: temp = r(v) 7: r(v) = ⊥ 8: if P rog(r, o) |= p then 9: Support(s, o)(v) = ⊥ 10: else 11: r(v) = temp 12: end if 13: end for 14: Return Support(s, o)

and Nebel 2005). Therefore, by only checking a specific subset of axioms through a subset of basic variables in the context, we are not able to conclusively say that a derived variable is false. The previous two methods are able to handle negated derived variables as every axiom is considered. The next step would be to exhaustively search for the best approximated regressed state and to compare against full regression. In practice this was too computationally complex, but details can be found in the Appendix.

5

Execution Monitoring

Execution monitoring is one beneficiary of the ability to produce regressed partial states in the presence of axioms. It is an established testbed with many applications: enabling plan executions to recover under uncertainty, testing the robustness of our partial states, and enabling replanning. It is also a strong tool when attempting to handle generalized planning (Srivastava, Immerman, and Zilberstein 2011), having been explored in the area of robotics (Fikes, Hart, and Nilsson 1972). In this paper, we use execution monitoring to compare different regression approximation techniques by quantifying how many states they can readily handle. The framework is generally laid out as follows. First, we begin simulating a computed plan from an initial state. Plans are generated prior to execution. With these plans, we can produce a sequence of regressed states, starting from the goal and iteratively moving through the plan in reverse order: P∗ . At some point in the simulation, we change the value of the state, putting the simulator in a new, unexpected state. Using our regressed partial states, we can check if there is any known partial state that is entailed by our current state. If there is, we know we can recover by continuing the execution of the plan at that spot. If not, we know our partial states do not capture this state, and replanning is necessary. We do not perform any replanning step, but rather demonstrate when it is not necessary. Our method is meant to complement existing execution monitoring frameworks,

rather than replace them entirely. Three core decisions were made when designing our execution monitoring methodology that ultimately determine the probability of states changing. The first is to choose when a change occurs. This is done by pre-selecting a random step in the plan in which our execution will deviate. The second choice is to select the basic variable to change. There are two ways in which we have chosen to select this variable. We use a uniform random method, where every basic variable has an equal chance of being selected. We also use a weighted method that ranks and weighs each choice based on the size of the domain. This method selects variables that can take on more values with high likelihood. The final decision is that we randomly select a new value for our variable to take. Under our approach, the new value must be different from the previous value. If this were not the case, the recovery would be trivial. Execution monitoring allows us to calculate various metrics to determine how resilient our execution is. One metric we can obtain is the suffix length. Suffix length is the index of the action in a plan (indexed in reverse) in which, if the plan was executed from that point, would result in a state that achieves the goal. Given a partial state p, suf f ix length(p) = argmini [p |= AAAR(S∗ [len(S∗ ) − i], π[len(S∗ ) − i], P∗ [i]). If no action is entailed then suffix length does not exist. Replanning is not necessary if the changed state entails a partial state obtained through AAAR. Another metric we can calculate is the success rate. This measures how many trials result in the changed state entailing a regressed partial state. A high success rate corresponds to a plan that is often able to recover without replanning. Finally, there is the undefined rate. This is the number of undefined variables in all partial states in P∗ , normalized, and is indicative of how much information is generalized, which allows more states to entail our approximate regression.

6

Evaluation

We hope to answer the following research questions: 1. How robust does our approximate regression formula make our plans, or in other words, how often are we able to recover without replanning? 2. How general are our plans? How much redundant information is contained in each state/ in knowing which variables may be undefined? We hope to answer the first question by calculating the success rate and the suffix length, which is the number of steps to achieve the goal state. High success rates imply robust plans, and suffix length informs the amount of work required to recover. The latter two questions we can analyze by looking at how many basic variables need defined assignments to achieve the goal and how many are set to ⊥. All experiments were run on 12th Gen Intel(R) Core(TM) i7-12700H with 32 GB of RAM. The plans were generated in advance or collected from the IPC 2004 results (Edelkamp and Hoffmann 2005), in the cases of Promela domains.

6.1

Domains

Many domains were found via a public repository1 , a popular repository for PDDL domains with axioms (dosydon 2017). We also altered two domains from IPC 23 (Taitler et al. 2024). Domains were chosen based on availability and the number of problem instances. Some problem sets in (dosydon 2017) were omitted due to having only two instances or not having axioms. The domains that come from IPC 4 include PromelaPhilosophers, Promela-Optical-Telegraphs, Miconic, PSR, Blocksworld, and Sokoban. Each uses axioms in a different way. Philosophers and Optical Telegraphs use axioms to define deadlocks. Miconic and Sokoban axioms are both used to derive reachability. The former refers to a floor being reachable, and the latter refers to a grid position. Blocksworld uses axioms to define properties such as above and holding. Lastly, PSR uses axioms to represent the transitive flow of electricity. In addition to these domains, we modify the following domains to include axioms. All of these domains come from IPC 23 (Taitler et al. 2024). (Labrynth) The goal of this domain is to make a plan to guide an agent through a dynamic maze. The maze can shift along each direction in a torus fashion, changing the paths through the maze. We use axioms to introduce reachability into this domain in a similar way to the Sokoban domain. (Quantum Circuit Layout Synthesis) The goal of this problem is to first map logical qubits onto physical qubits. We modify this domain such that some variables are no longer given by the actions, but rather intermediate variables are given, and the initial variable must be derived. These axioms are simpler than those in other domains, but are still representative of how axioms may be used. We gathered plans from each domain using the FastDownward planner (Helmert 2006). These plans are not necessarily optimal plans, but rather just a satisficing plan. Due to this, we just ran the stock version of FastDownward with no additional configuration; time was irrelevant. Not every instance of each domain has a corresponding plan due to the computation time it takes to produce them. We ran an execution monitor for 10,000 iterations for every problem instance across four different configurations. The configurations are partitioned via two decision points. The first is what method should be used to instantiate Support. V1 (Version 1) and V4 both use the naive method, specified in Section 4.1, to achieve the initial Support with respect to the goal-achieving action. V2 and V3 use the postprocessing method in Section 4.3 and the “in-order” heuristic. The relevant variables method of instantiation was omitted as post-processing was similar, leading to a marginal difference. The second choice is whether to continue to postprocess the Support during subsequent regression calculations. V1 and V2 choose to omit this step, while V3 and V4 do not. These configurations allow us to explore two different axes to apply our approximated regression formula. Domains which had stratified axioms present are unable to use post-processing and therefore have an N/A. 1

https://github.com/dosydon/axiom benchmarks

Domain Blocksworld Labrynth Miconic Optical Philosophers PSR-large Quantum Sokoban

Probs 9 24 50 25 48 43 3 6

V1 12.8 2.3 31.1 6.8 12.8 0.5 12.1 0

V2 & V3 N/A 31.4 49.1 73.2 35.4 24.9 24.6 N/A

V4 N/A 31.4 49.1 48.1 27.1 24.9 24.6 N/A

Max 12.8 99.9 73.3 80 50 5.7 39.7 0

Table 1: Average percentage of undefined variables (Undefined rate) across various configurations over entire plans. N/A is for domains with stratified axioms. Best method is bolded.

Figure 2: Violin plot of undefined variables

Figure 1: Area graph showing how many undefined variables are in each instance

6.2

Undefined Rate

Table 1 contains information on how many variables are undefined across an entire plan. For each configuration, a plan is used to generate a series of states. Given this series, we calculate the percentage of variables at each step which could have been undefined and average them. Percentages are used as each instance has a different number of variables. 50 would mean, on average, half of all basic variables are set to ⊥ across the entire plan execution. The max column shows the greatest reduction given a single step. In every case, V2 and V3 are the same. Consequently, in all domains tested, it is the same to post-process only the goal as opposed to all of the steps. V4 is the third most efficient method. The naive method is, as expected, the least effective method. Some of the examples have a low undefined rate. This can be explained by analyzing the number of basic variables in the domain. With domains such as Sokoban, the majority of the variables are derived. For example, the first Sokoban instance has three basic variables and 70 derived variables. This makes it difficult to undefine variables since only zero to three basic variables can be undefined. Conversely, the 6 6 instance of Labrynth, with 1375 basic variables and 36 derived variables leads to larger improvements.

stances are able to undefine half of all basic variables. This graph looks solely at regressing the goal state with the postprocessing. Figure 2 shows that the variables are undefined for each domain one step from the goal by domain for every instance in a domain. Notably, most domains are consistent with how much redundant information exists, with some being exactly the same across all instances: e.g. philosophers always have 50% of basics undefined. To further explore how these domains change when regression is applied, we will focus on the Philosophers problems in particular. Figure 3 shows the first instance of promela-philosophers applied over four configurations.

6.3

6.4

Experimental Configuration

Figure 1 shows how much information is required for each domain, one step from the goal. This gives a sense of what is required for a partial state to be able to achieve the goal. Over all domains tested, approximately half of all in-

Figure 3: Regressing philosophers problem 1

Execution Monitoring and Recovery

We can now introduce our execution monitoring and see how our regression approximation can help with execution. The first metric we will analyze is whether the execution could recover without replanning. Looking at one domain,

Instance Blocksworld 9 Labrynth 6 6 Miconic 30 4 Phil 48 PSR large 26 Opt 9 Quantum 3 Sokoban 7

Average Suffix 18 5.6 25.5 231.6 15.1 71.3 16.4 15

STD 9.3 2.2 17 136.8 9.4 40.6 9.9 0

Plan Length 30 8 60 441 31 140 36 15

Table 3: Plan suffix across various instances

7 Figure 4: The number of recoveries across all instances of Philosophers

Instance Blocksworld Labrynth Miconic Phil PSR Large Opt Quantum Sokoban

RR Small 24.54% 40.75% 67.29% 24.65% 71.60% 40.61% 30.04% 0.25%

RR Large 2.21% 0.1858% 48.33% 21.03% 18.87% 40.71% 23.21% 0.24%

All Conf Same Y Y Y N N N N N

Table 2: Plan recovery rate on the smallest and largest instances

Figure 4 shows the average recoveries for Philosophers. W corresponds to whether the variables were weighted with Y meaning yes and N meaning no, The second value corresponds to whether the naive method was used for the initial Support or the post-processing method. We tested postprocessing for subsequent regression calculations, but it had no impact. We can see that the configuration used does play a significant role in whether the monitor recovers. Weighting variables is highly domain-specific, with some domains, such as Optical, performing 25% worse on average when using weighted variables. We can look at the recovery rate of all domains, both the largest and smallest instances, in Table 3. This table reports the configuration where post-processing is used at all steps and variables are weighted. For domains with stratified axioms, the relevant variables method was used. The success rate is domain-dependent, but many domains avoided replanning. The second metric we can analyze is suffix length. Table 2 gives numerical data on suffix lengths across the largest instance of each domain. We found that across the board, the configuration has a marginal impact on which step of a plan the execution monitor is able to recover. STD is the standard deviation of when the execution monitor is able to recover. From this, we can see that the execution monitor is able to restart the execution halfway through the plan. While this may seem intuitive, it is possible to construct scenarios where any average suffix is possible.

Conclusion

Axioms are a powerful tool that offer many benefits and can simplify complex phenomena (Thiébaux, Hoffmann, and Nebel 2005). Despite their utility, many extensions and applications of planning do not take advantage of them. We set out to improve this by introducing an approximation for regression over actions with axioms in the domain. We have implemented an approximate regression algorithm for fully observable deterministic domains with axioms. Three different versions of this method were created: a naive method which keeps all basic variables to ensure that axiom calculation is performed exactly the same as the state used to approximate regression, a relevant variables method which only keeps the states required for specific axioms, and a post processing method which chooses a specific set of axioms which can achieve the desired result. Additionally, the appendix contains other potential methods. Using our newly regressed partial states, we introduce an execution monitoring framework. This enables robust behaviour during plan execution by often avoiding replanning if something goes awry. We also use it to test statistical properties of our regression methodology. Across eight domains, we have identified many key insights. The first is that in current benchmarks, only applying post-processing to the goal state produces an approximate regression over the plan that is just as good as applying post-processing at every step. Problems may be constructed where this is not the case, which raises the question of whether this is a property of real-world domains or if existing benchmarks are simply too limited in scope. Roughly half of the time, across all domains, the execution monitoring system avoided replanning. This allows applications of planning to save computing time. Additionally, our approach was able to greatly generalize plans across all domains, with differences in the number of basic variables between domains having a great impact. Moving forward, we hope to expand the algorithm to handle both conditional and non-deterministic effects, expand the datasets used, and explore why heuristics did not provide a measurable improvement in practical domains. Another area of future work would be to expand up the benchmarks that contain axioms. To our knowledge there are limited examples. To fully explore the capabilities of such an algorithm, domains will need to be created or modified to include these richer specifications.

Acknowledgments We acknowledge the support of Scotiabank, in conjunction with the Smith School of Business Scotiabank Centre for Analytics & AI, and Mitacs.

References Baier, J. A.; and McIlraith, S. A. 2006. Planning with firstorder temporally extended goals using heuristic search. In AAAI, 788–795. Chen, D. Z.; Hofmann, T.; Klassen, T. Q.; and McIlraith, S. A. 2025. Satisficing and Optimal Generalised Planning via Goal Regression (Extended Version). dosydon. 2017. GitHub - dosydon/axiom benchmarks: PDDL planning problems with derievd predicates and axioms. Edelkamp, S.; and Hoffmann, J. 2005. The Deterministic Part of IPC-4: An Overview. Journal of Artificial Intelligence Research, 24: 519–579. ArXiv:1109.5663 [cs]. Fikes, R. E.; Hart, P. E.; and Nilsson, N. J. 1972. Learning and executing generalized robot plans. Artificial intelligence, 3: 251–288. Fritz, C.; and McIlraith, S. A. 2007. Monitoring Plan Optimality During Execution. In ICAPS, 144–151. Giacomo, G. D.; Favorito, M.; and Fuggitti, F. 2022. Planning for Temporally Extended Goals in Pure-Past Linear Temporal Logic: A Polynomial Reduction to Standard Planning. Artificial Intelligence, (arXiv:2204.09960). ArXiv:2204.09960 [cs]. Helmert, M. 2006. The Fast Downward Planning System. Journal of Artificial Intelligence Research, 26: 191–246. ArXiv:1109.6051 [cs]. Ivankovic, F.; and Haslum, P. 2015. Optimal Planning with Axioms. In International Joint Conference on Artificial Intelligence. Muise, C.; McIlraith, S.; and Belle, V. 2014. NonDeterministic Planning With Conditional Effects. Proceedings of the International Conference on Automated Planning and Scheduling, 24: 370–374. Muise, C.; McIlraith, S. A.; and Beck, J. C. 2011. Monitoring the execution of partial-order plans via regression. In Twenty-Second International Joint Conference on Artificial Intelligence. Citeseer. Muise, C.; McIlraith, S. A.; and Beck, J. C. 2024. PRP Rebooted: Advancing the State of the Art in FOND Planning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, 20212–20221. Reiter, R. 2001. Knowledge in action: logical foundations for specifying and implementing dynamical systems. MIT press. Röger, G.; and Grundke, C. 2024. Negated occurrences of predicates in PDDL axiom bodies. In Proceedings of the KI2024 Workshop on Planning, Scheduling, Design and Configuration (PuK 2024).

Speck, D.; Geißer, F.; Mattmüller, R.; and Torralba, Á. 2019. Symbolic Planning with Axioms. Proceedings of the International Conference on Automated Planning and Scheduling, 29: 464–472. Srivastava, S.; Immerman, N.; and Zilberstein, S. 2011. A new representation and associated algorithms for generalized planning. Artificial Intelligence, 175(2): 615–647. Taitler, A.; Alford, R.; Espasa, J.; Behnke, G.; Fišer, D.; Gimelfarb, M.; Pommerening, F.; Sanner, S.; Scala, E.; Schreiber, D.; Segovia-Aguas, J.; and Seipp, J. 2024. The 2023 International Planning Competition. AI Magazine, 45(2): 280–296. Thiébaux, S.; Hoffmann, J.; and Nebel, B. 2005. In defense of PDDL axioms. Artificial Intelligence, 168(1–2): 38–69.

Appendix 7.1

Full Regression and Exhaustive Search

Given Vb , one can calculate the Cartesian product of all assignments that generate a partial state which satisfies the definition of Regr′ (ϕ, o), with ⊥ being a valid assignment. This Cartesian product represents a version of an unapproximated regression of the system, or the full arbitrary formula ϕ; the version that we attempt to use when computing full regression. This is done by translating the cartesian product into a disjunction of states, each of which is a conjunction of assignments. We represent full regression in this manner because we need the formula to take the form of partial states. Every possible state which in which an operator is applicable must entail at least one of these partial states. This form of regression contains redundant information but is an upper bound. Calculating the Cartesian product of all assignments is an expensive operation and is only feasible for very small problems in terms of Vb . We were only able to use it in the smallest problems within reasonable time bounds. Similar to the naive method, this serves as an informative baseline. Despite this it does serve as an excellent comparison tool to evaluate our selected approximated regression. From this cartesian product we are able to extract individual partial states to be used as approximated regressed states. Each one in the cartesian product is a valid approximate regression. With this said we can introduce our new method, the exhaustive method. The exhaustive method looks for the partial state that is the most general and still satisfies the condition that given our plan we are able to execute it and achieve the goal. This method takes into consideration the context and ensures that the propositions (1) and (2) in section 4 are satisfied. As every possible initialization is in the cartesian product this is guaranteed to be the best solution.