Learning to Correct Mistakes: Backjumping in Long-Horizon Task and Motion Planning
Authors: Yoonchang Sung
Zizhao Wang
Peter Stone
Venue: CoRL 2022 Poster (2022)
Keywords: task and motion planning
heuristic learning
supervised leanring

Abstract: As robots become increasingly capable of manipulation and long-term autonomy, long-horizon task and motion planning problems are becoming increasingly important.  A key challenge in such problems is that early actions in the plan may make future actions infeasible. When reaching a dead-end in the search, most existing planners use backtracking, which exhaustively reevaluates motion-level actions, often resulting in inefficient planning, especially when the search depth is large. In this paper, we propose to learn backjumping heuristics which identify the culprit action directly using supervised learning models to guide the task-level search. Based on evaluations of two different tasks, we find that our method significantly improves planning efficiency compared to backtracking and also generalizes to problems with novel numbers of objects.

Learning to Correct Mistakes: Backjumping in Long-Horizon Task and Motion Planning
Yoonchang Sung", Zizhao Wang" Peter Stone 'The University of Texas at Austin 'Sony Al
Abstract: As robots become increasingly capable of manipulation and long-term autonomy, hong-horizon task and motion planning problems becoming increas- ingly important. A key challenge in such problems is that early actions in the plan may make future actions infeasible. When reaching a dead-end in the search, most existing planners use backtracking, which exhaustively reevaluates motion- level actions, often resulting in inefficient planning, especially when the search depth is large. In this paper. propose to learn backjumping heuristics which identify the culprit action directly using supervised learning models guide the task-level search. Based on evaluations on two different tasks, we find that our method significantly improves planning efficiency compared backtracking and also generalizes problems with novel numbers of objects.
Keywords:
Task and motion planning, heuristic learning, supervised leanring
1 Introduction
Integrated task and motion planning (TAMP [1]) is a framework for making sequential decisions in robotic tasks. Solving TAMP problems involves a hybrid search over sequence of discrete actions (e.g., which object to manipulate) and their continuous motion parameters (e.g., with which pose to grasp the object). One important practical challenge is that for number objects, the search space becomes intractable due to a large depth and branching factor.
tasks with large
Target object
Movable objects
Movable objects
Cabinet
Fixed objects
Goal region
Figure 1: (Left) illustration of the packing task, whose goal move all objects cabinet. Putting first several objects near the entrance prevents the robot from putting the remaining objects inside. (Right) An illustration of the navigation among movable obstacles (NAMO) task whose goal is to move the red target object to the goal region.
In this work, address the challenges of long-horizon TAMP where early actions the plan may make future actions infeasible. For example, as shown in Fig. 1, if the robot places the first few ob- jects near the cabinet entrance in packing task, or the target retrieval path a navigation among movable obstacles (NAMO [2]) task, the problems become infeasible, unless the culprit actions that
Equal contribution.
6th Conference on Robot Learning (CoRI. 2022), Auckland, New Zealand.

---

