Learning Long-Horizon Action Dependencies in Sampling-Based Bilevel Planning

Authors: bartłomiej  cieślar
leslie  kaelbling
tomás  lozano-pérez
jorge  mendez-mendez
csail  mit
Venue: robot-learning_org_CoRL_2024_Conference
Published: 2024-06-07 05:00:52

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.

Main paper: 
 introduction: 
 The goal is to place blocks in the box, but space constraints require early placements to leave room for later ones.Solving long-horizon problems, (e.g., preparing a meal), is key toward deploying autonomous robots. Model-based approaches, and in particular 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 it 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.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→ • • • →slice), and a motion planner, which computes motions to enact the abstract actions. If all of the long-horizon dependencies are encoded at the task-planner level (e.g., picking a cucumber requires the gripper to be free, and picking a knife causes the gripper to not be free), then TAMP can find a valid sequence of 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 a 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 variety 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 successful and failed plans, and trains a transformer to predict whether a state is conducive to a solution, given a chosen sequence of abstract actions. We show empirically that our method substantially im-proves the efficiency of backtracking, resulting in a much higher success rate given a time limit. Our contributions include: 1) a 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. 
related work: 
 Many recent works have developed learning mechanisms to improve the capabilities of model-based planning. Some methods learn planning models, in the form of state abstractions, abstract actions, controllers, or low-level transition functions [6, 8, 4, 9, 10, 11, 12] . The learned models are then used as part of the planning domain itself, to perform planning. Our approach instead learns mechanisms to improve the efficiency of planning given a 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] . Related to our work, which aims to predict motion planning failures before they occur, are 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 a 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 to [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] or using a learned model directly as a planner [23] . These methods are complementary to our work and could be used in combination with it.3 Problem Formulation 
