What Planning Problems Can A Relational Neural Network Solve?
Authors: Jiayuan Mao
Tomás Lozano-Pérez
Joshua B. Tenenbaum
Leslie Pack Kaelbling
Venue: NeurIPS 2023 spotlight (2023)
Keywords: Planning
Relational Neural Network
Circuit Complexity

Abstract: Goal-conditioned policies are generally understood to be "feed-forward" circuits, in the form of neural networks that map from the current state and the goal specification to the next action to take. However, under what circumstances such a policy can be learned and how efficient the policy will be are not well understood. In this paper, we present a circuit complexity analysis for relational neural networks (such as graph neural networks and transformers) representing policies for planning problems, by drawing connections with serialized goal regression search (S-GRS). We show that there are three general classes of planning problems, in terms of the growth of circuit width and depth as a function of the number of objects and planning horizon, providing constructive proofs. We also illustrate the utility of this analysis for designing neural networks for policy learning.

What Planning Problems Can A Relational Neural Network Solve?
Jiayuan Mao! Tomás Lozano-Pérez! Joshua B. Tenenbaum 1.2.3 Lestie Pack Kaclbling'
MIT Computer Science Artificial Intelligence Laboratory
MIT Department of Brain and Cognitive Sciences
Center for Brains, Minds and Machines
Abstract
Goal-conditioned policies are generally understood to be "feed-forward" circuits, in the form of neural networks that map from the current state and the goal specifi- cation to the next action take. However, under what cireumstances such policy can be learned and how efficient the policy will be are not well understood. In this paper, we present circuit complexity analysis for relational neural networks (such as graph neural networks and transformers) representing policies for planning problems, by drawing connections with serialized goal regression search (S-GRS). We show that there are three general classes of planning problems, in terms of the growth of circuit width and depth as a function of the number of objects and planning horizon, providing constructive proofs. We also illustrate the utility of this analysis for designing neural networks for policy learning.
Introduction
Goal-conditioned policies are generally understood to be "feed-forward" circuits, in the form of neural networks such as multi-layer perceptrons (MLPs) or transformers [Vaswani al., 2017]. They take a representation of the current world state and the goal as input, and generate an action as output. Previous work has proposed methods for learning such policies for particular problems via imitation or reinforcement learning [Wang et al., 2018, Dong al., 2019, Li et al., 2020]; recently, others have tried probing current large-language models to understand the extent to which they already embody policies for wide variety of problems [Liang et al., 2022, Carta et al., 2023].
However, major theoretical challenge remains. general, we understand that planning problems are PSPACE-hard with respect to the size of the state space [Bylander, 1994]. but there seem to exist efficient (possibly suboptimal) policies for many problems such as block stacking [Dong et al., 2019] that generalize to arbitrarily sized problem instances. In this paper, we seek to understand and clarify the circuit complexity of goal-conditioned policies for classes of "classical" discrete planning problems: under what circumstances can polynomial-sizer policy circuit be constructed, and what its size? Specifically, we highlight relationship between a problem hardness measure (regression width, related to the notion of "width" in the forward planning literature [Chen and Giménez, 2007]) and circuit complexity. We concretely provide upper bounds on the policy circuit complexity as function of the problem's 's regression width, using constructive proofs that yield algorithms for directly compiling a planning problem description into a goal-conditioned policy. We further show that such policies can be learned with conventional policy gradient methods from environment interactions only, with the theoretical results predicting the necessary size the network.
There are several useful implications of these results. First, by analyzing concrete planning domains, we show that for many domains. there do exist simple policies that will generalize to problem instances with an arbitrary number of objects. Second, our theory predicts the circuit complexity of policies for these problems. Finally, our analysis suggests insights into why certain planning
Project page:
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