placed objects in obstructive positions are corrected. When planning fails, identifying culprit actions is desirable as the search can focus on correcting the culprit actions, ignoring irrelevant actions.
Generating explanations for failure has been explored to guide search [3, 4, 5]. In TAMP, geometric failures guide the task-level planner, often done via backtracking to try a different alternative for the immediately prior action in the plan [6]. As backtracking exhaustively explores the search tree (Fig. 2(b)), correcting the culprit action can involve an exponential number of evaluations of all the intermediate actions. The complexity becomes especially daunting in TAMP because the continuous motion parameters induce an infinite branching factor for each action.
In the constraint satisfaction literature [7]. backjumping has been introduced to alleviate the com- plexity of backtracking by taking a short cut to an ancestor action. In discrete settings, it may be possible to jump back to the culprit action directly without precluding any possible solutions. How- ever, because of the infinite branching factor in TAMP, conclusively identifying the culprit action is generally not possible. Even estimating the culprit requires solving the original backtracking problem, which can be very time-consuming (see details in Sec. 4).
We thus propose learning approach by shifting the computational burden to the training phase where training data collected by solving backtracking problems. Our observation that because the true culprit action always exists in any failure cases, learning models designed to exploit this may predict the culprit accurately. Specifically, we explore two frameworks to learn backjumping heuristics: (1) imitation learning which directly predicts the culprit from all previous actions, and (2) plan feasibility which indirectly predicts the culprit by checking the solution can be found after each action. Our proposed learning process is domain-indeeeendet way of learning domain- specific heuristics. We summarize our contributions as follows:
We propose two backjumping heuristic learning methods improve the efficiency of solving long-horizon TAMP problems. We also present two algorithms containing learning methods as a subcomponent, which treats the continuous parameters differently.
Our empirical results show that our methods improve planning efficiency by 40% for packing and 99% for NAMO, both against backtracking. Furthermore, by incorporating graph neural network (GNN [8]) into the learning model, our methods can generalize to problems with novel numbers of objects while outperforming backtracking consistently.
2
Preliminaries
We introduce the TAMP notation that will be used to define our problem and the sequence- before- specify strategy that we improve on.
2.1 G-TAMP notation
Although our method can potentially be applied to a broader class of TAMP problems [1], we focus on particular subclass of TAMP called geometric TAMP (G-TAMP [9]) for clarity of presenta- tion. In G-TAMP, mobile manipulator is tasked with moving multiple objects to target regions among movable obstacles. We assume quasi-static dynamics of the world'. deterministic effects of actions, and obsly-lbeer environments. Even with these assumptions. the proposed problem is already hard (NP-hard explained in Sec. 7), but relaxing these assumptions may still be possible by introducing belief-space planning [10, 11], which we leave future work.
80 > where M is a set of movable objects, RR is a set of target regions, O is a set of operators, F is a feasibility checking function, T is a transition function, G is goal set, and 80 is an initial state. The goal is to find a sequence of grounded and refined operators* starting from 50 to reach a state G.
Formally, a G-TAMP problem defined by a tuple <
M, R and s: In G-TAMP, the environment consists of any number of fixed objects such as tables, NM movable objects M (m such as cups, and NR target regions R {rr Na We denote the world state by which consists of the robot configuration and the pose of each movable object.
1 'The objects remain stable states after being manipulated by the robot. "e say that an operator is grounded if its discrete parameters are specified and refined if its continuous parameters are specified.

---

O: Operators in G-TAMP move one object to region, such as PICKANDPLACE and PUSH. Each refined operator o (d = (m, ry), = (g: g)) E O consists of (1) the discrete parameter d E . x R. specifying which object to move and which region move to, and (2) the continuous parameters composed of a grasp g E (3)) on my and a placement pose @ E (E) in Tj.
F and T: The feasibility of an operator can be determined by evaluating constraints (e.g, reachabil- ity and collision avoidance) using an external motion planner. We denote this feasibility evaluation as Boolean- -alued function F(s. o) + {0. 1). If the operator is feasible, deterministic transition function Tss, o) determines the new state s'.
G: A goal set G is defined as conjunction of predicates, such as INCABINET (m; ry CABINET) which becomes TRUE if my is stably located in the cabinet.
k=O
Ga
G
k-1
C
Maximum
F1
jump
C
Op
S
O
22
Ok-1
Safe jump
F
F2
F
Backtrack
k=4
X
X
X
x
km44
CO
Gx
k=K G
Figure 2: (a) Constraint network consisting of variables represented by circles (continuous variables: and G, and discrete variables: d) connected by constraints F represented by squares. (b) Example of search tree when a dead-end is met level (i.e., k²).. Orange squares represent sampled values (N values each level). Orange shaded area denotes a particular assignment to (co..., C3) (i.e. a partial plan). All values of cs are inconsistent with this partial plan causing the dead-end. Maximum jump k" in this example is 1 (a culprit variable is C1 denoted by blue circle), and thus, A. = 21..
G-TAMP problems can alternatively be seen as hybrid constraint satisfaction problems, as shown in Fig. 2(a). Circles represent variables whose domains are either continuous (5k and (τ) or discrete (de), and squares represent constraints (F²). When the plan length is K, we find values for sets of variables { K-1 and K- such that all constraints (Fr)
R R-1 are satisfied and sg E G.
2.2 Sequeece--efore--peecfy strategy
Sequence-before-satist [4, 12, 13, 14, 15, 16, 17, 1] one strategy to solve TAMP problems which this work is based on. The strategy consists of two stages: (1) In the sequencing stage, the strategy finds plan skeletons [18] reaching the goal set G symbolically only, ie.., (d& (= are computed but their continuous counterparts K-) are left unspecified. (2) In the specifying stage, the strategy chooses plan skeleton often based on AI planning heuristics and refines (cx) K-1 satisfying the constraints and a goal condition. For notational simplicity, in the rest of the paper, we use ma to represent the object moved by operator ok- We treat objects that are not included in grounded plan as fixed objects.
Note that the two stages repeat until either finding solution or reporting no solution, generating multiple plan skeletons. Our method (Sec. 4 and Sec. 5) accommodates these multiple plan skeletons by learning a specific model for each plan skeleton. In this section we focus on the case of a single plan skeleton for ease of presentation.
K-1 in the specifying stage by construct- ing search tree rooted from Co (Fig. 2(b)). Since the domain of c is continuous, the strategy uses sampling (e.g., uniform sampling from the domain of c [19]) to obtain N refined values to select from. Index i corresponds to both the level of the tree and the step in the plan skeleton. When the assigned values of (Co, ..., -1) are inconsistent with all sampled values of cs (i.e. violating the
Backtracking search is generally used to find values of (cx) (cx)
'The special Euclidean group SB(3) is used to express a 3D rigid-body transformation consisting of trans- lation and rotation.
3

---

constraint FR), say the search hits dead-end and denote the dead-end level by kd The search then backtracks to a parent node Ck-1 to assign another value and retries the consistency check with Ck. If successful, child node ck+1 1 is evaluated at the next level, otherwise another value of Ck-1 attempted. Backtracking repeats this process exhaustively until it finds values of (cx) K-= that consistent, i.e., the solution of problem.
3 Problem Description
When the planning horizon is long. the above facktracking-basee strategy becomes intractable the search space increases exponentially. Our goal in this work is to adopt the idea of backjumping [7] to effectively reduce the search space and achieve efficient planning in TAMP.
In contrast to backtracking which only backtracks level by level when dead-ends persist, we can speed up the search by backjumping multiple levels (Fig. 2(b)). A backjump is said to be safe if it does not preclude any solutions. Specifically, level k safe jump corresponds to an ancestor level k < kd such that attempting all possible values of its descendants at all levels between lt and ka does not resolve the dead-end. We denote all safe-jump levels by set K.
The larger the jump, the better, because larger jumps avoid more computation. We denote the largest safe jump by maximum jump, i.e., k* min K.. Correspondingly, responsible for making all values of C being inconsistent with partial plan.
call Cg. culpris variable
The objective is to find k* to backjump safely and maximally whenever dead-end is met at level kd, thus improving the overall efficiency of the sequence-before-ppeiiiy strategy.
4 Backjump Learning Methods
The constraint network in Fig. 2(a) contains chain structure with respect to constraints F& by con- sidering dR. Ck2 and 8ą as large variable node for each k. Because of this topological structure, no constraints connect variables that are more than one level apart. Moreover, we can only estimate k* as we use sampling to handle continuous domains. For these reasons, k* identification using backjumping is inherently challenging in TAMP.
It however possible to find an approximation of k- with backtracking since it evaluates all possible combinations of assignments using all sampled values from the root to level kd Also, since k* always exists for any dead-end situations and is unique, data with a sufficient amount of samples. Leveraging these observations, we propose two alternative supervised learning methods to identify kt,, where training labels gathered by solving tasks from the same distribution using backtracking.
hope to gather less noisy labeled
The robot configuration is used in an external motion planner to check the feasibility of corre- sponding refined operator, but it is not used in our learning models. We thus define a new state notation consisting of poses of movable objects only.
(a) Imitation learning
Network computation
(b) Plan feasibility
Softmax
Ridirectional edge in the state graph (i.e., relative pose between two objects)
0/1
MLP2
MLP2
MLP2
Undirectional RNN or Masked multi-head attention
Bidirectional RNN Multi-head attention
MLP1
GNN
GNN
GNN
MLP1
...
MLP1
S1
ms
m2
m2
...
m2
mo
mm
mo
mk
...
M&
mi-
mIK-
Figure 3: Architectures of the learning models. In each graph, state 3e implies that objects (m,,. mp-1) are relocated by the robot while other objects (ma.... mx) remain in their original locations.

---

4.1 Imitation learning
When the search hits a dead-end at level k" we first propose a predictor to directly predict the maximum jump k* in the domain of (0,....,'' ka 1), from the sequence of states (81,-..3 8gae) and the geometric attributes of a movable object m (e.g., size). In our model, each state is represented by fully-connected graph whose nodes are the poses of movable objects and each edge is the relative pose between each pair of objects.
As shown in Figure 3(a), to predict k*, model (1) extracts the state features from each state in the sequence using the same GNN, (2) computes the temporal features across the sequence of state features using bidirectional recurrent neural network (bRNN [20]) multi-head attentions [21], (3) extracts the movable object features from ma with MLP1 (multilayer perceptron), and (4) with pairs of temporal features and object features as inputs, applies the same prediction network MLL2 to predict the likelihood of each step being k* The model is trained to minimize the cross-entropy loss between the predicted likelihood of being k' and the ground-truth k- label.
The k' labels are collected from the backtracking tree search. At any ka we record its current state trajectory as (51...., 5kz). When the backtracking successfully reaches the level kd for the first time after the dead-end, we record its state trajectory up to level hd as ($',..., 3gd) be the i-th element from the corresponding trajectory sequences. The k- the first level where two trajectories diverge, iee, k arg min, { E (0, (O....,k* kad 1} 8i+1 o 8/41)
Let &, and s
4.2 Plan feasibility
Besides directly estimating k*, we investigate alternative counterfactual approach that learns binary classifier to predict whether a refined partial plan at each level contributes to a dead-end. We the predicted labels (i.e., either feasible infeasible) to identify which level corresponds to k*.
Specifically, with a sequence of states ($1....: St4) that faces a dead-end at level kd, we start with $1
where only co is refined (i.e., a value is assigned) but the rest of the variables (cx )a= are not refined yet.* Then, the classifier predicts whether finding consistent assignment of values for (cx) ) is feasible. If infcasible, it implies that the placement of mo is culprit action making the rest of variables (c*)k=1 inconsistent with cu- By definition, level O becomes the maximum jump k=, If feasible, we continue with 82 where cy and e₁ are refined only and the classifier predicts fcasibility for (cx) 2 Likewise, we iteratively apply the classifier to predict feasibility in an ascending order of k; we stop if infeasibility is predicted and output the corresponding step as k*, or continue the next step otherwise.
Let R E (1) be the step where (cx) (io) are refined and feasibility for (c+) is to be evaluated. As shown in Figure 3(b), to predict whether level k' < kdd is safe jump, our model (1) extracts the state features from 5% using GNN, (2) extracts the object features from (m²) ) each with MLPI, (3) computes the temporal feature from the state features and object features using a unidirectional RNN or multi-head attention (the inputs to the attention are also masked in way to make the computation unidirectional) and (4) applies the classification network MLP2 to the temporal feature to predict whether finding consistent values for cua is feasible.
For model training, note that plan feasibility can be trained on any pair of state sy and future variables (ck')..., (4) where e does not have to be dead-end, thus making it relatively easy to Kk= generate a large amount of training data. For any state 8y/ (i.e., assigned values of (cx) (c=) in the
search tree), if its subtree reaches level k 2 k', the plan feasibility for (cs'...., Ct) is 1, 0 otherwise. The model is trained to minimize the binary cross-entropy loss between the predicted and ground-truth feasibility for (c.,...,ckk) Ck).
5 Backjumping Algorithms
In this section, we present our algorithm that leverages the proposed learning methods backjump- ing heuristics to guide the search. The overall algorithm is similar to backtracking except that, at dead-ends, backtracking replaced by backjumping with ks predicted by the trained model.
Note that refining ca determines the pose of movable object me.
5

