Literature
Display
← All papers

What Planning Problems Can A Relational Neural Network Solve?

Jiayuan Mao · Tomás Lozano-Pérez · Joshua B. Tenenbaum · Leslie Pack Kaelbling

· NeurIPS 2023 ↗

Reasoning15 min text · CondensedOriginal paper ↗
Contents

At a glance

When can one compact relational neural policy solve a planning problem across different numbers of objects? This paper constructs policies from goal-regression search and relates their required depth and relation arity to strong optimal serializability (SOS) width. Small fixed width permits a fixed breadth of relations; planning depth can still grow with the problem. A suitable regression-rule selector can reduce the required computation further.

These are representation and compilation results for discrete, deterministic planning classes. They do not guarantee that training discovers the constructed policy, that a fixed architecture solves general planning, or that all practical tasks have small width. Experiments illustrate the depth dependence in three small domains.

1 Introduction

A policy shared across instances needs to handle a varying number of objects while preserving the reasoning needed to choose actions. The analysis connects classical planning, regression search, and relational circuits instead of treating network size as an arbitrary hyperparameter. General propositional planning remains PSPACE-complete (Bylander, 1994); restricted domain and goal classes can nevertheless have compact policies.

The central distinction is between breadth—the maximum arity of a relation represented by the network—and depth, the number of computational layers per policy decision. Breadth is not the ordinary hidden-channel width, and bounded arity does not mean a constant total number of tensor entries as the object count grows.

Refer to caption
Figure 1: (a) Illustration of the Blocks World domain that we will be using as the main example. (b) The action schema definition in Blocks World. clear​(x)\textit{clear}(x) means there is no object on xx. (c) A backward search tree for solving the goal clear​(B)\textit{clear}(\text{B}). (d) A serialized goal regression search tree for the same goal. (e) The form of a goal-conditioned policy for this problem.

2 Preliminaries: Planning Domain and Problem

The setting is classical deterministic planning over a fixed set of objects and Boolean ground atoms. A state lists true atoms; a STRIPS action has preconditions plus add and delete effects. The retained transition formula specifies applicability and the next state. A goal-conditioned policy repeatedly chooses actions until the goal holds.

The analysis primarily uses a single-atom goal. A conjunction can be compiled into a goal-achieve action, but its preconditions can increase the relevant width. Object creation, uncertain dynamics, and continuous control are outside these formal assumptions.

Equation∀s.∀a.pre​(a)⊆s⟹(𝒯⁡(s,a)=s∪eff+​(a)∖eff−​(a)).\forall s.\forall a.\textit{pre}(a)\subseteq s\implies\left({\mathcal{T}}(s,a)=s\cup\textit{eff}_{+}(a)\setminus\textit{eff}_{-}(a)\right).

3 Goal Regression Search and Width

Plain backward search starts from the desired goal set, chooses a final action that achieves a goal without deleting another, and regresses to its preconditions. A goal stack prevents recursive cycles. Algorithm 1 retains the exact procedure. Its cost depends on both planning horizon and intermediate goal-set size and is exponential in the general case.

function bwd(s0s_{0}, 𝒜{\mathcal{A}}, goal_set)
  if goal_set⊆s0\textit{goal\_set}\subseteq s_{0} then return empty_list()   
  possible_t = empty_set()
  for a∈{a∈𝒜∣goal_set∩eff−​(a)=∅​and​goal_set∩eff+≠∅}a\in\{a\in{\mathcal{A}}\mid\textit{goal\_set}\cap\textit{eff}_{-}(a)=\emptyset~\textbf{and}~\textit{goal\_set}\cap\textit{eff}_{+}\neq\emptyset\} do
   new_goals=goal_set∪pre​(a)∖eff+​(a)\textit{new\_goals}=\textit{goal\_set}\cup\textit{pre}(a)\setminus\textit{eff}_{+}(a)
   if new_goals∈goal stack\textit{new\_goals}\in\textit{goal stack} then continue    
   π\pi = bwd(s0s_{0}, new_goals)
   if π≠⟂\pi\neq\perp then
      possible_t.add​(π+{a})\textit{possible\_t}.\textit{add}(\pi+\{a\})      
  return shortest path in possible_t

