Venue: CoRL 2022 Conference

Reviews:

final_score: rating: Strong Accept: I recommend accepting the paper and will argue for my recommendation even if other reviewers hold a different opinion.
review_content: summary: This paper proposes a data-driven approach to efficient task-level search in geometric task and motion planning (G-TAMP). Specifically, the paper replaces inefficient backtracking with backjumping, which directly backtracks multiple steps in the search tree when an infeasible level is detected. The authors present two supervised learning methods to learn to detect the “culprit action” (i.e. the earliest action in the search tree that needs to be corrected by backjumping in order to resolve infeasibility). The first approach is imitation learning, where the tree level corresponding to the culprit action is directly output based on the state sequence. The second approach is classification, in which the feasibility of a partially-refined future plan is checked from a fixed state at some level of the tree. The effectiveness of both approaches are demonstrated in two different mobile manipulation tasks in a physics-based motion simulator.
strengths_and_weaknesses: **Strengths of the Paper**

1) Tree search in continuous state spaces is notoriously difficult to solve. Yet, it appears quite often in robotics, including the G-TAMP problems that are addressed in this work. The paper proposes an interesting approach to accelerating tree search algorithms by means of learning a backjumping strategy. The general idea of using machine learning for tree search is not new (see the weaknesses section below), but the proposition of backjump learning is novel as far as I am aware. 
2) Even though no theoretical analysis is provided, the empirical evaluation of the proposed approaches are well-executed and convincing. 
3) The quality of presentation is high in general, although some improvements could be made (see the weaknesses section below).


**Weaknesses of the Paper**
1) (*Resolved after rebuttal*) As noted above, the general idea of data-driven tree search for improved efficiency is not new. For instance, Masti and Bemporad [1] propose to use a learned predictor to circumvent costly branch-and-bound pruning in exploring a binary search tree, in the context of mixed integer programming. In [2], Pinto and Fern present a supervised learning approach to efficient guided-search in a Markov-decision tree. These approaches can be loosely categorized as “learning an efficient sampling (or branching) strategy in tree search,” which would be an alternative domain-independent way of learning domain-specific heuristics. In contrast, the method presented in this paper fixes a sampling strategy (i.e. either batch of forgetting sampling) and instead learns how to correct the plan from bad samples. This observation leads to the following fundamental, motivational question: “how is the backjumping correction strategy advantageous over directly learning an efficient sampling strategy (which seems more common in data-driven, accelerated tree search) in the first place?” This point should be clarified in the paper.

2) (*Resolved after rebuttal*) In terms of the presentation quality, I was a bit confused by Section 2.2 which lacks the details of how the sampling is performed, until I saw the two sampling methods described finally in Section 5. The authors may want to re-order or augment the explanations about sampling for extra clarity.

[1] Masti, Daniele, and Alberto Bemporad. "Learning binary warm starts for multiparametric mixed-integer quadratic programming." In 2019 18th European Control Conference (ECC), pp. 1494-1499. IEEE, 2019.

[2] Pinto, Jervis, and Alan Fern. "Learning partial policies to speedup MDP tree search via reduction to IID learning." The Journal of Machine Learning Research 18, no. 1 (2017): 2179-2213.

**Other Minor Points and Questions**

1) (*Resolved after rebuttal*) How is the plan length K selected? Is that chosen heuristically by domain knowledge? It seems that the choice of K is crucial in long-horizon planning tasks, since underestimating the value of it could lead to the robot failing to find any feasible plan regardless of the backjumping strategy.
2) (*Resolved after rebuttal*) In Table 4, the imitation learning approach seems to benefit more from increased data size than the classification approach. Is there a reasonable explanation for that?
3) (*Resolved after rebuttal*) In tables, how specifically is “statistically significantly different from one with *” determined?
4) (*Resolved after rebuttal*) Typo: “On important practical challenge” → “One important practical challenge” (Section 1, line 17) 
5) (*Resolved after rebuttal*) Typo: “Often done often” → “Often done” (Section 1, line 26).


robotics_focus: Highly relevant to robotics but no hardware experiments
quality_of_the_limitations_section: Limitations are addressed clearly
summary_of_recommendation: ~~I recommend "weak accept," based on the overall novelty of backjumping learning (as noted in the strengths section) as well as the motivational question of "why learn backjumping instead of learning a sampling strategy itself?" (as noted in the weaknesses section).~~

My concerns have been addressed after the rebuttal. I am convinced that the overall novelty of the paper is high, providing an interesting alternative to guided sampling for accelerated search. Thus I recommend acceptance.
issues: ~~Please refer to the weaknesses section and the questions stated above.~~
review_title: null