tamp formulation: 
 A deterministic TAMP domain Z = ⟨O, T, Λ, Ω, ϕ, S, A, f, α⟩ consists of a set of objects o ∈ O (e.g., the red mug) of types t ∈ T (e.g., mugs). The low-level elements are a set of object-oriented continuous states s ∈ S = o∈O S o , a set of continuous actions a ∈ A, and a partial low-level transition function f : S × A → S ∪ {⊥} (⊥ denotes execution failure). Objects of a type share a common state set: S t ⊃ S o (e.g., pose and size of the red mug). The abstract elements are the set of abstract states λ ∈ Λ (e.g., the mug is red and on the table, the table is on the floor) and the set of lifted abstract actions ω ∈ Ω : t 1 × . . . × t mω → Ω (e.g., pick⟨object⟩), which can be grounded into ground abstract actions ω = ω(o 1 ∈ t 1 , . . . , o mω ∈ t mω ) ∈ Ω (e.g., pick⟨red mug⟩) with specific typed objects. The partial abstract transition function ϕ : Λ × Ω → Λ ∪ {⊥} specifies how ground abstract actions change the abstract state (e.g., picking the red mug removes it from the table).The state abstraction function α : S → Λ relates the continuous and abstract states (e.g., given the red mug's pose, it is on the table), while abstract and continuous actions are related by controllers c ω : Θ cω × S → S ∪ {⊥} for each ground abstract action ω (e.g., a pick object controller). Each controller is parameterized by θ ∈ Θ cω (e.g., a grasp for the object) and follows the constraints of the abstract transition function, so ∀ s∈S;θ∈Θc ω c ω (θ, s) = s ′ =⇒ ϕ(α(s), ω) = α(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 α(s ′ ).A TAMP problem ⟨s 0 , G⟩ consists of an initial low-level state s 0 and a set of abstract goal states G (e.g., the red mug is on the third shelf). One way to solve a TAMP problem is to first find a task plan π = ⟨ω 1 , . . . , ω n ⟩ of ground abstract actions that induces a sequence of abstract states λ 0 , . . . , λ n such that α(s 0 ) = λ 0 , ∀ 1≤i≤n ϕ(λ i-1 , ω i ) = λ i , and λ n ∈ G, using search algorithms such as Fast Downward [7] with A* [24] . TAMP solvers then refine the task plan into a controller plan p = ⟨θ 1 , . . . , θ n ⟩, which induces states σ = ⟨s 0 , . . . , s n ⟩ such that ∀ 1≤i≤n c ωi (θ i , s i-1 ) = s i .1: function BT(s i , i, π) θ i+1 ∼ ψ ωi+1 (s i ) 6: s i+1 := c ωi+1 (θ i+1 , s i ) 7:if s i+1 = ⊥ then p := BT(s i+1 , i + 1, π) return ⊥ Algorithm 1: Classic Backtracking.SeSamE approaches [5, 6] set the controller parameters using sampling distributions ψ ω associated with each ground abstract action ω. Samplers then generate controller parameters θ ∼ ψ ω (s) using those distributions, conditioned on the continuous state. Parameters are found via backtracking search on an internal model of the domain (Algorithm 1 [2] ), which recursively extends the current refinement ⟨θ 1 , . . . , θ i ⟩. The main loop (Lines 4-11) repeatedly samples new controller parameters for the current ground abstract action ω i+1 (Line 5), checks if the sampled parameters enable computing the next state that matches the expected abstract state (Lines 6-8), and continues the search recursively (Lines 3, 9-11). If there exists a dependency between ground abstract actions ω i and ω i+d , the algorithm will take exp(O(d)) steps to detect if ω i is sampled incorrectly. Note that Algorithm 1 is not complete (it can become probabilistically complete if we allow the first action's parameters θ 1 to be resampled ad infinitum), and the base of the exponent depends on r iter .To see why Algorithm 1 struggles with long-range dependencies, consider the (infinite, layered, and directed) graph of continuous states reachable from the initial state s 0 after any number i of steps, following a task plan π = ⟨ω 1 , . . . , ω n ⟩. We will characterize the states s i that enable reaching states ⟨s i+1 , . . . , s n ⟩ that match the abstract states ⟨λ i+1 , . . . λ n ⟩ associated with π. Our approach in Section 4 learns to detect states that don'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 i and task plan prefix length i. This condition can be defined inductively as: the state s i matches the expected abstract state λ i , and some continuous state s i+1 reachable from s i by following the next action in the plan ω i+1 , permits refining the task plan. Formally, we consider the graph ⟨V, →⟩. V i at each layer i is defined inductively. The base case contains only the initial state: V 0 ≜ {⟨s 0 , 0⟩}. The (i + 1)-th layer contains all the states that can be reached by following the (i + 1)-th action, ω i+1 , from any state in the previous layer V i : V i+1 ≜ {⟨s ′ , i + 1⟩ : ∃ ⟨s,i⟩∈Vi;θ∈Θc ω i+1 c ωi+1 (θ, s) = s ′ }. The nodes in the graph are V ≜ 0≤i≤n V i . The edge relation → denotes that there is a parameterization of the (i + 1)-th controller that brings a state s to a next state s ′ : ⟨s, i⟩ → ⟨s ′ , i + 1⟩ ≜ ∃ θ∈Θc ω i+1 c ωi+1 (θ, s) = s ′ . The condition for refinability of the task plan from a given state is defined inductively. In the base case, γ(⟨s, n⟩) ≜ α(s) = λ n . The inductive step is the cause for the computational difficulty of backtracking in SeSamE:EQUATIONTo 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 a 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, γ holds for all states in the top row (1A-6A) corresponding to top grasps, and does not hold for states in the bottom row (1B-6B). However, Algorithm 1 uses only β to decide whether to continue expanding the current refinement. In our example, β holds for states in the bottom row (1B-6B), which are not conducive to a successful box placement. However, using backtracking to approximate η takes exponentially long in n -i. If the donut is grasped from the side, this causes the search to focus on retrying topping actions for a 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's grasped from the side and vice versa. The colored boxes describe the ground abstract actions ω available to the robot, with the arrows signifying corresponding continuous actions (achievable by the controller for a 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 η(⟨s i+1 , i + 1⟩) before Line 9. In other words, we want to assess for each state s i+1 and plan suffix ω i+1 , . . . ω n , whether there exists a valid refinement of the suffix. We could then evaluate this condition before Line 9 and, if it doesn't hold, return to Line 5 to resample parameters θ i+1 . This would avoid the expensive backtracking necessary for Algorithm 1 to discover that the choice of θ i+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 ψ ωi+1 , since otherwise the planner would not find them. 
learning to optimize the backtracking search: 
 To reduce the backtracking, we propose to learn η to determine whether it is possible to further refine the controller plan from the current state s i and use it as a heuristic for search. We do so using a feasibility classifier h that, based on a sequence of prior states σ = ⟨s 0 , . . . , s i ⟩ and the task plan π = ⟨ω 1 , . . . , ω n ⟩, classifies whether a given task plan is likely to be refinable from the current state.See Appendix E for a simplified explanation of this section.1: function BT-h(σ, π, conf min , h) 2:σ : ⟨s 0 , . . . , s i ⟩,π : ⟨ω 1 , . . . , ω n ⟩ 3:if i = n then return ⟨⟩ 4:for 1 . . . r iter do 5:θ i+1 ∼ ψ ωi+1 (s i ) 6: s i+1 := c ωi+1 (θ i+1 , s i ) 7: if s i+1 = ⊥ then continue 8: η, conf := h(π, σ ⊕ ⟨s i+1 ⟩) 9:if ¬η then continue 10:p := BT-h(σ ⊕ ⟨s i+1 ⟩, π, min(conf min , conf), h) 11: if p ̸ = ⊥ then 12: return p ⊕ ⟨θ i+1 ⟩ 13: if conf > conf min then 14: return ⊥ 15:return ⊥ Algorithm 2: Backtracking with Feasibility Classifier. The blue parts highlight changes from Figure 1 .Algorithm 2 uses the classifier to prune controller parameter samples that would lead to unrefinable states. With each of r iter search attempts (Lines 4-14), the algorithm first samples the next controller parameters θ i+1 (Line 5) and tries to run the controller to produce the next state s i+1 (Lines 6-7). Then, it uses the feasibility classifier to predict whether further search is likely to succeed from that state (Lines 8-9). The search then continues recursively (Lines 3, 10-12). Inspired by [18] , if the current search step fails, the algorithm backtracks to the previous step with the lowest feasibility classifier confidence conf min (Lines [13] [14] . This backjumping procedure further reduces backtracking by resampling parameters that are least likely to succeed, under the learned classifier.Per the definition in Equation 1, our classifier requires as input the current state s i and the suffix of the task plan ⟨ω i , . . . , ω n ⟩. Notably, both of these inputs vary in length across problems and even across steps within a problem-the number of steps in the task plan trivially affects its length, and assuming that the continuous state set S t for each type t is a real-valued vector space R k , 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 . In principle, we could have two sets of tokens: one representing s i as a set of object states, and another representing the sequence of ground abstract actions in the task plan. However, it is unclear how a transformer would simultaneously handle the (ordered) sequence of actions and the (unordered) set of states.Figure 3 : Architecture of the feasibility classifier h, supplied with the sequence of ground abstract actions ω j = ωj (o j,1 , . . . , o j,mω j ), 1 ≤ j ≤ n and refined continuous states s 0 , . . . , s i .Instead, we let each token be a pair ⟨s j , ω j ⟩, 1 ≤ j ≤ n. Such a token must contain information to identify the abstract lifted action ωj , the objects that ground the action o 1 , . . . , o mω j , and the state s j . Including the entirety of s j in the input would again require a varying-length representation. Since we will have multiple such tokens, we can restrict the representation of s j to the state of objects in the action, s j,o1 , . . . , s j,om ωj . 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 l , we use a one-hot encoding with a fixed maximum size r maxobj -we randomize 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 m ω varies across actions. To produce 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 ω 1≤j≤i , we use the state s j produced by the controller, while for subsequent actions we use the latest state s i . Because featurizer inputs from such states may be drawn from different distributions 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 ω j>i that have not been refined. D ′ := {⟨π, σ⟩ ∈ D : n -1 ≥ l + 1} 6:for random r dp ⟨π, σ⟩ ∈ D ′ do 7:σ : ⟨s 0 , . . . , s n ⟩, π : ⟨ω 1 , . . . , ω n ⟩ 8:σ pref := ⟨s 0 , . . . , s l ⟩ 9: T := BT-h-CaptureSearchTree(σ pref , π, 1.0, h) 10: D + ∪= {⟨π, σ pref ⊕⟨ŝ⟩⟩ : ŝ ∈ SuccessfulTries(T)} 11: D -∪= {⟨π, σ pref ⊕ ⟨ŝ⟩⟩ : ŝ ∈ StuckTries(T)} 12: h := TrainNeuralClassifier(D + , D -, l) 13:return h Algorithm 3: Generating data for the Feasibility Classifier.We assume access to a dataset D of demonstrations in the form of task plans, controller plans, and state sequences: ⟨π, p, σ⟩. Demonstrations can trivially be used as positive training data for the classifier: all parameters in the controller plan were sampled correctly, so any prefix of the controller plan ⟨θ 1 , . . . , θ i ⟩ and its associated sequence of states σ = ⟨s 0 , . . . , s i ⟩ should be accepted by our classifier. One (naïve) way to obtain negative data is to run the backtracking search from Algorithm 1 on the same TAMP problems that we obtained demonstrations for. In the resulting search tree, from each node s 0 , . . . , s n-1 on the successful 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 r iter , these can be treated as unrefinable states. Concretely, we can take any prefix of the successful state sequence σ = ⟨s 0 , . . . , s i ⟩ and follow any application in the search tree of the subsequent controller c ωi+1 with parameters θ ̸ = θ i+1 that differ from the successful controller plan. The resulting state ŝ = c ωi ( θ, s i ) can be combined with σ to produce a negative data point for the given task plan π. This process is illustrated in Figure B.1. Note that it 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 state s l on the successful sequence of states σ = ⟨s 0 , . . . , s n ⟩. We then alternate running classifieraided backtracking (Algorithm 2) to generate negative data starting from s l and training a classifier using the obtained data to use for the next round of backtracking for data collection for a decreased value of l. The process is summarized in Algorithm 3. Initially, the feasibility classifier always outputs a confidence of 1 (Line 2). We then iterate over descending state prefix lengths, starting from n -2 (Lines 4-12). For each task plan prefix length l, we select r dp viable data points (i.e., task plans of length ≥ l + 2; Lines 5-6). For each data point, we 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 in 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 a given prefix upon finding the first positive or negative data point. 
experiments: 
 Our experimental evaluation aims to address (Q1) whether using backtracking with a feasibility classifier can meaningfully improve the speed of plan refinement, (Q2) whether the method generalizes to 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.We use 2D (Shelves, Donut, Statue) and 3D (Packing, Trays-simulated in PyBullet) quasi-static domains with collision checking only after each action (Figures 1 and 4 ). We provide abstract actions ω and controllers c ω for each domain, and the learners must determine the continuous parameters θ cω 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 to parameterize the controllers. For the 3D domains, we perform planning without simulated motion, In 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 a 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 pick-and-place of a statue in a grid of rooms (side length-train: 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-place of blocks (training: 4-10, eval: 10) by a robot arm from a table to a 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 a robot arm from a table into a set of trays. Each tray should not have more than one block, but this can only be tested at the end.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 is a feedforward diffusion model trained on the data of the corresponding lifted action from the demonstrations in D.• Myopic Diffusion Samplers (B1a): The diffusion-based samplers used by our method, introduced in [5] , used for general backtracking without a feasibility classifier.• Myopic Gaussian Samplers (B1b): An alternative to B1a 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 (A1) and the data-gathering procedure (A2, A3). See Appendix A for details.To address Q1-3, we evaluated the baselines on the 2D domains. For Q1 and Q2, we used a dataset D of 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 in Section 5.1. For Q4, we evaluated the ablations on the Pybullet domains, with a dataset of 2000 data points. For the remaining experimental data see Appendix D.The results of Figure 5 demonstrate that our method is on average superior to all our baselines and ablations for all experimental setups. Additionally, it shows 40%+ improvement in number of problems solved over the baselines on the non-generalization and non-reduceddata experiments. Thus, Q1 can be answered affirmatively. For Q2, our method shows limited 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, making this our only environment where an individual object's state is out-of-distribution for the networks. In addition, transformers show limited generalization to out-of-distribution input lengths [29] , which may be a contributing factor.The results in Figure 6 address Q3, showing superior performance in reduced data regimes. More initial training data improves performance.Figure 7 contains results to answer Q4. Compared to our results, the data collection ablation A2 and A3 shows on average 25%-50% reduced performance on the Trays domain, which demonstrates that our bootstrapping approach for data collection is critical to the method's overall success. Simmilarly, ablating the backjumping (A1) reduces the method's performance by on average 50% reduced solution success rate on the Packing domain, which highlights the significance of that procedure in our method. 
conclusion and limitations: 
 We proposed a solution to learn to account for long-horizon action dependencies in sampling-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 common solutions to use bigger networks or collect larger datasets can address this limitation. One challenge specific to our method is that data is labeled as positive or negative by our own data collection mechanism. If our sampling distributions ψ are low-quality (which can happen in the case of learned distributions similar reasons of scale) or we attempt too few samples r iter at each step of backtracking, this can lead to noisy labels that complicate the training of the classifier. Increasing r iter can reduce this labeling noise. Our choice to use transformer architectures carries the drawback 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. 
 
 Appendix: Sampling-Based Bilevel Planning" Bartłomiej Cieślar 1 , Leslie Kaelbling 1 , Tomás Lozano-Pérez 1 , and Jorge Mendez-Mendez 2 1 CSAIL MIT 2 Stony Brook University {bcieslar,lpk,tlp}@csail.mit.edu jorge.mendezmendez@stonybrook.eduFor 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.All experiments were run on 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.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 a possible failure. The cover must be placed after the boxes are on the shelves. The lifted abstract actions are "Move Box", "Move Cover to Top" and "Move Cover to Bottom". All lifted abstract actions share a single controller, whose parameters are some ⟨x, y⟩ 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 a box or on a shelf (depending on the goal). 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. The lifted abstract actions are "Move Robot", "Grasp Donut" "Place Donut in Box", "Place Donut on Shelf" and "Add Topping to Donut". The movement, grasp position and placement position in the abstract action controllers are parameterized by the ⟨x, y⟩ displacement. All other controller parameters are determined using binary decisions based on a 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 far away from the robot; a similar restriction applies to the grasping and placement actions. The positions of the objects are relative to the robot, and the objects cannot be rotated. There are 10 varieties of possible toppings in the goals.• Statue Domain: A robot traverses a grid of rooms connected by doors to pick up a statue from the bottom-left corner 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 parameterization specifies the offset ⟨x, y⟩ that the robot moves by, and the grab controller specifies a thresholded value for the orientation of the statue (horizontal, vertical) in the 3D axis from the front of the robot (not perpendicular to the world). The positions of objects are in absolute coordinates, and (other than the horizontal/vertical rotations of the statue) the objects cannot be rotated.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 to grasp it and where to place the block (upright) relative to the center of the box. The positions of objects are 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 configurationthis is necessary for the task planner to find a 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 a one-hot encoding of the tray. The positions of objects are in absolute coordinates, and the rotations are in quaternions.This section describes the ablations used to validate the need for each element of our approach.• No backjumping (A1): 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 as our full approach.• Negative training data from the longest failed trajectory (A2): To assess the importance of our data collection scheme, we train our 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.Table 1 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 based on its prediction accuracy on the Shelves domain, 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-based methods (including our own) set r iter = 20 for all domains. Our data collection method from Section 4.3 collects r dp = 4000 data points per the iteration of the data collection loop. To ensure a fair comparison, the Gaussian and diffusion samplers were trained for a comparable amount of time, and the GNN baseline was trained for a similar amount of time as our method (including the data collection procedure). 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 hyperparameters for the classifier, summarized in 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 a standard binary cross-entropy loss with the Adam optimizer, over randomly drawn mini-batches. In addition to the output of the featurizer network, for each token we concatenate a 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 ω j such that j = i). These additional inputs aid the network with locating the key information in the sequence of tokens. As is standard practice in the literature, we also concatenate the sinusoidal positional encodingto each token. As described in [29] , we offset the positions of the tokens by a random value to improve out-of-distribution generalization with respect to the length of the task plan. Before passing the token to the transformer, we pass it through a linear map to ensure In this appendix, we present the experimental results not included in Section 5.4. The timings only consider the tasks for which each baseline succeeded, which is why on the 2D domains our method sometimes exhibits a higher runtime than the baselines. The timings for the GNN baseline (B2) were not included because the policy is designed to compute a single solution; if the solution works, it succeeds, and otherwise it immediately fails. In consequence, when it does succeed, it is much faster (∼ 1000×) than our approach.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 parameters for the motion controllers associated with those operators (the motion plan). The task plans are commonly found using common search algorithms such as Fast Downward [7] with A* [24] .The controller parameters are 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 contribution 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 a 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 on states generated after running each controller in sequence.The states are then passed through featurizer networks, which are a simple feedforward architecture [25] with a ReLU activation [26] , to form a sequence of tokens. These tokens are then concatenated 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 parameter discovery is possible. The featurizer networks, transformer and final linear layer are trained jointly in a 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 parameter 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 a positive training datapoint. We also notice that, given a successful motion plan, the controller parameter search can be restarted at any point in that plan to produce the aforementioned datapoints. The challenge to overcome is that, without the use of an already functioning feasibility classifier, this datapoint collection procedure is prohibitively long. Thus, in our data collection algorithm, given a set of already found motion plans, we step-by-step restart the controller parameter search from progressively earlier points in 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 a more detailed description of the algorithm.F Discussion of running the method on a real world setupWhile our experiments in Section 5 in the main paper focused on simulated domains, our approach could feasibly be used on a real robot under certain constraints. In summary, other than a faithful simulator of the real world scene, we require a source of data to train the feasibility classifier, which need not be realistic, just representative of what plans will be run on the simulator during evaluation. Specifically, the following components would be crucial to add to our system before running it on real hardware:• A simulator synchronized with the real robot. The challenge here is making sure the positions 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 B1a from Section 5.2) in a 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 simulated environment. Importantly, the plan found during motion planning with the simulator would have to be executed in an open-loop manner, i.e. under the assumption of no catastrophic execution failure (such as the robot dropping an object). Should we want to handle a case of such a failure, a replanning procedure would have to be introduced into the task planner and we would have to collect data for such failure recovery during the successful plan search.8th Conference on Robot Learning (CoRL 2024), Munich, Germany. 


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

Reviews: review: title: title: Official review
paper_summary: paper_summary: 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.
main_review: main_review: Positives:
- The problem the paper addresses is important and challenging.
- The paper is well-written, except for a few parts (see writing comments).
- The biggest positive for me is that the computational problem is grounded in a popular existing approach (SeSamE-based methods) and is motivated in a rigorous manner.
- I appreciate the automated voice used in the video very much as it strengthens the double blind review process

Negatives:
- There are no hardware experiments in the paper and this is a significant concern for me. A lot of TAMP research heavily relies on accurate simulation of real-world perception and physics. Further, this paper also heavily relies on data collection, which is performed in simulation as well. Several issues come up with data collection and TAMP in the real world; sometimes they are pervasive enough that you might have to throw away some of your rigor. It would have been preferred to begin with a focus on applying the approach to real-world, 3D environments as far as possible, even if at the expense of making technical assumptions for these experiments or covering fewer domains. I would like to see that the authors have thoroughly thought about this in their response to my first question for rebuttal and have a realistic plan for hardware experiments.

Writing comments:
- There is a critical reference to the domain from Section 5 in an involved explanation in Section 3: I think it is perfectly reasonable to describe the domain in Section 3 (mentioning that we use an example to ground understanding of the approach) and refer to *it* in Section 5. This will make Section 3 much easier to read.
- The notation for the TAMP problem description can be made a lot more readable by utilizing diagrams to depict the notions of continuous and abstract states, grounding, etc. Consider using [this blog post](https://lis.csail.mit.edu/bilevel-planning-for-robots-an-illustrated-introduction/) as a reference.
- Typically with papers heavy on notation, I think it is useful to have a “TL;DR” or an “In a Nutshell” section that uses minimal notation and terminology but still explains the core algorithmic contribution of the approach. I would appreciate adding such a section before the Problem Formulation. I understand that there is limited space and a trade-off here and this is only a suggestion. As a solution, consider moving either the results on the 2D domains or some of the result analysis to Supplementary material.

Note: My score for review confidence is a 4 solely because I have not verified in minute detail the math in Section 3.3 and correctness of Algorithm 2.
questions: questions: 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:
    - is grounded within the specific context of your paper as far as possible (and does not talk about addressing problems for extremely *general* approaches)
   - includes proposing a few concrete next steps (be it “engineering” or “research”)
   - includes thoughts about the data collection
   - includes references to support any claims where applicable
2. 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.
3. The work heavily relies on data collection. Can you please briefly comment on the implications on generalization of your approach to unseen domains?
4. 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.
5. 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)
limitations: limitations: 3
review_summary: review_summary: 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".
title: title: Learning search heuristics for sampling-based TAMP
paper_summary: paper_summary: 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.
main_review: main_review: The paper makes a solid contribution demonstrating the applicability of supervised learning methods to learning heuristics for sampling-based TAMP problems. The paper can be improved in the following ways. 

1, The paper presentation can be improved to make it more friendly to people who are less familiar with the literature of TAMP (sampling-based or not) and backtracking search (with heuristics or not). The "packing" example shown in Figure 1 can be revised to serve such purposes. 

2, It's not surprising to see that one can learn heuristics for guiding the backtracking search (for TAMP or other tasks) -- generally it's expected one can leverage supervised learning methods to improve search efficiency. The unknown is on the generalization of the learned heuristics (Q2 in Section 5 on Experiments). Unfortunately, the experiments only evaluated the generalization in domains of different sizes. Could the proposed approach generalize to novel objects, novel requests, novel tasks, different actions, and even different domains? 

3, This is a minor comment. Figure 2 is helpful as it highlights the point of the learned heuristic function but still could be more intuitive. Some visuals on a real robot (or simulation) would be very nice. The current version requires some imagination to clearly get the point. 

4, It seems the paper doesn't include a real-robot component.
questions: questions: 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? 

Is 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? 

Is there a reason that the proposed approach is difficult to be realized on a real robot? Evaluations or demonstrations would be helpful.
limitations: limitations: 3
review_summary: review_summary: 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.
title: title: Important and novel approach on long-horizon dependencies in TAMP.  Needs improvement in related work and experimental evaluation.
paper_summary: paper_summary: 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.
main_review: main_review: Strength:

The paper considers the important and relevant problem of long-horizon dependencies TAMP planning. The authors compared against 3 different methods. The authors provided a detailed and clear explanation on the data generation method  and how to include the classifier in the TAMP approach.

Weakness:

More detailed clarity in TAMP formulation section is needed.  The authors need to include relevant work in related section. Experimental evaluation need to be focused on 3D problems.  Details are provided below:

1) The author should consider other traditional and learning based method on culprit detection problem and guided search in TAMP such as:-
Lagriffoul 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
Wells, Andrew M., et al. "Learning feasibility for task and motion planning in tabletop environments." IEEE robotics and automation letters 4.2 (2019): 1255-1262.
C. 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},
M. 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},

