Planning with Object Creation

Venue: icaps-conference_org_ICAPS_2024_Conference
Published: 2023-12-05 17:26:06

Abstract: Classical planning problems are defined using some specification language, such as PDDL. The domain expert defines action schemas, objects, the initial state, and the goal. One key aspect of PDDL is that the set of objects cannot be modified during plan execution. While this is fine in many domains, sometimes it makes the modeling much more complicated. This not only impacts the performance of the planners, but it also requires the domain expert to bound the number of required objects beforehand, which might be an intractable problem by itself. Here, we introduce an extension to the classical planning formalism, where action effects can create and remove objects. This problem is semi-decidable, but it becomes decidable if we can bound the number of objects at any given state, even though the state-space is still infinite. On the practical side, we extend the Powerlifted planning system to support this PDDL extension. Our results show that Powerlifted does not lose efficiency by supporting this extension while allowing for easier PDDL models.

Main paper: 
 introduction: 
 Bob, a former classical planning researcher, is opening a 20 new logistics company. Real life, however, is not so simple. He first needs to decide how many trucks he needs to buy. Buying many trucks is not an issue -Bob became very rich working with classical planning -but he still wants to minimize his expenses. He decides to tackle this problem using classical planning. Bob encodes the map of his city and the delivery locations in PDDL (McDermott 2000; Haslum et al. 2019) . He then declares a bunch of truck objects in advance, and cleverly encodes his actions to balance the costs between buying a new truck and doing more deliveries with 30 a same truck. But how does he know how many trucks to declare in advance? Does he compute an estimate upper bound or does he overshoot this bound? Computing it seems as if he is solving the problem himself, so he goes with a rough estimate of 10 trucks. But does the optimal solution only require 10 trucks? What if it requires much more? Bob gets worried, and increases the number of truck objects to 1, 000.He finally formalizes his problem and runs it on some classical planners. All planners take months to solve his task. At the end, the optimal plan uses 11 trucks. Even if 99.8% of the objects were irrelevant, they still impacted the performance of the planners (Fuentetaja and de la Rosa 2016; Silver et al. 2021) . Bob ends up frustrated with the whole procedure. If only there was a native way to let planners introduce more objects as they plan.In this paper, we introduce a novel way of dealing with problems where the objects are not all known upfront. Instead of preemptively declaring all objects in the definition of the task, new objects can be created and also removed via action effects. There are three clear benefits to this extension: (i) it makes the encoding simpler and more natural for several domains (e.g., Long and Fox 2003) , (ii) it reduces the amount of expert knowledge need in the domain encoding (e.g., Petrov and Muise 2023) , and (iii) it might improve performance of planners by reducing state size and number of unnecessary objects (e.g., Fuentetaja and de la Rosa 2016).On the theoretical side, classical planning with object creation is semi-decidable. In other words, if a plan exists we are guaranteed to find it. However, no algorithm will recognize, in general, if a task is unsolvable. If we talk about optimal planning though, the problem becomes decidable. Furthermore, for tasks with bounded states we show decidability, even though the state-space is still infinite.On the practical side, we introduce a PDDL extension that allows for object creation/removal in the effect of actions. More importantly, we extend the state-of-the-art lifted planner Powerlifted (Corrêa et al. 2020) to deal with our formalism. Powerlifted has better performance when using the extended PDDL, in comparison with the original PDDL encodings where all objects are declared beforehand and object creation/removal is simulated with auxiliary predicates. Overall, this is a first implementation showing object creation is feasible and useful for many domains.We consider first-order languages L = ⟨V, P⟩, where V is a finite set of variables and P is a finite set of predicate symbols. Each predicate symbol P ∈ P has an associated arity ar(P ) ∈ N 0 . We restrict our definitions to languages without constant or function symbols. 1 Thus, a term is a variable. An atom P (t 1 , . . . , t ar(P ) ) is composed of a predicate symbol P ∈ P and a tuple of terms ⟨t 1 , . . . , t ar(P ) ⟩. We assume familiarity with common concepts from first-order logic.An interpretation over a first-order language L is a tuple I = ⟨U I , {P I } P ∈P ⟩ consisting of • a finite2 set U I of objects called the universe, and • for each predicate symbol P ∈ P, its interpretation P I ⊆ (U I ) ar(P ) . A variable assignment is a function σ (partial or total) that maps the variables V to objects. For a variable v and object t, we write σ[v/t] for the assignment that agrees with σ on variables other than v and maps v to t. With some abuse of notation, we extend σ to atoms, e.g., σ(P (v, w)) := P (σ(v), σ(w)). 3As usual, we write I, σ |= φ to denote that a formula is 95 true for a given interpretation and assignment. This is defined as usual in first-order logic with one extension. Under regular first-order logic conventions, variable assignments are always total, and we must have σ(V) ⊆ U I for the notation s, σ |= φ to be legal. In this paper, we do allow assignments to map variables to objects that are not part of the universe of I, but atoms involving such variables will always be false, i.e., I, σ ̸ |= P (v 1 , . . . , v n ) if for some i we have that σ(v i ) / ∈ U I . This does not require a modification to the standard semantics of atoms (if σ(V) ⊆ U I then define I,σ |= P (v 1 , . . . , v n ) iff ⟨σ(v 1 ), . . . , σ(v n )⟩ ∈ P I ),but is rather an extension of which notations are considered legal, i.e., we extend the notation I, σ |= φ to cases where σ(V) ̸ ⊆ U I . This extension will prove convenient for defining the semantics of object-creation effects in the following 110 section (in particular, for conditional effects).A planning task with object creation is a tuple Π = ⟨L, s 0 , G, A⟩, where L is a first-order language; s 0 is the initial state, which is an interpretation over L; G is the goal, 115 which is a closed formula over L; A is a finite set of action schemas, defined below. In the context of planning tasks, interpretations are known as states, and it is customary to denote them by s. Example 1. We use the logistics scenario from the Introduction as a running example. Variables are denoted using upper case letters (T, L, etc.), and objects as lower case letters (c 1 , t, etc.). The predicate symbols are at, in, connected (binary) and headquarters (unary). The initial state s 0 has:U s0 := {p 1 , c 1 , c 2 } P s0 := {connected(c 1 , c 2 ), connected(c 2 , c 1 ), at(p 1 , c 1 ), headquarters(c 1 )}.(We write P s0 as a set of atoms here to simplify notation.)We define the goal G := at(p 1 , c 2 ). Intuitively, our task has a package p 1 initially located at city c 1 . There are two cities, c 1 and c 2 , which are connected.The city c 1 is the headquarters of the company. The goal is to move p 1 from c 1 to c 2 .The action schemas are defined in the next example. An action schema A = ⟨pre(A), eff(A)⟩ consists of a precondition pre(A) and an effect eff(A). The precondition pre(A) is a first-order formula. Effects are defined inductively as follows:• every atom a and its negation ¬a are effects, called simple effects; • if e 1 , e 2 are effects, then (e 1 ∧ e 2 ) is a conjunctive effect;• if φ is a first-order formula and e is an effect, then (φ ▷ e) is a conditional effect;• if v ∈ V is a variable and e is an effect, then ∀v : e is a universal effect; • if v ∈ V is a variable and e is an effect, then ⊕v : e is an object-creation effect;• if v ∈ V is a variable, then ⊖v is an object-removal effect.As usual we may drop parentheses when there is no resulting ambiguity, e.g., we may write e 1 ∧ e 2 ∧ e 3 instead of ((e 1 ∧ e 2 ) ∧ e 3 ). Apart from object-creation and objectremoval effects, these definitions follow the PDDL formalism (McDermott et al. 1998; Haslum et al. 2019) , except that we use logic notation. Intuitively, an object-creation effect creates a new object and binds it to a variable v within the effect. An object-removal effect removes an object in the resulting state. Example 2. Define the following action schemas: pre(buy) := headquarters(L) eff(buy) := ⊕T : at(T, L) pre(sell-all) := ¬headquarters(L) eff(sell-all) := ∀T : at(T, L) ▷ ⊖T pre(move) := at(T, L) eff(move) := ¬at(T, L) ∧ at(T, M ) Thus, action buy says "if the L is the headquarters, then add a new truck to L"; sell-all says "if location L is not the headquarters, sell all the trucks at L"; and move says "move a truck T from location L to M ".We extend the definition of free variables from formulas to effects:• for a simple effect e, free(e) is the set of variables appearing in e; • free(e 1 ∧ e 2 ) = free(e 1 ) ∪ free(e 2 ); • free(φ ▷ e) = free(φ) ∪ free(e); • free(∀v : e) = free(e) \ {v};• free(⊕v : e) = free(e) \ {v}.• free(⊖v) = {v}. We also extend the definition to action schemas as free(A) = free(pre(A)) ∪ free(eff(A)). Free variables of action schemas correspond to parameters in PDDL.Next, we want to define semantics for action application, for which purpose we introduce the changes function. This function maps a state, variable assignment and effect to a tuple of new objects, removed objects, added atoms, and deleted atoms. We define changes(s, σ, eff) inductively:• if eff is a positive simple effect a, then changes(s, σ, eff) = ⟨∅, ∅, {σ(a)}, ∅⟩;• if eff is a negative simple effect ¬a, then changes(s, σ, eff) = ⟨∅, ∅, ∅, {σ(a)}⟩; • if eff = (e 1 ∧ e 2 ), then changes(s, σ, eff) = ⟨New 1 ∪ New 2 , Rem 1 ∪ Rem 2 , Add 1 ∪ Add 2 ,⟩ = changes(s, σ[v/u], e) for all u ∈ U s . • if eff = ⊕v : e, then changes(s, σ, eff) = ⟨New ′ ∪ {new}, Rem ′ , Add ′ , Del ′ ⟩,where new is a unique fresh object,5 and ⟨New ′ , Rem ′ , Add ′ , Del ′ ⟩ = changes(s, σ[v/new], e).• if eff = ⊖v, then changes(s, σ, eff) = ⟨∅, {σ(v)}, ∅, ∅⟩, Example 3. Let σ be an assignment with σ(L) = c 1 . Then changes(s 0 , σ, eff(buy)) = ⟨{t}, ∅, {at(t, c 1 )}, ∅⟩ where t is a fresh object not in U s0 .We are now ready to complete the definition of action semantics. A ground action A s,σ is given by an action schema A, a state s, and a variable assignment σ that maps the free variables of A to elements of U s (its definition for other variables does not matter). We say that the ground action A s,σ is applicable in a state s if s, σ |= pre(A). The successor state succ(s, σ, A) under A s,σ is the state defined as follows. Let changes(s, σ, eff(A)) = ⟨New, Rem, Add, Del⟩. For each P ∈ P, letAdd P = {⟨t 1 , . . . , t n ⟩ | ⟨P, ⟨t 1 , . . . , t n ⟩⟩ ∈ Add} Del P = {⟨t 1 , . . . , t n ⟩ | ⟨P, ⟨t 1 , . . . , t n ⟩⟩ ∈ Del} Then succ(s, σ, A) = ⟨U ′ , (P ′ ) P ∈P ⟩, where U ′ = (U s \ Rem) ∪ New P ′ = {t ∈ (P s \ Del P ) ∪ Add P | t ∈ U ′ }.Example 4. Using σ from the previous example, the successor state s 1 = succ(s, σ, buy) is:U s1 := {p 1 , c 1 , c 2 , t} P s1 := {connected(c 1 , c 2 ), connected(c 2 , c 1 ), at(p 1 , c 1 ), at(t, c 1 ), headquarters(c 1 )}. A plan is a finite sequence of ground actions A s0,σ0 0 , . . . , A sn,σn i such that, A si,σi is applicable in state s i for 0 ≤ i ≤ n, and s i+1 = succ(s i , σ i , A i ) for 0 ≤ i < n, and succ(s n , σ n , A n ) |= G.Remark 1. Our logical language does not have constant symbols. We decided so because we do not want to commit to what happens if an object named by a constant symbol is removed (e.g., should the constant symbol interpret a different object?). Instead, we observe that constants can be emulated in our definition of planning with object creation.Suppose C is a finite set of constant symbols that may appear in the goal and the action schemas. For each c i ∈ C, introduce a unary predicate C i . In the initial state, ensure that the interpretation of each C i predicate consists of a single object. We replace an action A by an action A ′ as follows. Let {c 1 , . . . , c m } ⊆ C be the set of constants symbol occurring in A. We define pre(A ′ ) aspre(A ′ ) = ∃x 1 . . . . ∃x m . C i (x i ) ∧ pre(A)[c i /x i ]where pre(A)[c i /x i ] indicates the original precondition but replacing each constant c i with the respective variable x i .Intuitively, this ensures that none of the objects relevant to A (those interpreted by constants that are mentioned in A) have been removed. If they have have, however, the action becomes inapplicable. We also define eff(A ′ ) = eff(A)[c i /x i ].Last, the goal G is modified in a similar fashion, by quantified its constants on the new predicates. This construction encodes that, whenever an object associated to constant symbol is removed, all action schemas referring to this constant are inapplicable. It also encodes that once an object mentioned in the goal is removed, the goal is no longer reachable.We introduce two natural decision problems:Definition 1 (OBJCREATION-PLANEX). Given a planning task with object creation Π, is there a plan for Π? Definition 2 (OBJCREATION-PLANLEN). Given a planning task with object creation Π and k ∈ N, is there a plan for Π with length at most k?Classical planning problems can be solved in many different ways, e.g., satisfiability (Kautz and Selman 1992 ), heuristic search (Bonet and Geffner 2001) . In this work, we will extend the planning-as-heuristic-search paradigm to planning with object creation. We assume that the reader has familiarity with search algorithms and their terminology.We extended the PDDL syntax with the keywords : new and : remove. The first one allows for the creation of objects, and the second for their removal. Their syntax is as follows:(: new (?v1 . . .?vN) (eff)) (: remove (?v1 . . .?vN))where v1, . . . , vN are variables and eff is an effect. In contrast to the logic formalism above, the PDDL syntax allows to create or remove many objects at once. This can be easily reproduced within our formalism. For object creation, the PDDL encoding is equivalent to ⊕v 1 : . . . : ⊕v N : eff, and the encoding of the object removal effect is equivalent to ⊖v 1 ∧ . . . ∧ ⊖v N .6 Example 5. In our running example, the action buy is written in PDDL as (: action buy : parameters (?L) : precondition (headquarters ?L) : effect (: new (?T) (at ?T ?L))).This extension simplifies many PDDL models. With standard PDDL, domain experts need to puzzle out how to simulate object creation. This usually involves adding extra predicates, and modifying conditions to take these predicates into account. For example, in the original Settlers domain (Long and Fox 2003) vehicles can be created during the search.To encode this in PDDL, the authors had to introduce a new predicate potential that indicated whether some object was a potential vehicle or note. Besides enumerating in the initial state all potential vehicles, they also had to add to every action using an vehicle ?V the precondition (potential ?V). The resulting domains are usually much more entangled and complicated than their versions with native PDDL object creation.We show next that OBJCREATION-PLANEX is undecidable.In fact, it is undecidable even if it contains one single action schema with an object creation effect. We can use our formalism above to decide whether a Turing Machine (TM) halts at a given input or not.Definition 3 (Turing Machine). A Turing Machine (TM) isgiven by a tuple M = ⟨Q, Σ, δ, q 0 , q accept , q reject ⟩, where• Q is a finite set of states; • Σ = {0, 1, □} is the alphabet; • δ : (Q \ {q accept , q reject }) × Σ → Q × Σ × {L, R} is the transition function; • q 0 ∈ Q is the start state; • q accept ∈ Q is the accept state; • q reject ∈ Q is the reject state, where q accept ̸ = q reject ;The machine has a head that can move left (L) or right (R), and a working tape. This tape is denoted as Tape. We assume it is infinite to the right, but not to the left. Given an input x ∈ {0, 1} * , Tape starts with x written on its left-most cells, and □ is on all the other (infinite many) cells (denoting that they are empty). The head of the machine starts at the leftmost cell (i.e., the first symbol of x).Theorem 1. OBJCREATION-PLANEX is undecidable.Proof. We reduce the problem of deciding whether a given TM M halts (i.e., reaches either q accept or q reject ) on a given input x to the problem of deciding if there is a plan for Π.The first-order language of Π is defined as follows. The 260 variables are Q i , S i , D, C i (also without indices) where Q i encode states (i.e., Q i ∈ Q), S i encodes TM tape symbols (i.e., S i ∈ Σ), D encodes TM directions (i.e., D ∈ {L, R}), and C i encodes TM positions on the tape. It contains the following predicates: state(Q 1 ), encoding that the TM is 265 currently at state Q 1 ; transition(Q 1 , Q 2 , S 1 , S 2 , D) encoding that from state Q 1 when reading S 1 there is a transition that writes S 2 , changes state to Q 2 , and moves the head in direction D; head(C) indicating that the head is at cell C; next(C 1 , C 2 ) indicating that C 1 is immediately to the left of 270 C 2 in Tape; right-limit(C), indicating that cell C is the current right-most cell; symbol(C, S) encoding that cell C has symbol S written in it; terminated, a nullary predicate indicating that the run of the TM terminated in q accept or q reject ; is-right(D) and is-left(D) checking if direction D is right 275 (R) or left (L); accept(Q 1 ) and reject(Q 1 ) checking if state Q 1 is q accept or q reject .Our task has the following action schemas: (i) read a symbol at cell C and move the head to the left; (ii) read a symbol at cell C and move the head to the right, to a cell that has 280 been reached before or is in the input; (iii) read a symbol at cell C and move the head to the right, to a fresh cell, while expanding the tape; (iv) reject the input; (v) accept the input.To keep things short, we only show action schema (iii). We denote this action by A. It uses variablesQ 1 , Q 2 , S 1 , S 2 , C 1 , C 2 , D. We define pre(A) as pre(A) := state(Q 1 ) ∧ transition(Q 1 , Q 2 , S 1 , S 2 , D) ∧ symbol(C 1 , S 1 ) ∧ head(C 1 ) ∧ right-limit(C 1 ) ∧ is-right(D),and the effect eff(A) as follows:eff(A) := state(Q 2 ) ∧ symbol(C 1 , S 2 ) ∧ ¬state(Q 1 )∧ ¬symbol(C 1 , S 1 ) ∧ ¬head(C 1 ) ∧ ¬right-limit(C 1 ) ∧ (⊕C 2 : head(C 2 ) ∧ right-limit(C 2 ) ∧ next(C 1 , C 2 ))Action schemas (i) and (ii) are similar, but they have no object creation effect: instead of moving the head to a new 285 tape cell, they use the predicate next to encode already existing cells. Action schema (iv) has variable Q, precondition state(Q) ∧ reject(Q), and effect terminated. Action (v) is analogous to (iv) but uses accept(Q) in the precondition.In the initial state s 0 = {U s0 , {P s0 }}, the interpretation 290 {P s0 } contains7 • transition(q 1 , q 2 , s 1 , s 2 , d) if δ(q 1 , s 1 ) = (q 2 , s 2 , d);• state(q 0 ); • for the i-th symbol of the input x, we introduce the atom symbol(c i , s i ) where c i is the i-th cell of Tape and 295 s i ∈ {0, 1} is the respective symbol in x. If a cell c ′ comes after (i.e., to the right) of c in Tape, we introduce predicate next(c, c ′ ). If c is the last cell in Tape, we add right-limit(c).Procedure 1: Compute plan for tasks with object creation for all σ : free(A) → U s do 8:if s, σ |= pre(A) then 9:openList ← openList ∪ {succ(s, σ, A)} 10: return unsolvable• head(c 0 ) where c 0 is the first cell of the tape, 300• is-right(R) and is-left(L),• accept(q accept ) and reject(q reject ), while U s0 contains all objects in {P s0 }. The goal is defined as G = terminated.The initial state of our task exactly encodes the initial con-305 figuration of M in input x: the head starts at the first cell, the state is the initial state q 0 , and the input is encoded in the first cells of the tape. The actions simulate the possible transitions between configurations of the TM. The important detail is that we initialize only a finite number of symbol predicates, which is actually the length of x. Whenever we need to use new cells, we can use the action schema described above to append an extra cell at the end of the tape. Task Π can simulate M precisely. If there exists a plan for Π, the plan can be converted into a trace of configurations of M . Similarly, if M never halts, Π has no plan.Theorem 1 shows that planning with object creation is undecidable in general. However, when plans exist we can still compute them. In other words, OBJCREATION-PLANEX is semi-decidable.First, consider Procedure 1. It shows a general state-space search (without duplicate elimination). It works just the same for tasks with object creation. If openList behaves as a FIFO, then Procedure 1 is a breadth-first search. This procedure can also be extended to accommodate heuristic esti-325 mates or other sort of optimizations.Corollary 2. OBJCREATION-PLANEX is semi-decidable.For Corollary 2, note that although the state space is infinite, we are searching for a finitely long path in a finitely branching state space. For such scenarios, breadthfirst search (i.e., Procedure 1 using a FIFO open-list) is semicomplete because it will consider all (finitely many) paths of length k before considering any longer path. Hence, if a solution exists, it will be found after a finite computation Corollary 3. OBJCREATION-PLANLEN is decidable.To see this, we can again run breadth-first search, keeping track of the length of generated paths and rejecting the input as soon as we reach the given length bound.But there are still some details missing for a practical implementation of the above procedure. For example, we would like to quickly generate successor states, and also to define how to come up with fresh objects during object creation.To generate successor states, we need to find all assignment functions leading to applicable actions. Let s be a state and A an action schema. We can find all ground actions A s,σ1 , . . . , A s,σm by computing all σ i such that s, σ i |= pre(A). As states are finite, solving this problem is decidable. Free variables occurring in eff(A) but not in pre(A) can take any possible value, so we consider all possible assignments.Now assume that A has an object creation effect ⊕v : e, where e is an effect. At a given state s, we need to instantiate v to a fresh object that is not in U s . There are infinitely many ways to do so. The new object could be assigned to a natural number, or it could be an arbitrarily long sequence of characters, like aaaa, or anything else that is not in U s . But all these choices are just names assigned to the new object, and they do not influence the semantics of the successor state. In other words, they are just syntactic. Any such choice of name is isomorphic to the other ones. Choosing one welldefined method to come up with names is sufficient. We call a function that chooses the next fresh object in a given state a choice function.One of the simplest ways is to map every object o ∈ U s0 to an index id(o) = i for i ∈ N. Whenever we need a fresh object in a state s, we compute the minimum j ∈ N not assigned to any object in U s . We then introduce a new object named j and set id(j) = j. In other words, new objects are identified by the minimum non-used index in the current state. 8 Removing an object o unassigns id(o). A successor state keeps the same mapping as its parent state, besides the newly created or removed objects. For example, if our state s has three objects, we can map them to indices 1, 2, and 3. If the action A s,σ has an object-creation effect, this object can be assigned to index 4. The successor state succ(s, σ, A) still maps the three original objects to 1, 2, and 3, but it also maps the fourth object to 4.This bring us to yet another efficiency concern. Assume that we have a state s and two actions A and B. Let us also assume that A and B have an always satisfiable precondition. Moreover, eff(A) := (⊕v : P (v)), while eff(B) := (⊕v : Q(v)). The sequences ⟨A s,σ1 , B succ(s,σ1,A),σ2 ⟩ and ⟨B s,σ2 , A succ(s,σ2,B),σ1 ⟩ lead to two different states, but both are semantically equivalent: they only differ by the names used to identify the created objects. The two resulting states are isomorphic, and keeping only one of them is sufficient.State-space search algorithms usually rely on duplicate state detection, but this is not enough here because we want to detect all isomorphic states. Unfortunately, no polynomial-time algorithms are known for this (Grohe and Schweitzer 2020) .This problem is similar to the one faced by orbit space search algorithms (Alkhazraji et al. 2014; Domshlak, Katz, and Shleyfman 2015) . In orbit space, search nodes correspond to equivalence classes of states, instead of individual states. Two states are considered equivalent if they are detected to be symmetric. This symmetry detection is usually done based on canonical states.Ideally, a canonical state would be a unique representative of an equivalence class. During search, it is sufficient to store the canonical state for each encountered equivalence class and then use standard duplicate elimination techniques. The efficiency of canonical state computation is a crucial part of the performance of orbit space search planners. In practical implementations, computing true canonical representatives is considered to be too expensive, and therefore canonical states are approximated by a greedy procedure. This leads to some lost opportunities for detecting equivalence, but does not affect correctness.In planning with object creation, one would expect symmetrical states to occur often, as the different names given to new objects are another source of symmetry. We can tackle this problem as in orbit search, by using (exact or approximate) canonical states for each equivalence class.Example 6. Let us say we have two states s 1 and s 2 , and a, b, c and d are objects created during search:U s1 = {a, b, c}, P s1 = {P (a), P (c), Q(a), Q(b)}, U s2 = {b, c, d}, P s2 = {P (b), P (d), Q(b), Q(c)}.These states are equivalent via the object mapping {a → b, b → c, c → d}. In this case, this would be already detected by a very simple algorithm approximating canonical representatives by mapping each object to its index in a lexicographical order: for s 1 we would map {a → 1, b → 2, c → 3}, and in s 2 we would map {b → 1, c → 2, d → 3}. In both cases, we would end up with the same state s ′ , showing equivalence:U s ′ = {1, 2, 3}, P s ′ = {P (1), P (3), Q(1), Q(2)}.Inspired by the work on bounded situation calculus (De Giacomo, Lespérance, and Patrizi 2016), we consider the case in which the number of objects in U s , for any state s, is bounded by a fixed constant k. We say that such a task is 420 state-bounded, with bounding constant k.There are several sufficient conditions to guarantee stateboundedness (De Giacomo, Lespérance, and Patrizi 2016). We refer the reader to the original paper for details. This case is decidable by direct reduction to situation calculus (e.g., Claßen, Hu, and Lakemeyer 2007) using the results in De Giacomo, Lespérance, and Patrizi (2016) . Let us first define a recycling choice function: a choice function is 430 said recycling if, after an object is removed from a state s, the object can be re-introduced by an object creation effect in some state reachable from s. The choice function described above assigning every object to a natural number is recycling. Intuitively, if we use a recycling choice function we create only finitely many new objects. Hence, Procedure 1 considers only finitely many states, and it is thus decidable. But note that the state-space of the task is still infinite, although each state has bounded size.We extended the Powerlifted planner (Corrêa et al. 2020) to allow object creation effects. The source code of our implementation and our benchmarks will be publicly available.Powerlifted is a heuristic search planner that only supports STRIPS (Fikes and Nilsson 1971) extended with types, so we only implemented a STRIPS fragment of our formalism. We consider the following as a STRIPS task with object creation: preconditions are restricted to conjunctive formulas over positive atoms; an effect can only be a simple, conjunctive, or object-creation effect; the goal is a conjunctive formula. Note that Theorem 1 uses this fragment in the proof, so plan existence for STRIPS tasks with object creation has the same decidability results as the complete formalism.In this fragment, the algorithm by Corrêa et al. ( 2020) is still sufficient to compute the applicable ground actions. As preconditions are conjunctions of positive atoms, the precondition of an action A can be considered as a conjunctive query (Ullman 1989) . If we answer this query over a state s, every tuple in the answer corresponds to a function σ mapping free(A) to U s such that A s,σ is applicable. Corrêa et al. (2020) exploit structural properties of these queries (i.e., acyclicity) to compute successor states efficiently.We use the choice function mapping objects to natural numbers as described above (i.e., a new object o is mapped to the smallest natural number j such that there is no o ′ where id(o ′ ) = j). We did not implement any isomorphism check between states, and we rely on syntactic duplicate detection. We leave more sophisticated techniques based on (approximate) canonical representatives as future work.To improve the search, we modified the lifted width-based search (Lipovetzky and Geffner 2012, 2017) implemented by Corrêa and Seipp (2022) . Best-first width search (BFWS) (Lipovetzky and Geffner 2017) uses the novelty measure to choose which states to expand. The novelty w(s) of a state s is the size of the smallest non-empty set of ground atoms Q such that s is the first state visited where s |= Q. For example, if s is the first state containing atom a, then w(s) = 1. In contrast, if there is no single atom that first occurred in s but there is a subset {a, b} that first occurred together in s, then w(s) = 2. A more informed version of novelty is w f (s), which is computed only considering tuples in states s ′ where f (s) = f (s ′ ). We implemented BFWS with w #G (s), where #G is the number of atoms in the goal satisfied in s. We only compute w #G up to pairs. If there is no new pair in s, then w #G (s) = 3.Novelty measures do not seem to fit with object creation: introducing a fresh object makes the state have a novelty of 1, so BFWS always prioritizes states that create objects. In domains where the number of created of objects is unbounded, this could lead to an infinite sequence of actions. To solve this, our implementation only consider tuples of atoms that do not mention new objects. In other words, we compute the novelty of a state over those tuples that only mention objects in U s0 . However, this has the completely opposite effect: new objects do not account for the novelty of a state, so they do not add any information to the BFWS. What can happen in this case is that BFWS finds plans creating the minimum number of objects necessary. As we will see in our experimental results next, this does indeed happen often. Yet, this modified BFWS still improves our planner. benchmarks. Two of them are based on previously existing domains that encode object creation by listing all possible objects at the initial state and using auxiliary predicates to simulate object creation. This made it necessary in the original PDDL to introduce an arbitrary on the number of objects that can be created and then experiment with different bounds to deal with tasks that are wrongly considered unsolvable because the number of objects is too low.For each domain, we have two versions: one using our new PDDL extension, and one where all potential objects are declared in the initial state. The version using the new syntax is called the extended version, while the other is called standard version. This comparison is imperfect because only the extended version captures the underlying problem faithfully, but it allows us to compare our planner using object creation with existing planning systems.Cluster Management In this new domain, we must produce a set of files. These files are produced by executing scripts on certain inputs. For example, executing script S with input I 1 might output O 1 , and executing S with I 2 might output O 2 . Our benchmark contains instances with up to 100 files and 20 different scripts. We also have a cluster with multiple CPUs, where we can load and execute these scripts with the corresponding files. The actions are to load a file or script in a CPU, to execute a script, to save a file into 530 memory, and to add a new CPU to the cluster. So if a script must be used several times (with different inputs to produce different outputs), it might be preferable to load it only once in one of the CPUs and leave it there. The problem in this domain is to find the optimal amount of CPUs to obtain a 535 certain set of goal files as quick as possible. We can add new CPUs to our cluster using an action that creates a new CPU object. In the standard version, we pre-declare 5 CPUs.Commutative Rings This domain was introduced by Petrov and Muise (2023) . A task in this domain is a statement in elementary algebra. A plan is a proof for this statement. The domain focuses on tasks related to commutative rings. One task, for example, is to prove that for all commutative rings R, a × 0 = 0 for every a ∈ R. Action schemas represent the axioms of commutative rings, equality operations, definitions of products, sums, and inverses. Object creation can be used to model existential axioms and build complex expressions. For instance, given a commutative ring R, for any a, b ∈ R there exists an element a+b ∈ R. So we can construct a new object c and define c = a+b to be used later. In the original domain, Petrov and Muise (2023) introduce a fixed number of undeclared variables at the initial state. However, this makes the task harder to ground, while also bounding the number of proofs the planner can explore. We used the original tasks of this domain, but compiled away conditional effects, which are not supported by Powerlifted.Logistics Company This is a new domain, and it is similar to the running example in our paper. We have a set of connected locations and a set of packages that must be delivered to specific locations. Our company has headquarters in a few locations, and we can buy trucks that appear at one of these headquarters. Actions are to move the truck, (un)load packages, and buy a new truck. The challenge is to find a good balance between how many trucks to buy to deliver all packages efficiently. While all tasks are solvable with one single truck, it might be that using multiple trucks decreases the plan length significantly. In our instances, the number of locations varies between 3 and 1 000, the number of packages from 1 to 100, and the number of headquarters from 1 to 20. In the standard version, the number of declared trucks at the initial state is twice the number of headquarters in the task.Settlers This domain is based on the Settlers domain used in the IPC 2002. (Long and Fox 2003) . The domain focuses on resource management. Products and factories must be built from raw materials and used in the manufacture or transportation of further materials. The objective is to construct a variety of building types at various specified locations. The original domain is numeric: the quantity of resources at each location is defined by numeric fluents. But these fluents are discrete and their maximum values are always bounded, so one can emulate them using predicates to encode a successor relation over the natural numbers. Long and Fox (2003) mention that this domain highlights the necessity of object creation during plan execution. In the standard version, all objects had to be declared in advance, which made grounding harder and made the modeling more convoluted. We removed "maritime" objectswharfs, docks, ships -in our version, because the original instances were too challenging for all planners.We ran Powerlifted on both versions of our benchmarks (standard and extended versions). Powerlifted using the standard versions is denoted as PWL, and using the extended versions as PWL ++ . For each, we tested two configurations: a breadth-first search (BFS), and the BFWS as explained in the previous section. These are not the best configurations of Powerlifted (e.g., Corrêa et al. 2022) , but are the bestperforming configurations that we could extend to support object creation within the scope of this paper. 9Table 1 shows the coverage of all methods in our benchmark. PWL ++ outperforms PWL when using BFWS, but it has lower coverage with BFS. The BFWS implementation does not consider tuples considering newly created objects. This can be an issue with the extended versions, as only some objects are considered when evaluating the novelty of a state. But this is not always problematic. In the Logistics 605 Company domain, for example, using one truck is already enough to solve the task so BFWS does not favor the creation of new trucks. This increases coverage in the extended version but also impacts plan quality. In some cases, the optimal plan had length 10, but PWL ++ with BFWS only found 610 plans with more than 100 steps. With respect to runtime, PWL ++ and PWL are comparable in both configurations. With respect to memory, there are larger differences depending on the domain. In a few instances of the Commutative Ring, PWL ++ used up to 10 times more more memory than PWL. In this domain, some of the original instances in the standard version do not use any undeclared variables. In the extended version, the planner is not aware that they are not needed, so they are introduced multiple times. This blows up the size of the state space. To solve this problem it is crucial to have heuristic estimates that can better decide when more objects are needed.Powerlifted has some advantages when solving tasks that are hard to ground, but its search capabilities are not on par with ground planners. To compare PWL ++ with a state-ofthe-art heuristic search planner, we also ran Fast Downward (Helmert 2006) on the standard versions. To keep the results comparable, we used the blind search and we implemented BFWS in Fast Downward. We denote Fast Downward as FD in the rest. Results are also shown in Table 1 .When using blind search, FD is significantly better than PWL ++ and somewhat better than PWL. This is consistent with previous results (Corrêa et al. 2020) . For larger problems, grounding becomes a challenge (Corrêa et al. 2023 ). This can be seen when comparing FD with BFWS and 635 PWL ++ with BFWS. Although the coverage of FD increases by almost 50% when switching from blind search to BFWS, it is still worse than PWL ++ . Only in the Cluster Management domain, FD outperforms PWL ++ . This is also the only domain where all tasks can be grounded within seconds, 640 as the number of ground actions is low (a few thousands) even declaring all objects in advance. In the Logistics Company domain, where several of the declared objects are not necessary (although helpful) grounding does become a major bottleneck. In this domain, FD has worse coverage than 645 PWL ++ . The same happens in the Commutative Ring do-main, even though in this domain we have at most one undeclared variable per task -but in the grounding several actions use this object. As noted by Petrov and Muise (2023) , adding one single undeclared variable to the initial state is already enough to make the grounding much harder.Object creation has been considered several times as an important feature to large scale planning systems (Long and Fox 2003; Petrov and Muise 2023) . So far, all methods trying to solve this problem used compilations. Fuentetaja and de la Rosa (2016) present an automatic compilation of "irrelevant objects" (i.e., objects whose name do not specifically matter) into counters. While this is all right in certain domains, it has inherent limitations. Two irrelevant objects can only compiled into the same counter if they are fungible and do not differ their properties during the plan. In our logistics company example this is impossible, as trucks do differ (e.g., each truck can be at a different location). Counters also must be first compiled into relations, which forces them to be bounded. Similar compilations have been proposed to automatically encode indistinguishable objects into counters represented by numeric variables (Riddle et al. 2016) .In situation calculus (McCarthy 1963) , infinitely many objects have already been considered (cf. Reiter 2001) although mostly in theory. In comparison to our work, the most relevant result in situation calculus is the work by De Giacomo, Lespérance, and Patrizi (2016) . They show that bounded situation calculus -when the number of objects in tuples is bounded -is decidable. As aforementioned, this is essentially the same as planning with object creation for tasks with bounded number of objects.Lifted planners were dominant in the 1990s (Penberthy and Weld 1992; Younes and Simmons 2003) . Although progress in this area was slow during the early 2000s, recent work showed its usefulness in hard-to-ground benchmarks (Corrêa et al. 2021; Lauer et al. 2021; Wichlacz, Höller, and Hoffmann 2022; Höller and Behnke 2022; Shaik and van de Pol 2022; Horčík, Fišer, and Torralba 2022) . We used the Powerlifted planner, but other lifted heuristic search planners should be capable of dealing with object creation (e.g., Horčík and Fišer 2021) .We formalized an extension of classical planning that allows for object creation and removal during plan execution, called "planning with object creation" for short. In our formalism, this creation/removal happens as special kind of action effects. In general, planning with object creation is semi-decidable; when states are bound, however, the problem becomes decidable. We also implemented support for object creation/removal in the Powerlifted planner (Corrêa et al. 2020) . In our experimental results, support for this extension caused no harm to the planner performance. It was also on par with state-of-the-art classical planners (Helmert 2006) . To further scale performance, one could use more informed heuristic estimates for tasks with object creation.We will discuss later how constant symbols can be emulated, so not allowing them syntactically is no loss of generality.Interpretations in the context of classical planning are always finite.Note that for atoms a = P (v1, . . . , vn), σ(a) is not formally an atom because σ(vi) is not a term. We can think of σ(a) as the pair ⟨P, ⟨σ(v1), . . . , σ(vn)⟩⟩ consisting of a predicate symbol and a tuple of objects.This is the only place where we use our notation that s, σ ̸ |= P (v1, • • • , vn) if σ(vi) ̸ ∈ U s for some i.A fresh object is an object that is not in U s . We explain later a simple way on how to choose new. The supplementary material also contains a more thorough discussion on this topic, and how to guarantee uniqueness.In PDDL, parameters can be typed. We also allow for this in our extension, but we do not define in our formalism for simplicity.Again, using atoms to write {P s 0 } for simplicity.This requires keeping track of the id-value for created objects as we process the effect of an action. For a choice function where this is not necessary, see the supplementary material.It would be interesting to extend delete-relaxation heuristics as implemented in Powerlifted to object creation, but this is not a simple task and requires developing its own theory. 
 
 Appendix:  