UA E) handsfree, on-table(A), on-table(B), on-table(E), onte, onto, clcan(A), (lear(0), clear(E)
picR tobie(x):
piaco-table(xte
on-babbe(x), clean(x), handsfree effe: holding(s)
holding(s)
effe; on-table(x), clean(s), handsfree off-: haldinu(s)
eff-: on-table(x), clean(s), handsfree
unstock(s, x2: on
stack(s, y}=
pre: on(e, x), clear(s), handsfree offe: holcina(K), clear(y)
prec holding(s), ciwer(s) (y)
offe: cluarty), halding(s) off holding(K), clear(y)
offi: on(*, y), clear(A), handsfres
Blocks World Visualization and its Representation
(b) Action schemas in Blocks World
clear(U)
Clear(H)
handsfree on on on-geal
lunstack(s,
(on(C, ny, clear(C), handsfrree)
place-table(B)
un unstacks(, (lare-ttobl-(1)
Temor Represcatation and Goal Literal
[ttckk(D E)
ContC, (onte, R), clear(11) (C, B), (less(C)), handsfiree
(or[C, R), clean(C)) holding()), clear(t))
Retational Neural Network (es, GNNs Transfommes)
010
Junstackto,
(ontS, B), clean(E), on(o, c), claur(D), handsfrree
Cnstare EJocettable(00
Next Action
on C)2 clear(D), handsfrre boldlnng()) (d) Goal Regression Search with Serialization
unstack(D, C)
(c) Conventional Backward Search
(0) Compiled ReINN Policy
Figure 1: (a) Illustraiion of the Blocks World domain that we will be using as the main example. (b) The action schema definition in Blocks World, clear(x) means there is no object on x. (c) A backward search tree for solving the goal clear(B). (d) A serialized goal regression search tree for the same goal. (e) The form of goal-conditioned policy for this problem.
problems, such as Sokoban and general task and motion planning (TAMP) problems, are hard, and likely cannot be solved in general by fixed-sized MLP or transformer based policies [Culberson, 1997, Bega-Brown and Roy, 2020]. In the rest of the paper, Section 2 provides problem definitions, Sections and 4 provides complexity definitions, theoretical results, and the policy compilation algorithm; Section 5 discusses the practical implications of these results.
2 Preliminaries: Planning Domain and Problem
Throughout this paper, we focus on analyzing the search complexity and policy circuit complexity of classical planning problems. Importantly, these planning problems have an object-centric represen- tation and sparsity in the transition models: the state of the world is represented as a set of entities and their properties and relationships, while each action only changes sparse set of properties and relations of a few objects. These features will contribute to search efficiency.
Formally, we consider the problem of planning and policy learning for space S of world states. A planning problem is a tuple (S, so. G,,,T, where so E S is the initial state, 9 S S a goal specification, A is set of actions that the agent can execute, and T is (possibly partial) environmental transition model T : SSx A S. The task of planning is to output a sequence of actions in which the terminal state sy induced by applying a, sequentially following T satisfies sy E G. The task of policy lcarning is to find a function z(s,)) that maps from the state and a goal specification to the next action so that applying recurrently on so eventually yields state sy G.
We use atomic STRIPS [Fikes and Nilsson, 1971, Lifschitz, 1987] to formalize the object-centric fac- torization of our planning problems. Specifically, as illustrated in Fig. la, the environmental state can be represented as a tuple (U,,P,), where Ul is the set of objects in state s, denoted by arbitrary unique names (e.g.. A, B). The second component, Ps, is set of atoms: handfree(), or--table(A) (A), on(C, B), etc. Each atom contains predicate name (e.g., on) and a list of arguments (e.g., C, B). All atoms in P. are true at state while any atoms not in P, are false. Since we do not consider object creation and deletion, we simply use Po to denote the set of all possible atoms for the object universe U
Illustrated in Fig. lb, a (possibly partial) transition model T is specified in terms of a set of object- parameterized action schemas (name, args, precond, effect), where name the name of the action, args is a list of symbols, precond and effect are descriptions of the action's 's effects. In the basic STRIPS formulation, both precond and effect are sets of atoms with variables in args, and effect further decomposed into eff. and eff_.. denoting "add" effects and "delete" effects. An action schema (e.g.. unstack) can be grounded into concrete action a ge. unstack(D, C)) by binding all variables args.
"For simplicity, throughout the paper, will be focusing Boolean state variables.
2

---

Algorithm 1 Plain backward search.
Algorithm 2 Serialized goal regression search.
function BwD(Sg, A. yoal_set))
function (-GRS( R, g, cons)
if goal set S Su then return empty_
if E so then return (5p) possible_r= empty_sct()
possible_ = cmpty_set()
for {a E A goal_set n eff (a)
for E (r R cons eff_ (action(r)) 0 and
0 and goal_set elf, # 0] do
goal(r) = g) do
new so__goal== = goal set U pre(a) eff.(a) (a) if new_goals E goal stack then continue
Pt. ... PP = subgoals(r)
if 3p; s.t. p. E goal stack then continue
for in 1, ,k do
new c = cons U [pI, PP-1) x, S-GRS(S,-1- Pt, new_c)
π = BWD(Sg, new_goals)
if ==1 then break
8, ((11,,
if π # then possible_t-addee + (a)) return shortest path in possible_
T. #11 then
possible_taadee ftadd(m +... + nu + (a))
+.......
return shortest path in possible_
The formal semantics of STRIPS actions is: Vs.Va.reeaa) S = (T(s,))= s U eeff. \ eff-(a)) That is, for any state and any action a, if the preconditions of a satisfied in s, the state resulting from applying a to s will be s U eff. (a) ef)_ Note that T may not be defined for all (s, a) pairs. Furthermore, we will only consider cases where the goal specification is single atom, although more complicated conjunctive goals or goals that involve existential quantifiers can be easily supported by introducing additional "goal-achieve" action that lists all atoms in the original goal as its precondition. From now on, we will use to denote the single goal atom of the problem.
3 Goal Regression Search and Width
simple and effective way to solve STRIPS problems is backward search". IIlustrated in Algorithm 1 we start from the goal (g), and search for the last action a that can be applied to achieve the goal (i.e.,g g (a). Then, add all the preconditions of action avoid infinite loops, we also keep track of a "goal stack" variable composed of all goal goal_ser'ss s that have appeared in the depth-firs first search stack. The run-time of this algorithm has critical dependencies on (1) the number of steps in the resulting plan and (2) the number of atoms in the intermediate goal sets in search. In general, it has worst-case time complexity exponential in the number of atoms.
our search target and recurse. To
3.1 Serialized Goal Regression Search
One possible way to speed up backward search is to serialize the subgoals in the goal set: that is, to commit achieving them in partieular order. In the following sections, we study variant of the plain backward search algorithm, namely serialized goal regression search (S-GRS, Algorithm 2), which uses a sequential decomposition of the preconditions: given the goal atom g, it searches for the last action a and also an order in which the preconditions of a should be accomplished. Of course, this method cannot change the worst-case complexity of the problem (actually, it may slow down the algorithm in cases where we need to search through many orders of the preconditions), but there are useful subclasses of planning problems for which it can achieve a substantial speed-up.
A serialized goal regression rule in R, informally, takes the following form: '~ Pl. P1.P2.-. "...... Pk ll a. It reads: in order to achieve g. which is single atom, we need to achieve atoms PI,'.. PPs sequentially, and then execute action a. To formally define the notion of achieving atoms pl. P& "sequen- tially." we must include constraints in goal regression rules. Formally, we consider the application of rule under constraint c to have the following definition, g Pf. P2 c-Ipp.l ..... PP pp || which reads: in order to achieve g without deleting atoms in set we can first achieve Pi while maintaining c, then achieve P2 while maintaining c and Pl. ..., until we have achieved Ps. Finally, we perform a to achieve g. For example, in Blocks World, we have the rule: (onudffree(jom(BBB..eeee
c e~ on(A, B), clear(A) (I)oo((.B))))
unstack(A, B). Note that many rules might be infeasible for given state, because it is simply not possible to achieve p, while
"Fundamentally, hackward search has the same worst-case time complexity as forward search. We choose to analyze backward search because goal regression rules are helpful in determining fine-grained search complexity. We show the recursive version for clarity. This algorithm also be implemented breadth-fing search.
3

---

maintaining с and (pi,-.., ,P-1). In this case, achieving handsfree() before clear(A) is infeasible because handsfree() may be falsified while achieving clear(A), if we need to move other blocks that are currently on A. Similarly, on(A, A, B) must be achieved before clear(A) because moving A onto B will break clear(A) (because we need to pick up A).
The set of all possible goal regression rules can be instantiated based on all ground actions A in a planning problem. Specifically, for a given atom g (e.g., holding(A) and set of constraints c, and for each action a E A (e.g., pick-table(A) A)), if g E eff=(a) while c n eff- [a] = 0, then for any permutation of pre(a), there will be a goal regression rule: g *m p1.-. .P a, where p Pa is permutation of pre(a). We call this regression rule set Rg-
Given set of regression rules (e.g., Ro), we can apply the serialized goal-regression search (S-GRS) algorithm, shown in Algorithm 2. S-GRS returns a shortest path from state to achieve goal while maintaining cons. Unfortunately, this algorithm is not optimal nor even complete (e.g., a sequence of preconditions may not be "serializable," " which we will define formally later), in the general case. To make it complete, is necessary to backtrack through different action sequences to achieve each subgoal, which increases time complexity. We include a discussion in Appendix A.I.
3.2 Serialization of Goal Regression Rules
Although Algorithm 2 not complete in general, provides insights about goal regression. In the following, we will introduce two properties of planning problems such that S-GRS becomes optimal, complete, and efficient. For brevity, we define OptSearch (tatte, goal, cons) as the set of optimal trajectories that achieve goal, from state, while maintaining cons. Here, goal can be conjunction. Definition 3.1 (Optimal serializability). goal regression rule geons 6m PI.-.. .P ll is optimally serializable w.r.t. a state s if and only if. for all steps V E OptSearch(s, PaAA--AAP--- cons) and VA, E OptSearch(T 11). Pi. cons (pt..... -P-il) then πe π. E OptSearch(s, p1 ...... A pt, cons). Furthermore, Vx E OptSearch(s, P1 A... A Pa. cons), π @ a E OptSearch(s, g. cons)
Intuitively, a rule is optimally serializable if any optimal plan for the length i- prefix of its preconditions can be extended into an optimal plan for achieving the length prefix. For example, in Blocks World, the rule holding(A) em on(A, B), clear(A) (A), handsfree() || unstack(A, B) is optimally serializable when on(A, B) true for s. We define the set of optimally serializable rules for a state s as s)), and the set of single-literal goals that can be solved with OSR(.) from so as OSG(s))) Theorem 3.1. For any goal& g E OSG(so), S-GRS optimal and complete. See proof in Appendix A.2.
3.3 Width of Search Problems
Chen and Giménez [2007] introduced the notion of the width of a planning problem and showed that the forward- search complexity is exponential in the width of problem. We extend this notion to regression- based searches and introduce a generalized version of regression rules in which not all previously achieved preconditions must be explicitly maintained.
Definition 3.2 (Generalized regression rules). generalized,
regression rule euce l| where e, C (Pi, (Pi.P2. PP--1) Its width is |c| max(lc]l. Icgll- is g 6m P1 pele, P2 . ..... .Px
For example, for any initial state so that satisfies on(A, B), the following generalized rule is optimally serializable: clear(B) en on(A, B)), clear(A)), haansfree()lceerraaas || unstack(A, B). When we plan for the second precondition clear(A), plan for clear(A) will not change on(A,
ignore the first condition on(A, B), because the optimal B). B). Using such generalized rules to replace the default rule set Ro improves search efficiency by reducing the number of possible subgoals. To define existence conditions for highly efficient search algorithms and policies, we need a stronger notion:
Definition 3.3 (Strong seiimally-seriaizzable (SOS) width of regression rules). A generalized regres- sion rule has strong optimally-serializaable serializable width k w.r.t. state s if (a) is optimally serializable, (b) its width is k, and, (c) VcOptSearch(s, p; U c; U c. 0) c OptSearch(s, (Pi. .P C., O,
In the Blocks World domain, given particular state s. if on(A, B) E s, the generalized goal re- gression rule clear(B) eM on(A, B), clear(A), handsfree(jieeannk || unstack(A, B) is strong optimally- serializable, because the optimal trajectory to achieve clear(A) A) will not move A.
la b denotes concatenation of sequences. nei denotes the subsequence (ag.--. .-m1 SIt is possible to make a non-optimally serializable - rule into an optimally serializable one by introducing "super predicates" as the conjunction of existing predicates, at the cost of increasing the state and action space sizes. We include discussions in Appendix A.3.

---

Definition 3,4 (SOS width of problems). A planning problem P == (0, (.,,0...7777 A.T) has strong optimally-seriaal serializable width k if there exists a set of strong optimally-serializabae width k &rules R w.r.l. So, such that S-GRS can solve P using only rules in R.
So.
Theorem 3.2. If a problem P is of SOS width k, can be solved in time O(Nttl) with S-GRS, where N is the number of aloms. Here we have omitled polynomials related to enumerating all possible actions and their serializations (which are polynomial w.r.t. the number of objects in U).
Proof idea. We start by assuming knowing R: the proof can be simply done by analyzing function calls: there are at most O(N*+1) possible argument combinations of (goal, cons). Next, since the enumeration of all possible width-k rules can be done in polynomial time. Therefore, the algorithm runs in polynomial time and it does not need to know R a priori. Note that the SOS condition cannot be removed because even if regression rules have a small width, there will be possibly exponential branching factor caused by "free variables" in regression rules that do not appear in the goal atom. See the full proof in Appendix A.4. We also describe the connections with classical planning width and other related concepts, as well as how to generalize to V-quantified preconditions in Appendix A.5.
Importantly, planning problems such as Blocks World and Logistics have constant SOS widths, independent of the number of objects. Therefore, there exist polynomial algorithms for finding their solutions. Our analysis is inspired by and closely related to classical (forward) planning width Chen and Giménez [2007] and Lipovetzky and Geffner [2012]. Indeed, we have:
Theorem 3.3. Any planning problem that has SOS-width k has forward width of at most k + 1 and, hence, can be solved by the algorithm IW(K + 1). See the full proof in Appendix A.6.
Remark. Unfortunately, SOS width and forward width are not exactly equivalent to each other. There exist problems whose forward width is smaller than k + 1, where k is the SOS width. Appendix A.6 presents a concrete example. However, there are two advantages of our SOS width analysis over the forward width analysis. In particular, proofs for (forward) widths of planning problems were mostly done by analyzing solution structures. By contrast, our constructions form a new perspective: a problem has a large width if the number of constraints to track during a goal regression search is large. This view is helpful because our analyses can now focus concrete regression rules for each individual operator in the domain - how its preconditions can be serialized. Second and more importantly, our "backward" view allows to reason about circuit complexities of policies.
4 Policy Realization
We have studied sequential backward search algorithms for planning: now, we address the questions of how best to "compile" or "learn" them as forward circuits representing coal-conditioned policies, and how the size of these circuits depends on properties of the problem. Here, we will focus on understanding the complexity of a certain problem class; that is, set of problems in the same domain (e.g., Blocks World) with a similar goal predicate (e.g., having one particular block clear). In particular, we will make use of relational neural networks (ReINN. such as graph neural networks [Morris et al., 2019] and Transformers [Vaswani et al., 2017I). They accept inputs of arbitrary size, which is critical for building solutions to problems with arbitrary-sized universes. Another critical fact is that these networks have "parameter-tying" in the sense that there is a constant-sized set of parameters that is re-used according to given pattern to realize network.
In particular, as illustrated in Fig. 2. we will show how to take the set of operator descriptions for a planning domain and construct relational neural network that represents a goal-conditioned policy: takes a state and goal (encoded as a special predicate, e.g., on-goal) and outputs a ground action. Here, the state is represented as graph (objects are nodes, and relations are edges; possibly there will be hyperedges for high-arity relations). For example, the input contains nullary features (a single vector for the entire environment), unary features (a vector for each object), binary features (a vector for each pair of objects), etc. The goal predicate can be represented similarly. These inputs are usually represented as tensors. The complexity of this neural network will depend on the SOS width of problems in the problem class of interest.
We will develop two compilation strategies. First, in Section 4.2, we directly compile the BWD and the S-GRS algorithms into ReINN circuits. For problems with constant SOS width that is independent of the size of the universe, there will exist finite-breadth circuits (but the depth may depend on the size of the universe). In Section 4.3, we discuss a new property of planning problems- the existence of regression rule selector circuits- wreccts-which results in policy circuits that are smaller than those generated
5

---

by previous strategies, and they are potentially of finite depth. The construction of the regression rule selector is not automatic and will generally require human priors or machine learning.
4.1 Relational Neural Network Background
We first quantify what a relational neural net- work can compute, using the formalization de- veloped by Luo al. [2022]: see also Morris et al. [2019]. Barceló et al. [2020]. Let depth D be the number of layers in a ReINN, and breadth B be the maximum arity of the relations (hyperedges) in the network. For example, to represent a vector embedding for each tuple of
hands
Nuilary Predicates
Nallary Actions
on-table
holding clean
ReINN
Unary Predicatiss
Unary Actions
size 5, f(x,, X2. Xs)), where "I. ,ss E U/ are entities in the planning problem, we need relational neural network with breadth 5. We will only consider networks with a constant breadth. We denote the family of relational neural networks with depth D and breadth B as Re B). We will not be modeling the actual "hidden dimension" of the neural network layers (i.c., the number of neurons inside each layer), but we will assume that it is bounded (for example, as a function of B and the number of predicates in the domain). Under such assumptions (most practical graph neural networks, Transformers, and hypergraph neural networks do follow these assumptions), we have the following lemma.
on goag
unsttack
Binary Predicates
Binary
CinaryAActionl Actions
Environment
State
Action
Figure 2: The input and output of a relational neu- ral network (RelNN) policy.
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 B variables, extended with counting quantifiers of the form P= which state that there are least n nodes satisfying formula s.
(Upper Bound) Any function f in FOCB can be realized by ReINNID, B) for some D.
(Lower Bound) There exists a function in FOCg such that for all D, f cannot be realized by ReINN[D, 1].
Here, we sketch a constructive proof for using ReINNs to realize FOL formulas. The breadth B is analogous to the number of variables in FOL for encoding the value of the expression; the depth D is y, z) needs 3 layers, one
the number of "nested quantifiers." For example, the formula Ex.Vy.Vz.j for each quantifier. Furthermore, we call a ReINN finite breadth (depth) if B (D) is independent of the number of objects. Otherwise, we call it unbounded breadth (depth).
4.2 Compilation of BWD and S-GRS
Lemma 4.1 states an "equivalence" between the expressive power of relational neural networks and first-order logie formulas. In the following, we take advantage of this equivalence to compile search algorithms into relational neural networks. First, we have the following theorem.
Theorem 4.1 (Compilation of BWD). Given a planning problem P. let T be the length of the optimal trajectory (the planning horizon), kowD be the maximum number of atoms in the goal set in BWD, and B be the maximum arity of atoms in the domain. The backward search algorithm BWD can be compiled into relational neural network in RelNN[O(T),P B.B kgwpl.
Proof sketch. We provide a construction in which the ReINN computes set of subgoals (i.e., a set of sets of ground atoms) Goal at each layer d. Initially, Goal" = H[g]]. Then, sg E Goal if there is a path of length d from any state that satisfies sg to g. See Appendix B.1 for the full proof.
Although this construction is general and powerful, it is unrealistic for large problems because the depth can be exponential in the number of objects, and the number of atoms in the subgoal conjunctive formulas can be exponential the depth. Therefore, in the following, we will leverage the idea of serialized goal regression to make a more efficient construction.
Theorem 4.2 (Compilation of S-GRS), Given a planning problem P of SOS width k, let T be the length of the optimal trajectory, and B be the muximum arity of aloms in the domain. The serialized goal regression search S- S-GRS can be compiled into a RelNN(O(T), (k + 1) B]. where k 1 S KnWD- See Appendix B.2 for the full proof using similar technique in Theorem 4.1.

---

on-table(x)
if True: apply: holding(x) II place-table(s)
(n y) < if True: apply: clear(y), holding(x) II stack(x, y) holding(x)
if exists y. on(x, y);
apply: on(x, y), clear(x), handsfree II unstack(x, y)
if on-table(x); apply: on-table(x), clear(x), handsfree II pick-table(x) if holding(x): apply: holding(x) II place-table(x) if exists y. only, x): apply: on(y, x), clear(y), handsfree II unstack(y, x)
E
clear(x)
Goal on
(a) The regression rules selector for Blocks World (applicable w.r.t. any constraints).
on-table-g((x) holding(x) - place-table(x)
on-table-g"xx) A-holding(x) holding-goal**xxx)
vx. vy. ond(x, y) A clear(y) A holding(x) stock(x, y)
Goal:: holding(D)
vx. vy. ond(x, y) A clear(y) A-halding(x) - holding-gond holding-goa1*t(x))
vx. vy. on y) A-clear(y)
clear-goa14tHy))
vx. vy. holding-g"xx) A on(x, y) clear(x) A handsfree + unstack(x)
vy. holding-g*(x) A on(x, y) clear(x) Ashandsfree handsfree-gdhh
Action: unstack(D, C)
vx. Vy. holding-g gx() A on(x, y) A-clear(x) clear-g"M(x)
(b) Compilation of rule selectors into First-Order Logic formulas.
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.
Figure 3:
Remark. The compilation in Theorem 4.2 can generate finite-breadth, unbounded-depth ReINN cir- cuits for more problems than the compilation in Theorem 4.1. For example, in Blocks World, the number of atoms in the goal sets in BWD is unbounded. However, since the problem is of constant SOS width, it can be compiled into finite-breadth circuit. When the search horizon T is finite, both the SOS width and kawD will be finite because there are only a constant number of actions that can be applied to update the goal set / constraint set. So problem can be compiled into finite-depth, finite-breadth ReINN circuit with BWD compilation if and only if it can be compiled with S-GRS compilation, although S-GRS compilation may generate smaller circuits.
4.3 Compilation of S-GRS with a Regression Rule Selector
Unfortunately, both constructions the previous section require a depth-O(TT) ReINN eircuit, which is impractical for most real-world problems, as T can be exponential in the number of objects in domain. In order to compile the goal regression search algorithm into a smaller circuit, we consider scenarios where the rule used to construct the (optimal) plan can be computed without doing full search. Here the idea is to bring in human priors or machine learning to learn a low-complexity regression rule selector that directly predicts which goal regression rule use. There exists such rule selector for some problems (e.g., Blocks World) but not others (e.g., Sokoban).
Formally. we define a state-dependen regression rule selector (RRS) select(s, g, cons), which returns an ordered list of preconditions and ground action a. Its function body can written in the following form: g 4- if p(s, cons) pi .P> .P consUlpi) ,... PP Pm consUipi.-PPe-ll || a, which reads: in order to achieve under constraint P1.P2. Pm ll a. Formally, select is composed of a collection p.pgs. any given state pre is an ordered list of preconditions, is a ground action, is the goal atom, and cons is the constraint. p.pre, a. g. and cons may contain variables in args. Such rule selector be implemented by hand (as a set of rules, as illustrated Fig. 3a for the simple Blocks World domain), or learned by a ReINN model.
state if p(s, cons) is true, can apply the regression rule rules. Each rule a tuple of (args. p. pre, a, g, cons), where args is set of variables, p is a FOL formula that can be evaluated
The main computational advantage is that now, for a given tuple (s, g, cons), there is a single ordered list of preconditions and final action. Therefore, given the function select, we can simply construct sequence of actions that achieves the goal by recursively applying the rule selector. In this section, we will first discuss scenarios where such rule selectors can be computed with shallow ReINN circuits.
Circuit complexity of regression rule selectors. We first discuss scenarios where there exist finite-depth, finite-breadth circuits for computing the regression rule selector. Note that there are three "branching" factors in choosing the regression rule: 1) the operator to use, 2) the order of the preconditions, and 3) the binding of "free" variables that are not mentioned in the goal atom.
7

