BaB-ND: Long-Horizon Motion Planning with Branch-and-Bound and Neural Dynamics

Ablation study to show the contribution of individual components, such as the branching heuristic or specific modifications to the bound propagation method

We conducted additional ablation studies on the Object Sorting and Pushing with Obstacles tasks to evaluate how different design choices impact planning performance following three settings below:

1. Different heuristics for selecting subdomains to split:

   • 1. Select based on both lower and upper bounds ($\underline{f}^*\_{\mathcal{C}\_i}$ and $\overline{f}^*\_{\mathcal{C}\_i}$).
   • 2. Select based only on upper bounds ($\overline{f}^*\_{\mathcal{C}\_i}$ only).
   • 3. Select based only on lower bounds ($\underline{f}^*\_{\mathcal{C}\_i}$ only).

   Among these heuristics, selecting promising subdomains based on both lower and upper bounds achieves better planning performance by balancing exploitation and exploration effectively compared to the other strategies.

   	$\underline{f}^*\_{\mathcal{C}\_i}$ and $\overline{f}^*\_{\mathcal{C}\_i}$	$\overline{f}^*\_{\mathcal{C}\_i}$ only	$\underline{f}^*\_{\mathcal{C}\_i}$ only
   Object Sorting	31.0482	32.1249	33.2462
   Pushing with Obstacles	31.9839	32.2777	32.6112

2. Different heuristics for splitting subdomains:

   • 1. Split based on the largest $(\overline{\boldsymbol{u}}\_{j} - \underline{\boldsymbol{u}}\_{j}) \cdot |n\_j^{\text{lo}} - n\_j^{\text{up}}|$.
   • 2. Split based on the largest $(\overline{\boldsymbol{u}}\_{j} - \underline{\boldsymbol{u}}\_{j})$.
   • 3. Split based on the largest $|n\_j^{\text{lo}} - n\_j^{\text{up}}|$.

   Our heuristic demonstrates superior planning performance on both tasks by effectively identifying important input dimensions to split.

   	$(\overline{\boldsymbol{u}}\_{j} - \underline{\boldsymbol{u}}\_{j}) \cdot \|n\_j^{\text{lo}} - n\_j^{\text{up}}\|$	$(\overline{\boldsymbol{u}}\_{j} - \underline{\boldsymbol{u}}\_{j})$	$\|n\_j^{\text{lo}} - n\_j^{\text{up}}\|$
   Object Sorting	31.0482	34.5114	32.8438
   Pushing with Obstacles	31.9839	32.3869	32.6989

3. Bounding component:

   • 1. Use our bounding approach with propagation early-stop and search-integrated bounding.
   • 2. Use constant zero as trivial lower bounds to disable the bounding component.
   • 3. Disable both the bounding component and our heuristic for selecting subdomains to split.

   Our bounding component improves planning performance by obtaining tight bound estimations, helping prune unpromising subdomains to reduce the search space, and prioritizing promising subdomains for searching.

   	Ours	Disable bounding	Disable bounding and domain selection heuristic
   Object Sorting	31.0482	33.6110	34.4535
   Pushing with Obstacles	31.9839	32.3419	34.6227

Could you provide more details on the novelty of the approach from a machine learning point of view ?

From a robotics and motion planning perspective, our approach demonstrates significantly better performance compared to principled optimization tools like MIP and other sampling-based motion planners. This is demonstrated across diverse tasks (e.g., rigid and deformable objects, object piles, and non-convex feasible regions) and model architectures (e.g., MLP- and GNN-based neural dynamics models). As noted by Reviewer ci99, “It might set a new direction in combining machine learning verification methods with motion planning.”

From a machine learning perspective, while our BaB-ND is inspired by alpha-beta-CROWN, a method that has achieved notable success in formal verification of machine learning, it cannot be directly applied to the planning and optimization challenges we address. To bridge this gap, we completely redesigned the branching techniques, extensively adapted the underlying bounding algorithm, and integrated it with sampling-based planning methods (searching). These technical innovations were essential for achieving superior planning performance across a range of complex robotic manipulation tasks.

We have attempted to address all your questions and made the corresponding changes to the paper. We believe the paper is now much stronger thanks to your suggestions. Please let us know if you have any additional concerns and we will really appreciate it if you can reevaluate our paper.

Could you illustrate the method using a specific example of a robotic manipulation task, detailing how abstract concepts like the input u and bounds map to task-specific elements?

We have provided a simplified example of our manipulation task with an illustration of our method in Figure 3 in the paper. Below, we refer to Figure 3 to introduce abstract concepts:

In Figure 3(a), we first define the configuration of the task, where the robot moves left or right to push an object toward the target. Now we define the inputs, objective, neural dynamics model, subdomains, bounds and the pruning process involved in this task:

• Inputs: The inputs in our formulation are the action sequence with a horizon of $H$. In this simplified case, we consider a horizon of 1 and restrict the action to 1D. So in this case, the inputs become a 1D action $u \in \mathcal{C}$ representing the movement of the robot pusher, with $\mathcal{C} = [-l, l]$ as its domain, where $l$ is the maximum movement distance (e.g., $1 \, \text{cm}$ in practice). A value of $u < 0$ means the robot moves left, while $u > 0$ means the robot moves right.

• Objective: The objective $f(u)$ measures the distance between the object and the target under a specific action $u$. In this case, $f(u) = d\_1^2 + d\_2^2$, where $d\_1$ is the distance between a keypoint ($P\_1$) on the object and the corresponding keypoint ($P\_{1,T}$) on the target, and $d\_2$ is the distance between another keypoint pair ($P\_2$ and $P\_{2,T}$). For example, if the robot moves left ($u < 0$), $d\_2$ decreases while $d\_1$ increases.