---

Since sample a finite number of values for (c=))=0 from their continuous domains, we need mechanism to sample more values a solution is not found with those currently available values. We propose two versions of the algorithm: (I) the batch sampling method, and (2) the forgetting method, differing by how the sampling process is treated. The pseudocodes of both algorithms are presented in the appendix.
In batch sampling, we first draw a batch of N samples for each variable of (ca) k== and then find a consistent sequence of values using the backjumping algorithm. If a solution is not found before the search tree is exhausted, we draw another batch of samples to construct a new search tree. Since the search tree maintains the same set of values, memoization techniques such as no- no-goods can be applied to further accelerate the search, which we leave as future work.
The forgetting method on the other hand does not keep previously sampled values, but discards them and redraws new samples each time the search visits a different level in the search tree. Thus, mem- oization is unavailable the forgetting method, although it may potentially explore the continuous search space effectively.
Both algorithms are run until the time limit is reached. It is open question which of the two methods is more theoretically beneficial (e.g., in terms of convergence rate); we instead show the performance of both methods empirically.
Evaluation
This section reports on experiments designed to evaluate the following hypotheses: (1) How effi- ciently can our backjumping methods find a solution in comparison with backtracking? (2) How well does model generalize different numbers of objects? (3) Which of the backjumping algorithms between batch sampling and forgetting performs more efficiently? We evaluate these hypotheses on the packing and NAMO tasks, described next.
6.1 Evaluation tasks
Our evaluation tasks are implemented in the PyBullet [22] simulator where a PR2 robot is used as mobile manipulator (see Fig. 1). We use PDDL [23, 24] to find plan skeletons in the sequencing
stage and bidirectional RRT [25] as an external motion planner [26] in the specifying stage.
In the packing task, the objective is to move all objects located randomly the right tables into the cabinet on the left. For a
operator where the target region ry is the cabinet, we define the sampling domain the 2D base plane of the cabinet draw placement pose samples p. As the interior space of the cabinet can be accessed from one side only and is not spacious enough, objects placed near the entrance may make placing future objects infeasible.
In the NAMO task, there are 10 movable boxes (in blue) located randomly in the vicinity of the robot's path and 27 fixed boxes (in brown) in the room and the goal is to move the target box (in red) to the goal region (in gray). As blue boxes block the path to reach the target box, the robot must clear them by relocating them in their vicinity. We also define the domain for sampling box placement poses from a circular are on the floor computed with respect to the robot base frame. When moving back to the goal region, with the target box in hand, the robot is unlikely to find feasible motion plan if blue boxes were relocated to blocking positions. Unlike the packing task where objects move from one fixed object to another fixed object, objects moved to and from the same fixed object (i.e., the floor) in NAMO.
6.2 Implementation details
For both backtracking and backjumping,
N = 30 for the packing task and N 4 for the NAMO task. We denote our method and architecture combinations as:
IL-RNN and IL-Attn: Imitation learning with RNN and with multi-head attention, respectively.
PF-RNN and PF-Attn: Plan fcasibility with RNN and with multi-head attention, respectively. The architecture and training details be found in the appendix. For PF, as the trained model outputs a probability of being either feasible or infeasible, we additionally introduce a threshold c
"ood is assignment subset of {cx kk-d that cannot be extended to any solutions.