Algorithm 1 Plain backward search.
function s-grs(s0s_{0}, ℛ{\mathcal{R}}, g, cons)
  if g∈s0\textit{g}\in s_{0} then return (s0)(s_{0})   
  possible_t = empty_set()
  for r∈{r∈ℛ∣cons∩eff−(action(r))=∅r\in\{r\in{\mathcal{R}}\mid\textit{cons}\cap\textit{eff}_{-}(\textit{action}(r))=\emptyset and goal(r)=g}\textit{goal}(r)=g\} do
   p1,p2,⋯,pkp_{1},p_{2},\cdots,p_{k} = subgoals(r)
   if ∃pi\exists p_{i} s.t. pi∈goal stackp_{i}\in\textit{goal stack} then continue    
   for ii in 1,2,⋯,k1,2,\cdots,k do
      n​e​w​_​cnew\_c = cons∪{p1,⋯,pi−1}\textit{cons}\cup\{p_{1},\cdots,p_{i-1}\}
      πi\pi_{i} = s-grs(si−1s_{i-1}, pip_{i}, new_c)
      if πi==⟂\pi_{i}==\perp then break       
      si=𝒯⁡(si−1,πi​[−1])s_{i}={\mathcal{T}}(s_{i-1},\pi_{i}[-1])    
   if πk≠⟂\pi_{k}\neq\perp then
      possible_t.add​(π1+…+πk+{a})\textit{possible\_t}.\textit{add}(\pi_{1}+\ldots+\pi_{k}+\{a\})      
  return shortest path in possible_t

Algorithm 2 Serialized goal regression search.

3.1 Serialized Goal Regression Search

Serialized goal regression search (S-GRS) commits to an order for achieving an action’s preconditions. When solving the next precondition, it preserves external constraints and previously achieved preconditions; an admissible final action must not delete those constraints. The retained rules show this explicitly for clearing a block.

Algorithm 2 keeps a shortest local subplan. In general this loses completeness or optimality because different ways to achieve a subgoal can leave different states. Appendix A.1’s exhaustive variant tracks those alternatives; the faster main algorithm has guarantees only under the stated serializability conditions.

Equationsgc⇜p1c,p2c∪{p1},⋯,pkc∪{p1,⋯pk−1}∥ag^{c}\leftsquigarrow p_{1}^{c},p_{2}^{c\cup\{p_{1}\}},\cdots,p_{k}^{c\cup\{p_{1},\cdots p_{k-1}\}}~\|~aclear​(B)∅⇜on​(A,B),clear​(A){on​(A,B)},handsfree​(){on​(A,B),clear​(A)}|unstack​(A,B)\textit{clear}(\text{B})^{\emptyset}\leftsquigarrow\textit{on}(\text{A},\text{B}),\textit{clear}(\text{A})^{\{\textit{on}(\text{A},\text{B})\}},\textit{handsfree}(\text{})^{\{\textit{on}(\text{A},\text{B}),\textit{clear}(\text{A})\}}~\|~\textit{unstack}(\text{A},\text{B})

3.2 Serialization of Goal Regression Rules

Optimal serializability requires optimal prefix plans to extend through each ordered precondition and finally to an optimal plan for the goal. The exact definition and Theorem 3.1 are retained. The completeness claim applies to goals reachable through the optimally serializable rules, not arbitrary action orderings or arbitrary planning instances.

Definition 3.1 (Optimal serializability).

A goal regression rule gcons⇜p1,⋯,pk|ag^{\textit{cons}}\leftsquigarrow p_{1},\cdots,p_{k}~\|~a is optimally serializable w.r.t. a state ss if and only if, for all steps ii, if ∀π<i∈OptSearch​(s,p1∧⋯∧pi−1,cons)\forall\pi_{<i}\in\textit{OptSearch}(\textit{s},p_{1}\wedge\cdots\wedge p_{i-1},\textit{cons}) and ∀πi∈OptSearch​(𝒯⁡(s,π<i),pi,cons∪{p1,⋯,pi−1})\forall\pi_{i}\in\textit{OptSearch}({\mathcal{T}}(s,\pi_{<i}),p_{i},\textit{cons}\cup\{p_{1},\cdots,p_{i-1}\}) then π<i⊕πi∈OptSearch​(s,p1∧⋯∧pi,cons)\pi_{<i}\oplus\pi_{i}\in\textit{OptSearch}(\textit{s},p_{1}\wedge\cdots\wedge p_{i},\textit{cons}). Furthermore, ∀π∈OptSearch​(s,p1∧⋯∧pk,cons)\forall\pi\in\textit{OptSearch}(\textit{s},p_{1}\wedge\cdots\wedge p_{k},\textit{cons}), π⊕a∈OptSearch​(s,g,cons)\pi\oplus a\in\textit{OptSearch}(\textit{s},g,\textit{cons})§§ § a⊕ba\oplus b denotes concatenation of sequences..

Theorem 3.1.

For any goal g∈OSG​(s0)g\in\textit{OSG}(s_{0}), S-GRS is optimal and complete. See proof in Appendix A.2.

3.3 Width of Search Problems

Generalized rules explicitly preserve only selected earlier preconditions. Their width counts those retained constraints plus the external constraint set. Strong optimal serializability adds a crucial requirement: any optimal plan under the selected constraints must still achieve the full relevant prefix. Small syntactic width alone is insufficient.

For SOS width k, Theorem 3.2 bounds search by O(N^(k+1)), where N counts ground atoms, suppressing polynomial action-enumeration factors. Theorem 3.3 connects SOS width k to forward width at most k + 1 and iterated-width search. This is an upper bound; the two widths need not be equal.

Definition 3.2 (Generalized regression rules).