• Neural dynamics model: The values of $d\_1$ and $d\_2$ depend on a neural network dynamics model $f\_{\text{dyn}}$. This model takes as input the current positions of $P\_1$ and $P\_2$, along with an action $u$, to predict the next positions of $P\_1$ and $P\_2$. Based on these predictions, $d\_1$ and $d\_2$ are updated accordingly and $f(u)$ may exhibit non-convex behavior.

Our goal in planning is to find the optimal action $u^*$ that minimizes $f(u)$. To achieve this, we propose a branch-and-bound-based method. In Figure 3(b), $c$, and (d), we illustrate some key concepts and the overall procedure of our method:

• Subdomains: A subdomain $\mathcal{C}\_i \in \mathcal{C}$ is a subset of the entire input domain $\mathcal{C}$ (action space in our case). For example, in Figure 3(b), we initially split $\mathcal{C} = [-l, l]$ into two subdomains: $\mathcal{C}\_1 = [-l, 0]$ and $\mathcal{C}\_2 = [0, l]$, to separately analyze left and right movements.

• Lower and upper bounds: Each subdomain $\mathcal{C}\_i$ has associated lower and upper bounds: $\underline{f}^*\_{\mathcal{C}\_i}$ and $\overline{f}^*\_{\mathcal{C}\_i}$. These represent the bounds of the best objective in $\mathcal{C}\_i$ (${f}^*\_{\mathcal{C}\_i} := \min\_{u \in \mathcal{C}\_i} f(u)$). For example, if the optimal objective (the sum of the squared distances between keypoint pairs, $d\_1^2 + d\_2^2$) given by the best action in $\mathcal{C}\_i$ is 2, we might estimate $\underline{f}^*\_{\mathcal{C}\_i} = 1$ and $\overline{f}^*\_{\mathcal{C}\_i} = 3$. ($1\leq \min\_{x\in\mathcal{C}\_i}d\_1^2 + d\_2^2 = 2 \leq 3$) Intuitively, $\underline{f}^*\_{\mathcal{C}\_i}$ overestimates the effect of the optimal action on improving $f(u)$, while $\overline{f}^*\_{\mathcal{C}\_i}$ underestimates it.

• The pruning process: We compute $\underline{f}^*\_{\mathcal{C}\_i}$ using bounding (Figure 3$c$) and $\overline{f}^*\_{\mathcal{C}\_i}$ using searching (Figure 3(d)). These bounds allow us to determine whether a subdomain $\mathcal{C}\_i$ is promising for containing the optimal action $u^*$ or whether it can be pruned as unpromising. For instance, in Figure 3, if $\underline{f}^*\_{\mathcal{C}\_1} = 4$ and $\overline{f}^*\_{\mathcal{C}\_2} = 3$, it means that no objective better than 4 can be achieved in $\mathcal{C}\_1$, while no objective worse than 3 can occur in $\mathcal{C}\_2$. In this case, we can directly prune $\mathcal{C}\_1$ without further exploration.

• The branch-and-bound process: Our branch-and-bound process include 3 key components: branching, bounding and searching. Specifically, We can initially bound and search on the input space $\mathcal{C}$, and then split it into subdomains like $\mathcal{C}\_1$ and $\mathcal{C}\_2$ in Figure 3(b) (branching). Then on the new subdomains, we continue to repeat these steps, and we may prune any subdomains with lower bounds larger than the best objective we found so far. Iteratively,the algorithm will concentrate on improving the solution in the smaller and more promising subspace, leading to better planning actions.

Thank you for acknowledging our innovation in integrating bound propagation methods inspired by neural network verification, as well as the effectiveness and applicability of our BaB-ND on challenging manipulation tasks. We greatly appreciate your thoughtful comments and constructive suggestions. In response, we have included more detailed illustrations connecting our algorithm to a toy robotic task and have conducted additional experiments as suggested:

1. Runtime analysis for GPU and CPU versions of our BaB-ND;
2. Ablation study for our BaB-ND;
3. Runtime analysis comparing our BaB-ND with sampling-based methods;
4. Search space analysis for our BaB-ND.

Accessibility of method section, especially to readers not familiar with neural network verification techniques

Thank you for your suggestion. To improve the accessibility of our method, we have added a new example in Appendix A.1 that demonstrates its application to a practical, toy robotic task. This example includes a clear definition of the objective, inputs, bounds, and subdomains.

While we were unable to provide a full introduction to CROWN due to the extensive mathematical exposition it would require, we emphasize one key insight: CROWN provides a lower bound for our objective function, which is used in the branch-and-bound procedure to prune unhelpful subdomains. We have revised the paper to make this point clearer. Additionally, we address your two specific questions regarding our methods below.

Can you provide more details on the bounding step of the method? How are bounds estimated in a way that ensures meaningful pruning of subdomains in practical robotic tasks?

We first emphasize that it is not essential to understand the bounding algorithm to understand the high-level idea of BaB-ND. From the view of BaB-ND, bounding as a component is used to provide the lower bounds of the objective function in different subdomains. These bounds are used to prune unpromising subdomains and identity promising subdomains. We have improved our writing to highlight its high-level idea and provided a detailed illustration of the bounding component with a simple example on an MLP in our revised Appendix B.2.

