# Learning to Correct Mistakes: Backjumping in Long-Horizon Task and Motion
Planning

Yoonchang Sung1*, Zizhao Wang1*, Peter Stone1,2
1The University of Texas at Austin 2Sony AI

###### 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 on 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.

> Keywords: Task and motion planning, heuristic learning, supervised leanring

##  1 Introduction

**footnotetext: Equal contribution.

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 a 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 long-horizon tasks with
a large number of objects, the search space becomes intractable due to a large
depth and branching factor.

Figure 1: (Left) An illustration of the packing task, whose goal is to move
all red objects into the 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, we address the challenges of long-horizon TAMP where early
actions in the plan may make future actions infeasible. For example, as shown
in Fig. 1, if the robot places the first few objects near the cabinet entrance
in a packing task, or on the target retrieval path in a navigation among
movable obstacles (NAMO [2]) task, the problems become infeasible, unless the
culprit actions that 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 complexity 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.
However, 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 a learning approach by shifting the computational burden to
the training phase where training data is collected by solving backtracking
problems. Our observation is 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 if the solution can be found after
each action. Our proposed learning process is a domain-independent way of
learning domain-specific heuristics. We summarize our contributions as
follows:

  * •

We propose two backjumping heuristic learning methods to 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 a 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 a particular subclass of TAMP called _geometric
TAMP_ (G-TAMP [9]) for clarity of presentation. In G-TAMP, a mobile
manipulator is tasked with moving multiple objects to target regions among
movable obstacles. We assume quasi-static dynamics of the world111The objects
remain in stable states after being manipulated by the robot., deterministic
effects of actions, and fully-observable 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 as future work.

Formally, a G-TAMP problem is defined by a tuple
$<\mathcal{M},\mathcal{R},\mathcal{O},F,T,\mathcal{G},s_{0}>$ where
$\mathcal{M}$ is a set of _movable objects_ , $\mathcal{R}$ is a set of
_target regions_ , $\mathcal{O}$ is a set of _operators_ , $F$ is a
_feasibility checking function_ , $T$ is a _transition function_ ,
$\mathcal{G}$ is a _goal set_ , and $s_{0}$ is an _initial state_. The goal is
to find a sequence of grounded and refined operators222We say that an operator
is _grounded_ if its discrete parameters are specified and _refined_ if its
continuous parameters are specified. starting from $s_{0}$ to reach a state
$s\in\mathcal{G}$.

$\mathbin{\vbox{\hbox{\scalebox{0.75}{$\bullet$}}}}$ $\mathcal{M}$,
$\mathcal{R}$ and $s$: In G-TAMP, the environment consists of any number of
_fixed objects_ such as tables, $N_{\mathcal{M}}$ movable objects
$\mathcal{M}=\\{m_{i}\\}_{i=1}^{N_{\mathcal{M}}}$ such as cups, and
$N_{\mathcal{R}}$ target regions
$\mathcal{R}=\\{r_{j}\\}_{j=1}^{N_{\mathcal{R}}}$. We denote the _world state_
by $s$ which consists of the robot configuration and the pose of each movable
object.

$\mathbin{\vbox{\hbox{\scalebox{0.75}{$\bullet$}}}}$ $\mathcal{O}$: Operators
in G-TAMP move one object to a region, such as PickandPlace and Push. Each
refined operator $o\left(d=(m_{i},r_{j}),c=(q,g)\right)\in\mathcal{O}$
consists of (1) the _discrete parameter_ $d\in\mathcal{M}\times\mathcal{R}$
specifying which object to move and which region to move it to, and (2) the
_continuous parameters_ $c$ composed of a grasp $g\in\mathit{SE}(3)$333The
special Euclidean group $\mathit{SE}(3)$ is used to express a 3D rigid-body
transformation consisting of translation and rotation. on $m_{i}$ and a
placement pose $q\in\mathit{SE}(3)$ in $r_{j}$.

$\mathbin{\vbox{\hbox{\scalebox{0.75}{$\bullet$}}}}$ $F$ and $T$: The
feasibility of an operator can be determined by evaluating constraints (e.g.,
reachability and collision avoidance) using an external motion planner. We
denote this feasibility evaluation as a Boolean-valued function
$F(s,o)\rightarrow\\{0,1\\}$. If the operator is feasible, a deterministic
transition function $T(s,o)$ determines the new state $s^{\prime}$.

$\mathbin{\vbox{\hbox{\scalebox{0.75}{$\bullet$}}}}$ $\mathcal{G}$: A goal set
$\mathcal{G}$ is defined as a conjunction of predicates, such as
$\mbox{{InCabinet}}\left(m_{i},r_{j}=\mbox{{Cabinet}}\right)$ which becomes
True if $m_{i}$ is stably located in the cabinet.

Figure 2: (a) Constraint network consisting of variables represented by
circles (continuous variables: $s$ and $c$, and discrete variables: $d$)
connected by constraints $F$ represented by squares. (b) Example of a search
tree when a dead-end is met at level $4$ (i.e., $k^{d}$). Orange squares
represent sampled values ($N$ values at each level). Orange shaded area
denotes a particular assignment to $(c_{0},...,c_{3})$ (i.e., a partial plan).
All values of $c_{4}$ are inconsistent with this partial plan causing the
dead-end. Maximum jump $k^{\star}$ in this example is $1$ (a culprit variable
is $c_{1}$ denoted by a blue circle), and thus, $\mathcal{K}=\\{1,2,3\\}$.

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 ($s_{k}$ and $c_{k}$) or discrete ($d_{k}$), and squares
represent _constraints_ ($F_{k}$). When the plan length is $K$, we find values
for sets of variables $\\{d_{k}\\}_{k=0}^{K-1}$ and $\\{c_{k}\\}_{k=0}^{K-1}$
such that all constraints $\\{F_{k}\\}_{k=0}^{K-1}$ are satisfied and
$s_{K}\in\mathcal{G}$.