Decision: All reviewers find the topic interesting, and the paper's presentation clear. As such, it would have some value to the planning community. However, it's contribution is somewhat limited: A proof of undecidability nearly identical to that in this paper was published already in 2009 ("Message-Based Web Service Composition, Integrity Constraints and Planning Under Uncertainty: A New Connection", by Hoffmann, Bertoli, Helmert and Pistore, JAIR vol. 35, 2009). The formalization presented in this paper is slightly different, but it does not spell out the relation with previous formalizations. The algorithm for planning with object creation is a basic adaptation of lifted planning, leaving important aspects for future development. In summary, the recommendation is to accept the paper, but this is a borderline recommendation.

Should the paper not be accepted into the main conference, it would make a good contribution to one of the ICAPS workshops, such as HSDIP.

Reviews: review: strength_weakness: strength_weakness: Main one is that I see the contribution as quite moderate.

It is not specifically stated in the paper but it seems this work is for classical planning with negative and disjunctive preconditions and
forall and conditional effects, without action costs?. This should clearly stated. The implementation is for classical planning (strips planning with types).

The paper says nothing about how the order of different effects with creation/removal affects the action application. But with forall effects the order of effects is now relevant, and this does not seem to be considered by the "changes" function (conjunction of effects is formalized with unions). For instance, the next state for an action with the effects: (1) create truck t with p(t) (2) create a fact q for all trucks would be different if the effects are considered in the reverse order: (1) create a fact q for all trucks, (2) create truck with p(t).

