Learning Long-Horizon Action Dependencies in Sampling-Based Bilevel Planning
Authors: Bartłomiej Cieślar
Leslie Pack Kaelbling
Tomás Lozano-Pérez
Jorge Mendez-Mendez
Venue: CoRL 2024 (2024)
Keywords: task and motion planning
long-horizon
learning for planning
TL;DR: We learn a heuristic to optimize backtracking in sampling-based approaches to Task and Motion Planning.

Abstract: Autonomous robots will need the ability to make task and motion plans that involve long sequences of actions, e.g. to prepare a meal. One challenge is that the feasibility of actions late in the plan may depend on much earlier actions. This issue is exacerbated if these dependencies exist at a purely geometric level, making them difficult to express for a task planner. Backtracking is a common technique to resolve such geometric dependencies, but its time complexity limits its applicability to short-horizon dependencies. We propose an approach to account for these dependencies by learning a search heuristic for task and motion planning. We evaluate our approach on five quasi-static simulated domains and show a substantial improvement in success rate  over the baselines.

Learning Long-Horizon Action Dependencies in Sampling-Based Bilevel Planning
Bartlomiej Cieslar', Leslie Kaelbling', Tomás Lozano-Pérez', and Jorge Mendez-Mender?
'CSAIL MIT
Stony Brook University
{bcieslar, Srckeslar,,pk,,a0 t1pppkttpppeeee mit. jorge www.emeeeeeeeeetttrrrrroooo edu
Autonomous robots will need the ability to make task and motion plans that involve long sequences of actions, e.g. to prepare meal. One challenge is that the feasibility actions late in the plan may depend on much earlier actions. This issue is exacerbated these dependencies exist at a purely geometric level, making them difficult to express for a task planner. Backtracking is a common technique resolve such geometric dependencies, but its time complexity limits its applicability short-horizon dependencies. We propose approach count for these dependencies by learning search heuristic for task and motion planning. We evaluate our approach five quasi-static simulated domains and show a substantial improvement in success rate over the baselines.
Abstract:
Keywords: task and motion planning, long-horizon, learning for planning
Introduction
Solving long-horizon problems, (e.g., preparing a meal), key toward deploying autonomous robots. Model-based approaches, and in particu- lar task and motion planning (TAMP) [1], offer strong generalization to handle such tasks. A major challenge is that the decisions made early on may be incorrect, but this may only become apparent multiple steps later, such as picking a cucumber in the middle and later needing to slice down the middle. We propose an approach that learns how to use an existing world model to plan efficiently, by predicting the long-horizon consequences of the continuous choices made early during planning.
Figure 1: main from Section 5. The goal is to place blocks in the box, but space constraints require early placements to leave room for later ones.
Packing do-
Bilevel TAMP approaches [2, 3, 4, 5, 6] split robot decision-making into a task planner, which produces a sequence of abstract actions (e.g., pick-> sslice) and motion planner, which computes motions to enact the abstract actions. all of the long-horizon dependencies are encoded at the task-planner level (e.g., picking a cucumber requires the gripper to free, and pick- ing knife causes the gripper to not free), then TAMP can find valid sequence actions with classical planning systems such as Fast Downward [7]. However, long-horizon dependencies that arise from purely geometric constraints are difficult to encode at the task-planner level. One solution for such cases is to find sequence of abstract actions, and then use a combination of sampling (to determine continuous parameters for executing each abstract action) and backtracking (to recursively resample parameters to resolve all dependencies). While backtracking has succeeded at solving a va- riety of robot problems [6, 5, 8), its runtime is exponential in the range of the dependencies between actions and often relies on hand-crafted sampling distributions to handle situations where the set of valid samples has small measure relative to the unconstrained parameter space. As our experiments show, this makes seemingly simple problems intractable for bilevel TAMP approaches.
We propose a mechanism that learns to reject unpromising samples (e.g., an incorrect cucumber grasp) by foreseeing the feasibility of further search. Our approach efficiently collects data of suc- cessful and failed plans, and trains transformer to predict whether state conducive to a solution, given a chosen sequence of abstract actions. We show empirically that our method substantially im-
8th Conference Robot Learning (CoRL. 2024), Munich, Germany.

---

proves the efficiency of backtracking, resulting in a much higher success rate given a time limit. Our contributions include: 1) formalization of long-horizon action dependencies, 2) a transformer architecture for estimating the likelihood of finding parameters for a task plan, 3) an efficient data collection scheme for the classifier, and 4) a modified backtracking method guided by the classifier.
2 Related Work
Many recent works have developed learning mechanisms to improve the capabilitiess of model-based planning. Some methods learn planning models, in the form of state abstractions, abstract actions, controllers, or low-level transition functions [6, part of the planning domain itself, perform planning. Our approach instead learns mechanisms to improve the efficiency of planning given known model. Within this space, existing approaches have learned parameter samplers for backtracking within bilevel TAMP, using either Gaussian [8, 6] or diffusion-based samplers [5]. Prior work has shown how to combine model learning and sampler learning into an integrated learning approach [8, 6]. Other works focus on utilizing existing imperfect domain models for planning by avoiding discrepancies with the real world [13].
10, 11, 12]. The learned models are then used
Related to work, which aims to predict motion planning failures before they occur, the works on culprit detection problem, focusing on explaining failures of motion planning [14, 15, 16, 17, 18]. Within those, the work most closely related to ours uses a learned culprit detector to backtrack the motion planning multiple steps at a time (backjump) [18]. Our approach uses this backjumping procedure as fallback for cases when the feasibility classifier produces false positives, using the confidence from our model to determine the most promising number of backtracking steps. Compared [18], our approach addresses the challenge of efficiently gathering data by jointly learning the backtracking optimization heuristic and generating the data.
Non-model-based approaches to construct long-horizon plans have included sampling trajectories from diffusion models [19] or performing gradient descent [20]. Because these mechanisms lack a model to predict state changes resulting from the robot's actions, they struggle with generalization. Other works explore long-horizon feasibility analysis for task plans, by learning a heuristic to aid task planners [21, 22] using a learned model directly a planner [23]. These methods complementary our work and could be used in combination with it.
3 Problem Formulation
3.1 TAMP Formulation
consists of set of objects O (e.g., the red mug) of types t E T (e.g., mugs). The low-level elements are set of object-oriented continuous states 8 E S = IIoeo S.,. a set of continuous actions a E A, and partial low-level transition function f f x - SU [1} (L denotes execution failure). Objects of a type share a common state set: S, 3 S, (e.g.. pose and size of the red mug). The abstract elements are the set of abstract states À E A (e.g., the mug is red and on the table, the table is on the floor) and the set of lifted abstract actions ã E f2 t1 ... x tm Ω (e.g., (objecc)))) which can be grounded into ground abstract actions w @(0 E tt...., Omg (m E Ω (e.g., pick(red mug)) with specific typed objects. The partial abstract transition function Φ A x Ω + A U {1} specifies how ground abstract actions change the abstract state (e.g., picking the red mug removes it from the table).
A deterministic TAMP domain Z =
The state abstraction function a S relates the continuous and abstract states (e.g., given the red mug's pose, it is the table), while abstract and continuous actions are related by controllers f O x S + SU {1} for each ground abstract action (c.g., pick object controller). Each controller is parameterized by 0 E O., (e.g., a grasp for the object) and follows the constraints of the abstract transition function, so VeES; cu s0) = o' = d(a()), w) = a(s'). The controller executes a sequence of actions whose resulting states are governed by the transition function f. If successful, the controller results in a state s' that matches the expected abstract state a(s').
A TAMP problem (so, G) consists of an initial low-level state su and set of abstract goal states G' (c.g., the red mug is on the third shelf), One way to solve TAMP problem is to first find

---

task plan π = (wi.....,.a w.) of ground abstract actions that induces sequence of abstract states A0.... An such that o<(8)) = Ao V Visien wi) = A, and A, E G, using search algorithms such as Fast Downward [7] with A# [24]. TAMP solvers then refine the task plan into a controller plan p p= (01....,0u, On), which induces states o = (so....,8.) .n) such that V Vigignou (0,, 8i-1) = 8i.
3.2 SeSamE Formulation
1: function (T(s;, i, T)
SeSamE approaches [5, 6] set the controller parameters us- ing sampling distributions the associated with each ground ab-
2:
π : (W1, Wn) if = n then return
3:
4:
for 1... Titer do
stract action w. Samplers then generate controller parameters 5:
0.+1 Moisi (8:)
0 ~ (s) using those distributions, conditioned on the contin- 6:
8441 = Suits (0++1:8)
uous state. Parameters are found via backtracking search on an
7:
if s/+1 = then
internal model of the domain (Algorithm 1 [2]). which recur- 8:
continue
sively extends the current refinement (01,-...:;) 0:). The main 9:
p == BT( 1,411,00 1)
loop (Lines 4-11) repeatedly samples new controller parame- 10: if p 1 then
ters for the current ground abstract action wi+1 (Line 5), checks 11:
return p (0++1)
the sampled parameters enable computing the next state that 12:
return 1
matches the expected abstract state (Lines 6-8), and continues Algorithm I: Classic Backtracking. the search recursively (Lines 3, 9-11). If there exists dependency between ground abstract actions wi and Wi+d, the algorithm will take exp(O(d)) steps to detect if w, is sampled incorrectly. Note that Algorithm is not complete (it can become probabilistically complete if we allow the first action's 's parameters 0 to be resampled ad infinitum), and the base of the exponent depends on Fier-
3.3 Graphical View of Lang- Dependencies
To see why Algorithm struggles with long-range dependencies, consider the (infinite, layered, and directed) graph continuous states reachable from the initial state so after any number i of steps, following a task plan (wi......u We will characterize the states s; that enable reaching states ( 8n) that match the abstract states (A++1:-.. Xx) associated with æ. Our approach in Section 4 learns detect states that don't 't satisfy this condition and skips them during search.
At a high level, we want to determine whether there exists a further task plan refinement from each continuous state s; and task plan prefix length i. This condition can be defined inductively as: the state 8; matches the expected abstract state X,, and some continuous state $;+1 reachable from 8; by following the next action in the plan W,+1, permits refining the task plan. Formally, we consider the graph (V, -+). Vi at each layer i is defined inductively. The base case contains only the initial state: Vo {(s0, }} The (i+ 1)-th layer contains all the states that can be reached by following the (i + 1)-th action, wi+1, from any state in the previous layer V;: V++1 {(s', i 1) EV..))EV.:8B8) swet Swess s) = s') s'}. The nodes in the graph are V & Unsisn V4. The edge relation + denotes that there a parameterization of the (i + 1)-th controller that brings a state s to a next state s': (s, 1) + (s', 1) e 3 Sur+s (0,s) s) s'. The condition for refinability of the task plan from a given state defined inductively. In the base case, 7((s, n)) - a(s) = Ann The inductive step is the cause for the computational difficulty of backtracking in SeSamE:
7(8,, i))
a(s) = A A o((a,)))
1)) ^ (a. i) + (s',
(1)
n((s.))
To illustrate, in Figure 2 we show the structure of the Donut domain from Section 5, where a robot picks a donut, adds toppings using topping machines, and places the donut in a box or on shelf (depending on the goal, see Figure 4 for visualization). The donut must be grasped from the top to place it in the box, and from the side for the shelf; this is the main point of failure. For now, assume that the goal is to place the donut in the box. For this case, y holds for all states in the top row (1A- 6.A) corresponding to top grasps, and does not hold for states in the bottom row (1B-6B). However, Algorithm uses only / to decide whether to continue expanding the current refinement. our successful
example, 33 holds for states in the bottom row (1B-6B), which are not conducive box placement. However, using backtracking to approximate 77 takes exponentially long in i. If the donut is grasped from the side, this causes the search to focus on retrying topping actions for
3

---

Denut Placed the Box
the Top
2A
3A
(4A)
5A
6A
Donut Geaobed
Move
Added
Sprinites Acted
Move
3B
5B
6B
From Side
Donut Placed
the Shaf
Figure 2: The representation of the graph of continuous states of the Donut domain from Section 5. The robot picks up a donut, either from the side or from the top (which is not encoded in the abstract state), moves to and uses different topping machines, and then places the donut either in the box (state 7) or on the shelf (state 8). The donut cannot be placed in the box if it grasped from the side and vice versa. The colored boxes describe the ground abstract actions w available to the robot, with the arrows signifying corresponding continuous actions (achievable by the controller for given ground abstract action). The circles mark the groups of similar continuous states, while the dashed rectangles group them into abstract states.
very long time (reaching Line 8 in Algorithm 1 each time the robot fails to execute a box placement and reach state 7), ignoring that the culprit of failure was the initial grasp.
One way to make this process more efficient would be to evaluate i 1)) before Line 9. In other words, we want to assess for each state 8;+1 and plan suffix wi+1, Wn, whether there exists a valid refinement of the suffix. We could then evaluate this condition before Line 9 and, if it doesn't 't hold, return to Line 5 to resample parameters fs+1- This would avoid the expensive backtracking necessary for Algorithm to discover that the choice of 0,+1 was incorrect. In practice, a method that leverages this should only consider sets of states with non-zero measure of being reached via refinement under the sampling distribution tiw.. since otherwise the planner would not find them.
Learning to Optimize the Backtracking Search
To reduce the backtracking, we propose to learn 1) to determine whether it is possible to further refine the controller plan from the current state s; and use it as a heuristic for search. We do so using a feasibility classifier h that, based on a sequence of prior states a = (So...... 8;) and the task plan ı = (w.....,,, classifies whether a given task plan likely to be refinable from the current state. See Appendix for simplified explanation of this section.
1: function BT-h(a, T, conf h) {50, ... 8;), (WI, Wx)
4.1 Backtracking with Feasibility Classifier
2:
Algorithm uses the classifier to prune controller param- eter samples that would lead to unrefinable states. With
3:
if = n then return ()
4:
for 1... Piter do
each of Titer search attempts (Lines 4-14), the algorithm
5:
0,-1 ~ Vurcn (st)
first samples the next controller parameters 0,41 (Line 5) and tries run the controller produce the next state 8(41 (Lines 6-7). Then, it uses the fcasibility classifier to predict whether further search is likely to succeed from that state (Lines 8-9). The search then continues recur- sively (Lines 3, 10-12). Inspired by [18], if the current 11:
6:
8;-1 C.._ ( (0+1,
7:
if si+1 = then continue
8:
77. con == h( @ (s++1))
9:
if -1 then continue
10:
p BT-h( @ (s--1); 1), n,
min(confmin. conf), h) x then
if if
search step fails, the algorithm backtracks to the previ- 12:
return p 2 (8++1)
ous step with the lowest feasibility classifier confidence 13:
if conf > confmin then
conf (Lines 13-14). This backjumping procedure fur-
14:
return 1
ther reduces backtracking by resampling parameters that are least likely to succeed, under the learned classifier.
15:
return 1
Algorithm 2: Backtracking with Feasi- bility Classifier. The blue parts high- light changes from Figure I.
4.2 Feasibility Classifier Architecture
Per the definition in Equation 1, our classifier requires as input the current state s, and the suffix of the task plan (w..... wn). Notably, both of these inputs vary in length across problems and even across steps within problem- the number of steps in the task plan trivially affects its length, and

---

assuming that the continuous state set St for each type is real-valued vector space R., the number of objects affects the dimensionality of the state. To deal with these variations, we use a transformer architecture (we could alternatively have used a recurrent neural net) that consumes tokens that represent state-action pairs, as illustrated in Figure 3. principle, we could have two sets of tokens: one representing 9; as a set of object states, and another representing the sequence of ground abstract actions in the task plan. However, it is unclear how transformer would simultaneously handle the (ordered) sequence of actions and the (unordered) set of states.
Instead, we let each token be a pair (sy:4y) 1 S S n. Such token must contain information to identify the ab- stract lifted action Wj, the objects that ground the action 01.-...2 "1....;0ma, Oma," and the state 85- Including the entirety of Sj in the input would again require a varying-length rep- resentation. Since we will have multiple such tokens, we can restrict the representation of sy to the state of objects in the action, $j,01...... Aj.0ma," Once the current token is sequenced with the remaining tokens, the transformer will receive information about all objects that parameterize any action in the plan, which can be thought of as the set of objects relevant to the TAMP problem. To identify each object o,, we use a one-hot encoding with a fixed maximum size m'axobj we random- ize the one-hot encodings during training to avoid overfitting to the particular object instances in the training. One remaining challenge is that the number of objects my varies across actions. To pro- duce a fixed-length token representation and introduce the identity of the action, we concatenate the object states and one-hot encodings and pass them through a lifted abstract action-specific featurizer network with a simple feedforward architecture [25] and ReLU activations [26], trained end-to-end with the transformer (details in Appendix C). For each ground abstract action that has already been refined Wissgr we use the state s produced by the controller, while for subsequent actions we use the latest state 8, Because featurizer inputs from such states may be drawn from different distribu- tions than the ones produced from states generated directly by the controller (e.g.. if object positions are encoded relative to the robot), we train separate featurizer networks for ground abstract actions Wj>i that have not been refined.
0,11
taken
takene
Smin(ss))
one-hott +
fränsforwer
fealturizer for wi;
mean pooling
token;
sigmoid
Architecture of the feasibil- ity classifier h. supplied with the se- quence of ground abstract actions Wj- = Wj (o,,1..... .......,,jj,aa. m0, ), S j S ni and re- fined continuous states sp....,8i.
Figure 3:
4.3 Data Gathering
We assume access to a dataset 5 of demonstrations in the form of
1: function DATA-GATHERINGGO
2:
= Constant(2 ()
04.00 = 0 0
task plans, controller plans, and state sequences: (N,P, σ). Demon-
4:
for [ = max (n - 2: 12:(TT,))) (T, 0) E ...0...d do
D' () E D::: 10--1 1121+1
strations can trivially be used as positive training data for the clas-
6:
for random Tap (T,O) E E do
7:
: (So. (Sp......
(Wi (wi....,Wu., W.)
sifier: all parameters in the con- troller plan were sampled correctly,
8:
Prref == (80- T BT-h- Ca-th-Captureeearcee Tree म, 1.0,
so any prefix of the controller plan 10:
Q+ U= TT, o mer @ (8) 8 E SuccessfulTries((T)
(0I...., 0.) and its associated se- 11:
0 U= (T, pret (8)) & E StuckTries(T))
quence of states a = (se. (So...... s;) 12:
h h= PrainneuralClaseee (I. (D.,
should be accepted by our classi- 13:
return h
fier. One (naïve) way obtain neg- Algorithm 3: Generating data for the Feasibility Classifier.
ative data is to run the backtracking search from Algorithm I on the same TAMP problems that we obtained demonstrations for. In the resulting search tree, from each node su...., Sn on the suc- cessful path (except for the last one), there is a single branch that corresponds to a successful plan. All remaining branches failed to be refined, and because we want to find prefixes that are likely to be refined by backtracking with a fixed Fiter these can be treated as unrefinable states. Concretely, we can take any prefix of the successful state sequence o = (So...., st) and follow any application in the search tree of the subsequent controller cursa with parameters 0 a 0.+1 that differ from the successful controller plan. The resulting state & cw. (0, st) can be combined with to produce
5

---

a negative data point for the given task plan я. This process is illustrated in Figure B.1. Note that is imperative that the negative data point shares all but the last state with a successful plan; otherwise, any state outside of the successful plan could have caused the failure. This implies that, to generate negative data points, backtracking must also find a successful motion plan. As explained in Section 3.2, this process takes exponentially long.
To alleviate this cost, we will use the fact that the backtracking search can also be started from any sn). (su..... We then alternate running classifier-
state on the successful sequence of states aided backtracking (Algorithm 2) to generate negative data starting from 81 and training classifier using the obtained data to use for the next round of backtracking for data collection for a decreased value of I. The process is summarized outputs confidence of 1 (Line 2). We then iterate descending state prefix lengths, starting (Lines 4-12). For each task plan prefix length I, select rap viable data points (i.e., task plans of length 2 | + 2; Lines 5-6). For each data point, run backtracking and return the entire search tree traversed by the algorithm (Line 9) and generate the feasibility classifier data (Lines 10-11). Note that we also generate positive data points this step, because the samplers used for backtracking may generate a distribution shift from the initial demonstrations D. We then train the new classifier (Line 12) and decrease the prefix length. In practice, we stop the search from given prefix upon finding the first positive or negative data point.
Algorithm Initially, the feasibility classifier always
from
5 Experiments
Our experimental evaluation aims to address (Q1) whether using backtracking with feasibility classifier can meaningfully improve the speed of plan refinement, (Q2) whether the method general- izes unseen plan lengths, (Q3) how well the method handles reduced initial demonstration dataset D. and (Q4) whether the data collection, the backjumping. and the architecture of the classifier are necessary for the method to work. We run all our experiments with 8 different datasets of task plans and state sequences and test them on 50 test problems for each dataset. The evaluation metric is whether a method was able to find a solution motion plan within a timeout of 120s. See Appendix D complete success rate and timing data across all the domains. See Appendix A for additional details on the runtime, domains, baselines, and ablations.
5.1 Domains
We use 2D (Shelves, Donut, Statue) and 3D (Packing, Trays- in PyBullet) quasi-static domains with collision checking only after each action (Figures and 4). We provide abstract actions w and controllers c, for each domain, and the learners must determine the continuous parameters 0c.. that enable solving each problem. To simulate expert demonstrations to construct the dataset (D, we run SeSamE backtracking, using Fast Downward [7] as the task planner and ground- truth samplers parameterize the controllers. For the 3D domains, perform planning without simulated motion,
STATUE
SHELVES
Figure 4: Evaluation domains. Shelves, the blue boxes are placed on the green shelves and the red cover is placed on top or bottom. In Donut, the robot grasps the donut either from top or side, uses the topping machines (blue), and places it in the box or shelf (green). In Trays, the blocks should be placed in the different trays, which is not encoded at the task-plan level. In Statue, the robot should grasp the statue (horizontally or vertically) and move it to the top right corner; red doors cannot fit the statue grasped vertically, while narrow green doors cannot fit the statue grasped horizontally.

---

and then run bi-directional RRT [27] to validate the generated state sequences. Appendix F describes the steps necessary to run our method on real robot.
Shelves: Contains horizontally stacked shelves (training: 2-5, eval: 5-10) to be filled with boxes and then covered on the bottom or top (each box placement can cause cover placement failure).
Donut: See Section 3.3. We use 1-3 topping machines for training and 3-6 for eval.
Statue: Robot sock-and-place of statue in grid of rooms (side length- :rigghhtrain:: 2-4, eval: 4-8). Depending on the path from start to end, the statue has to be initially correctly picked up.
Packing: A pick-and-plas -lacce of blocks (training: 4-10, eval: 10) by robot arm from table to box. Blocks are arranged in two rows; the back row has to be filled first due to collision.
Trays: A pick-and-place of blocks (training: 4-8, eval: 8) by robot arm from table into set of trays. Each tray should not have more than one block, but this can only be tested at the end.
5.2 Methods Evaluated
We evaluate the following methods.
Backtracking with Feasibility Classifier (Ours): Our classifier-guided backtracking method from Section 4, using the diffusion-based samplers from [5]. There is one sampler for each lifted abstract action, and its input is the concatenation of the states of objects that ground the lifted action. Each sampler feedforward diffusion model trained the data of the corresponding lifted action from the demonstrations in !
Myopic Diffusion Samplers (Bla): The diffusion-based samplers used by our method, introduced in [5], used for general backtracking without feasibility classifier.
Myopic Gaussian Samplers (Blb): An alternative Bla with similar parameterization, using the learned Gaussian- based rejection samplers from [6].
GNN Policy (B2): A goal-conditioned graph neural net (GNN) [28] trained via behavior cloning.
Ablations: We ablate the backjumping (AI) and the data-gathering procedure (A2, A3). See
Appendix A for details.
5.3 Experimental Setups
To address Q1-3, we evaluated the baselines on the 2D domains. For Q7 and Q2, we used a dataset ① 2000 data points, while for Q3 we varied the dataset size between 500 and 2000 data points. For Q3, we used the minimum size for each test domain. For Q2, on 3D domains we varied the maximum number of blocks in the training data across the range described Section 5.1. For Q4, evaluated the ablations on the Pybullet domains, with dataset of 2000 data points. For the remaining experimental data see Appendix D.
5.4 Results and Analysis
The results of Figure 5 demonstrate that our method is on average superior all our base- lines and ablations for all experimental setups. Additionally, it shows 40%+ improvement
Shelves
100%
100%
100%
Ours: Backtracking with
Salved Problems
(Higher (ettter)
Feasibility Classifier
75%
75%
75%
B1a: Myopic Diflusion Samplers
50%
50%
50%
B1b: Myopic Gaussian Samplers
25%
B2: GNN policy
0%
0%
Number of Shelves
Number of Toppings
Grid Size
Figure 5: Generalization results on 2D domains across varying domain sizes. Our approach is the only one that solves nearly all problems in the minimum environment size, and generalizes to increasing sizes. Avg. across 8 seeds, ranges are min. and max, 0% plots are dropped for clarity.

---

Shelves
Donut
Statue
100%
100%
100%
Ours: Becktracking with Feasiblity Classiferr
Solved Probl problems
(Higher is Better)
75%
Ba: Myapic Diffusion Samplers
50%
B1b: Myapic Gaussian Samplers
25%
palicy
1000 1500 2000 Number of Datapoints
500 100015002000 Number Datapoints
500 1000 20001500000
Number Datapoints
Figure 6: Data efficiency results on 2D domains across initial dataset sizes. Our approach solves most problems given the maximum initial dataset size, and outperforms baselines in smaller data regimes. Avg. across 8 seeds, ranges are min. and max, 0% plots are dropped for clarity.
in number of problems solved over the baselines on the non-generalization and non-reduced- data experiments. Thus, Ql can be answered affirmatively. For Q2, our method shows lim- ited generalization for some domains. Its accuracy on the Shelves domain reduces with more shelves. One explanation is that the size of the cover grows with the number shelves, mak- ing this our only environment where an individual object's state is out-of-distribution input networks. In addition, transformers show limited generalization
for the
lengths [29], which may be contributing factor.
100%
Packing
100%
Trays
The results in Figure 6 address Q3, showing superior performance in reduced data regimes. More initial training data improves performance.
Salved Problems
(Higher is Better)
60%
40%
40%
20%
20%
Figure 7 contains results answer Q4. Com- pared to our results, the data collection abla- tion A2 and A3 shows on average 25%-50% re- duced performance on the Trays domain, which demonstrates that our bootstrapping approach for data collection is critical the method's overall success. Simmilarly, ablating the back- jumping (Al) reduces the method's performance by on average 50% reduced solution success rate on the Packing domain, which highlights the sig- nificance of that procedure in our method.
0%
0%
Ours: Backtracking
A2: Backtracking Feseibillty Classiferr negalive training data from the longeet failed trajectory
Feasibllit Classifier
A1: Backtracking with Feasiblity Classifior Backjumping
A3: Backtracking with Feasiblity
Classiferr negallive training dala prefixes
trajectory
Figure 7: Ablations the Packing and Trays domains. Assuming last action to be the wrong one (A2) reduces success rate. Backjumping (A1) and assuming all actions to be wrong in case of planning failure (A3) maintains success Avg. across 8 seeds, error bars are stddev., ranges min. and max.
6 Conclusion and Limitations
We proposed solution to learn to account for long-horizon action dependencies in sampling-based based bilevel planning. We showed experimentally that our approach substantially outperforms existing methods in problems requiring long-horizon reasoning. One limitation of our approach, common to most learning methods based on neural nets, is that using a small feasibility classifier network, or a small initial dataset of demonstrations for training, leads to degraded performance. The com- mon solutions to use bigger networks or collect larger datasets can address this limitation. One challenge specific our method that data labeled as positive negative by our own data col- lection mechanism. If our sampling distributions & are low low-quality (which can happen in the case of learned distributions similar reasons of scale) or we attempt too few samples Titer at each step of backtracking, this can lead to noisy labels that complicate the training of the classifier, Increasing Fiter can reduce this labeling noise. Our choice to use transformer architectures carries the draw- back that generalization to longer inputs (in this case, longer plans) is limited (see [29]). Applying regularization techniques during training can mitigate this challenge. Other directions to improve our approach include limiting the distance of action dependencies or collecting data only every k-th prefix length to accelerate data collection, or using classifier-based guidance [30] to more efficiently sample from diffusion models.

---

Acknowledgments
We thank Aditya Agarwal for initial discussions on the feasibility classifier architecture. The re- search of J. Mendez-Mendez funded by an MIT-IBM Distinguished Postdoctoral Fellowship. We gratefully acknowledge support from NSF grant 2214177; from AFOSR grant FA9550-22-1-0244 from ONR MURI grant N00014-22-1-27400 from ARO grant W91 INF-233-- -------33,0; from the MIT- IBM Watson AI Lab; from the MIT Quest for Intelligence; and from the Boston Dynamics Artificial Intelligence Institute. The experimental data was gathered using the MIT Supercloud [31].
References
[1] C. R. Garrett, Chitnis, R. Holladay, B. Kim, Silver, L. P. Kaelbling, and T. Lozano- Pérez. Integrated Task and Motion Planning, Oct. 2020. URL http://arxiv.nn org/ /bs////////// 2010.01083. arXiv:2010.01083 [es].
[2] Srivastava, E. Fang, L. Riano, R. Chitnis, J. Russell, and P. Abbeel. Combined task and motion planning through extensible planner-independent interface layer. 2014 IEEE International Conference on Robotics and Automation (ICRA), pages 639-646 2014. URL https://apt semanticscholas Drmmaa/iisccolla...oooorrosDooas 15991003.
[3] N. T. Dantam, Z. K. Kingston, S. Chaudhuri, and L. E. Kavraki. Incremental task and motion planning: A constraint-based approach. In Robotics: Science and Systems (RSS), volume 12, page 00052, 2016.
[4] T. Silver, R. Chitnis, J. Tenenbaum, L. P. Kaelbling, and T. Lozano-Pérez. Learning sym- bolic operators for task and motion planning. In 2021 IEEE/RSJ International Conference Intelligent Robots and Systems (IROS), pages 3182-3189, 2021.
[5] J. Mendez-Mendez, L. P. Kaelbling, and T. Lozano-Pérez. Embodied lifelong learning for task and motion planning. In Proceedings of the 7th Conference on Robot Learning (CoRL-23), 2023. URL https://proceediing mlr. wwwpppee2s///////p mendez2aa. pdf.
( httee//222mmmedezz--ee mendez--endezeae
[6] R. Chitnis, T. Silver, J. B. Tenenbaum, T. Lozano-Perez, and L. P. Kaelbling. Learn- ing SymbolSymbolii Relational Transition Models for Bilevel Planning, June 2022. URL http://arxiv www.ooogg//bb//..ee.oeoee 14074. arXiv:2105.14074 [es].
[7] M. Helmert. The fast downward planning system. Journal of Artificial Intelligence Research, 26:191-246, July 2006. ISSN 1076-9757. doi:10.1613/jirr11700 1705. URL http: //dx doi.
org/10. 1613/jairrarr. 1705.
[8] T. Silver, A. Athalye, J. B. Tenenbaum, T. Lozano-Pérez, and L. P. Kaclbling. Learning neuro- symbolic skills for bilevel plamning. 6th Annual Conference on Robot Learning, 2022. URL https://openreviess ee
[9] T. Silver, R. Chitnis, Kumar, W. McClinton, T. Lozano-Pérez, Kaelbling, and B. Tenen- baum. Predicate invention for bilevel planning. Proceedings of the AAAI Conference on Arti- ficial Intelligence, 37:121 17:12120-122 20-12219, 2023.
[10] N. Shah, Nagpal, Verma, and S. Srivastava. From reals to logic and back: Inventing sym- bolic vocabularies, actions, and models for planning from raw data. arXiv preprint 2402.11871, 2024.
[11] G. Konidaris, P. Kaelbling, and T. Lozano-Perez. From skills to symbols: Learning symbolic representations for abstract high-level planning. Journal of Artificial Intelligence Research, 61: 215-289 2018.
[12] B. Ames, Thackston, and G. Konidaris. Learning symbolic representations for planning with parameterized skills. In 2018 IEEE/RSJ International Conference Intelligent Robots and Systems (IROS), pages 533,,33, 2018. doi: 10.111990/// 85943359331.

---

[13] E. Ratner, C. J. Tomlin, and M. Likhachev. Operating with inaccurate models by integrating control-level discrepancy information into planning. In 2023 IEEE International Conference on Robotics and Automation (ICRA), pages 7823-7829, 2023. doi:10.1 111.1111///////88999 .2023. 10161389.
[14] F. Lagriffoul and B. Andres. Combining task and motion planning: A culprit detection problem. The International Journal of Robotics Research, 35(8):800-927, 2016. doi:
0L.11770278366915569999
[15] A. M. Wells, N. T. Dantam, A. Shrivastava, and L. Kavraki. Learning feasibility for task and motion planning tabletop environments. IEEE Robotics and Automation Letters, 4(2): 1255-1262, 2019. doi:10. 1T..///........./..1
[16] C. V. Braun, J. Ortiz-Haro, M. Toussaint, and O. S. Oguz. Rhh-Igp: Receding horizon and heuristics-based logic-geometrie programming for task and motion planning. In 2022 IEEE/RSJ International Conference Intelligent Robots and Systems (IROS), pages 13761- 13768, 2022. 100010090/000441722222299999
[17] M. Khodeir, A. Sonwane, Hari, and Shkurti. Policy-guided lazy search with feedback for task and motion planning. In 2023 IEEE International Conference on Robotics and Automation (ICRA), pages 3743-377 3749, 2023. Noi:10.110//ICR.. 20223.203999929 10161 109.
[18] Y. Sung, Z. Wang, and P. Stone. Learning correct mistakes: Backjumping in long-horizon task and motion planning. In 6th Annual Conference on Robot Learning, 2022. URL https: // //penreview. //peetevieen.ee//forrm/ htt.fformmiddrrIwfff/.
[19] U. A. Mishra, S. Xue, Y. Chen, and D. Xu. Generative skill chaining: Long-horizon skill planning with diffusion models. In 7th Annual Conference on Robot Learning, 2023, URL
https://openreviex net. formm? HE
[20] C. Agia, T. Migimatsu, J.
Wu, and J. Bohg. Stap: Sequencing task task-agnostic policies. In 2023 IEEE International Conference on Robolics and Automation (ICRA), pages 7951-7958, 2023. doi: 11111...1//CRAAA4 1.2.A448899..22..111 202.
[21] Z. Yang, C. R. Garrett, T. Lozano-Perez, L. Kaelbling, and D. Fox. Sequence-Based Plan Feasibility Prediction for Efficient Task and Motion Planning. In Proceedings of Robotics: Science and Systems, Daegu, Republic of Korea, July 2023. 101.0115500//SS.222....
[22] K. Lin, C. Agia, T. Migimatsu, M. Pavone, and J. Bohg. Text2motion: from natural language instructions feasible plans. Autonomous Robots, Nov 2023. ISSN 1573-7527. doi: 1007/ s10514-023-10111 10131-77 URL https://doi http::://doooorg///// (0og/10.100 1007 1007 023 10131-7.
[23] D. Driess, J.-S. Ha, and M. Toussaint. Learning to solve sequential physical reasoning problems from scene image. The International Journal of Robotics Research, 40(12-14): 1435-1466, 2021. 00110011777/077334211155666 02783649211056967
URL
[24] E. Hart, N. Nilsson, and Raphael. formal basis for the heuristic determination of minimum cost paths. IEEE transactions Systems Science and Cybernetics, 4(2):100-107, 1968.
[25] Rosenblaut The perceptron: A probabilistic model for information storage and organization in the brain. Psychological Review, 65(6):386-40S, 1958.
[26] V. Nair and G. E. Hinton. Rectified linear units improve restricted boltzmann machines. In Proceedings of the 27th international conference machine learning (ICML-10, pages 807- 814, 2010.
[27] A. H. Qureshi and Y. Ayaz. Intelligent bidirectional expidiy- random trees for optimal motion planning in complex cluttered environments. Robotics and Autonomous Systems, 68:
10

---

1-11, 2015. ISSN 0921-8890. ocittp/s/oodug///////00////o/000 URL https: www.sscennedirect.. http:///wwaacca.....c.o////////a
[28] T. Silver, R. Chitnis, A. Curtis, J. B. Tenenbaum, T. Lozano-Perez, and P. Kaelbling. Plan- ning with learned object importance in large problem instances using graph neural networks. In AAAI Conference on Artificial Intelligence, 2020. URL attps://apls htt.//ppp..emmtticccchhh...aaa
org/ org/CorpusID: 221 221655845.
[29] Y. Zhou, U. Alon, X. Chen, X. Wang, R. Agarwal, and D. Zhou. Transformers can achieve length gencralization but not robustly, 2024.
[30] Dhariwal and A. Q. Nichol. Diffusion models beat GANs on image synthesis. In A. Beygelz- imer, Y. Dauphin, Liang, and J. W. Vaughan, editors, Advances Neural Information Pro- cessing Systems, 2021. URL attps://openrevier: net/ferumm AAAWuCaaa..
[31] A. Reuther, J. Kepner, C. Byun, S. Samsi, W. Arcand, D. Bestor, B. Bergeron, V. Gadepally, M. Houle, M. Hubbell, M. Jones, A. Klein, L.. Milechin, Mullen, A. Prout, A. Rosa, C. Yee, and P. Michaleas. Interactive supercomputing on 40,000 cores for machine learning and data analysis. In 2018 IEEE High Performance extreme Computing Conference (HPEC), pages 1-6. IEEE, 2018.
[32] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, E. Kaiser, and I. Polo- sukhin. Attention is all you need. In Advances in neural information processing systems, pages 5998 6008, 2017.
[33] D. E. Rumelhart, G. E. Hinton, and R. J. Williams. Learning representations by back- propagating errors. Nature, 323(6088) 1986.
[34] Garrido-Jurado, R. MuñiozSalinas,, F. Madrid-Cuevas and M. Marín-Jiménez. Automatic generation and detection of highly reliable fiducial markers under occlusion. Pattern Recogni- fion, 47(6):228--2292, 2014. ISSN 0031-3203.
[35] K. Arun, T. S. Huang, and S. D. Blostein. Least-squares fitting of two 3-d point sets. IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI-9(5)6698-70) 1987. doi: 10. 1091999/PMMLMMM 197747767965.

---

Appendices to
"Learning Long-Horizon Action Dependencies in Sampling-Base -Baed Bilevel Planning"
Bartlomiej Cieslar!, Leslie Kaelbling', Tomás Lozano-Pérez', and Jorge Mendez-Mender?
'CSAIL MIT
Stony Brook University
Socieslar,1pk,, tlp .ii. edu j mewddeeeeeeeeee2stooorrooooo edu
A
Additional Experimental Details
For the purpose of reproducibility, this appendix contains additional details of the runtime, domains, baselines, and ablations for the experiments in Section 5 in the main paper.
A.1 Runtime
All experiments were Ubuntu 22.04.3 using 20 cores of Intel Xeon Gold 6248 and a 32GB Nvidia Volta V100. We use 30 threads to collect the data for our method and its ablations in parallel. For the 3D domains, we use PyBullet for collision checking and rendering.
A.2 Detailed Domain Descriptions
This section provides additional details of the domains.
Shelves Domain: Contains horizontally stacked shelves to be filled with boxes and then covered on the bottom or top (as specified by the goal). The boxes are always taller than the shelves, requiring long-horizon reasoning of how to avoid them interfering with the cover. Each box placement introduces possible failure. The cover must be placed after the boxes are the shelves. The lifted abstract actions are "Move Box", "Move Cover Top" and "Move Cover to Bottom". All lifted abstract actions share single controller, whose parameters are some (xr, v) absolute position of a point on the moved and on the target object, and the (x, y) offset with respect to the target destination to place the moved object on. The positions of the objects are in absolute coordinates, and the objects cannot be rotated.
Donut Domain: A robot picks a donut, adds toppings using topping machines, and places the donut in box or on shelf (depending on the goal). The donut must be grasped from the top to place in the box, and from the side for the shelf; this is the main point of failure. The lifted abstract actions are "Move Robot", "Grasp Donut" "Place Donut in Box", "Place Donut Shelf" and "Add Topping to Donut". The movement, grasp position and placement position in the abstract action controllers are parameterized by the (z. y) displacement. All other controller parameters are determined using binary decisions based on threshold on a real value (e.g., either a top or side grasp, or which topping to add). The topping machines cannot be used if they're too away from the robot; a similar restriction applies to the grasping and placement actions. The positions of the objects are relative the robot, and the objects cannot be rotated. There are 10 varieties of possible toppings in the goals.
Statue Domain: A robot traverses grid of rooms connected by doors to pick up statue from the bottom-left comner and place it in the top-right corner. The statue can be carried horizontally or vertically. All possible paths to goal go through one door that can only fit the statue carried one way. The main point of failure is the statue grasp, but failures are only apparent upon reasoning about the entire task plan, and not just the goal. The lifted abstract actions are "Go through Door", "Go through Door with Statue". "Grab Statue" and "Place Statue". The movement controller pa- rameterization specifies the offset (xr, y) that the robot moves by, and the grab controller specifies thresholded value for the orientation of the statue (horizontal, vertical) the 3D axis from the front of the robot (not perpendicular to the world). The positions of objects are in absolute coordi- nates, and (other than the horizontal/vertical rotations of the statue) the objects cannot be rotated.
12

---

In training problems, the positions of objects are randomly offset to keep them in distribution for the larger grids of rooms in test problems.
Packing Domain: A Franka Panda arm grabs blocks from the table and places them in a box, open from the front and facing the robot. The blocks only fit if placed in two rows, so the first blocks must be placed in the back to make room for the subsequent ones in the front. The blocks initially lie down scattered across the table. The only lifted abstract action is "Place Block". The controller is parameterized by where along the block grasp it and where to place the block (upright) relative to the center of the box. The positions of objects in absolute coordinates, and the rotations are in quaternions.
Trays Domain: A Franka Panda arm grabs blocks from the table and places them in one of 9 trays. The goal is to place only one block in each tray, but the relationship between blocks and which trays they are placed into is not encoded at the task-plan level. The blocks are initially upright scattered across the table. The lifted abstract actions are "Move Block" and a dummy "Check Trays" action that confirms (at the end of the plan) if the blocks are in the target configuration- this necessary for the task planner to find goal-reaching plan, but prevents the movement actions from knowing the precise target placements. The controller is parameterized by where to place the block (upright) relative to the center of the tray and one-hot encoding of the tray. The positions of objects are in absolute coordinates, and the rotations are in quaternions.
A.3 Backjumping and Data Collection Ablations
This section describes the ablations used to validate the need for each element of our approach.
No backjumping (Al): To study the impact of backjumping on our method, this ablation disables backjumping, instead always backtracking only one step. The ablation uses exactly the same trained networks our full approach.
Negative training data from the longest failed trajectory (A2): To assess the importance of data collection scheme, we train method by generating positive training data from the prefixes of controller plans from the demonstrations dataset D and negative training data from the longest failed refinements of attempts at running backtracking on the problems from D.
Negative training data from all prefixes of a failed trajectory (A3): This ablation is similar to A2, but instead generates negative training data from all prefixes of the longest failed refinement.
A.4 Training the Baselines
Table presents the hyperparameters used when evaluating the baselines and the diffusion-based samplers used in our method (classifier hyperparameters are included in Appendix C).
The hyperparameters of each method were tuned hased on its prediction accuracy on the Shelves do- main, using a held-out validation dataset of 20% of the data points. We picked the hyperparameters with the lowest validation loss for each method. The SeSamE- methods (including our own) set Finr 20 for all domains. Our data collection method from Section 4.3 collects ráp = 4000 data points per the iteration of the data collection loop. To ensure a fair comparison, the Gaussian and diffusion samplers were trained for comparable amount of time, and the GNN baseline was trained for similar amount of time as our method (including the data collection procedure).
B Data Gathering Illustrative Example
Figure B.1 illustrates an example search tree that the backtracking algorithm could produce during the data collection described in Section 4.3.
C Network Training Setup
In this appendix, for the purposes of reimplementation and reproducibility, we describe the training setup for our transformer-based classifier. We use an encoder-only transformer. We select the hy- perparameters for the classifier, summarized in Table 2, based on the accuracy on the final iteration of training in the data collection algorithm from Section 4.3 on the Shelves environment- runs that
13

---

Table 1: Hyperparameters for the baselines and samplers for our method
Method
Hyperparameter
Value
number of training iterations
10000
number of diffusion timesteps
100
Diffusion sampler
hidden layer sizes learning rate regressor hidden sizes classifier hidden sizes number of training terations learning rate number of epochs
x 512
1c 4
1024 x 2
128 2
Gaussian sampler
20000
1e-3
1600
number of message passings
3 512
GNN
hidden sizes (encoders, models, and decoders)
learning rate
le
i i= 0
grasp
move
2 2
glaze
move
place in box
Figure B.1: Example data collection search graph. This is the subgraph of the refinability graph described in Section 3.3 found via backtracking search on the Donut domain, using räp 4. Rows separated by dashed lines represent layers of the graph (as labeled by i), filled nodes represent continuous states 8; found during backtracking search, and empty nodes labeled by indicate that the sampled parameters resulted in controller failure. The path highlighted in yellow corresponds a successful execution, so all nodes and corresponding prefixes of the plan are positive samples for h. The nodes boxed by red dotted lines exemplify the negative samples that lead refinement failure, as described in Section 4.3.
caused the data collection to take prohibitively long (e.g., because accuracy in early iterations was too low) were terminated early and discarded.
We optimize standard binary cross-entropy loss with the Adam optimizer, over randomly drawn mini-batches. In addition the output of the featurizer network, for each token concatenate one-hot encoding of which featurizer network produced it (identifying the lifted abstract action and whether the state was produced by its controller, as explained in Section 4.1), and a binary flag to indicate whether the corresponding ground abstract action was the latest one to be refined (i.e.. the action wy such that j = i). These additional inputs aid the network with locating the key information in the sequence of tokens. As standard practice the literature, we also concatenate the sinusoidal positional encodingto each token. As described in [29], we offset the positions of the tokens by random value improve out-of-distribution generalization with respect to the length of the task plan. Before passing the token to the transformer, pass through linear map to ensure
14

---

Table Feasibility classifier training hyperparameters Hyperparameter
Value
Model learning rate (without the transformer)
le
Transformer learning rate
le 5
Number training iterations
5000
Batch size
4000
Featurizer network hidden layer sizes
x 256
Feautrizer network output size
256
Sinusoidal embedding dimensionality
128
Sinusoidal embedding base
130
Transformer token width
128
Transformer feedforward block hidden size
512
Number of transformer heads Number of transformer residual blocks
8
matching dimensionality. Our transformer then uses multi Meali-head attention: the token is split into number transformer heads, each processing chunk of the mapped token.
D Additional Experimental Results
In this appendix, we present the experimental results included in Section 5.4. The timings only consider the tasks for which each baseline succeeded, which is why the 2D domains our method sometimes exhibits higher runtime than the baselines. The timings for the GNN bascline (B2) were not included because the policy is designed to compute single solution; if the solution works, it succeeds, and otherwise it immediately fails. In consequence, when it does succeed, it is much faster (~ x000x) than our approach.
E Simplified Explanation of Our Contribution
SeSamE approaches [5, 6] methods for task and motion planning work by first creating a task plan of high-level operators (such as grab cup or place the cup on the table) and finding controller param- eters for the motion controllers associated with those operators (the motion plan). The task plans are commonly found using common search algorithms such Fast Downward [7] with A [24]. The controller parameters found by their recursive sampling step-by-step for each of the motion controllers associated with the operators in the task plan using the feasibility classifier. Our con- tribution centers around preemptively rejecting the controller parameters that are likely to result in downstream search failures (e.g., when an incorrectly grasped Donut cannot be placed into box due to collision of the arm with the box). See Section 4.1 for the details of the recursive controller parameter discovery process.
We condition the feasibility classifier states generated after running each controller in sequence. The states then passed through featurizer networks, which are simple feedforward architec- ture [25] with ReLU activation [26], to form a sequence of tokens. These tokens are then concate- nated with sinusoidal positional embeddings and passed through a transformer architecture [32]. The tokens produced by a transformer are then averaged together and passed through a linear layer with a sigmoid activation [33] to produce the final confidence of whether further controller param- eter discovery is possible. The featurizer networks, transformer and final linear layer are trained jointly in supervised manner. See Section 4.1 for the rationale behind the specific choice of the feasibility classifier architecture.
To gather the data for training the feasibility classifier we use the fact that, during the controller pa- rameter search, each controller parameter for which the previous steps of recursive search succeed but for which subsequent search fails can be used as negative training datapoints. Likewise, each controller parameter for which the subsequent search succeeds can be used as positive training datapoint. We also notice that, given successful motion plan, the controller parameter search can be restarted at any point in that plan to produce the aforementioned datapoints. The challenge to
15

---

Shelves
Denut
Statue
Ours: Backtracking with Feesibilit Cleesifier
(Lower is Better)
Solve Time
10s
10s
10s
81a: Myopic Ditusion Samplers
B1b: Myopic Gaussian Samplers
GNN policy
05
05
10
Number of Shelves
Number of Toppings
Grid Size
Figure D.2: Solve times for the generalization experiments 2D domains across varying domain sizes. Other than the Statue domain, our approach is faster than the sampler-based baselines (B l and B1b) across all environment sizes. We omit the GNN baseline (B2) because it does not do planning and therefore is trivially faster than planning approaches. Averaged across 8 seeds, ranges represent mininum and maximum values. Note that 0% plots are dropped for clarity.
Shelves
Donut
Statue
100s
1005
1005
Ours: Backtracking with Feasiblltt Classifier
(Lower is Better)
Solve Time
10s
105
105
B1a Myapic Diflusian Samplers
15
B1b: Myapic Gaussian Samplers
palicy
0s
0s
0s
500
1000
1500
2000
500 1000 1500 2000 Number of Datapoints
500 1000 1500 2000
Number of Datapoints
Number of Datapoints
Figure D.3: Solve times for the data efficiency experiments on 2D domains across initial dataset sizes. Our approach is on average faster than the sampler-based baselines (Bla and B1b) across all dataset sizes. We omit the GNN baseline (B2) because it does not do planning and therefore is trivially faster than planning approaches. Averaged across 8 seeds, ranges represent minimum and maximum values. Note that 0% plots are dropped for clarity.
Packing
Trays
100s
100s
Backtracking
(Lower Better)
Feasibility Classifeer
Solve Time
10s
10s
A1: Backrrackig with Fesesbiliy
Cleasifeer Bacijumping
Az: Backtracking ig with Feasibily bityy Classifier negalive training data from the longest failed trajectory
1s
1s
A3: Backtracking Feasibillyy
Claselfer negallie twining dataa from prefiees of falled trajectory
0s
0s
Figure D.4: Solve times for generalization (left) and data efficiency (right) results on 3D domains across varying domain sizes. Our approach consistently the ablation A3 is comparably fast on the Packing domain, but over 3x slower on the Trays domain. Avg. across 8 seeds, ranges are min, and max, 0% plots are dropped for clarity.
3x faster than ablations A and A2;
16

---

Packing
Trays
100%
100%
Ours: Backtracking with Feasibility Classifier
Solved Problems (Higher is Better)
80%
80%
60%
60%
B1a: Myopic Diffusion Samplers
40%
B1b: Myopic Gaussian Samplers
20%
20%
0%
0%
B2: GNN policy
10
Max Training Blocks Packing
Max Training Blocks
Trays
100%
100%
Ours: Backtracking with
Solved Problems (Higher is Better)
80%
80%
Feasibility Classifier
60%
60%
B1a: Myopic Diffusion Samplers
40%
B1b: Myopic Gaussian Samplers
20%
20%
0%
0%
B2: GNN policy
1000 1500 2000
500
1000
1500 2000
Number of Datapoints
Number Datapoints
Figure D.5: Results on generalization (top) and data efficiency (bottom) of our method and baselines on 3D domains across varying maximum number of blocks during training and initial dataset sizes. Our approach shows higher success rate on almost all experimental setups. Avg. across 8 seeds, ranges are min. and max, 0% plots are dropped for clarity.
Packing
Trays
100s
100s
Ours: Backtracking with Feasibility Classifier
Solve Time (Lower is Better)
10s
10s
B1a: Myapic Diffusion Samplers
1s
1s
B1b: Myopic Gaussian Samplers
0s
0s
B2: GNN policy
10
Max Training Blocks Packing
Max Training Blocks
Trays
100s
100s
Ours: Backtracking with Feasibility Classifier
(Lower is Better)
Solve Time
10s
10s
B1a: Myopic Diffusion Samplers
1s
1s
B1b: Myopic Gaussian Samplers
Os
0s
B2: GNN policy
500
1000 1500 2000
500
1000 1500 2000
Number of Datapoints
Number of Datapoints
Figure D.6: Solve times for generalization (top) and data efficiency (bottom) results on 3D domains varying domain sizes. Our approach is consistently over 5x faster than baselines Bla and Blb. Avg. across 8 seeds, ranges are min. and max, 0% plots are dropped for clarity.
17

---

overcome is that, without the use of an already functioning feasibility classifier, this datapoint col- lection procedure prohibitively long. Thus, our data collection algorithm, given a set of already found motion plans, we step-by-step restart the controller parameter search from progressively ear- lier points the motion plans, train our feasibility classifier after each such step, and use it to speed up the search for subsequent data collection steps. See Appendix B for an illustrated example of this process and Section 4.3 for more detailed description of the algorithm.
F Discussion of running the method on a real world setup
While our experiments in Section in the main paper focused on simulated domains, our approach could feasibly be used on real robot under certain constraints. summary, other than a faithful simulator of the real world scene, we require a source of data train the feasibility classifier, which need not be realistic, just representative of what plans will be tion. Specifically, the following components would be crucial to add to our system before running on real hardware:
the simulator during evalua-
A simulator synchronized with the real robot. The challenge here is making sure the po- sitions of objects are well represented in the simulator (since the robot joint positions can usually be accurately measures). Assuming the objects used in the domain are known, or can be extracted from somewhere, locating them can be achieved using e.g., Aruco tags [34], using ICP [35].
Data of successful trajectories, which can be collected by running the backtracking search without the heuristic in the simulator (baseline Bla from Section 5.2) in parallelized manner. While this method does require some source of controller parameter samplers, which in our case are learned through Imitation Learning, they require much less trajectory data to train, as shown in [5]. Alternatively, the data can be collected by having a human click through a trajectory for the robot to follow.
Real-world abstract action controllers can be achieved by utilizing the synchronization of the simulator with the real world and using the controllers used for planning in the simu- lated environment. Importantly, the plan found during motion planning with the simulator would have to executed an open-loop manner, i.e. under the assumption of no catas- trophic execution failure (such as the robot dropping an object). Should we want to handle case of such a failure, replanning procedure would have be introduced into the task planner and we would have to collect data for such failure recovery during the successful plan search.
18


Reviews:
[{"review_id": "NyONaay2up", "reviewer": "Reviewer_KAhV", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": 3, "strengths_and_weaknesses": "", "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": "Bilevel planning approaches for long-horizon tasks that use sampling and backtracking to account for continuous-level failures typically require handcrafted sampling distributions for valid continuous samples. This is intractable for seemingly simple problems. The authors propose using data of successful and failed plans to learn a model (transformer) that predicts such a valid set to improve the efficiency of backtracking in these methods. The paper contains promising results in simulation.", "summary_of_recommendation": "The paper addresses an important and challenging problem relevant to hierarchical model-based planning methods, motivates it rigorously, and grounds it in popular TAMP approaches. However, due to no hardware experiments, my recommendation is \"weak accept\". Depending on responses to rebuttal questions, I could lean towards a \"strong accept\" or a \"weak reject\".", "technical_quality": 4, "clarity_of_presentation": 4, "potential_impact": 3, "robotics_focus": 3, "quality_of_limitations": 3, "questions_for_rebuttal": "1. Can you please share in detail your thoughts on moving towards on-robot deployment of your approach? The response to this question does not need to be *long*; just thorough. For that, it might help to make sure that your response:\n    - is grounded within the specific context of your paper as far as possible (and does not talk about addressing problems for extremely *general* approaches)\n   - includes proposing a few concrete next steps (be it “engineering” or “research”)\n   - includes thoughts about the data collection\n   - includes references to support any claims where applicable\n2. The problem of informing the “high level” about uncertainty in the “low level” is a classic and interesting problem with hierarchical model-based approaches. Naturally, researchers outside of the TAMP community have also looked into versions of this problem but use different words such as “control level” and “planning level”. For instance, consider the paper [“Operating with Inaccurate Models by Integrating Control-Level Discrepancy Information into Planning” by Ratner et al.](https://ieeexplore.ieee.org/document/10161389) Please briefly talk about how this work relates to yours and what the trade-offs are. Please also include a shorter version of your response to this question in the Related Work section.\n3. The work heavily relies on data collection. Can you please briefly comment on the implications on generalization of your approach to unseen domains?\n4. Further, the paper mentioned in question (2.) above uses only data observed during execution. Please also briefly comment on the trade-offs due to this distinction in their approach and yours.\n5. How does your work relate to / overlap with work on learning symbols, such as initiation set classifiers? For an example of a paper in this area, see [\"Learning Symbolic Representations for Planning with Parameterized Skills\" by Ames at al.](https://ieeexplore.ieee.org/abstract/document/8594313)", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Lp9ijKytIH", "reviewer": "Reviewer_dUuw", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": 4, "strengths_and_weaknesses": "", "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": "This paper aims to develop a learning approach for improving the efficiency of solving sampling-based task and motion planning (TAMP) problems. The motivation of this proposed approach is that backtracking search is commonly used in resolving dependencies in sampling-TAMP, but backtracking is too slow for long-horizon TAMP problems. This paper assumes access to a dataset of triples, each including a task plan, motion plan and state sequence. Learning from such a dataset using Transformers produces a heuristic function for guiding the backtracking search. Results show improvements over baselines that use diffusion samplers and Gaussian samplers, as well as baselines of GNN policies. Three household domains were used in experiments.", "summary_of_recommendation": "The paper presents a solid contribution to the sampling-based TAMP literature. The experiments can be improved by evaluating its generalization capability using different tasks and on real robots.", "technical_quality": 5, "clarity_of_presentation": 4, "potential_impact": 3, "robotics_focus": 3, "quality_of_limitations": 3, "questions_for_rebuttal": "Given the dataset, couldn't one directly learn a TAMP planner? What's preventing us from doing so? Is it still necessary to use a fast-forward planner? \n\nIs it the case that the generalization evaluation was only performed in the same domain (where the training data was collected and where the experiments were performed)? What's its performance in generalization beyond that? \n\nIs there a reason that the proposed approach is difficult to be realized on a real robot? Evaluations or demonstrations would be helpful.", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "3u2ET5i8Bq", "reviewer": "Reviewer_5rxt", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": 3, "strengths_and_weaknesses": "", "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": "The paper presents an approach of handling long-horizon action dependencies in TAMP problems.  The proposed method uses a transformer based feasbility classifier that determines whether a given task plan can be refined from a current input state. The classifier is also used  in alternatively to generate negative data set in between its' training. The confidence  returned by the classifier is used to backtrack to the previous step on failed searches. Experiments are conducted on 2D and 3D environment and compared against diffusion based  and GNN based models in terms of success rate. The proposed method shows superior  performance in the experimental environments.", "summary_of_recommendation": "The paper shows a novel approach in TAMP with promising results in 2D. Needs improvement in experimental evaluation and related work.", "technical_quality": 4, "clarity_of_presentation": 4, "potential_impact": 3, "robotics_focus": 3, "quality_of_limitations": 3, "questions_for_rebuttal": "1) The author should consider other traditional and learning based method on culprit detection problem and guided search in TAMP such as:-\nLagriffoul F, Andres B. Combining task and motion planning: A culprit detection problem. The International Journal of Robotics Research. 2016;35(8):890-927. doi:10.1177/0278364915619022\nWells, Andrew M., et al. \"Learning feasibility for task and motion planning in tabletop environments.\" IEEE robotics and automation letters 4.2 (2019): 1255-1262.\nC. V. Braun, J. Ortiz-Haro, M. Toussaint and O. S. Oguz, \"RHH-LGP: Receding Horizon And Heuristics-Based Logic-Geometric Programming For Task And Motion Planning,\" 2022 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Kyoto, Japan, 2022, pp. 13761-13768, doi: 10.1109/IROS47612.2022.9981797. keywords: {Legged locomotion;Heuristic algorithms;Decision making;Kinematics;Programming;Robustness;Planning},\nM. Khodeir, A. Sonwane, R. Hari and F. Shkurti, \"Policy-Guided Lazy Search with Feedback for Task and Motion Planning,\" 2023 IEEE International Conference on Robotics and Automation (ICRA), London, United Kingdom, 2023, pp. 3743-3749, doi: 10.1109/ICRA48891.2023.10161109. keywords: {Adaptation models;Runtime;Codes;Automation;Search problems;Manipulators;Skeleton},\n\n2) Although the authors stated RNN can be used as the feasibility classifier, an explanation  behind using transformer as the underlying architecture will be useful.\n\n3) The experiments and comparison are conducted primarily with 2D environments. Most of existing TAMP problems are in 3D. The authors should provide the experimental evaluation focused  on the results from 3D environments. \n\n4) What are the DOF of the robot in 2D environments?\n\n5) The authors should consider benchmark TAMP problems from: https://pypi.org/project/guided-tamp-benchmark/\nand http://tampbenchmark.aass.oru.se/index.php?title=Main_Page", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The reviewers found many positive aspects of the paper, but also clearly articulated some questions for the authors.
Thank you for your responses.
Decision: Accept