---

make classification decision robust. We apply the model each step and record predicted probability of being feasible at step h as Pk- We select k' as the first step whose ps < e. is computed by averaging between the maximum and minimum values of pk. where k is an element from (0, (O...., kd 1). Empirically, we find that introducing this adaptive threshold e predicts k* 0.5.
more accurately than a fixed threshold, e.g. setting
All our reported results are obtained by training with 3 different seeds. We observe in our supervised learning setting that changing the seed to train the model does not affect the performance much.
In Sec. 6.5, we show that the forgetting algorithm empirically outperforms batch sampling. Thus, we use the forgetring algorithm to obtain results for planning efficiency and generalization. We include complete results for batch sampling the appendix.
6.3 Planning efficiency
We collect data from 500 problems with 10 objects for packing and from 250 problems for NAMO. New 100 problems and 50 problems are used to test packing and NAMO, respectively.
To measure planning efficiency, we consider the number of nodes visited in the search tree, where fewer nodes imply fewer feasibility checks, leading to faster planning. As shown in the top rows of Table 1, in both tasks, our backjumping methods are significantly more efficient than backtracking. We also show how closely our backjumping k- approximates the ground- touund-truth k* in the appendix.
In NAMO, imitation learning outperforms plan feasibility. We conjecture that movable objects in NAMO do not affect each other (i.e., relocating one box does not affect the feasibility of relocating another box), making it easier for imitation learning to find k* close to k*.
We also show in the appendix that some methods still greatly outperform backtracking with fewer training data, and that the performances in Table 1 can further be improved with more training data.
The number of nodes visited in the search tree. Numbers represent the mean + 95% confidence interval computed by solving 100 problems. the middle rows, numbers in (-) represent the number objects tested. In the bottom row, BS represents batch sampling. The number with * represents the best-performing method. The bolded numbers are those whose performance is not statistically significantly different from the one with * (i.e, their confidence intervals are overlapping).
Table I:
Task
Backtracking
IL RNN
IL Attn
PF RNN
PF Attn
Packing
4414 + 879
2464 464
2638 + 602
2205 313
2062 + 297"
NAMO
(21 + 10) x 1
543 1 187
425 1 153"
529 + 188
2614.7 1 709.5
Packing (11)
12098 + 2518
5350 + 1094'
7044 + 1481
6142 + 767
7109 + 809
Packing (12)
34719 = 6514
15139 = 3080
16339 - 3971
22377 3244
31824 + 3925
Packing (BS)
13541 = 4205
4464 + 1160
7073 + 2040
4556 + 749
4311 + 690"
6.4
Generalization
We examine whether our method can generalize to novel number of objects. In particular, we train our model using 10 objects and test with more objects (i.e., 11 and 12 objects). Note that adding more objects to the packing task is more challenging than removing objects as it leads to more dead-ends and harder estimation of k.* due insufficient space in the cabinet.
As shown in the middle rows of Table 1, our methods still significantly outperform backtracking and the performance ratios of our methods and backtracking remain similar those in the top rows where the number of objects is the same for both training and testing, with the only exception of PF Attn in Packing (II) and (12). We conjecture that the use of GNNs allows our learning models to handle novel numbers of objects.
6.5 Comparison of backjumping algorithms
As shown in the bottom row of Table 1, evaluated on the same set of 100 problems packing with 10 objects, batch sampling is about 2 ~ times slower than forgetting, while still outperforming
7