To understand the effectiveness of the estimated bounds in pruning subdomains for practical robotic tasks, we conducted an additional experiment on task Pushing with Obstacles. Below, we report three metrics over the brand-and-bound iterations: (1) the normalized space size of pruned subdomains, (2) the size of the selected subdomains for searching, and (3) the improvements in the objective value.

As iterations progress, the average total space size of pruned subdomains increases rapidly and then converges, indicating the effectiveness of our bounding methods. Once the pruned space size reaches a plateau, the total space size of selected promising subdomains continues to decrease, showing that the estimated lower bounds remain effective in identifying promising subdomains. The decreasing objective over iterations further confirms that BaB-ND focuses on the most promising subdomains, reducing space size to the magnitude of $1 \times 10^{-4}$.

Dear Reviewer,

Please provide feedback to the authors before the end of the discussion period, and in case of additional concerns, give them a chance to respond.

Timeline: As a reminder, the review timeline is as follows:

November 26: Last day for reviewers to ask questions to authors.

November 27: Last day for authors to respond to reviewers.

Dear Reviewer kMxQ,

We have provided detailed responses to all your questions and revised our paper accordingly. We believe the paper is now much stronger, thanks to your constructive feedback and suggestions. As the paper revision deadline is less than a day away, we would appreciate it if you could kindly review our response and let us know if you have any additional questions. Thank you!

Best Regards,
The Authors

Thank you for your feedback. We greatly appreciate your follow-up questions and the opportunity to provide further clarification on our work. We have revised our paper to further include experiment details, provided a new visualization of the action definitions, as well as included new experiments to show our effectiveness under input discontinuities.

What are the exact inputs ( u ) in the robotic experiments? For instance, in the pushing with obstacles task, is the contact point between the pusher and the object determined by BaB-ND? The same question applies to the other tasks.

For all tasks, the inputs $\boldsymbol{u}$ are defined as a sequence of actions over a planning horizon of $H$. The specific definitions of the actions vary across tasks briefly discussed below, and we’ve also updated detailed descriptions in Appendix D.1 to make our paper more clear. We additionally provide a visualization of the action definitions and will include it in our future revision.

• For the Pushing with Obstacles and Object Merging tasks, the action is defined as the 2D movement of the pusher $(\Delta x, \Delta y)$ in the xy-plane. (visualization (a) and (b))
• For the Object Sorting task, the action includes the 2D initial position of the pusher $(x, y)$ and its 2D movement $(\Delta x, \Delta y)$ in the xy-plane. (visualization $c$)
• For the Rope Routing task, the action is the 3D movement of the gripper $(\Delta x, \Delta y, \Delta z)$ in 3D space along the xyz axes. (visualization (d))

For all tasks, we do not explicitly determine the contact point. Instead, our BaB-ND framework outputs a sequence of end-effector positions for the robot to follow, which implicitly decides, for instance, which side of the T-shaped object is being pushed.

How does the proposed method manage input domains that contain discontinuities or are subject to constraints?

There are indeed discontinuities in our input domains. For example, the Pushing with Obstacles task contains non-feasible regions occupied by obstacles. Below, we first detail how we consider the discontinuities in our objective function and then present additional empirical results showcasing the effectiveness of our method in handling discontinuities compared with the baselines. We have updated Appendix D.4 in our paper to make these settings more clear.

Objective formulation: We implicitly define the discontinuities or constraints in our objective function by adding large penalty items on the non-feasible regions. Take the example of Pushing with Obstacles, we define the cost function at step $t$ as following:

$c(x_t, u_t) = w_t\left\|x_t-x_{\text{target}}\right\| + \lambda \sum_{{o} \in {O}} \left(\text{ReLU}(s_{{o}} - \left\|p_t-p_{{o}}\right\|) + \text{ReLU}(s_{{o}} - \left\|x_t-p_{{o}}\right\|)\right)$

• $x_t$ and $u_t$ are the state and action at step $t$. $x_{\text{target}}$ is the target state. The state is the concatenation of the keypoint positions. The action is the pusher movement at every step.
• $\left\|x_t-x_{\text{target}}\right\|$ gives the difference between the state at time $t$ and the target, weighted by $w_t$.
• $p_t$ is the position of the robot pusher.
• $p_o$ and $s_o$ give the position and size of an obstacle $o\in O$ where $O$ is the set of the obstacles.
• The term $\text{ReLU}(s_{{o}} - \left\|p_t-p_{{o}}\right\|)$ introduces a positive penalty when the pusher is within the obstacle ${o}$ (i.e., when $s_{{o}} > \left\|p_t-p_{{o}}\right\|$).
• Similarly, the second $\text{ReLU}$ term, $\text{ReLU}(s_{{o}} - \left\|x_t-p_{{o}}\right\|)$, penalizes distances between the keypoints and the obstacle ${o}$, calculated for each keypoint individually ($\left\|x_t-p_{{o}}\right\|$ is computed keypoint-wise).
• $\lambda$ is a constant value that penalizes collisions.

Performance change with varying input discontinuities: We conducted a follow-up experiment by removing the obstacles (non-feasible regions) in the problem, simplifying the objective function. Below, we report the performance of different methods on the simplified objective function (w/o obstacles) and the original objective function (w/ obstacles).

The results show that in simple cases, although our BaB-ND consistently outperforms baselines, MPPI and CEM provide competitive performance. In contrast, in cases with constraints and discontinuities, BaB-ND significantly outperforms the baselines, demonstrating its effectiveness in handling these complex cases.