A generalized, optimally-serializable regression rule is gc⇜p1c∪c1,p2c∪c2,⋯,pkc∪ck|ag^{c}\leftsquigarrow p_{1}^{c\cup c_{1}},p_{2}^{c\cup c_{2}},\cdots,p_{k}^{c\cup c_{k}}~\|~a, where ci⊆{p1,p2,⋯,pi−1}c_{i}\subseteq\{p_{1},p_{2},\cdots,p_{i-1}\}. Its width is |c|+max⁡{|c1|,⋯,|ck|}|c|+\max\{|c_{1}|,\cdots,|c_{k}|\}.

Definition 3.3 (Strong optimally-serializable (SOS) width of regression rules).

A generalized regression rule has strong optimally-serializable width kk w.r.t. state ss if (a) it is optimally serializable, (b) its width is kk, and, (c) ∀c​OptSearch​(s,pi∪ci∪c,∅)⊆OptSearch​(s,{p1,⋯,pi}∪c,∅)\forall c\textit{OptSearch}(s,p_{i}\cup c_{i}\cup c,\emptyset)\subseteq\textit{OptSearch}(s,\{p_{1},\cdots,p_{i}\}\cup c,\emptyset).

Definition 3.4 (SOS width of problems).

A planning problem P=⟨𝒮,s0,g,𝒜,𝒯⟩P=\langle{\mathcal{S}},s_{0},g,{\mathcal{A}},{\mathcal{T}}\rangle has strong optimally-serializable width kk if there exists a set of strong optimally-serializable width kk rules ℛ{\mathcal{R}} w.r.t. s0s_{0}, such that S-GRS can solve PP using only rules in ℛ{\mathcal{R}}.

Theorem 3.2.

If a problem PP is of SOS width kk, it can be solved in time O⁡(Nk+1)O(N^{k+1}) with s-grs, where NN is the number of atoms. Here we have omitted polynomials related to enumerating all possible actions and their serializations (which are polynomial w.r.t. the number of objects in 𝒰{\mathcal{U}}).

Theorem 3.3.

Any planning problem that has SOS-width kk has a forward width of at most k+1k+1 and, hence, can be solved by the algorithm IW​(k+1)\textit{IW}(k+1). See the full proof in Appendix A.6.

4 Policy Realization

A relational network receives the state and goal as predicates over objects and predicts an action. Shared parameters allow different object counts, while higher-arity tensors can still be large. The paper gives two constructions: unroll general search, or use a state-dependent rule selector to avoid much of that search.

4.1 Relational Neural Network Background

A RelNN[D, B] has D layers and maximum relation arity B. Hidden feature dimension is assumed bounded, although the number of object tuples grows with instance size. Under this model, bounded-variable first-order logic with counting characterizes representable computations, following Luo et al. and the related logical expressivity results cited in Lemma 4.1.

The lemma’s lower bound separates families of logical functions requiring B versus B − 1 variables. It does not by itself prove that every fixed-breadth network fails on every difficult planning domain.

Lemma 4.1 (Logical expressiveness of relational neural networks (Luo et al., 2022; Cai et al., 1992)).

Let FOCB denote a fragment of first-order logic with at most BB variables, extended with counting quantifiers of the form ∃≥nϕ\exists^{\geq_{n}}\phi, which state that there are at least nn nodes satisfying formula ϕ\phi.

  • •

    (Upper Bound) Any function ff in FOCB can be realized by RelNN​[D,B]\textit{RelNN}[D,B] for some DD.

  • •

    (Lower Bound) There exists a function ff in FOCB such that for all DD, ff cannot be realized by RelNN​[D,B−1]\textit{RelNN}[D,B-1].

Original figure
Figure 2: The input and output of a relational neural network (RelNN) policy.

4.2 Compilation of BWD and S-GRS

Unrolling backward search gives depth O(T) and breadth β·k_BWD, where T is the optimal planning horizon, β the maximum predicate arity, and k_BWD the largest regressed goal-set size. The SOS construction reduces breadth to (k + 1)β while retaining O(T) depth.

Thus a domain with constant SOS width can have finite breadth even when the straightforward backward-search encoding does not. Depth may still be unbounded or even exponential in the object count through T. These are constructive upper bounds, not efficient training guarantees.

Theorem 4.1 (Compilation of BWD).

Given a planning problem PP, let T be the length of the optimal trajectory (the planning horizon), kBWDk_{\text{BWD}} be the maximum number of atoms in the goal set in bwd, and β\beta be the maximum arity of atoms in the domain. The backward search algorithm bwd can be compiled into a relational neural network in RelNN​[O⁡(T),β⋅kBWD]\textit{RelNN}[O(T),\beta\cdot k_{\text{BWD}}].

Theorem 4.2 (Compilation of S-GRS).

