BaB-ND: Long-Horizon Motion Planning with Branch-and-Bound and Neural Dynamics
Authors: Keyi Shen
Jiangwei Yu
Jose Barreiros
Huan Zhang
Yunzhu Li
Venue: ICLR 2025 Poster (2025)
Keywords: Robotic Manipulation
Model-Based Planning
Neural Dynamics
Branch-and-Bound Method
Primary area: applications to robotics, autonomy, planning

Abstract: Neural-network-based dynamics models learned from observational data have shown strong predictive capabilities for scene dynamics in robotic manipulation tasks. However, their inherent non-linearity presents significant challenges for effective planning. Current planning methods, often dependent on extensive sampling or local gradient descent, struggle with long-horizon motion planning tasks involving complex contact events.
In this paper, we present a GPU-accelerated branch-and-bound (BaB) framework for motion planning in manipulation tasks that require trajectory optimization over neural dynamics models. Our approach employs a specialized branching heuristic to divide the search space into sub-domains and applies a modified bound propagation method, inspired by the state-of-the-art neural network verifier $\alpha,\beta$-CROWN, to efficiently estimate objective bounds within these sub-domains. The branching process guides planning effectively, while the bounding process strategically reduces the search space.
Our framework achieves superior planning performance, generating high-quality state-action trajectories and surpassing existing methods in challenging, contact-rich manipulation tasks such as non-prehensile planar pushing with obstacles, object sorting, and rope routing in both simulated and real-world settings. Furthermore, our framework supports various neural network architectures, ranging from simple multilayer perceptrons to advanced graph neural dynamics models, and scales efficiently with different model sizes.

Published as a conference paper at ICLR 2025
BAB-ND: LONG-HORIZON MOTION PLANNING WITH BRANCH-AND-BOUND AND NEURAL DYNAMICS
Keyi Shen ', JJinnwei Yu Jose Barreiros?, Huan Zhang', Yunzhu Li
University of Illinois Urbana-Champaign Toyota Research Institute 3Columbia University (keyis2, 3y79/0illinole edu, jose www.rriirosttt..igio.. huanShuan saaauuaannzhanggaa com, yunzhu. li@columbia. edu
ABSTRACT
Neural-netoork dynamics models learned from observational data have shown strong predictive capabilities for scene dynamics in robotic manipulation tasks. However, their inherent non-linearity presents significant challenges for effec- tive planning. Current planning methods, often dependent on extensive sampling or local gradient descent, struggle with long-horizon motion planning tasks involving complex contact events. In this paper, we present a GPU-accelerated branch-an bound (BaB) framework for motion planning in manipulation tasks that require trajectory optimization over neural dynamics models. Our approach employs a specialized branching heuristics to divide the search space into subdomains, and applies a modified bound propagation method, inspired by the state-of-the-art neu- ral network verifier a, C.8-CR efficiently estimate objective bounds within these subdomains. The branching process guides planning effectively, while the bounding process strategically reduces the search space. Our framework achieves superior planning performance, generating high-qualigg state-action trajectories and surpassing existing methods challenging, contact-rich manipulation tasks such non-prehensile planar pushing with obstacles, object sorting, and rope routing in both simulated and real-world settings. Furthermore, our framework supports various neural network architectures, ranging from simple multilayer perceptrons to advanced graph neural dynamics models, and scales efficiently with different model sizes. Project page: https:/ /ttps::/robopiil wit.ll..ttgobog... lo obbab-nd/
INTRODUCTION
Learning- -based predictive models using neural networks reduce the need for full-state estimation and have proven effective across a variety of robotics-related planning tasks in both simulations (Li et al. Hafner et al.) 22199;; Schrittwieser al.) 2020 Seo et al. (023) and real-world settings (Lenz
2018
ct al.
2013
Finn & Levine 2017; Tian et al. 2219) Lee et al. 2020; Manuelli et al. 2020 Nagabandi
al.
2020 Lin al. 2021 Huang al. 2022 Driess al.
2023 Wu et al. 2023 Shi et al. 2023).
While neural dynamics models can effectively predict scene evolution under varying intiill conditions and input actions, their inherent non-linearity presents challenges for traditional model-based planning algorithms, particularly in long-horizon scenarios.
To address these challenges, the community has developed range of approaches. Sampling- baaed methods such as the Cross-Entropy Method (CEM) (Rubinstein & Kroese|[01]] and Model Predictive Path Integral (MPPI) ( (Williams et al. 2017) have gained popularity in manipulation tasks (Lowryy et al. 2018 Manuelli et al. 20200] Nagabandi et al. 2020: Wang et al. 2023) due to their flexibility. compatibility with neural dynamics models, and strong GPU support. However, their performance in more complex. higher-dingg digeee-dimensional planning problems is limited and requires further theoretical analysis (Yi et al. (0044). Alternatively, more principled optimization approaches, such as Mixed- Integer Programming (MIP), have been applied to planning problems using sparsified neural dynamics models with ReLU activations (Liu et al. 2023b). Despite achieving global optimality and better closed-loop control performance, MIP is inefficient and struggles to scale to large neural networks, limiting its ability to handle larger-scale planning problems.
In this work, we introduce branch-and-bound (BaB) based framework that achieves stronger performance on complex planning problems than sampling- based methods, while also scaling to
"Equal contribution.

---

Published as a conference paper at ICLR 2025
Observation
State, Action
Neural Dynamics
World
Planner
Action
New State
Better
Branch Bound
Pushing w/ Obstacles
Object Merging
Planner
Split
Queued
Pruned
Split
Queued
Rope Routing
Object Sorting
(a) Planning with BaB-ND
(b) Benchmark tasks
Figure 1: Framework overview. (a) Our framework takes scene observations and applies a branch-and- bound (BaB) method to generate robot trajectories using the neural dynamies model (ND). The BaB-ND planner constructs search tree by branching the problem into sub-domains and then systematically searching only promising sub-domains by evaluating nodes with a bounding procedure. (b) BaB-ND demonstrates superior long-horizon planning performance compared to existing sampling- closed-loop control in the real-wor world scenarios. We evaluate our framework various complex planning tasks, including non non-pree prehensile planar pushing with obstacles, object merging, rope routing, and object sorting.
methods and achieves better
large neural dynamics models that are intractable for MIP-based approaches, Our framework is inspired by the success of BaB neural network verification (Bunel et al. 2018 2020b Palma et al.
202I), which tackles challenging optimization objectives involving neural networks. State-of- -he-oo-tthearr art
neural network verifiers such as a. e.B-CROWN (Xu et al.] 2021; Wang et al. 2021 Zhang et al. 2022a), utilize BaB alongside bound propagation methods (Zhang al. 2018 Salman et al. 2019).
demonstrating impressive strength and scalability in verification tasks, far surpassing MIP-based approaches (Tjeng et al. 2019: Anderson al., 2020). However, unlike neural network verification, which only requires finding lower bound of the objective, model-based planning demands high- quality feasible solutions (i.c.. planned state-action trajectories). Thus, significant adaptation and specialization are necessary for BaB-based approaches to effectively solve planning problems.
Our framework, BaB-ND (Figure aa), divides the action space into smaller subdomains through novel branching heuristics (branching), estimates objective bounds using modified bound propagation procedure to prune subdomains that cannot yield better solutions (bounding), and focuses searching on the most promising subdomains (searching). We evaluate our approach on contact-rich manipulation tasks that require long-horizon planning with non-smooth objectives, non-convex feasible regions (with obstacles), long action sequences, and diverse neural dynamics model architectures (Figure b). Our results demonstrate that BaB-ND consistently outperforms existing sampling-basee methods by systematically and strategically exploring the action space, while also being significantly more efficient and scalable than MIP-based approaches by leveraging the inherent structure of neural networks and GPU support.
We make three key contributions: (1) We propose general, widely applicable BaB-based framework for effective long-horizon motion planning neural dynamics models. (2) Our framework intro- duces novel branching, bounding, and searching procedures, inspired by neural network verification algorithms but specifically adapted for planning over neural dynamics models. (3) We demonstrate the effecttivnnsss applicability, and scalability of our framework across range of complex planning problems, including contact-rich manipulation tasks, the handling of deformable objects, and object piles, using diverse model architectures such as multilayer perceptrons and graph neural networks.
2 RELATED WORKS
Neural dynamics model learning in manipulation. Dynamics models, learned from observations in simulation or the real world using deep neural networks (DNNs), have been widely and successfully
2

---