We hope that we have addressed your follow-up questions and we greatly appreciate your feedback. Please let us know if you have any additional concerns.

Thank you for acknowledging our well-structured writing, well-defined formulation, and the extensive experiments we have conducted. We greatly appreciate your thoughtful comments and constructive suggestions. In response, we have clarified the novelty and distinctions of our BaB-ND compared to neural network verification techniques and provided additional details regarding our real-world experiments in the revised paper. Furthermore, we have included a new real-world experiment demonstrating the application of our BaB-ND in dynamic scenarios.

The specific novelty and distinctions of the proposed method compared to neural network verifiers are unclear, beyond its focus on model-based trajectory planning.

We have revised our paper to include a discussion of the distinctions between our BaB-ND and existing neural network verification algorithms in the method section and appendix, summarized as follows:

1. Goals: BaB-ND aims to optimize an objective function involving neural dynamics models to solve challenging planning problems, seeking a concrete solution $\tilde{\boldsymbol{u}}$ (a near-optimal action sequence) in space $\mathcal{C}$ to an objective-function minimization problem $\min_{{\boldsymbol{u}} \in \mathcal{C}}{f({\boldsymbol{u}})}$. In contrast, neural network verification focuses on proving a sound lower bound of $f({\boldsymbol{u}})$ in the space $\mathcal{C}$, and a concrete solution $\tilde{\boldsymbol{u}}$ is not needed. These fundamental distinctions in goals lead to different algorithm design choices.

2. Branching Techniques: In BaB-ND, branching techniques are designed to effectively guide the search for better concrete solutions, considering both the lower and upper bounds of the best objective. In neural network verification, branching techniques focus solely on improving the lower bounds.

3. Bounding Approaches: While existing bounding approaches, such as CROWN from neural network verification, can provide provable lower bounds for objectives, they are neither effective nor efficient for planning problems. To address this, we adapt the CROWN algorithm with propagation early-stop and search-integrated bounding to efficiently obtain tight bound estimations.

4. Searching Components: BaB-ND introduces a searching component within the branch-and-bound procedure to identify optimal solutions for planning problems. This component not only benefits from the BaB framework but also guides it to enhance the search process. In contrast, neural network verifiers typically lack the searching component [1, 2], as their primary focus is on obtaining lower bounds for the objective rather than determining objective values for specific inputs.

[1] S. Wang et al., ‘Efficient bound propagation with per-neuron split constraints for complete and incomplete neural network verification’, NeurIPS, 2021.
[2] H. Zhang et al., ‘General Cutting Planes for Bound-Propagation-Based Neural Network Verification’, NeurIPS, 2022.

The robot experiments lack clarity, with important details omitted.

We answer your specific questions regarding the details of robot experiments as below. And we provide a more detailed description in our revised Appendix D.4.

What are the definitions of open-loop and closed-loop performance? They are unclear, making the results in Figure 5 difficult to interpret.

The key difference between open-loop and closed-loop is whether feedback from the environment is used.

In the open-loop experiment, the trajectory is planned solely based on the initial and goal states, without incorporating any feedback from the environment during execution. Performance is evaluated by summing the planned costs over all steps.

In the closed-loop experiment, feedback from the environment is continuously integrated by the controller to adjust its current plan, effectively compensating for discrepancies between model predictions and reality. Performance is assessed based on the final cost to the target.

Our results demonstrate that, with our effective BaB planning framework, we achieve noticeably better performance in both open-loop and closed-loop settings.

The learned dynamics function relies on a well-designed simulator, which may limit the scalability of this method to a wide variety of tasks.

Learning neural dynamics models for planning is an emerging technique, and we acknowledge the challenges of building effective models for diverse scenarios. Prior work ([3-5] and others discussed in the related work section) has explored various types of neural dynamics models to address limitations in their design and learning. Some of these models are trained using well-designed simulators, but when such simulators are unavailable, many are trained directly through real-world interactions [6].

That said, addressing these challenges is not the focus of our work. Instead, our paper emphasizes effective planning using pre-trained neural dynamics models for robotic manipulation tasks. Our method is compatible with MLPs and GNNs, which are widely used in prior work [3-6], and can be seamlessly integrated with advancements in training methods for these models, further broadening their potential applications.

[3] A. Nagabandi et al., ‘Deep dynamics models for learning dexterous manipulation’, CoRL, 2020.
[4] X. Lin et al., ‘Learning Visible Connectivity Dynamics for Cloth Smoothing’, CoRL, 2021.
[5] Z. Liu et al., ‘Model-Based Control with Sparse Neural Dynamics’, NeurIPS, 2023.
[6] H. Shi et al., ‘RoboCook: Long-Horizon Elasto-Plastic Object Manipulation with Diverse Tools’, CoRL, 2023.

The method assumes static initial poses for obstacles and goal regions, making it challenging to adapt to dynamic changes. … Is it possible to extend the current method to scenarios where obstacles or goal regions are dynamic?

We conducted an additional experiment on varied conditions, like the configuration of the target or obstacles may change during the execution. Please refer to the anonymous video links: Demo video for adding a new obstacle and Demo video for changing target state. The results show that our BaB-ND can effectively provide new long-horizon action sequences to reach the target when the environment changes.

It appears that much of the processing time is consumed by searching. It will dramatically increase computation time and workload when the action space includes both 3D translations and 3D rotations. Would this limit scalability to a full 3D action space?