Given a planning problem PP of SOS width kk, let T be the length of the optimal trajectory, and β\beta be the maximum arity of atoms in the domain. The serialized goal regression search S-GRS can be compiled into a RelNN​[O​(T),(k+1)⋅β]\textit{RelNN}[O(T),(k+1)\cdot\beta], where k+1≤kBWDk+1\leq k_{\text{BWD}}. See Appendix B.2 for the full proof using a similar technique as in Theorem 4.1.

Refer to caption
Figure 3: State-dependent regression rule selector in the Blocks World domain. For brevity, we have omitted atoms in the constraint set. All rules listed above are applicable under any constraints.

4.3 Compilation of S-GRS with a Regression Rule Selector

A regression-rule selector uses the current state, goal, and constraints to choose an action, an ordering of its preconditions, and bindings for any free variables. In Blocks World, the block directly above the target selects the useful unstack rule. Resource-dependent free-variable choices can make such a selector much harder to express.

Given a selector, the compiled policy traces the first unsatisfied precondition until it reaches an executable action. The exact selector definition, serializability condition, theorem, and lifted policy rules are retained. Selector construction is not automatic: it may require domain knowledge or learning.

Definition 4.1 (RRS Serializability).

A regression rule selector is serializable if and only if the following condition holds for any state ss, any goal gg, and any constraint set. Consider the regression rule returned by select​(s,g,cons)⇜p1,p2,⋯,pk|a\textit{select}(s,g,\textit{cons})\leftsquigarrow p_{1},p_{2},\cdots,p_{k}~\|~a. If gg is achievable from ss, then it can be achieved via the concatenation of the following trajectories: a¯1=trregress​(s,p1,constraint)\overline{a}_{1}=\textit{tr}^{\textit{regress}}(s,p_{1},\textit{constraint}), a¯2=trregress​(𝒯⁡(s,a¯1),p2,constraint∪{p1})\overline{a}_{2}=\textit{tr}^{\textit{regress}}({\mathcal{T}}(s,\overline{a}_{1}),p_{2},\textit{constraint}\cup\{p_{1}\}), ⋯\cdots, a¯k\overline{a}_{k}, and {a}\{a\}.

Equationsgcons⇜if​ρ​(s,cons):p1cons,p2cons∪{p1},⋯,pmcons∪{p1,⋯,pm−1}|a,g^{\textit{cons}}\leftsquigarrow\text{if}~\rho(s,\textit{cons}):p_{1}^{\textit{cons}},p_{2}^{\textit{cons}\cup\{p_{1}\}},\cdots,p_{m}^{\textit{cons}\cup\{p_{1},\cdots,p_{m-1}\}}~\|~a,⟨args,ρ,pre,a,g,cons⟩\langle\textit{args},\rho,\textit{pre},a,g,\textit{cons}\rangleclear​(B)⇜on​(A,B),clear​(A),handsfree​()|unstack​(A,B)\textit{clear}(\text{B})\leftsquigarrow\textit{on}(\text{A},\text{B}),\textit{clear}(\text{A}),\textit{handsfree}(\text{})~\|~\textit{unstack}(\text{A},\text{B})

Compiling policy neural networks.

Theorem 4.3 gives depth O(d·D_r) and breadth max(B_r, β), with d the regression-tree depth and D_r/B_r the selector’s circuit requirements. The policy must follow a selector that actually yields a plan. A balanced regression tree can reduce depth relative to plan length, but a chain can still require linear depth; a logarithmic reduction is not universal.

Variable iterations of a recurrent layer can handle increasing depth. A derived predicate such as above(x, y) can also shorten inference, but it supplies additional reachability information. Such an encoding shortcut should not be confused with solving the same reasoning problem from the original immediate-neighbor predicates.

Theorem 4.3 (Compilation of S-GRS with a regression rule selector).

Given a regression rule selector select (i.e., the state-constraint condition function ρ\rho) that can be computed by a relational neural network in RelNN​[Dr,Br]\textit{RelNN}[D_{r},B_{r}], for any planning problem PP, if trselect​(s0,g,∅)≠⟂\textit{tr}^{\textit{select}}(s_{0},g,\emptyset)\neq\perp, letting dd be the depth of the regression tree, then there is a RelNN circuit for the problem in RelNN​[O⁡(d⋅Dr),max⁡(Br,β)]\textit{RelNN}[O(d\cdot D_{r}),\max(B_{r},\beta)], where β\beta is the maximum arity of predicates.

Equation
∀d.∀i<|pre|.\displaystyle\small\forall d.\forall i<|\textit{pre}|. (Goald=(g,cons))∧ρ⁡(s,cons)∧pre≤i∧¬prei+1⇒(Goald+1=(prei+1,cons∪pre≤i))\displaystyle\left(\textit{Goal}^{d}=(g,\textit{cons})\right)\wedge\rho(s,\textit{cons})\wedge\textit{pre}_{\leq i}\wedge\neg\textit{pre}_{i+1}\Rightarrow\left(\textit{Goal}^{d+1}=(\textit{pre}_{i+1},\textit{cons}\cup\textit{pre}_{\leq i})\right)
∀d.\displaystyle\forall d. (Goald=(g,cons))∧ρ⁡(s,cons)∧pre⇒a\displaystyle\left(\textit{Goal}^{d}=(g,\textit{cons})\right)\wedge\rho(s,\textit{cons})\wedge\textit{pre}\Rightarrow a