---

First, in many cases, a simple condition on the state determines which operator is appropriate to use, and the preconditions can be achieved in fixed order. Second, in many cases, the unbound variables in rule are either determined by early preconditions or can be bound arbitrarily. When these values must be chosen very carefully (e.g.wween when there are resource constraints); then a simple regression rule selector may not exist. For example, in Blocks World, to achieve clear(B), then the optimal way is to perform unstack(A, B), where A is the object on B. Furthermore, in this case, the precondition order is fixed: clear(B) se on(A, B), clear(A), handsfree() unstack(A, B) for arbitrary pairs of objects A, B. In the following, we consider cases where the regression rule selector can be computed with a first-order logic formula, therefore finite-depth and finite- breadth RelNN circuit.
Serializability of RRS. Given a regression rule selector select, we can obtain a single trajectory (if g is reachable from s under constraints cons). We define tr"dlee(ss cons) as the trajectory returned by recursive application of select. It returns 1 if no plan can be found.
Definition 4.1 (RRS Serializability). A regression rule selector is serializable if and only if the following condition holds for any state any goal g. and any constraint set. Consider the regression rule returned by select(s.g, g, cons) to P1.P2."'. .Ps Il a. If g is achievable from s, then it can be achieved via the concalenation of the following trajectories: ai 1regesss (s, Pt, constraint), To = rrrgess (T (s,ā1). p2, constraint U (pi)). "'", Tg. and (a).
Compiling policy neural networks. If there exists regression rule selector that is computable with a finite-depth, finite-breadth ReINN circuit, it will be possible to construct policy for the original problem with another ReINN circuit. This construction can be dramatically more efficient than the general constructions in Section 4.2. Let k denote the "width" of the regression rule selector, i.e. the maximum size of the constraints we need to keep track of when applying select.
Theorem 4.3 (Compilation of S-GRS with regression rule selector). Given regression rule selector select fí.e., the State-constraing condition function p) that can be computed by a relational neural network in ReINN[D,, B,I. for any planning problem P. if tyeelett g. 0) $1., letting d be the depth of the regression tree, then there is a RelNN circuit for the problem in ReINN[O(d D,), max B), where & is the maximum arity of predicates.
Proof. For any step i, let er be the length prefix of the precondition list. We define Goat' to be the single goal atom and set of constraints we need to satisfy at depth d. We have the following rules:
Vd.Vi (prel. (Goat" = (g. cons)) A cons) A gre A --re;-1 = (Goat'tl (pre;,,, cons U pre
Vd. (Goat' = cons)) A p(s, cons) A pre = a
Here the evaluations of preconditions pre are based the current state (input to the policy network) and they can be evaluated in parallel. We illustrate this construction in Fig. 3b. The first set of rules computes the next subgoal (and constraint set) to achieve, while the second set of rules outputs the next action when all preconditions of the current rule have been satisfied (which will be the output of the entire policy). Since at each layer d, we only need to keep track of one tuple of (g, cons), the breadth of the circuit is m)),B,.B), where / is required to store the input state.
This construction yields significant reduction in breadth (from tracking all conjunctions up to kowD atoms to only one tuple of (g. cons)), as well as a reduction of the number of layers for the ReINN policy, depending on the domain. In particular, if the average number of preconditions that need to be recursively solved in each rule is (roughly equal to the number of preconditions in each rule), the depth of the regression tree is d = O(log, 7), where T is the planning horizon.
Finally, for some problems, even if we have a regression rule selector, to compute a plan, we may still need an unbounded depth of search steps (i.e., d depends on the number of objects in the domain). For example, in Blocks World, achieve clear( A), the number of steps needed is proportional the number of objects on top of A. There are two ways to build relational neural network policy in this case. First, we can allow the network to have a variable number of iterations by applying the same layer recurrently several times. Second. there might be "shortcuts" that we can learn. We discuss both solutions in Appendix B.3. These methods allow us to construct finite-depth ReINN circuits for a variety of domains, including Blocks World, and path-finde find-finiin in any acyelic maze.
5 Problem Analysis and Results
We first analyze the regression width and eircuit complexities for familiar AI planning problems. Table I summarizes the results on simplified setting where the goal of the planning problem is
8

---