---

backtracking. Although forgetting empirically exceeds batch sampling in evaluation, we point out in Sec. 5 that enhancing batch sampling is potentially achievable by leveraging ideas from the constraint satisfaction literature [7].
Related Work
In TAMP [27, 10, 28, 4, 16], geometric failures are often used to provide feedback task-level planning to guide its search. However, this feedback in literature is mostly local [5] meaning that the failure is involved with a particular sequence of actions. In this work, we propose a global feedback that considers the entire plan skeleton by leveraging backjumping.
The minimum constraint removal (MCR) problem [3] is related to our problem as its objective is to find a parsimonious set of objects to remove in order to reach a goal region. Our problem is generalization to MCR in that a goal placement of an object not defined and that objects are not removed but relocated. Since MCR is NP-hard, our problem also falls into the NP-hard category.
The most relevant papers papers address shortcomings of backtracking. A method proposed in the culprit detection problem generates global feedback from failures in answer set programming [29] but it pre-discretizes the state which may ignore certain motion constraints. The work [12] improves the efficiency of back- tracking by jointly optimizing parameters such as trajectory, grasp, and placement pose; their work uses trajectory optimization, which is competing framework for sampling-base basdd motion planning our method is based on.
work the culprit detection problem [5] and the work [12]: both
Learning other heuristics to improve planning efficiency has been proposed in the TAMP and motion planning communities, such predicting feasibility the motion level [30, 31, 32] and guiding sampling [33, 34]. Instead, our approach learns task-level heuristics by analyzing long-horizon dependencies, which can potentially complement existing heuristics to improve efficiency further.
Limitations
Besides future work discussed the paper, some limitations of the presented work are as follows: (1) We consider incorporating backjumping with given single plan skeleton only, not with set of possible plan skeletons, which may be critical when objects have substantially different sizes.
(2) We test on relatively simple geometric objects and assume known 3D CAD models. A more alistic geometry of objects, egg., constructed by point clouds, in our framework, is future direction.
(3) We evaluate with the same geometry of obstacles (iee, the same cabinet in packing and the same arrangement of fixed objects in NAMÓ). Future work would be to achieve generalization to novel geometry of obstacles drawn from some distribution.
Conclusion
In this paper, we present learning frameworks learn backjumping heuristics from data identify the culprit action aimed at improving the efficiency of solving TAMP problems. Our experimental results demonstrate our method exceeds backtracking by far terms of planning efficiency and its generalization to problems with novel numbers of objects.
Acknowledgments
This work has taken place in the Learning Agents Research Group (LARG) UT Austin. LARG research is supported in part by NSF (CPS- 1739944,, 1724172,,57 FAIN-2019844), ONR (N00014- 18-2243), ARO IF-11I9-1122-33333 DARPA, GM, Bosch, and UT Austin's Good Systems grand challenge. Peter Stone serves as the Executive Director of Sony AI America and receives financial compensation for this work. The terms of this arrangement have been reviewed and approved by the University of Texas at Austin in accordance with its policy on objectivity in research.

