Lifted Successor Generation in Numeric Planning (Extended Version)

Dominik Drexler · 2025

Read Lifted Successor Generation in Numeric Planning (Extended Version) by Dominik Drexler (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-00673.txt.

Introduction

Dominik Drexler speeds up automated planning for tasks with numbers. Most planners translate a task written in a first-order-like language into ground facts before searching, and that grounding step can explode exponentially on hard tasks. Drexler extends a leading lifted successor generator, which works with the compact lifted form, to handle numeric preconditions on actions for the first time.

The method enumerates maximum cliques in a substitution consistency graph, where each clique yields one ground action, now augmented with numeric checks. The generator is proved exact under stated conditions. When conditions fail it may over-list actions, but a final applicability filter restores completeness, and in practice the failure is rare across benchmark domains. Rich numeric planning fragments become searchable without the grounding blowup.

Catalog record

CREATORDominik Drexler
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE33 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-00673

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Lifted Successor Generation in Numeric Planning (Extended Version) Dominik Drexler Abstract Most planners ground numeric planning tasks, given in a first-order-like language, into a ground task representation. However, this can lead to an exponential blowup in task representation size, which occurs in practice for hard-to-ground tasks. We extend a state-of-the-art lifted successor generator for classical planning to support numeric precondition applicability. The method enumerates maximum cliques in a substitution consistency graph. Each maximum clique represents a substitution for the variables of the action schema, yielding a ground action. We augment this graph with numeric action preconditions and prove the successor generator is exact under formally specified conditions. When the conditions fail, our generator may list inapplicable ground actions; a final applicability check filters these without affecting completeness. However, this cannot happen in 23 of 25 benchmark domains, and it occurs only in 1 domain. To the authors’ knowledge, no other lifted successor generator supports numeric action preconditions. This enables future research on lifted planning for a very rich planning fragment. Introduction Numeric planning extends classical planning by introducing numeric state variables, constraints, and effects, thereby enabling the modeling of richer and more realistic domains ( Fox and Long 2003 ) . Although tasks are typically specified in a first-order-like representation, most planners fully ground them. This grounding step often performs well on many existing benchmarks but can lead to an exponential increase in representation size. At the same time, the ground representation facilitates the development of domain-independent heuristics to guide search ( Hoffmann 2003 ; Aldinger and Nebel 2017 ; Scala et al. 2017 , e.g.,) , which are less straightforward to define directly over first-order representations. However, exponentially larger ground tasks may not fit into memory, causing search to fail, thereby imposing a limitation on lifted search guidance , such as lifted heuristics ( Chen and Thiébaux 2024 ; Borelli et al. 2025 , e.g.,) or generalized policies ( Wang and Thiébaux 2024 , e.g.,) learned on smaller example tasks yet scaling to larger ones. Our work is also compatible with extensions of such to numeric planning ( Francès, Bonet, and Geffner 2021 ; Corrêa et al. 2022 ; Horčík, Fišer, and Torralba 2022 ; Drexler, Seipp, and Geffner 2022 ; Wichlacz, Höller, and Hoffmann 2022 ; Ståhlberg, Bonet, and Geffner 2023 , e.g.,) . We address the lifted successor generation problem. More precisely, given a first-order action schema and a state, the task is to enumerate exactly those ground actions that are applicable in the state. In comparison, grounded planners often instantiate ground actions independent of a specific state upfront, which can be exponentially many, and store them in a data structure that allows fast enumeration for a given state ( Helmert 2009 ) . In the lifted successor generation setting, however, applicability must ensure consistent object-variable substitutions across all relevant lifted representations, such as literals and numeric constraints. To the best of our knowledge, existing lifted successor generators build upon conjunctive queries ( Corrêa et al. 2020 ) , constraint satisfaction problem ( Francès 2017 ) , or k -clique enumeration in k -partite graphs (KPKC) ( Ståhlberg 2023 ) . We build upon the KPKC-based approach, initially proposed for classical planning tasks, which formulates lifted successor generation as a k -clique enumeration problem in k -partite graphs. This approach encodes an action precondition as a k -partite substitution consistency graph, where each k -clique represents an object-variable substitution of the action parameters yielding a candidate applicable ground action. The generator is sound and complete when predicates have arity at most two, meaning that it cannot generate inapplicable ground actions. However, in the general case, a verification of actual applicability is required. We extend the KPKC-based approach to consider additional structural information from numeric planning tasks. Our approach incorporates numeric constraints into the substitution consistency graph. Consequently, we generalize the theoretical guarantees from the classical to the numeric planning fragment. Our theoretical result guarantees soundness and completeness if and only if literals, function terms, and constraints have arity at most two. We ran an empirical evaluation that validates this result, showing that inapplicable ground actions cannot occur in 23 out of 25 domains across two benchmark suites. Moreover, we observe such actions occurring in only one of the two candidate domains. Background In this section, we define the background and notation on interval arithmetic ( Moore, Kearfott, and Cloud 2009 ) and numeric planning ( Fox and Long 2003 ; Haslum et al. 2019 ) . We consider extended real numbers \overline{\mathbb{R}}=\mathbb{R}\cup\{-\infty,+\infty\} . Interval Arithmetic A (closed) interval is J=[a,b]=\{r\in\overline{\mathbb{R}}\mid a\leq r\leq b\} and the set of all intervals is \mathcal{J}=\{[a,b]\mid a,b\in\overline{\mathbb{R}},a\leq b\}~\dot{\cup}~\{\emptyset\} where \emptyset denotes the empty interval. For an arithmetic operator \odot\in\{+,-,\times,\div\} and a comparison operator \oplus\in\{=,<,>,\leq,\geq\} , and for all J,J^{\prime}\in\mathcal{J} , we define \displaystyle J\odot J^{\prime} \displaystyle=\mathit{hull}\bigl(\{x\odot y\mid x\in J,y\in J^{\prime}~.~x\odot y\text{ is defined }\}\bigr), \displaystyle J\oplus J^{\prime} \displaystyle=\begin{cases}\text{true}&\exists x\in J,y\in J^{\prime}~.~x\oplus y\text{ evaluates to true,}\\ \text{false}&\text{otherwise.}\end{cases} where convex hull \mathit{hull}(S)=[\inf S,\sup S] for set S , with \mathit{hull}(\emptyset)=\emptyset . If S is unbounded from above (resp. below) then \sup S=+\infty (resp. \inf S=-\infty ). Numeric Planning A numeric planning task is a tuple \langle\mathcal{P},\mathcal{F},\mathcal{A},\mathcal{O},\mathcal{S}_{0},\mathcal{G}\rangle . The planning domain comprises \langle\mathcal{P},\mathcal{F},\mathcal{A}\rangle , and the task information comprises \langle\mathcal{O},\mathcal{S}_{0},\mathcal{G}\rangle , namely: Predicates and Literals. \mathcal{P} is a set of predicate symbols. Each predicate symbol P in \mathcal{P} has an associated arity \mathit{ar}(P) in \mathbb{N} . An atom over a predicate P of arity \mathit{ar}(P)=k is an expression P(x_{1},\ldots,x_{k}) where x_{i} with i=1,\ldots,k are variables or constants. An literal is either an atom p or its negation \neg p . Functions and Numeric Expressions. \mathcal{F} is a set of function symbols. Each function symbol F in \mathcal{F} has an associated arity \mathit{ar}(F) in \mathbb{N} . A function term over a function symbol F of arity \mathit{ar}(F)=k is an expression F(x_{1},\ldots,x_{k}) where x_{i} with i=1,\ldots,k are variables or constants. A function expression is any expression built from function terms using arithmetic operators \odot . A numeric constraint is an expression of the form e\oplus e^{\prime} where e and e^{\prime} are function expressions and \oplus is a comparison operator. A numeric effect is an expression of the form f\otimes e , where f is a function term, e is a function expression, and \otimes is one of \{:=,\mathrel{+}=,\mathrel{-}=,\mathrel{\times}=,\mathrel{\div}=\} . Objects and Substitutions. \mathcal{O} is a set of objects (constants). A substitution function \rho over some set of variables \mathcal{X}(\rho) and objects \mathcal{O} is a function \rho:\mathcal{X}(\rho)\rightarrow\mathcal{O} mapping each variable in \mathcal{X}(\rho) to an object in \mathcal{O} . We write \mathcal{R}(\mathcal{X},\mathcal{O}) for the set of all \rho over \mathcal{X} and \mathcal{O} . We write x_{1}/o_{1},\ldots,x_{n}/o_{n} for a substitution function \rho over variables \mathcal{X}=\{x_{1},\ldots,x_{n}\} and objects \mathcal{O} such that \rho(x_{i})=o_{i} for all i=1,\ldots,n . We write \rho\subseteq\rho^{\prime} iff \mathcal{X}(\rho)\subseteq\mathcal{X}(\rho^{\prime}) and \rho(x)=\rho^{\prime}(x) for all x in \mathcal{X}(\rho) . The application of \rho to a syntactic element y (e.g., an atom, literal, function term, function expression, numeric constraint, numeric effect, or action), denoted by y[\rho] , replaces every occurrence of each variable x_{i} with the corresponding object o_{i}=\rho(x_{i}) . The set of free variables occurring in an element y is denoted \mathcal{X}(y) , and the arity \mathit{ar}(y) of y is set

Read the complete text