###  2.2 Sequence-before-specify strategy

Sequence-before-satisfy [4, 12, 13, 14, 15, 16, 17, 1] is 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 skeleton_ s [18]
reaching the goal set $\mathcal{G}$ symbolically only, i.e.,
$(d_{k})_{k=0}^{K-1}$ are computed but their continuous counterparts
$(c_{k})_{k=0}^{K-1}$ are left unspecified. (2) In the specifying stage, the
strategy chooses a plan skeleton often based on AI planning heuristics and
_refine_ s $(c_{k})_{k=0}^{K-1}$ satisfying the constraints and a goal
condition. For notational simplicity, in the rest of the paper, we use $m_{k}$
to represent the object moved by operator $o_{k}$. We treat objects that are
not included in a grounded plan as fixed objects.

Note that the two stages repeat until either finding a 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.

Backtracking search is generally used to find values of $(c_{k})_{k=0}^{K-1}$
in the specifying stage by constructing a search tree rooted from $c_{0}$
(Fig. 2(b)). Since the domain of $c_{k}$ is continuous, the strategy uses
sampling (e.g., uniform sampling from the domain of $c_{k}$ [19]) to obtain
$N$ refined values to select from. Index $k$ corresponds to both the level of
the tree and the step in the plan skeleton. When the assigned values of
$(c_{0},...,c_{k-1})$ are inconsistent with all sampled values of $c_{k}$
(i.e., violating the constraint $F_{k}$), we say the search hits a _dead-end_
and denote the dead-end level by $k^{d}$. The search then backtracks to a
parent node $c_{k-1}$ to assign another value and retries the consistency
check with $c_{k}$. If successful, a child node $c_{k+1}$ is evaluated at the
next level, otherwise another value of $c_{k-1}$ is attempted. Backtracking
repeats this process exhaustively until it finds values of
$(c_{k})_{k=0}^{K-1}$ that are consistent, i.e., the solution of a problem.

##  3 Problem Description