---

References
[1] C. R. Garrett, R. Chitnis, R. Holladay, B. Kim, T. Silver, L. P. Kaelbling, and T. Lozano- Integrated task and motion planning. Annual review of control, robotics, and autonomous systems, 4:265 293, 2021.
[2] M. Stilman, J.-U. Schamburek, J. Kuffner, and T. Asfour. Manipulation planning among mov- able obstacles. In Proceedings 2007 IEEE international conference on robotics and automa- tion, pages 3327-3332. IEEE, 2007.
[3] K. Hauser. The minimum constraint removal problem with three robotics applications. The International Journal of Robotics Research, 33(():5-17, 2014.
[4] S. Srivastava, E. Fang, L.. Riano, R. Chitnis, S. Russell, and P. Abbeel. Combined task and motion planning through an extensible planner-independent interface layer. In 2014 IEEE international conference robotics and automation (ICRA), pages 639-646. IEEE, 2014.
[5] F. Lagriffoul and B. Andres. Combining task and motion planning: A culprit detection prob- lem. The International Journal of Robotics Research, 35(8):890-927, 2016.
[6] J. Bidot, L. Karlsson, F. Lagriffoul, and A. Saffiotti. Geometric backtracking for combined task and motion planning in robotic systems. Artificial Intelligence, 247:229 -265, 2017.
[7] R. Dechter, D. Cohen, et al. Constraint processing. Morgan Kaufmann, 2003.
[8] T. N. Kipf and M. Welling, Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:16099 02907, 2016.
(9] B. Kim, Shimanuki, L. Kaelbling, and Lozano- Pérez. Representation, learning, and planning algorithms for geometric task and motion planning. The International Journal of Robotics Research, 41(2):210-231 2022.
[10] L. P. Kaelbling and T. Lozano-Pérez. Integrated task and motion planning in belief space. The International Journal of Robotics Research,
2013.
[11] C. R. Garrett, Paxton, T. Lozano-Pérez, L. Kaelbling, and D. Fox. Online replanning in belief space for partially observable task and motion problems. In 2020 IEEE International Conference on Robotics and Automation (ICRA), pages 5678-5684. IEEE, 2020.
[12] D. Moddield-Menell. C. Lin, R. Chitnis, S. Russell, and P. Abbeel. Sequential quadratic pro- gramming for task plan optimization. In 2016 IEEE/RSJ International Conference on Intelli- gent Robots and Systems (IROS), pages 5040-5047. IEEE, 2016.
[13] C. R. Garrett, T. Lozano-Pérez, and L. P. Kaelbling, Sampling- based methods for factored task and motion planning. The International Journal of Robotics Research, 37(13-14):1796- 2018.
[14] N. T. Dantam, Z. K. Kingston, S. Chaudhuri, and L. E. Kavraki. An incremental constraint- based framework for task and motion planning. The International Journal of Robotics Re- search, 37(10):1134 1151, 2018.
[15] M. A. Toussaint, K. R. Allen, A. Smith, and J. Tenenbaum. Differentiable physics and stable modes for tool-use and manipulation planning. 2018.
[16] S.-Y. S. Zhang, and P. Stone. The petlon algorithm to plan efficiently for task-level-optimal navigation. Journal of Artificial Intelligence Research, 1-500, 2020.
[17] C. R. Garrett, T. Lozzno-Pérez, and I.. P. Kaelbling. Pddistream: Integrating symbolic planners and blackbox samplers via optimistic adaptive planning. In Proceedings of the International Conference on Automated Planning and Scheduling, volume 30, pages 440-448, 2020.
[18] T. Lozano-Pérez and L. P. Kaelbling. A constraint-based method for solving sequential manip- ulation planning problems. In 2014 IEEF/RSJ International Conference on Intelligent Robots and Systems, pages 3684-3691. IEEE, 2014.

---

[19] K. Hauser and J.-C. Latombe. Multi-modal motion planning in non-expansive spaces. The International Journal of Robotics Research, 29(7):897-915, 2010.
[20] S. Hochreiter and J. Schmidhuber. Long short-term memory. Neural computation, 978):1335- 1780, 1997.
[21] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and Polosukhin. Attention is all you need. Advances in neural information processing systems, 30, 2017.
[22] E. Coumans and Y. Bai. Pybullet, python module for physics simulation for games, robotics and machine learning. 2016.
[23] M. Fox and D. Long. Pdd12. 1: An extension to pddl for expressing temporal planning domains. Journal of artificial intelligence research, 20:61-124, 2003.
[24] T. Silver and R. Chitnis. Pddlgym: Gym environments from pddl problems. arXiv preprint
200.:22002.06432, 2020.
[25] J. Kuffner and S. M. LaValle. Rrt-connect: An efficient approach to single-query path planning. In Proceedings 2000 ICRA. Millennium Conference. IEEE International Conference on Robotics and Automation. Symposia Proceedings (Cat. No. 00CH37065), volume 2, pages 995-1001. IEEE, 2000.
[26] C. Garrett. Pybullet planning. mouullet-plannnnge 2018.
Available https://pppi.cog/proooes
[27] C. Dornhege, P. Eyerich, T. Keller, Trüg, M. Brenner, and B. Nebel. Semantic attachments for domain- -ineiinnindependent planning systems. In Nineteenth International Conference on Auto- mated Planning and Scheduling, 2009.
[28] L. de Silva, A. K. Pandey, and R. Alami. An interface for interleaved symbolic-geomette planning and backtracking, In 2013 IEEE/RSJ International Conference on Intelligent Robots and Systems, pages 232-239. IEEE, 2013.
[29] V. Lifschitz. Answer set programming. Springer Heidelberg, 2019.
[30] A. M. Wells, N. T. Dantam, A. Shrivastava, and L. E. Kavraki. Learning feasibility for task and motion planning in tabletop environments. IEEE robotics and automation letters, 4(2): 2255-1262,2013 2019.
[31] D. Driess, O. Oguz, J.-S. Ha, and M. Toussaint. Deep visual heuristics: Learning feasibility of mixed-integer programs for manipulation planning. In 2020 IEEE International Conference Robotics and Automation (ICRA), pages 9563-9569. IEEE, 2020.
[32] S. Li and N. T. Dantam. Learning proofs of motion planning infcasibility. In Robotics: Science and Systems, 2021.
[33] R. Chitnis, D. Hadfield-Menell A. Gupta, S. Srivastava, E. Groshev, C. Lin, and P. Abbeel. Guided search for task and motion plans using learned heuristics. In 2016 IEEE International Conference on Robotics and Automation (ICRA), pages 447-454. IEEE, 2016.
[34] C. Zhang, J. Huh, and D. D. Lee. Learning implicit sampling distributions for motion planning. In 2018 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages IEEE, 2018.
10