final_score: rating: Strong Accept: I recommend accepting the paper and will argue for my recommendation even if other reviewers hold a different opinion.
review_content: summary: The authors propose to adapt the backjumping technique used in constraint solving. Since locating the culprit action is not analytically tractable, they instead propose learning a domain specific model to predict the correct location to jump to. They find that this leads to significant reductions in search time on all tasks tested, including a 99% reduction in search time on the NAMO task. 
strengths_and_weaknesses: This is an interesting way of improving efficiency with impressive results. It offers a clever way of encoding the problem as well, which allows for generalization across an interesting domain of problems.

One question I felt was inadequately addressed was what happens when the model makes an incorrect prediction. I presume that if the model under-predicts the length of the optimal jump, then it will continue to perform backtracking. However, it's unclear what happens if the model over-jumps. Does it prevent an optimal solution? Can it prevent the solver from finding any solution? How often does the model over-predict a jump? I see that some of these questions are addressed in the appendix, but I think it deserves at least some comment in the main body of the paper. 
robotics_focus: Highly relevant to robotics but no hardware experiments
quality_of_the_limitations_section: Additional details required
summary_of_recommendation: ~~The paper could be clearer in what the tradeoffs of using backjumping guided by a learned model are and how accurate the model is. However, these are somewhat minor issues in my opinion, and it is a solid idea backed by impressive experimental results, so I recommend to accept.~~

The authors addressed my central concerns in their response. 
issues: ~~Question of what happens when the model is inaccurate is inadequately addressed~~
review_title: null

final_score: rating: Weak Accept: I recommend accepting the paper, but will not argue for my recommendation if the majority of other reviewers have a different opinion.
review_content: summary: This paper focuses on improving a task and motion planning approach. Due to the infeasibility of covering the search space in such problems extensively, the solver might get stuck in later stages of the search due to some earlier assignment of the world/object configurations. This work proposes to train a prediction model to backjump onto the search state where the bottleneck might have occurred. In essence, the default backtracking is replaced with this backjumping heuristic. The learned model is shown to improve the computational efficiency of the solver on two different tasks.
strengths_and_weaknesses: strengths:
- the proposed predictor is effective at solving similar problems being tested

weaknesses:
- full state knowledge is assumed, and
- same/similar setups are used for both tasks, e.g., simple and same object geometries: might then use user defined heuristics and/or analytical methods to compute feasibility?
robotics_focus: Relevant but unlikely to deploy to hardware in near future
quality_of_the_limitations_section: Additional details required
summary_of_recommendation: The paper implements a learning architecture to predict where to backjump in the search process when the solver gets stuck during solving for a task and motion planning problem. As a result, instead of backtracking, which is the default procedure, the predictor allows instantly jumping to earlier levels of the search tree, which in turn increases the computational efficiency. Both of the scenarios presented are relatively simplistic due to the simplifying assumptions. Thus, the work falls short on justifying the efficiency and applicability of the proposed inclusion of a predictor for a broader set of sequential manipulation tasks, especially to the more realistic ones.

issues: - as mentioned in the 'weaknesses' above, the most critical issue is the experimental setup: same container, same object types, simpler shapes, same arrangement of fixed objects, etc. and using the full-state knowledge -> they do not help the reader accept the effectiveness of the proposed addition of a backjumping predictor as useful for real sequential manipulation tasks and the presented results as convincing. Yes, the authors already acknowledge those, but I think these are still serious limitations that without taking some steps towards handling more realistic scenarios, the value of the work will be highly limited.
- varying training data size: why increasing the data size 4-fold doesn't improve the prediction efficiency?
- what are the computation times (wall-clock time)? 
- related work: there is some line of work ([R1] + some follow-up) that investigates learning heuristics to speed up TAMP solvers. How do you compare to them?
- related work: As mentioned by the authors, joint optimization based approaches can also solve such issues [12] (there is also LGP-line of work which have been almost totally neglected in the paper). More discussion might help emphasize the difference to those, and the advantages of the approach used within this paper.

[R1] D. Driess et al., "Deep Visual Heuristics: Learning Feasibility of Mixed-Integer Programs for Manipulation Planning", IEEE ICRA, 2020.
review_title: null

final_score: rating: Weak Accept: I recommend accepting the paper, but will not argue for my recommendation if the majority of other reviewers have a different opinion.
review_content: summary: This paper considers the backtracking search over action refinements that must be performed in a sequence-then-refine Task and Motion Planning solver, after a promising action skeleton has been identified.

If a mistake is made is made early on in refinement, the search will eventually reach a dead-end. If the number of steps between the "culprit" action and the dead-end is large, then backtracking will waste lots of computation on sampling different refinements of the intermediate steps.