5 Problem Analysis and Results

The domain analysis and Table 1 concern single-atom goals. Blocks World, Logistics, Gripper, Rover, and Elevator have the stated constant-breadth constructions; most still need unbounded depth. Gripper’s constant-depth case assumes direct travel between rooms. The paper classifies Sokoban as unbounded and nonserializable under its analysis; the constructive upper-bound theorems alone are not a general neural-circuit lower-bound proof.

Experiments use Neural Logic Machines with hidden dimension 64, three random seeds, and standard errors. Assembly3 requires selecting a compatible A–B–C chain. With training on ten objects, breadth-two/depth-two networks achieve 100% at 10, 30, and 50 objects; depth one falls from 20% to 2% and 0%.

In the generated Logistics graphs, depth three scores 100%, 30%, and 23%, while depth n/5 + 1 scores 100% at all three sizes. That adaptive depth is manually chosen for the graph generator. For BlocksWorld-Clear, both policies succeed, but depth n/10 + 3 yields average plans of 2.5, 3.1, and 3.5 steps versus 2.9, 10.2, and 15.7 for fixed depth three. Success alone therefore hides a substantial planning-efficiency difference.

Problem
Constant
Breadth?
Depth
BlocksWorld ✓ (k=1k=1) Unbounded
Logistics ✓ (k=0k=0) Unbounded
Gripper ✓ (k=0k=0) Constant
Rover ✓ (k=0k=0) Unbounded
Elevator ✓ (k=0k=0) Unbounded
Sokoban ✗ Unbounded
Table 1: Width and circuit complexity analysis for 6 problems widely used in AI planning communities. For problems with a constant circuit breadth, we also annotate their regression width kk. “Unbounded” depth means that the depth depends on the number of objects.
Task Model n=10 n=30 n=50
As3 RelNN​[1,2]\textit{RelNN}[1,2] 0.2±0.05 0.02±0.01 0.0±0.0
As3 RelNN​[2,2]\textit{RelNN}[2,2] 1.0±0.0 1.0±0.0 1.0±0.0
Log. RelNN​[3,2]\textit{RelNN}[3,2] 1.0±0.0 0.30±0.03 0.23±0.05
Log. RelNN​[f​(n),2]\textit{RelNN}[f(n),2] 1.0±0.0 1.0±0.0 1.0±0.0
BW RelNN​[3,2]\textit{RelNN}[3,2] 1.0 / 2.9±0.4 1.0 / 10.2±0.45 1.0 / 15.7±2.5
BW RelNN​[f​(n),2]\textit{RelNN}[f(n),2] 1.0 / 2.5±0.4 1.0 / 3.1±0.5 1.0 / 3.5±0.4
Table 2: Success rate of learned policies in different environments. For Assembly3 (As3) and Logistics (Log.), we show the success rate. For Blocks World (BW), we show the success rate / average solution length. We choose f⁡(n)=defn/5+1f(n)\mathrel{\raisebox{-1.1625pt}{$\overset{\text{\tiny def}}{=}$}}n/5+1 for Logistics and f⁡(n)=defn/10+3f(n)\mathrel{\raisebox{-1.1625pt}{$\overset{\text{\tiny def}}{=}$}}n/10+3 for BlocksWorld. In the notation of RelNN​[D,B]\textit{RelNN}[D,B], DD is the number of layers and BB is the maximum arity of edges.

6 Related Work and Conclusion

The work connects planning width and serialization with hierarchical task networks, hierarchical goal networks, relational expressivity, and algorithmic alignment. It explains why some object-centric problem classes admit compact policies and how constraints or long dependency chains can increase required computation.

The proofs establish existence and circuit bounds within discrete first-order domains. Learning the selector, handling resources, extending to continuous perception and action, and constructing universal multi-domain policies remain separate problems. The small experiments support the predicted depth dependence in their generators rather than general planning competence.

Acknowledgement.

The authors acknowledge reviewer feedback and support from ONR/MURI, the Center for Brains, Minds and Machines, NSF, AFOSR, ARO, MIT–IBM Watson AI Lab, MIT Quest for Intelligence, and Boston Dynamics AI Institute. The stated views are the authors’ own.

Appendix

The appendices give the complete search variant and proofs, circuit constructions, six-domain width analysis, and experimental implementation details.

Appendix A Proofs and Discussions for Search Complexity

Appendix A gives the exhaustive search variant, optimality and complexity arguments, the limits of serialization, and the connection to forward-width search.

A.1 Complete and Optimal Version of S-GRS