Definition of successor state: formalization of P' is weird and it seems incorrect to me. With the current formalization it seems that P' is a set of objects instead of a set of object tuples. I imagine the authors want to say that the new object tuples in P' are restricted to those that contain objects that have not been remove, which is the same as removing from the previous state all facts concerning a removed objects.

Introducing dynamic creation/removal of objects in PDDL is rather straight-forward. The authors say that they not define types in the formalism for simplicity, but in PDDL is very easy to define a syntax for introducing new objects with types. I don't see any reason not to
include them in the paper.

Undecidablity results:  is there any relation with the following works?: 
The computational complexity of propositional STRIPS planning. T. Bylander. Artif. Intell. 1994.
Complexity, decidability and undecidability results for domain-independent planning. K. Erol, D.S. Nau, V.S. Sybrahmanian. Artif. Intell. 1995 

line 95: that a formula -> that a formula $\varphi$
line 100: s undefined. Replace it by $\mathcal{I}$ or define s
line 124: The goal is to have p1 at c2 (to move is an action)

-------------------
Post-rebuttal
-------------------
Thank you for your response.
Some previous works on planning for web service composition was mentioned in the discussion. Specifically, a JAIR 2009 paper Hoffmann, Bertoli, Helmert and Pistore contains a very similar undecidability proof.  This should be revised and cited.
questions: questions: 1. Can you comment on how the order of effects is considered here?
2. Can you clarify the issue with the successor generation?
3. Can the results be derived from the Turing Machine by Bylander 94? 
4. Can you include experiments on quality and expanded states?
strength_weakness: strength_weakness: - The paper itself, on a practical point of view, doesn't introduce anything regarding how to better solve planning with objects creation. The   "Overall Procedure in Practice" and "Implementation" section reuse some existing techniques and solvers to make it work with object creations. For me, this is not a big weakness, as stated in the strengths section, I believe this paper aims to introduce the paper from a theoretic point of view and I believe more work will come afterwards to push the envelope further. And for me, this is sufficient for accepting the paper. 
- I believe that Table 1 should also include the times and the memory, since you claim PWL++ to be more memory expensive.
- At line 631 you call B as "blind" while it is "breadth-first search" (although in A* they mean the same thing)

