What Planning Problems Can A Relational Neural Network Solve?

Summary

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

Strengths

* The paper provides a novel approach to quantifying the complexity of planning problems * As far as I am aware, this is the first paper to analyze what kind of planning problems can be solved by neural networks. * The formal analysis can aid in better evaluations of the neural approaches proposed for planning problems.

Weaknesses

* Some of the notations are not clear (See questions for details).

Questions

**Major** 1. Algorithm 1 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. 1. Action should be mentioned as input in Algorithm 1. 1. `goal stack` is not defined 1. Algorithm 2 1. $R_o$ should be part of the input 1. `goal stack` is not defined 1. `goal_set` is not defined 1. Is $\pi$ a plan? If so, $\pi[-1]$ is the last action. So is $s_i$ an intermittent state or action? 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? 1. 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? 1. How are the generalized goal regression rules identified? For example, consider the rule in Line 139. Can such a rule be identified automatically? 1. Were the serialized goal regression rules used in defining the relational neural network? Can explicit knowledge of such rules enable efficient learning? 1. Which relational network was used in the experiments? NLM, ReNN, or NLRL? 1. 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? 1. Can authors provide the classes for common IPC domains like Logistics, Gripper, Rover, Elevator, etc? **Minor** 9. Regression rule set notation has discrepancies. In Algorithm 2, $R_0$ is used, whereas in Line 109 $R^0$ is defined. 9. There is a discrepancy in the function name. Line 111 uses S-GRS but Algorithm 2 uses GRS. 9. 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. 9. In Definition 3.1, is $\bar{a}$ a trajectory or action? For consistency, I recommend using the symbol $a$ for actions alone. 9. 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. 9. I know the space is limited, but I would still recommend moving the connection to plan width from appendix to main paper.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

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.

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). - Quality: The proposed method is supported by theoretical analysis and proofs. A small set of experiments were conducted to validate the approach. - Clarity: The order of presentation is mostly nice, even though the terminology used throughout the paper sometimes makes it hard to follow. - 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.

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). - 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. - Related work section might be placed earlier (e.g., after introduction) for better placing this work w.r.t. the literature. - 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.

Questions

- What are the main bottlenecks/issues to apply this formulation for continuous planning problems, e.g., such as the ones in robotics? - Would this analysis and construction be still useful/practical for larger/more complex problems, which require larger networks? If yes, how? - 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? - Serialization of goal regression rules seem to be highly related to mathematical optimization / dynamical programming. Can you elaborate on this connection?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

- Limitations of the work have been barely touched upon on the paper. - The discussion on applying this formulation to continuous planning problems, e.g., in robotics, can be extended. - In general, an evaluation and discussion on the type of problems that the proposed formulation is not applicable to would be nice.

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.

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.

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. l.114 Please refer to a specific appendix. l.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? l.130 Does Theorem 3.1 have proof? Please, provide a reference. l. 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. l.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. l.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.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

The limitations are briefly discussed in the conclusion. Negative societal impact is not an issue with this work.

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

Strengths

- Innovative combination of tractable planning with the expressivity of some NN. Serialization is a suggestive idea for a tractable fragment for planning. - The idea of 'regression rule selector' might be hard to use in an effective symbolic algorithm. Framing it as learning is an innovative idea.

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. - The paper doesn't clarify whether the goal of the approach is to solve a single problem or problems from a domain. - For instance, the width of [LG2012] refers to problems, but then they discuss width across instances of a problem. - This might be easily fixed in the next discussion. - Experiments cannot be replicated as we lack details.

Questions

- What's the goal stack in the algorithms? - How are the objects encoded in the RelNN? - What's the difference/similarity in the encoding of problems where the policy have bounded vs unbouded depth? - 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. - Might such renaming have any effect in the experiments? - Are MLP per se part of the class of relational NN? - How are the problems and outputs encoded in the MLP? - 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. - How does D change with the complexities of the formulas? - In thm 4.3, why does the breath only grows with max(B_r, max arity of predicates)? - 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.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

2 fair

Contribution

2 fair

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. In 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. Lacking intuitions, the empirical study offer some light in this direction, but a reader in NeurIPS might need further details on how this was done. Finally, 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. For that reason and others, this one is a very relevant reference: Learning Sketches for Decomposing Planning Problems into Subproblems of Bounded Width. Dominik Drexler, Jendrik Seipp, Hector Geffner. ICAPS 2022. https://arxiv.org/abs/2203.14852 All in all, I learned a lot from the paper. That's a positive sign. Minor point(s): - why can serialization be incomplete? Perhaps explaining this might be useful: https://en.wikipedia.org/wiki/Sussman_anomaly

thank you

Thank you for the thoughtful response. I'm satisfied. I think the analysis per domain can be quite insightful. In your response, I see the mention of parameters on the structure of the formulas. In my opinion, this suggests that the encoding, decoding, and parameters should be made clear as the paper progress. "Enconding graph" is sometimes abused in the literature, leaving the reader with no idea of about affects the size of the network and the expressivity.

Thanks

I appreciate the sincere and detailed explanations by the authors. Even though practicality concerns are addressed to some degree, it is not solid enough for me to raise my score at the moment.

Thank You

Dear reviewers and area chairs, As the reviewer-author discussion phase is coming to an end, we would like to say thank you, and that we truly appreciate your constructive feedback. We are glad that our rebuttal and additional results have addressed the concerns from all reviewers, and we will definitely incorporate the suggested changes and new discussions in our next version. Authors