Our method exactly targets providing a significantly more scalable alternative to popular existing sampling/searching-based methods (e.g., MPPI and CEM). As you noted, existing sampling-based methods face scalability challenges with large input dimensions (e.g., long-horizon action sequences in 3D space) because they search for solutions across the entire input space, requiring an exponentially increasing number of samples to achieve sufficient coverage. In contrast, our BaB-ND strategically splits and prunes unpromising regions of the input space, guiding and improving the effectiveness of existing sampling-based methods. Our experiments (Figure 6(b) in the paper) demonstrated that our BaB-ND produces noticeably better results and scales more effectively to larger input dimensions compared to existing sampling/searching-based methods.

We have attempted to address all your questions and made the corresponding changes to the paper. We believe the paper is now much stronger thanks to your suggestions. Please let us know if you have any additional concerns.

For data collection to train the dynamics function, thousands of episodes are gathered in the simulator. How is action sampling handled for each task? Are actions randomly generated? Is there a sim-to-real gap? Why not train an RL agent in the simulator instead?

During data collection, we randomly initialize the object's state and the end effector's position. Actions are then randomly sampled to encourage interactions between the end effector and the object, ensuring sufficient coverage of scene variations that the neural dynamics model may encounter during testing.

Yes, there can be a sim-to-real gap. To address this, we use a closed-loop planning framework for real-world deployment that incorporates feedback from the environment. This approach effectively compensates for model errors and enables success across a diverse set of challenging manipulation tasks.

While it is possible to train an RL agent in the simulator, that is not the focus of our work. This paper addresses the trajectory optimization problem involving a pre-trained dynamics model. Our key contribution is demonstrating how to effectively perform planning with learned dynamics models, rather than training improved RL agents. The study on effective neural dynamics model training is an important future work for the robot learning community.

What is the action space or control signal for most tasks? It appears to be limited to translations in the 2D plane.

We have both 2D and 3D tasks. For the Pushing with Obstacles and Object Merging tasks, the action space is the movement of the pusher in the xy-plane, with a movement limit of [-3, 3] cm along each axis per step. For the Object Sorting task, the action space includes the position of the pusher and its movement. The pusher's position must be within the 2D workspace, and its movement is limited to [-20, 20] cm in the xy-plane. For the Rope Routing task, the action space is the movement of the gripper in 3D space, with the same movement limit of [-3, 3] cm along each axis.

We agree that incorporating more complex 3D tasks could further enhance the significance of this work. As part of future extensions, we plan to apply our framework to tasks from [3, 4], such as dexterous and cloth manipulation. We are confident in the potential results, as these tasks typically rely on CEM/MPPI for planning, and we have demonstrated that our method consistently outperforms CEM/MPPI in both efficiency and performance.

[3] A. Nagabandi et al., ‘Deep dynamics models for learning dexterous manipulation’, CoRL, 2020.
[4] X. Lin et al., ‘Learning Visible Connectivity Dynamics for Cloth Smoothing’, CoRL, 2021.

With a 20-step planning horizon, how many actions does the controller execute? What is the planner’s operating frequency?

In the closed-loop planning, the controller executes around 140 actions for a 20-step planning horizon. This is because we use a smaller action bound during execution to provide more precise control. The planner operates at a frequency of about 4 fps. We have included more details about our real-world experiment setting in Appendix D.4.

The limitations and potential future directions of this work are not discussed.

We included additional discussions on the limitations and potential future directions in our revised version in Appendix A.4.

We acknowledge that although our branch and bound procedure can help systematically explore the input space and efficiently guide searching, its planning performance can be limited by the underlying sampling-based searching algorithms. Developing and integrating stronger searching algorithms into our BaB-ND can extend its capability on more challenging planning problems. Adaptively adjusting the branching heuristics and bounding estimation can also further improve the convergence on more general cases.

Dear Reviewer,

Please provide feedback to the authors before the end of the discussion period, and in case of additional concerns, give them a chance to respond.

Timeline: As a reminder, the review timeline is as follows:

November 26: Last day for reviewers to ask questions to authors.

November 27: Last day for authors to respond to reviewers.

Thank you for your feedback. We greatly appreciate your follow-up questions and the opportunity to provide further clarification on our work. We have revised our paper (Appendix D.1) to include a detailed description of input and observation spaces, and also expanded the limitations section based on your suggestion.

For the rope task, could you clarify if the action space includes 3 degrees of freedom (DoF)? Were there any tasks that required incorporating a rotation action?

In our Rope Routing task, the action space consists of 3 DOF, defined as the movement of the robot gripper in 3D space along the xyz axes $(\Delta x, \Delta y, \Delta z)$. We additionally provide a visualization of the action definitions for all tasks to illustrate the action space, please check out to visualization (d) for details.

In our Object Sorting task, the orientation of the pusher rotates around the gravity direction, determined by the starting and ending locations of the pusher (i.e., the pusher is always perpendicular to the pushing direction $(\Delta x, \Delta y)$ in visualization $c$).

We have updated Appendix D.1 to include more details about the definition of actions in our tasks, and will include the visualization in our future revision.

Regarding the dynamic model training in simulation, what does the current observation space include?

We follow a general design principle of using 3D points as the state representation for training the dynamics models across all tasks, as 3D points can capture both geometric and semantic information and are easy to transfer between simulation and the real world. Specifically:

• For the tasks Pushing with Obstacles and Object Merging, we assign keypoints on objects to capture the geometric information of the objects (e.g., 4 keypoints for a 'T'-shaped object and 3 keypoints for an 'L'-shaped object).
• For the task Object Sorting, we consider an object-centric representation by using the center point of all objects as the state and model their interactions as a graph using graph neural networks.
• For the task Rope Routing, we sample multiple keypoints (e.g., 10) along the rope as the state to better represent its geometric configuration.