Algorithm 3 retains all possible trajectories and resulting states for each ordered subgoal. Allowing empty subtrajectories covers cases where an earlier plan has already achieved a later precondition. Restricting trajectories to have no loops ensures termination; Figure 4 illustrates the state branching.

This complete optimal variant can be slower than plain backward search. The authors count O(3^N) possible state/constraint combinations, versus O(2^N) in their backward-search comparison, because the maintained constraints must be a subset of the state. It is not the efficient fixed-width guarantee for Algorithm 2.

function grsopt(s0s_{0}, g, cons)
  if g∈s0g\in s_{0} then return (s0)(s_{0})   
  all_possible_t = empty_set()
  for rr ∈\in ℛ0{\mathcal{R}}_{0}: cons∩eff−​(action​(r))=∅∧goal​(r)=g\textit{cons}\cap\textit{eff}_{-}(\textit{action}(r))=\emptyset\wedge\textit{goal}(r)=\textit{g} do
   p1,p2,⋯,pkp_{1},p_{2},\cdots,p_{k} = subgoals(r)
   if ∃pi\exists p_{i} s.t. pi∈goal stackp_{i}\in\textit{goal stack} then
     continue    
   possible_t={∅}\textit{possible\_t}=\{\emptyset\}
   for ii in 1,2,⋯,k1,2,\cdots,k do
     next_possible_t = empty_set()
     for prefix_t in possible_t do
      imm_state = last_state​(prefix_t)\textit{last\_state}(\textit{prefix\_t})
      for nt ∈\in grsopt(imm_state, pip_{i}, cons∪{p1,⋯,pi−1}\textit{cons}\cup\{p_{1},\cdots,p_{i-1}\}) do
        next_possible_t=next_possible_t∪{prefix_t+nt}\textit{next\_possible\_t}=\textit{next\_possible\_t}\cup\{\textit{prefix\_t}+\textit{nt}\}            
     possible_t = next_possible_t    
   all_possible_t = all_possible_t ∪\cup {t+𝒯⁡(last_state​(t),action​(r))|t∈possible_t}\left\{t+{\mathcal{T}}\left(\textit{last\_state}(t),\textit{action}(r)\right)|~t\in\textit{possible\_t}\right\}   
  return all_possible_t
Algorithm 3 Serialized goal regression search with multiple optimal path tracking.

A.2 Proof for Theorem 3.1: S-GRS Optimality and Completeness

Theorem 3.1’s completeness follows from defining the target class through reachable optimally serializable rules. Optimality is proved by induction on subproblem distance: already satisfied goals need no actions, and optimal prefix extensions plus the final action give an optimal plan while preserving constraints.

A.3 Making Non-SOS Problem Serializable

A nonserializable conjunction can be encoded as one new super-predicate, such as p_and_q(x). Operators must be split into cases and updated to maintain that predicate consistently. Repeating this construction can expand the predicate and operator sets exponentially, so it shifts complexity into the representation.

The source’s illustrative effect assignments contain inconsistent plus/minus signs and operator subscripts. They are retained as written below; the conceptual conjunction compilation should not be treated as an executable operator specification without resolving those inconsistencies.

Equations¬q⁡(x)\neg q(x)eff+​(o1)=eff+​(o)\textit{eff}_{+}(o_{1})=\textit{eff}_{+}(o)eff−​(o1)=eff+​(o)\textit{eff}_{-}(o_{1})=\textit{eff}_{+}(o)eff+​(o1)=eff+​(o)∪{p_and_q​(x)}\textit{eff}_{+}(o_{1})=\textit{eff}_{+}(o)\cup\{\textit{p\_and\_q}(x)\}eff−​(o1)=eff−​(o)\textit{eff}_{-}(o_{1})=\textit{eff}_{-}(o)

A.4 Proof for Theorem 3.2: Polynomial Hardness for SOS-k problems.

The proof counts O(N^(k+1)) possible goal/constraint combinations and uses the SOS condition to justify reusing optimal trajectories. It then argues that candidate rules can be enumerated with the stated polynomial overhead, so a valid rule set need not be supplied beforehand. This reuse is conditional on the theorem’s assumptions, not a general license to ignore the starting state in planning caches.

The retained width-zero counterexample has a free variable shared across subgoals. Without the strong condition, solving the later subgoal need not preserve the earlier one; branching can remain exponential despite small nominal width.

Refer to caption
Figure 4: Illustration of the branching factor caused by tracking multiple resulting states after achieving a subgoal.
Equationg⁡(x)⇜p1​(x,y)∅,p2​(x)∅|a1​(x,y)g(x)\leftsquigarrow p_{1}(x,y)^{\emptyset},p_{2}(x)^{\emptyset}~\|~a_{1}(x,y)

A.5 Additional Discussion

Additional discussion considers how to identify useful rules, interpret width as retained constraints, and extend the syntax beyond bounded lists of preconditions.

Deriving optimally-serializable, small-width rules.