When the planning horizon is long, the above backtracking-based strategy
becomes intractable as 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, at level $k^{d}$, _safe jump_ corresponds to an ancestor level
$k<k^{d}$ such that attempting all possible values of its descendants at all
levels between $k$ and $k^{d}$ does not resolve the dead-end. We denote all
safe-jump levels by a set $\mathcal{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^{\star}=\min\mathcal{K}$. Correspondingly, we call $c_{k^{\star}}$ a
_culprit variable_ responsible for making all values of $c_{k}$ being
inconsistent with a partial plan.

The objective is to find $k^{\star}$ to backjump safely and maximally whenever
a dead-end is met at level $k^{d}$, thus improving the overall efficiency of
the sequence-before-specify strategy.

##  4 Backjump Learning Methods

The constraint network in Fig. 2(a) contains a chain structure with respect to
constraints $F_{k}$ by considering $d_{k}$, $c_{k}$, and $s_{k}$ as one 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^{\star}$ as we use sampling to handle continuous domains.
For these reasons, $k^{\star}$ identification using backjumping is inherently
challenging in TAMP.

It is however possible to find an approximation of $k^{\star}$ with
backtracking since it evaluates all possible combinations of assignments using
all sampled values from the root to level $k^{d}$. Also, since $k^{\star}$
always _exists_ for any dead-end situations and is _unique_ , we can hope to
gather less noisy labeled data with a sufficient amount of samples. Leveraging
these observations, we propose two alternative supervised learning methods to
identify $k^{\star}$, where training labels are gathered by solving tasks from
the same distribution using backtracking.

The robot configuration is used in an external motion planner to check the
feasibility of a corresponding refined operator, but it is not used in our
learning models. We thus define a new state notation $\bar{s}$ consisting of
poses of movable objects only.

Figure 3: Architectures of the learning models. In each graph, state
$\bar{s}_{k}$ implies that objects $(m_{0},...,m_{k-1})$ are relocated by the
robot while other objects $(m_{k},...,m_{K})$ remain in their original
locations.

###  4.1 Imitation learning

When the search hits a dead-end at level $k^{d}$, we first propose a predictor
to directly predict the maximum jump $k^{\star}$ in the domain of
$\\{0,\dots,k^{d}-1\\}$, from the sequence of states
$(\bar{s}_{1},\dots,\bar{s}_{k^{d}})$ and the geometric attributes of a
movable object $m_{k^{d}-1}$ (e.g., size). In our model, each state $\bar{s}$
is represented by a 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^{\star}$, our 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 a
bidirectional recurrent neural network (bRNN [20]) or multi-head attentions
[21], (3) extracts the movable object features from $m_{k^{d}}$ with MLP1
(multilayer perceptron), and (4) with pairs of temporal features and object
features as inputs, applies the same prediction network MLP2 to predict the
likelihood of each step being $k^{\star}$. The model is trained to minimize
the cross-entropy loss between the predicted likelihood of being $k^{\star}$
and the ground-truth $k^{\star}$ label.

The $k^{\star}$ labels are collected from the backtracking tree search. At any
$k^{d}$, we record its current state trajectory as
$(\bar{s}_{1},\dots,\bar{s}_{k^{d}})$. When the backtracking successfully
reaches the level $k^{d}$ for the first time after the dead-end, we record its
state trajectory up to level $k^{d}$ as
$(\bar{s}^{\prime}_{1},\dots,\bar{s}^{\prime}_{k^{d}})$. Let $\bar{s}_{i}$ and
$\bar{s}^{\prime}_{i}$ be the $i$-th element from the corresponding trajectory
sequences. The $k^{\star}$ is the first level where two trajectories diverge,
i.e.,
$k^{\star}=\operatorname*{arg\,min}_{i}\big{\\{}i\in\\{0,...,k^{d}-1\\}\big{|}\bar{s}_{i+1}\neq\bar{s}^{\prime}_{i+1}\big{\\}}$.

###  4.2 Plan feasibility

Besides directly estimating $k^{\star}$, we investigate an alternative
_counterfactual_ approach that learns a binary classifier to predict whether a
refined partial plan at each level contributes to a dead-end. We use the
predicted labels (i.e., either feasible or infeasible) to identify which level
corresponds to $k^{\star}$.

Specifically, with a sequence of states $(s_{1},\dots,s_{k^{d}})$ that faces a
dead-end at level $k^{d}$, we start with $s_{1}$ where only $c_{0}$ is refined
(i.e., a value is assigned) but the rest of the variables
$(c_{k})_{k=1}^{k^{d}}$ are not refined yet.444Note that refining $c_{k}$
determines the pose of a movable object $m_{k}$. Then, the classifier predicts
whether finding a consistent assignment of values for $(c_{k})_{k=1}^{k^{d}}$
is feasible. If infeasible, it implies that the placement of $m_{0}$ is a
culprit action making the rest of variables $(c_{k})_{k=1}^{k^{d}}$
inconsistent with $c_{0}$. By definition, level 0 becomes the maximum jump
$k^{\star}$. If feasible, we continue with $s_{2}$ where $c_{0}$ and $c_{1}$
are refined only and the classifier predicts feasibility for
$(c_{k})_{k=2}^{k^{d}}$. 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^{\star}$, or continue to the
next step otherwise.

Let $k^{\prime}\in\\{1,...,k^{d}\\}$ be the step where
$(c_{k})_{k=0}^{k^{\prime}-1}$ are refined and feasibility for
$(c_{k})_{k=k^{\prime}}^{k^{d}}$ is to be evaluated. As shown in Figure 3(b),
to predict whether a level $k^{\prime}<k^{d}$ is a safe jump, our model (1)
extracts the state features from $\bar{s}_{k^{\prime}}$ using GNN, (2)
extracts the object features from $(m_{k})_{k=k^{\prime}}^{k^{d}}$ each with
MLP1, (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 a way to make the computation unidirectional) and
(4) applies the classification network MLP2 to the temporal feature to predict
whether finding consistent values for $c_{k^{d}}$ is feasible.

For model training, note that plan feasibility can be trained on any pair of
state $s_{k^{\prime}}$ and future variables $(c_{k^{\prime}},\dots,c_{k})$
where $c_{k}$ does not have to be a dead-end, thus making it relatively easy
to generate a large amount of training data. For any state $s_{k^{\prime}}$
(i.e., assigned values of $(c_{k})_{k=0}^{k^{\prime}-1}$ in the search tree),
if its subtree reaches a level $k\geq k^{\prime}$, the plan feasibility for
$(c_{k^{\prime}},\dots,c_{k})$ is 1, or 0 otherwise. The model is trained to
minimize the binary cross-entropy loss between the predicted and ground-truth
feasibility for $(c_{k^{\prime}},\dots,c_{k})$.

##  5 Backjumping Algorithms

In this section, we present our algorithm that leverages the proposed learning
methods as backjumping heuristics to guide the search. The overall algorithm
is similar to backtracking except that, at dead-ends, backtracking is replaced
by backjumping with $k^{\star}$ predicted by the trained model.

Since we sample a finite number of values for $(c_{k})_{k=0}^{K-1}$ from their
continuous domains, we need a mechanism to sample more values if a solution is
not found with those currently available values. We propose two versions of
the algorithm: (1) 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
$(c_{k})_{k=0}^{K-1}$, 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-goods_ 555No-good is an assignment to a subset of
$\\{c_{k}\\}_{k=0}^{K-1}$ that cannot be extended to any solutions. 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, memoization is unavailable in 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 an 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.

##  6 Evaluation

This section reports on experiments designed to evaluate the following
hypotheses: (1) How _efficiently_ can our backjumping methods find a solution
in comparison with backtracking? (2) How well does our model _generalize_ to
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, as described next.

###  6.1 Evaluation tasks

Our evaluation tasks are implemented in the PyBullet [22] simulator where a
PR2 robot is used as a 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 on
the right tables into the cabinet on the left. For a PickandPlace operator
where the target region $r_{j}$ is the cabinet, we define the sampling domain
as the 2D base plane of the cabinet to 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 $p$ from a circular arc 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 a 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 are moved to and
from the same fixed object (i.e., the floor) in NAMO.

###  6.2 Implementation details

For both backtracking and backjumping, we use $N=30$ for the packing task and
$N=4$ for the NAMO task. We denote our method and architecture combinations
as:
$\mathbin{\vbox{\hbox{\scalebox{0.75}{$\bullet$}}}}$ IL-RNN and IL-Attn:
Imitation learning with RNN and with multi-head attention, respectively.
$\mathbin{\vbox{\hbox{\scalebox{0.75}{$\bullet$}}}}$ PF-RNN and PF-Attn: Plan
feasibility with RNN and with multi-head attention, respectively.
The architecture and training details can 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 $\epsilon$ to make a
classification decision robust. We apply the model to each step and record a
predicted probability of being feasible at step $k$ as $p_{k}$. We select
$k^{\star}$ as the first step whose $p_{k}<\epsilon$. $\epsilon$ is computed
by averaging between the maximum and minimum values of $p_{k}$, where $k$ is
an element from $(0,\dots,k^{d}-1)$. Empirically, we find that introducing
this adaptive threshold $\epsilon$ predicts $k^{\star}$ more accurately than a
fixed threshold, e.g., setting $\epsilon=0.5$.

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 forgetting algorithm to obtain results for
planning efficiency and generalization. We include complete results for batch
sampling in 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 $\hat{k}^{\star}$ approximates the
ground-truth $k^{\star}$ 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 $\hat{k}^{\star}$ close to $k^{\star}$.

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.

Table 1: The number of nodes visited in the search tree. Numbers represent the mean $\pm$ 95% confidence interval computed by solving 100 problems. In the middle rows, numbers in $(\cdot)$ represent the number of 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). Task | Backtracking | IL RNN | IL Attn | PF RNN | PF Attn
---|---|---|---|---|---
Packing | 4414 $\pm$ 879 | 2464 $\pm$ 464 | 2638 $\pm$ 602 | 2205 $\pm$ 313 | 2062 $\pm$ 297$*$
NAMO | (21 $\pm$ 10) $\times 10^{4}$ | 543 $\pm$ 187 | 425 $\pm$ 153$*$ | 529 $\pm$ 188 | 2614.7 $\pm$ 709.5
Packing (11) | 12098 $\pm$ 2518 | 5350 $\pm$ 1094$*$ | 7044 $\pm$ 1481 | 6142 $\pm$ 767 | 7109 $\pm$ 809
Packing (12) | 34719 $\pm$ 6514 | 15139 $\pm$ 3080$*$ | 16339 $\pm$ 3971 | 22377 $\pm$ 3244 | 31824 $\pm$ 3925
Packing (BS) | 13541 $\pm$ 4205 | 4464 $\pm$ 1160 | 7073 $\pm$ 2040 | 4556 $\pm$ 749 | 4311 $\pm$ 690$*$

