Graph Learning for Numeric Planning

Summary

This paper proposed new learning-based methods for numeric planning. Numeric planning is formalized with the PDDL language. The proposed approaches are based on graph neural networks, and are evaluated in a lot of domains, e.g., blockworld, childsnack.

Strengths

The experiment section seems solid, and the proposed approaches are evaluated in lots of domains. The experiment results demonstrate significant improvement over the compared baseline.

Weaknesses

As there is only one closely related work on learning for numeric planning, it is hard to assess whether this is an important research problem. The abstract has not summarized the novelty of this work, and the relationship between the two proposed approaches. There are some missing related works about learning heuristics: evolution of Heuristics github.com/FeiLiu36/EoH.

Questions

Are the proposed two approaches suitable for different scenarios? Can the authors analyze this issue?

Rating

3

Confidence

3

Soundness

2

Presentation

1

Contribution

2

Limitations

This paper has discussed the potential limitations.

Summary

The paper proposes a new method for learning a heuristic function to guide search for solving numeric planning problems. In contrast to classical planning, the states in numeric planning may involve numeric variables while the state transitions are defined by mathematical expressions over these kinds of variables. In addition, numeric planning is computationally quite challenging to solve but it may be the right formulation in many interesting real-world applications. The proposed heuristic is learned from training data consisting of example planning instances and their corresponding optimal plans. Features are automatically extracted from a graphical representation of the planning instances and used subsequently by the machine learning models encoding the heuristic functions. The experimental evaluation is carried out on standard benchmarks for numeric planning. The results show clearly that state-of-the-art search algorithms guided by the proposed heuristics improve considerably over their competitors.

Strengths

- The paper targets an important problem in the area of automated planning and proposes more effective heuristics to guide search algorithms for solving these problems. - The empirical evaluation is sound and covers standard benchmarks in the numeric planning domain. The results are presented in a relatively clear manner and therefore it is easy to understand the benefits of the proposed approach compared to existing state-of-the-art.

Weaknesses

- In my opinion, the presentation is the main weakness of the paper. While I believe it is a solid contribution for numeric planning, the way it is currently presented makes it hard to understand the details. - The examples currently supporting sections 3.1 and 3.2 need to be expanded a little more. Right now, it is kind of difficult to follow them. - Section 4 which describes the graph neural network is too high level and without a supporting example is very hard to understand. - There is currently a relatively big disconnect between Sections 3, 4 and 5. Namely it takes a while to figure out that the features extracted by the proposed method are subsequently used to learn the heuristics. The current notation doesn't help much either. I also think that adding illustrative examples in Section 5 would clearly improve the quality of the presentation.

Questions

- The paper claims that grounding is not required for building the graphical representation of the planning problem. However, the graph shown in Figure seems to be partially grounded. So, how much grounding is needed to build such graphs?

Rating

5

Confidence

4

Soundness

3

Presentation

1

Contribution

3

Limitations

The limitations are addressed clearly in the paper.

Summary

The paper tackles numeric planning problems by proposing two heuristics for numeric planning. The first one is based on graph kernels for graphs and addresses both continuous and categorical attributes. The second uses graph neural networks. The authors experimentally show the effectiveness of the two proposed algorithms by showing that they show better coverage compared to domain independent planners for numeric planning.

Strengths

- The paper shows experimentally that their proposed learned heuristics shows better coverage, and that is significant. - The approach is novel and paper is also novel (except for the recent related work which the authors cover in the intro) - The authors do a decent job with explaining the literature and citing appropriately. - The use of classical machine learning due to being cheap and interpretable

Weaknesses

The paper presentation can be improved. Examples below (no particular order): 1. The abstract states “… in comparison to domain-independent planners” whereas it is more informative to state domain-independent numeric planners. (Other places did indicate numeric planners). 2. The paper can be dense in various places (section 5 for example) 3. Sometimes the authors miss details that can be helpful in understanding the paper. For example, what is M(3h||3n) can you explain? Maybe it would be good to give a bit of explanations on each of the configurations. 4. Fig 1, why x, y, z are not shown as blocks, the figure was confusing at first specially given that there are dotted block spaces above y and z with only 2 available blocks whereas the limit is 3 blocks. 5. In the Table2 caption, mention which ones are your proposed planners and the two variations (rank/cost). 6. minor typo: “Requires requires” repeated in section 3.1

Questions

1. Can you claim theoretically on admissibility, safe pruning, or tractability of the proposed algorithms? I find it strange that the authors refer to prior work re theory. At least a proof sketch can be given which refers to prior work. 2. Related to 1, can you prove the complexity on the WL algorithm (right before section 4 starts). 3. Can you please explain with an example how one should read Table 1. 4. Which planner is h^LMCUT used in. h^LMCUT is a heuristics, not a planner, right? Same with the other heuristics mentioned in the figure, not sure if it is accurate to refer to them as planners. 5. In section 8, you mention in the last sentence, one can learn forms of domain knowledge different from heuristic functions, can you give an example.

Rating

7

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

The paper covers that.

Summary

The authors introduce a method to generate features for planning tasks that involve numerical variables. These features can then be used with machine learning to learn a heuristic function from a set of training examples. Architectures used for learning include Gaussian processes and graph neural networks. The authors also introduce a method for learning to rank states and do a search based on the ranking instead of the cost-to-go. Results show that, for benchmarks modified to include numerical variables, learning a heuristic function with Gaussian process regression and ranking performs significantly better than planners that do not make use of a numerical representation.

Strengths

Ranking states instead of learning cost-to-go has shown promise. The paper presents a novel ranking method that can be combined with machine learning. The ranking method was significantly better than the corresponding non-ranking method. This could have broader implications for machine learning applied to planning.

Weaknesses

The only learning approach that performed better than the baseline planners was the Gaussian process regression with ranking, while Gaussian process regression with cost-to-go performed better than three out of four baseline planners. This makes it appear as if ranking is contributing to the overall success and not the numerical representation and learning.

Questions

Do any of these baseline planners make use of ranking? Is it possible that the main increase in performance is due to ranking and not the numerical representation and learning? On line 152, V is comprised of G, while, on line 151, it says that G is comprised of V. Do these two Gs represent different concepts?

Rating

4

Confidence

2

Soundness

3

Presentation

3

Contribution

2

Limitations

The learning approach relies on supervised learning, which assumes a planner exists that can already solve problems and may limit performance to what the existing planner can solve in a given time limit. On the other hand, research using deep reinforcement learning does not assume the existence of any solver.