Published as a conference paper at ICLR 2025
applied to robotic manipulation tasks (Shi et al.
2023 Wang al.
2023). Neural dynamics models
can be learned directly from pixel space (Finn et al.
2016]] Ebert et [011 2018 Yen-Chen et al.
2020;
Suh & Tedrake. 2020) or low-dimensional latent space (Watter et al. 2015 Agrawal et al.
2016 Hafner et al. 2019h a Schrittwieser et al. 2020; Wu et al. 2023). Other approaches use more
structured scene representations, such keypoints (Kulkarni et al. 2019: Manuelli al. [200 Li
ct al. 2020). particles (Li et al. 20188] Shi et al., 2022 Zhang et al. (024). and meshes (Huang et al.
2022). Our work employs keypoint or object-centric representations, and the proposed BaB-ND
framework is compatible with various architectures, ranging from multilayer perceptrons (MLPs) to
graph neural networks (GNNs) (Battaglia et al.) 2016 Li et al. 2019))
Model-based planning with neural dynamics models. The highly non-linear and non-convex nature of neural dynamics models hinders the effective optimization of model-based planning problems. Previous works (Yen-Chen al. 2020) Ebert al., 2017; Nagabandi et al., 2020,
Finn & Levine 2017, Manuelli et al. [2000; Sacks et al.] 2023; ; Han et al., (0224) utilize sampling- based algorithms like CEM (Rubinstein & Kroese 2013) and MPPI (Williams et al. 2017) for online planning. Despite their flexibility and ability to leverage GPU support, these methods struggle with large input dimensions due to the exponential growth in the number of required samples. Previous work (Yin et al.) 2022) improved MPPI by introducing dynamics model linearization and covariance control techniques, but their effectiveness when applied to neural dynamics models remains unclear. Other approaches (Li et al.] 2018 2019h have used gradient descent to optimize action sequences but encounter challenges with the local optima and non-smooth objective landscapes. Recently, methods inspired by neural network verification have been developed to achieve safe control and robust planning over systems involving neural networks (Wei & Liu 2022 Liu et al. 20233) Hu et al., 2024a] Wu al. 2024 Hu et al. 2024b), but their scalability to more complex real-world manipulation tasks is still uncertain. Moreover, researchers are also exploring the promising direction of performing planning over graphs of convex sets (GCSs) for contact-rich manipulation tasks Marcucci] (2024);
Graesdal et al. (2024). However, these approaches do not incorporate neural networks.
Neural network verification. Neural network verification ensures the reliability and safety of neural networks (NNs) by formally proving their output properties. This process can be formulated as finding the lower bound of minimization problem involving NNs, with early verifiers utilizing
MIP (Tjeng et al. 2019) or linear programming (LP) (Bunel et al., [0188] [L & Kumar. (2020). These approaches suffer from scalability issues (Salman et al.] 2019 Zhang et al.) [022b] Liu et al. 2 because they have limited parallelization capabilities and fail to fully exploit GPU resources. On
the other hand, bound propagation methods such as CROWN (Zhang et al., (018) can efficiently propagate bounds on NNs (Eric Wong 2018 ( et al. 2019 Wang et | 2018 Gowal et al. 2019)
in layer-by-layer manner, with the ability to be accelerated on GPUs. Combining bound propagation
with BaB leads to successful approaches in NN verification (Bunel et al., 2020a De Palma et al. 2021
Kouvaros & Lomuscio 2021: Ferrari et al., (022), and notably, the a.3-C framework (Xu
et al. 2021 Wang et al. 2021] ZZhag et al. (002a)) achieved strong verification performance on
large NNs (Bak et al. [021 Müller al. (022). In our model-based planning setting, utilize the lower bounds from verification, with modifications and specializations, to guide our systematic
search procedure find high-quality feasible solutions.
3 BRANCH-AND-BONK BOUND FOR PLANNING WITH NEURAL DYNAMICS MODELS
Formulation. We formulate the planning problem as optimization problem in Eq. where c is the cost function, to is the current time step, and H is the planning horizon. &, is the (predicted) state at time step f, and the current state ft. It, is known. Ue {u u S u S x} R is the robot's action at each step. Sayn is the pre-trained neural dynamics model (Please refer to Section DD3 for details about learning the neural dynamics model.), which takes state and action at time / and predicts the next state o The goal of the planning problem is to find a sequence of optimal actions de that minimize the sum of step costs:
H
min (M,E44
Σ clEt, uz) S.t. $e-1= = Sayn ut) Amnta
min f(u). UEC
(1)
This problem can be challenging due to its long planning horizon H, complex cost function c, and the non-linear neural dynamics model fayn with recursive dependencies every step. Existing sampling- based and gradient- based methods may converge to sub-optima without systematic searching, while MIP- methods fail to scale up with the size of sayn and the planning horizon H.
3

---

Published as a conference paper at ICLR 2025
To simplify notation, we can substitute all constraints on 8e+1 into the objective recursively, and further simplity the problem as a constrained optimization problem minuec f(u) (Eq. DT. Here f is our final objective, a scalar function that absorbs the neural network Sayn and the cost function summed in all H steps. u (M + +H) } E C is the action sequence and C C Rd is the entire input space with dimension d = kH. We also flatten u as vector containing actions for all time steps, and use uj denote a specific dimension. Our goal is to then find the optimal objective value f and its corresponding optimal action sequence u..
Branch-and-boue on ID toy example. Our work proposes to solve the planning problem Eq. T using branch-and-boud bound. Before diving into tech- nical details, we first provide a toy case of a non- convex objective function f(u) in ID space (k = H 1,C [-1, 11) and illustrate how to use branch-and- bound to find f*
f(u)
fM
2
f(u)
f(4
In Figure 2 I, we visualize the landscape of f(u) with its optimal value f". Initially, we don't It know f but we can sample the function ent locations (orange points). Although sampling (searching) often fails to discover the optimal f" over C = 1], it gives an upper bound of f", since any orange point has an objective greater than or equal to f*. We denote f" as the current best upper bound (orange dotted line).
Go
few differ-
f(u)
f(u)
In Figure 2, we split into two subdomains C₁ and C2 (branching) and then estimate the lower bounds of the objective in C1 and C2 using linear functions (bounding). The key insight is if the lower bound in one subdomain is larger than f then sampling from that subdomain will not yield any better objec- tive than f" and we may discard that subdomain to reduce the search space. In the example, C₁ is discarded in Figure 3.
Figure 2: Seeking f" with Branch-and- Bound. ① Sample on input space C. e: sampled points. * the optimal value f" --: the current hest upper bound of f from sampling. 3 Branch C into Ci and Cz. the linear lower bounds of f in sub- domains. 2 Discard C₁ since its lower bound is larger than : the remaining subdomain be searched. 4 Search on only C2 and upper bound of f" is improved. -..-: the previous upper bound. Continue to branch C2 and bound on C3 and Ca. 6 Search Cs. The upper bound approaches f"
Then, Figure 2 4, we only perform sampling in C2 with the same number of samples. Searching in the reduced space is likely to obtain better objective and therefore f" can be improved.
We could repeat these procedures (branching, bounding, and searching) to reduce the sampling space and improve f as in Figure and Figure Finally, the value of f will converge f*. This branch-and-bour hound method systematically partitions the input space and iteratively improves the objective. In practice, heuristics for branching, along with methods for bound estimation and solution search, are critical to the performance of branch and bound.
Methodology overview. We now discuss how to use the cranch-ande aadl--ndd-buula bound (BaB) method to find high-quality actions for the planning problem formulated min fu) (Eq. Ip. We define
subproblem minuec, f((u) as the task of minimizing f'(u) within a subdomain C. where C, C C. Our algorithm, BaB-ND, involves three components: branching (Figure 3 bb Section 3.1. bounding
(Figure c. Section 3.2). and searching (Figure 3dd Section 3.3
Branching generates partition {C+} of some input space C such that U.C. C, enabling systematic exploration of the input space.
Bounding estimates the lower bound of f(u) on each subdomain C, (denoted as f" The lower bound can be used to prune unpromising domains and also guide the search for promising domains.
Searching seeks good feasible solutions and outputs the best objective Fè, within each subdomain C. Fe, is an upper bound of f*, as any feasible solution provides an upper bound for the optimal minimization objective s*
4

---

Published as a conference paper at ICLR 2025
(a) Configuration
(b) Branching
(c) Bounding
(d) Searching
Target
Better
c
Current
Pusher
Split
&
Action u in 1D
C1
Define (u) dl +.g
f(u)
Prune
Split
C3
CA
Figure 3: Illustration of the branch-and-boue process. (a) Configuration: we visualize simplified case of pushing object toward the target using ID) action u. We select two keypoints on the object and target and denote the distances di and d2. Then define our objective function f(u) and seek u to minimize it. (b) Branching: we iteratively construct the search tree by splitting, queuing, and pruning nodes (subdomains). In every iteration, only the most promising nodes are prioritized for splitting, cooperating with bounding and scarching. (c) Bounding: In every subdomain C,, we obtain the linear lower bound of f (f") via bound
search better solutions with smaller objective (f") ) selected subdomains. indicates the most promising subdomain every iteration. The search space progressively shrinks within the original input domain C with better solutions found and more subdomains pruned. detailed illustration our BaB-ND simplified robotic manipulation task is provided in Section A.1
propagation. (d) Searching:
We can always prune subdomain C, its Le, > Ff where F == min; Fc, is the best upper bound
among all subdomains {C,), since, in Cj. there is no solution better than the current best objective f be repeated many times, and each time during branching, some previously produced subdomains C; can be picked for bounding, and searching, while the remaining subdomains stored in set IP for future branching. Our main algorithm is shown in Algorithm
The above procedure
Distinctions from neural network verification. Although the generic BaB framework has been
applied in neural network verification (Bunel al. 2018 Wang et 2021). its goal is prove sound lower bound of f(u) within C, ensuring that J. < f In contrast, our BaB-ND aims to find a concrete solution ū-a near-optimal action sequence- for the objective-mininizaton problem minuee fuu). These fundamental differences in objectives lead to distinct design choices.
We propose new branching heuristics that effectively guide the search for better solutions, extensively adapt the existing bounding algorithm CROWN (Zhang al., (2018) tackle its ineffectiveness and inefficiency issues under our complex planning setting and integrate new searching component to find quality action sequences.
3.1 BRANCHING HEURISTICS FOR BAB-ND PLANNING
The efficiency of BaB relies heavily on the quality branching. Thus, selecting promising subdo- mains and determining effective ways to split them are two critical aspects of BaB, corresponding to batch pick_out(PP,.. n) and batch batch_split ((C,) in Algorithm | ized branching heuristies designed to select and split subdomains obtain high-quality solutions.
Here, we introduce our special-
Heuristic for selecting subdomains to split. The function batch Beecch_piick__e pick_out(PF n) picks n most promising subdomains for branching, based on their associated f" or Fe,- The pickout process must balance exploitation (focusing on areas around good solutions) and exploration (investigating regions that have not been thoroughly explored). First, we sort subdomains C, by Fc. in ascending order and select the first subdomains to form (Cpitt }. Subdomains with smaller Fü. are prioritized, as good solutions have been found there. Then, form another promising set (Co by sampling n
5

---

Published as a conference paper at ICLR 2025
Algorithm 1 Branch and bound for planning. Comments are in brown.
1: Function: bab_pl palaningnng
2: Inputs: f. C, (batch size), terminate (Termination condition)
3: {(f" ú)} + saatch_search. (f, (C))
Initially search on the whole > Initially bound on the whole
4: {f") bbuacchbbuudd (f,(C))
5: P {(C, ,ú]
b IP is the set of all candidate subdomains
6: while length(P) > 0 and not terminate do
7:
[(C.: JT, ūc,,] <- baatch_pick___ out (P,
P Pick out subdomains to split from Splits each C, into two subdomains CP and C,P D Estimate lower bounds on new subdomains
8:
C,T) batch_splis ({Ci))
9:
Vgg Fap) t batch bound (f,
10:
(leep Tep), (fop) uow)t }} + batch_search (fi (C,, C)
Search new solutions
11:
min (fee.ee)) <f then
12:
Topl) i arg argmin (ITcz. P l'Prunrrr (((h TepTTe)) Foy) 1C,, Sep Toy))
T' - min
D. Update the best solution if needed
13:
Prune bad domains using f
14:
Outputs: F.
subdomains from the remaining N ones, using softmax, with the probability p; defined in Eq. 2
where 7 is the temperature and sattee represents L", after min-max normalization for numerical stability. smaller fo, may indicate potentially better solutions in C,, which should be prioritized:
SSp(-Seesccatel (T)
Σj=1 exp( Le, seatedd
Note that this heuristic was not discussed in the neural network verification literature, which requires verifying all subdomains, making the order of subdomain selection less critical.
Heuristic for splitting subdomains. batch batch_split ({C+)) partitions every C, to help search for good solutions. For a box-constrained subdomain C, == {uy 3 S u, S U,ij O,..., d 1}
(subscript i omitted for brevity), it is natural to split it into two subdomains Cla and C.P along
dimension jL by bisection. Specifically. Che {ug u u S - }. C.P = {ug
4,,+" < uy S (.j)). ). In both C.. and C,P -4, S n S új j holds. 2
One native way to select j" choose the dimension with the largest input range u, uy This efficient strategy can help identify promising solutions since dimensions with larger range often indicate greater variability or uncertainty in However, it does not consider the specific landscape of f. which may indicate dimensions better suited for splitting.
We additionally consider the distribution of top w% samples with the best objectives from searching to partition C, into promising subdomains worth further searching. Specifically, for every dimension
j. we record the number of top samples satisfying u, S U, I _ and _. tu
2 < u, S U as
n/o and nj up respectively. Then, |n]] n. indicates the distribution bias of top samples along dimension j. A dimension with large in .,, is critical to objective values in C, and should be prioritized to split due to the imbalanced samples on two sides. In this case, it is often possible that one of the two subdomains (Cle and ( contains better solutions, whereas the other has a larger lower bound for the objective and can be pruned.
Based on the discussion above, we rank input dimensions descendingly by (u, 22,) |m/ n select the top one j", and then split C, into subdomains evenly on dimension j This heuristic is notably different from those discussed in neural network verification literature (Bunel et al. 2018 2020b), since we aim to find better feasible solutions, not better lower bounds.
3.2 BOUNDING METHOD FOR BAB-ND PLANNING
Our bounding procedure aims to provide a tight lower bound for the objective function f(u) in any subdomain, enabling the pruning of unpromising subdomains and the identification of promising

---

Published as a conference paper at ICLR 2025
ones. While this component is crucial to the effectiveness of BaB, grasping this high-level idea is sufficient to understand our main algorithm.
To guide the search with tight bound estimation, an important insight is that in the planning problem, a strictly sound lower bound is not required, as the lower bound is used to evaluate the quality of subdomains rather than to provide a provable guarantee of fu,) as in neural network verification. Based on this observation, we propose two approaches, propagation early-stop and searching- integrated bounding, to obtain an efficient estimation of the lower bound fe. leveraging popular bound propagation- based algorithms like CROWN (Zhang et al. 2018).
Approach 1: Propagation early-stop. CROWN is bound propagation algorithm that propagates
a linear lower bound (inequality) through the neural network and has been successfully used in BaB-based neural network verifiers for the bounding step (Xu et al. 2021 Wang et al., 202T). In CROWN, the linear bound will be propagated backward from the output (in our case, f( to the input of the network (in our case, u), and be concretized to concrete lower bound value using the constraints on inputs (in our case, C,).
However, this linear bound can become increasingly loose in deeper networks and may result in vacuous lower bounds. In our planning setting with the neural dynamics model faya. the long planning horizon H in Eq. D requires unrolling fayn H times to form fu). leading to excessively loose bounds that are ineffective for pruning unpromising domains during BaB.
To address this challenge, we stop the bound propagation process early to avoid the excessively loose bound when propagated through multiple layers the input u. The linear bound will be concretized using intermediate layer bounds, as discussed in Approach 2, rather than the constraints on the inputs. more formal description of this technique (with technical details on how CROWN is modified) is presented in Appendix B.2 with an illustrative example.
Approach 2: Search-integrated bounding. In CROWN, the propagation process requires re- cursively computing intermediate layer bounds (often referred as pre-activation bounds). These pre-activation bounds represent the lower and upper bounds for any intermediate layer that is followed by nonlinear layer. The time complexity of this process is quadratic with respect the number of layers. Directly applying the original CROWN-like bound propagation is both ineffective and inefficient for long-hore long-horizon planning, as the number of pre-activation bounds increases with the planning horizon. This results in overly loose lower bounds due to the accumulated relaxation errors and high execution times.
To quickly obtain the pre-activation bounds, we can utilize the by-product of extensive sampling during searching to form the empirical bounds instead of recursively using CROWN calculate these bounds. Specifically, we denote the intermediate layer output for layer as (u),, and assume we have M samples ut (m = I,..., M)) from the searching process. We calculate the pre-activation lower and upper bounds min,, (u"")) and max, go(um)) for each dimension of (u)) Although these empirical bounds may underestimate the actual bounds, they are sufficient for CROWN to get good estimation of fo to guide the search.
3.3 SEARCHINN APPROACH FOR BAB-ND PLANNING
Given an objective function f and a batch of subdomains {C,), batch_seeachta (C+)) explores these subdomains to find solutions, returning the best objectives and associated inputs {(fe, uc. }} A large variety of sampling-basee
methods can be utilized and we currently adopt CEM as the underlying method. Other existing methods, such as MPPI or projected gradient descent (PGD), can be alternatives. In typical neural network verification literature, searching is often ignored during BaB (Wang et al., 2 Bunel et al. (020b)) since these approaches do not seek feasible solutions.
To cooperate with the bounding component, we need to additionally record the outputs of needed intermediate layer v, and obtain their bounds as described in Section (.22 Since we require the lower bound of the optimal objective fü, for every C, the outputs of layer must be calculated for every C, using the samples within the subdomain.
Considering that the subdomains {C,} will become progressively smaller, it is expected that sampling- based methods could provide good solutions. Moreover, since we always record fč, and its associated ic. they can initialize future searches on least one of the split subdomains (Clo and C.P) from C..
7

---

Published as a conference paper at ICLR 2025
4 EXPERIMENTAL RESULTS
In this section, we evaluate the performance of our BaB-ND on a range of complex robotic ma- nipulation tasks. Our primary objective is investigate three key questions through experiments: (1) How effectively does BaB-ND handle long-horizon planning? (2) Is BaB-ND applicable to
diverse manipulation scenarios involving multi-object interactions and deformable objects? (3) How does the scalability of BaB-ND compare to existing methods?
Synthetic example. Before deploying our BaB-ND on robotic manipulation tasks, we design synthetic function to evaluate its capability for finding optimal solutions in a highly non-convex problem. We define f(u) = 2: 5um + cos 50u,, u E [_1,, where d is the input dimension. The optimal solution f - 1..9803 and f(u) has local optima with global optima along each dimension. Hence, optimizing fu) can be challenging as d increases.
-50
Objective
-100
Optimaa
GD
-150-
We compare BaB-ND with three baselines: (1) GD: projected Gradient Descent on random samples with hyper- parameter tuning for step size; (2) MPPI: Model Predictive Path Integral with hyper-parameter tuning on noise level and reward temperature; (3) CEM: Decentralized Cross- Entropy Method (Zhang et al., 2022c using an ensemble of independent CEM instances performing local improvements of their sampling distributions.
MPPI
CEM
Ours
25
50
75
100
Input dimension
Figure 4: Optimization result on a syn- thetic f(x over increasing dimensions d. BaB-ND outperforms all baselines in terms of the optimized objective. We all methods multiple times and visualize the median values with 25th and 75th per- centiles in the shaded area.
we visualize the best objective values found by different methods across different input dimensions up to 100. BaB-ND consistently outperforms all baselines which converge to sub-optimal values. For d 100, BaB- ND can achieve optimality on 98 to 100 dimensions. This synthetic experiment demonstrates the potential of BaB-ND in planning problems involving neural dynamics.
In Figure 4
Experiment settings. We evaluate our BaB-ND on four complex robotic manipulation tasks involving non-smooth objectives, non-convex feasible regions, and requiring long action sequences. Different architectures of neural dynamicc like MLP and GNN are leveraged for different scenarios. Please refer to Scction D for more details about tasks, dynamics models, and cost functions.
Pushing with Obstacles. In Figure this task involves using a pusher to manipulate a "T"- shaped object reach target pose while avoiding collisions with obstacles. An MLP neural dynamics model is trained with interactions between the pusher and object without obstacles. Obstacles are modeled in the cost function, resulting in non-smooth landscapes and non-convex feasible regions.
Object Merging, In Figure 5ec, two "L""shaped objects are merged into a rectangle at a specific target pose, which requires long action sequence with multiple contact mode switches.
Rope Routing. As shown in Figure b, the goal is to route a deformable rope into a tight-fitting slot (modeled in the cost function) in the 3D action space. Instead of greedily approaching the target in initial steps, the robot needs to find the trajectory to finally reach the target.
Object Sorting, In Figure pusher interacts with cluster of objects to sort one outlier object out of the central zone to the target while keeping others closely gathered. We use GNN to predict multi-object interactions. Every long-range action may significantly change the state. Additional constraints actions are considered in the cost to avoid crashes between the robot and objects.
We evaluate baselines and BaB-ND on the open-loop planning performance (the best objective of Eq. found) in simulation. Then, we select the best two baselines to evaluate their real-world closed-loop control performance (the final step cost or success rate of executions).
In real-world experiments, we first perform long- horizon planning to generate reference state trajecto- ries and leverage MPC (Camacho & Bordons Alba 2013) to efficiently track the trajectories in two tasks: Pushing with Obstacles and Object Merging. In the Rope Routing task, we directly execute the planned long- horizon action sequence due to its small sim-to-real gap. In the Object Sorting task, since the observations can change greatly after each push, we use MPC to replan after every action.
8

---

Published as a conference paper at ICLR 2025
Time
Time
Target
Inttal
Inibal
Lift and routing
(a) P Pushing w/ Obstacles
(b) R Rope Routing
Time
Target
(c) Object Merging
Time
(d) Object Sorting
Figure 5: Qualitative results real-world manipulation tasks. We evaluate BaB-ND across four complex robotic manipulation tasks, involving non-convex feasible regions, requiring long- horizoo planning, and interactions between multiple objects and the deformable rope. For each task, we visualize the initial and target configurations and one successful trajectory. Please refer to our project page for video demonstrations.
Effectiveness. We first evaluate the effectiveness of BaB-ND Pushing with Obstacles and Object Merging tasks which are contact-rich and require strong annghhorioon planning performance. The quantitative results of open-loop and closed loop performance for these tasks presented in Figure
In both tasks, our BaB-ND effectively optimizes the objective of Eq. and gives better open- loop performance than all baselines. The well- eellnelanned trajectories can yield improved closed-loop performance in the real world with efficient tracking. Specifically, in the Pushing with Obstacles task, GD offers much worse trajectories than others, often resulting in the "sr'-shaped object stuck at one obstacle. MPPI and CEM can offer trajectories passing through the obstacles but with poor alignment
(a) Open-loop
Performance
85
100
65
80
50-
45-
40
35
40
55
25
CEM
100%
(b) Closed-loop Performance
75%
4-
50%
2-
25%
0
MPPI
CEM
Ours
MPPI
CÉM
Ours
MPPI
CEM
Ours
MPPI
CEM
Ours
Pushing w/ Obstacles
Object Merging
Rope Routing
Object Sorting
Sucoess rate (1). Other metrics closed-loop performance are finel costs (1).
Figure 6: Quantitative analysis of planning performance and execution performance in real world. BaB- ND consistently outperforms baselines open-loop performance leading better closed-lood performance. (a) The open-loop performance all tasks in simulation. report the best objective of Eq. I found by all methods across different test cases. (b) The closed-loop performance in real world. GD is excluded from testing due to its poor open-loop performance. We report the success rate for Rope Routing, since greedy trajectory that horizontally routes the rope may achieve low final cost but fails to place it into the slot, and report final step costs for all other tasks.

---

Published as a conference paper at ICLR 2025
with the target. In contrast, BaB-ND can not only pass through obstacles successfully, but also often perfectly align with the final target.
Applicability. We assess the applicability of BaB-ND Rope Routing and Object Sorting tasks involving the manipulation of deformable objects and interactions between multiple objects modeled by GNNs. The quantitative results in Figure demonstrate our applicability to these tasks.
In the Rope Routing task, MPPI, CEM, and our method achieve comparable open-loop performance, while GD may struggle with suboptimal trajectories, often routing the rope horizontally and getting stuck outside the slot. In the Object Sorting task, CEM outperforms MPPI, as MPPI is better suited for planning continuous action sequences, whereas this task involves discrete actions. Our method outperforms CEM, achieving a similar median performance with noticeably lower variance.
(a) Runtime different model sizes and planning horizons
(b) Runtime breakdown
MIP
Ours
0:948
206.0
1:177
8.000K
94.31K
0.708
13500
2440
2.332
3.20
224
14.75
Runlime e (Seconde)
Model Size
Planning Horizon
Blammin Horizon
76.04K
5,909
4515
200
134
239
530
25
Runtime (Seconda)
Branching Other Bourding
0.333K 0.712K 2:40K 34 3IK 134.86 530.KK
250K 0.71KK 3U00XC 34.3K 136.K 530
Searching
Model
Figure 7: Quantitative analysis of runtime and scalability. (a) The runtime of MIP and BaB-ND for solving simple planning problems with varying model sizes and planning horizons. BaB-ND can handle significantly larger problems than MIP. ("Fail" indicates MIP fails to find any solution within 300 seconds.) (b) Runtime breakdown of our components on large and complex planning problems with H = 20. Runtimes for components other than searching increase slightly model size grows, indicating the strong scalability of BaB-NDI
Scalability. We evaluate the scalability of our BaB-ND on Pushing with Obstacles task with varying model sizes and planning horizons on multiple test cases, in comparison to MIP (Liu et al,, 2023b). We train the neural dynamics models with different sizes and the same architecture, and the number of parameters in the single neural dynamics model fayn to indicate the model size. Moreover, accommodate MIP, we remove all obstacle-related components in cost and define the objective as the step cost after planning horizon H, c(fta Ut +HI) instead of the accumulated cost.
In Figure 7 a, we visualize the average runtime of MIP and ours test cases with different model sizes and planning horizons. The results show that MIP only handles small problems. Among all 36 settings, provides optimal solutions for sub-optimal solutions for 3, and fails to find any solution for the remaining within 300 seconds. In contrast, our BaB-ND scales up well to large problems with planning horizon H 20 and model containing over 500K parameters.
In Figure 7, we evaluate the runtime of each primary component of our BaB-ND across various model sizes, ranging from approximately 9K to over 500K, using the original objective for the Pushing with Obstacles tasks (containing items to model obstacles and accumulated cost among all steps) over a planning horizon of H 20. The breakdown bar chart illustrates that the runtimes for the branching and bounding components grow relatively slowly across model sizes, which increase more than 50-fold. Our improved bounding procedure, as discussed Section 3.2 scales well with growing model size. In addition, the searching runtime scales proportionally to neural network size since the majority of searching time is spent on sampling the model with large batch size on GPUs.
CONCLUSION
In this paper, we propose neural dynamics in robotic manipulation tasks. We leverage specialized branching heuristics for systematic search and adapt the bound propagation algorithm from neural network verification to estimate tight objective bounds efficiently and reduce search space. Our framework demonstrates superior planning performance in complex, contact-rich manipulation tasks, well as scalability and adaptability to various model architectures. The limitations and future directions are discussed in Section A.4
aanhh--and-buudd framework for long-horizon motion planning with
10

---

Published as a conference paper at ICLR 2025
6 ACKNOWLEDGMENT
This work is supported by the Toyota Research Institute (TRI). We thank Hongkai Dai, Aykut Onol, and Mengchao Zhang for their constructive suggestions on the paper manuscript. We also thank Mingtong Zhang, Haozhe Chen, Baoyu Li, and Binghao Huang for their help with real-world experiments and simulation environment development. This article reflects solely the opinions and conclusions of its authors, not those of TRI or any other Toyota entity.
REFERENCES
Pulkit Agrawal, Ashvin Nair, Pieter Abbeel, Jitendra Malik, and Sergey Levine. Learning poke by poking: Experiential learning of intuitive physics. arXiv preprint
2016.
Ross Anderson, Joey Huchette, Will Ma, Christian Tjandraatmadja, and Juan Pablo Vielma. Strong mixed-integer programming formulations for trained neural networks. Mathematical Programming. 183(1):3-39, 2020.
Stanley Bak, Changliu Liu, and Taylor Johnson. The second international verification of neural networks competition (ynn-comp 2021): Summary and results. arXiv preprint wrXiv:219.000990 2021.
Peter Battaglia, Razvan Pascanu, Matthew Lai, Danilo Jimenez Rezende, et al. Interaction networks for learning about objects, relations and physics. Advances in neural information processing systems, 29, 2016.
Victor Blomqvist. Pymunk. https://pymunk..oo November 2022.
Rudy Bunel, llker Turkaslan, Philip H. S. Torr, Pushmeet Kohli, and M. Pawan Kumar. A unified view of piecewise linear neural network verification. In Advances in Neural Information Processing Systems (NeurIPS), 2018.
Rudy Bunel, Alessandro De Palma, Alban Desmaison, Krishnamurthy Dvijotham, Pushmeet Kohli, Philip S. Torr, and M. Pawan Kumar. Lagrangian decomposition for neural network verification. Conference on Uncertainty in Artificial Intelligence (UAI), 2020a.
Rudy Bunel, Jingyue Lu, llker Turkaslan, Philip H. S. Torr, Pushmeet Kohli, and M. Pawan Kumar. Branch and bound for piecewise linear neural network verification, 2020b.
Eduardo Camacho and Carlos Bordons Alba. Model Predictive Control. Springer Science & Business Media, 2013.
Alessandro De Palma, Harkirat Singh Behl, Rudy Bunel, Philip H. S. Torr, and M. Pawan Kumar. Scaling the convex barrier with active sets. International Conference on Learning Representations (ICLR), 2021.
Danny Driess, Zhiao Huang, Yunzhu Li, Russ Tedrake, and Marc Toussaint. Learning multi-object dynamics with compositional neural radiance fields. In Conference on robot learning, pp. 1755- 1768. PMLR, 2023.
Frederik Ebert, Chelsea Finn, Alex X Lee, and Sergey Levine. Self-supervised visual planning with temporal skip connections. In CoRL, pp. 344-356, 2017.
Frederik Ebert, Chelsea Finn, Sudeep Dasari, Annie Xie, Alex Lee, and Sergey Levine. Visual foresight: Model-based deep reinforcement learning for dision-based robotic control. arXiv preprint arXiv:1812.005: 005668, 2018.
Zico Kolter Eric Wong. Provable defenses against adversarial examples via the convex outer adversarial polytope. In International Conference Machine Learning (ICML), 2018.
Claudio Ferrari, Mark Niklas Muller, Nikola Jovanovic, and Martin Vechev. Complete verification via multi-neuron relaxation guided mrmnch-nnd-buune arXiv preprint arXiv:2205.00266 2022.
Chelsea Finn and Sergey Levine. Deep visual foresight for planning robot motion. In 2017 IEEE International Conference Robotics and Automation (ICRA), pp. 2786-2793. IEFF, 2017.
11

---

https://ppprrreieeeeeeefoonmnmnd Published as a conference paper at ICLR 2025
Chelsea Finn, Ian Goodfellow, and Sergey Levine. Unsupervised learning for physical interaction through video prediction. arXiv preprint arXiv:1605.07157, 2016.
Sven Gowal, Krishnamurthy Dvijotham, Robert Stanforth, Rudy Bunel, Chongli Qin, Jonathan Uesato, Timothy Mann, and Pushmeet Kohli. On the effectiveness interval bound propagation for training verifiably robust models. Proceedings of the IEEE International Conference Computer Vision (ICCV), 2019.
Bernhard Paus Graesdal, Shao Yuan Chew Chia, Tobia Marcucci, Savva Morozov, Alexandre Amice, Pablo A. Parrilo, and Russ Tedrake. Towards tight convex relaxations for contact-rich manipulation. 2024. URL
Danijar Hafner, Timothy Lillicrap, Jimmy Ba, and Mohammad Norouzi. Dream to control: Learning 2019a.
behaviors by latent imagination. arXiv preprint
Danijar Hafner, Timothy Lillicrap, Ian Fischer, Ruben Villegas, David Ha, Honglak Lee, and James Davidson. Learning latent dynamics for planning from pixels. In International Conference on Machine Learning, pp. 2555 2565,, PMLR, 2019b.
Danijar Hafner, Timothy Lillicrap, Ian Fischer, Ruben Villegas, David Ha, Honglak Lee, and James Davidson. Learning latent dynamics for planning from pixels. In International Conference Machine Learning, pp. 2555-2565 2019c.
Tyler Han, Alex Liu, Anqi Li, Alex Spitzer, Guanya Shi, and Byron Boots. Model predictive control for aggressive driving over uneven terrain, 2024.
Hanjiang Hu, Jianglin Lan, and Changliu Liu. Real-tine time safe control of neural network dynamic models with sound approximation, 2024a.
Hanjiang Hu, Yujie Yang, Tianhao Wei, and Changliu Liu. Verification of neural control barrier functions with symbolic derivative bounds propagation. In 8th Annual Conference Robot Learning, 2024b.
Zixuan Huang, Xingyu Lin, and David Held. Mesh-based dynamics model with occlusion reasoning for cloth manipulation. In Robotics: Science and Systems (RSS), 2022.
Alexander Kirillov, Eric Mintun, Nikhila Ravi, Hanzi Mao, Chloe Rolland, Laura Gustafson, Tete Xiao, Spencer Whitehead, Alexander C. Berg, Wan-Yen Yen Lo, Piotr Dollár, and Ross Girshick. Segment anything. arXiv:2304.02643 2023.
Panagiotis Kouvaros and Alessio Lomuscio. Towards scalable complete verification of relu neural networks via dependency-bess bassd branching. IJCAI, pp. 2643-2650, 2021.
Tejas D Kulkarni, Ankush Gupta, Catalin Ionescu, Sebastian Borgeaud, Malcolm Reynolds, Andrew Zisserman, and Volodymyr Mnih. Unsupervised learning of object keypoints for perception and control. Advances in neural information processing systems, 32: 12:100244-0734 2019.
Joonho Lee, Jemin Hwangbo, Lorenz Wellhausen, Vladien Koltun, and Marco Hutter. Learning quadrupedal locomotion over challenging terrain. Science robotics, 5(47), 2020.
Ian Lenz, Ross A Knepper, and Ashutosh Saxena. Deepmpe: Learning deep latent features for model predictive control. In Robotics: Science and Systems, volume 10, pp. 25. Rome, Italy, 2015.
Yunzhu Li, Jiajun Wu, Russ Tedrake, Joshua B Tenenbaum, and Antonio Torralba. Learning particle dynamies for manipulating rigid bodies, deformable objects, and fluids. arXiv preprint arXiv: /./.0016000 2018
Yunzhu Li, Jiajun Wu, Jun-Yan Yan Zhu, Joshua B Tenenbaum, Antonio Torralba, and Russ Tedrake. Propagation networks for moddll-assed control under partial observation. In 2019 International Conference on Robotics and Automation (ICRA), pp. 1205-1211. IEEE, 2019.
Yunzhu Li, Antonio Torralba, Anima Anandkumar, Dieter Fox, and Animesh Garg. Causal discovery in physical systems from videos. Advances in Neural Information Processing Systems, 33, 2020.
12

---

Published as a conference paper at ICLR 2025
Xingyu Lin, Yufei Wang, Zixuan Huang, and David Held. Learning visible connectivity dynamics for cloth smoothing. In Conference on Robot Learning, 2021.
Changliu Liu, Tomer Amon, Christopher Lazarus, Christopher Strong, Clark Barrett, and Mykel J. Kochenderfer. Algorithms for verifying deep neural networks. Foundations and Trends@ in Optimization, 4(3-4):244-404, 2021.
Shilong Liu, Zhaoyang Zeng, Tianhe Ren, Feng Li, Hao Zhang, Jie Yang, Chunyuan Li, Jianwei Yang. Hang Su, Jun Zhu, and Lei Zhang. Grounding dino: Marrying dino with grounded pre-training for open-set object detection, 2023a.
Ziang Liu, Genggeng Zhou, Jeff He, Tobia Mareucei, Li Fei-Fei, Jiajun Wu, and Yunzhu Li. Model- based control with sparse neural dynamics. In Thirty-sevnnth Conference on Neural Information Processing Systems, 2023b. URL. U http:///gpeerreeee...e/e/onnoddd
Kendall Lowrey, Aravind Rajeswaran, Sham Kakade, Emanuel Todorov, and Igor Mordatch. Plan online, learn offline: Efficient learning and exploration via model-based control. arXiv preprint a8Xiv: 1. 1.01848, 2018.
Jingyue Lu and M. Pawan Kumar. Neural network branching for neural network verification. In International Conference on Learning Representations (ICLR), 2020.
Miles Macklin, Matthias Müller, Nuttapong Chentanez, and Tae- Yong Kim. Unified particle physics for real-time applications. ACM Transactions on Graphics (TOG), 33(4):1-12, 2014.
Lucas Manuelli, Yunzhu Li, Pete Florence, and Russ Tedrake. Keypoints into the future: Self-supervised correspondence in model-based reinforcement learning. arXiv preprint wwXii:2009.050085, 2020.
Tobia Mareueci. Graphs of Convex Sets with Applications to Optimal Control and Motion Planning. PhD thesis, MASSACHUSETTS INSTITUTE OF TECHNOLOGY, 2024.
Mark Niklas Müller, Christopher Brix, Stanley Bak, Changliu Liu, and Taylor T Johnson. The third international verification of neural networks competition (vnn-comp 2022); Summary and results. arXiv preprint arXiv:2212.10377 2022.
Anusha Nagabandi, Kurt Konolige, Sergey Levine, and Vikash Kumar. Deep dynamics models for learning dexterous manipulation. In Conference on Robot Learning, pp. 1101-1112, PMLR, 2020.
Alessandro De Palma, Rudy Bunel, Aymeric Desmaison, Krishnamurthy Dvijotham, Pushmeet Kohli, Philip H. S. Torr, and M. Pawan Kumar. Improved branch and bound for neural network verification via lagrangian decomposition. arXiv preprint urXiv:2104.06711 2021.
Reuven Y Rubinstein and Dirk P Kroese. The cross-entropy method: a unified approach to combina- torial optimization, Monte-Carke simulation and machine learning. Springer Science & Business Media, 2013.
Jacob Sacks, Rwik Rana, Kevin Huang, Alex Spitzer, Guanya Shi, and Byron Boots. Deep model predictive optimization. 2023.
Hadi Salman, Greg Yang, Huan Zhang, Cho-Jui Hsieh, and Pengchuan Zhang. A convex relaxation barrier to tight robustness verification of neural networks. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
Julian Schrittweserr, Ioannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Simon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, et al. Mastering atari, go, chess and shogi by planning with a learned model. Nature, 58847839);604-669, 2020.
Younggyo Seo, Danijar Hafner, Hao Liu, Fangchen Liu, Stephen James, Kimin Lee, and Pieter Abbeel. Masked world models for visual control. In Conference on Robot Learning, pp. 1332-1344. PMI.R, 2023.
Haochen Shi, Huazhe Xu, Zhiao Huang, Yunzhu Li, and Jiajun Wu. Robocraft: Learning see, simulate, and shape elasto-plastic objects with graph networks. arXiv preprint 27X.v:200..02909 2022.
13

---

Published as a conference paper at ICLR 2025
Haochen Shi, Huazhe Xu, Samuel Clarke, Yunzhu Li, and Jiajun Wu. Robocook: Long-horizon clasto-plastic object manipulation with diverse tools, 2023.
Gagandeep Singh, Timon Gehr, Markus Püschel, and Martin Vechev. An abstract domain for certifying neural networks. Proceedings of the ACM on Programming Languages (POPL), 2019.
HJ Suh and Russ Tedrake. The surprising effectiveness linear models for visual foresight in object pile manipulation. arXiv preprint arXiv:2002.09093, 2020.
Stephen Tian, Frederik Ebert, Dinesh Jayaraman, Mayur Mudigonda, Chelsea Finn, Roberto Calandra, and Sergey Levine. Manipulation by feel: Touch-based control with deep predictive models. In 2019 International Conference on Robotics and Automation (ICRA), pp. 818-824. IEEE, 2019.
Vincent Tjeng, Kai Xiao, and Russ Tedrake. Evaluating robustness of neural networks with mixed integer programming, 2019.
Shiqi Wang, Kexin Pei, Justin Whitehouse, Junfeng Yang, and Suman Jana. Efficient formal safety analysis of neural networks. In Advances in Neural Information Processing Systems (NeurIPS), 2018.
Shiqi Wang, Huan Zhang, Kaidi Xu, Suman Jana, Xue Lin, Cho-Jui Hsieh, and Zico Kolter. Beta- crown: Efficient bound propagation with per-neuron split constraints for complete and incomplete neural network robustness verification. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
Yixuan Wang, Yunzhu Li, Katherine
Li Fei-Fei, and Jiajun Wu. Dynamic- Resolution Model Learning for Object Pile Manipulation. In Proceedings of Robotics: Science and Systems, Daegu, Republic of Korea, July 2023. doi: 10. 226607/RSS.2223.XXXX.
Manuel Watter, Jost Tobias Springenberg, Joschka Boedecker, and Martin Riedmiller. Embed to control: A locally linear latent dynamics model for control from raw images. arXiv preprint arXiv:1506.07366 2015.
Tianhao Wei and Changliu Liu. Safe control with neural network dynamic models, 2022.
Grady Williams, Andrew Aldrich, and Evangelos A Theodorou. Model predictive path integral control: From theory to parallel computation. Journal of Guidance, Control, and Dynamics, 40(2): 344-357, 2017.
Junlin Wu, Huan Zhang, and Yevgeniy Vorobeychik. Verified safe reinforcement learning for neural network dynamic models, 2024. URL hBt////pp////rrv.oo///////..... 15994
Philipp Wu, Alejandro Escontrela, Danijar Hafner, Pieter Abbeel, and Ken Goldberg. Daydreamer: World models for physical robot learning. In Conference on Robot Learning, pp. PMLR, 2023.
Kaidi Xu, Huan Zhang, Shiqi Wang, Yihan Wang, Suman Jana, Xue Lin, and Cui Hsieh. Fast and complete: Enabling complete neural network verification with rapid and massively parallel incomplete verifiers. International Conference Learning Representations (ICLR), 2021.
Lin Yen-Chen, Maria Bauza, and Phillip Isola. Experience-embeedee visual foresight. In Conference on Robot Learning, pp. 1015-1024. PMLR, 2020.
Zeji Yi, Chaoyi Pan, Guangi Hc, Guannan Qu, and Guanya Shi. Covo-mpe: Theoretical analysis of sampling- based mpe and optimal covariance design, 2024.
Yin, Zhiyuan Zhang, Evangelos Theodorou, and Panagiotis Tsiotras. Trajectory distribution control for model predictive path integral control using covariance steering. In 2022 International Conference on Robotics and Automation (ICRA), pp. 4478-1484, 2022. doi: 10. 1669/6 2022.9811615.
Huan Zhang, Tsui-We Weng, Pin-Yt Chen, Cho-Jui Hsieh, and Luca Daniel. Efficient neural network robustness certification with general activation functions. In Advances in Neural Information Processing Systems (NeurIPS), 2018.
14

---

Published as a conference paper at ICLR 2025
Huan Zhang, Shiqi Wang, Kaidi Xu, Linyi Li, Bo Li, Suman Jana, Cho-Jui Hsieh, and J Zico Kolter. General cutting planes for bound bound-propagatinn propagation based neural network verification. Advances in Neural Information Processing Systems, 2022a.
Huan Zhang, Shiqi Wang, Kaidi Xu, Yihan Wang, Suman Jana, Cho-Jui Hsich, and Zico Kolter. A branch and bound framework for stronger adversarial attacks of ReLU networks. In International Conference on Machine Learning (ICML), pp. 26591-26604 PMLR, 2022b.
Kaifeng Zhang, Baoyu Li, Kris Hauser, and Yunzhu Li. Adaptigraph: Material-adaptive graph-based neural dynamics for robotic manipulation. In Proceedings of Robotics: Science and Systems (RSS), 2024.
Zichen Zhang, Jun Jin, Martin Jagersand, Jun Luo, and Dale Schuurmans. simple decentralized cross-entropy method, 2022c. http///ss//aaii..aaaa//222233333
15

---

Published as a conference paper at ICLR 2025
A EXTENDED FORMULATION AND METHOD OVERVIEW
A.1 ILLUSTRATION OF BAB-ND ON A SIMPLIFED TASK
We refer to Figure to introduce theoretical concepts in Section and illustrate BaB-ND simplified robotic manipulation task.
Configuration. In Figure a, we first define the configuration of the task, where the robot moves left or right to push an object toward the target.
The ID action C in this its domain, where / is the maximum movement distance (e.g., 1 cm in practice). A value of u < 0 means the robot moves left, while u >> 0 means the robot moves right.
represents the movement of the robot pusher, with C C= =[-1,
I] as
The objective [()) measures the distance between the object and the target under specific action u. In this case, f(u) = df + dz where dj the distance between keypoint (P1) the object and the corresponding keypoint (Pi,r) on the target, and d2 is the distance between another keypoint pair (P2 and P2,r). For example, if the robot moves left (u 0), d2 decreases while dj increases.
The values of d1 and d2 depend on neural network dynamics model fayn- This model takes as input the current positions of P1 and P. relative to the pusher, along with an action u, to predict the next positions of P1 and Pg. Based on these predictions, d1 and d2 are updated accordingly, and f(u) may exhibit non-convex behavior.
Formulation of BaB. Our goal in planning is to find the optimal action u." that minimizes fu)). waaphhhnd-bouud--aae
To achieve this, we propose three components of our method. We first introduce some concepts below.
method. In Figure3]b c, and d, we illustrate
subdomain C, E a subset of the entire input domain C. For example, in Figure b, we initially split C = [],, into two subdomains: C1 (-1, 0] and C2 [0, (]. to separately analyze left and right movements.
Each subdomain C₂ has associated lower and upper bounds of the best objective in it: Le, and Te. These represent the bounds of the best objective in C, (fč minwee, f(u)). For example, if the optimal objective (the sum of the squared distances between keypoint pairs, df d)) given by the S minuec; df + d3 2 S 3). Intuitively, f. underestimates the minimum objective in C,, while Te. overestimates it.
best action in C, is 2, we might estimate f'c and Se.
We split the original domain C into multiple subdomains C, with branching, compute Le using bounding (Figure 3 c), and Jc. using searching (Figure d). These bounds allow us to determine whether a subdomain C; is promising for containing the optimal action u" or whether it can be pruned unpromising. For instance, in Figure assume fe, and Fc, 3. This means that objective better than can be achieved C1, while no objective worse than 3 can occur in C2. In this case, we can directly prune C₁ without further exploration.
Branching. Figure 3 b. we visualize the branching process, which constructs a search tree iteratively. We first split C [-1, into two subdomains: C₁ = [-1, 0] and C2 = [0, 1). allowing us to consider left and right movements separately. We can iteratively split any subdomain into smaller subdomains. For example, C2 can be further split into C3 and Ca.
Naively, we could search every subdomain and select the best action among all subdomains as our final best action. However, this approach is computationally expensive, especially when C is divided into many small subdomains. Therefore, we need to prune unpromising subdomains to reduce the search space and computational overhead.
Bounding. Pruning relies on the bounding component (Figure c), which provides f*, the lower bound fuu) within a given input domain. In our simplified case, f represents the lower bound of the sum of the squared distances between keypoint pairs.
16

---

Published as a conference paper at ICLR 2025
This bounding process is performed for every subdomain. Within specific subdomain, such as C1, we estimate a linear function (2)) that is always smaller than or equal to f(u) in C1 (i.e., g(u)= f(u), Yu E C1). We then use the minimum value of g(u) in C as the lower bound of f(u) in Ci (i.e, = minuer, (())). This estimation is based on CROWN and our adaptations.
Intuitively, subdomains with large lower bounds can be treated as unpromising, while those with small lower bounds are considered promising. Using these lower bounds, we can prioritize the promising subdomains and prune unpromising subdomains whose lower bounds exceed f the best objective found so far.
Searching. The best objective found, S" :- min; fe, is the best objective among all subdomains, where fc. represents the upper bound of the best objective in C, obtained through the searching process using sampling saasiing-bbsed methods, as shown in Figure 3.
Specifically, Jc, == minuyed, f(ux) is the best objective among all input samples un in C.. This is valid because Vu, E C,, S f(ug) holds. Thus, any l(ux)) can serve as an upper bound for Je, but select the best one achieve tighter bound on Fc.-
With more subdomains being pruned in the branch-and and-buund process, sampling- -bsedd methods can be applied to progressively smaller input spaces, enabling the discovery of better objectives. This process may ultimately converge to the actual optimal value f and identify the optimal action u..
A.2 ALGORITIM OF BAB-ND
The BaB-ND algorithm Algorithm 2 takes an objective function / with neural networks, a domain C as the imput space, and termination condition if necessary. The sub-procedure batch search seeks better solutions on domains [C,]. returns the best objectives {Fc, and the corresponding solutions {ūc,} for selected subdomains simultaneously. The sub-procedure
computes the lower bounds of f* on domains {C,} as described in Section 3.2 It operates batch and returns the lower bounds {f )-
In the algorithm, we maintain f and ê as the best objective and solution we can find. We also maintain a global set storing all the candidate subdomains where fe, 2 F Initially, we only have the whole input domain C, so we perform batch_search and batch_bound on C and initialize the current f" ū, and P (Lines 2-4).
Then we utilize the power of GPUs branch, search, and bound subdomains in parallel while main- taining P (Lines 6- 11). Specifically, batch pick out selects n (batch size) promising subdomains from P. If the length of IP is less than n, then n is reduced the length of batch split splits each selected C; into two subdomains C.Po and C.P according to a branch heuristic in parallel. Pruner filters out bad subdomains (proven with fe. > Sf', and the remaining ones are inserted into P.
The loop breaks if there are no subdomains left in or if some other pre-defined termination conditions, such as timeout or finding a good enough objective F 1 fuh, are satisfied (Line 5). We finally return the best objective f and the corresponding solution ů.
A.3 DISTINCTIONS BETWEEN BAB-ND AND NEURAL NETWORK VERIFICATION ALGORITHMS
Goals. BaB-ND aims optimize an objective function involving neural dynamics models solve challenging planning problems, seeking a concrete solution ă (a near-optimal action sequence) to an dnreettve-minimmzann
problem minuec f(u). In contrast, neural network verification focuses on proving a sound lower bound of f(u) in the space C, where concrete solution û is not needed. These fundamental distinctions in goals lead to different algorithm design choices.
Branching Heuristies. In BaB-ND, branching heuristics 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 heuristics focus solety on improving the lower bounds.
17

---

Published as a conference paper at ICLR 2025
Algorithm 2 Branch and bound for planning. Comments are in brown.
1: Inputs: f. C, (batch size), terminate (Termination condition)
2: {(f", ú}} batch_ssarch (C))
Initially search on the whole Initially bound on the whole b is the set of all candidate subdomains
3: {f") batch_boundd (f, (C})
4: IP (
while (ength((P) > and not terminate do
6:
[(C., TT, úc,]] batch batch_pick out nP) Pick subdomains split and remove them from Each C; splits into two subdomains C, and C," b Search new solutions
7:
(,,, + batch_splite ((C.))
8:
(TTe (Tp
&- batch_ search (J, (C..c..))
9:
Lor Lon) batch_ (f, ()
Compute lower bounds subdomains
10: if min (opp)) <f then
(Top.Toy)) u arg argmin (Top..c.4 Top3) (T', ((,, Sep Jep) 1C,, (CT:sep:Tee)) Outputs: f"
T - min
Update the best solution needed Prune bad domains using J
12:
P+- Prrnnr
13:
Bounding Approaches. While existing bounding approaches, such as CROWN from neural net- work 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.
Searching Components. BaB-ND includes additional searching component in the branch-and- bound procedure to find the optimal solution to planning problems. Neural network verifiers typically do not have this component, as they focus solely obtaining lower bounds of objectives over input space rather than identifying objective values for specific inputs. We further adapt the searching component to benefit from the BaB procedure while also guiding BaB for improved searching.
A.4 LIMITATIONS AND FUTURE DIRECTIONS
In this section, we discuss few limitations of our work and potential directions for future work.
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 low objective as predicted by the learned dynamics model but still miss the target (e.g., the model predicts that 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.
Optimality of our solution may be inftuenced by the underlying searching algorithms..
The planning performance BaB-ND is inherently influenced by the underlying campling-based searching algorithms (e.g., sampling-ber based methods may over-exploit over-explore the objective landscape, resulting in suboptimal solutions in certain domains). Although our branch-and- procedure can mitigate this issue by systematically exploring the input space and efficiently guiding the search, incorporating advanced sampling-bail -based searching algorithms with proper parameter scheduling into BaB-ND could improve its ability tackle more challenging planning problems.
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 generalizable strategies for broader applications, potentially leveraging reinforcement learning approaches.
18

---

Published as a conference paper at ICLR 2025
B MORE DETAILS ABOUT BOUNDING
B. PROOFS OF CROWN BOUNDING
In this section, we first share the background of neural network verification including its formulation and a efficient linear bound propagation method CROWN (Zhang et al. 2018) to calculate bounds over neural networks. We take the Multilayer perceptron (MLP) with ReLU activation as the example and CROWN is general framework which is suitable to different activations and model architectures.
Definition. We define the input of neural network biases of an L-layer neural network as ( E xd::x:;-1 and b H. (i E (1....,4} re- spectively. The neural network function
Rd, and define the weights and
Rdo R is defined f(x) (z),, where 2 (x) g()) (x) + b(), (x) = (x)) and (x)
a is the activation function and we use ReLU throughout this paper. When the context is clear, we omit (xx and use z) and (()
2 to represent the pre-activation and post-activation values of the j-th neuron in the i-th layer. Neural network verification seeks the solution of the optimization problem in Eq.
) x E C, (1,.... ................. L 13 (3) The set C defines the allowed input region and our aim is to find the minimum of f(x) for E C, and throughout this paper we consider an lp ball around a data example zn: C = {xr | wolls ll S e).
min (xx = (T.) s.t. 20) (())((- + (() 200) (=)1),,
First, let we consider the neural network with only linear layers. in this case, it is easily to get linear relationship between x and f(x) that f(x) = Wr + b no matter what is the value L and derive the closed form of f min f(x for C. With this idea in our mind, for neural networks with non-linear activation layers, if we could bound them with some linear functions, then it is still possible to bound f fz) with linear functions.
Then, we show that the non- linear activation ReLU layer & = ReLU(2) can be bounded by two linear functions in three cases according to the range of pre-activation bounds I 2 S active (1 2 0), inactive (u S 0) and unstable (1 < 0 < u) in Lemma B.
Lemma B.1 (Relaxation of ReLU layer in CROWN). Given pre-activation vector 2 1 = u (element-wise), 2 = ReLU(2), we have
D2 D=+b<å
where D, D,De E Rad are diagonal matrices defined as:
1,
ifl, 20,00
f1,20 20
Djs
0,
uf 0
DjJ.
0.
if 0
(4)
Cjj
u
u,
u, 0>
a E Rd a free vector s.t., 0 a b, Rdd are defined as
0, ifl, > 0or u,
0
0,
ff, > 0 or uj 50
b, = 0, uu 1>
b
u,l
if 0> 13.
(5)
U,
1,,"
Proof. For the j-th ReI.U neuron, 1, 2 0, then ReLU(22) = zj: if uj < 0. then ReLU(2;) = 0. For the case of 1 < 0 uj, the ReI.U function can be linearly upper and lower bounded within this range:
ajzj & ReLU(z2)) u
(z 1,)
A 14
S uj
where 0 0 a < is a free variable any value between 0 and produces a valid lower bound.
Next we apply the linear relaxation of ReLU to the L-layer neural network f(z) to further derive the linear lower bound of fz). The idea is to propagate a weight matrix W and bias vector b from the I-th layer to 1-th layer. Specifically, when propagate through ReLUU layer, we should greedily select upper bound of 2, when W., is negative and select lower bound of & when W,, is positive to calculate the lower bound of f(x). When propagate through linear layer, we do not need to do such selection since there is relaxation linear layer.
19

---

Published as a conference paper at ICLR 2025
Theorem B.2 (CROWN bound propagation neural network). Given the L-layer neural network f f() as defined in Eq. we could find a linear function with respect to input x.
f(z) = == 2 W x + (1)
(6)
where W and l are recursively defined as following:
(1) W() (1) = b d 14 I...L
(7)
A (4) IE Rdexdr (()) =0
(8)
A
W 20
(
Wen
(l+1)
D (1)
E Rduixx VI 1....
(9)
d
W
20
(++1)
b
<0
(41)
+b
-1 I.-
(10)
where VI -1..1..L--1
D (1)
E R44d and (0)
D E Bd are defined as in Lemma B. I And
subscript "2 0" stands for taking positive elements from the matrix while setting other elements to zero, and vice versa for subscript "< 0"
Proof. First we have
f(x) = 2(L) = A (1))((4) + (L)
-((W ((--)) + (D) + (4)
-w g(C-1) 3(L-1((11) +b (1)
(11)
Refer Lemma B.I have
(( ((1-1) 11-11) + (1.-1) < ((4-1) < (D (1-11) +
(12)
Then we can form the lower bound (L) element by element: we greedily select the upper
bound of s(6-1) < D(L-") (L-1) + by 1(1-1) when Wi, (L)
negative, and select the lower bound b, (L-1) otherwise. It can be formatted as
ji 3j
-(L-1) 2 D (1-1))((-1)
j.
W g(L-1) + +5t0) 2 (1-1)) + (
(13)
where A (6-1) E Rdr.xd.-- is defined as
(L-1)
(L)
D jj
W
<0
(2)
(14)
(1-1)
if W 20
for simplicity, rewrite it in matrix form
A (4-1) w D w D (L-11)
(15)
And (L-1)) E Rd is similarly defined as
(1-1))
(1) W 2o (1--1)
W
1 +b
(1) (l-))(())) (())
(16)
Then we continue to replace 2 (t--1) in Eq. 13 as W 1) (T-22 + -((--1)
(L-1)) 1) + b
(L)
A (1-1) (((-1) 13(6-- A (1-1)) (L-1) + (
= (L-1) g(L-2) + 5 1(1-1)
(17)
By continuing to propagate the linear inequality to the first layer, we get
f(x) > w [(0) + b
(1) x x+
(18)
n
20

---

Published as a conference paper at ICLR 2025
After getting the linear lower bound of far, and given I C, we could solve the linear lower bound in closed form as in Theorem B.3] is given by the Hölder's 's inequality.
Theorem B.3 (Bound Concretization under ép ball Perturbations). Given the L-layer neural network
(() as defined in Eq. [ and input E C B, +) {ar | zollp lp S <c) we could find
(1) (1)
concrete lower bound of f(z) by solving the optimization problem minsee W x b solution gives
and its
min f(x) =EC
min sEC
W
(1) x
(1) 2+
x+b
- |
W
(1)
W
To b
(1)
(19)
where" 1 + =1= and 1 denotes taking fg-norm for each row in the matrix and the result makes p 9
up a vector."
Proof.
min
(")
x x+ +bb
(20)
#EC
(1)
min (011
W (no ()) +b
(21)
(1)
A) + - (1) (11)
=e(, min W
W 20 +b"
(22)
(0,11
(1)
e( max
W 1) + W
Ty + b
(23)
(0,1
(1)
11) + W (1)
(1)
e( max (0.)(
Z0 +b
(24)
[1.1111p) + w (1)
2o + +b (1)
() (Hölder's inequality)
2 - E( max
W
(25)
(01)(0.1)
e||
11
W
Fo + b
(26)
B.2 DETAILS ABOUT ROUND PROPAGATION EARLY-STOP
We parse the objective function I into a compu- tational graph g (V, E), where V and E are the sets of nodes and edges, respectively. This
Algorithm 3 Bound Propagation w/ Early-stop.
1: Function: compute_ bouudd
2: Inputs: computational graph G, output node
process can be accomplished using popular deep learning frameworks, such PyTorch, which sup- port not only neural networks but also more general functions. In the graph G, any mathematical op- eration is represented as a node w E V, and the edges e = (w, u) E E define the flow of compu- tation. The input u. constant values, and model
early-stop set
3: CROWN BeoWH_init(G.20
4: Q t (), Qppuhh(o)
5:
while length(() d
6:
с Q.popp) for w E In(v)
7:
8:
du -
parameters constitute the input nodes of G, form-
9:
if d... = 0 and w $ I then
ing the input set I = {v In(v) = 0}. where
10:
Q.push(w)
In(e)= = [ (w, E E} denotes the set of input nodes for a node u. Any arithmetic operation, such
11:
if E S then continue
as ReLU, which requires input operands, is also rep- resented as node in G but with non-empty input
13: CROWN CROWN_prop(()
14:
f + CROHN_conccettize(1,,
set. The node o is the sole output node of G and provides the scalar objective value in our case.
15: Outputs: _
Our method (Algorithm 3) takes as input the graph & of f. the output node o to bound, and a set of early-stop nodes S c V. It outputs the lower bound of the value of i.e., f It first performs CROWN init to initialize d, for all nodes e, representing the number of output nodes of u that have not yet been visited.
The algorithm maintains a queue Q of nodes to visit and performs a Breadth First Search (BFS) on G. starting from o. When visiting node u, it traverses all input nodes of u, decrementing d.. If all
21

---

Published as a conference paper at ICLR 2025
output nodes of wo have been visited and w is not imput node of G, w is added Q for propagation (Lines 7-10). The key modification occurs in Lines 11-12, where bound propagation from to all its input nodes is stopped if S.
Finally, the algorithm concretizes the output bound f at nodes v E -USS based on their lower and upper bounds 1, and u, We assume I, and u, are known for I since the input range of N. as well as all constant values and model parameters, is known, For any v E S, its I, and u. are given by minm gu go (u") and max ge (uu")) from Search-integrated bounding in Section 3.2
An illustrative example for bounding. Assume f(u) is an L-layer MLP. We illustrate how to estimate its lower bound f with early stopping at the last ReLU layer in Fig- ure 8 For simplicity, we denote the output f(u). the L-th linear layer, the ReLU layer, the L - 1-th linear layer, and the input as nodes Ny. Nr, Nn, Nr-11, and Nu, respec- tively. Additionally, we denote f(u)
Step
Step 2
Step
Step
Linear
Linear Z-
Linear --
Linear
Graph
A--1
7-
the output value of node Ny., z(L-1)(u) (u) as the input of Nr. and output of NR. and z (()=1)(u) (u) as the input of NR and output of 111
(u)
RaLu
RaLU
RaLU
RaLU
+1
Linear
Linear
Linaar
Linear
In Step 1, we initialize CROWN and the queue Q for traversal, starting with the output node yy. In Step 2, we update the out-degree of node Nr which is the input of
Queue
Linear
ReLU
ReLU
Ny, and propagate from y to Nr. Since d, = 0 indicates that all its outputs (in this case, only Ny) have been visited, node Nr, is added to Q. In Step 3, we continue propagation to the input of Nr, which is the node Ng. Then NR is added to Q. In Step 4, we visit RR which is defined as early- stop node. The backward flow stops propagating to its input node N and N is not added to Q because it is not an input node. Since Q is now empty, the bound propagation is complete.
Linear
Figure 8: Bound propagation with early- stop on an L-layer MLP f(u). Bound prop- agation starts from the node of output and then backwards layer by layer the L- linear layer. The backward flow is high- lighted as t and stop at X. In the queue, the node popped every step is semitransparent.
Finally, we require the lower and upper bounds of (u4-))(u) (the input value of N and the output value of Nr.-)) i) to compute f". Using our Search-integrated bounding approach, these bounds are obtained empirically from samples during the searching process.
A deeper look at the illustrative example. We now connect the CROWN theorem in Section B.1 to our illustrative example better understand the behaviors of CROWN prop and Here, the input in Section B.I corresponds to u.
CROWN_prop
In Step 2, since e L is linear layer, calling CROWN prop corresponds the propagation in Eq. Note that no relaxation is introduced when propagating through the linear layer.
In Step
R a non-linear ReLU layer, and calling CROWN_prop prop corresponds to the propagation in Eq. 13 This step requires a linear estimation of the non-linear layer as described in Eq. [2] which is obtained from the lower and upper bounds of the input to Na (i.e., 2(f--)) (u)) using Lemma B.1 At this stage, linear relaxation is introduced for the non-linear layer, potentially loosening the final lower bound of (u)
The lower and upper bounds of 2(L-1)()) are referred to as intermediate layer bounds or pre- activation bounds in Section 3.2 However, these bounds are initially unknown in practice. In the original CROWN algorithm, computing these bounds requires recursively calling compute bound with L --1 In our approach, these bounds are instead estimated empirically from samples during the searching process, as they serve as the input bounds for the early-stop node NR-
Now assume we have obtained the intermediate layer bounds and propagated the linear relation through the non-linear node Ng. With the early-stop mechanism, we stop further propagation to Nr.1 and subsequently to the input Ny, At this point, BeWWW__oocretieeee is called to compute f" using the intermediate layer bounds and the relaxed linear relation between N2z and N obtained from propagation. Specifically, this can be achieved by replacing with ((L-1)(u) in Theorem B.3
22

---

Published as a conference paper at ICLR 2025
In contrast, the original CROWN algorithm continues propagating through Nz-1 and eventually to the input Nu. then calls hatp:/__oncerrii_e using the linear relation between Nu and Ny and the lower and upper bounds of Nu described in Theorem B.3
Improvement of our approaches. Here, we discuss why our bounding approaches (Propagation early-stop and Search-inte intrrrc-eteeeetedd bounding) achieve much tighter bound estimations and greater efficiency compared to the original CROWN.
Efficiency: The original CROWN performs bound propagation through every layer and recursively computes each intermediate layer bound by propagating it back to the input. This process results in quadratic time complexity with respect to the number of layers. contrast, our method conducts bound propagation only from N to few early-stop nodes and derives the input bounds of these nodes from prior sampling-bar
searching without recursively calling CROWN, As result, the time complexity of our approach can be linear with respect to the number of layers and even constant under certain configurations of early-stop nodes.
Effectiveness: As introduced earlier, the looseness in bound estimation stems from the linear relaxation of non-linear layers. In the original CROWN, the number of linear relaxations is quadratic with respect to the number of non-linear layers. In our approach, the bounding procedure involves far fewer linear relaxations. Furthermore, the empirical bounds obtained from searching, which may slightly underestimate the actual bounds, contribute to further tightening the bound estimation.
23

---

Published as a conference paper at ICLR 2025
C ADDITIONAL EXPERIMENT RESULTS
C.I SCALABILITY ANALYSIS
Comparison with sampling-basee methods. We conducted an experiment compare the scala- bility of our BaB-ND with sampling-basse methods on complex planning problems. We used the same model sizes and planning horizons as Figure ( (a), optimizing the complex objective function applied in the Pushing w/ Obstacles task. Parameters for all methods were adjusted to ensure similar runtimes for the largest problems.
The results in Figure 9 show that the runtime of our BaB-ND is less sensitive to the increasing complexity of planning problems compared to sampling-han methods. While BaB-ND incurs additional overhead from initializing a,,8CROWN and performing branching and bounding, it is less efficient than sampling-basee methods for small problems.
MPPI
CEM
CROWN
Fall
300
Planning Pootzon
Rumsmm (Scoordd))
2112
0.52
2.00
2651
2
0.75
255
3527
6.79
5331
12.09
17/66
25:43
200
130
5370
644
2022
2:75
15.7%
12:79
17.30
5.40
937
7216
17:35
18.1
18.55
15.09
29.9
22114
90.55
6860
1653
20.00
6:76
11:13
26-17
MAY
2.10
2616
33:08
20.29
$4.0
3:31
46:00
+4.0
100
19.22
10:30
55:47
117.0
11:11
12:10
19.1
34.34
40.01
11:53
11:33
14.90
3305
18.50
33.97
30:17
10.02
40.12
03.20
036x
2400 36./K
(3A5X550
62lox
3440
24.3K
13428
5354K
2212K
6716 2.447
2431K (34
5334K
A222K 6712
244K 34314 (54.X Model Size
Model Size
Model Size
Model 152c
Figure 9: Comparison of runtime with sampling- based methods. Although our BaB-ND efficient on small planning problems than baselines, achieves similar efficiency on larger planning problems.
We also report the average objectives for all methods on the largest four planning problems to evaluate their effectiveness Table [ Overall, the performance gaps between our BaB-ND and the baselines increase with the size of the problem, highlighting the ineffectiveness of compling-based methods for large, complex planning problems.
Table I: Comparison of planning performance across different configurations
Planning Problem Size
Method
(134.2K,15)
(134.2K,20)
(530.2K,15)
(530..2K,0)
GD
57.2768
64.4789
54.7078
60.2575
MPPT
47.4451
53.7356
45.1371
45.6338
CEM
47.0403
47.6487
43.8235
38.8712
Ours
46.0296
46.1938
41.6218
34.6972
Additionally, we evaluate the planning performance of sampling baased methods and our approach on the same simple synthetic planning problems those in Figure 7 We report only the six cases that MIP can solve optimally within 300 seconds. The results in Table [ show that, under these much simpler settings compared those our main experiments, all methods perform similarly. Sampling-basee methods (MPPI, CEM, and ours) achieve gap under the order of x 10-4 compared to MIP with an optimality guarantee.
Table 2: Comparison planning performance on simple synthetic planning problems
Planning Problem Size
Method
(0.232K,1)
(0.712K.
(2.440K.1)
(0.232K.3)
(0.712K.3)
(0.232K.5)
MIP
30.3592
32,9750
33.5496
22.1539
28. 28.0832
15.6069
GD
30.3622
32.9750
33.5496
22.3242
28.1404
17.068
MPPI
30.3592
32.9750
33,5496
22.1539
28.0832
15.6069
CEM
30.3592
32.9750
33.5496
22.1539
28.0832
15.6069
Ours
30.3592
32,9750
33.5496
22.1539
28.0832
15.6069
24

---

Published as a conference paper at ICLR 2025
Comparison with CPU version. We evaluate the performance improvement from CPU to GPU in Figure T0 We use the same test cases as in Figure 7 and report
CPU
GPU
Fall
Phieiing Hotton
Funtima (Scordd))
2044
20:4
M8.2
2:
200
"NaN" if the process does not terminate within 300 seconds.
71:00
1057
6:40
27.11
The results clearly demonstrate that our implementation benefits significantly from GPU acceleration, achieving over 10x speedup compared to the CPU version, even for small planning problems.
Model Size
Model Size
Figure 10: Comparison of runtime CPU and GPU.
GPU acceleration improves the scalability BaB-ND much.
C.2 COMPARISON WITH CONVENTIONAL MOTION PLANNING APPROACHES
We conduct an additional experiment on the task Pushing with Obstacle to compare the planning performance of our campling-based baselines, our BaB-ND, and two conventional motion planning approaches: 1. Rapidly-exploring Random Tree (RRT); 2. Probabilistic Roadmap (PRM). In Table 3 Since RRT and PRM do not optimize the objective as we did in sampling-has methods and our BaB-ND, we only report the step cost at planning horizon H as the final step cost instead of the planning objective.
Table 3: Comparison of planning performance with RRT and PRM
GD
MPPI
CEM
RRT
PRM
Ours
Final step cost (L)
4.1238
1,5082
1.0427
10.6472
1.6784
0.2339
The results demonstrate that method significantly outperforms all other approaches. Imple- mentation 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 getting stuck on obstacles, often failing to reach the target state.
C.3 ABLATION STUDY AND
ANALYSIS
Ablation Study. We conduct an additional ablation study on the Pushing w/ Obstacles and Object Sorting tasks to evaluate how different design choices impact planning performance in Table 4
Table 4: Ablation study on branching and bounding components
(a) Heuristies for Selecting subdomains to Split
fr and fe;
Te, only
fr, only
Pushing w/ Obstacles Object Sorting
31.9839 31.0482
32.2777 32.1249
32.6112 33.2462
(b) Heuristies for Splitting subdomains
||
n
(17,
21
|| n2
Pushing w/ Obstacles Object Sorting
31.9839
32,3869
32,6989
31.0482
34.5114
32,8438
(e) Bounding Component
Ours
Zero fr,
Zero f²,
f only
Pushing w/ Obstacles Object Sorting
31.9839 31.0482
32.3419 33.61 10
34.6227 34.4533
(a) Heuristics for selecting subdomains to split: 1. Select based on both lower and upper bounds fö,
and Fe. 2. Select based only on F', 3. Select based only on f", Among these heuristics, selecting
25

---

Published as a conference paper at ICLR 2025
promising subdomains based both fo, and fc. achieves better planning performance by balancing exploitation and exploration effectively compared the other strategies.
(b) Heuristics for splitting subdomains: 1. Split based on the largest (ū, - =,) In " 2. Split
based the largest (ī, 22) 3. Split based the largest In// n Our heuristic demonstrates
superior planning performance by effectively identifying important input dimensions to split.
(c) Bounding components: 1. Use 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 the heuristic for selecting subdomains split. Our bounding component improves planning performance by obtaining tight bound estimations, helping prune unpromising subdomains reduce the search space, and prioritizing promising subdomains for searching.
parraetarr Analysis. We adjust three w/ Obstacles and Object Sorting to evaluate its hyper-parameter sensitivity:
in BaB-ND for the tasks Pushing
n= Ri E [0, 1), the ratio of the number of subdomains picked with the best upper bounds (n1) to the number of all picked subdomains (n) in the heuristic used for selecting subdomains to split. A larger promotes exploitation, while a smaller 7 encourages exploration.
T E R. the temperature softmax sampling in the heuristic for subdomain selection. A larger T results in more uniform and random sampling. whereas smaller 7 leads more deterministic selection of subdomains with smaller lower bounds.
(0, 100), the percentage of top samples used in the heuristic for splitting subdomains. A larger w results in more conservative decisions by considering more samples, while a smaller w leads to more aggressive splitting.
We report the mean objectives under different hyper-parameter configurations in Table 5 The base prree-pprraettr configuration is 0.75, T = 0.05, and w 1. For benchmarking, we vary at most one typer-parameter at a time while keeping the others fixed the base configuration.
Table Planning performance under different pppae-errreeter configurations
(a) hyper-parameter
0.25
0.50
= 0.75
Pushing w/ Obstacles
31.8574
31,9828 30.2795
31.9839
Object Sorting
30.1760
31.0482
(b) hyper-parameter T
0.05
20
Pushing w/ Obstacles
31.9839
32.3990
32. 1267
Object Sorting
31.0482
31.2366
31.8263
(c) harer--ar
0.1
10
Pushing w/ Obstacles 32,0068
31.9839
32,0599
Object Sorting
30.5953
31.0482
31.1545
The results show that different but the gaps are relatively small. This indicates that our BaB-ND is not highly sensitive to these hyper-paranee pppemppareetrss. Consequently, it feasible in practice to use fixed seper-parameter configuration that delivers reasonable performance across different test cases and tasks.
configurations produce slight variations in objectives,
C.4 QUANTITATIVE ANALYSIS ON SEARCH SPACE
We conducted an experiment to measure the normalized space size of pruned subdomains over iterations. In Table 6 we report three metrics over the branch-and- iterations: 1. the normalized space size pruned subdomains, the size the selected subdomains, and 3. the improvement in the objective value.
26

---

Published as a conference paper at ICLR 2025
With increasing iterations, the average and best total space size of pruned subdomains increases rapidly and then converges, demonstrating the effectiveness of our bounding methods. Once the pruned space size reaches plateau, the total space size of selected promising subdomains continues to decrease, indicating that the estimated lower bounds remain effective identifying promising subdomains. The decreasing objective iterations further confirms that BaB-ND focuses the most promising subdomains, reducing space size to the magnitude of 1 x 10-4.
Table Performance Metrics Over Iterations
Iterations
Metric
0
4
8
12
16
20
Pruned space size (Avg, 1)
0.0000
0,7000
0.8623
0.8725
0.8744
0,8749
Pruned space size (Best, 1)
0.0000
0.8750
0.9921
0.9951
0.9951
0,9952
Selected space size (Avg,
1.0000
0.3000
0.0412
0.0048
0.0005
0.0003
Best objective (Avg, 1)
41.1222
36.0511
35.5091
34.8024
33,8991
33.3265
C.5 PERFORMANCE CHANGE WITH VARYING INPUT DISCONTINUITIES
We conducted follow-up experiment by removing the obstacles (non-feasible regions) in the problem of Pushing w/ Obstacles, 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) in Table
The results show that in simple cases, although our BaB-ND consistently outperforms baselines, MPPI and CEM provide competitive performance. In contrast, in complex cases, BaB-ND significantly outperforms the baselines, demonstrating its effectiveness in handling discontinuities and constraints.
Table 7: Performance comparison varying input discontinuities
(a) Objective w/o obstacles
(134.2K,15)
(134.2K.20)
(530.2K,15)
(530.2K.20)
GD
64.5308
64.2956
63.0130
60.6300
MPPI
34.4295
26.9970
33,8077
26.1204
CEM
34.3864
26.7688
33.6669
25.9599
Ours
34.2347
26.4841
33.6144
25.6603
(b) Objective w/ obstucles (Table
(134.2K,15)
(134.2K,20)
(530.2K,15)
(530.2K,20)
GD
57.2768
64.4789
54.7078
60.2575
MPPT 47.4451
53.7356
45.1371
45.6338
CEM 47.0403
47.6487
43.8235
38.8712
Ours 46.0296
46.1938
41.6218
34.6972
C.6 FURTHER SCALABILITY ANALYSIS THE SYNTHETIC EXAMPLE
We extend our experiment the synthetic example shown in Figure 4, as this allows us to easily scale up the input dimension while knowing the optimal objectives. We vary the input dimension N from 50 to 300 and compare our BaB-ND with MPPI and CEM.
Although this synthetic example is simpler than practical cases, it provides valuable insights into the expected computational cost and solution quality demonstrates the potential of BaB-ND in handling complex scenarios such as 3D tasks. We report the gaps between the best objective found by different baseline methods and the optimal objective value below.
scale to high-dimensional problems. It
The results in Table & show that our BaB-ND much outperforms baselines when the input dimension increases. These results are expected since existing sampling based methods search for solutions across the entire input space, requiring exponentially increasing number of samples achieve
27

---

Published as a conference paper at ICLR 2025
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-bas based methods.
Table 8: Performance comparison across different input dimensions (Metric: Gap to f',
Input dimension N
Method
50
100
150
200
250
300
MPPI
7.4467
45.1795
105.1584
181.1274
259.1044
357.3273
CEM
5.1569
15.6328
26.3735
39.3862
61.6739
92.4286
Ours
0.0727
0.2345
0.4210
0.6976
1.2824
1.7992
We further report the following metrics about our BaB-ND in Table to better understand the behavior of BaB-ND under high-dimensional cases: The gap between the best objective found and the optimal objective value above, 2. The normalized space size of pruned subdomains at the last iteration, 3. The normalized space size of selected subdomains the last iteration, and The total runtime.
The results demonstrate that our BaB-ND effectively focuses on small regions to search for better objectives, while the runtime increases approximately linearly with input dimension under GPU acceleration.
Table 9: Performance metrics across different input dimensions N
Input Dimensions
Metric
50
100
150
200
250
300
Gap f (L)
0,0727
0.2345
0.4210
0.6976
1.2824
1.7992
Selected Space Size (L)
0,0002
0.0017
0.0026
0,0042
0.0064
0.0040
Pruned Space Size (1)
0.8515
0.6073
0.3543
0.1762
0.0579
0.0113
Runtime ())
4.2239
6,5880
9.5357
11.6504
13.7430
15.8053
28

---

Published as a conference paper at ICLR 2025
Ar, Ay.
J. Ar.
AAr,
Au. Avl
(a) Pushing Obstacles
(b) Object Merging
(c) Rope Routing
(d) Object Sorting
Visualization of real-world experiments with illustration of action spaces in different tasks. In tasks Pushing w/ Obstacles and Object Merging, the actions are defined as the movement of the pusher in 2D space. In the task Rope Routing, the action defined the movement of the gripper in 3D space. In the task Object Sorting, DoF action is defined as the 2D starting position and movement of the pusher.
Figure 1I:
D EXPERIMENT DETAILS
D.1 DEFINITION OF ACTIONS AND STATES
We consider actions with 2-4 degrees of freedom (DoF) in Cartesian coordinates for our tasks. Across all tasks, we adopt a general design principle of using 3D points as the state representation, as they effectively capture both geometric and semantic information and facilitate seamless transfer between simulation and the real world. The specific definitions of actions and states for each task are detailed below:
Pushing w/ Obstacles. The action is defined 2D movement of the pusher, (Ax, Ay). within single step, as illustrated in Figure a.. Four keypoints are assigned to the "T"'-shaped object to capture its geometric features, visualized in Figure 12 a.
Object Merging. The action is similarly defined as 2D movement of the pusher, (Ax, Ay), within one step, as shown Figure b The orientation of the pusher rotates around the gravity direction and is always perpendicular to the direction of pushing (Az, Ay). The state is represented by six keypoints on the "L" "L"-shaped objects (three keypoints per object), as depicted in Figure 12
Rope Routing. This task involves DoF actions, defined as movements of the robot gripper along the Cartesian axes, (Ax, Ay, Az), as illustrated in Figure I1 c. To better represent the rope's geometric configuration. multiple keypoints (e.g.. 10) are sampled along the rope, as shown in Figure
Object Sorting. This task requires a series of independent long-range pushing actions, where the initial position of the pusher for each step is independent of its final position from the previous step. The action defined by the 2D initial position of the pusher, (æ. y), and its subsequent 2D movement, (Ar, Ay), visualized Figure [ For the state, use an object-centric representation, defining the state as the center points of all objects, as illustrated in Figure 12 d. Interactions between objects modeled graph using graph neural networks.
For all tasks, we do not explicitly specify the contact points between the robot and objects. Instead, our BaB-ND framework generates sequence of end-effector positions for the robot to follow, implicitly determining aspects such as which side of the "T"'shaped object is being pushed.
D.2 DATA COLLECTION
For training the dynamics model, randomly collect interaction data from simulators. For Pushing w/ Obstacles, Object Merging, and Object Sorting tasks, we use Pymunk (Blomqvist) 2022) to collect data, and for the Rope Routing task, the following paragraphs, we introduce the data generation process for different tasks in detail.
NVIDIA FleX (Macklin et al. 2014) to generate data. In
Pushing w/ Obstacles. As shown in Figure 12 a, the pusher simulated as a 5mm cylinder. The stem of the "T"'-shped object has a length of 90mm and width of 30mm, while the bar has a length of 120mm and width of 30mm. The pushing action along the x-y axis is limited to 30mm. We don't add explicit obstacles in the data generation process, while the obstacles are added as penalty terms during planning. We generated 32,000 episodes, each containing 30 pushing actions between the pusher and the "T''shaped object.
29

---

Published as a conference paper at ICLR 2025
(a) Pushing Obstacles
Object Merging
(c) Rope Routing
(d) Object Sorting
Simulation environments used for data collection. We use Pymunk to simulate environments involving only rigid body interactions. For manipulating the deformable rope, we utilize NVIDIA FleX to simulate the interactions between the rope and the robot gripper.
Figure 12:
Object Merging. As shown in Figure 12 b, the pusher is simulated as 5mm cylinder. The leg of the "h="shaped object has a length of 30mm and a width of 30mm, while the foot has a length of 90mm and width of 30mm. The pushing action along the x-y axis is limited to 30mm. We generated 64,000 episodes, each containing 40 pushing actions between the pusher and the two "L"-shaped objects.
Rope Routing. As shown in Figure 12 we use xArm6 robot with gripper to interact with the rope. The rope has length of 30cm and radius of 0.03em. One end of the rope fixed while the gripper grasps the other end. We randomly sample actions in 3D space, with the action bound set to 30cm. The constraint is that the distance between the gripper position and the fixed end of the rope cannot exceed the rope length. We generated 15,000 episodes, each containing 6 random actions. For this task, we post-process the dataset and split each action into 2em sections.
shown in Figure 12 d, the pusher is simulated as a rectangle measuring 45mm by 3.5mm. The radius of the object pieces is set to 15mm. For this task, we use long push as our action representation, which generates the start position and pushing action length along the x-y axis. The pushing action length is bounded between 1100m and 100mm. We generated 32,000 episodes, each containing 12 pushing actions between the pusher and the object pieces.
Object Sorting.
D.3 DETAILS OF NEURAL DYNAMICS MODEL LEARNING
We learn the neural dynamics model from the state-action pairs collected from interactions with the environment. Let the state and action at time t be denoted 2, and ue. Our goal is to learn a predictive model faym: instantiated as a neural network, that takes a short sequence of states and actions with 1-step history and predicts the next state at time 1:
4 = Sayn (x,, uz)
(27)
To train the dynamics model for better long-term prediction, we iteratively predict future states over time horizon Tú, and optimize the neural network parameters by minimizing the mean squared error (MSE) between the predictions and the ground truth future states:
1+Th Σ
L
1 - Jayn 1.
(28)
Th
For different tasks, we choose different types of model architecture and design different inputs and outputs. For Pushing w/ Obstacles, Object Merging, and Rope Routing tasks, we use an MLP as our dynamics model. For the Object Sorting task, we utilize a GNN as the dynamics model, since the pieces are naturally modeled graph. Below is the detailed information for each task.
Pushing w/ Obstacles. We use four-layer MLP with [128, 256, 256, 128] neurons in each respective layer. The model is trained with an Adam optimizer for epochs, using learning rate of 0.001. A cosine learning rate scheduler is applied to regularize the learning rate. For the model input, we select four keypoints on the object and calculate their relative coordinates to the current pusher position. These coordinates are concatenated with the current pusher action (resulting an input dimension of 10) and input into the model. For the loss function, given the current state and action sequence, the model predicts the next 6 states, and we compute the MSE loss with the ground truth.
30

---

Published as a conference paper at ICLR 2025
Object Merging. We use the same architecture, optimizer, training epochs, and learning rate scheduler as in the Pushing w/ Obstacles setup. For the model input, we select three keypoints for each object and calculate their relative coordinates to the current pusher positions. These coordinates are then concatenated with the current pusher action (resulting in a state dimension of 12) and input into the model. We also use the same loss function in the Pushing w/ Obstacles setup.
Rope Routing. We use two-layer MLP with 128 neurons in each layer. The model is trained with an Adam optimizer for 50 epochs, with a learning rate of 0.001, and a cosine learning rate scheduler to adjust the learning rate. For the model input, we use farthest point sampling to select 10 points on the rope, reordered from closest to farthest from the gripper. We then calculate their relative coordinates both the current and next gripper positions, concatenate these coordinates, and input them into the model. For the loss function, given the current state and action sequence, the model predicts the next states, and we compute the MSE loss with the ground truth.
Object Sorting. We use the same architecture as DPI-Net (Li et al. 2018). The model trained with an Adam optimizer for 15 epochs, with learning rate of 0.001, and cosine learning rate scheduler to adjust the learning rate. For the model input, we construct a fully connected graph neural network using the center position of each piece. We then calculate their relative coordinates to the current and next pusher positions. These coordinates are concatenated as the node embedding and input into the model. For the loss function, given the current state and action sequence, the model predicts the next 6 states, and we compute the MSE loss with the ground truth.
D.4 DEFINITION OF COST FUNCTIONS
In this section, we introduce our cost functions for model-based planning Eq. 1 across different tasks. For every task, we assume the initial and target states 2o and Vtarget are given. We denote the position of the end-effector at time f as Pt. In tasks involving continuous actions like Pushing w/ Obstacles, Object Merging, and Rope Routing, the action u, is defined the movement of the end-effector, P: 1 Ue. and Po is given by the initial configuration. In the task of Object Sorting involving discrete pushing, Pt is given by the action ag as the pusher position before pushing. In settings with obstacles, we set the set of obstacles as O. Each E O has its associated static position and size as Po and s.. Our cost functions are designed to handle discontinuities and constraints introduced by obstacles, and BaB-ND can work effectively on these complex cost functions.
Pushing w/ Obstacles. As introduced before, we formalize the obstacles as penalty terms rather than explicitly introducing them in the dynamics model. Our cost function is defined by cost the goal position plus a penalty cost indicating whether the object or pusher collides with the obstacle. The detailed cost is listed in Eq. 29
Ct c(Ir, we)
= w. 1|+,
Eearger|
+
Σ oEO
(ReLU(s, - -lpp - poll) + ReLU(s, - 1|,r - -oll))
(29)
where ||x, - Turgetll gives the difference between the state at time and the target. I|p:- 1ir--aa Poll and ||,, - Po give the distances between the obstacle and the end-effector and the object, respectively. Two ReLU items yield positive values (penalties) when the pusher or object is located within the obstacle o. W, is weight increasing with time to encourage alignment the target. À is large constant value to avoid any collision. In implementation, x2 is concatenation of positions of keypoints, and ||x, Poll is calculated keypoint- Ideally, er can be optimized to 0 by strong planner with the proper problem configuration.
Object Merging, In this task requiring morgzooizonn planning to manipulate two objects, we do not set obstacles and only consider the difference between the state at every time step and the target. The cost shown in Eq.
we
|x
Fuarget
(30)
Rope Routing. In this task involving a deformable rope, we sample keypoints using Farthest Point Sampling (FPS). Zraget is defined as the target positions of sampled keypoints. The cost is defined in Eq. [3 similar to the one in Pushing w/ Obstacles. Here, two obstacles are introduced to form the fight-fitting slot. In implementation, naively applying such cost does not always achieve our
31

---

Published as a conference paper at ICLR 2025
target of routing the rope into the slot since trajectory greedily translating in the z-direction without lifting may achieve optimality. Hence, we modify the formulation by assigning different weights for different directions y, 2) when calculating a| the lowest cost.
Furget to ensure the desirable trajectory yields
Cr We Fe Frargerll
Σ (ReLU(s, llp. poll) ReLU(s. ||=re Poll)) (31)
Object Sorting. In this task, pusher interacts with cluster of object pieces belonging to different classes. We set zugget as the target position for every class. Additionally. for safety concerns to prevent the pusher from pressing
the object pieces, we introduce obstacles defined the object pieces in the cost as Eq. [2] For each object piece o, its size 8, is set as larger than the actual size in the cost, and its position Po is given by It. The definition of the penalty is similar to that in Pushing w/ Obstacles.
Ct = W4 |10 Tnagert + A
Σ oEO
ReLU |pp: -Po
(32)
D.5 DETAILS OF REAL WORLD DEPLOYMENT
We have four cameras observing the enviromment from the corners the workspace. We implemented task-specific perception modules to determine the object states from the multi-view RGB-D images.
Pushing w/ Obstacles and Object Merging. We use two-level planning framework these two tasks, involving both long-horizon and short-horizon planning. First, given the initial state (so) and pusher position, we perform long-horizon nag-hhoizon open-loop planning to obtain a reference trajectory (so, do, $1, 01, ................................ S. Next, MPPI planner is used as local controller to efficiently track this trajectory. Since the local planning horizon is relatively short, the local controller operates at a higher frequency. In the local planning phase, the reference trajectory is treated Initially, we set 8 as the subgoal and use the local controller to plan local trajectory. Once is reached, 82 is set as the next subgoal. By iterating this process, ultimately reach the final goal state.
queue of subgoals.
For perception, filter the point cloud based color from four cameras, and align it with iterative closest point (ICP) to determine the object states.
Rope Routing. For the Rope Routing task, we observe that the sim-to-real gap relatively small. Therefore, the long-horizon planned trajectory is executed directly in open-loop manner.
For perception, we begin by using Grounding DINO (Liu et al., 2023a) and Segment Anything Model (SAM) (Kirillov et al. 2023) to generate the mask for the rope and extract its corresponding point cloud. Subsequently, we apply farthest point sampling to identify 10 key points on the rope, representing its object state.
Object Sorting. There are relatively large observation changes after each pushing action. This creates noticeable sim-to-real gap for the planned long-horizon trajectory. As result, replan the trajectory after each action.
For perception, filter the point cloud based color from four cameras and use K-means clustering to separate different object pieces.
D.6 HYPERPARAMETERS OF BASELINES
We follow previous works et et al. 2018 2019) to implement gradient descent (GD) for planning and enhance it through hyperparameter tuning of the step size. Specifically, we define a base step size and multiply it by varying ratios to launch independent instances with different step sizes. The best result among all instances is recorded for performance comparison. Similarly, we adapt MPPI (Williams et al. 2017) by tuning its noise level and reward temperature. We also implement the Decentralized Cross- Entropy Method (CEM) (Zhang et al.) 2022c), which enhances CEM using an ensemble of independent instances. The specific hyperparameter settings for these methods are provided in Table T0
32

---

Published as a conference paper at ICLR 2025
Table 10: Hyperparameter setting for baselines
Hyperparameter setting for GD
Hyperparameters
Pushing w/ Obstacles
Object Merging
Rope Routing
Object Sorting
Number of samples
320000
160000 18
50000
24000
Number of iterations
16
16
15
Base step size
0.01
0.01
0.01
0.01
Step size ratios
[0.05, 0.1, 0.25, 0.5, 0.75, 1, 2, 5, 10]
Hyperparameter setting MPPI
Hyperparameters
Pushing w/ Obstacles
Object Merging
Rope Routing
Object Sorting
Number of samples
320000
160000
64000
32000
Number of iterations
20
22
50
18
Base temperature Temperature ratios
20
20
20
50
10.1, 0.5, 1, 1.5, 21
10.1, 0.5, 1.5, 21
[0.1, 0.5, 1, 51
[0.1, 51
Base noise std
0.15
0.15
0.12
0.3
Noise ratios
10.1, 0.5, 5, 1, 1.5, 2]
10.1. 0.5, 1, 1.5,
[0.1, 0.5, 1, 5]
[0.5, 1, 1.5]
(c) Hyperparameter setting for CEM
Hyperparameters
Pushing w/ Obstacles
Object Merging
Rope Routing
Object Sorting
Number of samples
320000
160000
64000
32000
Number of iterations
20
55
50
16
Jitter item
0.001
0.0005
0,001
0.0005
Number of elites
10
10
10
10
Number of agents
10
10
10
10
D.7 IMPLEMENTATION DETAILS OF CONVENTIONAL MOTION PLANNING APPROACHES
RRT. As shown in Algorithm in each step, sample target state and find the nearest node in the RRT tree. We sample 1000 actions and use the dynamics model to predict 1000 future states. We select the state that is closest to the sampled target and does collide with obstacles, then add it to the tree. We allow it to plan for 60 seconds, during which it can expand tree with about 4000 nodes (NVax 4000). To avoid getting stuck local minima, we randomly sample target states 50% of the time, and for the other 50%, we select the goal state as the target.
PRM. shown in Algorithm 5 the PRM construction algorithm generates probabilistic roadmap by sampling N pairs of object states and pusher positions from the search space, adding these pairs as nodes, and connecting nodes within a defined threshold Here, we set N 100K and 0.15. The roadmap is represented contains edges representing feasible connections. The planning over PRM Algorithm 6 uses this roadmap find a path from the initial state the goal state. It first integrates the initial state into the graph and connects to nearby nodes, removes any nodes and edges colliding with obstacles, and applies A search find optimal path.
graph G E"). where V includes the sampled nodes, and E
33

---

Published as a conference paper at ICLR 2025
Algorithm 4 Rapidly-EEploring Random Tree (RRT)
1: Input: Initial state zo, goal state Zgoal, search space A' (A' is object state space), maximum iterations Nmax. action upper and lower bounds {u, 21, threshold 6
2: Output: A path from To to goal or failure
3: Initialize tree T with root node To
4: for i = 1 to Nmxx do
5: Sample a random state Frand from X
6: Find the nearest node 2neer in T Frand
7:
Sample 1000 actions within [T, J as a set 2 and compute the corresponding next states Xnew faan [aan(=nearr 2))
8:
Select the nearest, collision-free next state from Xnew as Unew
9:
Add Fnew T with an edge from Feear if Inow is within 5 of Zgoal then
10:
Add gigoal to T with an edge from Fnew return Path from Tp to Zgual in T
12:
13: return Failure (No valid path found within Nax iterations)
Algorithm 5 Probabilistic Roadmap (PRM) Construction
1: Input: Search space {X'' P) (A': object state space, P: pusher position space), number of nodes
N, connection threshold 8
2: Output: A constructed PRM G (V, EE)
3: Initialize the roadmap G (V, E)) with V and E = 0
4: Randomly sample N pairs (z, p) from {X
5: Add the sampled pairs as nodes G: = {or < N}. where eq = (2 ps)
6: for = 1 to N do
7: for j = 1 to N do
8: if + then
9:
Compute action Pj P; Predict the next state Zgew fayn (2), if' distance( new 2z)) < then
11:
Add an edge Cij = {w= + Uy to
13: return G= = GVVVE)
Algorithm 6 Planning over PRM
Input: Initial state Tinit, initial pusher position Pinit: goal state Tyoal, obstacle space (Natas Pota } constructed PRM G = (V, E), connection threshold 8
2: Output: A path from Tinit to Zgooll or failure
3: Add (Jinits Pinit) to V
4: for each node Uy E V do
5: Compute action = Pý Punit
6: Predict the next state Fnew = fayn (Finits 2))
7: if distance(Vinww x.2) < 8 then
8: Add an edge (Vinit - m. to F.
9: Remove all edges and nodes in G that collide with obstacles (Notss Potn)
10: Use the A search algorithm to find path from Vinic = (Xinit, Pinit) to I Fgaal in G
Identify the node Unearest closest Egoal
12: Extract the path from Vinit to Uncarest
return the extracted path
34


Reviews:
[{"review_id": "FA3hxkmEkD", "reviewer": "Reviewer_ci99", "summary": "This paper presents BaB-ND, a GPU-accelerated Branch-and-Bound framework designed for long-horizon motion planning in robotic manipulation tasks that require trajectory optimization over neural dynamics models. Addressing challenges associated with non-linearity in neural network dynamics, BaB-ND utilizes a branching heuristic to divide the action space into sub-domains and a modified bound propagation method (inspired by neural verification methods like α, β-CROWN) to efficiently prune non-promising regions. This systematic approach allows BaB-ND to outperform some existing methods in tasks like object pushing, sorting, and rope manipulation, where contact-rich dynamics and high-dimensional action spaces are involved. The framework supports diverse neural architectures (e.g., MLPs, GNNs) and demonstrates scalability and superior planning quality in both simulated and real-world settings.\n\nOverall, this work presents a novel idea, with a clear presentation, and I could increase my rating if my questions are covered during the rebuttal phase.", "questions": "- In the supplementary video, it is stated that planning time / horizon is the same for all methods. How would the performance of the baseline methods change if we increase the planning time? In the experiments, it is shown that BaB-ND outperforms other methods in almost all tasks. May it be the case that other methods have not yet found their optimal solutions?\n\n- Can you prune enough sub-domains so that the algorithm does not end up sampling exhaustively? In which cases (or for which type of objective functions) can you provide an assurance that enough sub-domains will be pruned? Can you give a theoretical insight into it? More generally, since the proposed method relies on sampling, in which cases it performs poorly compared to the non-sampling methods?\n\n- Why isn't there any sampling-based method for scalability comparison? It is expected for a sampling-based method to be more scalable compared to MIP (?).\n\n- How is the close-loop control achieved and feedback received?  \n\n- data collection: how are the variations (assuming there are) of the task achieved? \n\n- Fig.6: consistency on the plots is preferred. For rope routing, cost performance is reported for the open-loop scenario, whereas success rate is reported for the closed-loop. Why is it so?\n\n- Could the authors discuss potential modifications for real-time application?\n\n- Could the authors expand on hyperparameter sensitivity?\n\n- Are there potential optimizations for early-stopping propagation in bound calculations? The current early-stopping approach helps avoid excessive error from deep-layer propagation, but it may not achieve the tightest bounds possible. Any chance on adative stopping based on some criteria/threshold?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "**Originality**:\nThis paper is quite original in its approach to motion planning by adapting the branch-and-bound (BaB) algorithm for neural dynamics (ND) models. Unlike existing methods, which typically rely on sampling-based or gradient descent approaches, this work creatively applies a modified bound propagation technique inspired by neural network verification algorithms, specifically the α,β-CROWN method. This adaptation is novel for addressing the inherent non-linearity and complexity of neural dynamics in long-horizon planning tasks. It might set a new direction in combining machine learning verification methods with motion planning.\n\n**Quality**:\nThe research demonstrates rigor and of high-quality.\n- Good amount of testing across diverse scenarios (planar pushing, object sorting, rope routing)\n- Performance advantages over existing methods like Mixed-Integer Programming and sampling-based approaches\n- Robust handling of complex, contact-rich environments\n- The video covers the experiments and demonstrates the improvement over alternative methods\n\n**Clarity**\nThe presentation of the paper is good.\n- Well-organized structure and methodology explanation\n- Effective use of visual aids and diagrams\n- The step-by-step example of applying BaB on a 1D problem is particularly helpful\n- (mostly) clear differentiation between BaB-ND and traditional verification methods\n\n**Significance**\nThe work is important in several fronts.\n- It addresses a critical challenge in robotic motion planning: managing complex, long-horizon tasks with contact dynamics\n- The provided solution is -somewhat- scalable, when compared to an existing method\n- Different neural architectures (MLPs to graph neural networks) are used, which demonstrates its applicability on different architectures, and hence different types of problems.", "weaknesses": "There are several weaknesses/limitations of the work:\n\n**Limited Task Diversity**:\n- Current evaluation focuses primarily on basic manipulation tasks (pick-and-place and pushing, relying on planar motions)\n- Framework's applicability remains uncertain for:\n  - Complex 3D manipulation with critical contact points and impact forces\n  - Highly constrained environments requiring precise 3D motions of the full robot kinematic chain\n  - e.g., Real-world scenarios like book reordering across shelves\n\n**scalability**: (somewhat similar to the comment above) \n- Despite GPU acceleration, potential bottlenecks exist:\n  - Computationally intensive bound propagation\n  - Extensive branching requirements\n  - Challenges for real-time applications\n- Paper would benefit from:\n  - Discussion of potential optimizations for real-time use\n  - Experiments measuring latency in time-sensitive scenarios\n  - Strategies for reducing computational overhead\n\n**Lack of Comparative Analysis**:  I acknowledge that it'd be out of scope, but still some remarks:\n- Comparisons with traditional motion planners that use full state information might be interesting, especially considering the somewhat long runtime of BaB-ND + the training time for each task. Overall, that could provide a better context regarding trade-offs between:\n  - BaB-ND's computational costs (including training time)\n  - Performance of conventional motion planning approaches\n  - Overall efficiency in practical applications\n\n**Insufficient Hyperparameter Analysis**: The BaB-ND framework includes various hyperparameters, such as the choice of branching heuristic, bound propagation depth, and sampling rates. However, there is limited discussion or analysis on how these hyperparameters influence performance across different tasks or neural architectures. Since tuning these parameters is likely critical for achieving optimal results in different scenarios, an expanded study on hyperparameter sensitivity would be beneficial. For instance, sensitivity experiments could provide insights into the trade-offs between solution quality and computational efficiency, guiding practical implementation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "0ztTK8MsAf", "reviewer": "Reviewer_bbRD", "summary": "The paper presents a GPU-accelerated Branch-and-Bound (BaB) framework for planning in robotic tasks using neural dynamics models, employing α,β-CROWN for bound propagation. The framework supports various neural network architectures, such as MLPs and GNNs, but the model requires customization based on different scenarios, selecting specific architectures for tasks like object sorting and rope routing​.", "questions": "1. 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?\n\n2. Would including broader baselines from other methodologies provide a more comprehensive benchmark for evaluating the framework? Stronger comparisons could help clarify its extensibility.\n\n3. 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.\n\n4. Since each scenario requires a custom-designed network, how practical is this approach for real-world applications? What are the estimated time and resource requirements for designing and tuning a model for a new scenario, and could this affect the framework’s usability in resource-limited settings?\n\n5. Does the current setup introduce complexity that might hinder practical implementation? If an optimal network is not chosen, how significantly would this impact performance, and are there ways to mitigate this dependency on precise network selection?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The framework leverages bound propagation from neural network verification (α,β-CROWN) to optimize neural dynamics in planning tasks. By structuring the search space into sub-domains and pruning non-promising regions, it shows potential for handling high-dimensional, complex scenarios. \n2. BaB-ND effectively focuses on feasible solutions over global optimization, adapting BaB methods for motion planning in complex, contact-rich robotic tasks. It supports diverse neural architectures, such as MLPs and GNNs.\n3. With GPU acceleration, BaB-ND hints at the potential to manage extended planning horizons and complex models", "weaknesses": "1. The code URL provided in the paper is currently unavailable.\n2. 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.\n3. Most experiments are conducted in 2D scenarios, and even the 3D rope manipulation task appears relatively simple, which raises questions about the framework's scalability to more complex 3D environments and interactions, especially with deformable objects.\n4. Although a generalized pipeline is proposed, the framework’s actual scalability across more diverse and complex tasks remains unproven. The comparisons are mostly limited to similar methods, without broader baselines that might better validate its extensibility and robustness.\n5. The current experiments focus on relatively simple tasks, leaving uncertainty about the framework’s effectiveness in more complex or varied scenarios. Custom neural network design for each task could make adaptation time-consuming and resource-intensive.\n6. The framework’s success is sensitive to selecting suitable network architectures for each task. Without careful selection, mismatches could lead to substantial inefficiencies or even failure, indicating a high demand for expert design and tuning.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "UYmcvXtE5Y", "reviewer": "Reviewer_kMxQ", "summary": "The paper presents an approach for solving complex long-horizon motion planning tasks using a GPU-accelerated branch-and-bound (BaB) framework. The primary innovation is the integration of bound propagation methods inspired by neural network verification, namely CROWN, to handle the non-linearity of neural dynamics models. This method allows for efficient partitioning of the search space and systematic pruning of sub-domains that cannot yield better solutions, focusing the search on promising areas. The authors demonstrate that BaB-ND outperforms existing sampling-based and mixed-integer programming (MIP) methods in handling contact-rich manipulation tasks like planar pushing and object routing. The framework supports various neural architectures and shows scalability, making it applicable to real-world robotic planning problems.", "questions": "- Can you provide more details on the bounding step of the method? How are bounds estimated in a way that ensures meaningful pruning of sub-domains in practical robotic tasks?\n- 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?\n- How is GPU acceleration implemented in your approach, and what specific parts of the framework benefit from it? Could you provide runtime comparisons with and without GPU acceleration?\n- Why was Mixed-Integer Programming (MIP) not used as a baseline for comparing the quality of the solutions? Similarly, why were methods like MPPI and CEM not included for runtime performance comparisons?\n- Have you considered performing an ablation study to show the contribution of individual components, such as the branching heuristic or specific modifications to the bound propagation method?\n- Could you provide more details on the novelty of the approach from a machine learning point of view ?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- The paper tackles an important and challenging problems in robot motion planning, especially in scenarios involving long-horizon, contact-rich tasks.\n- The paper provides a solid overview of related work in neural dynamics, motion planning, and neural network verification, positioning the contribution well within the context of existing research.\n- The use of a branch-and-bound (BaB) framework integrated with bound propagation methods adapted from neural network verification shows potential for enhancing motion planning capabilities.\n- The proposed method is designed to support various neural network architectures, allowing applicability to different robotic models and tasks.\n- The experiments are complex and challenging, showcasing the method’s applicability to real-world scenarios such as object routing and planar pushing.", "weaknesses": "- The method section is highly abstracted, which leaves readers unable to connect theoretical concepts such as the objective function, inputs, bounds, and sub-domains to practical robotic manipulation problems. Explanations remain too abstract and disconnected from practical robotic tasks. Also, the paper does not detail the method sufficiently, particularly the bounding step, making it difficult for readers to understand the full implementation of the approach.\n- Understanding the methodology relies heavily on prior familiarity with the CROWN method, making the paper less accessible to readers who are not already experts in neural network verification techniques.\n- Although GPU acceleration is mentioned as a key advantage, the paper does not provide sufficient detail or evidence to demonstrate how GPU acceleration is implemented or its specific benefits.\n- While the paper compares performance against sampling-based methods, the absence of Mixed-Integer Programming (MIP) as a baseline for evaluating the optimality of solutions is a significant oversight. Additionally, runtime performance is not benchmarked against methods like MPPI and CEM.\n- The paper does not include an ablation study to show the importance of individual components or design choices in the proposed method, leaving gaps in understanding the contribution of each element.\n- From a robotics perspective the use of a branch-and-bound framework with neural dynamics in contact-rich robotic manipulation seems novel, however, the novelty and contribution from a machine learning perspective is not clear.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "AKHc3tjDSI", "reviewer": "Reviewer_U2wt", "summary": "This work introduces a divide-and-conquer approach for planning long-horizon manipulation trajectories. The method relies on a dynamics function trained on simulated data and operates through branching, bounding, and searching.", "questions": "What are the definitions of open-loop and closed-loop performance? They are unclear, making the results in Figure 5 difficult to interpret.\n\nFor 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?\n\nIs it possible to extend the current method to scenarios where obstacles or goal regions are dynamic?\n\nWhat is the action space or control signal for most tasks? It appears to be limited to translations in the 2D plane.\n\nWith a 20-step planning horizon, how many actions does the controller execute? What is the planner’s operating frequency?\n\nIt 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?", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The writing is clear and well-structured, and the appendix contents are helpful.\n\nThe concepts and formulation are well-defined, and the 1D toy example effectively validates the idea.\n\nThe method includes extensive experiments, both simulated and real-world, with comparisons to several baseline methods.", "weaknesses": "The specific novelty and distinctions of the proposed method compared to neural network verifiers are unclear, beyond its focus on model-based trajectory planning.\n\nThe robot experiments lack clarity, with important details omitted.\n\nThe limitations and potential future directions of this work are not discussed.\n\nThe learned dynamics function relies on a well-designed simulator, which may limit the scalability of this method to a wide variety of tasks.\n\nThe method assumes static initial poses for obstacles and goal regions, making it challenging to adapt to dynamic changes.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)