We have updated Appendix D.1 and Figure A12 to include a visualization and more details about the definition of the observation spaces in our tasks.

I appreciate the discussion on limitations and future direction. However, expanding on specific content and including more corner cases would strengthen the section.

Thank you for your suggestions. We have expanded our discussion on limitations and future directions with specific examples and corner cases:

1. Planning performance depends on the prediction errors of neural dynamics models.

   The neural dynamics model may not perfectly match the real world. As a result, our optimization framework, BaB-ND, may achieve a good objective as predicted by the learned dynamics model but still miss the target (e.g., the model predicts that a certain action reaches the target, but in reality, the pushing action overshoots). While improving model accuracy is not the primary focus of this paper, future research could explore more robust formulations that account for potential errors in neural dynamics models to improve overall performance and reliability.

2. Optimality of our solution may be influenced by the underlying searching algorithms.

   The planning performance of BaB-ND is inherently influenced by the underlying sampling-based searching algorithms (e.g., sampling-based methods may over-exploit or over-explore the objective landscape, resulting in suboptimal solutions in certain domains). Although our branch-and-bound procedure can mitigate this issue by systematically exploring the input space and efficiently guiding the search, incorporating advanced sampling-based searching algorithms with proper parameter scheduling into BaB-ND could improve its ability to tackle more challenging planning problems.

3. Improved branching heuristics and strategies are needed for more efficiently guiding the search for more challenging settings.

   There is still room for improving the branching heuristics and bounding strategies to generalize across diverse tasks (e.g., our current strategy may not always find the optimal axis to branch). Future efforts could focus on developing more advanced branching strategies for challenging applications, potentially leveraging reinforcement learning based approaches.

We hope that we have addressed your follow-up questions and we greatly appreciate your feedback. Please let us know if you have any additional concerns.

Dear Reviewer U2wt,

Thank you again for the opportunity to provide further clarification on our work. We have addressed your follow-up questions in detail and revised the paper accordingly. The changes, especially the new visualization, further strengthened its clarity.

As tomorrow is the final day for receiving feedback from you, we would greatly appreciate any additional comments you may have and kindly hope you might reconsider the score.

Best Regards,
The Authors

Thank you for acknowledging our novel contributions in adapting branch-and-bound (BaB) for neural dynamics (ND) models and its potential to set a new direction in combining ML verification methods with motion planning. We greatly appreciate your thoughtful comments and constructive suggestions, and we have conducted additional experiments as you suggested:

1. Performance comparison with conventional motion planning approaches;
2. Hyperparameter analysis for our BaB-ND;
3. Search space analysis for our BaB-ND;
4. Runtime analysis for our BaB-ND and sampling-based methods;
5. Planning performance comparison under a longer time limit.

Task Diversity

We would like to emphasize that we have already included a diverse set of tasks, encompassing rigid bodies and deformable objects, single objects and object piles, 2D and 3D actions, non-convex feasible regions, and long action sequences. Additionally, we have demonstrated the framework's applicability to both MLP- and GNN-based neural dynamics models.

The tasks included in this paper are significantly more challenging than those in prior work using MIP for planning [1]:

• The Object Pushing task in [1] only considered 1-step planning. Our Pushing with Obstacles task introduces additional obstacles with diverse configurations, making it considerably more challenging and requiring a much longer planning horizon.
• The Rope Manipulation task in [1] is limited to 2D planar actions and short-horizon planning. In comparison, we extend this task to a 3D scenario where the rope must be routed into a tight-fitting slot, necessitating long-horizon planning.

We agree that incorporating more complex 3D tasks could further enhance the significance of this work. As part of future extensions, we plan to apply our framework to tasks from [2, 3], such as dexterous and cloth manipulation. We are confident in the potential results, as these tasks typically rely on CEM/MPPI for planning, and we have demonstrated that our method consistently outperforms CEM/MPPI in both efficiency and performance.

[1] Z. Liu et al., ‘Model-Based Control with Sparse Neural Dynamics’, NeurIPS, 2023.
[2] A. Nagabandi et al., ‘Deep dynamics models for learning dexterous manipulation’, CoRL, 2020.
[3] X. Lin et al., ‘Learning Visible Connectivity Dynamics for Cloth Smoothing’, CoRL, 2021.

Scalability (potential bottlenecks, real-time use) and potential modifications for real-time application

Potential bottlenecks: We have provided a detailed analysis of the runtime for each component (branching, bounding, and searching) across planning problems of varying sizes (Figure 7(b) in the paper). The results indicate that branching and bounding add only marginal overhead, particularly for larger problems, as both branching and bounding can be parallelized and benefit significantly from GPU acceleration.

The primary bottleneck remains the searching process, which is similar to the sampling-based planning methods such as CEM and MPPI. In practice, if a sufficiently good solution can be identified, the runtime of the search process can be reduced by decreasing the number of samples or iterations during sampling.

Time-sensitive scenarios: For real-world deployment on robots, planning only needs to be performed once at the start, typically taking 1 minute. During execution, a real-time low-level planner is employed to track the original plan. Consequently, our proposed approach does not pose a bottleneck for real-time manipulation.

If we want to further improve the efficiency of the algorithm, we could explore warm-starting future BaB-ND launches by reusing the branch-and-bound tree from previous solutions wherever possible. Additional strategies include minimizing redundant initialization overhead across multiple launches or splitting multiple dimensions simultaneously during branching.