Reviews:
[{"review_id": "t4hPE_cQLfI", "reviewer": "Reviewer_MW4W", "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.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths of the Paper**\n\n1) 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. \n2) Even though no theoretical analysis is provided, the empirical evaluation of the proposed approaches are well-executed and convincing. \n3) The quality of presentation is high in general, although some improvements could be made (see the weaknesses section below).\n\n\n**Weaknesses of the Paper**\n1) (*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.\n\n2) (*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.\n\n[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.\n\n[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.\n\n**Other Minor Points and Questions**\n\n1) (*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.\n2) (*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?\n3) (*Resolved after rebuttal*) In tables, how specifically is “statistically significantly different from one with *” determined?\n4) (*Resolved after rebuttal*) Typo: “On important practical challenge” → “One important practical challenge” (Section 1, line 17) \n5) (*Resolved after rebuttal*) Typo: “Often done often” → “Often done” (Section 1, line 26).\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "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).~~\n\nMy 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.", "technical_quality": "Very Good:  Convincing.", "clarity_of_presentation": "Very Good:  Well organized and clear.", "potential_impact": "", "robotics_focus": "Highly relevant to robotics but no hardware experiments", "quality_of_limitations": "Limitations are addressed clearly", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"impact": "4: The work contains interesting new ideas that will potentially have major impact in robotics or machine learning.", "issues": "~~Please refer to the weaknesses section and the questions stated above.~~", "reviewer_expertise": "3: The reviewer is fairly confident that the evaluation is correct"}, "extra_text": {}}, {"review_id": "ixXjdY79TUW", "reviewer": "Reviewer_q4VZ", "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.\n\nIf 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.\n\nThis 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.\n\nThe authors evaluate the approach in two simulated robotics problems, and demonstrate improvements in search efficiency over backtracking.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\n* 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. \n\n* The learning approach and model architectures seem reasonable, and the results on evaluation tasks demonstrate a significant improvement over backtracking.\n\nWeaknesses:\n\n* (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?\n* (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. \n* 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.\n\nQuestions:\n\n(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?\n\n(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.\n\n(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?\n\nDo you have any insight as to why the PF Attn models are doing so much worse than PF RNN?\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "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. \n\n(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.", "technical_quality": "Good: Generally convincing, but some additional experiments or analyses needed.", "clarity_of_presentation": "Good: Minor revision needed to improve organization or clarity.", "potential_impact": "", "robotics_focus": "Highly relevant to robotics but no hardware experiments", "quality_of_limitations": "Additional details required", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"impact": "3: The work is incremental and unlikely to have much impact, even though it may be technically correct and well executed.", "reviewer_expertise": "4: The reviewer is confident but not absolutely certain that the evaluation is correct"}, "extra_text": {"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.\n\n* (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.\n\n\n"}}, {"review_id": "QRvWybiLyJZ3", "reviewer": "Reviewer_Kqwz", "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. ", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.\n\nOne 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. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "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.~~\n\nThe authors addressed my central concerns in their response. ", "technical_quality": "Very Good:  Convincing.", "clarity_of_presentation": "Good: Minor revision needed to improve organization or clarity.", "potential_impact": "", "robotics_focus": "Highly relevant to robotics but no hardware experiments", "quality_of_limitations": "Additional details required", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"impact": "3: The work is incremental and unlikely to have much impact, even though it may be technically correct and well executed.", "issues": "~~Question of what happens when the model is inaccurate is inadequately addressed~~", "reviewer_expertise": "2: The reviewer is willing to defend the evaluation, but it is quite likely that the reviewer did not understand central parts of the paper"}, "extra_text": {}}, {"review_id": "KoYYftzyBrL", "reviewer": "Reviewer_MGEc", "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.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "strengths:\n- the proposed predictor is effective at solving similar problems being tested\n\nweaknesses:\n- full state knowledge is assumed, and\n- 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?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "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.\n", "technical_quality": "Fair: Significant additional evidence required to support the claims.", "clarity_of_presentation": "Good: Minor revision needed to improve organization or clarity.", "potential_impact": "", "robotics_focus": "Relevant but unlikely to deploy to hardware in near future", "quality_of_limitations": "Additional details required", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"impact": "3: The work is incremental and unlikely to have much impact, even though it may be technically correct and well executed.", "reviewer_expertise": "3: The reviewer is fairly confident that the evaluation is correct"}, "extra_text": {"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.\n- varying training data size: why increasing the data size 4-fold doesn't improve the prediction efficiency?\n- what are the computation times (wall-clock time)? \n- 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?\n- 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.\n\n[R1] D. Driess et al., \"Deep Visual Heuristics: Learning Feasibility of Mixed-Integer Programs for Manipulation Planning\", IEEE ICRA, 2020.\n"}}]

Author rebuttal:

Decision: Accept (poster)