Typos:
- Third bullet point after line 170, it should be i \in \{1,2\}
- Line 228: "note" -> "not"
- Line 230: "an vehicle" -> "a vehicle"
- Line 590 should be another paragraph
questions: questions: 1) For me, it was confusing Theorem 1 stating that "OBJCREATION-PLANEX is undecidable" and Corollary 2 stating "OBJCREATION-PLANEX is semi-decidable". How can they be both?
2) At line 360 you state that "we compute the minimum j ∈ N not assigned to any object in Us". This computation is pointless, right? It can be simply stored somewhere and retrieved. Computing the minimum makes it look like a hard task, but for me, it should be a simple look-up table.
3) Why do you only deal with object-creation in the experimental analysis and not with object-removal?
4) In the cluster management domain, at line 535 you state the need to find "the optimal amount of CPUs". The word "optimal" here is not the right choice, since you do not make optimal planning, right?
strength_weakness: strength_weakness: 1.	The paper's contributions could benefit from a clearer structure.
2.	The experimental evaluation of the approach has room for further development and expansion.
3.	The experimental evaluation of the approach might benefit from streamlining domain presentations while focusing more on illustrating the quality of solution plans or compared the proposed approach with existing compilation approaches. Additionally, expanding the test set to include more domains could enrich the evaluation.
4.	While the related work section touches upon plan generation with object creation, it appears relatively brief and somewhat incomplete in capturing all directly relevant literature in this domain. It would have been interesting to have more details on compilation approaches such as “Introducing Dynamic Object Creation to PDDL Planning ICAPS 2019 Workshop WIPC.
questions: questions: Q1 : Why differentiate between objects and constants? Both concepts stem from PDDL, yet from a theoretical and logical standpoint, they essentially represent constants. Focusing solely on constants might offer greater clarity in discussions.
Q2: In the evaluation, two versions of each domain were used: one based on the introduced formalism allowing object creation and removal, and the other where all potential objects were declared upfront. The selection process for potential objects in the latter version might not have been explicitly detailed in the paper.
Typically, the set of potential objects in the second version (where all potential objects are declared) involves identifying the minimal set of objects needed to find a solution. This set could include objects required by the actions, initial state, and goal specifications within the domain.
In some cases, additional predicates might be introduced, similar to the original Settlers benchmark proposed by Long, to simulate or encompass potential objects that might be dynamically created or removed in the formalism allowing object manipulation.
However, the paper might benefit from providing a more explicit and detailed explanation of how the second version of the domains, with all potential objects declared, was produced. This could involve specifying the criteria used for object selection, potential predicate additions, and any assumptions made to simulate the object set.
Adding such details would offer transparency and clarity, ensuring a better understanding of the process used to create the comparison versions of the domains.
Could you detail this point?
Q3: Why just consider coverage criteria in evaluation and not plan quality ? 
Q4: Why not compared you approach with compilation ones ? Is there any reason why this comparison cannot be made?