Problem
Constant Breadth?
Depth
Task
Model
n=10
n=30
n=50
As3
ReINN[1 2]
0.2g005
0.02ga01
0,0g0.
Worlk
(k
Unbounded
As3
ReINNN2, 2]
1.0g00
1.0.n.
1.0.0.
Logisties
0)
Unbounded
Log-
ReINN[3. 2]
1.0,00
0.30
0.23
Gripper
/ (k- 0)
Constant
Log.
Re(NN( 2]
1.0.00
1.0.00
1.0.00
Rover
/ (k 0)
Unbounded
BW
ReINN[3, 2]
2.9.0.
1.0/
10.2.0.45
1.0 15.7
Elevator
/ (K 0)
Unbounded
BW
ReINNL/(().21 1.0/ 20.
1.0 / 3.
1.0 1.5
Sokoban
Unbounded
Table 1: Width and circuit complexity Table 2: Success rate of learned policies in different environ- analysis for 6 problems widely used in ments. For Assembly3 (As3) and Logisties (Log.), we show AI planning communities. For problems the success rate. For Blocks World (BW), we show the suc- with a constant circuit breadth, we also cess rase/ average solution length. We choose f(n) d n/5+1 I annotate their regression width k. "Un- for Logistics and f(1) del n/10 3 for BlocksWorld In the bounded" depth means that the depth de- notation of ReINNDD, B}, D is the number of layers and B is the maximum arity of edges.
pends on the number of objects.
single atom. In summary, most of these problems have constant breadth (i.e., the regression width of the corresponding problem is constant) except for Sokoban. Most problems have an unbounded depth: that is, the depth of the circuit will depend on the number of objects (e.g.. the size of the graph or the number of blocks). For problems this list, when there are multiple goals, usually the goals are not serializable (in the optimal planning case). If we only care about satisficing plans, for Logistics, Gripper, Rover, and Elevator, there exists a simple serialization for any conjunction of goal atoms (basically achieving one goal at time). See Appendix C for more detailed proofs and additional discussions of generalization to multiple goals and suboptimal plans.
Next, given this analytical understanding of the relationship between planning problems and their policy circuit complexity, we perform some simple experiments to see whether that relationship is borne out in practice. Relational neural networks have been demonstrated to be effective in solving some planning problems [Dong et al., 2019, Jiang and Luo, 2019, Li er al., 2020], but their complexity has not been systematicllly explored. We consider two families of problems: one predicted to require finite depth and one predicted to require unbounded depth. For all tasks, we use Neural Logic Machines [Dong et al., 2019] as the model; we set the number of hidden neurons in the MLP layers to be sufficiently large (64 in all experiments) so that it is not the bottleneck for network expressiveness. We use the same encoding style for all problems (the graph-like relationship). Therefore, whether different problems have bounded or unbounded width primarily depends on the available goal regression rules, how these rules can be serialized, and the width of the rules. We show the average performance across random seeds, with standard errors.
Assembly3: finite depth circuits. The domain Assembly3 contains objects. Each object has category, chosen from the set (A, B, C). The goal of the task is to select three objects OA, Og, and oc sequentially, one for each category, while satisfying a matching constraint: match(os, 0g) and match(oB. Oc). Therefore, to select the first object (c.g., an object of type A), the policy needs to perform two layers of goal regression (first find the set of possible B-typed objects that match the object, and then find another C-typed object). We trained two models. Both models have breadth 2, but the first model has only layer (theoretically not capable of representing the two-step goal regression), while the second model has 2 layers. Shown in Table 2, we train models on environments with 10 objects and test them environments with 10, 30, and 50 objects. The first model is not able to learn a policy for the given task, while the second exhibits perfect generalization.
Logistics: unbounded depth circuits. We also construct a simple Logistics domain with only cities and trucks (no airplanes), in which the graphs are not strongly connected (by first sampling a directed tree and then adding forward-commn connectinnn edges). We train the policy network on problems with less than 1=10 cities and test it on n=30 and n=50. Here, we trained two policies. The first policy has a constant depth of 3, and the second policy has a depth of D = n/5 1, which is a manually chosen function such that it is larger than the diameter of the graph. Shown in Table 2, the first model fails to generalize to larger graphs due to its limited circuit depth. Intuitively, to find a path in graph by recursively applying the regression rule, we need a circuit of an adaptive depth (proportional to the length of the path). By contrast, the second model with adaptive depths generalizes perfectly.
Blocks Corld unbounded depth circuits. Based on the goal regression analysis, in Blocks World, in order to achieve the goal atom clear(A) for a specific block A, we would need

---

circuit that is as deep as the number of objects on A in the initial state. We follow the same training and evaluation setup as in Logistics. Our analysis focuses on the length of the generated plan. Shown in Table 2, although both policy networks accomplish the task with a 1.0 success rate (because there a trivial policy that randomly drops clear blocks onto the table), the policy whose depth depends on the number of blocks successfully finds a plan that is significantly shorter than fixed-depth policy. This suggests the importance of using ReINNs with a non-constant depth for certain problems.
Related Work and Conclusion
Most of the existing work on planning complexity considers the NP-Completeness or PSPACE- Completeness of particular problems, such as the traveling salesman problem [Karp, 1972], Sokoban [Culberson, 1997]. and Blocks World [Gupta and Nau, 1992]. In general, the decision problem of plan existence is PSPACE-Complete for atomic STRIPS planning problems [Bylander, 1994]. Seminal work on fine- gree-graded planning problem complexity introduces planning width [Chen and Giménez, 2007] and the IW algorithm [Lipovetzky and Geffner, 2012, Drexler et al., 2022]. Our work is greatly inspired by these ideas and strives to connect them with circuit complexity.
The concept of serialized goal regression is not completely new. These rules are particularly related to the methods in hierarchical task networks [Erol et al., 1994] and can also be seen as special cases of hierarchical goal networks [Alford et al., 2016], derived by dropping preconditions [Sacerdoti, 1974]. In addition, others, including Korf [1987] and Barrett and Weld [1993], have characterized different degrees of serializability of subgoals, but their analysis is not as fine-grained as this.
Our circuit complexity analysis builds on existing work on relational neural network expressiveness. in particular, GNNs and their variants. Xu et al. [2019] provides an illuminating characterization of GNN expressiveness in terms of the WL graph isomorphism test. Azizian and Lelarge [2021] analyze the expressiveness of higher-order Folklore GNNs by connecting them with high-dimensional WL-tests. Barceló et al. [2020] and Luo et al. [2022] reviewed GNNs from the logical perspective and rigorously refined their logical expressiveness with respect to fragments of first-order logic. Our work extends their results, asking the question of what planning problems a ReINN can solve.
Our work is also related to how GNNs may generalize to larger graphs (in our case, planning problems with an arbitrary number of objects). Xu et al. [2020, 2021] have studied the notion of algorithmic alignment to quantify such structural generalization. Dong et al. [2019] provided empirical results showing that NLMs generalize in Blocks World and many other domains. Buffelli et al. [2022] introduced a regularization technique to improve GNNs' generalization and demonstrated its effectiveness empirically. Xu al. [2021] also showed empirically on certain algorithmic reasoning problems (e.g., max -eg-ee, shortest path, and the n- n-body problem). In this paper, we focus on constructing policies that generalize instead of algorithms, using a similar idea of compiling specific (search) algorithms into neural networks.
Conclusion. To summarize, we have illustrated connection between classical planning width, regression width, search complexity, and policy circuit complexity. We derive upper bounds for search and circuit complexities horizon. These results provide an explanation of the success of relational neural networks learning generalizable policies for many object-centric domains. The compilation algorithms highlight that when there are resource constraints such as free space, agents' inventory size, etc., a small policy circuit may not exist. This includes cases such as Sokoban and general task and motion planning. Furthermore, our idea of serialization can be generalized to hierarchical decomposition of problems; it can be potentially extended to other domains such as optimization and planning under uncertainty.
a function of the regression width of problems and planning
Although all of the analyses in this paper have been done for fully discrete domains by analyzing first-order logic formulas, understanding the implications in relational neural network learning is important because, ultimately, ReINNs can be integrated with perception and continuous action policy networks to solve realistic robotic manipulation problems (e.g., physical Blocks World [Li et al., 2020I). It is challenging to directly generalize our proof to scenarios where states and actions are continuous values because in these cases, there will be an infinite number of possible actions (e.g.. the choice of grasping poses, trajectories, etc.). We believe that it is an interesting question to investigate similar "width"" -like definitions in sampling and discretization-basee So far, we have only analyzed the circuit complexity of policies for individual planning problems; an interesting future direction is to extend these analyses to the learning and inference of "ggneral" policies such as large language models that can generate plans for many different planning domains.
continuous planning algorithms.
10

---

Acknowledgement. We thank anonymous reviewers for their valuable comments. We gratefully acknowledge support from ONR MURI grant N00014-16- 1--170 from the Center for Brain, Minds, and Machines (CBMM, funded by NSF STC award CCF-1231216), from NSF grant 2214177; from Air Force Office of Scientific Research (AFOSR) grant FA9550-23 2--50022-1--2 100--22-1---20 12-1-9 from ONR MURI grant N00014-22-1-274
from ARO grant W91 1NF-23-11-000 from the MIT-IBM Watson AI Lab; from the MIT Quest for Intelligence; and from the Boston Dynamics Artificial Intelligence Institute. Any opinions, findings, and conclusions recommendations expressed in this material are those of the authors and do not necessarily reflect the views of our sponsors.
References
Ron Alford, Vikas Shivashankar, Mark Roberts, Jeremy Frank, and David W Aha. Hierarchical Planning: Relating Task and Goal Decomposition with Task Sharing. In ICAI,, 2016. 10
Waiss Azizian and Mare Lelarge. Expressive Power of Invariant and Equivariant Graph Neural Networks. In ICLR, 2021.
Pablo Barceló, Egor V Kostylev, Mikacl Monet, Jorge Pérez, Juan Reutter, and Juan Pablo Silva. The logical expressiveness of graph neural networks. ICTR, 2020. 6, 10
Anthony Barrett and Daniel S Weld. Characterizing Subgoal Interactions for Planning. In IJCAI, 1993. 10
Davide Buffelli, Pietro Liò, and Fabio Vandin. SizeShiftReg: Regularization Method for Improving Size- Generalization in Graph Neural Networks. In NeurlPS, 2022. 10
Tom Bylander. The Computational Complexity of Propositional STRIPS Planning. Artif. Intell., 69(1-2): 165 204, 1994. 1, 10
Jin- Yi Cai, Martin Fürer, and Neil Immerman. An Optimal Lower Bound on the Number of Variables for Graph Tdentification. Combinatorica, 12(4):389-410, 1992. 6
Thomas Carta, Clément Romac, Thomas Wolf, Sylvain Lamprier, Olivier Sigaud, and Pierre- Yves Oudeyer. Grounding Large Language Models in Interactive Environments with Online Reinforcement Learning. arXiv:2302.0266 2023.
Hubie Chen and Omer Giménez. Act Local, Think Global: Width Notions for Tractable Planning. In ICAPS, 2007. 1, 5, 10, 15
Joseph Culberson. Sokoban PSPACE-complete. Technical report, University of Alherta, 1997. 2, 10 Honghua Dong, Jiayuan Mao, Tian Lin, Chong Wang, Lihong Li, and Denny Zhou. Neural Logic Machines. In ICLR, 2019. 1, 1,9, 10, 21
Dominik Drexler, Jendrik Seipp, and Hector Geffner. Learning Sketches for Decomposing Planning Problems into Subproblems of Bounded Width. In ICAPS, 2022. 10
Kutluhan Erol, James Hendler, and Dana Nau, HTN planning: Complexity and Expressivity. AAAI, 1994. 10
Richard E Fikes and Nils J Nilsson. STRIPS: New Approach the Application of Theorem Proving Problem Solving. Artif. Intell., 2(3-4):189-088, 1971. 2
Eugene C Freuder. A Sufficient Condition for Backtrack-Fre Search. JACM, 29(1):24 32, 1982. 15
Naresh Gupta and Dana S Nau. On the Complexity of Blocks-Worll Planning. Artif. Intell., 26(-3)) 1992. 10
Zhengyao Jiang and Shan Luo. Neural Logic Reinforeement Learning. In ICML, 2019. 9
Richard Karp. Reducibility among Combinatorial Problems. Springer, 1972.
Richard E Korf. Planning Search: A Quantitative Approach. Artif. Intell., 33(1):65 88, 1987. 10
Richard Li, Allan Jabri. Trevor Dareel,, and Pulkit Agrawal. Towards Practical Multi- Manipulation Using Relational Reinforcement Learning. In ICRA, 2020. 1,9, 10
Jacky Liang, Wenlong Huang, Fei Xia, Peng Xu, Karol Hausman, Brian Ichtor, Pete Florence, and Andy Zeng. Code as Policies: Language Model Programs for Embodied Control. arXiv preprint arXiv:209.00753, 2022.
Vladimir Lifschitz. On the Semantics of STRIPS. In Reasoning about Actions and Planx. Morgan Kaufmann, 1987. 2
Nir Lipovetzky and Hector Geffiner. Width and Serialization of Classical Planning Problems. In ECA/ 2012. IOS Press, 2012. 5, 10, 15

---

Zhezheng Luo, Jiayuan Mao, Joshua B Tenenbaum, and Leslie Pack Kaelbling. On the Expressiveness and Generalization of Hypergraph Neural Networks. In LoG. 2022. 6, 10
Christopher Morris, Martin Ritzert, Matthias Fey. William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and
Martin Grohe. Weisfeller and Leman Go Neural: Higher-Order Graph Neural Networks. In AAAI, 2019. 5,
Earl D Sacerdoti, Planning Hierarchy of Abstraction Spaces. Artif. Intell., 5(2):115-135, 1974.
Ashish Vaswani, Noam Shazeer, Niki Parmar. Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is All You Need. In NeurIPS, 2017. 1,5
William Vega-Brown and Nicholas Roy. Task and Motion Planning is PSPACE PSPACE-Complete. AAAI, 2020.
Tingwu Wang, Renjie Liao, Jimmy Ba, and Sanja Fidler. Nervenet: Learning Structured Policy with Graph
Neural Networks. ICLR, 2018.
Keyulu Xu, Weihua Hu, Jure Leskovee, and Stefanic Jegelka. How Powerful are Graph Neural Networks? In ICLR, 2019. 10
Keyulu Xu, Jingling Li, Mozhi Zhang, Simon S Du, Ken-ichi Kawarabayashi, and Stefanie Jegelka. What can Neural Networks Reason About? In ICI.R, 2020. 10
Keyulu Xu, Mozhi Zhang, Jingling Li, Simon Du, Ken-ichi Kawarabayashi, and Stefanie Jegelka. How Neural Networks Extrapolate: From Feedforward to Graph Neural Networks, In ICLR, 2021.
12

---

Appendix
The appendix of the paper organized as the following. In Appendix A, we provide the proof details and more discussion with related work on search complexity. In Appendix B, we provide the proof details and more discussion on policy circuit complexity. Next, in Appendix C, we include a detailed analysis of regression widths and circuit complexities for empirical planning problems. Finally, in Appendix D, we describe environmental setups and implementation details for the experiments.
A Proofs and Discussions for Search Complexity
A.1 Complete and Optimal Version of S-GRS
Algorithm 3 shows a complete and optimal version of the serialized goal regression search algorithm. The key difference between this variant and the simplified one presented in the paper is that now we keep track of multiple possible trajectories that can achieve the specified goal. The algorithm is complete because for any set of precondition atoms, in the optimal trajectory, there will always be an order in which they have been achieved (note that some of the sub-trajectories can be empty. indicating that while planning for the prefix the next subgoal has already been achieved; this covers the "parallel" precondition achievement case.). We show an example of this branching factor in Figure 4. Note that, to make sure that the algorithm eventually terminates, we need to make sure that all trajectories do not have loops.
However, this bare algorithm can be very slow: the worst time complexity of it is 0(3") with respect N, the number of atoms in Po in contrast 0(2%) for simpler backward search algorithm! This is because the possible state set for different subgoals and different constraints may overlap, so it will "waste" time during the search. Therefore, this algorithm may not be of practical use.
Algorithm 3 Serialized goal regression search with multiple optimal path tracking.
function GRSOPT( So. 8, cons)
if g E So then return (5p) all possible
empty_ setttsssstt_s
for r E Ry: cons n elf (action(r)) = A goal(r) = g do
pl, P2, ... PP subgoals(r)
Ap; s.t. P; E goal stack then
continue
possible_ (0)
for i in 1,2..... , do
next foll_possibl___ = empty_sepe s_e(() for prefix in possible do imm statsssttee-- = last past_ssate(prefix. for nt E GRsopr(inm_ssaate pt, cons U (PI.... Pi-l)) do
next_possible__ next_possible__ (prefix_ nf)
possible_ next coeut_possibler_
all possible 1 all possiblessspeeee 1 (t +I+T (lass_stateet).eom action(r)) possible r) return all _ol_soosible__
A.2 Proof for Theorem 3.1: S-GRS Optimality and Completeness
We define the set of optimally serializable rules for state as OSR(s), and the set of single-literal goals that can be solved with OSR(-) from as OSG(so).
Proof. Completeness: the definition of OSG(s)) asserts that g can be solved by S-GRS.
Optimality: proof by induction. In the following, we prove that for any g e OSG(sa), the trajectory returned by S-GRS is optimal.
Note that constraints is always subset of state state, the worst complexity is 0(3").
13

---

Subgoal: handsfree
Constraints: (n B), clear(C)
D
X
A
A F
A
(a) Current State
(b) 6 Different States that Satisfies the Subgoal and Constraints
Figure 4: Illustration of the branching factor caused by tracking multiple resulting states after achieving subgoal.
First, we consider the set of S-GRS calls the regression tree that contributes to the returned trajectory. We do induction based on distance metric. Consider any goal atoms g OSG(s)). let Distance(So, g. cons) be the length of the path returned by S-GRS. First, for all argument tuples with distance 0 (i.c.. $o and cons so), S-GRS will return the optimal trajectory.
Next, assuming that S-GRS will return optimal trajectories for all argument tuples with distances strictly smaller than d. Consider new argument call grs(So, goal, cons) with distance d. Consider now all optimally serializable and achievini rules r E OSR(sg) such that goal(r) g and cons n eff (action(r)) = 0. Let rg be the rule that returns the plan during search, and Pt ... Ps be the serialized precondition list. First, sub-function calls to S-GRS will return optimal plans by induction. Second, by optimal serializability of the rule r, we know that concatenating the sub-plans will yield an optimal plan to achieve g while preserving 8. Therefore, our induction holds.
A.3 Making Non-SOS Problem Serializable
Here we discuss general strategy to make non-SOS problems serializable by introducing super predicates. particular, for a given operator, two of the preconditions (without loss of generality, say, p(x) and q(x)) are not serializable, we can introduce new predicate _xx) and rewrite the precondition of the operator with this new super predicate.
The disadvantage of this encoding is that it will enlarge not only the predicate set but also the operator set. In particular, for any operator o such that p(x) E eff, or p(x) E (o). we need to break the operator into two sub-operators. For example, if p(x) E eff, (o), we need to create new operator o₁ that has =q(x) its precondition, and set (o = eff (o) and eff (01) eff=(o). For the second operator 02, it should have q(x) in its precondition and eff (o1) (o) (o) (p_ ip_and_____ ((x) and (o)) eff- (o). As the number of predicates this super predicate increases, the number of additional operators grows exponentially.
This provides characterization of "what contributes to the (forward) width of problem." " Specifi- cally, we have identified two sources of forward widths: non-serializabilit of certain operators, and the need track constraints while doing a regression search.
A.4 Proof for Theorem 3.2: Polynomial Hardness for SOS-k problems.
If a problem is of SOS width k, it can be solved in time O(N(+1), where N 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 2().
Proof. First, if we are given the rule set R, then the proof can be simply done by analyzing function calls: is important to observe that there are at most O(N*+1) possible argument combinations of (goal, cons) function GRS.
First, due to SOS condition, we only need to maintain one single optimal trajectory for each set of argument values (So. cons). Next, we consider only maintain single optimal trajectory for each pair of (goal, cons), ignoring the first argument Sy. Note that, even the "cached" trajectory does not include the input state So optimal serializability suggests that any trajectories for achieving (goal, cons) can be extended to future preconditions.
still return the cached trajectory. This is because the
Finally, we consider removing the assumption of knowing R. Note that the enumeration of possible goal width-k regression rules can be done in O which is considered constant when k is small.
14

---

Therefore, overall the algorithm runs in polynomial time and the solver does not need to know the set of optimally serializable regression rules R priori.
First, the fact that the algorithm does not need to know R a priori is important because it suggests that, as long as there exists a set of optimally serializable rules for the problem we are trying to solve, the search algorithm will find solution, without having any additional knowledge other than the operator definitions. Intuitively, this is because doing S-GRS with additional non-optimally serializable rules (e.g., using all rules in Ry) will not falsify the completeness and optimality of the algorithm.
Second, unfortunately, the SOS condition can not be relaxed. That is, we only assume optimal serializability of generalized regression rules and all rules have width k, the proof will fail. This is because even regression rules have a small width, there will be a possibly exponential branching factor caused by "free variables" in regression rules that do not appear in the goal atom. Concretely, This rule is of width O; however, since there is guarantee that any optimal trajectory for achieving P2(x) will also achieve Pi (x,y) A p2(x), during search, we can not use the cached trajectory for (p2(x), 0) as the return value when we solve for p2(x) after achieving pı y), which breaks the complexity analysis.
let us consider the following rule g(x) ** Pi(x, ()((x))))p>x') I| aı
A.5 Additional Discussion
Deriving aprimally-serializable, small-width rules. For a practical system, if we can know the set of regression rules needed, we can accelerate the search significantly. Here we discuss strategy for deriving such rules by analyzing the domain definition itself.
If we ignore the optimality, a sufficient condition that a rule is not strong optimal serializability for given state so is that, there exists a precondition p: such that there is no rule such that goal(r') p:. eff (action(r')) n = and goal(r) & subgoals(r") (r)) The last condition is the goal-stack checking: if achieving goal& g using rule r requires achieving goal g itself, then the rule not serializable.
Putting this into practice, consider all rules for achieving clear(A). If there is another object B on A in so, then only the rule derived from (Bstack(B,A) A) will be SOS serializable. This is because, for any other rules unstack(y, A), where y * B, achieving on(y, A) will involve achieving clear(A) itself. Note that this analysis can be done by static (lifted) analysis of the domain.
This analysis can be viewed as simulating a one-step goal regression search in lifted way, and can be extended to more steps. In some domains, this strategy will help rule out some serialization of the preconditions (such as the Blocks World example), but in general, whether a rule strong optimally serializable is state-dependent and can be hard to compute.
Connection with other concepts in search. Another view of the regression width is the maximum number of constraints one needs to track while applying S-GRS recursively. This notion is analogous to the treewidth of constraint graph in constraint satisfiability problems (CSPs): intuitively, the number of backward-pointing edges [Freuder, 1982].
As also briefly discussed in Lipovetzky and Geffner [2012], delete-relaxation heuristics are also related. In particular, the hFF heuristic can be interpreted as applying backward search by considering "parallelizability" in contrast to "serializabilityy" Informally, for given state and a sequence of preconditions pis we compute trajectories for each individual p; separately and concatenate them.
Generalization to Y-quantified preconditions. It would be possible to extend the definition to Y-quantified preconditions by simply allowing regression rules to have unbounded number of subgoals (e.g.. to handle goals such as Y xon-tabblex)). However, this is not helpful in general because the constraints will accumulate the number of subgoals becomes larger, and enumerating subgoal serialization will now take 0(m!) where m is the number of subgoals. This notion will be more helpful when we have a "goal regression rule selector."
A.6 Connection with Width-Ban Bast Forward Search IW(k)
Wecall the width of problem defined in Chen and Giménez [2007] and the Iterated Width algorithm IW(K) [Lipovetzky and Geffner, 2012] as forward width. Then we have:
15

---

Theorem A.1 (Sufficiency condition for forward width). Any planning problem that has SOS-width k has a forward width of at most k + 1 and, hence. can be solved by the algorithm IW(k 1).
Proof. We prove that for any trajectory returned by the S-GRS algorithm for an SOS width-k problem P. all actions in the trajectory achieve novel + I-sized atom set. this is true, then the final goal will be reachable from in the size k tuple graph in IW search.
Consider any action and a set of constraints cons. If the size k + 1 tuple (gl U cons has already been achieved before then due the SOS condition, we can make the returned plan shorter. This violates the optimality of the S-GRS algorithm.
the returned plan, it corresponds a unique rule for achieving subgoal
Unfortunately, these two definitions are not exactly equivalent each other. For example, consider the Blocks World domain and state of three stacked blocks A, B and C, the goal regression rule
clear(A) om on A), clear(B) handsfree()cceerte (ocearrB unstack(y,
is SOS. It has width because while achieving handsfreeO, we have to explicitly maintain clear(B); otherwise, is possible that we directly put back onto B instead of putting C onto the table (both plans are optimal for achieving handsfree() after achieving clear(B). By contrast, in IW, the Blocks World domain has width instead of the goal predicate is clear, because the optimal plan for achieving (andsfree()fnlerrBe happens to be the optimal plan for achieving on-table(C).
Proofs for (forward) widths of planning problems in IW were mostly done by analyzing solution structures. By contrast, the constructions in this paper form a new perspective to interpret planning problem width: they are subgoals and constraints that need be satisfied during a goal regression search. This view is helpful because our analyses focus on analyzing concrete goal regression rules, and the derived results are compositional. Unfortunately, not all problems that can be solved by /W(k) have a regression width of k - 1.
16

---

B Proofs and Discussions for Policy Circuit Complexity
B.1 Proof of Theorem 4.1: Compilation of BWD
Given a planning problem P, let T be the length the optimal trajectory as (the planning horizon), kawD be the maximum number of atoms in the goal set in BWD, and ß be the maximum arity of atoms the domain. The backward search algorithm BWD can compiled into a relational neural network in Re/NN(O(T), k.wD].
Goal is set of conjunctive formula.
Residual
State: on, clear
State: on, clear,
ReINN Layer
ReINN Layer
Next Action Prob. unstack(D, C)
Goal (on(B, A)}
Goal
(clcar(A) A holding(B)) (Until Esg.sg Goal Asg S s)
Figure 5: Illustration the compilation of backward search into a RelNN policy.
Proof. There is a proof by construction. As illustrated in Fig. a relational neural network can use its intermediate representations to keep track of a set of subgoals (i.e., set of sets of ground atoms) Goal at each layer d. Initially, Goal contains only the goal atom. Then, sg E Goal there is path of length d from any state s that satisfies sg S s to the final goal of the planning problem. For all layers d, for any subgoals sg, for ground actions a E A, sg E Goal A (sg U pre(a) (a)) E Goa Since the maximum number of atoms in BWD kgwD, we only need to keep track of ground atom conjunctions that involve at most kBwD B distinct objects. Therefore, BwD search can compiled into a relational neural network in RelNN[O(T), kBwD- -B].
0) =
more detailed construction is the following. Let K' = kBWD B. Let xi.... Xx be variables. (q((),.... .gg) is the set all possible conjunctive expressions that involve variables (x,,-.. .xv). Let q (x,,". Xx) be the value of qxx,,... xxx) at layer d, and expr(q,) be the conjunctive expression of qi- For all d, qj. and for all actions a that are grounded on variables from expr(q)) pre(a) eff,(a)), there (d+1)) (x),-..,.
(x),.... }. if (eff_ (a) n expr(q))
0) (expr(q)) .xe) logical rule: Vxi, .x. xp. (x....... .x)) = 9
Furthermore, for all d, qi (eff_(a) n expr(q)) = 0) A (expr(q)) U pre(a) eff. (a) c s), where s the current state, we have the following rule that outputs the next action to take, Vxi. .xp. 9. (x) ... xx.) = ddd+1), where d = indicates that there exists length d trajectory for achieving the goal. In practice, we will the
shortest one. Note that all these rules are fully quantified by Vxl, Np so they are lifted FOL rules and can be implemented by RelNN circuit.
B.2 Proof of Theorem 4.2: Compilation of S-GRS
Given a planning problem SOS width k, let T be the length of the optimal trajectory, and B be the maximum arity of atoms in the domain. The serialized goal regression search S-GRS can be compiled into a RelNM(O(T), (k + 1)- B), where + kBwD-
Proof. There is a proof by construction. The easiest construction is based on the sufficient condition between regression width & and ZW(k). In particular, based on Theorem 3.3, we know that /W(k + 1) can solve the planning problem P. Therefore, we can use the following construction to simulate IW(k + 1).
The most important trick the construction that a relational neural network can use intermediate representations to keep track of two sets of atoms. First, for each atom tuple up size & 1, whether is reachable from So within steps. Second, let s, be the last state of the optimal trajectory associated with for each atom tuple up to size k + and for predicate X2x),2,,"" .3p),
17