###  6.4 Generalization

We examine whether our method can generalize to a 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^{\star}$, due to 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 to 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 (11) 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 in packing with 10 objects, batch sampling is about 2 $\sim$ 3 times
slower than forgetting, while still outperforming backtracking. Although
forgetting empirically exceeds batch sampling in our evaluation, we point out
in Sec. 5 that enhancing batch sampling is potentially achievable by
leveraging ideas from the constraint satisfaction literature [7].

##  7 Related Work

In TAMP [27, 10, 28, 4, 16], geometric failures are often used to provide
feedback to 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 a generalization to MCR in that a goal
placement of an object is 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 to our work are the culprit detection problem [5] and
the work [12]; both 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 backtracking by jointly optimizing parameters such as trajectory, grasp,
and placement pose; their work uses trajectory optimization, which is a
competing framework for sampling-based motion planning our method is based on.

Learning other heuristics to improve planning efficiency has been proposed in
the TAMP and motion planning communities, such as predicting feasibility at
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.

##  8 Limitations

Besides future work discussed in the paper, some limitations of the presented
work are as follows:
(1) We consider incorporating backjumping with a given single plan skeleton
only, not with a 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 realistic geometry of objects, e.g., constructed by point
clouds, in our framework, is a future direction.
(3) We evaluate with the same geometry of obstacles (i.e., the same cabinet in
packing and the same arrangement of fixed objects in NAMO). Future work would
be to achieve generalization to novel geometry of obstacles drawn from some
distribution.

##  9 Conclusion