Dear Reviewer,

Please provide feedback to the authors before the end of the discussion period, and in case of additional concerns, give them a chance to respond.

Timeline: As a reminder, the review timeline is as follows:

November 26: Last day for reviewers to ask questions to authors.

November 27: Last day for authors to respond to reviewers.

Dear Reviewer ci99,

We have provided detailed responses to all your questions and revised our paper accordingly. We believe the paper is now much stronger, thanks to your constructive feedback and suggestions. As the paper revision deadline is less than a day away, we would appreciate it if you could kindly review our response and let us know if you have any additional questions. Thank you!

Best Regards,
The Authors

Practical considerations on selecting and training neural dynamics models

Thank you for raising the concerns and these are important considerations. Learning neural dynamics models is a rising technique, and we acknowledge the challenges in building effective models for different scenarios. Prior work ([1-3] and many other works discussed in the related work section) has explored various types of neural dynamics models to address limitations in their design and learning. However, addressing these challenges is not the focus of our work. Instead, our paper focuses on effective planning using pre-trained neural dynamics models for robotic manipulation tasks. Our method is compatible with MLPs and GNNs which are widely used in prior work [1,3] and can be integrated with advancements in training methods for these models, further enhancing their potential applications.

In practice, the model doesn’t have to be perfect. We apply closed-loop feedback control to compensate for the prediction error — we will constantly obtain feedback from the environment and replan to correct deviations from the original plan.

Estimated effort to obtain the neural dynamics models: Below, we provide a breakdown of the time required for data collection, model training, and long-horizon planning across different tasks:

Our framework is reasonably efficient: for most tasks shown in the paper, data collection (performed in simulation) takes less than 10 minutes, and model training requires approximately 20 minutes. The exception is the Rope Routing task, where data collection takes longer due to simulator inefficiencies. However, this can be addressed using faster simulators in the future.

It is also important to note that data collection is performed offline and only once. As a result, it introduces minimal overhead for the practical deployment of our framework.

Given that most experiments are based in 2D, what modifications would be necessary to extend the framework to more complex 3D tasks or interactions with deformable objects? Is the focus on 2D a practical choice, or does it reflect inherent limitations in handling higher-dimensional complexity?

No specific modifications are necessary to extend the framework to more complex 3D tasks or interactions with deformable objects. For example, the planning formulation for the Rope Routing task, which involves interacting with a deformable rope in 3D space, is identical to that of the 2D tasks. BaB-ND is designed to solve planning problems involving neural dynamics without relying on task-specific prior knowledge.

The focus on 2D tasks in many of the evaluations reflects practical considerations rather than limitations. Specifically, (1) these tasks effectively demonstrate the performance of BaB-ND compared to baseline methods, and (2) the 2D tasks are non-trivial, involving challenges such as object piles, non-convex feasible regions, and long action sequences. For instance, the Pushing with Obstacles task, to the best of our knowledge, has not been addressed in prior works. Even the original version of this task introduced in [4] only considered scenarios without obstacles and with a fixed target pose.

[4] C. Chi et al., ‘Diffusion Policy: Visuomotor Policy Learning via Action Diffusion’, RSS, 2023.

How might the framework perform in a wider range of challenging scenarios? Additional experiments with more varied conditions would offer insight into its adaptability to complex tasks or novel object interactions.

Thank you for the suggestion. We conducted additional experiments on varied conditions like the configuration of the target or obstacles may change during the execution. Please refer to the anonymous video links: Demo video for adding a new obstacle and Demo video for changing target state. The results show that our BaB-ND can effectively provide new action sequences to reach the target when the environment changes.

We have attempted to address all your questions and made the corresponding changes to the paper. We believe the paper is now much stronger thanks to your suggestions. Please let us know if you have any additional concerns, and we hope you can reevaluate our paper based on our response.

Thank you for acknowledging our novel contributions in adapting branch-and-bound (BaB) for neural dynamics (ND) models and its potential to handle extended planning horizons and complex models. We greatly appreciate your thoughtful comments and constructive suggestions, and we have included additional experiments as suggested:

1. Broader baselines from other methodologies, specifically more conventional motion planning approaches.
2. Evaluating our BaB-ND under dynamic scenarios.

We would also like to note the concern regarding the challenges in training neural dynamics models. However, we would like to clarify that this has been extensively studied in the robot learning community (as discussed in our related work section) but is not the focus of our paper. Instead, our work aims to address motion planning problems involving neural dynamics models.

The code URL provided in the paper is currently unavailable.