---

... .xx) is true in At each layer d, we consider all possible ground keep track of whether P( X2. actions a A, if there exists such (4, f2) such that 12 is not reachable within d steps and S 7 (s.,.a). a), we set f2 to be reachable within d + and Si;" = :))
In addition the realizability of the /W(k 1) algorithm, we need to additionally prove that, if we follow the policy derived by simulating 7W(k + 1) for the first step. we can recurrently apply this policy, To see that, consider the path from so to the goal state in /W(k+ 1) in the tuple graph. Since we are moving forward by one step in this tuple path, doing a search from the second tuple in the path (i.e., applying the same ReINN policy at the second world state) will yield the same trajectory.
Similar to the construction in Theorem 4.1, all the rules are lifted FOL rules and can be implemented by a ReINN circuit. It is also possible to use the same trick to compile the original S-GRS algorithm: essentially, for each (g, cons) pair, keep track of the optimal trajectory for achieving it. However, the construction will be more complicated and is omitted here.
B.3
More Discussion
For some problems, even if we have regression rule selector, compute a plan, we may still need an unbounded depth of search steps (i.e., d depends on the number of objects in the domain). For example, Blocks World, to achieve cleur(A), A), the number of steps needed is proportional to the number of objects on top of A. There are two ways to build relational neural network policy in this case. First, we can allow the network to have variable number of iterations by applying the same layer recurrently several times. We have already illustrated this in the experiment.
Second, there might be "shortcuts" that we can learn. An intuitive example is that in Blocks World, the goal regression for clear(A) A) will recur until we have found the topmost block stacked on top of A. the domain has new predicate above(x.) y) indicating whether the block x above another block then we can use just one single rule to predict the topmost block on top of A: the topmost block B on A satisfies above(B, A) A clear(B).
The same technique also applies to the problem of path-finding in any acyclic maze. Recall that classical solution any acyelic maze is that we only make right turns. This be cast linearization of the entire maze by doing a depth-first search from the start or the goal location. In particular, starting from the goal location if we only do right turns, we will get a sequence of the edges of the maze such that the start edge is one of the elements (if there is path from the start to the goal). Therefore, doing goal regression under this linearized maze is trivial: the entire "regression tree" is just chain of edges and there is a simple shortcut for predicting the next move.
18

---