In this paper, we present learning frameworks to learn backjumping heuristics
from data to identify the culprit action aimed at improving the efficiency of
solving TAMP problems. Our experimental results demonstrate our method exceeds
backtracking by far in 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) at UT
Austin. LARG research is supported in part by NSF (CPS-1739964, IIS-1724157,
FAIN-2019844), ONR (N00014-18-2243), ARO (W911NF-19-2-0333), 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

  * Garrett et al. [2021] C. R. Garrett, R. Chitnis, R. Holladay, B. Kim, T. Silver, L. P. Kaelbling, and T. Lozano-Pérez.  Integrated task and motion planning.  _Annual review of control, robotics, and autonomous systems_ , 4:265–293, 2021.
  * Stilman et al. [2007] M. Stilman, J.-U. Schamburek, J. Kuffner, and T. Asfour.  Manipulation planning among movable obstacles.  In _Proceedings 2007 IEEE international conference on robotics and automation_ , pages 3327–3332. IEEE, 2007.
  * Hauser [2014] K. Hauser.  The minimum constraint removal problem with three robotics applications.  _The International Journal of Robotics Research_ , 33(1):5–17, 2014.
  * Srivastava et al. [2014] 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 on robotics and automation (ICRA)_ , pages 639–646. IEEE, 2014.
  * Lagriffoul and Andres [2016] F. Lagriffoul and B. Andres.  Combining task and motion planning: A culprit detection problem.  _The International Journal of Robotics Research_ , 35(8):890–927, 2016.
  * Bidot et al. [2017] 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.
  * Dechter et al. [2003] R. Dechter, D. Cohen, et al.  _Constraint processing_.  Morgan Kaufmann, 2003.
  * Kipf and Welling [2016] T. N. Kipf and M. Welling.  Semi-supervised classification with graph convolutional networks.  _arXiv preprint arXiv:1609.02907_ , 2016.
  * Kim et al. [2022] B. Kim, L. Shimanuki, L. P. Kaelbling, and T. 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.
  * Kaelbling and Lozano-Pérez [2013] L. P. Kaelbling and T. Lozano-Pérez.  Integrated task and motion planning in belief space.  _The International Journal of Robotics Research_ , 32(9-10):1194–1227, 2013.
  * Garrett et al. [2020] C. R. Garrett, C. Paxton, T. Lozano-Pérez, L. P. 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.
  * Hadfield-Menell et al. [2016] D. Hadfield-Menell, C. Lin, R. Chitnis, S. Russell, and P. Abbeel.  Sequential quadratic programming for task plan optimization.  In _2016 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , pages 5040–5047. IEEE, 2016.
  * Garrett et al. [2018] 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–1825, 2018.
  * Dantam et al. [2018] 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 Research_ , 37(10):1134–1151, 2018.
  * Toussaint et al. [2018] M. A. Toussaint, K. R. Allen, K. A. Smith, and J. B. Tenenbaum.  Differentiable physics and stable modes for tool-use and manipulation planning.  2018\.
  * Lo et al. [2020] S.-Y. Lo, S. Zhang, and P. Stone.  The petlon algorithm to plan efficiently for task-level-optimal navigation.  _Journal of Artificial Intelligence Research_ , 69:471–500, 2020.
  * Garrett et al. [2020] C. R. Garrett, T. Lozano-Pérez, and L. P. Kaelbling.  Pddlstream: 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.
  * Lozano-Pérez and Kaelbling [2014] T. Lozano-Pérez and L. P. Kaelbling.  A constraint-based method for solving sequential manipulation planning problems.  In _2014 IEEE/RSJ International Conference on Intelligent Robots and Systems_ , pages 3684–3691. IEEE, 2014.
  * Hauser and Latombe [2010] 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.
  * Hochreiter and Schmidhuber [1997] S. Hochreiter and J. Schmidhuber.  Long short-term memory.  _Neural computation_ , 9(8):1735–1780, 1997.
  * Vaswani et al. [2017] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, Ł. Kaiser, and I. Polosukhin.  Attention is all you need.  _Advances in neural information processing systems_ , 30, 2017.
  * Coumans and Bai [2016] E. Coumans and Y. Bai.  Pybullet, a python module for physics simulation for games, robotics and machine learning.  2016\.
  * Fox and Long [2003] M. Fox and D. Long.  Pddl2. 1: An extension to pddl for expressing temporal planning domains.  _Journal of artificial intelligence research_ , 20:61–124, 2003.
  * Silver and Chitnis [2020] T. Silver and R. Chitnis.  Pddlgym: Gym environments from pddl problems.  _arXiv preprint arXiv:2002.06432_ , 2020.
  * Kuffner and LaValle [2000] J. 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.
  * Garrett [2018] C. R. Garrett.  Pybullet planning.  Available at https://pypi.org/project/pybullet-planning/, 2018.
  * Dornhege et al. [2009] C. Dornhege, P. Eyerich, T. Keller, S. Trüg, M. Brenner, and B. Nebel.  Semantic attachments for domain-independent planning systems.  In _Nineteenth International Conference on Automated Planning and Scheduling_ , 2009.
  * de Silva et al. [2013] L. de Silva, A. K. Pandey, and R. Alami.  An interface for interleaved symbolic-geometric planning and backtracking.  In _2013 IEEE/RSJ International Conference on Intelligent Robots and Systems_ , pages 232–239. IEEE, 2013.
  * Lifschitz [2019] V. Lifschitz.  _Answer set programming_.  Springer Heidelberg, 2019.
  * Wells et al. [2019] 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):1255–1262, 2019.
  * Driess et al. [2020] 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 on Robotics and Automation (ICRA)_ , pages 9563–9569. IEEE, 2020.
  * Li and Dantam [2021] S. Li and N. T. Dantam.  Learning proofs of motion planning infeasibility.  In _Robotics: Science and Systems_ , 2021.
  * Chitnis et al. [2016] 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.
  * Zhang et al. [2018] 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 3654–3661. IEEE, 2018.

##  Appendix A Introduction

**footnotetext: Equal contribution.

In this appendix, we provide additional materials and evaluations in support
of the main paper. We firstly present the architecture of our models and
training details in Section B. We secondly report a set of additional
evaluation results in Section C, such as the backjumping prediction accuracy
(Section C.1), varying training data size (Section C.2), batch sampling
results (Section C.3), empircal evaluation with additional baselines (Section
C.4), effect of the sample size (Section C.5), effect of the sampling budget
(Section C.6), computation time (Section C.7), and analysis on the overhead of
the model inference (Section C.8). We lastly show the pseudo-code of the
proposed algorithms in Section D.

Unless stated otherwise, all evaluations are conducted in the following
settings. The planning code is executed on one core of Intel(R) Xeon(R) Gold
6342 CPU. Numbers represent the mean $\pm 95\%$ confidence interval computed
by solving $100$ problems.

Table 2: Architectures for imitation learning (IL) and plan feasibility (PF) used for all tasks. Modules | Name | Parameter
---|---|---
GNN | node feature size, | 128
edge feature size, | 128
global feature size, | 128
node network, | [128, 128]
edge network, | [128, 128]
global network, | [128, 128]
IL | # of attention blocks | 3 for packing, 2 for NAMO
attention size | 256
# of attention heads | 8
attention residual network | [256]
RNN hidden size | 256
# of recurrent layers | 3 for packing, 2 for NAMO
object feature size | 256
MLP1 | [128]
MLP2 | [128, 128]
PF | # of attention blocks | 3 for packing, 2 for NAMO
attention size | 256
# of attention heads | 8
attention residual network | [256]
RNN hidden size | 256
# of recurrent layers | 3 for packing, 2 for NAMO
object feature size | 256
MLP1 | [128]
MLP2 | [128, 128]

##  Appendix B Architecture and Training Details

We list the architectures of our imitation learning (IL) and plan feasibility
(PF) models in Table 2 and training hyperparameters in Table 3. Note that both
IL and PF models use the same GNN architecture (Table 2). For each MLP
network, we represent its architecture, e.g., [128, 128] is an MLP of 2 hidden
layers with 128 neurons in each layer. For all activation functions, ReLU is
used.

Table 3: Hyperparameters shared across all methods and tasks. Name | Task
---|---
Packing | NAMO
number of tasks for training | 500 | 250
number of tasks for testing | 100 | 50
optimizer | Adam
learning rate | 1e-4
batch size | 32

##  Appendix C Additional Results

###  C.1 Backjumping prediction accuracy

