# finding_minimal_plan_reductions_using_classical_planning__4ff5a171.pdf Finding Minimal Plan Reductions Using Classical Planning MAURICIO SALERNO, Universidad Carlos III de Madrid, España RAQUEL FUENTETAJA, Universidad Carlos III de Madrid, España JENDRIK SEIPP, Linköping University, Sweden While classical planning research has made tremendous progress in the last decades, many complex tasks can still only be solved suboptimally. The satisficing plans found for these tasks often contain actions that can be removed while maintaining plan validity. Removing such redundant actions is desirable since it can decrease the plan cost and simplify the plan. Reducing a plan to a minimum-cost plan without redundant actions is NP-complete and previous work addressed this problem with a compilation to weighted Max SAT. In this work, we propose several simple and natural formulations to encode this problem as a classical planning task, and prove that solving the resulting tasks optimally guarantees finding minimal plan reductions. We analyze the relation of the classical planning formulations to the Max SAT compilation, and prove theoretical properties of the known concept of plan action landmarks. Finally, we evaluate the new approaches experimentally and show that they are competitive with the previous state of the art in minimal plan reduction. JAIR Associate Editor: Siddharth Srivastava JAIR Reference Format: Mauricio Salerno, Raquel Fuentetaja, and Jendrik Seipp. 2025. Finding Minimal Plan Reductions Using Classical Planning. Journal of Artificial Intelligence Research 84, Article 10 (October 2025), 35 pages. doi: 10.1613/jair.1.19437 1 Introduction Modern satisficing planning systems are able to solve large planning tasks efficiently (Lipovetzky and Geffner 2017; Richter and Westphal 2010). However, solutions found by these planners can be far from optimal, even producing plans with redundant actions. Intuitively, an action in a plan is redundant if it can be removed without affecting the plan s validity. In turn, a subsequence of actions in a plan is redundant if it can be removed without affecting validity, and plans without redundant subsequences are called perfectly justified (Fink and Yang 1992; Nebel et al. 1997). It is easy to see that justified plans are preferable to non-justified plans. First, cheaper plans are preferable, and removing redundant actions can lead to cost reductions. Second, in a plan reuse setting (Fink and Yang 1992), where a plan found for a task is reused to solve a subtask, removing redundant actions which are only related to goals in the original task that are not considered in the subtask can lead to a more efficient plan. Third, Olz and Bercher 2019 argue that removing redundant actions also improves plan explanations. Fourth, finding justified plans is particularly important in settings such as top-𝑘planning (Katz and Sohrabi 2022; Katz, Sohrabi, and Udrea 2020; Katz, Sohrabi, Udrea, and Winterer 2018; Speck et al. 2020), especially when diversity is required (Katz, Sohrabi, and Udrea 2022; Srivastava et al. 2007). Alternative plans with redundant actions are bound to have little practical value since they are the result of adding loops or other types of redundant actions to actually Authors Contact Information: Mauricio Salerno, orcid: 0000-0002-7664-5847, msalerno@pa.uc3m.es, Universidad Carlos III de Madrid, Leganés, Madrid, España; Raquel Fuentetaja, orcid: 0000-0002-3856-2629, rfuentet@inf.uc3m.es, Universidad Carlos III de Madrid, Leganés, Madrid, España; Jendrik Seipp, orcid: 0000-0002-2498-8020, jendrik.seipp@liu.se, Linköping University, Linköping, Sweden. This work is licensed under a Creative Commons Attribution International 4.0 License. 2025 Copyright held by the owner/author(s). doi: 10.1613/jair.1.19437 Journal of Artificial Intelligence Research, Vol. 84, Article 10. Publication date: October 2025. 10:2 Salerno, Fuentetaja & Seipp useful plans. Paths that are bound to contain redundant actions can also be pruned dynamically during the search (Karpas and Domshlak 2011). The existence of redundant actions in plans generated by modern planners is not limited to top-k settings, and it has been documented widely (Balyo, Chrpa, et al. 2014; Chrpa et al. 2012a,b; Med and Chrpa 2022; Nakhost and Müller 2010). For example, in the agile setting, where the goal is to find a plan as fast as possible, redundant actions in plans are quite common. We will analyze this in detail in Section 7.1, but highlight some extreme cases here already: 50% of the actions in plans found by the Freelunch Madagascar planner (Balyo and Gocht 2018) for the Data Network domain are redundant. Similarly, 55% of actions are redundant in plans found by YASHP3 (Vidal 2014) for the Hiking domain. These examples show that in some settings it is crucial to identify redundant actions in plans. However, checking whether a plan is perfectly justified is NP-complete (Fink and Yang 1992; Nakhost and Müller 2010), so it is important to develop efficient methods. In our work, we filter redundant actions from plans in a post-planning step while preserving the order of the remaining actions, in the same spirit as previous work (Balyo, Chrpa, et al. 2014; Chrpa et al. 2012a,b; Fink and Yang 1992; Med and Chrpa 2022; Nakhost and Müller 2010). Specifically, we focus on obtaining perfectly justified plans of minimum cost. These plans are referred to as minimal reductions of the original plan (Nakhost and Müller 2010). To our knowledge, there is only one previous approach for finding minimal plan reductions: Balyo, Chrpa, et al. 2014 cast the problem as a weighted partial Max SAT formula. While eliminating redundant actions reduces the plan length and often its cost, our main motivation is to find justified plans. In contrast, optimizing plan length or cost is central for post-planning plan optimization, which usually involves modifying the plan actions and/or the action order (Muise et al. 2016; Olz and Bercher 2019; Say et al. 2016; Siddiqui and Haslum 2015; Waters et al. 2020). Bercher et al. (2024) present a comprehensive survey on plan optimization, including some methods focused in removing redundant actions from plans. Given a plan for a planning task, we propose several automatic reformulations to a new planning task whose optimal solution is a minimal reduction of the original plan. Automated planning is PSPACE-complete even in its simplest form (Bylander 1994), but there are several reasons that justify its use to find minimal plan reductions: (1) the planning formulation is natural, since choosing which actions are needed to go from an initial state to a goal state is planning; (2) it is simple, in contrast to the previous weighted Max SAT approach; (3) in many cases it is also more efficient; and (4) it is portable to other planning settings where the solution is a sequence of actions, such as temporal or conformant planning (Bonet and Geffner 2000). This article extends a conference publication (Salerno et al. 2023a). In that paper, we presented the first classical planning formulation to find minimal plan reductions. Here, we make the following novel contributions: We thoroughly review existing work on eliminating redundant actions from plans. We study, both theoretically and empirically, four different alternative formulations of the minimal reduction problem as a classical planning task, including the one from the conference paper, which is explained in more detail here including an analysis of its theoretical properties. We analyze fix-point plan action landmarks theoretically (Salerno et al. 2023a). We introduce the concept of always redundant actions, characterizing actions that can never be part of a minimal reduction of a plan. We identify situations where the use of planning is preferable to the weighted Max SAT approach by Balyo, Chrpa, et al. 2014, and vice versa. We carry out a comprehensive evaluation, aimed at empirically comparing the different classical planning-based approaches among themselves and with the weighted Max SAT approach; and obtaining empirical evidence for the identified situations where a planning approach is preferable to weighted Max SAT. Journal of Artificial Intelligence Research, Vol. 84, Article 10. Publication date: October 2025. The rest of the article is organized as follows: Section 2 introduces background on classical planning and plan justifications. Section 3 summarizes related work. Section 4 presents four planning compilations and their theoretical properties. Sections 5 and 6 introduce plan action landmarks and always unnecessary actions, respectively. Finally, Section 7 contains the empirical evaluation, before Section 8 concludes the paper. 2 Background In this section we describe the planning formalism we use throughout this work, as well as the concepts of plan justification and redundant actions. We consider classical planning tasks in the SAS+formalism with action costs (Bäckström and Nebel 1995). Definition 1 (planning task). A planning task is a tuple Π = V, A, I, G , where: V is a set of finite-domain state variables 𝑣, each with a finite domain D(𝑣). Any pair 𝑣,𝑑 such that 𝑣 𝑉 and 𝑑 D(𝑣) is a fact, written as 𝑣 𝑑. For Boolean variables 𝑣, we refer to fact 𝑣 as 𝑣, and 𝑣 as 𝑣. A partial state 𝑠is a mapping of a subset of variables vars(𝑠) V to values in their respective domains, and we often treat partial states as sets of facts. The value of variable 𝑣 vars(𝑠) in partial state 𝑠is denoted as 𝑠[𝑣] D(𝑣). Partial states that assign values to all variables (vars(𝑠) = V) are called states. The set of all states in the planning task is denoted as 𝑆(Π). A is a finite set of actions. Each action 𝑎 A is a pair 𝑝𝑟𝑒(𝑎), eff (𝑎) , where pre(𝑎) and eff (𝑎) are both partial states defining the precondition and the effect of 𝑎, respectively. An action 𝑎 A is applicable in state 𝑠iff pre(𝑎) 𝑠. Applying action 𝑎in 𝑠yields the successor state 𝑠[[𝑎]], with 𝑠[[𝑎]][𝑣] = eff (𝑎)[𝑣] if 𝑣 vars(eff (𝑎)) and as 𝑠[[𝑎]][𝑣] = 𝑠[𝑣] otherwise. Each action 𝑎 A has a non-negative cost 𝑐(𝑎) R+ 0. I is the initial state. G is a partial state describing the goal condition. A solution or plan for Π is an action sequence 𝜋= 𝑎1, . . . ,𝑎𝑛 that, when applied in succession starting from the initial state, induces a state sequence S𝜋= 𝑠0, . . . ,𝑠𝑛 such that 𝑠0 = I, G 𝑠𝑛, and for each 𝑖with 1 𝑖 𝑛, 𝑎𝑖is applicable in 𝑠𝑖 1, and 𝑠𝑖= 𝑠𝑖 1[[𝑎𝑖]]. We denote the length of plan 𝜋= 𝑎1, . . . ,𝑎𝑛 as |𝜋| = 𝑛. The cost of a plan 𝜋is 𝑐(𝜋) = Í𝑛 𝑖=1 𝑐(𝑎𝑖). A plan is optimal if there is no cheaper plan. We slightly abuse notation and let 𝑎𝑖 𝜋denote that action 𝑎𝑖occurs at position 𝑖of 𝜋. Example 1. A well-known domain in automated planning is Blocksworld (Slaney and Thiébaux 2001). In this domain, a set of blocks can be either on a table or stacked on top of each other. A mechanical arm can hold one block at a time, and it can place the block it is holding on the table or stack it on top of another block. The arm can only pick up blocks that do not have another block on top of them. We will use the Blocksworld task in Figure 1 as a running example. Figure 1a shows the initial state, where four different blocks are on the table, and Figure 1b shows the goal description, where block A is on the table, while B is on top of A. Figure 2 presents a SAS+representation of the task. It is easy to see that the single optimal plan for this planning task is: 𝜋1 = pick-up-b, stack-b-a . However, an equally valid plan for this planning task is: 𝜋2 = pick-up-c, stack-c-d, pick-up-b, stack-b-a . Since 𝜋1 is a subsequence of 𝜋2 and both achieve the goals, it is trivial for a human to realize that the actions pick-up-c, stack-c-d can be removed from the plan and still reach the goals. In other words, they are not justified. The notion of action and plan justifications can be traced back to the early 1990s. Fink and Yang 1992 define three types of plan justification: backwards justification, well-justification and perfect justification. Backwards justification is the weakest of the three, and it is defined using the notion of causal links between actions in a plan (Mc Allester and Rosenblitt 1991). In essence, there is a causal link between two actions 𝑎𝑖and 𝑎𝑗, if 𝑎𝑖produces a fact 𝑓that is a precondition of 𝑎𝑗, and no action in between them overwrites that fact. The set of causal links of a plan can be extracted in polynomial time (Jiménez Celorrio et al. 2013). Journal of Artificial Intelligence Research, Vol. 84, Article 10. Publication date: October 2025. 10:4 Salerno, Fuentetaja & Seipp (a) Initial state (b) Goal description Fig. 1. Example Blocksworld planning task. Definition 2 (causal link). Given a planning task Π = V, A, I, G and a plan 𝜋= 𝑎1,𝑎2, . . . ,𝑎𝑛 for Π, there exists a causal link ℓ= 𝑎𝑖, 𝑓,𝑎𝑗 between actions 𝑎𝑖and 𝑎𝑗(1 𝑖< 𝑗 𝑛) if there is a fact 𝑓= 𝑣 𝑑 eff (𝑎𝑖) pre(𝑎𝑗), and there is no action 𝑎𝑘with 𝑖< 𝑘< 𝑗, such that 𝑣 𝑣𝑎𝑟𝑠(eff (𝑎𝑘)). An action is backward justified if it is causally related to a goal fact: there is a chain of causal links that connects the action to a goal fact. Definition 3 (backward justified action). Given a planning task Π = V, A, I, G and a plan 𝜋= 𝑎1,𝑎2, . . . ,𝑎𝑛 for Π, an action 𝑎𝑖 𝜋is backward-justified if at least one of the following conditions is true: Action 𝑎𝑖achieves a goal fact that is not achieved by any action after 𝑎𝑖. Formally, there is a fact 𝑓 eff (𝑎𝑖) G such that there is no action 𝑎𝑗 𝜋with 𝑗> 𝑖and 𝑓 eff (𝑎𝑗). There exists a causal link ℓ= 𝑎𝑖, 𝑓,𝑎𝑗 and 𝑎𝑗is backward justified. Backward justification fails to capture if an action can be removed from the plan without invalidating it, because it only considers the last achiever of a fact before an action needs it. In other words, it could be the case that an action that can be removed from the plan is backward justified. The next type of justification is well-justification, which captures if a single action can be removed from the plan without invalidating it: Definition 4 (well-justified action). Given a planning task Π = V, A, I, G and a plan 𝜋= 𝑎1,𝑎2, . . . ,𝑎𝑛 for Π, an action 𝑎𝑖 𝜋is well-justified if and only if its removal from the plan invalidates 𝜋. A plan is backward/well justified if all of its actions are backward/well justified. The action sequence resulting from removing any number of actions from a plan (including no actions) is a subsequence of the original plan. When the resulting subsequence is also a plan for the planning task, we call it a plan reduction. Definition 5 (plan reduction). Let 𝜋be a plan for a planning task Π and 𝜌be a subsequence of 𝜋. Then 𝜌is a plan reduction of 𝜋if and only if 𝜌is also a plan for Π. Throughout the article, when it is necessary to relate a specific subsequence of actions of length 𝑚with the sequence (plan) of length 𝑛, 𝑚 𝑛, from which it originates, we use the notation 𝑎𝑓(1), . . . ,𝑎𝑓(𝑚) , where 𝑓is a strictly monotonic function mapping the action indices in the subsequence to action indices in the sequence. For instance, if the plan is 𝑎1,𝑎2,𝑎3,𝑎4,𝑎5 , the subsequence containing the first and third actions is 𝑎𝑓(1),𝑎𝑓(2) with 𝑓(1) = 1 and 𝑓(2) = 3. Journal of Artificial Intelligence Research, Vol. 84, Article 10. Publication date: October 2025. Variables V = {arm, a-pos, b-pos, c-pos, d-pos, a-top, b-top, c-top, d-top} Domains D(arm) = {free, full} D(a-pos)= {arm,𝑏,𝑐,𝑑, table} D(a-top) = {clear, blocked} . . . Actions A = {pick-up-a, put-down-a, stack-a-b, unstack-a-b, . . . } pick-up-a = {a-pos 𝑡𝑎𝑏𝑙𝑒, a-top 𝑐𝑙𝑒𝑎𝑟, arm free}, {a-pos 𝑎𝑟𝑚, arm full} put-down-a= {a-pos 𝑎𝑟𝑚}, {a-pos 𝑡𝑎𝑏𝑙𝑒, arm free} stack-a-b = {a-pos 𝑎𝑟𝑚, b-top 𝑐𝑙𝑒𝑎𝑟}, {a-pos 𝑏, b-top 𝑏𝑙𝑜𝑐𝑘𝑒𝑑, arm free} unstack-a-b= {a-pos 𝑏, a-top 𝑐𝑙𝑒𝑎𝑟, arm free}, {a-pos 𝑎𝑟𝑚, b-top 𝑐𝑙𝑒𝑎𝑟, arm full} . . . Initial state I = { a-pos 𝑡𝑎𝑏𝑙𝑒, b-pos 𝑡𝑎𝑏𝑙𝑒, c-pos 𝑡𝑎𝑏𝑙𝑒, d-pos 𝑡𝑎𝑏𝑙𝑒, a-top 𝑐𝑙𝑒𝑎𝑟, b-top 𝑐𝑙𝑒𝑎𝑟, c-top 𝑐𝑙𝑒𝑎𝑟, d-top 𝑐𝑙𝑒𝑎𝑟, arm free} Goal state G = { a-pos 𝑡𝑎𝑏𝑙𝑒, b-pos 𝑎, b-top 𝑐𝑙𝑒𝑎𝑟} Fig. 2. SAS+representation of the Blocksworld task in Figure 1. For each block, there is a variable representing its position, which can be on the table, on top of another block, or being held by the mechanical arm. Another variable represents whether a block has a block on top of it. The last variable represents if the arm is holding a block or if it is free. For each block, there is one action to pick it up from the table, and one to put it down on the table. Finally, for each pair of blocks, there are actions to either stack or unstack them. A plan is well-justified if all of its actions are well-justified, which means that a plan 𝜋is well-justified if and only if there does not exist a plan reduction 𝜌such that |𝜌| = |𝜋| 1 (i.e. no action can be removed individually without invalidating the plan). Going back to our running example, the plan pick-up-b, stack-b-a, pick-up-c is not well-justified, since action pick-up-c can be removed from the plan without affecting its validity. However, the plan pick-up-c, stack-c-d, pick-up-b, stack-b-a is well-justified: removing any action creates an invalid plan (either because some actions are not applicable or because the goals are not achieved). In order to identify this type of redundant actions, we need the strongest type of justification, which is the main interest of this work: perfect justification. In contrast to backward and well-justification, perfect justification is defined over plans instead of over actions. Definition 6 (Perfect justification). A plan 𝜋for planning task Π is perfectly justified if and only if there is no plan reduction 𝜌of 𝜋such that |𝜌| < |𝜋|. This means that a plan is perfectly justified if no non-empty subset of actions can be removed from it without invalidating the plan, so the plan pick-up-c, stack-c-d, pick-up-b, stack-b-a is not perfectly justified. Journal of Artificial Intelligence Research, Vol. 84, Article 10. Publication date: October 2025. 10:6 Salerno, Fuentetaja & Seipp The task of finding a well-justified plan reduction of a given plan can be solved in polynomial time, while verifying if a plan is perfectly justified, as well as the problem of finding a perfectly justified plan reduction, are NP-complete (Fink and Yang 1992; Nakhost and Müller 2010). Finally, the task of finding the cheapest perfectly justified plan reduction of a given plan is known as the minimal reduction problem (Balyo, Chrpa, et al. 2014; Nakhost and Müller 2010). 3 Related Work on Action Elimination Over the years, several methods have been proposed to identify and remove redundant actions from plans. We group them into two coarse categories: optimal action elimination methods, and sub-optimal (greedy) action elimination methods. Optimal action elimination methods produce a minimal reduction, while greedy action elimination methods can quickly remove redundant actions, but have no guarantees that the resulting plan reduction is minimal. The main focus of this work are optimal action elimination methods. 3.1 Greedy Methods Fink and Yang 1992 present, to the best of our knowledge, the first three methods to identify and eliminate redundant actions from plans. (1) The first method, which we will call FY1, guarantees producing backward justified plans. FY1 checks, for each action in a plan, if there exists a causal link chain rooting from the action to a goal fact. Any action that is not causally linked to a goal is removed, ensuring that the resulting plan is backward justified. (2) The second method, FY2, yields well-justified plans. FY2 checks, for each action 𝑎in the plan, if the sequence resulting from removing 𝑎is still a plan. If so, 𝑎is removed. This loop is repeated until no actions can be removed from the plan, producing a well-justified plan. (3) The final method, FY3, greedily tries to remove each action from the plan. If any of the remaining actions are not applicable afterwards, they are also removed. If the resulting sequence is not a plan, FY3 restores the actions removed in this step. Otherwise, if the resulting sequence is a plan, the method continues with the same greedy process for each remaining action. This process guarantees finding well-justified plans, and it was actually rediscovered by Nakhost and Müller 2010. Chrpa et al.Chrpa et al. 2012a,b study redundant actions from the view of action dependencies. If two actions in a plan are inverse (applying the second after the first has the same effect as not applying any of them), and no action in between them depends on the first action, then they can both be removed from the plan. Balyo, Chrpa, et al. 2014 build on FY3, taking into account action costs when deciding which set of redundant actions to remove from the plan. The original method removes sets of redundant actions as soon as it discovers them, but their algorithm is a bit less greedy, by identifying multiple sets of redundant actions, and eliminating the one with the highest cost. Med and Chrpa 2022 further improve this greedy action elimination method by introducing Plan Action Landmarks (PALs) and action cycles. We will explain plan action landmarks in detail in Section 5, but put simply, a plan action landmark is an action that must be a part of any plan reduction (i.e., it is never redundant). Action cycles extend the notion of inverse actions from pairs of actions to sequences, identifying (not necessarily consecutive) subsequences of actions in a plan that, if removed, lead to the same state after the execution of the last action. Naively, one could try to preprocess a plan by identifying loops or action cycles in the plan and removing them. However, while the resulting sequence (without the loop) will be a plan, this cannot be done if the purpose is to find a minimal reduction. We illustrate this with a simple example: a task with three Boolean variables 𝑣1, 𝑣2, 𝑣3. The initial state is I = { 𝑣1, 𝑣2, 𝑣3} and the goal is G = {𝑣1, 𝑣2, 𝑣3}. Consider the plan 𝜋= 𝑎1,𝑎2,𝑎3,𝑎4,𝑎5 , where: 𝑎1 = { 𝑣1, 𝑣2}, {𝑣1, 𝑣2} 𝑎2 = {𝑣1, 𝑣2}, { 𝑣1, 𝑣2} Journal of Artificial Intelligence Research, Vol. 84, Article 10. Publication date: October 2025. 𝑎3 = { 𝑣1}, {𝑣1} 𝑎4 = { 𝑣3}, {𝑣3} 𝑎5 = { 𝑣2}, {𝑣2} After applying 𝑎1 and 𝑎2, we end up in the initial state again. So removing all action cycles from 𝜋yields plan 𝜋 = 𝑎3,𝑎4,𝑎5 . Assuming unit costs for all actions, the minimal reduction of 𝜋 is 𝑎3,𝑎4,𝑎5 , since no action is redundant. In contrast, the minimal reduction of 𝜋is 𝑎1,𝑎4 . 3.2 Optimal Methods To the best of our knowledge, the only previous optimal method to solve the minimal reduction problem was proposed by Balyo, Chrpa, et al. 2014. Given a planning task Π and a plan 𝜋= 𝑎1, . . . ,𝑎𝑛 for Π, they define a CNF formula 𝐹Π,𝜋, such that each satisfying assignment represents a plan reduction of 𝜋. By solving 𝐹Π,𝜋with a weighted partial Max SAT solver, they find a plan reduction 𝜋 of minimal cost. Then, by solving a new 𝐹Π,𝜋 created from this reduction using unit cost clauses, they guarantee there are no zero-cost redundant actions in the plan reduction, finding a minimal reduction. We include a full description of the formulation of 𝐹Π,𝜋in Appendix A. 3.3 Plan Justification Beyond Classical Planning Muise et al. 2016 proposed a partial weighted Max SAT encoding that is able to identify redundant actions in plans, as well as produce partial order plans from linear plans. A partially ordered plan, instead of imposing a total order over the actions, specifies a set of ordering constraints (action x is before action y). Their encoding is able to find a minimum cost least commitment partial order plan, that, given an input partially ordered plan, finds a partially ordered plan with the cheapest cost that has the least possible ordering constraints over the actions. Solving this problem can potentially generate cheaper and more flexible plans compared to finding minimal reductions, as it also considers re-ordering actions as well as partially ordered plans. However, while related to our work, re-ordering and de-ordering are distinct research questions with different aims and challenges. Finding a minimal-cost reordering can be exponentially harder than finding minimal reductions in practice, as it requires considering all possible permutations of subsets of actions, whereas minimal reduction only considers subsets. The computational difficulty not only differs significantly in theory, but it can also be observed in practice: Muise et al. 2016 consider re-orderings and mention that plans with more than 200 actions are problematic for their method, since their encoding is too big to fit in memory. In contrast, our methods handle input plans with more than 3000 steps within a few seconds. More recently, Sreedharan et al. 2023 proposed a generalization of plan justifications to policies, in the context of fully observable, non-deterministic planning (FOND). The work focuses on generalizing the notion of welljustified actions. An action is well-justified in a policy if it is needed in every possible trace from the initial state to a goal state. They propose a planning compilation to identify when an action is well-justified in this context. When this new planning task is unsolvable, the action in question is well-justified. 4 Minimal Reduction as Planning In this section, we introduce four planning formulations to solve the minimal reduction problem. First, we describe the design space within which we create the formulations, motivating each option and analyzing their trade-offs. We then describe each formulation and show that an optimal solution to the resulting planning tasks is a minimal reduction of the input plan. Finally, we compare the theoretical properties of each formulation, which will help to interpret the empirical results shown in Section 7. Journal of Artificial Intelligence Research, Vol. 84, Article 10. Publication date: October 2025. 10:8 Salerno, Fuentetaja & Seipp 4.1 Design Space Given a planning task Π and a plan 𝜋that solves Π, the minimal reduction problem asks for a least-cost, perfectly justified reduction 𝜋 of 𝜋. To solve this minimal reduction problem with a classical planner, we must devise a new planning task Π that allows applying or skipping the actions of the original plan 𝜋, while preserving their relative order, and eventually achieving the goal of Π. The simplest task variant that guarantees this is a formulation where each action in the plan is either applied or skipped in order. This implies that plans for the new task have the same length as the input plan. However, when many consecutive actions 𝜋are redundant, it might be more efficient to skip multiple actions at a time, allowing us to find solutions at shallower depths of the search tree. Similarly, for plans with little redundancy, applying multiple actions at a time might improve search performance. With these idea in mind, we propose four different planning compilations: Πs1 a1 ( skip one, apply one ): each action of the plan is either applied or skipped individually.1 Πsm a1 ( skip multiple, apply one ): each action of the plan can be applied individually, but multiple actions can be skipped at a time. Πs1 am ( skip one, apply multiple ): multiple actions can be applied at a time, but actions are skipped individually. Πsm am ( skip multiple, apply multiple ): multiple actions can be applied and skipped simultaneously. 4.2 Πs1 a1 Compilation: Skipping and Applying Single Actions Let Π = V, A, I, G be a planning task and 𝜋= 𝑎1,𝑎2, . . . ,𝑎𝑛 be a plan for Π. We define 𝑅𝜋as the set of facts that appear in a precondition of the actions in the plan 𝜋or in the goal: 𝑅𝜋= Ð 𝑎𝑖 𝜋pre(𝑎𝑖) G. 𝑅𝜋represents the set of relevant facts for 𝜋, or the facts read by 𝜋. We also define 𝑊𝜋as the facts that appear in the effects of the actions or the initial state: 𝑊𝜋= Ð 𝑎𝑖 𝜋eff (𝑎𝑖) I. 𝑊𝜋are the facts written by 𝜋. We refer to the set of all facts in 𝜋as 𝐹𝜋= 𝑅𝜋 𝑊𝜋. With this, we define the function 𝜏, that given a fact 𝑣 𝑑, maps the fact to itself if 𝑣 𝑑is read by 𝜋and to the irrelevant fact 𝑣 𝜃otherwise. ( 𝑣 𝑑 if 𝑣 𝑑 𝑅𝜋 𝑣 𝜃 otherwise. Then, the new planning task Πs1 a1 = V , A , I , G has facts 𝐹 𝜋= {𝜏(𝑣 𝑑) | 𝑣 𝑑 𝐹𝜋}, and is defined as: V = {𝑣 | 𝑣 V |D(𝑣 )| > 1} {pos}, where D(𝑣 ) = {𝑑| 𝑣 𝑑 𝐹 𝜋}; and variable pos with D(pos) = {0, . . . ,𝑛} tracks the current position in the original plan. Note that D(𝑣 ) only contains 𝜃if there is a fact 𝑣 𝑑 𝑊𝜋\ 𝑅𝜋.2 A = {𝑎 𝑖| 1 𝑖 𝑛} {skip𝑖| 1 𝑖 𝑛}, so that for each original plan action 𝑎𝑖, there is one apply action 𝑎 𝑖and one skip action skip𝑖. Actions 𝑎 𝑖are defined as: pre(𝑎 𝑖) = pre(𝑎𝑖) {pos 𝑖 1} eff (𝑎 𝑖) = {𝜏(𝑣 𝑑) | 𝑣 𝑑 eff (𝑎𝑖) 𝑣 V } {pos 𝑖} where the new action has the same preconditions as the original one, plus an additional precondition to ensure that the current position is the preceding one. The effects are the same as the original action, but mapped with function 𝜏to only keep relevant values, plus an additional effect to update the current position. 1This compilation was first presented in our original conference paper (Salerno et al. 2023a). 2Just removing effects that map a variable 𝑣to 𝜃is not enough. Even though 𝑣 𝜃is never read itself, it can affect the applicability of a later action that has 𝑣 𝑑, with 𝑑 𝜃in its preconditions. Journal of Artificial Intelligence Research, Vol. 84, Article 10. Publication date: October 2025. The skip𝑖actions just increase the value of pos from 𝑖 1 to 𝑖: 𝑝𝑟𝑒(skip𝑖) = {pos 𝑖 1} eff (skip𝑖) = {pos 𝑖} The 𝑎 𝑖actions maintain the cost 𝑐(𝑎𝑖) of the corresponding 𝑎𝑖, while the skip𝑖actions have zero-cost.3 I = {𝜏(𝑣 𝑑) | 𝑣 𝑑 I 𝑣 V } {pos 0} is composed of two sets of facts: (1) the facts from the original initial state that are relevant for the plan, i.e., those that belong to (I 𝑅𝜋) and new facts of the form 𝑣 𝜃, setting the variables in V with an irrelevant initial value to 𝜃; and (2) a set with just one fact initializing pos variable to zero. G = G {pos 𝑛} contains the original goals and requires the pos variable to be at the end of the original plan (the latter could be omitted, but it can be useful for heuristics). With this definition of the task, plans for Πs1 a1 can only contain skip actions (with a corresponding skipped action in the original plan) and actions from the original plan in the same order (if they appear in the plan at position 𝑖, they are only applicable when pos is 𝑖 1). Proposition 1. Let Π = V, A, I, G be a planning task, 𝜋= 𝑎1, . . . ,𝑎𝑛 be a plan for Π, Πs1 a1 = V , A , I , G be the reformulated planning task and 𝜋s1 a1 = 𝑏1, . . . ,𝑏𝑚 be a plan for Πs1 a1. Then, there is a one-to-one correspondence between the actions in 𝜋and the actions in 𝜋s1 a1 such that 𝑛= 𝑚and 𝑎𝑖 𝑏𝑖, where 𝑏𝑖is either 𝑎 𝑖(the reformulation of 𝑎𝑖) or skip𝑖. Proof. This follows directly from the construction of Πs1 a1. Every 𝑎 𝑖 A maintains the precondition and relevant effects of 𝑎𝑖 𝜋. Also, both 𝑎 𝑖and skip𝑖actions are only applicable if pos is 𝑖 1, and they set pos to 𝑖. Since pos is 0 in the initial state and 𝑛in all goal states, all plans for Πs1 a1 select either 𝑎 𝑖or skip𝑖at each of the 𝑛steps, producing a plan of length 𝑚= 𝑛. Given Proposition 1, it is trivial to translate a plan 𝜋s1 a1 for Πs1 a1 into a subsequence of the original plan 𝜋for Π. Definition 7 (translated plan). Let 𝜋= 𝑎1,𝑎2, . . . ,𝑎𝑛 be a plan for Π, 𝜋s1 a1 = 𝑏1,𝑏2, . . . ,𝑏𝑛 be a plan for Πs1 a1, and 𝑚, 𝑚 𝑛, the number of actions in 𝜋s1 a1 that are not skip actions. The translated plan is the subsequence 𝜋 = 𝑎𝑓(1), . . . ,𝑎𝑓(𝑚) of 𝜋, containing exactly those actions 𝑎𝑓(𝑘) 𝜋for which the corresponding 𝑏𝑓(𝑘) 𝜋s1 a1 is not a skip action. We now prove that a solution for Πs1 a1 translated by Definition 7 is guaranteed to be a plan reduction of the original plan. We also show that, since the compilation only allows for the application of actions in the original plan or for their explicit elimination, the set of all plans that solve Πs1 a1 translated by Definition 7 is exactly the set of all plan reductions of the original plan. Formally: Proposition 2. Let Π = V, A, I, G be a planning task, 𝜋be a plan for Π, Πs1 a1 = V , A , I , G be the reformulated planning task, and 𝑃s1 a1 be the set of all plans for Πs1 a1 translated by Definition 7. Then 𝑃s1 a1 is exactly the set of all plan reductions of 𝜋for Π. Proof. We have to show that (i) any plan 𝜋 𝑃s1 a1 is a plan reduction of 𝜋, and that (ii) any plan reduction of 𝜋for Π belongs to 𝑃s1 a1. (i) Let 𝜋 be a plan in 𝑃s1 a1, obtained with Definition 7 from original plan 𝜋and plan 𝜋s1 a1 for Πs1 a1. By Definition 7, 𝜋 = 𝑎𝑓(1), . . . ,𝑎𝑓(𝑚) is a subsequence of 𝜋. The initial state I of Πs1 a1 contains all facts from I that are relevant for 𝜋. Every 𝑎 𝑖 A maintains the precondition of its corresponding action 𝑎𝑖 𝜋. Actions 𝑠𝑘𝑖𝑝𝑖in 𝜋s1 a1, omitted from 𝜋to generate 𝜋 by Definition 7, only modify the pos variable and do not contribute to the achievement of other facts in action preconditions or goals. Then 𝑎𝑓(1) is applicable in I, and every action 𝑎𝑓(𝑖) 𝜋 is applicable 3Below, we elaborate on how to handle problems with zero-cost actions. Journal of Artificial Intelligence Research, Vol. 84, Article 10. Publication date: October 2025. 10:10 Salerno, Fuentetaja & Seipp in the state resulting from the application of the previous action 𝑎𝑓(𝑖 1) 𝜋 . The goal description G of Πs1 a1 contains the goals G of Π. Thus, 𝜋 achieves the goals of Π from initial state I, and therefore it is a plan for Π. Since 𝜋 is a subsequence of 𝜋, by Definition 5 𝜋 is a plan reduction of 𝜋. (ii) Let 𝜌be a plan reduction of 𝜋. By Definition 5, 𝜌is a subsequence of 𝜋, so there exists a strictly monotonic function 𝑓mapping its action indices into action indices in 𝜋. The image of 𝑓, img(𝑓), is the set of indices of the actions in 𝜋included in 𝜌. Assume a plan 𝜋s1 a1 is generated from 𝜋by replacing every action 𝑎𝑖 𝜋, where 𝑖 img(𝑓), by the corresponding reformulated action 𝑎 𝑖 A ; and every 𝑎𝑖 𝜋, where 𝑖 img(𝑓) by skip𝑖. Since 𝜌is a plan for Π, 𝜋s1 a1 is a plan for 𝑃s1 a1. Then, the plan reduction 𝜌can be obtained from 𝜋and 𝜋s1 a1 by Definition 7 and therefore 𝜌 𝑃s1 a1. Now that we have shown that all plan reductions of 𝜋for Π can be generated from Πs1 a1, it is easy to see that, if there are no zero-cost actions in Π, an optimal solution for Πs1 a1 is a minimal reduction of 𝜋.4 Theorem 1. Let 𝜋be a plan for a planning task Π without zero-cost actions, and 𝜋s1 a1 an optimal plan for the task Πs1 a1 generated for Π and 𝜋. The plan 𝜋 obtained from 𝜋s1 a1 using Definition 7 is a minimal reduction of 𝜋. Proof. To prove that 𝜋 is a minimal reduction of 𝜋, we have to show that (i) 𝜋 is a plan reduction of minimal cost and (ii) that 𝜋 is perfectly justified. Proposition 1 proves (i), since 𝜋s1 a1 is a plan for Πs1 a1 if and only if the translated plan 𝜋 is a plan reduction of 𝜋. Hence, since action costs in Π and Πs1 a1 are the same, except for skip actions which have zero-cost, and 𝜋s1 a1 is a plan of minimal cost for Πs1 a1, 𝜋 is a plan reduction of minimal cost of 𝜋. Furthermore, from the fact that there are no zero-cost actions in Π, 𝜋 cannot contain redundant actions: if it did, there would exist a plan reduction of lesser cost, implying that 𝜋s1 a1 is not an optimal plan for Πs1 a1, which is assumed. By contradiction, it follows that 𝜋 must be perfectly justified, proving (ii). Since 𝜋 is both a plan reduction of minimal cost and perfectly justified, it is a minimal reduction of 𝜋. Zero-cost Actions. In the presence of zero-cost actions in Π, further steps must be taken to guarantee that an optimal solution for Πs1 a1 is also perfectly justified. One option, in a similar fashion as the WPMax SAT approach (Balyo, Chrpa, et al. 2014), is to create a new Πs1 a1 task, taking as input a plan reduction of minimal cost, but assigning cost 1 to all non-skip actions. However, this implies solving two different planning tasks, which can be time-consuming. To avoid this, we adapt the original costs of the input plan actions by setting the cost of all zero-cost actions to 1, and multiplying all other costs by the factor 𝑓= 𝑚 mincost + 𝜖 , where 𝑚is the number of zero-cost actions in the input plan, mincost is the smallest positive action cost in the plan, and 𝜖is an arbitrarily small positive real number. If all actions have zero-cost, 𝑓is undefined but also unneeded. This factor satisfies 𝑚< 𝑓 mincost, which guarantees that removing any action with an original cost greater than zero will be more beneficial than removing any set of actions that originally cost zero. So, with this modification, an optimal plan for Πs1 a1 is a minimal reduction for 𝜋. Example 2. To better illustrate what a Πs1 a1 task looks like, we return to the running example from Figure 1. Figure 3 shows the Πs1 a1 task resulting from the input plan pick-up-c, stack-c-d, pick-up-b, stack-b-a . The domain of each variable is mapped as explained, only keeping facts in 𝑅𝜋(those that are relevant for the new planning task). Variables a-pos and d-pos can be removed from the task, since their domains only have one value. We keep them in the example to explicitly illustrate cases where variables would disappear. Note that the number of actions in Π and Πs1 a1 differ. The reformulated task has exactly 8 actions, while the original task had 20 (4 pick-up, 4 put-down, 12 stack). This discrepancy stems from the fact that the number of actions in Πs1 a1 depends on the number of actions in the plan 𝜋, not the actions in the task. If |𝜋| = 𝑛, then |A | = 𝑛 2. The Πs1 a1 formulation allows for the explicit application or elimination (skipping) of each action in the input plan. A Πs1 a1 task induces a state space in the form of a tree, rooted in the initial state. It has a branching factor of 4We leave zero-cost actions out of the proof for clarity, but we show how to handle them immediately afterwards. Journal of Artificial Intelligence Research, Vol. 84, Article 10. Publication date: October 2025. Variables V = {arm, a-pos, b-pos, c-pos, d-pos, a-top, b-top, c-top, d-top, pos} Domains D(arm) = {𝑓𝑟𝑒𝑒,𝜃} D(a-pos)= {𝜃} D(a-top) = {𝑐𝑙𝑒𝑎𝑟,𝜃} D(b-pos)= {table, arm, a} D(b-top) = {𝑐𝑙𝑒𝑎𝑟,𝜃} D(c-pos) = {table, arm,𝜃} D(c-top) = {𝑐𝑙𝑒𝑎𝑟,𝜃} D(d-pos)= {𝜃} D(d-top)= {𝑐𝑙𝑒𝑎𝑟,𝜃} D(pos) = {0,1,2,3,4} Actions A = {pick-up-c , skip-pick-up-c, stack-c-d , skip-stack-c-d, pick-up-b , skip-pick-up-b, stack-b-a , skip-stack-b-a} pick-up-c = pre(pick-up-c) {pos 0}, eff (pick-up-c) {pos 1} skip-pick-up-c= {pos 0}, {pos 1} stack-c-d = pre(stack-c-d) {pos 1}, eff (stack-c-d) {pos 2} skip-stack-c-d= {pos 1}, {pos 2} pick-up-b = pre(pick-up-b) {pos 2}, eff (pick-up-b) {pos 3} skip-pick-up-b= {pos 2}, {pos 3} stack-b-a = pre(stack-b-a) {pos 3}, eff (stack-b-a) {pos 4} skip-stack-b-a= {pos 3}, {pos 4} Initial state I = {arm 𝑓𝑟𝑒𝑒, a-pos 𝜃, b-pos 𝑡𝑎𝑏𝑙𝑒, c-pos 𝑡𝑎𝑏𝑙𝑒, d-pos 𝜃, a-top 𝑐𝑙𝑒𝑎𝑟, b-top 𝑐𝑙𝑒𝑎𝑟, c-top 𝑐𝑙𝑒𝑎𝑟, d-top 𝑐𝑙𝑒𝑎𝑟, pos 0} Goal state G = {b-pos on-a, b-top 𝑐𝑙𝑒𝑎𝑟, pos 4} Fig. 3. SAS+representation of the Πs1 a1 task generated from the Blocksworld task in Figure 1 and the plan pick-up-c, stack-c-d, pick-up-b, stack-b-a . at most 2, and each path from the root to a leaf has length 𝑛, where 𝑛= |𝜋| is the number of actions in the input plan. Since only leaf nodes can be goal states, all plans for Πs1 a1 tasks have length 𝑛as well. Figure 4 shows the full state space of the Πs1 a1 task for our running example. 4.3 Πsm a1 Compilation: Skipping Multiple Actions at Once Looking at the definition of a Πs1 a1 task, the naive way to allow skipping multiple actions at a time, is to introduce additional skip actions that change the pos variable to any index greater than its current value. For that, if |𝜋| = 𝑛, the set of skip actions would be SKIPS = {skip𝑖𝑗 | 0 𝑖< 𝑗 𝑛}, where 𝑠𝑘𝑖𝑝𝑖𝑗= {pos 𝑖}, {pos 𝑗} . However, this would incur |SKIPS| = Í𝑛 𝑖=1 𝑖= 𝑛(𝑛+1) 2 skip actions. Since plans commonly have thousands of steps, avoiding this quadratic growth can be beneficial. For this, we now propose a compilation where multiple actions can be skipped without incurring this quadratic growth. Journal of Artificial Intelligence Research, Vol. 84, Article 10. Publication date: October 2025. 10:12 Salerno, Fuentetaja & Seipp c-pos 7 arm arm 7 θ . . . c-pos 7 θ arm 7 free . . . b-pos 7 arm arm 7 θ . . . b-pos 7 a arm 7 free . . . b-pos 7 arm arm 7 θ . . . b-pos 7 a arm 7 free . . . stack-b-askip-stack-b-a skip-pick-up-b skip-stack-b-a skip-stack-c-d skip-pick-up-b skip-stack-b-a skip-pick-up-c skip-stack-c-d stack-b-askip-stack-b-a skip-pick-up-b skip-stack-b-a Fig. 4. Πs1 a1 task state space for the running example. In each node, only the relevant facts that differ from the parent node are shown. Goal states are marked gray. In the initial state all four blocks are on the table, and the mechanical arm is empty. Here, we can either apply the action pick-up-c, or skip it. If it is applied, in the resulting state the mechanical arm is holding block C. Otherwise, nothing changes (except for the pos variable, that we omit for simplicity). Continuing the explanation on the branch of the tree that skips the first action (right branch), the second action of the plan (stack-c-d) is not applicable, since the arm is not holding block C. In this case, the only applicable action is to skip this action. If we continue down this branch, we can pick-up-b and stack-b-d, finding a plan reduction that is a minimal reduction of the input plan. Its cost is 0 + 0 + 1 + 1 = 2. The idea of this new formulation is simple: when one action is applied, all preceding actions become inapplicable. For this, we simply need to introduce a new Boolean variable activei to the task for each action 𝑎𝑖in the input plan. Initially, all actions are active (𝑎𝑐𝑡𝑖𝑣𝑒𝑖, for all 𝑖), and each action 𝑎𝑖has 𝑎𝑐𝑡𝑖𝑣𝑒𝑖in its precondition. Applying action 𝑎𝑖makes the preceding actions and itself inapplicable by setting 𝑎𝑐𝑡𝑖𝑣𝑒𝑗for all 𝑗 𝑖. Let Π = V, A, I, G be a planning task and 𝜋= 𝑎1, . . . ,𝑎𝑛 be a plan for Π. We formally define the planning task Πsm a1 = V , A , I , G as follows: V = {𝑣 | 𝑣 V |D(𝑣 )| > 1} {active𝑖| 1 𝑖 𝑛}, where D(𝑣 ) = {𝑑| 𝑣 𝑑 𝐹 𝜋}, as for Πs1 a1, and D(active𝑖) = { , }, for all 1 𝑖 𝑛. A = {𝑎 𝑖| 1 𝑖 𝑛}, where each 𝑎 𝑖is defined as: pre(𝑎 𝑖) = pre(𝑎𝑖) {active𝑖} eff (𝑎 𝑖) = {𝜏(𝑣 𝑑) | 𝑣 𝑑 eff (𝑎𝑖) 𝑣 V } { active𝑗| 1 𝑗 𝑖} I = {𝜏(𝑣 𝑑) | 𝑣 𝑑 I 𝑣 V } {active𝑖| 1 𝑖 𝑛} G = G Journal of Artificial Intelligence Research, Vol. 84, Article 10. Publication date: October 2025. In a Πsm a1 task, actions 𝑎𝑖in the original plan can be applied if their original preconditions pre(𝑎𝑖) are met and no action that comes after 𝑎𝑖in the plan has been applied. Thus, plans for Πsm a1 can only contain actions from 𝜋maintaining their original order, implying that those plans are plan reductions of 𝜋. To translate Πsm a1 plans into plans for Π, we simply consider for each action its corresponding action in Π. Since each action in Πsm a1 deactivates itself and all preceding actions, its corresponding action index in the original plan is the highest index of the active𝑖variables it sets to in its effects. Formally: Definition 8 (translated Πsm a1 plan). Let 𝜋= 𝑎1,𝑎2, . . . ,𝑎𝑛 be a plan for Π, 𝜋sm a1 = 𝑏1,𝑏2, . . . ,𝑏𝑚 be a plan for Πsm a1 . The translated plan 𝜋 , for each action 𝑏 𝜋sm a1 , takes the corresponding action 𝑎from the original task. A plan for Πsm a1 translated by Definition 8 is a plan reduction of the original plan. Additionally, the set of all plans that solve Πsm a1 translated by Definition 8 is exactly the set of all plan reductions of the original plan. Proposition 3. Let Π = V, A, I, G be a planning task, 𝜋be a plan for Π, Πsm a1 = V , A , I , G be the reformulated planning task, and 𝑃sm a1 be the set of all plans for Πsm a1 translated by Definition 8. Then 𝑃sm a1 is exactly the set of all plan reductions of 𝜋for Π. Proof. We will show that (i) any plan 𝜋 𝑃sm a1 is a plan reduction of 𝜋for Π, and that (ii) any plan reduction of 𝜋 for Π is in 𝑃sm a1 . (i) Let 𝜋 be a plan in Πsm a1 translated from a plan 𝜋sm a1 for Πsm a1 . Since plans for Πsm a1 maintain the order of the actions, 𝜋 is a subsequence of 𝜋. The initial state I contains all relevant facts for 𝜋, and all actions in A maintain all preconditions and relevant effects of their corresponding actions in 𝜋. Thus, since all actions in 𝜋sm a1 are applicable in succession starting from I , all actions in 𝜋 must be applicable in succession starting from I. Furthermore, since G = G and 𝜋sm a1 is a plan for Πsm a1 , 𝜋 is a plan for Π. (ii) Let 𝜌be a plan reduction of 𝜋for Π. By translating actions in 𝜌following the Πsm a1 compilation, we obtain the action sequence 𝜋sm a1 . Since 𝜌is a plan reduction of 𝜋, all of its actions are applicable in succession starting from I. Actions in Πsm a1 maintain all preconditions and relevant effects of the actions in 𝜋, and the only extra precondition is that the corresponding active variable is true. All active variables are set to true in I , and each action only deactivates preceding actions and itself. Hence, given that 𝜌is a subsequence of 𝜋, all actions in 𝜋sm a1 are applicable in succession starting from I . Finally, since G = G, 𝜋sm a1 is a plan for Πsm a1 . Thus, 𝜋sm a1 translated with Definition 8 is in 𝑃sm a1 . If there are no zero-cost actions in Π, an optimal solution for Πsm a1 is a minimal reduction of 𝜋for Π. We omit the corresponding proof since it is analogous to the one for Theorem 1, and we handle zero-cost action in the exact same way as for Πs1 a1 tasks. Theorem 2. Let 𝜋be a plan for planning task Π without zero-cost actions, and 𝜋sm a1 an optimal plan for the task Πsm a1 generated for Π and 𝜋. The plan 𝜋 obtained from 𝜋sm a1 using Definition 8 is a minimal reduction of 𝜋. Proof. The proof is analogous to the proof of Theorem 1. 4.4 Πs1 am Compilation: Applying Multiple Actions at Once To apply multiple actions at a time, we create macro-actions (Fikes et al. 1972) of consecutive actions in the input plan. Traditionally, generating macro-actions involves identifying sequences of actions that are usually applied together (Dawson and Siklóssy 1977; Fikes et al. 1972; Korf 1985). However, since we are interested in finding a plan reduction of an input plan, we know exactly which actions can be applied consecutively simply by looking at the different consecutive subsequences of the plan. Given a plan 𝜋= 𝑎1,𝑎2, . . . ,𝑎𝑛 , the number of consecutive subsequences of at least two actions is Í𝑛 1 𝑖=1 𝑖= 𝑛(𝑛 1) 2 . For example, the consecutive subsequences of 𝜋with |𝜋| = 3 are 𝑎1,𝑎2 , 𝑎1,𝑎2,𝑎3 , 𝑎2,𝑎3 . The macro-action generated from 𝑎𝑖,𝑎𝑖+1, . . . ,𝑎𝑗 represents applying consecutive actions 𝑎𝑖to 𝑎𝑗in a single step. Journal of Artificial Intelligence Research, Vol. 84, Article 10. Publication date: October 2025. 10:14 Salerno, Fuentetaja & Seipp The preconditions and effects of a macro-action 𝑎𝑖𝑗generated from two consecutive actions 𝑎𝑖,𝑎𝑗 are defined as follows: pre(𝑎𝑖𝑗) = pre(𝑎𝑖) (pre(𝑎𝑗) \ eff (𝑎𝑖)) eff (𝑎𝑖𝑗) = eff (𝑎𝑗) {𝑣 𝑑| 𝑣 𝑑 eff (𝑎𝑖), 𝑣 vars(eff (𝑎𝑗))} Chaining two actions in this way is always well-defined for two actions that appear consecutively in the original plan. To generate macro-actions of more than two actions, this procedure can simply be applied repeatedly. Thus, to allow the application of multiple actions at a time, we simply add the appropriate macro-actions in Πs1 a1 that represent consecutive subsequences of actions in 𝜋to Πs1 a1. The added macro-actions increase the number of actions from 2𝑛to 2𝑛+ 𝑛(𝑛 1) 2 compared to Πs1 a1, and the branching factor increases to at most 𝑛+ 1. The increased branching factor might slow down the expansion rate of the search. However, in cases where only a few or no actions can be removed from the original plan, Πs1 am will find solutions at shallower depths of the search tree compared to Πs1 a1. Given a planning task Π = V, A, I, G , a plan 𝜋= 𝑎1,𝑎2, . . . ,𝑎𝑛 , we define Πs1 am = V , A , I , G in terms of Πs1 a1 = V , A , I , G by simply modifying the set of actions to include all possible macro-actions of at least two consecutive actions in 𝜋: A = A {macro(𝑎𝑖,𝑎𝑗) | 1 𝑖< 𝑗 𝑛}, where macro(𝑎𝑖,𝑎𝑗) produces the macro-action including all actions from 𝑎𝑖to 𝑎𝑗in succession. Equivalent propositions to Proposition 1, Proposition 2 and Theorem 1 can be stated for Πs1 am, but we omit them because they are practically identical to the propositions and proofs for Πs1 a1. 4.5 Πsm am Compilation: Applying and Skipping Multiple Actions at Once To completely explore the design space of compilations described in Section 4.1, we need to formulate a compilation that can apply and skip multiple actions at a time. To do this, we simply take Πsm a1 and create macro-actions in the same way as it is done for Πs1 am, and we call it Πsm am. Given a planning task Π = V, A, I, G and a plan 𝜋= 𝑎1,𝑎2, . . . ,𝑎𝑛 , we define Πsm am = V , A , I , G in terms of Πsm a1 = V , A , I , G by modifying the set actions to include all possible macro-actions of at least two consecutive actions in 𝜋: A = A {macro(𝑎𝑖,𝑎𝑗) | 𝑎𝑖,𝑎𝑗 A 1 𝑖< 𝑗 𝑛}. Again, equivalent propositions to Proposition 3 and Theorem 2 can be stated for Πsm am, but we omit them because they are practically identical to the propositions and proofs for Πsm a1 . 4.6 Comparison Between Πs1 a1, Πsm a1 ,Πs1 am and Πsm am Given a planning task Π = V, A, I, G and a plan 𝜋= 𝑎1,𝑎2, . . . ,𝑎𝑛 , we show how the different compilations compare against each other in Table 1. Πs1 a1 and Πs1 am only require the additional pos variable, while Πsm a1 and Πsm am require the 𝑛active variables. |D(pos)| = 𝑛+ 1, so the number of facts in Πs1 a1 and Πs1 am increases only in that amount with respect to 𝑅𝜋, while |D(active𝑖)| = 2 for each of the 𝑛active variables, increasing the number of facts by 2𝑛for Πsm a1 and Πsm am. Πs1 a1 has two actions for each action in 𝜋, while Πsm a1 only has one action for each action in 𝜋. Similarly, Πs1 am has the 2𝑛actions from Πs1 a1 plus the macro-actions, while Πsm am has 𝑛actions plus the macro-actions. The branching factor for Πs1 a1 is always 2 (skip or apply each action in 𝜋), while the branching factor for Πsm a1 can be at most 𝑛(apply any of the active actions), for Πs1 am the highest branching factor is 𝑛+ 1 (apply any macro-action representing a subsequence starting from the first action or skip the first action), and for Πsm am it is 𝑛(𝑛+1) 2 (apply any action or any macro-action). Finally, the number of effects for actions created for both Πs1 a1 and Πs1 am only increases by 1 (updating the pos variable), while each action in Πsm a1 and Πsm am must deactivate itself and all preceding actions. We omit the size of the preconditions in the table since each compilation only adds one additional precondition to each action (pos Journal of Artificial Intelligence Research, Vol. 84, Article 10. Publication date: October 2025. Table 1. Comparison of different characteristics of each compilation. For each compilation we show the number of resulting variables (|V |), the number of actions (|A |), the number of facts |F |, the upper bound on the branching factor of the search tree induced by the compilation (BF), the number of effects of a reformulated action (|eff (𝑎 )|) in terms of the number of effects of the action it was created from, and the upper bound on the size of the state space induced by the compilation (|𝑆|). Πs1 a1 Πsm a1 Πs1 am Πsm am |V | |V| + 1 |V| + 𝑛 |V| + 1 |V| + 𝑛 |A | 2𝑛 𝑛 2𝑛+ 𝑛(𝑛 1) 2 𝑛+ 𝑛(𝑛 1) 2 |F | |𝑅𝜋| + 𝑛+ 1 |𝑅𝜋| + 2𝑛 |𝑅𝜋| + 𝑛+ 1 |𝑅𝜋| + 2𝑛 BF 2 𝑛 𝑛+ 1 𝑛(𝑛+1) 2 |eff (𝑎 𝑖)| |eff (𝑎𝑖)| + 𝑖 |eff (𝑎𝑖)| + 𝑖 |eff (𝑎𝑖)| |eff (𝑎𝑖)| + 𝑖 |𝑆| 2𝑛+1 1 2𝑛 2𝑛+1 1 2𝑛 variable or active variable). Note that both the effects and preconditions of Πs1 am and Πsm am depend on the number of effects and preconditions of the macro-action they represent, so they can have as many as |V| effects and preconditions. Regarding the size of the state space induced by each compilation, it is clear that all compilations can generate any subsequence of actions of the input plan. To obtain an upper bound on the size |𝑆| of the reachable state space induced by each of the four compilations, we assume that 𝑆contains no duplicate states. Under this assumption, each subsequence of actions from the original plan is a different state. For a plan of length 𝑛, the number of subsequences is 2𝑛. Πsm a1 and Πsm am implicitly eliminate actions, so they induce exactly as many states as there are subsequences of the plan (2𝑛). In contrast, Πs1 a1 explicitly eliminates actions. This translates into a branching factor of exactly 2 and a state tree of depth 𝑛(length of the input plan), so assuming there are no duplicates, the number of states is exactly Í𝑛 𝑖=0 2𝑖= 2𝑛+1 1. The size of the state space for Πs1 am is the same as for Πs1 a1, since the macro-actions do not generate different states, just more edges. 5 Plan Action Landmarks Even though identifying if a plan contains any redundant subsequence of actions is NP-complete in general, some actions can easily be detected as necessary. In this section, we discuss plan action landmarks (PALs), which are actions that must be part of any plan reduction of a given plan. The idea of identifying these type of actions to speed up action elimination methods was introduced by Med and Chrpa 2022. The authors proposed an algorithm to identify a specific type of plan action landmarks, which we call trivial plan action landmarks (TPALs). We use this name to distinguish them from fix-point plan action landmarks (FPALs), which extend the notion to a superset of trivial plan action landmarks. We use the name FPAL because these plan action landmarks are computed with a fix-point procedure. In the following, we define trivial and fix-point plan action landmarks, followed by a theoretical analysis of fix-point plan action landmarks. To simplify the notation and without loss of generality, we describe plan action landmarks in terms of extended planning tasks with virtual initial and goal actions. These actions establish the initial state and require that all the goals are achieved, respectively. Definition 9 (extended task and plan). Given a planning task Π = V, A, I, G , the extended task is Π𝑒= V𝑒, A𝑒, I𝑒, G𝑒 , defined as follows. V𝑒= { 𝑣| 𝑣 V} {𝑣𝑔}, where D( 𝑣) = D(𝑣) {init} and D(𝑣𝑔) = {init, goal}. Journal of Artificial Intelligence Research, Vol. 84, Article 10. Publication date: October 2025. 10:16 Salerno, Fuentetaja & Seipp I𝑒= {𝑣 init | 𝑣 V𝑒}. A𝑒= { pre(𝑎) {𝑣𝑔 init}, eff (𝑎) | 𝑎 A} {𝑎init,𝑎goal}, where 𝑎init = I𝑒, I , and 𝑎goal = G {𝑣𝑔 init}, {𝑣𝑔 goal} . G𝑒= {𝑣𝑔 goal}. Each plan 𝜋= 𝑎1,𝑎2, . . . ,𝑎𝑛 for Π corresponds to exactly one extended plan 𝜋𝑒= 𝑎0,𝑎1,𝑎2, . . . ,𝑎𝑛,𝑎𝑛+1 for Π𝑒, where 𝑎0 and 𝑎𝑛+1 are the virtual initial and goal actions 𝑎init and 𝑎goal, respectively. Definition 10 (plan action landmark). Let 𝜋be a plan for an extended planning task Π. An action 𝑎 𝜋 is a plan action landmark of 𝜋iff 𝑎is part of all plan reductions of 𝜋. Identifying whether an action in a plan is a plan action landmark is co-NP-complete (Med and Chrpa 2022), but some plan action landmarks can be identified in polynomial time. Trivial plan action landmarks are one such example. Here, the idea is to identify if a necessary fact for the plan has only one achiever. For example, if only one action 𝑎in a plan achieves a goal fact, removing 𝑎would render the plan invalid. Furthermore, if some preconditions of 𝑎are also achieved by a single action 𝑎 , then 𝑎 is also necessary. This is similar to the back-chaining method of fact landmark discovery (Hoffmann et al. 2004). Definition 11 (trivial plan action landmark, tpal). Let Π = V, A, I, G be an extended planning task and 𝜋= 𝑎0,𝑎1, . . . ,𝑎𝑛,𝑎𝑛+1 be a plan for Π. Action 𝑎𝑖is a trivial plan action landmark for 𝜋iff: (1) 𝑎𝑖is the goal action 𝑎𝑛+1 or (2) there is a trivial plan action landmark 𝑎𝑗, 𝑖< 𝑗, such that there is a fact 𝑝 eff (𝑎𝑖) pre(𝑎𝑗), and there is no action 𝑎𝑘, 𝑘< 𝑗, 𝑘 𝑖, such that 𝑝 eff (𝑎𝑘). Figure 5a illustrates the concept of TPALs graphically. We now prove that trivial plan action landmarks are in fact plan action landmarks.5 Proposition 4. Let 𝜋= 𝑎0,𝑎1, . . . ,𝑎𝑛,𝑎𝑛+1 be a plan for an extended planning task Π = V, A, I, G , and 𝑎𝑖 an action in 𝜋. If 𝑎𝑖is a trivial plan action landmark for 𝜋, then 𝑎𝑖is a plan action landmark for 𝜋. Proof by induction. (1) Base case: both the virtual initial and goal actions are present exactly once in any plan, and they must always appear at the beginning and the end, respectively. If 𝑎𝑖is a TPAL because it is the virtual goal action 𝑎𝑛+1, it must be part of any plan reduction of 𝜋for Π, since it is the only action in the plan that achieves the goal fact 𝑣𝑔 𝑔𝑜𝑎𝑙. Therefore, 𝑎𝑖is a plan action landmark. (2) Inductive step: assuming that 𝑎𝑗is a plan action landmark, we show that if 𝑎𝑖is a TPAL because it is the only action situated before 𝑎𝑗achieving a fact 𝑝in the precondition of 𝑎𝑗, then 𝑎𝑖is a plan action landmark. Since 𝑎𝑗is a plan action landmark, it is part of all plan reductions of 𝜋, and in consequence all facts in its precondition, including 𝑝, must be true in some state of the state sequence induced by applying the prefix up to 𝑎𝑗of any plan reduction. Since no other action in that prefix achieves 𝑝, all plan reductions must contain 𝑎𝑖. Therefore, 𝑎𝑖is a plan action landmark. The concept of fix-point plan action landmarks allows discovering additional plan action landmarks. They extend trivial plan action landmarks by exploiting the fact that, since plan action landmarks must be executed, their effects can be taken into account when identifying other plan action landmarks. While trivial plan action landmarks identify single achievers of a necessary fact (either because it is a goal fact or part of a precondition of a plan action landmark), fix-point plan action landmarks additionally identify single achievers of a necessary fact after a plan action landmark overwrote said fact. 5Proposition 4 is equivalent to Propositions 3 and 4 in the paper by Med and Chrpa 2022, but here we present it in a more compact way, by using the extended planning task. Journal of Artificial Intelligence Research, Vol. 84, Article 10. Publication date: October 2025. Fig. 5. Visual representation of (a) a trivial plan action landmark and (b) a fix-point plan action landmark. Actions already known to be trivial and fix-point plan action landmarks, respectively, are marked in blue. In (a), 𝒂𝒊is a trivial plan action landmark because it is the only achiever of 𝑝= 𝑣 𝑑, which is a precondition of the trivial plan action landmark 𝑎𝑗. The red line indicates the range of plan actions in which 𝑎𝑖is the only achiever. In (b), 𝒂𝒌is a fix-point plan action landmark because it is the only achiever of 𝑣 𝑑, a precondition of the fix-point plan action landmark 𝑎ℓ, situated before 𝑎ℓand after another previous fix-point plan action landmark action, 𝑎𝑖, generates a different value for the same variable 𝑣. Note that if there was another achiever of 𝑣 𝑑situated between 𝑎𝑖and 𝑎ℓ, 𝑎𝑘would not be a FPAL. Definition 12 (fix-point plan action landmark, fpal). Let Π = V, A, I, G be an extended planning task and 𝜋= 𝑎0,𝑎1, . . . ,𝑎𝑛,𝑎𝑛+1 be a plan for Π. Action 𝑎𝑘is a fix-point plan action landmark iff: (1) 𝑎𝑘is a trivial plan action landmark or (2) there is a fix-point plan action landmark 𝑎ℓ, 𝑘< ℓ, such that there is a fact 𝑣 𝑑 eff (𝑎𝑘) 𝑝𝑟𝑒(𝑎ℓ), and there is another fix-point plan action landmark 𝑎𝑖, 𝑖< 𝑘, with an effect 𝑣 𝑑 eff (𝑎𝑖) where 𝑑 𝑑and there is no other action 𝑎𝑗with 𝑗 𝑘, 𝑖< 𝑗< ℓsuch that 𝑣 𝑑 eff (𝑎𝑗). Figure 5b illustrates the concept of FPALs graphically. We now show that fix-point plan action landmarks are, indeed, plan action landmarks. Proposition 5. Let 𝜋= 𝑎0,𝑎1, . . . ,𝑎𝑛,𝑎𝑛+1 be a plan for an extended planning task Π = V, A, I, G , and 𝑎𝑘 an action in 𝜋. If 𝑎𝑘is a fix-point plan action landmark for 𝜋, then 𝑎𝑘is a plan action landmark for 𝜋. Proof by induction. (1) If an action 𝑎𝑘is a FPAL because it is a TPAL (case (1), Definition 12), it is a plan action landmark by Proposition 4. (2) Assuming that 𝑎ℓand 𝑎𝑖are plan action landmarks, we show that if 𝑎𝑘is a FPAL because 𝑎ℓand 𝑎𝑖are FPALs with 𝑖< 𝑘< ℓand 𝑎𝑘is the only achiever of a fact 𝑓= 𝑣 𝑑, where 𝑓 pre(𝑎ℓ) eff (𝑎𝑘) and 𝑣 𝑑 eff (𝑎𝑖), with 𝑑 𝑑 (case (2), Definition 12), then 𝑎𝑘is a plan action landmark. Since 𝑎ℓis a plan action landmark, it belongs to all plan reductions and, consequently, all facts in its precondition must be true in some state of the state sequence induced by applying the prefix up to 𝑎ℓof any plan reduction. Analogously, given that 𝑎𝑖is a plan action landmark, it belongs to all plan reductions and, consequently, after the application of 𝑎𝑖in any plan reduction, the value of 𝑣is necessarily 𝑑 . Since 𝑎𝑘is the only achiever of the fact 𝑣 𝑑, in the precondition of 𝑎ℓ, after 𝑎𝑖overwrote it, it must be part of all plan reductions, and therefore it is a plan action landmark. 5.1 Identifying Plan Action Landmarks Our method to identify fix-point plan action landmarks (and the subsumed TPALs) is shown in Algorithm 1. The input is an extended planning task and a plan. Initially, the virtual goal action is marked as a PAL. Then, the procedure Compute Achievers (called in line 3 and defined in lines 22 26) finds the achievers for each fact 𝑣 𝑑, i.e., all actions 𝑎𝑖 𝜋such that 𝑣 𝑑 eff (𝑎𝑖). For each fact, an achiever is a pair 𝑎𝑖,𝑘 , where 𝑎𝑖is an action in 𝜋and 𝑖< 𝑘. In this pair, 𝑘represents that action 𝑎𝑖is an achiever of fact 𝑣 𝑑until step 𝑘of the plan. This means that action 𝑎𝑖can achieve a fact for the precondition of another action 𝑎𝑗only if 𝑖< 𝑗 𝑘. Initially, for each effect of each action, we initialize 𝑘to the last plan position (line 26). Then, until no new plan action landmark is found (line 5), Compute PALs iterates backwards over all plan actions (line 6). If an action is a Journal of Artificial Intelligence Research, Vol. 84, Article 10. Publication date: October 2025. 10:18 Salerno, Fuentetaja & Seipp Algorithm 1 Compute fix-point plan action landmarks. 1: function Compute FPALs(Π, 𝜋) 2: 𝑎0,𝑎1, . . . ,𝑎𝑛,𝑎𝑛+1 𝜋 3: PALs {𝑎𝑛+1} 4: achs Compute Achievers(𝜋) Initial achievers 5: repeat 6: for 𝑖= 𝑛+ 1 to 0 do 7: if 𝑎𝑖 PALs then 8: for 𝑣 𝑑 pre(𝑎𝑖) do 9: 𝐴 {𝑎𝑗| 𝑎𝑗,𝑘 achs(𝑣 𝑑), 𝑗< 𝑖 𝑘} 10: if 𝐴= {𝑎𝑗} and 𝑎𝑗 PALs then Check if fact has a single achiever 11: PALs PALs {𝑎𝑗} 12: Update Achievers(achs,𝑎𝑗) 13: until PALs remains unchanged 14: return PALs 16: procedure Update Achievers(achs,𝑎𝑗) Update achievers 17: for 𝑣 𝑑 eff (𝑎𝑗) do 18: for 𝑑 D(𝑣) \ {𝑑} do 19: for (𝑎𝑖,𝑘) achs(𝑣 𝑑 ) with 𝑖< 𝑗< 𝑘do 20: achs(𝑣 𝑑 ) = (achs(𝑣 𝑑 ) \ 𝑎𝑖,𝑘 ) 𝑎𝑖, 𝑗 21: 22: function Compute Achievers(𝜋) 23: achs(𝑣 𝑑) = for all 𝑣 V, 𝑑 D(𝑣) 24: for 𝑎𝑖 𝜋do 25: for 𝑣 𝑑 eff (𝑎𝑖) do 26: achs(𝑣 𝑑) = achs(𝑣 𝑑) 𝑎𝑖, |𝜋| 27: return achs plan action landmark (line 7), it checks its precondition (lines 8 10) to see if a new plan action landmark can be identified using Definition 12: is there a unique achiever 𝑎𝑗that was not marked as a plan action landmark before? If a new plan action landmark 𝑎𝑗is identified, it is marked as such (line 11) and the until value of actions whose effects are overwritten by 𝑎𝑗are updated (line 12). Procedure Update Achievers (lines 16 20) finds, for every 𝑣 𝑑 eff (𝑎𝑗), the actions 𝑎𝑖before 𝑎𝑗that set 𝑣to 𝑑 , 𝑑 𝑑, and updates their until value to 𝑗. With only a single iteration of the fix-point loop (lines 5 13) and without the Update call (line 11), Algorithm 1 finds the set of all trivial plan action landmarks, and we call it Compute TPALs. The following two propositions follow from the fact that Compute TPALs and Compute FPALs are direct implementations of Definitions 11 and 12. Proposition 6. Algorithm Compute TPALs finds all trivial plan action landmarks. Proposition 7. Algorithm 1 finds all fix-point plan action landmarks. The Compute TPALs variant is equivalent to the algorithm proposed by Med and Chrpa 2022. The authors showed that it runs in linear time in the length of the plan if the size of action preconditions and effects is assumed to be constant. To find fix-point plan action landmarks, the fix-point loop in Algorithm 1 must be repeated Journal of Artificial Intelligence Research, Vol. 84, Article 10. Publication date: October 2025. every time a new plan action landmark is found. In the worst case, each iteration only discovers one plan action landmark, so the loop runs at most |𝜋| times. Making the same assumptions on the size of preconditions and effects, Algorithm 1 thus runs in 𝑂(|𝜋|2). 5.2 Using Plan Action Landmarks Since plan action landmarks must be part of any plan reduction, there is no need to consider skipping or eliminating them when looking for a minimal reduction. This reduces the branching factor and speeds up the search process for all compilations. We now show how to use information about plan action landmarks to shrink the search space and/or the task size of the four planning compilations. Reducing the Number of Skip Actions in Πs1 a1 and Πs1 am. Both Πs1 a1 and Πs1 am have explicit skip actions that represent eliminating actions, making it easy to not consider removing plan action landmarks simply by omitting their corresponding skip actions. The resulting PAL-enhanced tasks for Πs1 a1 and Πs1 am preserve V , I , G exactly as in Section 4, and only creating skip actions for actions that are not known plan action landmarks. For this, A is redefined as A = {𝑎 𝑖| 1 𝑖 𝑛} {skip𝑖| 1 𝑖 𝑛 𝑝𝑎𝑙(𝑎𝑖)}. Reducing the Number of Macro-Actions in Πs1 am and Πsm am. One clear detriment of Πs1 am and Πsm am is the quadratic number of actions that are created from the input plan. By only creating macro-actions using actions that are not known to be plan action landmarks, the number of actions and the branching factor can be greatly reduced. Reducing the Branching Factor in Πsm a1 and Πsm am. Whenever an action 𝑎𝑖is applied, all variables active𝑗, with 𝑗 𝑖are set to false. This represents eliminating all actions 𝑎𝑗with 𝑗< 𝑖for which active𝑗is true before applying 𝑎𝑖. In Πsm a1 and Πsm am actions are not explicitly removed. To ensure that no plan action landmark is removed, we will modify which actions are active in the initial state, and also change the effects of all actions by taking into account plan action landmarks. We describe these changes formally with the help of two functions: first Pal After(𝑖) and last Pal Before(𝑖), which, for a given planning task Π = V, A, I, G and plan 𝜋= 𝑎1, . . . ,𝑎𝑛 , provide the index of the first plan action landmark with index higher than 𝑖(or 𝑛if there are none), and the index of the last plan action landmark with index smaller than 𝑖(or 0 if there are none), respectively: first Pal After(𝑖) = ( 𝑛 if 𝑝𝑎𝑙(𝑎𝑘) for all 𝑘> 𝑖, min{𝑘| 𝑖< 𝑘 𝑛 𝑝𝑎𝑙(𝑎𝑘)} otherwise, and last Pal Before(𝑖) = ( 0 if 𝑝𝑎𝑙(𝑎𝑘) for all 𝑘< 𝑖, max{𝑘| 1 𝑘< 𝑖 𝑝𝑎𝑙(𝑎𝑘)} otherwise. We show how to modify the task Πsm a1 = V , A , I , G obtained from Π and 𝜋, but the same changes apply to Πsm am. The initial state I is modified so only actions up to the first plan action landmark in 𝜋are active: I = {𝜏(𝑣 𝑑) | 𝑣 𝑑 I 𝑣 V } {active𝑖| 1 𝑖 first Pal After(0)} { active𝑖| first Pal After(0) < 𝑖 𝑛} Regarding the effects of the actions 𝑎 𝑖 A , when 𝑎𝑖is a plan action landmark, all actions up to the next plan action landmark must be activated; and when an action is applied, only the preceding actions up to the previous plan action landmark are deactivated. Journal of Artificial Intelligence Research, Vol. 84, Article 10. Publication date: October 2025. 10:20 Salerno, Fuentetaja & Seipp eff (𝑎 𝑖) ={𝜏(𝑣 𝑑) | 𝑣 𝑑 eff (𝑎𝑖) 𝑣 V } {active𝑗| 𝑝𝑎𝑙(𝑎𝑖) 𝑖< 𝑗 first Pal After(i)} { active𝑗| last Pal Before(i) < 𝑗 𝑖} Furthermore, since plan action landmarks must be executed, each action must only deactivate all preceding actions up to the last plan action landmark (which will have deactivated all preceding actions up to the plan action landmark before that, and so on). When dealing with particularly long plans, this can reduce the size of the effects of each action drastically. Macro-Actions of Plan Action Landmarks. For all compilations, since plan action landmarks must be part of any plan reduction, consecutive subsequences of plan action landmarks can be replaced by a single macro-action. The effect it has on the search space is reducing the depth at which solutions are found. To maximize this effect, the longest possible subsequences must be chosen to be encapsulated as a macro-action. For a plan 𝜋= 𝑎1,𝑎2, . . . ,𝑎𝑛 , let CPAL be the set of the longest consecutive subsequences of plan action landmarks of 𝜋. For all subsequences in CPAL, their corresponding actions are replaced by the macro-action encapsulating all of them. The macro-actions are constructed as explained in Section 4.4. 6 Always Redundant Actions Similarly to plan action landmarks, one might wonder if there are actions that can be identified as always redundant, and not be considered when searching for a plan reduction of a given plan. However, the notion is not as clear as plan action landmarks. An action can be redundant because another action achieves the same facts, but if the other action is removed, this action might no longer be redundant in the resulting plan reduction. In the context of minimal reduction, we now propose actions that can be identified as redundant in polynomial time. In the minimal reduction problem, the goal is to find a perfectly justified plan reduction of least cost. So an action that is never part of a perfectly justified plan reduction cannot be part of a minimal reduction. We call this type of actions always redundant actions. As in the case of plan action landmarks, we use the extended planning task to simplify notation. Definition 13 (always redundant action). Let Π = V, A, I, G be an extended planning task and 𝜋= 𝑎0,𝑎1,𝑎2, . . . ,𝑎𝑛,𝑎𝑛+1 be a plan for Π. An action 𝑎𝑖 𝜋is always redundant iff there is no perfectly justified plan reduction 𝜌of 𝜋such that 𝑎𝑖 𝜌. Given a plan 𝜋for a task Π, if an action 𝑎𝑖 𝜋does not achieve any goal fact nor any precondition fact of another action, it can always be removed from any plan reduction 𝜌of 𝜋without affecting its validity. By Definition 6, 𝜌is not perfectly justified, so 𝑎𝑖is always redundant. Furthermore, if an action 𝑎𝑖only generates facts that are part of the precondition of always redundant actions 𝑎𝑗, following the same reasoning, 𝑎𝑖will not be part of any perfectly justified plan reduction. We call this type of actions trivially redundant actions. Note that, by Definition 9, virtual actions 𝑎0 and 𝑎𝑛+1 must be part of any plan for an extended task, so they are never redundant. Definition 14 (trivially redundant action). Let Π = V, A, I, G be an extended planning task and 𝜋= 𝑎0,𝑎1, . . . ,𝑎𝑛,𝑎𝑛+1 be a plan for Π. Actions 𝑎0 and 𝑎𝑛+1 are never trivially redundant. Action 𝑎𝑖, 1 𝑖 𝑛, is a trivially redundant action for 𝜋iff: for all 𝑎𝑗, 𝑖< 𝑗 𝑛+ 1, eff (𝑎𝑖) pre(𝑎𝑗) = or 𝑎𝑗is trivially redundant. Proposition 8. Let Π = V, A, I, G be an extended planning task and 𝜋= 𝑎0,𝑎1, . . . ,𝑎𝑛,𝑎𝑛+1 be a plan for Π. If 𝑎𝑖is trivially redundant, then 𝑎𝑖is always redundant. Proof by induction. Journal of Artificial Intelligence Research, Vol. 84, Article 10. Publication date: October 2025. (1) Base case: suppose 𝑎𝑖is trivially redundant because it does not achieve any precondition fact required by any subsequent action in the plan. That is, for all 𝑗, 𝑖< 𝑗 𝑛+ 1, eff (𝑎𝑖) pre(𝑎𝑗) = . Assume, for contradiction, that 𝑎𝑖is part of a perfectly justified plan reduction 𝜌of 𝜋. Let 𝜌 = 𝜌\ {𝑎𝑖}, that is, the plan obtained by removing 𝑎𝑖from 𝜌. Since 𝑎𝑖 s effects are not required by any subsequent action in 𝜋, removing 𝑎𝑖preserves applicability and the goal remains achieved. Therefore, 𝜌 is also a plan reduction of 𝜋, and |𝜌 | < |𝜌|. This contradicts the assumption that 𝜌is perfectly justified. Hence, 𝑎𝑖cannot be part of a perfectly justified plan reduction, and is therefore always redundant. (2) Inductive step: assume for all 𝑘, 𝑖< 𝑘 𝑛+ 1, if 𝑎𝑘is trivially redundant, then 𝑎𝑘is always redundant. Let 𝑎𝑖be a trivially redundant action such that 𝑝𝑟𝑒(𝑎𝑖) eff (𝑎𝑗) for some 𝑗, 𝑖< 𝑗 𝑛+ 1. Now suppose, for contradiction, that 𝑎𝑖is part of a perfectly justified plan reduction 𝜌of 𝜋. By the inductive hypothesis, all such 𝑎𝑗are always redundant and therefore cannot be included in any perfectly justified plan reduction of 𝜋. Hence, none of 𝑎𝑖 s effects are required in 𝜌. This reduces to the base case and by the argument in the base case, 𝑎𝑖must then be always redundant contradicting the assumption that it appears in a perfectly justified plan reduction. In a similar fashion as fix-point plan action landmarks, the effects of known plan action landmarks can be used to identify always redundant actions that are not trivially redundant. If an action 𝑎𝑖only achieves facts that are overwritten by a plan action landmark 𝑎𝑗before they are read by another action 𝑎𝑘, 𝑎𝑖can always be removed. However, in practice, this characterization is too restrictive to be useful: for 𝑎𝑖to be always redundant, there needs to be a plan action landmark 𝑎𝑗 A, with 𝑖< 𝑗, that sets the value of a variable 𝑣which does not occur in the precondition of 𝑎𝑗, that is, 𝑣 vars(eff (𝑎𝑗)) \ vars(pre(𝑎𝑗)), and there must be no action 𝑎𝑘, with 𝑖< 𝑘< 𝑗, with a precondition involving variable 𝑣. This type of always redundant actions is absent from our benchmarks and plans. Note that trivially redundant actions and actions that are not backward justified (Definition 3) are not equivalent. An action is not backward justified if there is no chain of causal links connecting it to the virtual goal action. However, this does not imply that the action can never be part of a perfectly justified plan reduction: causal links only consider the last achiever of a fact, so if multiple actions achieve the same fact, the action in question may still be included in a minimal reduction provided all other achievers are removed. In contrast, always redundant actions never achieve any fact that could be useful in reaching the goals in any perfectly justified plan reduction. Thus, all trivially redundant actions are not backward justified, but not all actions that are not backward justified are trivially redundant. Enhancing the performance of all planning compilations with information about always redundant actions is straightforward. Since always redundant actions are never part of a perfectly justified plan reduction, simply omitting the always redundant actions from the set of actions for the reformulated tasks is enough. 7 Evaluation We now evaluate the different methods for finding minimal reductions experimentally. We solve the different planning compilations with the Scorpion planning system (Seipp, Keller, et al. 2020), which is an extension of Fast Downward (Helmert 2006). We use 𝐴 with an admissible heuristic (described below) to find optimal plans, which is necessary to find minimal plan reductions with our approach. We use Python 3.10 to generate the planning task reformulations. To generate the WPMax SAT tasks formulations we use the Java code by Balyo, Chrpa, et al. 2014. To solve the WPMax SAT formulations, we use the Sat4J solver (Le Berre and Parrain 2010). All algorithm runs are limited to a runtime of 30 minutes and 8 Gi B of memory. Code and data for the planning compilations are available online (Salerno et al. 2025). Journal of Artificial Intelligence Research, Vol. 84, Article 10. Publication date: October 2025. 10:22 Salerno, Fuentetaja & Seipp Table 2. Per-domain benchmark analysis. For each domain, we show the number of plans (#), the length of the shortest plan (𝑚𝑖𝑛(𝐿)), the average number of actions in each plan (𝐿), and the length of the longest plan (𝑚𝑎𝑥(𝐿)). Additionally, for each planner, we show the average percentage of redundant actions in plans (number of redundant actions divided by the input plan length, multiplied by 100) and, in parentheses, the number of plans the planner found for each domain. Domain # min(𝐿) 𝐿 max(𝐿) Cerberus Madagascar LAMA BFWS YASHP3 Agricola 18 53 89.72 152 0.00 (2) (0) 0.00 (6) 0.00 (10) (0) Barman 57 150 196.40 377 6.36 (17) (0) 17.82 (19) 4.35 (20) 47.21 (1) Child Snack 25 33 55.48 86 0.00 (1) 4.05 (19) 5.92 (5) (0) (0) Data Network 34 18 95.82 402 3.57 (9) 57.49 (4) 15.90 (11) 7.40 (10) (0) Floortile 47 36 83.11 127 7.99 (20) 4.05 (20) 5.13 (2) 3.50 (2) 22.15 (3) GED 68 62 153.63 390 0.00 (20) (0) 0.00 (20) 0.00 (20) 4.50 (8) Hiking 47 13 446.89 4058 6.54 (8) 5.38 (8) 0.67 (9) 0.00 (8) 55.33 (5) Open Stacks 53 442 731.25 1115 0.00 (13) (0) 0.00 (20) 0.00 (20) (0) Org Synthesis 9 2 4.00 8 0.00 (3) (0) 0.00 (3) 0.00 (3) (0) Org Synthesis Split 21 24 37.62 68 0.00 (4) 0.00 (4) 0.00 (8) 0.00 (5) (0) Parking 45 70 103.64 147 0.00 (5) (0) 0.59 (20) 0.00 (20) (0) Snake 26 34 91.27 270 0.00 (5) (0) 0.00 (3) 0.00 (18) (0) Termes 31 100 732.00 2944 4.94 (11) (0) 9.77 (11) 40.33 (6) (0) Tetris 37 23 71.59 157 0.28 (13) 10.11 (4) 6.67 (2) 10.53 (17) 4.76 (1) Thoughtful 69 27 102.83 318 0.85 (18) 7.86 (5) 0.34 (16) 0.20 (20) 21.79 (10) Transport 53 143 480.85 1358 0.00 (6) (0) 10.15 (7) 7.50 (20) 26.22 (20) Visit All 60 919 3046.97 4976 0.00 (4) (0) 0.72 (16) 0.00 (20) 0.03 (20) 7.1 Benchmark Analysis As benchmarks, we use the same tasks and input plans as Med and Chrpa 2022.6 We omit tasks with conditional effects since the WPMax SAT approach does not support them.7 The benchmark set consists of tasks from the Agile tracks of the International Planning Competitions (IPC) of 2014 and 2018, and plans found with the following planners: Cerberus (Katz 2018), Freelunch Madagascar (Balyo and Gocht 2018), LAMA 2011 (Richter, Westphal, and Helmert 2011), BFWS Preference (Francès et al. 2018) and YAHSP3 (Vidal 2014). We refer to LAMA 2011 simply as LAMA , to Freelunch Madagascar as Madagascar and to BFWS Preference as BFWS . All planners aim to find a single plan as fast as possible. The number of actions in a plan directly influences the size of the state space induced by the reformulated task, and it also directly impacts the number of variables and clauses in the WPMax SAT formulation. Table 2 shows the size of the input plans, as well as the ratio of redundant actions. In general, we are dealing with plans with hundreds of steps, while plans for Visit All have thousands of steps. Particularly short plans are only found in Org Synthesis and Org Synthesis Split. LAMA and BFWS produce the lowest ratio of redundant actions on average, close to 4% on average, while still producing a high number of redundant actions in some domains, like Barman for LAMA (17.82%) and Termes for BFWS (40.33%). On the other hand, Madagascar and YASHP3 produce highly redundant plans, with 12% and 22.75% of the actions being redundant on average for each plan, respectively.8 6While they find plan reductions of arbitrary cost, we solve the minimal reduction problem. 7Adding support for conditional effects to our planning compilations is straightforward and we have done so for our submission to the International Planning Competition (Salerno et al. 2023b). 8We obtained these statistics using the best configuration for Πs1 a1, discussed in Section 7.4. Journal of Artificial Intelligence Research, Vol. 84, Article 10. Publication date: October 2025. Table 3. Comparison of the total time needed to reformulate all tasks, the total time needed to solve all tasks, the sum of these two runtimes, the geometric mean of the number of expansions and the number of solved tasks. All values are computed only over the commonly solved tasks, except for coverage. Note that solving a task compilation implies finding a plan reduction, which includes the case of returning the input plan if it already is a minimal reduction. Πs1 a1 Πsm a1 Πs1 am Πsm am Reformulation Time (s) 6.70 35.84 1497.56 7345.67 Planning Time (s) 16.22 32.14 716.64 55934.31 Compilation + Planning Time (s) 22.92 67.98 2214.20 63279.98 Expansions 105.64 84.41 86.02 68.58 Coverage 683 670 551 414 7.2 Comparison of Planning Compilations We begin by comparing the performance of the different planning compilations without using plan action landmarks. Table 3 shows an aggregated comparison of the performance of Πs1 a1, Πsm a1 , Πs1 am and Πsm am when using ℎmax (Bonet and Geffner 2001) as the heuristic function. We use this simple heuristic to compare the proposed methods, and will evaluate the best configuration of each approach with more advanced heuristic functions in Section 7.4. When it comes to time, Πs1 a1 is fastest overall, both regarding time needed to create the planning task and the time needed to solve it. Πsm am is noticeably slower compared to both Πsm a1 and Πs1 am. The reformulation and solving times for Πs1 am and Πsm am are extremely high when compared to the other reformulations (particularly for Πsm am). This follows from the fact that, as shown in Table 2, many plans have thousands of actions. The number of actions to be created by Πs1 am and Πsm am is quadratic in the length of the input plan (see Table 1), which explains this increase both in reformulation and solving time. For Πsm a1 , the reformulation time is higher than Πs1 a1, even though the number of actions is lower for the former (|𝜋| for Πsm a1 and 2 |𝜋| for Πs1 a1). This counter-intuitive result comes from the fact that actions in Πsm a1 have a large number of effects: each action must deactivate all preceding actions. Πsm am is affected by this large number of effects to an even greater extent because of its larger number of actions. The number of expansions is lower for Πsm a1 , Πs1 am and Πsm am when compared to Πs1 a1 which is to be expected. Allowing to skip and apply multiple actions at a time means states found at a deeper level of the search tree generated by Πs1 a1 can be achieved in a single expansion by the other compilations. However, as can be inferred from Table 1, in general the overhead of the large number of effects and actions, as well as the higher branching factor, translates into a slower expansion rate for the other compilations compared to Πs1 a1, and thus incurs a slower planning process. A per-domain comparison of the four compilations can be found in Figure 6 and in Table 4. For the Open Stacks and Visit All domains, both Πs1 am and Πsm am fail to solve any tasks within the time and memory limits. In contrast, Πs1 a1 and Πsm a1 solve all tasks for Open Stacks, and 58/60 and 53/60 for Visit All, respectively. Πs1 a1 is particularly faster than Πsm a1 for both domains. This is not reflected in Table 4, since we only include statistics for tasks solved by all compilations, but it can be appreciated in Figure 6(a). For Πs1 am and Πsm am, the cause for the weak performance in these domains is the quadratic number of actions created from the input plans, in conjunction with the particularly long plans from those domains.9 9This problem will be alleviated by the use of plan action landmark information in the following section. Journal of Artificial Intelligence Research, Vol. 84, Article 10. Publication date: October 2025. 10:24 Salerno, Fuentetaja & Seipp 10 2 10 1 100 101 102 103 Πs1 a1 (lower for 636 tasks) Πsm a1 (lower for 34 tasks) (a) Πs1 a1 vs Πsm a1 10 2 10 1 100 101 102 103 Πs1 a1 (lower for 547 tasks) Πs1 am (lower for 4 tasks) (b) Πs1 a1 vs Πs1 am 10 2 10 1 100 101 102 103 Πsm a1 (lower for 414 tasks) Πsm am (lower for 0 tasks) (c) Πsm a1 vs Πsm am 10 2 10 1 100 101 102 103 Πs1 am (lower for 409 tasks) Πsm am (lower for 5 tasks) (d) Πs1 am vs Πsm am Agricola Barman Child Snack Data Network Floortile GED Hiking Open Stacks Org Synthesis Org Synthesis Split Parking Snake Termes Tetris Thoughtful Transport Visit All Fig. 6. Comparison of the compilation+planning time between the different planning formulations using the ℎmax heuristic. Overall, Πs1 a1 outperforms the other three approaches, solving all tasks in all domains except for Hiking (37/47), Termes (26/31) and Visitall (58/60). In general, the solving time of Πs1 a1 is lower than the solving time of Πsm a1 , Πs1 am and Πsm am. However, there are cases where the opposite is true. 7.3 Plan Action Landmarks and Always Redundant Actions In this section, we analyze how prevalent trivial and fix-point plan action landmarks are in our benchmarks, as well as always redundant actions. Additionally, we study the impact of enhancing the planning reformulations with fix-point plan action landmark information. 7.3.1 Prevalence of Trivial and Fix-Point Plan Action Landmarks. Table 5 shows that, on average, more than half of the actions of all plans are trivial plan action landmarks, while over 85% of actions are fix-point plan action landmarks. Particularly, in many domains all actions are fix-point plan action landmarks (Org Synthesis, Org Synthesis Split, Open Stacks, Snake, Agricola). In these cases, the FPALs prove that the input plan is perfectly justified, and no planner call is needed. For other domains, a high number of plan action landmarks will greatly reduce the branching factor of the search when solving the reformulated planning tasks. For example, in the Journal of Artificial Intelligence Research, Vol. 84, Article 10. Publication date: October 2025. Table 4. Per-domain statistics for our four compilations using ℎmax: number of instances (#), coverage (C), time needed to reformulate all tasks (RT), time needed to solve all tasks (ST), and geometric mean of the number of expansions (E). All values are computed over the commonly solved tasks, except for coverage. Πs1 a1 Πsm a1 Πs1 am Πsm am Domain # C RT ST E C RT ST E C RT ST E C RT ST E Agricola 18 18 0.3 0.6 86.7 18 2.6 0.8 86.7 18 57.8 9.7 77.8 18 277.3 147.4 77.8 Barman 57 57 0.2 0.4 1332.6 57 1.4 3.6 478.7 57 52.0 39.4 1329.5 7 484.6 9823.3 475.5 Child Snack 25 25 0.2 0.8 68.5 25 0.7 1.4 61.9 25 20.1 5.4 67.3 25 65.9 1097.4 60.6 Data Network 34 34 0.3 1.4 162.4 34 1.8 4.2 131.0 33 52.5 86.8 153.4 30 439.8 7824.9 125.3 Floortile 47 47 0.5 2.0 197.3 47 2.4 4.6 156.3 47 45.4 24.9 195.1 47 349.9 5016.6 154.2 GED 68 68 0.7 1.5 109.6 68 3.8 2.9 102.7 68 59.5 18.5 98.9 44 741.2 13580.5 92.3 Hiking 47 37 0.2 1.1 42.8 37 0.4 1.5 37.8 36 3.8 5.3 38.7 36 12.3 74.3 34.0 Open Stacks 53 53 53 0 0 Org Synthesis 9 9 0.0 0.2 4.3 9 0.0 0.2 4.3 9 0.1 0.5 2.8 9 0.1 0.5 2.8 Org Synthesis Split 21 21 0.4 0.8 37.6 21 0.6 0.7 37.1 21 6.4 1.7 7.7 21 19.3 6.1 7.5 Parking 45 45 0.8 1.6 104.9 45 6.2 2.8 103.7 45 257.6 62.7 100.0 45 1082.6 1151.7 98.8 Snake 26 26 0.5 0.9 70.4 26 2.4 1.2 70.1 26 161.7 60.6 43.2 23 564.6 340.5 43.0 Termes 31 26 0.1 0.2 643.2 20 0.8 1.0 230.7 16 7.6 5.7 640.6 6 263.5 2047.9 228.3 Tetris 37 37 1.1 1.6 138.1 37 3.1 3.0 107.5 37 91.2 88.9 134.2 36 386.0 5713.7 104.2 Thoughtful 69 69 1.6 3.0 98.9 69 8.9 3.9 83.3 69 672.4 303.0 94.0 64 2488.5 5657.6 78.7 Transport 53 53 0.0 0.1 181.4 53 0.6 0.3 159.9 43 9.6 3.7 173.2 3 170.4 3452.0 151.7 Visit All 60 58 52 0 0 Overall 700 683 6.7 16.2 105.6 671 35.8 32.1 84.4 551 1497.6 716.6 86.0 414 7345.7 55934.3 68.6 Visit All domain, if trivial plan action landmarks are used to enhance the search, the branching factor is reduced from 2 to 1.14 on average, and to 1.004 for fix-point plan action landmarks. From these results, we can expect a large reduction of planning time for domains with a high prevalence of plan action landmarks, like Visitall, while domains with low prevalence, like Termes, will remain challenging. 7.3.2 Prevalence of Always Redundant Actions. On average, only 0.7% of actions in plans in our benchmark set are trivially redundant, indicating that modern satisficing planners very rarely yield plans with actions that cannot contribute to the goals of the task, but this does not mean they cannot be more prevalent in different settings. A setting where the idea of always redundant actions can be helpful is plan reuse: imagine you have a plan for a planning task, but you are interested in achieving only a subset of the original goal facts (Fink and Yang 1992). If the effects of some actions are only related to goals that are not in the selected subset of goals, they will be identified as always redundant and can be safely removed, quickly yielding a better plan for this specific subset of goals. Table 6 shows the average ratio of trivially redundant actions for each domain in the benchmark set, where each task is modified by only keeping a subset of the original goals. We consider the original task (100% of the goals), and tasks with 75%, 50% and 25% of the goals. As the number of goals gradually decreases, trivially redundant actions become more and more common, showing they can be useful in the plan-reuse context. Although few plans in our benchmark set contain trivially redundant actions, this does not mean they are never generated by modern planners. Take, for instance, the running example task from the Blocksworld domain shown in Figure 1 and the plan pick-up-b, stack-b-a, pick-up-c, stack-c-d . The goal of the task is to stack 𝐵on top of 𝐴, so actions stack-c-d and pick-up-c are not causally related to the goals of the task. By Definition 14, both actions are trivially redundant: the effects of stack-c-d are not read by any action (the virtual goal action only has the precondition {b-pos 𝑎, a-pos 𝑡𝑎𝑏𝑙𝑒}, and the effects of pick-up-c are only read by the trivially redundant Journal of Artificial Intelligence Research, Vol. 84, Article 10. Publication date: October 2025. 10:26 Salerno, Fuentetaja & Seipp Table 5. For each domain, we show the minimum ratio (min), average ratio (avg) and maximum ratio (max) of trivial and fix-point plan action landmarks (number of PALs over plan length). Domain min avg max min avg max Agricola 0.687 0.745 0.804 1.000 1.000 1.000 Barman 0.095 0.195 0.247 0.377 0.830 1.000 Child Snack 0.558 0.874 1.000 0.667 0.920 1.000 Data Network 0.161 0.579 0.903 0.161 0.794 1.000 Floortile 0.449 0.591 0.722 0.640 0.867 1.000 GED 0.031 0.436 0.864 0.059 0.966 1.000 Hiking 0.007 0.506 0.882 0.008 0.699 1.000 Open Stacks 0.758 0.822 0.925 1.000 1.000 1.000 Org Synthesis 1.000 1.000 1.000 1.000 1.000 1.000 Org Synthesis Split 0.426 0.893 1.000 1.000 1.000 1.000 Parking 0.556 0.648 0.728 0.865 0.983 1.000 Snake 0.107 0.361 0.786 1.000 1.000 1.000 Termes 0.000 0.051 0.199 0.000 0.282 1.000 Tetris 0.000 0.133 0.391 0.000 0.629 1.000 Thoughtful 0.253 0.803 1.000 0.459 0.949 1.000 Transport 0.096 0.395 0.741 0.369 0.785 1.000 Visit All 0.643 0.858 0.987 0.957 0.996 1.000 Overall (700) 0.000 0.582 1.000 0.000 0.865 1.000 action stack-c-d.) Plans for top-𝑘planning tasks are bound to include such actions: in a Blocksworld task, a second cheapest plan can always be constructed by picking up any block not mentioned in the goal description after reaching a goal state, and such an action will be trivially redundant. 7.3.3 Using Plan Action Landmarks. We now analyze how enhancing each reformulation with fix-point plan action landmarks affects its performance. Table 7 shows the impact plan action landmarks have on the performance of each individual compilation. The use of TPALs improves performance for all compilations, and FPALs similarly improve performance over only using TPALs. The coverage increases for all approaches: from 683 to 688 solved tasks for Πs1 a1; 670 to 684 for Πsm a1 ; 550 to 676 for Πs1 am; and 414 to 670 for Πsm am. Πs1 am (Table 7c) and Πsm am (Table 7d) are the greatest beneficiaries of plan action landmarks. This result follows from the fact that, by using plan action landmarks, the number of actions created for Πs1 am and Πsm am is lower, vastly reducing the time needed to create the task, which was the main culprit of its poor performance without plan action landmarks. The increase in reformulation time for Πs1 a1 (Table 7a) is due to the time needed to compute fix-point plan action landmarks, which is considered in the reformulation time. However, since the planning time is greatly reduced, the overall time is still lower than without plan action landmarks. The counter-intuitive decrease in reformulation time for Πsm a1 (Table 7b) is due to the fact that the number of effects in the actions of Πsm a1 shrinks drastically: each action must only deactivate all preceding actions up to the previous plan action landmark. In the best case, this reduces the number of effects of an action from thousands to 1, if the previous action is known to be a plan action landmark (only needs to Journal of Artificial Intelligence Research, Vol. 84, Article 10. Publication date: October 2025. Table 6. Average ratio of trivially redundant actions for tasks modified by keeping only a fraction of goal facts. The absolute number of goals in each modified task is rounded down to the closest integer. Domain 25% 50% 75% 100% Agricola 1.000 0.949 0.949 0.000 Barman 0.162 0.083 0.035 0.000 Child Snack 0.709 0.457 0.262 0.031 Data Network 0.411 0.216 0.111 0.057 Floortile 0.476 0.299 0.108 0.016 GED 0.930 0.869 0.024 0.000 Hiking 0.599 0.231 0.119 0.008 Open Stacks 0.013 0.002 0.001 0.000 Org Synthesis 0.667 0.153 0.153 0.000 Org Synthesis Split 0.430 0.239 0.046 0.000 Parking 0.064 0.010 0.007 0.000 Snake 0.386 0.151 0.069 0.000 Termes 0.080 0.017 0.011 0.000 Tetris 0.682 0.156 0.102 0.010 Thoughtful 0.083 0.036 0.008 0.000 Transport 0.288 0.130 0.045 0.005 Visit All 0.005 0.002 0.002 0.000 Overall (700) 0.411 0.235 0.121 0.007 Table 7. Impact of TPALs and FPALs on the performance of the different planning compilations. RT is the time needed to reformulate all tasks, PT is the time needed to find plans for all reformulated tasks, TT is the total time needed to solve all tasks (RT + PT), E is the geometric mean of the number of expansions and C is the number of solved tasks (coverage). All metrics (except for coverage) consider commonly solved tasks by the three configurations in the respective table. Πs1 a1 Πs1 a1-TPAL Πs1 a1-FPAL RT (s) 38.59 59.85 306.86 PT (s) 3260.66 1142.96 740.24 TT (s) 3299.24 1202.80 1047.10 E 283.25 85.54 10.41 C 683 686 688 (a) Impact of TPALs and FPALs on Πs1 a1. Πsm a1 Πsm a1 -TPAL Πsm a1 -FPAL RT (s) 7836.76 114.45 302.96 PT (s) 26382.58 1067.05 828.21 TT (s) 34219.34 1181.50 1131.17 E 183.16 63.06 7.31 C 670 682 684 (b) Impact of TPALs and FPALs on Πsm a1 . Πs1 am Πs1 am-TPAL Πs1 am-FPAL RT (s) 4479.09 718.11 140.62 PT (s) 19228.46 1684.42 1200.30 TT (s) 23707.55 2402.54 1340.92 E 140.63 51.00 9.27 C 551 675 676 (c) Impact of TPALs and FPALs on Πs1 am. Πsm am Πsm am-TPAL Πsm am-FPAL RT (s) 7345.67 518.83 141.74 PT (s) 55934.31 4162.95 2239.28 TT (s) 63279.98 4681.78 2381.02 E 68.58 28.18 4.02 C 414 658 670 (d) Impact of TPALs and FPALs on Πsm am. Journal of Artificial Intelligence Research, Vol. 84, Article 10. Publication date: October 2025. 10:28 Salerno, Fuentetaja & Seipp Table 8. Time needed to reformulate all tasks, time needed to solve all tasks, sum of reformulation and planning time, geometric mean of number of expansions and coverage. All approaches are enhanced using fix-point plan action landmarks and macro-actions of consecutive plan action landmarks. The heuristic used to solve all problems is ℎmax. Πs1 a1 Πsm a1 Πs1 am Πsm am Reformulation Time (s) 7.85 8.98 45.84 153.14 Planning Time (s) 12.9 14.36 65.76 2329.78 Total Time (s) 20.75 23.34 111.6 2482.92 Expansions 4.73 4.04 4.7 4.02 Coverage 688 684 676 670 deactivate itself). Using PALs reduces the number of expansions for all compilations, as expected, due to the reduced branching factor. Table 8 offers a direct comparison of performance between the different compilations enhanced with FPALs (the same statistics as Table 3, but now all compilations use fix-point plan action landmarks as explained in Section 5.2). Note that the commonly solved tasks for Table 3 and Table 8 differ, so times and expansions in those tables are not comparable. Since using FPALs is always beneficial, and Πs1 a1 is preferable to the other three compilations, we use Πs1 a1 enhanced with FPALs for all experiments below. 7.4 Using Different Heuristics Beyond ℎmax, we evaluated several heuristics spanning a diverse range of approaches to heuristic search. These include the blind heuristic (ℎ0), the ℎLM-cut heuristic (Helmert and Domshlak 2009) and the admissible landmarkbased ℎBJOLP heuristic (Domshlak et al. 2011). As a representative of a state-of-the-art heuristic for optimal classical planning, we considered saturated cost partitioning (Seipp, Keller, et al. 2020) over pattern database heuristics (Edelkamp 2001) and Cartesian abstractions (Seipp and Helmert 2018), referred to as ℎSCP. The evaluated heuristics can be categorized based on their trade-off between informativeness and computational cost. The blind heuristic (ℎ0) is fast to evaluate but wholly uninformed. The ℎmax heuristic strikes a balance, being semi-informed and moderately fast to evaluate. In contrast, ℎSCP, ℎLM-cut and ℎBJOLP are highly informed but require significantly greater computational effort. For the Πs1 a1 reformulation, augmented with fix-point plan action landmarks, ℎSCP achieves the highest coverage in all domains among all heuristics. However, ℎmax solves only one fewer task than ℎSCP (in the Termes domain) while requiring nearly two orders of magnitude less time for the tasks they both solve. To provide a closer comparison, Table 9 highlights results for three representative heuristics: ℎ0, ℎmax and ℎSCP. We do not include ℎLM-cut and ℎBJOLP in the table, as neither solves any task not solved by ℎmax and ℎSCP. The results reveal a trade-off between planning time and heuristic informativeness. While ℎ0 requires the least planning time for the commonly solved tasks, ℎSCP significantly reduces the number of node expansions. This reduction, however, comes at the cost of the high computational overhead required to compute and evaluate ℎSCP. For simpler problems, the additional computation time of informed heuristics like ℎSCP may not be justified. However, for more complex problems, only the additional information provided by such heuristics leads to finding a solution. 7.5 Comparison to WPMax SAT We now compare the Πs1 a1 planning compilation to the WPMax SAT approach (Balyo, Chrpa, et al. 2014), described in Section 3.2. We also highlight a particular plan characteristic where the WPMax SAT approach struggles, and Journal of Artificial Intelligence Research, Vol. 84, Article 10. Publication date: October 2025. Table 9. Per-domain statistics for Πs1 a1 enhanced with fix-point plan action landmarks with three different heuristics: ℎ0, ℎmax and ℎSCP. For each heuristic, we show coverage (C), time needed to solve all tasks (T), geometric mean of evaluated nodes per second (ER), and geometric mean of expanded nodes (E). For domains where all instances need at most 100 evaluations, we do not show ER. All results are computed over all commonly solved tasks. ℎ0 ℎmax ℎSCP Domain C T ER E C T ER E C T ER E Agricola 18 0.47 2.00 18 0.50 2.00 18 8.92 2.00 Barman 57 2.07 99568.9 104.77 57 2.09 34606.4 45.11 57 78.64 11784.9 31.42 Child Snack 25 0.63 6.92 25 0.68 6.49 25 28.48 5.90 Data Network 34 8.94 288314.3 100.41 34 1.86 57717.5 24.09 34 47.42 29565.8 23.21 Floortile 47 1.31 32.07 47 1.45 18.18 47 55.34 15.33 GED 68 1.82 490636.2 3.13 68 2.64 19100.0 2.55 68 74.58 10064.2 2.53 Hiking 37 6.59 516668.7 10.15 38 2.38 114388.3 5.80 38 43.52 49863.5 5.29 Open Stacks 53 1.50 2.00 53 1.79 2.00 53 92.87 2.00 Org Synthesis 9 0.25 2.00 9 0.24 2.00 9 6.71 2.00 Org Synthesis Split 21 0.56 2.00 21 0.59 2.00 21 16.16 2.00 Parking 45 1.22 3.57 45 1.17 3.14 45 53.39 3.10 Snake 26 0.66 2.00 26 0.82 2.00 26 27.59 2.00 Termes 20 3.21 463916.1 1709.28 28 1.31 80664.3 244.19 29 20.65 14374.6 148.08 Tetris 36 41.83 350780.8 76.11 37 0.95 29209.9 10.04 37 45.14 47046.2 19.75 Thoughtful 69 2.25 296896.2 6.28 69 2.39 38804.6 4.84 69 82.53 11331.0 4.50 Transport 53 5.62 332304.4 381.02 53 1.75 47618.0 53.52 53 63.14 7729.2 33.32 Visit All 60 12.45 78784.9 15.67 60 6.51 11441.9 5.74 60 774.82 38027.8 14.84 Overall 678 91.39 275706.3 14.25 688 29.13 39176.6 7.46 689 1519.89 19425.2 7.38 confirm it empirically using a slightly modified Visit All domain. Throughout this section we use Πs1 a1 enhanced with fix-point plan action landmarks and the ℎmax heuristic. 7.5.1 Solving Time and Coverage. Figure 7 compares the time it takes Πs1 a1 and WPMax SAT to solve the minimal reduction tasks. Figure 7a compares the time needed to create the tasks for both approaches, Figure 7b compares the time needed to solve the tasks, and Figure 7c compares the sum of task creation and solving times. We see that Πs1 a1 is faster in most cases, though there are cases where WPMax SAT manages to create the task faster. These cases consist mainly of tasks where the input planning task has a high number of fix-point plan action landmarks (like in Visit All and Open Stacks), since the time needed to compute them is accounted for in the reformulation time for Πs1 a1. Regarding the number of solved tasks, both approaches perform similarly. Πs1 a1 solves 688 out of 700 tasks, while WPMax SAT solves 687. Πs1 a1 solves one more task in the Transport and Hiking domains, while WPMax SAT solves one more task in the Termes domain. 7.5.2 Modified Visit All. We now present a family of minimal reduction tasks where the CNF formula created by the WPMax SAT approach grows drastically, while the planning approaches maintain the same number of actions. Journal of Artificial Intelligence Research, Vol. 84, Article 10. Publication date: October 2025. 10:30 Salerno, Fuentetaja & Seipp 10 2 10 1 100 101 WPMax SAT (lower for 146 tasks) (lower for 533 tasks) (a) Reformulation Time (s) 10 2 10 1 100 101 102 103 WPMax SAT (lower for 21 tasks) (lower for 664 tasks) (b) Solving Time (s) 10 2 10 1 100 101 102 103 WPMax SAT (lower for 77 tasks) Πs1 a1 (lower for 608 tasks) (c) Total Time (s) Agricola Barman Child Snack Data Network Floortile GED Hiking Open Stacks Org Synthesis Org Synthesis Split Parking Snake Termes Tetris Thoughtful Transport Visit All Fig. 7. Scatter plots comparing time needed to: (a) create the minimal reduction task, (b) solve the task and (c) total time (sum of task creation and solving time). In Appendix A, we show how the CNF formula proposed by Balyo, Chrpa, et al. 2014 is created. The number of variables is at most quadratic in the plan length 𝑛, while the number of clauses is at most cubic in 𝑛(Balyo, Chrpa, et al. 2014). The number of clauses depends both on the plan length and the number of achievers and opposers of the required facts. For the number of clauses to grow to the worst case, the input plan needs to contain 𝑛different options to generate each required fact (all actions in the plan are achievers) and 𝑛opposing actions for each fact (all actions in the plan are opposers). Therefore, the formulas generated for input plans where multiple actions require to use an exclusive fact, or consume a fact that needs to be restored with a different action (or actions) will be particularly large. Formula (1) shows that if a fact needs to be true at a given step of the plan, at least one of the actions that achieve said fact before the time step must be true. In the worst case, all actions achieve a specific fact, and this clause can have as many as 𝑛variables, with 𝑛being the plan length. Formula (2) shows that, in order for a fact to be achieved by a specific action at a certain time step 𝑖, none of the actions that oppose that fact must be part of the plan reduction between the action and the time step 𝑖. In the worst case, all actions Journal of Artificial Intelligence Research, Vol. 84, Article 10. Publication date: October 2025. oppose a fact achieved by an action, so this clause can have as many as 𝑛variables. Formula (4) declares that, if an action at time step 𝑖is part of the plan reduction, then all of its preconditions must be true at time 𝑖. For this, for each precondition 𝑝of the action, Formula (1) is added, and for each achiever of 𝑝Formula (2) is also added. If all actions are achievers and opposers of every fact, in the worst case, 𝑛+ 𝑛2 clauses are added to the CNF for each precondition of every action. Assuming the number of preconditions and effects is constant in the plan length, this translates into a cubic number of clauses, as noted by Balyo, Chrpa, et al. 2014. For plans with thousands of actions, this worst-case scenario translates into billions of clauses. In contrast, the size of the Πs1 a1 compilation does not depend on the number of achievers or opposers of facts in the plan; it is only dependent (linear) on the size of the input plan. To simulate a similar situation to this worst case scenario, we slightly modify the Visit All domain. In the original domain, an agent is placed in a grid and must visit all cells in the grid. The actions in the domain allow the agent to move from its current position to any adjacent cell. Our modification consists of adding a resource (fuel) that is consumed after each move: each move consumes the fuel and a refuel action can be executed at any point in the grid. With this modification, all move actions will be opposers of all other (they all consume the available fuel, which is needed to move). Also, for the fuel precondition there will be as many achievers as there are previous actions in the plan (a valid plan needs to refuel after every move action). We modify the input plans by adding a refuel action between move actions to create valid plans for this modified domain (this also makes the plans double in size) and run both Πs1 a1 using FPALs, macro-actions of FPALs and ℎmax and the WPMax SAT approach. Πs1 a1 shows a similar behavior as for the original plans and solves all tasks, while WPMax SAT runs out of memory for each task while creating the CNF. This indicates that, for plans where each fact has many achieving and opposing actions, using the planning reformulation might be preferable over the WPMax SAT when searching for a minimal reduction. 8 Conclusions In this work, we presented several approaches to find minimal plan reductions using classical planning, as well as a review of existing work related to redundant action detection in automated planning. Similarly, a theoretical analysis of trivial and fix-point plan action landmarks was presented, showing that both must be part of any plan reduction of a plan. Additionally, we introduced the concept of always redundant actions, which are actions that are not part of any perfectly justified plan reduction. Experimentally, we compared all planning compilations and found that, in general, Πs1 a1 is preferable to the other approaches, though there are cases where Πsm a1 and Πs1 am outperform it. We looked at the prevalence of trivial and fix-point plan action landmarks, and found that they are highly prevalent in our benchmark set. This indicates that, in many cases, one can identify most actions that must be part of a plan reduction in polynomial time. The same study was done for always redundant actions, and we found that they are not present in our benchmark set, but we illustrated settings where they occur. The performance of different heuristics when solving the minimal reduction problem with the different planning compilations indicates that, in the vast majority of cases, a simple heuristic is preferable over a more informative one. A comparison to the WPMax SAT approach shows that Πs1 a1 is faster in most cases, while solving roughly as many tasks. Finally, we proposed a simple modification to the Visit Alldomain to empirically show a particular type of tasks where the WPMax SAT approach struggles. The experiments using this domain showed that, under these conditions, the formula created by the WPMax SAT grows too fast to be able to find minimal reductions of long plans, while the planning approaches are able to solve them. In the future, we plan to study the impact of using our action elimination techniques inside of anytime planners that iteratively reduce the last found plan before a new search. Furthermore, since our techniques are general, they can be applied to other planning settings where the solutions are sequences of actions, such as temporal, Journal of Artificial Intelligence Research, Vol. 84, Article 10. Publication date: October 2025. 10:32 Salerno, Fuentetaja & Seipp numeric or conformant planning. While we focused on obtaining minimum plan reductions, our techniques can also be applied to find any plan reduction, simply by running a satisficing instead of an optimal planner on the reformulations. Finally, to solve the minimal reduction problem, we maintain the relative order of actions. However, it is easy to lift this restriction to solve the problem of finding the cheapest plan that also uses only actions from the input plan, but possibly in a different order. Acknowledgments This work was partially funded by grant PID2021-127647NB-C21 from MCIN/AEI/10.13039/501100011033, by the ERDF A way of making Europe , and by the Madrid Government under the Multiannual Agreement with UC3M in the line of Excellence of University Professors (EPUC3M17) in the context of the V PRICIT (Regional Programme of Research and Technological Innovation). Furthermore, this work was partially supported by the Wallenberg AI, Autonomous Systems and Software Program (WASP) funded by the Knut and Alice Wallenberg Foundation and by TAILOR, a project funded by the EU Horizon 2020 research and innovation programme under grant agreement no. 952215. The computations were enabled by resources provided by the National Academic Infrastructure for Supercomputing in Sweden (NAISS) partially funded by the Swedish Research Council through grant agreement no. 2022-06725. C. Bäckström and B. Nebel. 1995. Complexity Results for SAS+ Planning. 11, 4, 625 655. T. Balyo, L. Chrpa, and A. Kilani. 2014. On Different Strategies for Eliminating Redundant Actions from Plans. In: Proceedings of the Seventh Annual Symposium on Combinatorial Search (So CS 2014). Ed. by S. Edelkamp and R. Barták. AAAI Press, 10 18. T. Balyo and S. Gocht. 2018. The Freelunch Planning System Entering IPC 2018. In: Ninth International Planning Competition (IPC-9): Planner Abstracts, 51 54. P. Bercher, P. Haslum, and C. Muise. 2024. A Survey on Plan Optimization. In: Proceedings of the 33rd International Joint Conference on Artificial Intelligence (IJCAI 2024). Ed. by K. Larson. IJCAI, 7941 7950. B. Bonet and H. Geffner. 2001. Planning as Heuristic Search. 129, 1, 5 33. B. Bonet and H. Geffner. 2000. Planning with Incomplete Information as Heuristic Search in Belief Space. In: Proceedings of the Fifth International Conference on Artificial Intelligence Planning and Scheduling (AIPS 2000). Ed. by S. Chien, S. Kambhampati, and C. A. Knoblock. AAAI Press, 52 61. T. Bylander. 1994. The Computational Complexity of Propositional STRIPS Planning. 69, 1 2, 165 204. L. Chrpa, T. L. Mc Cluskey, and H. Osborne. 2012a. Determining Redundant Actions in Sequential Plans. In: Proceedings of the 24th International Conference on Tools with Artificial Intelligence (ICTAI 2012). IEEE, 484 491. L. Chrpa, T. L. Mc Cluskey, and H. Osborne. 2012b. Optimizing Plans through Analysis of Action Dependencies and Independencies. In: Proceedings of the Twenty-Second International Conference on Automated Planning and Scheduling (ICAPS 2012). Ed. by L. Mc Cluskey, B. Williams, J. R. Silva, and B. Bonet. AAAI Press, 338 342. C. Dawson and L. Siklóssy. 1977. The Role of Preprocessing in Problem Solving Systems. In: Proceedings of the 5th International Joint Conference on Artificial Intelligence (IJCAI 1977). Ed. by R. Reddy. William Kaufmann, 465 471. C. Domshlak, M. Helmert, E. Karpas, E. Keyder, S. Richter, G. Röger, J. Seipp, and M. Westphal. 2011. BJOLP: The Big Joint Optimal Landmarks Planner. In: IPC 2011 Planner Abstracts, 91 95. S. Edelkamp. 2001. Planning with Pattern Databases. In: Proceedings of the Sixth European Conference on Planning (ECP 2001). Ed. by A. Cesta and D. Borrajo. AAAI Press, 84 90. R. E. Fikes, P. E. Hart, and N. J. Nilsson. 1972. Learning and Executing Generalized Robot Plans. 3, 251 288. E. Fink and Q. Yang. 1992. Formalizing Plan Justifications. In: Proceedings of the Ninth Conference of the Society for Computational Studies of Intelligence, 9 14. G. Francès, H. Geffner, N. Lipovetzky, and M. Ramiréz. 2018. Best-First Width Search in the IPC 2018: Complete, Simulated, and Polynomial Variants. In: Ninth International Planning Competition (IPC-9): Planner Abstracts, 23 27. M. Helmert. 2006. The Fast Downward Planning System. 26, 191 246. M. Helmert and C. Domshlak. 2009. Landmarks, Critical Paths and Abstractions: What s the Difference Anyway? In: Proceedings of the Nineteenth International Conference on Automated Planning and Scheduling (ICAPS 2009). Ed. by A. Gerevini, A. Howe, A. Cesta, and I. Refanidis. AAAI Press, 162 169. J. Hoffmann, J. Porteous, and L. Sebastia. 2004. Ordered Landmarks in Planning. 22, 215 278. Journal of Artificial Intelligence Research, Vol. 84, Article 10. Publication date: October 2025. S. Jiménez Celorrio, P. Haslum, and S. Thiébaux. 2013. Pruning bad quality causal links in sequential satisfying planning. In: ICAPS 2013 Workshop on Planning and Learning, 45 52. E. Karpas and C. Domshlak. 2011. Living on the Edge: Safe Search with Unsafe Heuristics. In: ICAPS 2011 Workshop on Heuristics for Domain-Independent Planning (HDIP), 53 58. M. Katz. 2018. Cerberus: Red-Black Heuristic for Planning Tasks with Conditional Effects Meets Novelty Heuristic and Enchanced Mutex Detection. In: Ninth International Planning Competition (IPC-9): Planner Abstracts, 47 51. M. Katz and S. Sohrabi. 2022. Who Needs These Operators Anyway: Top Quality Planning with Operator Subset Criteria. In: Proceedings of the Thirty-Second International Conference on Automated Planning and Scheduling (ICAPS 2022). Ed. by S. Thiébaux and W. Yeoh. AAAI Press. M. Katz, S. Sohrabi, and O. Udrea. 2022. Bounding Quality in Diverse Planning. In: Proceedings of the Thirty-Sixth AAAI Conference on Artificial Intelligence (AAAI 2022). Ed. by V. Honavar and M. Spaan. AAAI Press. M. Katz, S. Sohrabi, and O. Udrea. 2020. Top-Quality Planning: Finding Practically Useful Sets of Best Plans. In: Proceedings of the Thirty-Fourth AAAI Conference on Artificial Intelligence (AAAI 2020). Ed. by V. Conitzer and F. Sha. AAAI Press, 9900 9907. M. Katz, S. Sohrabi, O. Udrea, and D. Winterer. 2018. A Novel Iterative Approach to Top-k Planning. In: Proceedings of the Twenty-Eighth International Conference on Automated Planning and Scheduling (ICAPS 2018). Ed. by M. de Weerdt, S. Koenig, G. Röger, and M. Spaan. AAAI Press, 132 140. R. E. Korf. 1985. Depth-First Iterative-Deepening: An Optimal Admissible Tree Search. 27, 1, 97 109. D. Le Berre and A. Parrain. 2010. The Sat4j library, release 2.2. Journal on Satisfiability, Boolean Modeling and Computation, 7, 2 3, 59 64. N. Lipovetzky and H. Geffner. 2017. Best-First Width Search: Exploration and Exploitation in Classical Planning. In: Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence (AAAI 2017). Ed. by S. Singh and S. Markovitch. AAAI Press, 3590 3596. D. A. Mc Allester and D. Rosenblitt. 1991. Systematic Nonlinear Planning. In: Proceedings of the Ninth National Conference on Artificial Intelligence (AAAI 1991). Vol. 2. AAAI Press, 634 639. J. Med and L. Chrpa. 2022. On Speeding Up Methods for Identifying Redundant Actions in Plans. In: Proceedings of the Thirty-Second International Conference on Automated Planning and Scheduling (ICAPS 2022). Ed. by S. Thiébaux and W. Yeoh. AAAI Press, 252 260. C. Muise, J. C. Beck, and S. A. Mc Ilraith. 2016. Optimal Partial-Order Plan Relaxation via Max SAT. 57, 113 149. H. Nakhost and M. Müller. 2010. Action Elimination and Plan Neighborhood Graph Search: Two Algorithms for Plan Improvement. In: Proceedings of the Twentieth International Conference on Automated Planning and Scheduling (ICAPS 2010). Ed. by R. Brafman, H. Geffner, J. Hoffmann, and H. Kautz. AAAI Press, 121 128. B. Nebel, Y. Dimopoulos, and J. Koehler. 1997. Ignoring Irrelevant Facts and Operators in Plan Generation. In: Recent Advances in AI Planning. 4th European Conference on Planning (ECP 1997). Ed. by S. Steel and R. Alami. Vol. 1348. Springer-Verlag, 338 350. C. Olz and P. Bercher. 2019. Eliminating Redundant Actions in Partially Ordered Plans A Complexity Analysis. In: Proceedings of the Twenty-Ninth International Conference on Automated Planning and Scheduling (ICAPS 2019). Ed. by N. Lipovetzky, E. Onaindia, and D. E. Smith. AAAI Press, 310 319. S. Richter and M. Westphal. 2010. The LAMA Planner: Guiding Cost-Based Anytime Planning with Landmarks. 39, 127 177. S. Richter, M. Westphal, and M. Helmert. 2011. LAMA 2008 and 2011 (planner abstract). In: IPC 2011 Planner Abstracts, 50 54. M. Salerno, R. Fuentetaja, and J. Seipp. 2025. Code and Data for the Article Finding Minimal Plan Reductions Using Classical Planning . https://doi.org/10.5281/zenodo.14065819. (2025). M. Salerno, R. Fuentetaja, and J. Seipp. 2023a. Eliminating Redundant Actions from Plans using Classical Planning. In: Proceedings of the Twentieth International Conference on Principles of Knowledge Representation and Reasoning (KR 2023). Ed. by P. Marquis, T. C. Son, and G. Kern-Isberner. IJCAI Organization, 774 778. M. Salerno, R. Fuentetaja, and J. Seipp. 2023b. Spock: Fast Downward Stone Soup with Redundant Action Elimination. In: Tenth International Planning Competition (IPC-10): Planner Abstracts. B. Say, A. A. Cire, and J. C. Beck. 2016. Mathematical Programming Models for Optimizing Partial-Order Plan Flexibility. In: Proceedings of the 22nd European Conference on Artificial Intelligence (ECAI 2016). Ed. by G. A. Kaminka, M. Fox, P. Bouquet, E. Hüllermeier, V. Dignum, F. Dignum, and F. van Harmelen. IOS Press, 1044 1052. J. Seipp and M. Helmert. 2018. Counterexample-Guided Cartesian Abstraction Refinement for Classical Planning. 62, 535 577. J. Seipp, T. Keller, and M. Helmert. 2020. Saturated Cost Partitioning for Optimal Classical Planning. 67, 129 167. F. H. Siddiqui and P. Haslum. 2015. Continuing Plan Quality Optimisation. 54, 369 435. J. Slaney and S. Thiébaux. 2001. Blocks World revisited. 125, 1 2, 119 153. D. Speck, R. Mattmüller, and B. Nebel. 2020. Symbolic Top-k Planning. In: Proceedings of the Thirty-Fourth AAAI Conference on Artificial Intelligence (AAAI 2020). Ed. by V. Conitzer and F. Sha. AAAI Press, 9967 9974. S. Sreedharan, C. Muise, and S. Kambhampati. 2023. Generalizing Action Justification and Causal Links to Policies. In: Proceedings of the Thirty-Third International Conference on Automated Planning and Scheduling (ICAPS 2023). Ed. by S. Koenig, R. Stern, and M. Vallati. AAAI Press, 417 426. Journal of Artificial Intelligence Research, Vol. 84, Article 10. Publication date: October 2025. 10:34 Salerno, Fuentetaja & Seipp B. Srivastava, T. A. Nguyen, A. Gerevini, S. Kambhampati, M. B. Do, and I. Serina. 2007. Domain Independent Approaches for Finding Diverse Plans. In: Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI 2007). Ed. by M. M. Veloso, 2016 2022. V. Vidal. 2014. YAHSP3 and YAHSP3-MT in the 8th International Planning Competition. In: Eighth International Planning Competition (IPC-8): Planner Abstracts, 64 65. M. Waters, L. Padgham, and S. Sardina. 2020. Optimising Partial-Order Plans Via Action Reinstantiation. In: Proceedings of the 29th International Joint Conference on Artificial Intelligence (IJCAI 2020). IJCAI, 4143 4151. A WPMax SAT Formulation Below, we summarize how the WPMax SAT formula by Balyo, Chrpa, et al. 2014 is constructed, in order to show how the characteristics of the planning task affect it. To encode the minimal reduction problem as a SAT problem, the following variables are defined: 𝑎𝑖for 1 𝑖 𝑛: 𝑎𝑖is used in the plan reduction. 𝑦𝑝,𝑖,𝑘for 1 𝑘< 𝑖 𝑛: plan action 𝑎𝑘is responsible for achieving fact 𝑝at step 𝑖in the plan reduction. 𝑦𝑝,𝑖,0: the initial state is responsible for achieving fact 𝑝at step 𝑖in the plan reduction. Using these variables, the formula 𝐹Π,𝜋is constructed as a conjunction of clauses representing which actions from the input plan are applied. For each action in the input plan, clauses are introduced to guarantee that all their preconditions hold when the action is applied. To formulate 𝐹Π,𝜋, the authors consider achievers and opposers. An action is an achiever of a fact 𝑓if 𝑓 eff (𝑎). Similarly, an action is an opposer of a fact 𝑣 𝑑if 𝑣 𝑑 eff (𝑎), with 𝑑 𝑑. With these notions, the sets of achievers and opposers can be defined as: Achs(𝑝,𝑖): set of plan positions 𝑗of the achievers of fact 𝑝with 𝑗< 𝑖. Opps(𝑝,𝑖, 𝑗): set of plan positions 𝑘of opposers of fact 𝑝with 𝑖 𝑘 𝑗. Using the achievers and opposers, the authors define the following formulas: 𝐹𝑝,𝑖: if a fact 𝑝is required to be true at step 𝑖in the plan reduction, then it must be generated by the initial state or by at least one of its achievers with plan positions smaller than 𝑖: 𝐹𝑝,𝑖= 𝑦𝑝,𝑖,0 Ü 𝑗 Achs(𝑝,𝑖) 𝑦𝑝,𝑖,𝑗 (1) 𝐹𝑝,𝑖,𝑗: for 1 𝑗 𝑛encodes that, if a plan action 𝑎𝑗is responsible for achieving fact 𝑝at time 𝑖in the plan reduction, then 𝑎𝑗must belong to the plan reduction, and that none of the opposing actions between 𝑗and 𝑖belong to the plan reduction: 𝐹𝑝,𝑖,𝑗= ( 𝑦𝑝,𝑖,𝑗 𝑎𝑗) Û 𝑘 Opps(𝑝,𝑗,𝑖) ( 𝑦𝑝,𝑖,𝑗 𝑎𝑘) (2) 𝐹𝑝,𝑖,0: the initial state is responsible for achieving fact 𝑝at time 𝑖: 𝑘 Opps(𝑝,0,𝑖) ( 𝑦𝑝,𝑖,0 𝑎𝑘) (3) 𝐹𝑎𝑖: if 𝑎𝑖is an action of the plan reduction, then all its preconditions are required to be true at time 𝑖: ( 𝑎𝑖 𝐹𝑝,𝑖) 𝐹𝑝,𝑖,0 Û 𝑗 Achs(𝑝,𝑖) 𝐹𝑝,𝑖,𝑗ª (4) 𝐹𝐺: all goal conditions must be true in the end of the plan: 𝐹𝑝,𝑖 𝐹𝑝,𝑖,0 Û 𝑗 Achs(𝑝,𝑛) 𝐹𝑝,𝑛,𝑗ª (5) Journal of Artificial Intelligence Research, Vol. 84, Article 10. Publication date: October 2025. Then 𝐹Π,𝜋is defined as: 𝐹Π,𝜋= 𝐹𝐺 Û 𝑖=1,...,|𝜋| 𝐹𝑎𝑖 (6) Clearly, every satisfying assignment 𝜙of 𝐹Π,𝜋constitutes a plan reduction 𝜋𝜙of 𝜋, where an action 𝑎𝑖is present in the plan reduction if 𝜙(𝑎𝑖) = . To solve the minimal reduction problem using 𝐹Π,𝜋, the authors use a weighted partial Max SAT (WPMax SAT) formula and a WPMax SAT solver. WPMax SAT problems have hard and soft clauses. In a solution to a WPMax SAT problem, all hard clauses must be satisfied, while soft clauses can be true or false. Each soft clause has a weight associated with it, and the goal is to satisfy the hard clauses while maximizing the summed weight of the satisfied soft clauses. The hard clauses are defined as 𝐻Π,𝜋= 𝐹Π,𝜋; while the soft clauses are unit clauses with negated action variables, 𝑆Π,𝜋= Ó 𝑎𝑖 Π 𝑎𝑖. The weight of each soft clause is the cost of the corresponding action. Thus, maximizing the weight of the satisfied soft clauses is equivalent to removing actions with maximal cost. To deal with potential redundant zero-cost actions remaining after solving the WPMax SAT, a minimal length reduction (same scheme but with unitary action costs) is performed on the resulting plan reduction. Received 07 June 2025; accepted 04 September 2025 Journal of Artificial Intelligence Research, Vol. 84, Article 10. Publication date: October 2025.