C Analysis of AI Planning Problems
Here, we list six popular problems that have been widely used in Al planning communities and discuss their circuit depth and breadth. We summarize results in the Table 3.
Problem
Breadth
Regression Width
Depth
Blocks World
Constant
Unbounded
Logistics
Constant
0
Unbounded
Gripper
Constant
Constant
Rover
Constant
0
Unbounded
Elevator
Constant
Unbounded
Sokoban
Unbounded
N/A (not serializable)
Unbounded
Table 3: Width and circuit complexity analysis for 6 problems widely used in Al planning communi-
ties. This table contains the same content as Table I; we include here for easy reference.
Note that here, we are limiting our discussion to the case where the goal of the planning problem is a single atom. In summary, most of these problems have constant breadth (i.e., the regression width of the corresponding problem is constant) except for Sokoban. Most problems have an unbounded depth: that is, the depth of the circuit will depend on the number of objects (c.g., ... the size of the graph or the number of blocks. The problem gripper has a constant depth under a single-atom goal because it assumes the agent can Sokoban has an unbounded breadth even for single-atom goals because if there are multiple boxes blocking the way simple rules. The constant breadth results can be proved by construction: list all regression rules in the domain. In the following Appendix C.I, first discuss the SOS width of two representative problems, Blocks World and Logistics. All other problems can be analyzed in a similar way.
directly between any rooms; therefore, no pathfinding is required.
designated position, the order move the boxes not be determined by
Before delve into concrete complexity proofs, would like to add the note that for problems in this list, when there are multiple goals, usually the goals are not serializable (in the optimal planning case). This can be possibly addressed by introducing "super predicates" that combine two literals. For example, if two goal atoms p(x) and q(x) are not serializable, we can introduce a new predicate p p_and p_and_g(x), (x),, and rewrite all operators with this super predicate. Appendix A.3 provides more discussion and examples. This will make the problem serializable but at the cost of significantly enlarging the set of predicates (exponentially with respect to the number of goal atoms).
we only care about satisficing plans, for Logisties, Gripper, Rover, and Elevator, there exists simple serialization for any conjunction of goal atoms (basically achieving one goal at time).
These theoretical analyses can be used in determining the size of the policy eircuit needed for each problem. For example, one should use ReINN of breadth (k 1).B, where is the regression width and B the max arity of predicates. For problems have unbounded depth, usually the depth of the circuit grows in O(N), where N is the number of objects in the environment (e.g., in Elevator, the number of floors).
19

---

C.1 SOS Width Analysis
To prove that problem be solved optimally using S-GRS, we only need show that there exists a goal regression rule selector. Therefore, we will be using the syntax from Section 4 to write down the set of goal regression rule selectors.
Finite SOS width for Blocks World.
Icons. xx. Xy.oy,yyyy x) so clear(x) en only, x), clearry), handsfreee) || unstack(y, x)
Mcons. V (xhodiing())) clear(x) come en holding(x) place-table(x)
x.ons.x.Vy..oxx... so hoding(x) (x) comss on(x, y), clear(x), handsfree() unstack(x,)) y)
Vcons. (x.) hoding( c) on on-table(x), clear(x) pick-table(x)
Ycons. 4x. on-table(x))nm
holding(x) place-table(x)
Xx.ns.Xx.Yy on(x, y) on clearly), holding(x) || stack(x,
Vcons. xcoosi.x.h)lding(3)) so handsfree() on holding(x) Il place-table(x)
Finite SOS width for Logisties.
Vv.ns.Vv.Ver Vo.V.. al(o, C) on in(o, v), at(y, II unloadly, x)
Vcons.Vv Vv.Vo.. in(o, v) on atlo, 6), at(v, E) x) Vcons.Vv.C..M2... allv, cons loc(f1, c), loc(l,,)), a), (i) drive((, (2.)) Vvons.Vv.a,..e Vaz, at(v, a)) coms em al(v, a)) fly(v.a..2))
Here, we have omitted static properties for type checking (such as and need to be airports).
20

---

D Experimental Details
D.1 Training details
Environment setup. For the Assembly3 task, first uniformly sample the set of type-A, type-B, and type-C object. Then, we randomly add match relationships so that there will be exactly only one tuple of (a, c) that satisfies the matching condition.
For the Blocks World-Clear task, we use the same random sampler for initial configurations as Neural Logic Machines [Dong et al., 2019]. It iteratively adds blocks randomly selects a clear object (or the table), and places a new object on top of it. After generating the initial state, randomly sample object that is not clear in the initial state as the target block.
empty initial state. At each step,
For the Logisties task, we first randomly generate a tree rooted at the start node. This is done by iteratively attaching new nodes to a leaf node. Next, randomly add small number of edges to the tree. Finally, we randomly pick node as the target node. Since we are only small number of additional edges added to the tree, with high probability, the starting node and the end node are not in the same strongly connected component.
Additional hyperparameters. The breadth, width, and hidden dimension parameters for neural networks have been specified in the experiment section and they vary across tasks. For all experiments, we use the Adam optimizer train the neural network, with a learning rate of e 0.001. Additionally, we set B1 = 0.9 and B2 = 0.999.
Compute. We trained with 1 NVIDIA Titan RTX per experiment for all datasets, from an internal cluster.
Code. We release the code for reproducing all our experimental results in http::/gittuub.cm/ coneppsaiiggalleerssoonniiiii width.
21