In Table 4, we show how closely our backjumping prediction $\hat{k}^{\star}$
finds the ground-truth $k^{\star}$ in the packing task, where each method is
trained with data collected from 500 problems. We consider three cases: (1)
$\hat{k}^{\star}=k^{\star}$ (i.e., correct prediction) where the backjump
correctly guides the search to directly modify the culprit, (2)
$\hat{k}^{\star}<k^{\star}$ (we call LT) where the backjump still has a chance
to reach the culprit without backjumping but overshoots (i.e., the culprit
exists in the descendants of $\hat{k}^{\star}$), thus having lower planning
efficiency compared with $\hat{k}^{\star}=k^{\star}$, and (3)
$\hat{k}^{\star}>k^{\star}$ (we call GT) where the backjump undershoots, and
thus, the search cannot reach the culprit without backjumping. For example,
that $\hat{k}^{\star}\leq k^{\star}$ at around 70% of the time implies that
the chance of finding the culprit without backjumping occurs more frequently
than missing the culprit, leading to improved planning efficiency.

Notice that our method involves sampling that approximates a continuous domain
in a discrete way. Because of this, both the following situations are possible
in the LT case: (1) The search may have a new opportunity to find a feasible
solution by sampling a different value for the variable that used to be the
culprit before backjumping but is no longer a culprit. (2) The search may make
a new culprit variable by sampling a wrong value, and thus, further
backtracking or backjumping is required to find a feasible solution.

Table 4: The accuracy of $\hat{k}^{\star}$ prediction in the packing task. Numbers represent the mean $\pm$ 95% confidence interval computed by solving $100$ problems. The number with $*$ represents the best-performing method within the same data size. The bolded numbers are those whose performance is not statistically significantly different from the one with $*$. Metric | IL RNN | IL Attn | PF RNN | PF Attn
---|---|---|---|---
Correct prediction percentage (%) | 39.3 $\pm$ 1.0 | 39.2 $\pm$ 1.5$*$ | 44.2 $\pm$ 0.5 | 43.0 $\pm$ 0.4
LT percentage (%) | 33.0 $\pm$ 2.2 | 30.0 $\pm$ 2.0 | 28.6 $\pm$ 2.2$*$ | 30.3 $\pm$ 2.3
GT percentage (%) | 27.6 $\pm$ 1.2 | 30.1 $\pm$ 2.1 | 27.2 $\pm$ 1.8 | 26.6 $\pm$ 1.9$*$
LT distance | 1.76 $\pm$ 1.10 | 1.76 $\pm$ 1.06 | 0.71 $\pm$ 1.12$*$ | 0.80 $\pm$ 1.20
GT distance | 1.58 $\pm$ 0.91 | 1.59 $\pm$ 0.93 | 1.37 $\pm$ 0.69 | 1.34 $\pm$ 0.65$*$
Prediction backjumping distance | 2.58 $\pm$ 1.66 | 2.48 $\pm$ 1.62$*$ | 2.56 $\pm$ 1.54 | 2.67 $\pm$ 1.62
Ground-truth backjumping distance | 2.44 $\pm$ 1.56

The mean and standard deviation of the LT distance and GT distance (i.e.,
$|\hat{k}^{\star}-k^{\star}|$ for both distances) are shown in the fourth and
fifth rows, and for each method, it can be seen that the prediction
$\hat{k}^{\star}$ has a relatively small deviation from the $k^{\star}$
labels. Finally, as shown in the last two rows, compared to backtracking which
always reevaluates the variable at one level higher, our methods backjump to
higher levels (i.e., $k^{d}-\hat{k}^{\star}$) and avoid evaluating irrelevant
variables. For reference, we show the ground-truth backjumping distance (i.e.,
$k^{d}-k^{\star}$); one can see that the prediction distances of all methods
are close to this ground-truth distance.

###  C.2 Varying training data size

In Table 5, we show the efficiency of our methods when varying the training
data size (i.e., data collected by varying the number of problems). All
methods trained with the reported data sizes outperform backtracking
significantly. With more data, the performance of each method improves, except
for PF trained with more than 2000 problems. PF collects sufficient data even
in a small data regime as it gathers one feasibility likelihood label for each
node visited in the search tree. Thus, further increasing data size does not
significantly affect the PF performance.

Table 5: The number of nodes visited in the search tree in the packing task when varying the data size (measured by the number of problems). Data size | Backtracking | IL RNN | IL Attn | PF RNN | PF Attn
---|---|---|---|---|---
100 | 4414 $\pm$ 879 | 3490 $\pm$ 698 | 3615 $\pm$ 831 | 3487 $\pm$ 704$*$ | 3592 $\pm$ 788
500 | 2464 $\pm$ 464 | 2638 $\pm$ 602 | 2205 $\pm$ 313 | 2062 $\pm$ 297$*$
2000 | 2439 $\pm$ 529 | 2404 $\pm$ 464$*$ | 3084 $\pm$ 672 | 3468 $\pm$ 729
4500 | 1769 $\pm$ 372$*$ | 2151 $\pm$ 507 | 2243 $\pm$ 498 | 2350 $\pm$ 484

###  C.3 Batch sampling results

We conduct additional evaluation of batch sampling on the NAMO task (in Table
6). The results match with our results on the packing task, i.e., although
batch sampling still outperforms backtracking by far, forgetting empirically
exceeds batch sampling in both tasks.

Table 6: The comparison between the forgetting method (F) and the batch sampling (BS) method, measured by the number of nodes visited in the search tree. Task | Backtracking | IL RNN | IL Attn | PF RNN | PF Attn
---|---|---|---|---|---
Packing (F) | 4414 $\pm$ 879 | 2464 $\pm$ 464 | 2638 $\pm$ 602 | 2205 $\pm$ 313 | 2062 $\pm$ 297$*$
Packing (BS) | 13541 $\pm$ 4205 | 4464 $\pm$ 1160 | 7073 $\pm$ 2040 | 4556 $\pm$ 749 | 4311 $\pm$ 690$*$
NAMO (F) | (21 $\pm$ 10) $\times 10^{4}$ | 543 $\pm$ 187 | 425 $\pm$ 153$*$ | 529 $\pm$ 188 | 2615 $\pm$ 710
NAMO (BS) | (44 $\pm$ 11) $\times 10^{4}$ | 16019 $\pm$ 5384 | 9558 $\pm$ 3411 | 4327 $\pm$ 1559$*$ | 84286 $\pm$ 55595