The code URL (https://anonymous.4open.science/r/BaB-ND-68C3) works on our end. Could you please try accessing it again with a different network connection?

Figure 6 has an ambiguous y-axis, making it difficult to understand what is being measured and, therefore, hard to assess the framework’s actual performance or effectiveness based on this chart.

We report the final cost for all experiments except rope routing. For Rope Routing, we find that relying solely on the final step cost is insufficient to evaluate trajectory success. A greedy trajectory that horizontally routes the rope might achieve a low final cost but fail to guide the rope into the slot. Therefore, we report the success rate for this task. We have clearly clarified this inconsistency in our revised paper.

Task diversity and scalability to more complex scenarios

We would like to emphasize that we have already included a diverse set of tasks, encompassing rigid bodies and deformable objects, single objects and object piles, 2D and 3D actions, non-convex feasible regions, and long action sequences. Additionally, we have demonstrated the framework's applicability to both MLP- and GNN-based neural dynamics models.

The tasks included in this paper are significantly more challenging than those in prior work using MIP for planning [1]:

• The Object Pushing task in [1] only considered 1-step planning. Our Pushing with Obstacles task introduces additional obstacles with diverse configurations, making it considerably more challenging and requiring a much longer planning horizon.
• The Rope Manipulation task in [1] is limited to 2D planar actions and short-horizon planning. In comparison, we extend this task to a 3D scenario where the rope must be routed into a tight-fitting slot, necessitating long-horizon planning.

We agree that incorporating more complex 3D tasks could further enhance the significance of this work. As part of future extensions, we plan to apply our framework to tasks from [2, 3], such as dexterous and cloth manipulation. We are confident in the potential results, as these tasks typically rely on CEM/MPPI for planning, and we have demonstrated that our method consistently outperforms CEM/MPPI in both efficiency and performance.

[1] Z. Liu et al., ‘Model-Based Control with Sparse Neural Dynamics’, NeurIPS, 2023.
[2] A. Nagabandi et al., ‘Deep dynamics models for learning dexterous manipulation’, CoRL, 2020.
[3] X. Lin et al., ‘Learning Visible Connectivity Dynamics for Cloth Smoothing’, CoRL, 2021.

Comparison with broader baselines from other methodologies

For baselines from other methodologies, we identified the following two approaches from more conventional motion planning community (as has also been suggested by reviewer ci99).

1. Rapidly-exploring Random Tree (RRT)
2. Probabilistic Roadmap (PRM)

We conducted additional experiments on task Pushing with Obstacle to compare the planning performance of our BaB-ND method against RRT and PRM. We also include the performance of the original baselines (i.e., GD, MPPI, and CEM) as a reference. The table below presents the final step cost at a planning horizon of $H$:

The results demonstrate that our method significantly outperforms all other approaches. Implementation details for RRT and PRM have been included in Appendix D. The main reasons for the performance gap are as follows:

1. The search space in our task is complex and continuous, making it challenging for discrete sampling methods like RRT and PRM to achieve effective coverage.
2. These methods are prone to getting stuck on obstacles, often failing to reach the target state.

Dear Reviewer,

Please provide feedback to the authors before the end of the discussion period, and in case of additional concerns, give them a chance to respond.

Timeline: As a reminder, the review timeline is as follows:

November 26: Last day for reviewers to ask questions to authors.

November 27: Last day for authors to respond to reviewers.

Dear Reviewer bbRD,

We have provided detailed responses to all your questions and revised our paper accordingly. We believe the paper is now much stronger, thanks to your constructive feedback and suggestions. As the paper revision deadline is less than a day away, we would appreciate it if you could kindly review our response and let us know if you have any additional questions. Thank you!

Best Regards,
The Authors

Thank you for your feedback. We greatly appreciate your follow-up questions and the opportunity to provide further clarification on our work. Specifically, we discussed the challenges in the field of neural dynamic models and added new experiments to show our scalability potential.

Regarding task generality versus customization, while the breakdown of task-specific data collection and training time is helpful, it does not fully address the concern about the framework's adaptability to diverse, real-world applications without significant manual tuning. There is insufficient discussion on how the framework could handle more complex scenarios or larger-scale tasks with minimal reliance on expert intervention.

We acknowledge that manual tuning or expert intervention can pose challenges for the framework in more complex scenarios or larger-scale tasks. While neural dynamics modeling is a promising technique for robotic manipulation, there remain many open research questions to address, such as (1) generating large-scale, high-quality data, (2) generalizing model design/learning across diverse scenarios, and (3) effectively leveraging these models for downstream applications.

Our work focuses on the last question by providing a stronger planner that is broadly applicable to various neural dynamics models. While we cannot solve all these challenges in a single paper, we believe our contributions represent meaningful progress in this direction and lay the groundwork for future exploration of generalizable, large-scale solutions.

Although feedback control is mentioned as a way to mitigate errors, there is a lack of concrete evidence or analysis on how design mismatches could impact performance or how such dependency could be reduced in practice.

Thank you for raising the issue of design mismatches again. We acknowledge that there are many challenges associated with learning of neural dynamics models, and design mismatches are indeed one of them (e.g., MLPs can struggle with handling multi-object interactions). However, it is not the primary focus of our contributions since we study better utilization of pre-trained models instead of learning of better models.

That said, we have made a good effort to reduce the mismatch issue in practice. We design our neural dynamics models for different tasks based on prior works in this area and further narrow the sim-to-real gap by fine-tuning the models with additional data collected from the real world.

Additionally, on scalability to 3D tasks, while it is stated that no specific modifications are necessary, the theoretical discussion does not address the potential challenges in higher-dimensional settings, such as increased search space complexity or computational demands, especially with deformable objects or non-convex feasible regions. It would be helpful to see a more detailed analysis of how the framework manages such challenges and whether strategies like pruning or bound propagation improvements are specifically designed to address the added difficulty in 3D scenarios. For example, what are the expected impacts on computational costs and solution times when moving from 2D to 3D? These clarifications would provide a stronger foundation for understanding the framework's scalability and robustness.

Thank you for your question regarding the scalability of our BaB-ND in complex manipulation tasks. To provide a stronger foundation for understanding the scalability and robustness of BaB-ND, we conducted additional experiments. These include a synthetic example that scales to hundreds of dimensions and further analysis of the search space in the Rope Routing task, which involves both 3D action and a deformable object.