This paper proposes to address this problem by learning a GNN-based model to predict the culprit after encountering a dead-end. This model can then be used to "backjump" directly to the culprit, without sampling refinements for intermediate actions. The model is trained using supervised learning with labels obtained from the backtracking algorithm.

The authors evaluate the approach in two simulated robotics problems, and demonstrate improvements in search efficiency over backtracking.
strengths_and_weaknesses: Strengths

* Culprit identification is difficult to get at analytically, so a learning method seems promising, and potentially very useful. The paper also makes a nice connection to the constraint satisfaction literature’s concept of backjumping. 

* The learning approach and model architectures seem reasonable, and the results on evaluation tasks demonstrate a significant improvement over backtracking.

Weaknesses:

* (Improved in rebuttal + to be added to paper) In general, I think the empirical evaluation of the method is lacking. At the moment, it is hard to glean any insight beyond the fact that this approach exhibits improved sample efficiency than vanilla backtracking on two problem types. Some other baselines/ablations would help - for instance what if backtracking just jumped a constant 2-3 steps back every dead-end. How would that compare?
* (Improved in rebuttal + to be added to supplementary materials) There is no discussion or analysis of the overhead that model inference adds to the backtracking procedure. 
* It is not clear to what degree this approach could generalize to planning domains with more diverse plans, as it seems that the training and test problems are very similar.

Questions:

(Clarified in rebuttal) As acknowledged by the authors, only a single plan skeleton is considered here. The assumption seems to be that the sequencing (task-planning) stage has already identified the correct skeleton. However, the authors state that the learned models are "guiding" the task-level search. Am I misunderstanding this or is it misleading?

(Clarified in rebuttal + to be added to paper) If you were to consider multiple plan skeletons, how would the batch/forgetting algorithms be modified so that they do not spend the entire time sampling the wrong plan skeleton? If there are good ideas about this, then a passing mention in the paper would be appreciated.

(Clarified in rebuttal + to be added to paper) How much variance is there in the training data, since it's also estimated using sampling, i would imagine there is a certain amount of variance. Does it matter what sampling budget is used for backtracking during data collection?

Do you have any insight as to why the PF Attn models are doing so much worse than PF RNN?

robotics_focus: Highly relevant to robotics but no hardware experiments
quality_of_the_limitations_section: Additional details required
summary_of_recommendation: I think that the idea being explored here is interesting, and worthwhile. I think the results are promising, but analysis/exposition of them is incomplete. I would love to see more experiments, and for the authors to provide more insight about what exactly we gain by using learning for culprit detection in this way. 

(Updated after rebuttal) The additional experiments conducted after the initial review have led to what I believe to be a more thorough evaluation of the proposed methods and how they compare to reasonable baselines.
issues: * The evaluation tasks are not well described. How exactly do they differ from each other, and from the training data. In the packing task, are all object locations sampled at random. In the NAMO are all the movable objects' locations randomly sampled? These details should be spelled out.

* (Clarified in rebuttal) It would be interesting to get a sense of the overhead of querying these models. Since PF models are being queried at every step, I imagine this would be quite considerable. In comparison, the IL models seem to only need to be queried once per dead-end. But beyond comparing the different architectures, it would be crucial to compare the time we save on backtracking with model inference time.
review_title: null

Meta-review: metareview: The paper proposes to learn backjumping heuristics for geometric task and motion planning frameworks. The key idea is to identify the "culprit action" that leads to the infeasible path during the search and directly "backjump" to correct the action selection. The authors present two types of solution under this idea: (1) directly predict the culprit action and (2) estimate the plan feasibility given each action choice. The method is tested on two types of rearrangement tasks using a mobile platform in simulation. 

Strengths: The reviewers agree on the importance of improving the efficiency of the search algorithm for large-scale manipulation planning problems, and that learning is a promising path to this objective. They also agree on the empirical effective of the proposed method, at least based on the evaluation setup presented in the paper.

Weaknesses: The main comments focus on empirical evaluations: (1) lack of comparison to baselines (R-q4VZ) such as guided sampling (R-MW4W) and (2) lack of more realistic and diverse evaluation tasks (R-q4VZ, R-MGEc) and ablation studies (R-Kqwz, R-q4VZ)

Post-response period: The authors have addressed most of the concerns raised by the reviewers. In particular, they have included additional baseline results, runtime performance, and answered most conceptual questions. I also agree that the method provides a conceptually simple yet effective improvement to a core component in TAMP.  However, during the post-response period, some doubts still remain on the applicability of the method on a broader set of tasks. Based on the response and the updated ratings (as well as their justifications), the AC recommends that the paper should be accepted with a poster presentation.
confidence: 5: The area chair is absolutely certain
Decision: Accept (Poster)