###  C.4 Empirical evaluation with additional baselines

We implement additional baselines, which backjump predetermined steps at dead-
ends, to compare with our methods. We report the number of nodes visited in
the search tree and the wall clock time, measured in seconds, obtained by the
forgetting algorithm for solving each packing problem with $10$ objects. We
choose the packing task because the performance gap between backtracking and
our method in packing is much smaller than that in NAMO, and thus the packing
task yields a more contrasting comparison.

Table 7: The number of nodes visited in the search tree and the wall clock time, measured in seconds, obtained by the forgetting algorithm for solving each packing problem with $10$ objects. # fixed backjumping steps | # visited nodes | Wall clock time
---|---|---
1 (i.e., backtracking) | 4414 ± 879 | 260.6 ± 58.1
2 | 3093 ± 509 | 120.0 ± 21.1
3 | 3323 ± 637 | 140.0 ± 26.9
4 | 2892 ± 557 | 154.0 ± 26.6
5 | 5408 ± 1106 | 391.6 ± 76.1
6 | 8360 ± 1570 | 577.9 ± 109.6
Always backjumping to root | 11212 ± 2002 | 685 ± 120

The results show that when the fixed step is set to $4$, the baseline
algorithm performs the best among all baselines. Its confidence interval even
overlaps with some of our methods, but we observe that our best results (i.e.,
$1889\pm 328$ of IL RNN from Table 9 and $2062\pm 297$ of PF Attn from Table
5) still show the performance statistically significantly better than all
baselines. Nonetheless, the rest of the results in the appendix support our
claim that the performance of our methods can further be improved by varying
training data size and/or sampling budget in training.

###  C.5 Effect of the sample size

We analyze the effect of the sample size (denoted by $N$ in the paper) on the
noisy data and the trained model performance so that users can determine
appropriate $N$ for their applications.

Since our method uses sampling, the planner may mistakenly think it hits a
dead end even if a feasible action (e.g., placement) is available. This
corresponds to a false negative, which contributes to noisy labels and informs
a sufficient number of samples not to miss a feasible action. The ideal sample
size varies depending on a problem domain. Thus, as an example, we show false-
negative ratios in the packing task (Table 8) where the goal is to find a
placement for the $10$-th object when there are $9$ objects in the cabinet.

Table 8: False-negative ratios resulted when using different sample sizes. Sample size | 10 | 30 | 50 | 70 | 90
---|---|---|---|---|---
False-negative ratio | 0.72 | 0.50 | 0.34 | 0.21 | 0.10

###  C.6 Effect of the sampling budget

We conduct additional evaluations on the performance of learning models in the
packing task when varying the number of samples (i.e., $N$ in the paper) used
in training. Specifically, we set the number of samples to be $10$, $30$, and
$50$ in training while that to be $30$ in testing.

Table 9: The ratio of model inference time over the total wall clock time (in $\%$) for solving a single problem. # samples in training / in testing | IL RNN | IL Attn | PF RNN | PF Attn
---|---|---|---|---
10 / 30 | 1889 $\pm$ 328$*$ | 2153 $\pm$ 369 | 3276 $\pm$ 597 | 2932 $\pm$ 450
30 / 30 | 2464 $\pm$ 464 | 2638 $\pm$ 602 | 2205 $\pm$ 313 | 2062 $\pm$ 297$*$
50 / 30 | 5752 $\pm$ 1446 | 6672 $\pm$ 1819 | 4859 $\pm$ 1100 | 4267 $\pm$ 1035$*$

The results show that IL performs the best for $10/30$, PF performs the best
for $30/30$, and both perform the worst for $50/30$. It is expected that at
the extreme (i.e., $N=1$) in training, IL would predict to backjump to near
the root as, most of the time, a feasible placement is not found with $N=1$.
This would behave similarly to a baseline, always backjumping to a root; thus,
its performance is expected to be poor. For a given number of samples in
testing, we can treat the sample size in training as a hyperparameter, and one
can tune it for their applications for better performance.

###  C.7 Computation time

We report the wall clock time for solving each problem, measured in seconds,
in Table 10. The wall clock time is roughly proportional to the number of
nodes visited in the search tree.

Table 10: The wall clock time for solving each problem, measured in seconds. Task | Backtracking | IL RNN | IL Attn | PF RNN | PF Attn
---|---|---|---|---|---
Packing | 202.0 $\pm$ 45.4 | 97.4 $\pm$ 19.3 | 162.1 $\pm$ 32.7 | 94.7 $\pm$ 22.0$*$ | 122.0 $\pm$ 23.8
NAMO | 61754.3 $\pm$ 24608.4 | 66.0 $\pm$ 19.9 | 67.8 $\pm$ 19.9 | 58.7 $\pm$ 18.3$*$ | 11648.3 $\pm$ 12342.7

###  C.8 Analysis on the overhead of the model inference

We report the ratio of model inference time over the total wall clock time (in
%) for solving a single problem.

Table 11: The ratio of model inference time over the total wall clock time (in $\%$) for solving a single problem. Task | IL RNN | IL Attn | PF RNN | PF Attn
---|---|---|---|---
Packing | 0.3 $\pm$ 0.2$*$ | 2.1 $\pm$ 0.6 | 7.7 $\pm$ 2.7 | 1.2 $\pm$ 0.3
NAMO | 12.5 $\pm$ 4.1 | 3.9 $\pm$ 1.4 | 12.4 $\pm$ 3.8 | 2.1 $\pm$ 0.6$*$