Lifted dependency analysis can reject rules that would require the current goal again and hence create a regression cycle. For clearing a block, this helps select the object actually on top. Such static pruning can be useful, but state-dependent strong serializability is not generally easy to decide.

Connection with other concepts in search.

Retained constraints resemble backward dependencies in a constraint graph, linking the intuition to treewidth and backtrack-free search. The paper also contrasts serial goal achievement with delete-relaxed heuristics that solve subgoals independently and concatenate their plans. These are connections in structure, not interchangeable guarantees.

Generalization to ∀ -quantified preconditions.

Universally quantified preconditions can create an unbounded number of subgoals. Constraints then accumulate and enumerating their orders can cost factorial time. A compact selector may avoid this enumeration in special domains; merely permitting quantified syntax does not preserve the original small-width bound.

A.6 Connection with Width-Based Forward Search IW(k)

The proof associates each step of an optimal SOS plan with a newly achieved tuple of at most k + 1 atoms. If that tuple had already appeared, the plan could be shortened under the strong condition. This supplies the forward-width upper bound stated again in Theorem A.1.

The reverse equivalence fails. Clearing a Blocks World target has an example of SOS width one but forward width one rather than the upper bound two: an existing on-table predicate provides a shorter forward tuple description. The original example rule is retained.

Theorem A.1 (Sufficiency condition for forward width).

Any planning problem that has SOS-width kk has a forward width of at most k+1k+1 and, hence, can be solved by the algorithm IW​(k+1)\textit{IW}(k+1).

Equation
clear​(A)⇜on​(B,A),clear​(B)∅,handsfree​(){clear​(B)}|unstack​(y,x)\textit{clear}(\text{A})\leftsquigarrow\textit{on}(\text{B},\text{A}),\textit{clear}(\text{B})^{\emptyset},\textit{handsfree}(\text{})^{\{\textit{clear}(\text{B})\}}~\|~\textit{unstack}(\text{y},\text{x})

Appendix B Proofs and Discussions for Policy Circuit Complexity

Appendix B constructs relational circuits for backward and width-based search, then discusses recurrence and changes in state representation.

B.1 Proof of Theorem 4.1: Compilation of BWD

At layer d, the network represents conjunctions of goals reachable by d backward regression steps. An action expands a conjunction when its delete effects do not conflict with it. Each encoded conjunction needs at most β·k_BWD object variables. Lifted first-order rules implement this expansion and select the first executable action at the shortest applicable layer; the original construction formulas are retained.

Original figure
Figure 5: Illustration of the compilation of backward search into a RelNN policy.
Equationssg∈Goald∧(eff−​(a)∩sg=∅)⇒(sg∪pre​(a)∖eff+​(a))∈Goald+1\textit{sg}\in\textit{Goal}^{d}\wedge\left(\textit{eff}_{-}(a)\cap\textit{sg}=\emptyset\right)\Rightarrow\left(\textit{sg}\cup\textit{pre}(a)\setminus\textit{eff}_{+}(a)\right)\in\textit{Goal}^{d+1}(eff−​(a)∩expr​(qi)=∅)∧(expr​(qj)=expr​(qi)∪pre​(a)∖eff+​(a))(\textit{eff}_{-}(a)\cap\textit{expr}(q_{i})=\emptyset)\wedge(\textit{expr}(q_{j})=\textit{expr}(q_{i})\cup\textit{pre}(a)\setminus\textit{eff}_{+}(a))∀x1,⋯,xk′.qi(d)​(x1,⋯,xk′)⇒qj(d+1)​(x1,⋯,xk′)\forall x_{1},\cdots,x_{k^{\prime}}.~q^{(d)}_{i}(x_{1},\cdots,x_{k^{\prime}})\Rightarrow q^{(d+1)}_{j}(x_{1},\cdots,x_{k^{\prime}})(eff−​(a)∩expr​(qi)=∅)∧(expr​(qi)∪pre​(a)∖eff+​(a)⊂s)(\textit{eff}_{-}(a)\cap\textit{expr}(q_{i})=\emptyset)\wedge(\textit{expr}(q_{i})\cup\textit{pre}(a)\setminus\textit{eff}_{+}(a)\subset s)∀x1,⋯,xk′.qi(d)​(x1,⋯,xk′)⇒a(d+1)\forall x_{1},\cdots,x_{k^{\prime}}.~q_{i}^{(d)}(x_{1},\cdots,x_{k^{\prime}})\Rightarrow a^{(d+1)}

B.2 Proof of Theorem 4.2: Compilation of S-GRS

The SOS proof uses the forward-width connection to simulate IW(k + 1). The circuit records reachability of small atom tuples and the truth of predicates in a representative terminal state of the associated optimal trajectory. One layer expands by an action. Reapplying the resulting policy follows the selected tuple path; the claimed breadth and depth depend on the preceding width result.

B.3 More Discussion

A recurrent relational layer can perform a number of iterations that grows with instance size. Alternatively, a derived above relation can identify a clear topmost block in one step. Computing that relation is additional work or information supplied by the representation.