Reviews:
[{"review_id": "k6MS32B5vy", "reviewer": "Reviewer_bz43", "summary": "The paper presents a mapping from tractable but incomplete algorithm classical planning into circuits that can be represented by a class of neural networks called relational neural networks RelNN including transformers architecture and graph neural networks. The paper is divided into two parts.\n\nThe first part presents an extension of Chen and Gomez [CG2007] that introduced a notion of width, in turn, related to the more practical notion of width proposed by Lipovetzky and Geffner [LG2012]. The change is about using regression search –not a big change given that as a theoretical algorithm– while keeping the same idea of keeping track of a reduced context.\n\nThe second part considers how to map policies based on those algorithms –given a set of regression rules– into a RelNN. The paper discusses the size of the required network in different cases. The best scenario is when the size of the NN doesn't grow linear with the size of the problems. Using the ideas of the first part, the paper shows how can that be expressed as a RelNN. Preliminary empirical results over a set of problems suggest a MLP is learning a policy that matches the ideas of the paper.   ", "questions": "- What's the goal stack in the algorithms?\n- How are the objects encoded in the RelNN?\n\t- What's the difference/similarity in the encoding of problems where the policy have bounded vs unbouded depth?\n- Is the encoding the same for two problems where we interchange the name of two objects? For instance, rename A s B and B as A in a blocks world problem.\n\t- Might such renaming have any effect in the experiments?\n- Are MLP per se part of the class of relational NN?\n- How are the problems and outputs encoded in the MLP?\n- The proof of 4.3 says that rules include \\rho, any kind of FOL. Lemma 4.1 refers to  FOL but only restricts the number of variables.\n\t- How does D change with the complexities of the formulas?\n- In thm 4.3, why does the breath only grows with max(B_r, max arity of predicates)?\n\t- Perhaps it's because the preconditions are evaluated once at a time, but the end of the proof says \"\\beta is required to store the input state\". A state includes more than one predicate.", "limitations": "This is a very interesting line of work combining results in different areas. The theoretical arguments focus on the existence of a bound, there is little formal study or intuition of how the complexity grows across different problems. For instance, if conditions are free FOL, for a fixed number of variables and objects, then the resulting circuits can have many different sizes.\n\nIn general many intuitions are hidden in the proofs ideas and not in the main text. That's a possible reasonable decision, but sometimes the key intuitions are hidden there and not connected with the overall picture.\n\nLacking intuitions, the empirical study offer some light in this direction, but a reader in NeurIPS might need further details on how this was done.\n\nFinally, I think this would be a better paper with a more clear distinction between problems and domains. Previous work using the notion of width tends to discuss it across a class of problems. In that setting, providing or obtaining a set of rules is more clear that for solving a single problem. The set of rules might be very different for subsets of problems. (For instance, blocks world instances where all the blocks start at the table). That framing would allow to establish connections with work in learning for generalized planning. \n\nFor that reason and others, this one is a very relevant reference:\nLearning Sketches for Decomposing Planning Problems into Subproblems of Bounded Width. Dominik Drexler, Jendrik Seipp, Hector Geffner.\nICAPS 2022.\nhttps://arxiv.org/abs/2203.14852 \n\nAll in all, I learned a lot from the paper. That's a positive sign.\n\nMinor point(s):\n- why can serialization be incomplete? Perhaps explaining this might be useful: https://en.wikipedia.org/wiki/Sussman_anomaly\n", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 2, "contribution": 2, "strengths": "- Innovative combination of tractable planning with the expressivity of some NN. Serialization is a suggestive idea for a tractable fragment for planning.\n- The idea of 'regression rule selector' might be hard to use in an effective symbolic algorithm. Framing it as learning is an innovative idea.\n", "weaknesses": "- The paper offers little insight into how depth and breadth behave in different problems. In particular, it's not clear how the complexity of the rules is related to that. Perhaps a better title for the current manuscript would be \"Relational Neural Network can Solve some Planning Problems\", as the paper does not help to identify what problems can be solved except by trial-and-error. That might be a good contribution, but then the tone of the paper might be different.\n- The paper doesn't clarify whether the goal of the approach is to solve a single problem or problems from a domain.\n\t- For instance, the width of [LG2012] refers to problems, but then they discuss width across instances of a problem.\n\t- This might be easily fixed in the next discussion.\n- Experiments cannot be replicated as we lack details.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your helpful comments!\n\n**Q1:** Replication of experiments.\n\n**A1:** Thanks for the suggestion. We will extend Appendix C to include more details. Also, we have released an anonymized version of the code with the supplement (since NeurIPS rebuttal does not allow for URLs, please check our Appendix D for the link).\n\n**Q2:** What's the goal stack in the algorithms?\n\n**A2:** Recall that both BWD and GRS are depth-first search algorithms. Here, \"goal stack\" means all the `goal` (or `goal_set`) arguments in the function calling stack. We will clarify that in the revision.\n\n**Q3:** How are the objects encoded in the RelNN?\n\n**A3:** In RelNNs (e.g., graph neural networks), the state is represented as a graph (objects are nodes and relations are edges; possibly there will hyperedges for multi-ary relations). Therefore, the objects are encoded as node indices. For example, the input contains nullary features (a single vector for the entire environment), unary features (a vector for each object), binary features (a vector for each pair of objects), etc. They are usually represented as tensors.\n\n**Q4:** What's the difference/similarity in the encoding of problems where the policy has bounded vs unbounded depth?\n\n**A4:** We use the same encoding style for all problems (the graph-like relationship). Therefore, whether different problems have bounded or unbounded width primarily depends on the available goal regression rules, how these rules can be serialized, and the width of the rules.\n\n**Q5:** Will changing of object names affect results?\n\n**A5:** No. In all our experiments, objects do not have names / identity information exposed to the neural network. This is related to the \"permutation-invariance\" of RelNNs, which means that any permutation of the input object set will not change the model performance.\n\n**Q6:** Is MLP a RelNN?\n\n**A6:** Yes, MLP is a \"degenerate\" RelNN with breadth 0. That is, the entire state is represented as a single vector.\n\n**Q7:** How are the problems and outputs encoded in the MLP?\n\n**A7:** We assume you meant to ask how problems and outputs are encoded in the relational neural networks. Here, the inputs to the neural network are tensor representations of the current state (e.g., $N\\times N$ matrices for a predicate of arity 2, where $N$ is the number of objects). Since we assume that the goal contains only one single atom, goals can be encoded as tensors too. For example, suppose that our goal is on(obj1, obj2), then it can be encoded as a matrix where only the entry corresponding to the pair (obj1, obj2) is 1; all other entries are 0.\n\n**Q8:** Depth bounds in Thm 4.3.\n\n**Q8:** Thank you for pointing this out! We plan to add more intuition for both Lemma 4.1 and later theorems. In short, there is a constructive proof for using RelNNs to realize FOL formulas. The breadth B is the number of variables in FOL, the depth D is the number of \"nested quantifiers\" in an FOL formula. For example, the formula `exists x. forall y. p(x, y)` needs two layers while `exists x. forall y. forall z. p(x, y, z)` needs 3. We will also clarify that the FOL formulas in $\\rho$ should be realizable by a RelNN with constant depth and breadth.\n\n**Q9:** Breadth bounds in Thm 4.3.\n\n**A9:** The intuition is that, if there are multiple preconditions for different rules, they can be evaluated \"in parallel\" and do not lead to larger breadth than individual rules: recall that breadth is actually the \"arity\" of edges in the graph. If we have many rules, we can increase the \"hidden dimension\" for each edge representation. Similarly, for state encoding, if we have multiple (say, 8) predicates (say, of arity 3), we can represent them by a tensor of size $N \\times N \\times N \\times 8$, where $N$ is the number of objects in the state. Here, we say the breadth of this representation is 3, because it needs $O(N^3)$ memory to encode.\n\n**Q10:** Limitations on missing intuitions behind proofs and how complexity grows across different environments. \n\n**A10:** Thank you for suggesting these. We will try our best to use the additional page in NeurIPS camera-ready version, if the paper gets accepted, to include more intuitions behind theorems and definitions. Based on your suggestion, we also added ...\n\n**Q11:** Distinction between problems and domains.\n\n**A11:** Thank you for the great suggestion! We will definitely incorprate this suggestion in our future revision. Concretely, we plan to add a definition for \"problem classes\" composed of problems that share the same domain (e.g., transition model) but vary in $s_0$ and goals. And then, we will discuss width of problem classes and policy complexities for problem classes.\n\n**Q12:** References.\n\n**A12:** Thank you for the references! We will cite the Drexler et al. paper on learning sketches: their idea of sketch is definitely related to our goal regression rule. The key differences are: their skeches can be viewed as high-level, feed-forward policies. By contrast, in our conditional rules, there might be multiple rules applicable at the current state, so search is still required. We will also use the Sussman anomaly example to illustrate the idea of incompleteness.'\n"}, {"review_id": "gy8qIY6yqS", "reviewer": "Reviewer_aaQH", "summary": "This paper discusses the expressivity of classical relational architectures and its implication for solving planning problems. In particular, the authors identify characteristics of the environments that make planning hard. They prove a theorem that bounds the size of a network sufficient to solve the problem of planning perfectly, under some assumptions on the underlying domain. Finally, they show experimental results in two simple environments.", "questions": "l.99 It's very convenient that you explain the discussed properties with an example. However, it would be even better if you briefly explained the meaning of actions. Although after reading I know what _clear_(A) means, explaining it at the beginning would be helpful. Also, generally, there is no precise description (even brief) of the BlocksWorld environment in the paper.\n\nl.114 Please refer to a specific appendix.\n\nl.124 I'm not sure if the provided intuition is correct. As far as I understand, it should be \"A rule is optimally serializable if any optimal trajectory extended with an optimal continuation forms an optimal plan.\" That is, the intuition described in the paper suggests just an existence of $a_2$. Is that correct?\n\nl.130 Does Theorem 3.1 have proof? Please, provide a reference.\n\nl. 317 It would be nice to show how the presented theory should influence design choices when using relational networks. For instance, I suggest providing a list of environments with a short explanation of their properties (finite/unbounded depth, serializability, width, theoretical bounds values, implications, etc.), even without experiments, even in the appendix. The discussion provided in l.305-317 is a good starting point. The discussion in the appendix (again, no reference) is also nice, but I believe it can be extended. Notably, with more examples. This way the theory you provide could be much more impactful.\n\nl.324 I like that you provide experiments both for theoretically bounded and unbounded depth. However, it's a shame that it turns out that unbounded depth is actually no bottleneck. In general, it's good to show such an environment, but here I'd like to see an experiment in an environment with truly unbounded depth and witness the growing success rate up to a practical bound. Because BlocksWorld actually requires little complexity, there is no experiment that links your theory with practice. How about BlocksWorld with a limited number of stacks? But it may fall in the category of \"resource constraints\", is that a problem? Actually, I do want here an environment with a _small_ but not _extremely small_ circuit.\n\nl.334 What does it mean that a model has breadth 2? Does it mean that a layer has 2 neurons? I suppose not, please clarify that.", "limitations": "The limitations are briefly discussed in the conclusion. Negative societal impact is not an issue with this work.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper is very clear and easy to follow. It's very convenient that you provide intuitive explanations of the derived theorems and explain them in an example environment. The motivation is clearly stated in the introduction. The problem is interesting and deserves a study. The presented results are novel and provide a deeper understanding of the capabilities of widely used architectures.", "weaknesses": "In my opinion, the greatest weakness of this paper is an insufficient discussion of the connection between the formulated theory and practical applications. I understand that the contribution of the work is mostly theoretical. Anyway, it would be nice to show how the presented theory should influence my design choices. For instance, I suggest providing a list of environments with a short explanation of their properties (finite/unbounded depth, serializability, width, theoretical bounds values, implications, etc.), even without experiments, even in the appendix.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your helpful comments!\n\n**Q1:** Connections to practical problems.\n\n**A1:** Thank you for the suggestion. We have included a new discussion of 6 popular problems that have been widely used in AI planning communities and discuss the circuit depth and breadth of them. We summarized their regression width, circuit depth, and circuit breadth in the following table. Please refer to our general response for more discussions (e.g., finding optimal plans vs. finding satisficing plans). These results can indeed be used in choosing neural network hyperparameters (e.g., the depth). We hope these discretized/simplified versions of practical problems can give us insight into their relative difficulty.\n\n| Problem     | Breadth   | Regression Width | Depth    |\n| --------    | --------  | ---------------- | -------- |\n| BlocksWorld | Constant  | 1 | Unbounded |\n| Logistics   | Constant  | 0 | Unbounded |\n| Gripper     | Constant  | 0 | Constant  |\n| Rover       | Constant  | 0 | Unbounded |\n| Elevator    | Constant  | 0 | Unbounded |\n| Sokoban     | Unbounded | N/A (not serializable) | Unbounded |\n\n**Q2:** Clarifications on the Blocks World environment and appendix references.\n\n**A2:** Thanks for the suggestion, we will include descriptions of the state representations in the BlocksWorld example, and put exact section numbers when we refer to appendices.\n\n**Q3:** L124, intuition about the goal regresion rule.\n\n**A3:** Thanks for catching that! Your intuition is correct and we will update the manuscript.\n\n**Q4:** Proof for Theorem 3.1.\n\n**A4:** Yes, the proof was attached in Appendix A.1. We will add an reference.\n\n**Q5:** Experiments showing the importance of truly unbounded depth.\n\n**A5:** Thanks for the suggestion! We totally agree that there should be an additional environment better showing the importance of unbounded depth.\n\nIn addition to the \"no resource constraint\" feature you mentioned, there is another aspect of BlocksWorld that makes finding a satisficing plan easy: non-existence of deadends (as long as you keep moving objects down to the table, you will eventually make the target object clear). An environment is that does not have this structure is Logistics (or any graph path problem in a non-strongly-connected graph).\n\nIn particular, we constructed a simple Logistics domain with only cities and trucks (no airplanes), and we construct the graph so that it's not strongly connected (by first sampling a directed tree and then add forward-connecting edges). Similar to other models trained in the environment, we train the policy network on problems with less than n=10 cities and test it on n=30 and n=50. The results are summarized below (with f(n)= n/5 + 1).\n\n| Model | n = 10 | n = 30 | n = 50 |\n| -------- | -------- | -------- | -------- |\n| RelNN(3, 2) | 1.0  | 0.30 | 0.23 | \n| RelNN(f(n), 2) | 1.0  | 1.0  |  1.0 |\n\nThe results show that having an unbounded depth circuit is important in learning a generalizable policy in this domain. We will add code for reproducing this experiment to the released code.\n\n**Q6:** L334 Breadth.\n\n**A6:** Breadth means the maximum arity in the relational representation. Breadth 2 means that in the RelNN, there is a vector representation between each pair of objects. For the \"number of neurons\", we use 64 for all experiments, which should be sufficiently large for the particular domains we are considering.\n"}, {"review_id": "VVOefWuaf0", "reviewer": "Reviewer_7eTK", "summary": "The paper explores the application of relational neural networks, seen as circuits, in representing policies for discrete planning problems. Specifically, it introduces a circuit complexity analysis that categorizes planning problems into three classes based on how circuit width and depth grow, by establishing connections with serialized goal regression search (S-GRS), which is a method for generating plans by working backwards from goals. In essence, the main contribution of the paper is that it combines previously introduced planning problem complexity related quantifications (width, depth) with circuit/policy complexity analysis to analyze the resource/representation requirements of policies. This analysis helps to better understand the capabilities of relational neural networks in solving planning problems, which in turn helps designing them for policy learning. By analyzing goal-conditioned policies for such planning problems, upper bounds on the circuit complexity of such policies are provided as a function of the problem's regression width. The experimental results support the theoretical formulations and demonstrate the practical applicability of the proposed approach for relatively small sized/simpler discrete planning problems. ", "questions": "- What are the main bottlenecks/issues to apply this formulation for continuous planning problems, e.g., such as the ones in robotics?\n\n- Would this analysis and construction be still useful/practical for larger/more complex problems, which require larger networks? If yes, how? \n\n- The problems investigated are solvable by classical search/planning methods, then what’s the advantage of using a RelNN that was constructed based on the provided analysis?\n\n- Serialization of goal regression rules seem to be highly related to mathematical optimization / dynamical programming. Can you elaborate on this connection? \n", "limitations": "- Limitations of the work have been barely touched upon on the paper. \n\n- The discussion on applying this formulation to continuous planning problems, e.g., in robotics, can be extended. \n\n- In general, an evaluation and discussion on the type of problems that the proposed formulation is not applicable to would be nice.\n", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- Originality: The paper proposes a new perspective for circuit complexity analysis for relational neural networks (GNNs, transformers), and thus what they can compute (i.e., their limits). \n\n- Quality: The proposed method is supported by theoretical analysis and proofs. A small set of experiments were conducted to validate the approach.\n\n- Clarity: The order of presentation is mostly nice, even though the terminology used throughout the paper sometimes makes it hard to follow. \n\n- Significance: Helpful for constructing relational neural networks for planning problems, and the proposed formulation can also help investigate solutions to planning problems for future works in this area. If the problems analyzed had a broader scope, it would have increased the overall impact of the paper.\n", "weaknesses": "- Lack of a convincing set of quantitative results: Proposed methods might be tested on different networks and problems (only two different problems and networks are presented). \n\n- A broader discussion of the applicability of the proposed analysis and formulation on different planning problems, especially to real-world (e.g., robotics) scenarios, would help convince the reader about the impact of the paper. \n\n- Related work section might be placed earlier (e.g., after introduction) for better placing this work w.r.t. the literature. \n\n- Supplementary material helps clarify some points, due to page limit it is hard to integrate this information but for clarity there might be more reference to it within the main text.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your helpful comments!\n\n**Q1:** Quantitative results:\n\n**A1:** Our main objective in this paper is to formally clarify the nuances of when relational neural network circuits can realize a policy for specific planning problems, and to understand the size of the circuits necessary to achieve this. We begin by exploring discrete planning problems. We hope our preliminary quantitative findings do provide some initial insights into practical algorithms. In our answer to your next question, we briefly discuss additional challenges that we might encounter when we shift towards constructing policy architectures and learning within more realistic frameworks, such as robotics.\n\n**Q2:** Analysis and construction for larger/more complex problems.\n\n**A2:** The theorems and constructions are general, so they apply to problems of any size. However, to build practical systems that plan in very large domains, additional methods for abstracting and factoring the planning problem, e.g., via hierarchical decomposition, will be crucial for efficient solutions.\n\nNeural network architecture: prior work [1] has demonstrated how different aggregation functions in graph neural networks carry different inductive biases. An intuitive example is that max-pooling over node features can act as an \"existential\" quantification, whereas mean-pooling can act as a majority voting. These considerations become crucial when tailoring solutions to specific problems.\n\nOf course, as the necessary circuits get more complex, the NN training may become more difficult. Also, more training data might be needed to provide something close to a \"complete presentation\" of the problem so that the RelNN can learn all regression rules in the domain.\n\nWe'd like to emphasize that our work is an attempt to bring us a step closer to a comprehensive understanding of learning and planning with object-centric representations. We hope it will pave the way for future explorations.\n\n[1] Keyulu Xu et al. How Powerful are Graph Neural Networks? In ICLR, 2019.\n\n**Q3:** Applicability in real-world scenarios.\n\n**A3:** Thanks for bringing up this question. We will extend the discussion in future revisions. The proposed analysis and formulation does generalize directly to \"real-world\" settings (e.g., object features should be extracted from visual perception inputs) if we assume the input state can be represented in an object-centric, and discrete manner (a.k.a. as logic \"predicates\"). For example, [2] has implemented relational neural network architectures for BlocksWorld from visual inputs.\n\nIt is challenging to generalize directly to scenarios where state variables and action parameters are truly continuous (e.g., in robotic manipulation tasks). The intuition is that, if actions have continuous parameters, there will be an infinite number of possible actions available at each state (depending on the choice of grasping poses, object placement poses, etc.). Therefore, the depth-first-search-based algorithm used in this paper will not work. Consequently, our policy compilation strategy will not work.\n\nRobotic manipulation problems can generally be more computationally complex than the discrete problems we studied because they can certainly contain those discrete problems as a sub-problem (e.g., a \"robotic\" blocks world). Meanwhile, any robotic planning problem that involves moving an articulated object with many links among many polygonal obstacles is PSPACE-complete [3]. Therefore, there are no efficient exact algorithms for these problems; many motion planning algorithms, for example, rely on sampling and discretization. However, how to better produce samples/discretize the space is generally hard. We believe that it is an interesting question to investigate similar \"width\"-like definitions in sampling and discretization-based continuous planning algorithms.\n\n[2] Richard Li, et al. Towards Practical Multi-Object Manipulation Using Relational Reinforcement Learning. In ICRA, 2020.\n\n[3] William Vega-Brown and Nicholas Roy. Task and Motion Planning is PSPACE-Complete. In AAAI, 2020.\n\n**Q4:** Paper organization, supplementary materials and links. \n\n**A4:** Thank you for suggestions. We will try our best to use the page in NeurIPS camera-ready if the paper gets accepted to include more intuitions, and definitely add links.\n\n**Q5:** The advantage of using a RelNN.\n\n**A5:** Thanks for raising this point. There are two major advantages of learning a RelNN. First, when domain is known (in STRIPS), the RelNN will have computation time O(depth of the circuit), due to its parallel execution nature. This is generally more efficient than running the classical planning algorithm. Second, there are scenarios when the domain is unknown to the agent, then RelNN is a method that supports learning policies from interactions or demonstrations. For example, consider an agent that is learning to play Minecraft, in which case we know that some crafting rules (e.g., in order to build an axe, we need wood planks and iron ore) have certain forms and thus can be serialized and have low width, but we still need to perform exploration in the environment to learn those rules.\n \n**Q6:** Serialization in mathematical optimization and dynamic programming.\n\n**A6:**  Serialization is strongly related to hierarchical decomposition, in which we assume we can solve some subpart of a problem without worrying about the rest of the problem. The connection to dynamic programming (in which we re-use solutions to subproblems in order to solve a bigger problem) is less clear to us, but it definitely bears additional thought!\n\n**Q7:** Applicability of the proposed formulation.\n\n**A7:** In this paper, we address the class of planning problems that can be formulated in atomic STRIPS. That is really only a small set of all interesting planning problems, and does not address continuous state/action spaces, stochasticity, partial observability, execution actions in parallel, etc."}, {"review_id": "1dbqx8SopA", "reviewer": "Reviewer_TK6j", "summary": "\nThis paper focuses on formalizing what class of planning problems can be solved by a relational neural networks. It aims to bridge the gap between the expressivity of relational neural networks and the complexity of planning problems. To do this, a serialized goal regression rule and search algorithm is defined. Three classes of planning problems are defined based on the serialized goal regression search and show these classes can provide network parameters for relational neural network. Experiments with two planning domains show the empirical implications of the results.", "questions": "**Major**\n\n\n1. Algorithm 1 \n    1. Plain backward search should satisfy two conditions for selection of action: $g \\cup eff_{+}(a) \\neq  \\emptyset$ and $g \\cup eff_{-}(a) = \\emptyset$. The second condition is captured in the Algorithm. But the first is not.\n   1. Action should be mentioned as input in Algorithm 1. \n   1. `goal stack` is not defined\n1. Algorithm 2\n    1.  $R_o$ should be part of the input\n    1.  `goal stack` is not defined\n    1.  `goal_set` is not defined\n    1.  Is $\\pi$ a plan? If so, $\\pi[-1]$ is the last action. So is $s_i$ an intermittent state or action? \n    1.  If any of the $p_i$ is available in the goal stack, then that branch is not explored in the backward search? What is the benefit of doing that?\n1. Line 107 mentions that there will be a goal regression rule for any possible permutation of pre(a), but as explained in Line 100 all of these are not feasible. Will the regression set contain infeasible rules as well?\n1. How are the generalized goal regression rules identified? For example, consider the rule in Line 139. Can such a rule be identified automatically? \n1. Were the serialized goal regression rules used in defining the relational neural network? Can explicit knowledge of such rules enable efficient learning?\n1. Which relational network was used in the experiments? NLM, ReNN, or NLRL? \n1. This is not a question. Just a discussion point. The traditional relational learning approaches learn rules one predicate at a time. The serialized goal-regression defines a class of planning problems that can be solved by satisfying one predicate at a time. So can this aid in understanding what class of planning problems can be solved by traditional relational learning approaches?\n1. Can authors provide the classes for common IPC domains like Logistics, Gripper, Rover, Elevator, etc?\n\n**Minor**\n\n9. Regression rule set notation has discrepancies. In Algorithm 2, $R_0$ is used, whereas in Line 109 $R^0$ is defined.\n9. There is a discrepancy in the function name. Line 111 uses S-GRS but Algorithm 2 uses GRS. \n9. Is $P_0$ defined in Line 61 the same as $P_{s_0}$? The set of predicates in the initial state does not define the set of all atoms.\n9. In Definition 3.1, is $\\bar{a}$ a trajectory or action? For consistency, I recommend using the symbol $a$ for actions alone. \n9. The term 'generalized goal regression rule' is not formally introduced. In line 141 such a rule is referred to as the reduced goal regression rule. For consistency, I recommend sticking to a single term.\n9. I know the space is limited, but I would still recommend moving the connection to plan width from appendix to main paper.", "limitations": " ", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "\n* The paper provides a novel approach to quantifying the complexity of planning problems\n* As far as I am aware, this is the first paper to analyze what kind of planning problems can be solved by neural networks.\n* The formal analysis can aid in better evaluations of the neural approaches proposed for planning problems.\n", "weaknesses": "\n* Some of the notations are not clear (See questions for details). \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your helpful comments!\n\n**Q1:** Notations in algorithm 1 and 2.\n\n**A1:** Thank you for all the suggestions. We will update our notations. For algorithm 1, we will include $\\mathcal{A}$ as input, define `goal_set` as the set of goals to achieve during the current backward search process (initialized as the goal of the planning problem), and define the goal stack as the set of `goal_set` arguments currently in the depth-first search stack. We intentionally omitted the condition of $\\textit{eff}_+$ in the algorithm to save space, because this does not affect the correctness of the algorithm (but only efficiency). We will similarly update algorithm 2 to define the goal stack and include $R$ as the input.\n\n**Q2:** Definition of $\\pi$.\n\n**A2:** Thanks for the catching that! $pi$ was intended to include only a sequence of actions. Therefore, we will rewrite the line of $s_i = \\pi_i[-1]$ to be $s_i = \\mathcal{T}(s_{i-1}, \\pi_i)$ (i.e., simulate all actions in $\\pi_i$ based on $s_{i-1}$).\n\n**Q3:** Not consider $p_i$ if $p_i$ is already in the goal stack.\n\n**A3:** In short, this design is to avoid a potential infinite loop.\n\nFirst, adding this line will not hurt the accuracy or optimality of the search algorithm, because the search algorithm seeks  optimal trajectories to achieve a certain goal. If the subgoal in the current regression rule is a subgoal that we wish to achieve at an earlier search depth, then using this regression rule will not yield an optimal trajectory for the earlier search depth subgoal.\n\nIf we do not add this condition, then there will be infinite loops: consider two regression rules for two predicates $p$ and $q$: `p <- q || a_1`, `q <- p || a_2`.\n\n**Q4:** Infeasible rules in the regression set.\n\n**A4:** Yes, the search algorithm does allow infeasible regression rules in $R$. This is because if a goal regression rule is infeasible (e.g., after achieving one of the precondition, we can not extend the current trajectory to achieve another precondition), the set `possible_t` will just be empty. Since the search algorithm enumerates all candidate rules to use, the search algorithm will return an answer as long as there exists a subset of feasible rules in the given rule set that can yield a successful plan.\n\n**Q5:** Identifying generalized goal regression rules.\n**A5:** In this paper, we did not discuss any particular algorithms to identify generalized goal regression rules. In general, in order to prove the correctness of a generalized goal regression rule, we need to verify that Definition 3.2 holds for the generalized rule. This is generally hard, and we have done this in a case-by-case manner (e.g., proving a particular generalized rule is applicable in BlocksWorld).\n\n**Q6:** Were the serialized goal regression rules used in defining the relational neural network? Can explicit knowledge of such rules enable efficient learning?\n\n**A6:** Thank you for this suggestion! Currently, the goal regression rules are not used in defining the network (we use regression rules to reason about the network size only). We think there are at least two interesting directions given your suggested idea. One would be to explicitly compile some set of given serialized goal regression rules into a network, either by manipulating network weights, or by introducing additional supervision. Another possible direction might be one where we know the basic form of the serialized regression rules, but don't know the value of some of the conditions: in such a case, we could encode those rules in a network leaving the unknown conditions \"free\", in the sense of representing them as an MLP, and then backprop to train just the weights in those MLPs, which we would expect to be substantially more sample efficient than learning the whole policy.\n\n**Q7:** Which relational network was used in the experiments? NLM, ReNN, or NLRL?\n\n**A7:** We were using NLMs for all the experiments.\n\n**Q8:** Connection to relational learning approaches.\n\n**A8:** Thanks for the suggestion! We think this is a very interesting idea. We think there are two possible ideas in leveraging tranditional relational learning in learning and planning. First, we can learn a PDDL-like domain definition, using traditional relational learning approaches; then, we can find ways to compile the learned definitions into a RelNN-like policy. Alternatively, one can consider learning a policy (such as all the regression rules in a domain). The difficulty with this approach is that in most domains, learning a single rule usually does not allow you to immediately solve novel problems. By contrast, multiple rules must be learned and used together in order to compute a plan. In this case, even though each regression rule only achieves only one single atom, we do not have direct supervision for them (but only learning signals when a set of rules have been learned).\n\n**Q9:** Classes for IPC planning problems.\n\n**A9:** Thanks for the great suggestion! We have included more analysis of the classic problems you suggested. Please refer to our general response for a detailed discussion.\n\n**Q10:** Notation discrepancies.\n\n**A10:** Thank you for catching these! We will fix the notation discrepancies for $R_0$, function names, and the definition for trajectories.\n\n**Q11:** Other clarifications and structures.\n\n**A11:** We appreciate all the suggestions. We will clarify that the set of predicates in the initial state does not define the set of all atoms, define generalized goal regression rule before Definition 3.2, and move back connections to plan width from appendix to the main paper.\n\n[1] Richard Li, Allan Jabri, Trevor Darrell, Pulkit Agrawal. Towards Practical Multi-Object Manipulation using Relational Reinforcement Learning."}]

