{"id":"63dddfb5-6baa-4e57-8059-8c3199b959d6","arxiv_id":"2411.15651","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":6,"one_line_summary":"Reusing the entire previous subtree in receding horizon tree search improves sample efficiency and final planning performance for real-time robot control, demonstrated on a nonprehensile manipulation task.","lead":"This paper introduces Model Predictive Trees, a planning algorithm that reuses the best branches of its previous search tree when replanning, so a robot can plan faster with fewer simulations. It shows large speedups over standard hotstarting methods on a car pushing a barrel through obstacles, with a theoretical error bound for reused trees under changing dynamics.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The stability guarantee (Thm. 4) is not validated in the hardware regime because Assumption 2 is violated; the reset threshold, not the reuse analysis, prevents divergence.","rationale":"The reader's weakest_assumption identifies Assumption 2 as the load-bearing premise, and I agree. The central claim has two parts: (1) reusing the entire selected subtree improves search quality and sample efficiency, and (2) the method remains stable under slowly changing dynamics with the Theorem 4 bound. The first part is supported by the numerical experiments, especially the 29.9% improvement over CEM-Reuse and the sample-efficiency gap (L=180 vs. 3000+). The second part is the place where the argument is least secure. In the hardware experiment, the dynamics estimate is held constant while the real contact physics contain friction and deformation; the three reported tree resets show that the assumed slow-variation and eps-accurate-estimate conditions are not met. Because the reset threshold is absent from Theorem 4, the theoretical guarantee does not explain the hardware result. This is not an accusation of dishonesty: the paper openly reports the resets and the unmodeled dynamics. It is a limitation that should be stated more carefully and, ideally, probed by an experiment that isolates the reset mechanism. The proposed concrete test, disabling resets and measuring the actual eta and eps, would directly determine whether the stability in the demonstrated regime comes from the theoretical bound or from the heuristic. If the method diverges without resets, the paper should either weaken the claim that Theorem 4 covers the demonstrated setting or extend the analysis to include the reset condition. Either way, the algorithmic contribution remains credible and worth publishing, so the reader's CONDITIONAL verdict is appropriate; I do not recommend changing it.","tokens_in":58,"tokens_out":16774,"duration_ms":230149,"concrete_test":"Run the hardware task, or a high-fidelity simulation with the same constant dynamics estimate and contact model, with the tree reset threshold tau set to infinity (i.e., disable resets) while keeping all other parameters fixed. If the planner diverges or fails to complete the pushing task without resets, then the reset mechanism is load-bearing in the demonstrated regime and Theorem 4's Assumption 2 is not satisfied there. Complement this by recording per-step values of ||d - dhat|| and ||d(k+1) - d(k)|| along the executed trajectory to estimate eps and eta, and check whether Eq. (10) alone would predict the observed tracking error.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's central claim includes a theoretical stability guarantee for subtree reuse: Theorem 4 bounds steady-state tracking error by sqrt(mbar/m)((K+1)eta+eps)/(1-alpha) under Assumption 2, which requires the disturbance d to change slowly (eta) and the dynamics estimate to be eps-accurate. This bound is what justifies reuse of a subtree built with stale dynamics estimates. However, the hardware demonstration in Sec. IV-E uses a constant estimated dynamics model while the real contact physics include friction, deformation, and other unmodeled effects; the paper reports three tree resets triggered by mismatch in theta and barrel position. The reset mechanism (Algorithm 1, lines 14-16, tau=0.5) discards the reused subtree when the simulated and physical states diverge, and this mechanism appears nowhere in Theorem 4's bound. Consequently, in the most challenging demonstrated setting, the observed stability is attributable to the reset heuristic rather than to the theoretical analysis of tree reuse. In simulation, if the planner uses the true contact model, then eta=eps=0 and the theorem reduces to a trivial statement, so the empirical results do not exercise the slow-dynamics regime the theory addresses. This is a real gap between the theoretical claim and the demonstrated regime, though it is openly acknowledged in the hardware section and does not undermine the algorithmic contribution of subtree reuse for sample efficiency.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces Model Predictive Trees (MPT), a receding-horizon tree search planner that reuses the entire selected subtree from the previous planning iteration rather than only the best trajectory. The authors provide a contraction-theoretic analysis (Theorem 3 and Theorem 4) intended to bound the steady-state tracking error of the closed-loop system when the dynamics estimate is stale, and they report numerical experiments against UCT, CEM, and CEM-Reuse, as well as a hardware demonstration on an autonomous vehicle pushing a barrel. The central claims are that subtree reuse improves sample efficiency and solution quality, and that the induced tracking error is bounded under slowly time-varying disturbances.","tokens_in":11715,"tokens_out":12332,"duration_ms":107361,"significance":"If the theoretical guarantee and the experimental results hold, the paper makes a useful contribution to receding-horizon planning: the idea of reusing an entire subtree, including low-value branches, is a sensible and potentially important extension of hotstarting. The sample-efficiency results are striking (e.g., MPT reaching value 80 with L=180 versus 3000+ for CEM-Reuse), and the hardware demonstration adds credibility to the practical relevance. The contraction-based stability analysis is a reasonable framework, and the proof of Theorem 3 appears sound under its assumptions. However, the main theoretical result (Theorem 4) has a gap concerning the mismatch between the model used by the controller and the model used to build the reused tree, and the theory does not account for the reset mechanism that is active in the hardware experiment. These issues prevent the paper from fully establishing both the stability guarantee and its empirical validation in the slow-dynamics regime.","major_comments":[{"comment":"The proof of Theorem 4 assumes that the desired trajectory satisfies the dynamics with the past estimate \\hat{d}_i, but the controller in Algorithm 1, line 10, uses the current estimate \\hat{F}_k (i.e., \\hat{d}_k).  Consequently, the desired trajectory is not a solution of the nominal system used in the feedback law, and the perturbation relative to that system includes the term \\hat{d}_k(x^d_k,u^d_{k+1}) - \\hat{d}_i(x^d_k,u^d_{k+1}), which is not accounted for in the bound (K+1)η+ε.  Without an additional assumption that the controller uses the same old estimate \\hat{d}_i, or a bound on the drift of the estimates themselves, Eq. (10) does not bound the tracking error of the implemented algorithm.  This is load-bearing for the claimed stability guarantee.","section":"Sec. III-B, Theorem 4 and Algorithm 1"},{"comment":"The reset threshold τ is not present in the theoretical analysis.  The hardware experiment reports three tree resets when the simulated and physical states diverge, and the paper acknowledges that Assumption 2 is violated due to friction, deformation, and other unmodeled effects.  Thus, in the most challenging demonstrated setting, the stability is attributable to the reset heuristic rather than to the reuse analysis, and Theorem 4 provides no condition under which resets are needed or a bound on their effect.  The authors should either extend the theory to incorporate the reset mechanism or explicitly state that Theorem 4 applies only in the no-reset regime, and provide a separate experimental validation of that regime.","section":"Sec. IV-E and Algorithm 1, lines 14-16"},{"comment":"The numerical experiments appear to use the same contact model for both the planner and the simulator, with no time-varying disturbance injected.  If η=ε=0, then Theorem 4's bound becomes trivial and the experiments do not exercise the slowly-varying-dynamics regime that the theory addresses.  The hardware experiment, by contrast, violates Assumption 2.  To support the theoretical claim, the paper should include a simulation study with a deliberately time-varying disturbance that satisfies Assumption 2 and show that the observed tracking error respects the predicted (K+1)η+ε dependence.","section":"Sec. IV-C, IV-D, and Theorem 4"},{"comment":"The statement that 'state-of-the-art baselines are either too sample-inefficient or unable to plan through the dynamics' is not supported by any experiment: no baseline is run on the hardware testbed and no quantitative comparison is provided for the hardware task.  This claim exceeds the evidence presented and should be removed or backed by comparative data.","section":"Sec. IV-E"}],"minor_comments":[{"comment":"The notation for the uniform bounds of the contraction metric is unclear: the text writes 'm In ⪯ M ⪯ mIn' with the same symbol m for both bounds, which makes the factor sqrt(m/m) in Eq. (10) appear to be 1.  Please use distinct symbols, e.g., \\underline{m} and \\overline{m}, throughout.","section":"Sec. III, notation"},{"comment":"The search depth K is defined as the depth of the tree, but the UCT search loop runs for j = k, ..., K+k, which creates K+1 levels of nodes.  This off-by-one inconsistency makes the timing argument in the proof of Theorem 4 harder to follow; please align the pseudocode and the theorem's indexing.","section":"Algorithm 1 and Sec. II-B"},{"comment":"The x-axis range of Fig. 4 is not specified, and the claim that UCT requires '>30000' simulations to reach V=80 is only meaningful if the reader knows the extent of the tested range.  Please provide the axis limits or state that UCT did not reach V=80 within the range considered.","section":"Fig. 4 and Sec. IV-D"},{"comment":"The row 'Reuse % Improvement' reports 124% for MPT, but the comparison baseline is not stated in the table caption.  It is presumably UCT, but this should be made explicit to avoid confusion.","section":"Table 1"},{"comment":"The reference [1] for UCT is cited as guaranteeing convergence to the optimal trajectory as runtime increases; the precise conditions under which this guarantee holds should be stated or cited more carefully.","section":"Sec. I-A"},{"comment":"The code link states that code 'will be made available'; the paper would be stronger if the code were already available at the time of submission, or if the statement indicated the planned release date.","section":"Abstract and Sec. V"}],"recommendation":"major_revision","confidential_remarks":"The paper's core algorithmic idea—reusing the whole selected subtree—is novel and the simulation results are promising, but the theoretical contribution is not yet fully connected to the implemented algorithm.  The main gap is Theorem 4's proof, which silently assumes the controller's nominal model matches the old estimate used to build the tree, contradicting Algorithm 1's use of the current estimate.  Also, the reset mechanism is essential in hardware but absent from the theory, and the numerical experiments do not test the slow-dynamics regime.  These are fixable with additional analysis and experiments, so I recommend major revision rather than rejection.  The related-work citations include several from the authors' own group ([8], [9], [23], [24]), which is not problematic per se but should not give the impression of over-reliance on self-citation."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The core idea here is genuinely worth your time: instead of hotstarting with the single best trajectory, MPT carries over the entire selected subtree from the previous planning iteration. That is a clean, sensible extension of existing reuse strategies (CEM/MPPI hotstarting, Schneider's recursive MCTS), and the paper shows it pays off: 29.9% higher value than CEM-Reuse, and reaching V=80 with L=180 versus 3000+ for CEM-Reuse. The hardware demo on the Ackermann car pushing a barrel through obstacles is real, runs at 5 Hz onboard a Jetson Orin, and exhibits a nice repositioning behavior that would be hard to get with the baselines. The work is also honest about the reset mechanism and the model mismatch in hardware.\n\nThe theory is a straightforward application of contraction theory. Theorem 3 is the standard DARE-based linearized feedback result, and Theorem 4 is a perturbation bound that honestly earns its place as a design guideline: tree depth K trades against disturbance timescale eta. The bound itself is fine, though the proof's indexing between physical and simulation time is a bit sloppy, and the statement that the maximal error is (K+1)eta+eps is only valid if you reuse a branch that is exactly K+1 steps old, which the argument gestures at but does not set up cleanly. Not a fatal flaw, but a referee should ask for a cleaner statement.\n\nThe bigger soft spot is the gap between theory and experiments. In simulation the planner uses the true model, so eta=eps=0 and Theorem 4's bound is vacuous. In hardware the contact dynamics clearly violate Assumption 2, and the paper openly says three tree resets were triggered; those resets, not the contraction bound, are what keep the system stable. So the theory is not really validated in the regime where it is nontrivial. The authors acknowledge this in the hardware section, and it does not undermine the empirical case for subtree reuse as a sample-efficiency technique, but it does mean the stability guarantee is more of a heuristic justification than a tested prediction.\n\nMinor issues: code is promised but not yet public, and a few hyperparameters (epsilon in UCT, the reward normalizer D, and the exact Q, R used) are not reported. All fixable in a revision.\n\nThis is a solid conference or journal submission. The algorithmic contribution is real, the experiments are meaningful, and the limitations are acknowledged. I would send it to peer review. Absolutely worth reading for anyone working on sample-based receding-horizon planning or contact-rich manipulation.","headline":"Subtree reuse is a real step forward for receding-horizon tree search, and the paper earns a serious review despite the theory being only loosely tied to the hardware regime.","tokens_in":12311,"tokens_out":1215,"would_cite":true,"duration_ms":13719,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper establishes that reusing the whole selected search tree from the previous planning round, rather than just the best trajectory, improves planning quality and sample efficiency, with a proven error bound when dynamics drift slowly.","keywords":["model predictive trees","receding horizon planning","Monte Carlo tree search","tree reuse","sample efficiency","contraction theory","nonprehensile manipulation","cross-entropy motion planning"],"falsifier":"Take a testbed where the per-step disturbance drift $\\eta$ can be set externally, hold the tree depth $K$ fixed, and measure whether the steady-state tracking error follows $\\sqrt{\\bar{m}/m}\\,((K+1)\\eta+\\epsilon)/(1-\\alpha)$; a second check is to replace the reused subtree with a compact summary of its node values and see whether the reported $29.9\\%$ advantage over hotstarting disappears.","tokens_in":11224,"feed_emoji":"🚗","tokens_out":9609,"duration_ms":81023,"temperature":0.7,"pith_summary":"The paper tries to establish that a receding-horizon planner can get much more from its past computation by reusing the entire selected subtree of the previous search instead of compressing the previous solution into a single hotstart trajectory. The proposed algorithm, Model Predictive Trees (MPT), keeps the trimmed subtree as the root of the next search, so rollouts are guided away from low-value regions and concentrated on refining high-value branches. The authors support the method with a stability analysis: when the true dynamics drift slowly and the online estimate is $\\epsilon$-accurate, the steady-state tracking error stays bounded by $\\sqrt{\\bar{m}/m}\\,((K+1)\\eta+\\epsilon)/(1-\\alpha)$, which quantifies the tradeoff between search depth and the timescale of the dynamics change. In simulation, MPT reaches a cumulative value of 80 with about 180 simulations where hotstarting cross-entropy methods need thousands, and it completes a real-time nonprehensile pushing task on hardware.","feed_headline":"Reusing the whole search tree lifts planner value by 29.9%","feed_subtitle":"Keeping the whole subtree makes replanning sample-efficient, with a stability bound for slow dynamics.","key_machinery":"The machinery pairs UCT tree search with a contraction-theoretic tracking controller. UCT builds a decision tree by $L$ fixed-depth rollouts, selecting child nodes with the upper-confidence-bound score $c.V/c.N + \\varepsilon\\sqrt{\\log(p.N)/c.N}$. The novel piece is the trimming operation that makes the previous iteration's best child the next root, preserving the whole subtree. Stability is supplied by a discrete-time Riccati feedback law $u_{k+1}=u^d_{k+1}-K(x_k-x^d_k)$ whose gain $K=(R+B^\\top M B)^{-1}B^\\top M A$ solves a Discrete Algebraic Riccati Equation; contraction of the closed loop gives the error bound that ties reuse depth $K$ to the disturbance drift rate $\\eta$. The tree reset threshold $\\tau$ is the safety valve that discards the reused tree when simulated and physical states diverge beyond a set tolerance.","core_discovery":"The central claim is that tree reuse should be structural rather than summary-based. Existing sampling-based receding-horizon solvers such as cross-entropy motion planning keep only the best trajectory (or the mean of elite samples) from the previous solve; MPT instead carries over the entire optimal subtree, so the next UCT search starts with a rich set of evaluated nodes. The paper proves (Theorem 4) that this reuse does not destabilize the closed loop: under the assumption that the disturbance changes by at most $\\eta$ per time step and the dynamics estimate is within $\\epsilon$, the steady-state tracking error is at most $\\sqrt{\\bar{m}/m}\\,((K+1)\\eta+\\epsilon)/(1-\\alpha)$, where $K$ is the search depth and $\\alpha$ is the contraction rate of a Riccati feedback controller. The bound makes the limitation explicit: the deeper the reused tree, the more out-of-date the dynamics estimates inside it, so depth must be chosen relative to how fast the dynamics drift. In the nonprehensile pushing experiments, the reuse policy yields a $29.9\\%$ higher average value than the best hotstarting baseline and reaches a value of 80 with $L=180$ simulations, versus more than 3000 for the hotstarting cross-entropy baseline.","pith_inferences":["An extension the paper leaves implicit is to make search depth adaptive: because Eq. (10) links admissible $K$ to the drift rate $\\eta$, a planner that shortens its tree when the dynamics are changing fast and lengthens it when they are quiet would directly exploit the tradeoff.","The same reuse logic could apply to learned dynamics or value models: the $\\epsilon$ term already accounts for estimation error, so replacing the fixed dynamics estimate with an online learner would change the shape of the bound without removing the need for it.","The reported advantage is over a baseline that summarizes the previous solution; the paper does not test whether a cheaper summary, such as keeping a handful of elite trajectories, would capture much of the same benefit, so the marginal value of full subtree reuse versus partial reuse is not yet isolated."],"forward_implications":["At a representative initial condition, MPT reaches a cumulative value of 80 with about $L=180$ simulations per iteration, whereas the hotstarting cross-entropy baseline needs about $L=3000$ and plain UCT does not catch up within 30,000, so the reuse rule is what buys sample efficiency.","The bound in Eq. (10) is a tuning rule: given a desired steady-state error, the admissible search depth $K$ shrinks as the disturbance drift rate $\\eta$ grows, so a planner can set depth from an online estimate of dynamics drift.","Because the entire subtree is kept, the next search inherits both high-value branches to refine and low-value branches to avoid, which concentrates the simulation budget and explains the much lower variance in value estimates seen in Fig. 4.","The tree reset threshold $\\tau$ is the practical complement to the theory: when simulated and physical states diverge, discarding the tree restores consistency, bounding the damage from unmodeled dynamics at the cost of lost reuse."],"supporting_citations":[{"why":"supplies the UCT algorithm whose upper-confidence-bound selection and convergence guarantee the MPT search is built on.","marker":"[1]"},{"why":"provides the discrete-time contraction theory results and perturbation bound that the steady-state error analysis relies on.","marker":"[24]"},{"why":"gives the existence condition for the Discrete Algebraic Riccati Equation solution used to compute the stabilizing feedback gain.","marker":"[25]"},{"why":"defines the cross-entropy motion planning baseline that MPT is compared against and that the CEM-Reuse hotstarting variant extends.","marker":"[10]"},{"why":"supplies the linear complementarity contact model used to simulate the nonprehensile pushing dynamics in the experiments.","marker":"[19]"}],"fun_headline_variants":["Tree reuse lifts replanning value by 29.9%","Reuse whole search tree, boost sample efficiency","MPT: Recycle the whole tree for planning gains","Whole-subtree reuse: sample-efficient receding horizon","Reusing the whole tree beats hotstart by 29.9%"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the unknown gap between model and reality changes slowly and is estimated accurately, because if either fails the tracking bound grows and, as in the hardware contact experiment, the tree-reset threshold rather than the theory is what prevents divergence.","fun_headline_variants_meta":{"raw":{"variants":["Tree reuse lifts replanning value by 29.9%","Reuse whole search tree, boost sample efficiency","MPT: Recycle the whole tree for planning gains","Whole-subtree reuse: sample-efficient receding horizon","Reusing the whole tree beats hotstart by 29.9%"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000597,"raw_usage":{"total_tokens":2799,"prompt_tokens":960,"completion_tokens":1839,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":576,"completion_tokens_details":{"reasoning_tokens":1756}},"tokens_in":576,"tokens_out":1839,"duration_ms":12248,"temperature":1.0,"reasoning_tokens":1756,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T14:04:27.679886+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a testbed where the per-step disturbance drift $\\eta$ can be set externally, hold the tree depth $K$ fixed, and measure whether the steady-state tracking error follows $\\sqrt{\\bar{m}/m}\\,((K+1)\\eta+\\epsilon)/(1-\\alpha)$; a second check is to replace the reused subtree with a compact summary of its node values and see whether the reported $29.9\\%$ advantage over hotstarting disappears.","supporting_citations":[{"cited_title":"Improved monte-carlo search,","cited_arxiv_id":null,"evidence_quote":"supplies the UCT algorithm whose upper-confidence-bound selection and convergence guarantee the MPT search is built on."},{"cited_title":"Contraction theory for nonlinear stability analysis and learning-based control: A tutorial overview,","cited_arxiv_id":null,"evidence_quote":"provides the discrete-time contraction theory results and perturbation bound that the steady-state error analysis relies on."},{"cited_title":"Existence condition on solutions to the algebraic riccati equation,","cited_arxiv_id":null,"evidence_quote":"gives the existence condition for the Discrete Algebraic Riccati Equation solution used to compute the stabilizing feedback gain."},{"cited_title":"Cross-entropy motion planning,","cited_arxiv_id":null,"evidence_quote":"defines the cross-entropy motion planning baseline that MPT is compared against and that the CEM-Reuse hotstarting variant extends."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"supplies the linear complementarity contact model used to simulate the nonprehensile pushing dynamics in the experiments."}],"review_version":1}