The appendix also describes a right-turn/depth-first linearization shortcut for path finding in an acyclic maze. Its topology and representation assumptions matter; it does not establish a fixed-depth optimal policy for arbitrary cyclic navigation problems.

Appendix C Analysis of AI Planning Problems

Table 3 restates the six-domain analysis. The guarantees are for the stated single-atom goal classes; optimal multi-goal planning is generally not serializable by simply achieving each goal once. Super-predicates can address interactions at potentially exponential representation cost.

For satisficing rather than optimal planning, the authors describe simple sequential goal achievement in Logistics, Gripper, Rover, and Elevator. Unbounded-depth domain constructions commonly scale with the number of objects or graph distance, even when relational breadth is constant.

Problem Breadth Regression Width Depth
BlocksWorld Constant 1 Unbounded
Logistics Constant 0 Unbounded
Gripper Constant 0 Constant
Rover Constant 0 Unbounded
Elevator Constant 0 Unbounded
Sokoban Unbounded N/A (not serializable) Unbounded
Table 3: Width and circuit complexity analysis for 6 problems widely used in AI planning communities. This table contains the same content as Table 2; we include it here for easy reference.

C.1 SOS Width Analysis

The appendix lists domain-specific regression-rule selectors as constructive witnesses for finite SOS width. These rules omit some static type checks and must be read with the domain assumptions.

Finite SOS width for Blocks World.

The Blocks World rules choose among unstack, place-table, pick-table, and stack according to current on/holding predicates. Their full seven-line formula array is preserved below. These single-goal constructions underlie the reported SOS width of one.

Equation
Seven original Blocks World regression-rule formulas.
Blocks World regression rules.

Finite SOS width for Logistics.

The Logistics rules regress location goals through unloading, loading, driving, and flying. Static checks such as requiring airport endpoints are omitted in the source. The displayed load/unload arguments use x and y despite quantifying other variable names; the original notation is retained rather than silently repaired.

Equation
∀cons.∀v.∀o.∀ℓ.\displaystyle\forall\textit{cons}.\forall v.\forall o.\forall\ell.~~ at​(o,ℓ)cons⇜in​(o,v),at​(v,ℓ)|unload​(y,x)\displaystyle\textit{at}(o,\ell)^{\textit{cons}}\leftsquigarrow\textit{in}(o,v),\textit{at}(v,\ell)~\|~\textit{unload}(y,x)
∀cons.∀v.∀o.∀ℓ.\displaystyle\forall\textit{cons}.\forall v.\forall o.\forall\ell.~~ in​(o,v)cons⇜at​(o,ℓ),at​(v,ℓ)|load​(y,x)\displaystyle\textit{in}(o,v)^{\textit{cons}}\leftsquigarrow\textit{at}(o,\ell),\textit{at}(v,\ell)~\|~\textit{load}(y,x)
∀cons.∀v.∀ℓ1.∀ℓ2.∀c.\displaystyle\forall\textit{cons}.\forall v.\forall\ell_{1}.\forall\ell_{2}.\forall c.~~ at​(v,ℓ2)cons⇜loc​(ℓ1,c),loc​(ℓ2,c),at​(o,ℓ1)|drive​(v,ℓ1,ℓ2,c)\displaystyle\textit{at}(v,\ell_{2})^{\textit{cons}}\leftsquigarrow\textit{loc}(\ell_{1},c),\textit{loc}(\ell_{2},c),\textit{at}(o,\ell_{1})~\|~\textit{drive}(v,\ell_{1},\ell_{2},c)
∀cons.∀v.∀a1.∀a2.\displaystyle\forall\textit{cons}.\forall v.\forall a_{1}.\forall a_{2}.~~ at​(v,a2)cons⇜at​(v,a1)|fly​(v,a1,a2)\displaystyle\textit{at}(v,a_{2})^{\textit{cons}}\leftsquigarrow\textit{at}(v,a_{1})~\|~\textit{fly}(v,a_{1},a_{2})

Appendix D Experimental Details

Appendix D specifies the three experimental generators, optimizer, compute, and released code.

D.1 Training details

The experiment settings below supplement Table 2’s depth schedules, breadth two, and hidden dimension 64.

Environment setup.

Assembly3 samples three object types and match relations with exactly one compatible A–B–C tuple. BlocksWorld-Clear adds blocks one by one onto a clear block or the table, then selects a target that is initially covered. Logistics grows a directed tree from the starting node and adds a few forward connections before sampling a destination. These structured distributions constrain the generalization claim.

Additional hyperparameters.

All experiments use Adam with learning rate 0.001, β₁ = 0.9, and β₂ = 0.999. Architecture depth varies by task as reported in Table 2.

Compute.

Each experiment uses one NVIDIA Titan RTX GPU on an internal cluster.

Code.

The released goal-regression-width repository contains reproduction code for the experiments.

Concept demonstration

Open image ↗