2) Section 3.1 need more explanations and definitions with examples. For example, it is difficult to understand the difference of lifted abstract actions and ground abstract actions.

3) Although the authors stated RNN can be used as the feasibility classifier, an explanation behind using transformer as the underlying architecture will be useful.

4) 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. What are the DOF of the robots in 2D environments?

5) The authors should consider benchmark TAMP problems from: https://pypi.org/project/guided-tamp-benchmark/
and http://tampbenchmark.aass.oru.se/index.php?title=Main_Page
questions: questions: 1) The author should consider other traditional and learning based method on culprit detection problem and guided search in TAMP such as:-
Lagriffoul 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
Wells, Andrew M., et al. "Learning feasibility for task and motion planning in tabletop environments." IEEE robotics and automation letters 4.2 (2019): 1255-1262.
C. 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},
M. 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},

2) Although the authors stated RNN can be used as the feasibility classifier, an explanation  behind using transformer as the underlying architecture will be useful.

3) 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. 

4) What are the DOF of the robot in 2D environments?

5) The authors should consider benchmark TAMP problems from: https://pypi.org/project/guided-tamp-benchmark/
and http://tampbenchmark.aass.oru.se/index.php?title=Main_Page
limitations: limitations: 3
review_summary: review_summary: The paper shows a novel approach in TAMP with promising results in 2D. Needs improvement in experimental evaluation and related work.