The results show the overhead of the querying backjumping model is relatively
cheap, consisting of less than $8\%$ for the packing task. Even though
querying takes $12.5\%$ of the wall clock time for NAMO tasks, it is
worthwhile considering that using backjumping reduces the total wall clock
time from $6\times 10^{4}$s to around $60$s. The results also show that the
difference between the overhead of IL and that of PF is marginal.

We also report the average time to determine the dead end when querying the
model, measured in milliseconds.

Table 12: The average time to determine the dead end when querying the model, measured in milliseconds. Task | IL RNN | IL Attn | PF RNN | PF Attn
---|---|---|---|---
Packing | 267.9 $\pm$ 217.5 | 56.5 $\pm$ 40.2 | 163.1 $\pm$ 112.4 | 16.9 $\pm$ 6.5$*$
NAMO | 823.4 $\pm$ 462.2 | 292.7 $\pm$ 176.3 | 800.8 $\pm$ 433.9 | 138.1 $\pm$ 68.3$*$

Even though the attention method is queried for every previous step while the
RNN is only queried once, it is still much faster than RNN because its time-
series computation can be parallelized on GPUs, while the RNN needs to finish
the time-series computation sequentially.

##  Appendix D Pseudo-code

We present the pseudo-codes for both batch sampling and forgetting algorithms.

Input : Time limit ($T$), number of samples per level ($N$)

1

2$\mathcal{P}\leftarrow\emptyset$ // Initialize the empty plan.

3$\mathcal{V}_{k}\leftarrow$sampleValues $(c_{k},N)$ $\forall
k\in\\{0,...,K-1\\}$ // Sample $N$ values per level $k$.

4$k\leftarrow 0$

5$\mathcal{V}_{k}^{\prime}\leftarrow\mathcal{V}_{k}$

6while  _not isTimeLimitExceeded $(T)$_ do

7 while  _$0\leq k\leq K-1$_ do

8 while  _not isEmpty $(\mathcal{V}_{k}^{\prime})$_ do

9

10 $v\leftarrow$selectValue $(\mathcal{V}_{k}^{\prime})$

11 if  _isConsistent $(v,\mathcal{P})$_ then // Check if $v$ is consistent
with $\mathcal{P}$.

12

13 $\mathcal{P}.$append $(v)$

14 $k\leftarrow k+1$ // Move to the next level.

15 $\mathcal{V}_{k}^{\prime}\leftarrow\mathcal{V}_{k}$

16 break

17 else

18 $\mathcal{V}_{k}^{\prime}\leftarrow$removeElements
$([v],\mathcal{V}_{k}^{\prime})$ // Remove $v$ from
$\mathcal{V}_{k}^{\prime}$.

19 if  _isEmpty $(\mathcal{V}_{k}^{\prime})$_ then // The dead-end is met
($k=k^{d}$).

20 $\hat{k}^{\star}\leftarrow$predictBackjump $(\textnormal{model inputs})$ //
Model inputs are specified in Section 4.

21 $\mathcal{P}\leftarrow$removeElements
$([\hat{k}^{\star},...,k-1],\mathcal{P})$ // Remove the last
$k-\hat{k}^{\star}$ elements from $\mathcal{P}$.

22 $k\leftarrow\hat{k}^{\star}$ // Backjump to level $\hat{k}^{\star}$.

23 break

24 end if

25

26 end if

27

28 end while

29

30 end while

31

32 if  _$k=0$_ then

33 $\mathcal{V}_{k}\leftarrow$sampleValues $(c_{k},N)$ $\forall
k\in\\{0,...,K-1\\}$ // Sample a new batch of $N$ values.

34 $\mathcal{V}_{k}^{\prime}\leftarrow\mathcal{V}_{k}$

35 else

36 return $\mathcal{P}$ // Plan is found.

37 end if

38

39 end while

return no solution

Algorithm 1 Batch sampling algorithm

Input : Time limit ($T$), number of samples per level ($N$)

1

2$\mathcal{P}\leftarrow\emptyset$ // Initialize the empty plan.

3$k\leftarrow 0$

4while  _not isTimeLimitExceeded $(T)$_ do

5 while  _$0\leq k\leq K-1$_ do

6 $\mathcal{V}_{k}\leftarrow$sampleValues $(c_{k},N)$ // Sample $N$ values.

7 while  _not isEmpty $(\mathcal{V}_{k})$_ do

8

9 $v\leftarrow$selectValue $(\mathcal{V}_{k})$

10 if  _isConsistent $(v,\mathcal{P})$_ then // Check if $v$ is consistent
with $\mathcal{P}$.

11

12 $\mathcal{P}.$append $(v)$

13 $k\leftarrow k+1$ // Move to the next level.

14 break

15 else

16 $\mathcal{V}_{k}\leftarrow$removeElements $([v],\mathcal{V}_{k})$ // Remove
$v$ from $\mathcal{V}_{k}$.

17 if  _isEmpty $(\mathcal{V}_{k})$_ then // The dead-end is met ($k=k^{d}$).

18 $\hat{k}^{\star}\leftarrow$predictBackjump $(\textnormal{model inputs})$ //
Model inputs are specified in Section 4.

19 $\mathcal{P}\leftarrow$removeElements
$([\hat{k}^{\star},...,k-1],\mathcal{P})$ // Remove the last
$k-\hat{k}^{\star}$ elements from $\mathcal{P}$.

20 $k\leftarrow\hat{k}^{\star}$ // Backjump to level $\hat{k}^{\star}$.

21 break

22 end if

23

24 end if

25

26 end while

27

28 end while

29

30 if  _$k\neq 0$_ then

31 return $\mathcal{P}$ // Plan is found.

32 end if

33

34 end while

return no solution

Algorithm 2 Forgetting algorithm