Author rebuttal:
We thank all reviewers for their thoughtful and constructive comments. Some of the reviewers have suggested applying the theorems and analyses developed in this paper to a broader set of problems. Here, we list 6 popular problems that have been widely used in AI planning communities and discuss their circuit depth and breadth. We summarize our results in the following table.


| 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 |

Note that here we are limiting our discussion to the case where the goal of the planning problem is a single atom. In summary, most of these problems have a constant breadth (i.e., the regression width of the corresponding problem is constant) except for Sokoban. Most problems have an unbounded depth: that is, the depth of the circuit will depend on the number of objects (e.g., the size of the graph or the number of blocks. The constant breadth results can be proved by construction: list all regression rules in the domain. We have analyzed the complexity of BlocksWorld and Logistics in Appendix A.6; all other problems can be proved in a similar way. The problem gripper has a constant depth under single-atom goal because it assumes the agent can move directly between any two rooms; therefore, no pathfinding is required. Sokoban has an unbounded breadth even for single-atom goals because if there are multiple boxes blocking the way to a designated position, the order to move the boxes can not be determined by simple rules.

For problems in this list, when there are multiple goals, usually the goals are not serializable (in the optimal planning case). This can possibly be addressed by introducing "super predicates" that combine two literals. For example, if two goal atoms p(x) and q(x) are not serializable, we can introduce a new predicate p_and_q(x), and rewrite all operators with this new super predicate. Appendix A.5 provides more discussion and examples. This will make the problem serializable but at the cost of significantly enlarging the set of predicates (exponentially with respect to the number of goal atoms).

If we only care about satisficing plans, for Logistics, Gripper, Rover, and Elevator, there exists a simple serialization for any conjunction of goal atoms (basically achieving one goal at a time).

These theoretical analyses can be used in determining the size of the policy circuit needed for each problem. For example, one should use a RelNN of breadth $(k + 1) \cdot \beta$, where $k$ is the regression width and $\beta$ is the max arity of predicates. For problems that have unbounded depth, usually, the depth of the circuit grows in $O(N)$, where $N$ is the number of objects in the environment (e.g., in Elevator, the number of floors).


Meta-review: The reviewers found the paper to make an interesting and novel contribution. Please take the critical feedback into account when preparing the camera ready version.
Decision: Accept (spotlight)