Pith. sign in

REVIEW 2 major objections 4 minor 120 references

Monte Carlo Tree Search with Spectral Expansion for Planning with Dynamical Systems

T0 review · 2 major / 4 minor · reviewed 2026-08-11 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read SETS, a Monte Carlo tree search that branches along natural motion modes, converges to a bounded-error approximation of the globally optimal plan for continuous deterministic differentiable MDPs.

desk verdict SETS is a strong, genuinely new spectral MCTS planner whose central convergence guarantee is currently disconnected from the implementation by a likely c2/c3 typo; with that fixed, the paper is a solid advance. read the letter →

arxiv 2412.11270 v1 pith:U5TLXF7Q submitted 2024-12-15 cs.RO

Benjamin Riviere , John Lathrop , Soon-Jo Chung This is my paper · ORCID
classification cs.RO
keywords MonteCarloTreeSearchspectralexpansioncontrollabilityGramiancontinuous-spaceplanningmodel-predictivecontrolautonomousrobotskinodynamicglobaloptimalitybounds
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper introduces Spectral Expansion Tree Search (SETS), a Monte Carlo Tree Search planner for continuous, deterministic, differentiable dynamical systems. SETS replaces the usual spatial discretization of a robot's state and action space with a tree whose branches follow the natural motion modes obtained from the spectrum of the locally linearized controllability Gramian. The authors prove that this discretization has bounded error: the difference between the continuous optimal value and SETS's estimate goes to a problem-dependent steady-state term as simulations grow. They demonstrate on quadrotor, tracked-vehicle, tethered-spacecraft, and glider experiments that this planner discovers non-trivial behaviors in real time. The central engineering claim is that a general, offline-training-free planner can handle high-dimensional, underactuated, non-convex robotics problems while still carrying an optimality guarantee.

What carries the argument

The Spectral Expansion operator is the load-bearing mechanism. At each node it linearizes the dynamics over a horizon $H$, computes the eigendecomposition of the controllability Gramian $CC^\top$, and launches $2n$ branches along the plus and minus singular vectors (the natural motion modes). A Discrete Algebraic Riccati Equation feedback controller steers the nonlinear system onto each linear reference trajectory, and the resulting reachable-set covering is bounded via Hausdorff distance lemmas. This discrete representation is what converts the continuous MDP into a finite tree whose value error can be analyzed by an MCTS convergence theorem.

What would settle it

Run Algorithm 1 exactly as published, with $c_1=1$, $c_2=0.5$, $c_3=1$, on a small continuous MDP whose optimal value can be computed by fine-grid value iteration, and measure $|V^*(x_0) - E[V(x_0,\ell)]|$ as $\ell$ grows. If the decay is not of order $\ell^{-1/2}$ or the estimate violates the Theorem 3 bound, then the stated exploration-law hypotheses are not satisfied by the delivered algorithm.

Watch

Extended reading notes

Core claim

SETS converges to a bound of the globally optimal solution for continuous Markov Decision Processes with twice-differentiable dynamics, Lipschitz state-dependent rewards, and bounded continuous action sets. Quantitatively, Theorem 3 bounds the value error by a convergence term plus a steady-state term: the estimate approaches within a problem-dependent constant of the continuous optimum as the number of tree rollouts grows. The mechanism is spectral expansion: at each node, linearize the dynamics, form the input-normalized controllability matrix, take its eigendecomposition, and branch along plus and minus each mode; a discrete Riccati feedback controller tracks the linear reference trajectory with the nonlinear system. This yields a branching factor linear in state dimension and a tree depth reduced by a factor of the branch length, dramatically shrinking the action-sequence count relative to uniform discretization. A separate MCTS convergence theorem achieves a $1/\sqrt{\tau}$ rate without knowing the reward gap, and combining the two results gives the overall convergence-to-a-bound guarantee.

Load-bearing premise

The finite-time convergence rate relies on the exploration constants satisfying $c_3 \in [1/4,1/2)$ and $c_2=2c_3$, as stated in the Supplemental Constants Discussion, but the implemented Algorithm 1 and Methods use $c_2=0.5$, $c_3=1$; if that mismatch is real rather than a typo, Theorem 2's $1/\sqrt{\tau}$ rate does not apply to the deployed algorithm.

Editorial extensions

If this is right

  • For any twice-differentiable deterministic dynamics with Lipschitz rewards, a robot can replan from a never-before-seen state in real time and the value of its plan approaches a bounded neighborhood of the continuous optimum as computation increases.
  • Branch length $H$ tunes the trade-off directly: larger $H$ converges faster but with larger asymptotic error, while smaller $H$ converges slower but tighter, giving a principled parameter design rule for receding-horizon operation.
  • Tree width scales linearly in state dimension ($2n$ modes) rather than exponentially in control dimension, so the method extends to high-dimensional platforms such as a 12-dimensional quadrotor with learned wind effects and a multi-spacecraft tether network.
  • The guarantee applies to value, not just feasibility, so SETS can be paired with local optimization in a search-then-optimize loop that keeps global exploration while refining the output trajectory.
  • The MCTS convergence result, which holds for deterministic rewards without knowing the gap between children, may transfer to discrete game-playing and other tree search settings that use polynomial exploration.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • As an extension the authors mention but do not develop, the spectral modes could serve as learned features for offline policy learning, model-predictive path integral control, or kinodynamic RRT-style planners, potentially reducing their search complexity.
  • The glider baseline study suggests that the spectral representation contributes more than the exploration strategy: a simpler predictive-sampling rollout on top of spectral expansion performed competitively, so representation and exploration can be decoupled and mixed.
  • If the exploration-constant mismatch flagged in the Supplemental Constants Discussion is not a typo, the deployed Algorithm 1 with $c_2=0.5$, $c_3=1$ falls outside the conditions of Theorem 2, and the real-time optimality guarantee would need an extended proof or a constants correction to cover the published implementation.
  • The steady-state error depends on linearization error and on the contraction rate of the Riccati tracking controller, so systems with poor local linearizations will need tighter tracking or shorter branches to keep the bound meaningful.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

Summary. The paper proposes Spectral Expansion Tree Search (SETS), a real-time MCTS planner for continuous, deterministic, differentiable MDPs. Instead of uniformly discretizing state or action spaces, SETS expands tree nodes along the dominant modes of the locally linearized controllability Gramian, generates reference trajectories to those modes, and tracks them with a DARE-based feedback controller. The theoretical core is threefold: Theorem 1 bounds the optimal-value error caused by replacing the continuous reachable set with the finite set of spectral modes; Theorem 2 provides a finite-time concentration bound for MCTS with polynomial exploration on finite-action MDPs; and Theorem 3 combines these into a bound of the form kappa4/sqrt(l) plus a steady-state error term. The paper reports hardware and simulation demonstrations on a quadrotor, a tracked vehicle, two tethered spacecraft, and a glider.

Significance. If the theorems hold for the algorithm as actually implemented, this is a notable contribution: it is one of the few real-time kinodynamic planners with a non-asymptotic global-optimality bound, and it targets a broad problem class rather than a narrowly specialized motion-planning formulation. The theoretical development is a genuine derivation from stated Lipschitz, contraction, and reachability assumptions, not a fit of constants to a target result, and the modular decomposition (reachable-set approximation in Theorem 1, MCTS value convergence in Theorem 2) is likely to be useful beyond this specific planner. The release of code and video links and the breadth of hardware experiments strengthen the reproducibility of the empirical claims. However, the paper's central guarantee is currently separated from its deployed algorithm by two concrete gaps: the exploration constants in Algorithm 1 are outside the regime proved in the supplement, and the mode-pruning heuristic used in all reported experiments removes modes that Theorem 1's covering argument requires. These gaps are fixable, but they make the significance contingent until the manuscript is corrected.

major comments (2)
  1. [Methods (Algorithm 1, Line 6; Methods paragraph) and Supplemental 'Constants Discussion'] The exploration constants used in Algorithm 1 are outside the regime in which Theorem 2 is proved. Algorithm 1 Line 6 and the Methods text specify c1=1, c2=0.5, c3=1, whereas the Supplemental 'Constants Discussion' proves the 1/sqrt(tau) rate only for c3 in [1/4,1/2) with c2=2c3. Substituting the implemented values gives cd5=cd6=1-c3/c2=-1, and Lemma 9's inductive condition cd3+c_{d+1}6-cd2>0 evaluates to 1-1-0.5=-0.5, so Equations (165)-(169) and the visit-count bound that feeds Theorem 2 no longer hold. Since Theorem 3's convergence term is exactly Theorem 2's rate, the central real-time optimality guarantee does not cover the deployed algorithm as written. The supplement's final sentence ('we used exactly those values in our experiments') suggests a transposition between c2 and c3 in the pseudocode; if so, the pseudocode and the Methods text must be corrected, and otherwise Theorem 2 must be reproved for the actual exploration law.
  2. [Methods, 'Heuristics'] The Heuristics paragraph states that the authors 'apply [the mode-pruning heuristic] in all of our experiments,' yet Theorem 1 and Lemma 3 use all 2n controllability-Gramian modes to bound dS(R_L^H(x0,U^H), {z_i^H}_{i=1}^{2n}) <= 2 sigma_max(C). Once only a subset of modes is expanded, the finite representation need not cover the linear reachable set in the sense required by the proof, and the steady-state error term in Theorem 3 is not certified for the reported implementations. The authors should either report at least one experiment using the full expansion or provide a supplementary argument showing that the omitted modes are unnecessary for the reward and constraint class considered; without this, the experimental validation is outside the proven algorithm.
minor comments (4)
  1. [Supplemental 'Lemma 4' and 'Lemma 2'] The factor sqrt(m)/m appearing in Lemma 4 and in Equation (89) appears to be a typo for sqrt(m)/m (or a consistent bound involving sqrt(m)); as written, the factor is ambiguous and should be cleaned up.
  2. [Supplemental 'Supplemental Tracked Vehicle'] Assumption 1 restricts rewards to state-only Lipschitz functions, but the tracked vehicle reward in Supplemental Equation (12) depends on the action (vd, omega_d). The paper already notes that the tracked-vehicle demonstration uses gamma=1 outside the theory; it should similarly state that the action-dependent reward is outside Assumption 1.
  3. [Supplemental 'Theorem 2' proof] The proof divides by Delta(j) and uses Delta_min(i) in the constants, but neither Theorem 2 nor Assumption 2 states that every node has a unique strictly optimal child with positive gap. Please add an explicit strict-gap assumption or explain how ties are handled so that arms with Delta(j)=0 do not make the bounds vacuous.
  4. [Methods, 'Heuristics' and 'Theoretical Results'] The sentence 'we return the maximum valued trajectory ... This practice maintains theoretical guarantees' is too terse. Because Theorem 2 and Theorem 3 bound the average estimator E[V(i,l)], the manuscript should spell out why the returned maximum-valued trajectory inherits the bound, for example by noting that all sampled values are bounded above by V*(i), so the maximum estimator lies between the average estimator and V*(i).

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity; the SETS optimality bound is a genuine derivation from stated regularity and contraction assumptions, and the self-citations are peripheral rather than load-bearing.

full rationale

The paper's derivation chain is self-contained in the relevant sense. Theorem 1 bounds the discretization error by combining a Lipschitz/Bellman comparison of MDPs (Lemma 1) with three reachable-set distance bounds: nonlinear vs. linearized dynamics, linear reachable set vs. controllability-Gramian modes, and modes vs. feedback-tracked nonlinear trajectories. Each quantity is defined from the dynamics, reward, and the locally linearized system, not from the optimal value being estimated. Theorem 2 proves MCTS value convergence for the polynomial exploration law by an induction on tree depth with non-stationary bandit arguments adapted from [87]; the constants are constrained explicitly in the Supplemental Constants Discussion, and the rate kappa5 = kappa6 = 1/2 follows from the stated choice c2 = 2c3, c3 in [1/4,1/2). Theorem 3 is just the triangle inequality combining Theorems 1 and 2. No fitted parameter is renamed as a prediction, and the spectral expansion operator is not defined in terms of V* or of the experiment outcomes. The self-citations ([91], [92]) are not load-bearing for the central optimality claim: [92] is invoked only for an auxiliary feasibility guarantee, and the main convergence theorem does not depend on it. The serious caveat in the paper is not circularity but a consistency gap: Algorithm 1 lists c2 = 0.5, c3 = 1, while the proof requires c3 in [1/4,1/2) and c2 = 2c3, so the deployed exploration law may fall outside the proven regime; this is a correctness/coverage issue, the opposite of assuming the conclusion. The bound's constants also depend on problem-specific quantities such as the Lipschitz constant of V* and sigma_max(C), making the result non-constructive in practice, but this is a standard Lipschitz argument rather than a circular reduction. Against external baselines (DPW, predictive sampling, uniform discretization) and independent hardware/numerical experiments, the paper's central claims retain independent content.

Assumptions & free parameters 5 free parameters · 6 assumptions · 0 invented entities

The central claim rests on standard regularity assumptions plus several hand-chosen algorithm parameters (H, exploration constants, DARE weights, mode pruning). The exploration constant mismatch between the method and the proven regime is the most concrete burden. No new physical entities are introduced.

free parameters (5)
  • Branch length H = H=1000 (glider), H=2 (tracked vehicle), others unspecified
    Controls the trade-off between MCTS convergence speed and discretization error in Theorem 3; selected empirically per experiment, e.g., from Fig. 5C.
  • MCTS exploration constants c1,c2,c3 = c1=1, c2=0.5, c3=1 (Algorithm 1); supplemental requires c2=2c3 with c3 in [0.25,0.5)
    Hand chosen; the main text values fall outside the regime in which Theorem 2 proves the 1/sqrt(tau) rate.
  • DARE weights Gamma_x, Gamma_u
    Not specified in the paper; they determine the contraction rate alpha used in Lemma 4 and Theorem 1's bound.
  • Mode pruning (velocity and angular velocity modes only) = used in all experiments
    The paper says searching only velocity and angular velocity modes improved performance and was applied in all experiments; this reduces branching factor below the proven 2n but is not analyzed.
  • Terminal reward D = D=0 in all experiments
    The feasibility guarantee in the text relies on a well-selected D; experiments use D=0, so the returned trajectory is not guaranteed feasible by the theory.
assumptions (6)
  • domain assumption Assumption 1: F twice differentiable, R Lipschitz and state-dependent, U a product of intervals
    Invoked in Theorem 1 and throughout; the quadrotor's DNN wind model (ReLU) is not C^2, so this assumption is not satisfied in that experiment.
  • domain assumption Discount factor gamma < 1
    Required for Lemmas 1, Theorems 1-3 via the Bellman contraction; the tracked vehicle experiment uses gamma=1, explicitly outside this assumption.
  • domain assumption Uniform contraction rate alpha < 1 for the DARE tracking controller across local linearizations
    Lemma 14 gives a sufficient condition (Gamma_x large, stabilizable (A,B)), but the paper does not verify this holds for the varying local linearizations in each experiment.
  • ad hoc to paper Strict optimal child gap Delta(j) > 0 at every node
    The MCTS convergence proof (Lemmas 5, 7, 9, 11) bounds suboptimal child visits by 1/Delta(j); zero-gap ties are not handled, and the theorem does not state this condition.
  • standard math The Bellman operator has a unique fixed point (discounted MDP with bounded rewards)
    Used in Lemma 1 proof, from standard dynamic programming [100].
  • domain assumption Local linearization error epsilon_H bounded over the branch (Taylor remainder)
    Lemmas 2 and 4 require F to have Lipschitz gradients and bound epsilon_H = max ||(x,u)-(xbar,ubar)||; if branches are aggressive, this error may be large.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Monte Carlo Tree Search with Spectral Expansion for Planning with Dynamical Systems." pith.science (2026). https://pith.science/paper/U5TLXF7Q

@misc{pith2026241211270,
  author       = {Pith},
  title        = {Pith review of: Monte Carlo Tree Search with Spectral Expansion for Planning with Dynamical Systems},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/U5TLXF7Q}},
  note         = {Machine review of arXiv:2412.11270}
}
read the original abstract

The ability of a robot to plan complex behaviors with real-time computation, rather than adhering to predesigned or offline-learned routines, alleviates the need for specialized algorithms or training for each problem instance. Monte Carlo Tree Search is a powerful planning algorithm that strategically explores simulated future possibilities, but it requires a discrete problem representation that is irreconcilable with the continuous dynamics of the physical world. We present Spectral Expansion Tree Search (SETS), a real-time, tree-based planner that uses the spectrum of the locally linearized system to construct a low-complexity and approximately equivalent discrete representation of the continuous world. We prove SETS converges to a bound of the globally optimal solution for continuous, deterministic and differentiable Markov Decision Processes, a broad class of problems that includes underactuated nonlinear dynamics, non-convex reward functions, and unstructured environments. We experimentally validate SETS on drone, spacecraft, and ground vehicle robots and one numerical experiment, each of which is not directly solvable with existing methods. We successfully show SETS automatically discovers a diverse set of optimal behaviors and motion trajectories in real time.

Figures

Figures reproduced from arXiv: 2412.11270 by the authors.

Figure 1
Figure 1. (A) Our method, SETS, is a new tree-based planning algorithm for dynamical systems. The tree’s edges [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. (A) SETS enables a drone, circled in blue, to plan trajectories to multiple targets (white) over a fan array and obstacles (orange) in real time. The twelve dimensional search tree is projected onto the two dimensional fan surface. The branches are colored by the order of expansion, with yellow indicating later trajectories. (B) The spectrum of the controllability Gramian is shown for flying in still air and flying … view at source ↗
Figure 3
Figure 3. Caption next page. 6 [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗
Figures from the paper (5 more)
Figure 4
Figure 4. Figure 4: (A) Still shots of the spacecraft experiment. The two tethered spacecraft arrest the motion of the target spacecraft. Planning through the tether-contact model, the controlled spacecraft shepherd the target spacecraft in the desired direction, toward the camera. These …
Figure 5
Figure 5. Figure 5: (A) The glider (blue) discovers an oscillation strategy between observing the target (green) to maximize its objective, and passing through the thermal (orange) to gain energy and maintain altitude. (B) Kinetic and potential energy of the glider over time. In nominal a…
Figure 6
Figure 6. Figure 6: Spectral Expansion: (A) The Spectral Expansion Operator: The nonlinear reachable set is shaded in green and the locally linearized reachable set is shaded in blue. The modes of the controllability spectrum are the axes of the ellipse {z i H} 2n i=1, and these are used …
Figure 7
Figure 7. Figure 7: This error term can also be controlled with other parameters. For example, the term with the worst growth [PITH_FULL_IMAGE:figures/full_fig_p018_7.png]
Figure 7
Figure 7. Figure 7: We evaluate SETS on a motion planning problem, where a 2D double integrator starts at the blue dot on [PITH_FULL_IMAGE:figures/full_fig_p019_7.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

120 extracted references · 73 canonical work pages

  1. [1]

    Bellman, Dynamic programming

    R. Bellman, Dynamic programming. Princeton University Press, 1957

    1957

  2. [2]

    Rapidly-exploring random trees: A new tool for path planning,

    S. LaValle, “Rapidly-exploring random trees: A new tool for path planning,” Research Report 9811, 1998

    1998

  3. [3]

    Probabilistic roadmaps for path planning in high-dimensional configuration spaces,

    L. E. Kavraki, P. Svestka, J.-C. Latombe, and M. H. Overmars, “Probabilistic roadmaps for path planning in high-dimensional configuration spaces,” IEEE Transactions on Robotics and Automation , vol. 12, no. 4, pp. 566–580, 1996

    1996

  4. [4]

    Sampling-based motion planning: A comparative review,

    A. Orthey, C. Chamzas, and L. E. Kavraki, “Sampling-based motion planning: A comparative review,” Annual Review of Control, Robotics, and Autonomous Systems , vol. 7, 2023

    2023

  5. [5]

    Model predictive control of swarms of spacecraft using sequential convex programming,

    D. Morgan, S.-J. Chung, and F. Y. Hadaegh, “Model predictive control of swarms of spacecraft using sequential convex programming,” Journal of Guidance, Control, and Dynamics , vol. 37, no. 6, pp. 1725–1740, 2014

    2014

  6. [6]

    Convex optimization for trajectory generation,

    D. Malyuta, T. P. Reynolds, M. Szmuk, T. Lew, R. Bonalli, M. Pavone, and B. Acikmese, “Convex optimization for trajectory generation,” arXiv preprint arXiv:2106.09125 , 2021

    arXiv 2021

  7. [7]

    R. S. Sutton and A. G. Barto, Reinforcement learning: An introduction. MIT press, 2018

    2018

  8. [8]

    Information-based guidance and control architecture for multi-spacecraft on-orbit inspection,

    Y. K. Nakka, W. H¨ onig, C. Choi, A. Harvard, A. Rahmani, and S.-J. Chung, “Information-based guidance and control architecture for multi-spacecraft on-orbit inspection,” Journal of Guidance, Control, and Dynamics , vol. 45, no. 7, pp. 1184–1201, 2022

    2022

Show all 120 references
  1. [9]

    Hierarchical task and motion planning in the now,

    L. P. Kaelbling and T. Lozano-P´ erez, “Hierarchical task and motion planning in the now,” inIEEE International Conference on Robotics and Automation , pp. 1470–1477, 2011

    2011

  2. [10]

    Integrated task and motion planning,

    C. R. Garrett, R. Chitnis, R. Holladay, B. Kim, T. Silver, L. P. Kaelbling, and T. Lozano-P´ erez, “Integrated task and motion planning,” Annual Review of Control, Robotics, and Autonomous Systems, vol. 4, pp. 265–293, 2021. 19

    2021

  3. [11]

    A survey of motion planning and control techniques for self-driving urban vehicles,

    B. Paden, M. ˇC´ ap, S. Z. Yong, D. Yershov, and E. Frazzoli, “A survey of motion planning and control techniques for self-driving urban vehicles,” IEEE Transactions on Intelligent Vehicles , vol. 1, no. 1, pp. 33–55, 2016

    2016

  4. [12]

    Planning and decision-making for autonomous vehicles,

    W. Schwarting, J. Alonso-Mora, and D. Rus, “Planning and decision-making for autonomous vehicles,” Annual Review of Control, Robotics, and Autonomous Systems , vol. 1, pp. 187–210, 2018

    2018

  5. [13]

    Reaching the limit in autonomous racing: Optimal control versus reinforcement learning,

    Y. Song, A. Romero, M. M¨ uller, V. Koltun, and D. Scaramuzza, “Reaching the limit in autonomous racing: Optimal control versus reinforcement learning,” Science Robotics, vol. 8, no. 82, p. eadg1462, 2023

    2023

  6. [14]

    An application of reinforcement learning to aerobatic helicopter flight,

    P. Abbeel, A. Coates, M. Quigley, and A. Ng, “An application of reinforcement learning to aerobatic helicopter flight,” in Advances in Neural Information Processing Systems (B. Sch¨ olkopf, J. Platt, and T. Hoffman, eds.), vol. 19, MIT Press, 2006

    2006

  7. [15]

    Deep learning for detecting robotic grasps,

    I. Lenz, H. Lee, and A. Saxena, “Deep learning for detecting robotic grasps,” in Proceedings of Robotics: Science and Systems , (Berlin, Germany), June 2013

    2013

  8. [16]

    Robust feedback motion policy design using reinforcement learning on a 3d digit bipedal robot,

    G. A. Castillo, B. Weng, W. Zhang, and A. Hereid, “Robust feedback motion policy design using reinforcement learning on a 3d digit bipedal robot,” inIEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 5136–5143, 2021

    2021

  9. [17]

    A sparse sampling algorithm for near-optimal planning in large markov decision processes,

    M. Kearns, Y. Mansour, and A. Y. Ng, “A sparse sampling algorithm for near-optimal planning in large markov decision processes,” Machine Learning, vol. 49, pp. 193–208, 2002

    2002

  10. [18]

    Bandit based monte-carlo planning,

    L. Kocsis and C. Szepesv´ ari, “Bandit based monte-carlo planning,” inEuropean Conference on Machine Learn- ing, pp. 282–293, Springer, 2006

    2006

  11. [19]

    From bandits to monte-carlo tree search: The optimistic principle applied to optimization and planning,

    R. Munos et al. , “From bandits to monte-carlo tree search: The optimistic principle applied to optimization and planning,” Foundations and Trends® in Machine Learning , vol. 7, no. 1, pp. 1–129, 2014

    2014

  12. [20]

    A survey of monte carlo tree search methods,

    C. B. Browne, E. Powley, D. Whitehouse, S. M. Lucas, P. I. Cowling, P. Rohlfshagen, S. Tavener, D. Perez, S. Samothrakis, and S. Colton, “A survey of monte carlo tree search methods,” IEEE Transactions on Com- putational Intelligence and AI in Games , vol. 4, no. 1, pp. 1–43, 2012

    2012

  13. [21]

    The traveling-salesman problem,

    M. M. Flood, “The traveling-salesman problem,” Operations research, vol. 4, no. 1, pp. 61–75, 1956

    1956

  14. [22]

    K. J. Astrom and R. M. Murray,Feedback systems: An introduction for scientists and engineers. USA: Princeton University Press, 2008

    2008

  15. [23]

    R. M. Murray, Robotic Control and Nonholonomic Motion Planning . University of California, Berkeley, 1991

    1991

  16. [24]

    Asteroid redirect mission reference concept

    “Asteroid redirect mission reference concept.” https://www.nasa.gov/wp-content/uploads/2015/04/ asteroid_redirect_mission_reference_concept_description_tagged.pdf. Accessed: 2024-05-16

    2015

  17. [25]

    R. W. Beard and T. W. McLain, Small unmanned aircraft: Theory and practice . Princeton University Press, 2012

    2012

  18. [26]

    Continuous upper confidence trees,

    A. Cou¨ etoux, J.-B. Hoock, N. Sokolovska, O. Teytaud, and N. Bonnard, “Continuous upper confidence trees,” in Learning and Intelligent Optimization: 5th International Conference, LION 5, Rome, Italy, January 17-21,

  19. [27]

    Predictive sampling: Real-time behaviour synthesis with mujoco,

    T. Howell, N. Gileadi, S. Tunyasuvunakool, K. Zakka, T. Erez, and Y. Tassa, “Predictive sampling: Real-time behaviour synthesis with mujoco,” arXiv preprint arXiv:2212.00541 , 2022

    2022 arXiv

  20. [28]

    ApS, MOSEK Fusion for C++ 10.1.21 , 2019

    M. ApS, MOSEK Fusion for C++ 10.1.21 , 2019

    2019

  21. [29]

    Time-optimal planning for quadrotor waypoint flight,

    P. Foehn, A. Romero, and D. Scaramuzza, “Time-optimal planning for quadrotor waypoint flight,” Science Robotics, vol. 6, no. 56, p. eabh1221, 2021

    2021

  22. [30]

    Autonomous in-orbit satellite assembly from a modular heterogeneous swarm,

    R. C. Foust, E. S. Lupu, Y. K. Nakka, S.-J. Chung, and F. Y. Hadaegh, “Autonomous in-orbit satellite assembly from a modular heterogeneous swarm,” Acta Astronautica, vol. 169, pp. 191–205, 2020

    2020

  23. [31]

    3d dynamic walking with underactuated humanoid robots: A direct collocation framework for optimizing hybrid zero dynamics,

    A. Hereid, E. A. Cousineau, C. M. Hubicki, and A. D. Ames, “3d dynamic walking with underactuated humanoid robots: A direct collocation framework for optimizing hybrid zero dynamics,” in 2016 IEEE Inter- national Conference on Robotics and Automation (ICRA) , pp. 1447–1454, IE...

    2016

  24. [32]

    Swarm assignment and trajectory op- timization using variable-swarm, distributed auction assignment and sequential convex programming,

    D. Morgan, G. P. Subramanian, S.-J. Chung, and F. Y. Hadaegh, “Swarm assignment and trajectory op- timization using variable-swarm, distributed auction assignment and sequential convex programming,” The International Journal of Robotics Research , vol. 35, no. 10, pp. 1261–1285, 2016

    2016

  25. [33]

    Unifying geometric, probabilistic, and potential field approaches to multi-robot deployment,

    M. Schwager, D. Rus, and J.-J. Slotine, “Unifying geometric, probabilistic, and potential field approaches to multi-robot deployment,” The International Journal of Robotics Research , vol. 30, no. 3, pp. 371–383, 2011

    2011

  26. [34]

    A second-order gradient method for determining optimal trajectories of non-linear discrete-time systems,

    D. Mayne, “A second-order gradient method for determining optimal trajectories of non-linear discrete-time systems,” International Journal of Control , vol. 3, no. 1, pp. 85–95, 1966

    1966

  27. [35]

    A direct multiple shooting method for real-time optimiza- tion of nonlinear dae processes,

    H. Bock, M. Diehl, D. Leineweber, and J. Schl¨ oder, “A direct multiple shooting method for real-time optimiza- tion of nonlinear dae processes,” in Nonlinear Model Predictive Control, pp. 245–267, Springer, 2000

    2000

  28. [36]

    Iterative linear quadratic regulator design for nonlinear biological movement systems,

    W. Li and E. Todorov, “Iterative linear quadratic regulator design for nonlinear biological movement systems,” in First International Conference on Informatics in Control, Automation and Robotics , vol. 2, pp. 222–229, SciTePress, 2004

    2004

  29. [37]

    Local convergence of sequential convex programming for nonconvex optimization,

    Q. T. Dinh and M. Diehl, “Local convergence of sequential convex programming for nonconvex optimization,” in Recent Advances in Optimization and its Applications in Engineering: The 14th Belgian-French-German Conference on Optimization , pp. 93–102, Springer, 2010

    2010

  30. [38]

    Gusto: Guaranteed sequential trajectory optimization via sequential convex programming,

    R. Bonalli, A. Cauligi, A. Bylard, and M. Pavone, “Gusto: Guaranteed sequential trajectory optimization via sequential convex programming,” in 2019 International Conference on Robotics and Automation (ICRA) , pp. 6741–6747, IEEE, 2019

    2019

  31. [39]

    The Open Motion Planning Library,

    I. A. S ¸ucan, M. Moll, and L. E. Kavraki, “The Open Motion Planning Library,” IEEE Robotics & Automation Magazine, vol. 19, pp. 72–82, December 2012. https://ompl.kavrakilab.org

    2012

  32. [40]

    Motion planning around obstacles with convex optimization,

    T. Marcucci, M. Petersen, D. von Wrangel, and R. Tedrake, “Motion planning around obstacles with convex optimization,” Science Robotics, vol. 8, no. 84, p. eadf7843, 2023

    2023

  33. [41]

    Sampling-based algorithms for optimal motion planning,

    S. Karaman and E. Frazzoli, “Sampling-based algorithms for optimal motion planning,” Int. J. Robotics Res. , vol. 30, no. 7, pp. 846–894, 2011

    2011

  34. [42]

    Asymptotically optimal sampling-based kinodynamic planning,

    Y. Li, Z. Littlefield, and K. E. Bekris, “Asymptotically optimal sampling-based kinodynamic planning,” The International Journal of Robotics Research , vol. 35, no. 5, pp. 528–564, 2016

    2016

  35. [43]

    Poccia, Deterministic sampling-based algorithms for motion planning under differential constraints

    E. Poccia, Deterministic sampling-based algorithms for motion planning under differential constraints . PhD thesis, Master’s thesis, Pisa Univ., Pisa, Italy, 2017

    2017

  36. [44]

    db-a*: Discontinuity-bounded search for kinodynamic mobile robot motion planning,

    W. H¨ onig, J. O. de Haro, and M. Toussaint, “db-a*: Discontinuity-bounded search for kinodynamic mobile robot motion planning,” in IEEE/RSJ International Conference on Intelligent Robots and Systems, IROS 2022, Kyoto, Japan, October 23-27, 2022 , pp. 13540–13547, IEEE, 2022

    2022

  37. [45]

    Real-time motion planning for agile autonomous vehicles,

    E. Frazzoli, M. A. Dahleh, and E. Feron, “Real-time motion planning for agile autonomous vehicles,” Journal of Guidance, Control, and Dynamics , vol. 25, no. 1, pp. 116–129, 2002

    2002

  38. [46]

    Maneuver-based motion planning for nonlinear systems with sym- metries,

    E. Frazzoli, M. A. Dahleh, and E. Feron, “Maneuver-based motion planning for nonlinear systems with sym- metries,” IEEE Transactions on Robotics, vol. 21, no. 6, pp. 1077–1091, 2005

    2005

  39. [47]

    Dynamic movement primitives in robotics: A tutorial survey,

    M. Saveriano, F. J. Abu-Dakka, A. Kramberger, and L. Peternel, “Dynamic movement primitives in robotics: A tutorial survey,” The International Journal of Robotics Research , 2021

    2021

  40. [48]

    Optimal sampling-based motion planning under differential con- straints: the drift case with linear affine dynamics,

    E. Schmerling, L. Janson, and M. Pavone, “Optimal sampling-based motion planning under differential con- straints: the drift case with linear affine dynamics,” in 2015 54th IEEE Conference on Decision and Control (CDC), pp. 2574–2581, IEEE, 2015

    2015

  41. [49]

    Lqr-trees: Feedback motion planning on sparse randomized trees,

    R. Tedrake, “Lqr-trees: Feedback motion planning on sparse randomized trees,” Robotics: Science and Systems, 2009

    2009

  42. [50]

    Funnel libraries for real-time robust feedback motion planning,

    A. Majumdar and R. Tedrake, “Funnel libraries for real-time robust feedback motion planning,” The Interna- tional Journal of Robotics Research , vol. 36, no. 8, pp. 947–982, 2017. 21

    2017

  43. [51]

    Optimal kinodynamic motion planning using incremental sampling-based meth- ods,

    S. Karaman and E. Frazzoli, “Optimal kinodynamic motion planning using incremental sampling-based meth- ods,” in 49th IEEE Conference on Decision and Control (CDC) , pp. 7681–7687, IEEE, 2010

    2010

  44. [52]

    Model-based reinforcement learning: A survey,

    T. M. Moerland, J. Broekens, A. Plaat, and C. M. Jonker, “Model-based reinforcement learning: A survey,” Foundations and Trends in Machine Learning , vol. 16, no. 1, pp. 1–118, 2023

    2023

  45. [53]

    Continuous upper confidence trees with polynomial exploration– consistency,

    D. Auger, A. Couetoux, and O. Teytaud, “Continuous upper confidence trees with polynomial exploration– consistency,” in Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2013, Prague, Czech Republic , pp. 194–209, Springer, 2013

    2013

  46. [54]

    Monte-carlo planning in large pomdps,

    D. Silver and J. Veness, “Monte-carlo planning in large pomdps,” in Advances in Neural Information Processing Systems (J. Lafferty, C. Williams, J. Shawe-Taylor, R. Zemel, and A. Culotta, eds.), vol. 23, 2010

    2010

  47. [55]

    Online algorithms for pomdps with continuous state, action, and observation spaces,

    Z. Sunberg and M. Kochenderfer, “Online algorithms for pomdps with continuous state, action, and observation spaces,” in Proceedings of the International Conference on Automated Planning and Scheduling, vol. 28, pp. 259– 263, 2018

    2018

  48. [56]

    Bayesian active sensing for fault estimation with belief space tree search,

    J. Ragan, B. Riviere, and S.-J. Chung, “Bayesian active sensing for fault estimation with belief space tree search,” in AIAA Scitech, 01 2023

    2023

  49. [57]

    Convergence of monte carlo tree search in simultaneous move games,

    V. Lisy, V. Kovarik, M. Lanctot, and B. Bosansky, “Convergence of monte carlo tree search in simultaneous move games,” in Advances in Neural Information Processing Systems , vol. 26, 2013

    2013

  50. [58]

    Cross-entropy motion planning,

    M. Kobilarov, “Cross-entropy motion planning,” The International Journal of Robotics Research, vol. 31, no. 7, pp. 855–871, 2012

    2012

  51. [59]

    Aggressive driving with model predictive path integral control,

    G. Williams, P. Drews, B. Goldfain, J. M. Rehg, and E. A. Theodorou, “Aggressive driving with model predictive path integral control,” in 2016 IEEE International Conference on Robotics and Automation (ICRA) , pp. 1433–1440, IEEE, 2016

    2016

  52. [60]

    Storm: An integrated framework for fast joint-space model-predictive control for reactive manipulation,

    M. Bhardwaj, B. Sundaralingam, A. Mousavian, N. D. Ratliff, D. Fox, F. Ramos, and B. Boots, “Storm: An integrated framework for fast joint-space model-predictive control for reactive manipulation,” in Conference on Robot Learning, pp. 750–759, PMLR, 2022

    2022

  53. [61]

    Sampling-based model predictive control leveraging parallelizable physics simulations,

    C. Pezzato, C. Salmi, M. Spahn, E. Trevisan, J. Alonso-Mora, and C. H. Corbato, “Sampling-based model predictive control leveraging parallelizable physics simulations,” arXiv preprint arXiv:2307.09105 , 2023

    2023 arXiv

  54. [62]

    Despot-alpha: Online pomdp planning with large state and observation spaces.,

    N. P. Garg, D. Hsu, and W. S. Lee, “Despot-alpha: Online pomdp planning with large state and observation spaces.,” in Robotics: Science and Systems , vol. 3, pp. 3–2, 2019

    2019

  55. [63]

    Trajectory optimization of chance-constrained nonlinear stochastic systems for motion planning under uncertainty,

    Y. K. Nakka and S.-J. Chung, “Trajectory optimization of chance-constrained nonlinear stochastic systems for motion planning under uncertainty,” IEEE Transactions on Robotics, 2022

    2022

  56. [64]

    Planning by incremental dynamic programming,

    R. S. Sutton, “Planning by incremental dynamic programming,” in Machine Learning Proceedings, (San Fran- cisco, CA), pp. 353–357, 1991

    1991

  57. [65]

    An optimal one-way multigrid algorithm for discrete-time stochastic control,

    C.-S. Chow and J. N. Tsitsiklis, “An optimal one-way multigrid algorithm for discrete-time stochastic control,” IEEE Transactions on Automatic Control , vol. 36, no. 8, pp. 898–914, 1991

    1991

  58. [66]

    Variable resolution discretization in optimal control,

    R. Munos and A. Moore, “Variable resolution discretization in optimal control,” Machine Learning, vol. 49, pp. 291–323, 2002

    2002

  59. [67]

    High-dimensional stochastic optimal control using continuous tensor decompositions,

    A. Gorodetsky, S. Karaman, and Y. Marzouk, “High-dimensional stochastic optimal control using continuous tensor decompositions,” The International Journal of Robotics Research , vol. 37, no. 2-3, pp. 340–377, 2018

    2018

  60. [68]

    Survey of model-based reinforcement learning: Applications on robotics,

    A. S. Polydoros and L. Nalpantidis, “Survey of model-based reinforcement learning: Applications on robotics,” Journal of Intelligent & Robotic Systems , vol. 86, no. 2, pp. 153–173, 2017

    2017

  61. [69]

    Deep reinforcement learning: A brief survey,

    K. Arulkumaran, M. P. Deisenroth, M. Brundage, and A. A. Bharath, “Deep reinforcement learning: A brief survey,” IEEE Signal Processing Magazine , vol. 34, no. 6, pp. 26–38, 2017

    2017

  62. [70]

    Proximal policy optimization algorithms,

    J. Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov, “Proximal policy optimization algorithms,” arXiv preprint arXiv:1707.06347 , 2017. 22

    2017 arXiv

  63. [71]

    Global convergence of policy gradient methods for the linear quadratic regulator,

    M. Fazel, R. Ge, S. Kakade, and M. Mesbahi, “Global convergence of policy gradient methods for the linear quadratic regulator,” in International Conference on Machine Learning , pp. 1467–1476, PMLR, 2018

    2018

  64. [72]

    Global convergence of policy gradient methods to (almost) locally optimal policies,

    K. Zhang, A. Koppel, H. Zhu, and T. Basar, “Global convergence of policy gradient methods to (almost) locally optimal policies,” SIAM Journal on Control and Optimization , vol. 58, no. 6, pp. 3586–3612, 2020

    2020

  65. [73]

    Global optimality guarantees for policy gradient methods,

    J. Bhandari and D. Russo, “Global optimality guarantees for policy gradient methods,” Operations Research, 2024

    2024

  66. [74]

    Multimodal probabilistic model-based planning for human-robot interaction,

    E. Schmerling, K. Leung, W. Vollprecht, and M. Pavone, “Multimodal probabilistic model-based planning for human-robot interaction,” in 2018 IEEE International Conference on Robotics and Automation (ICRA) , pp. 3399–3406, IEEE, 2018

    2018

  67. [75]

    Monte carlo tree search in continuous spaces using voronoi optimistic optimization with regret bounds,

    B. Kim, K. Lee, S. Lim, L. Kaelbling, and T. Lozano-P´ erez, “Monte carlo tree search in continuous spaces using voronoi optimistic optimization with regret bounds,” in Proceedings of the AAAI Conference on Artificial Intelligence, vol. 34, pp. 9916–9924, 2020

    2020

  68. [76]

    Model predictive path integral control: From theory to parallel computation,

    G. Williams, A. Aldrich, and E. A. Theodorou, “Model predictive path integral control: From theory to parallel computation,” Journal of Guidance, Control, and Dynamics , vol. 40, no. 2, pp. 344–357, 2017

    2017

  69. [77]

    Between mdps and semi-mdps: A framework for temporal abstraction in reinforcement learning,

    R. S. Sutton, D. Precup, and S. Singh, “Between mdps and semi-mdps: A framework for temporal abstraction in reinforcement learning,” Artificial Intelligence, vol. 112, no. 1, pp. 181–211, 1999

    1999

  70. [78]

    Magic: Learning macro-actions for online POMDP planning ,

    Y. Lee, P. Cai, and D. Hsu, “Magic: Learning macro-actions for online POMDP planning ,” in Proceedings of Robotics: Science and Systems , (Virtual), July 2021

    2021

  71. [79]

    Markovian state and action abstractions for mdps via hierarchical MCTS,

    A. Bai, S. Srivastava, and S. Russell, “Markovian state and action abstractions for mdps via hierarchical MCTS,” in Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, New York, NY (S. Kambhampati, ed.), pp. 3029–3039, IJCAI/AAAI Press, 2016

    2016

  72. [80]

    Monte carlo tree search with options for general video game playing,

    M. De Waard, D. M. Roijers, and S. C. Bakkes, “Monte carlo tree search with options for general video game playing,” in 2016 IEEE Conference on Computational Intelligence and Games (CIG) , pp. 1–8, IEEE, 2016

    2016

  73. [81]

    Constrained hierarchical monte carlo belief-state planning,

    A. Jamgochian, H. Buurmeijer, K. H. Wray, A. Corso, and M. J. Kochenderfer, “Constrained hierarchical monte carlo belief-state planning,” arXiv preprint arXiv:2310.20054 , 2023

    2023 arXiv

  74. [82]

    Policy gradient methods for reinforcement learning with function approximation,

    R. S. Sutton, D. McAllester, S. Singh, and Y. Mansour, “Policy gradient methods for reinforcement learning with function approximation,” Advances in Neural Information Processing Systems , vol. 12, 1999

    1999

  75. [83]

    Pilco: A model-based and data-efficient approach to policy search,

    M. Deisenroth and C. E. Rasmussen, “Pilco: A model-based and data-efficient approach to policy search,” in Proceedings of the 28th International Conference on Machine Learning (ICML-11) , pp. 465–472, 2011

    2011

  76. [84]

    Guided policy search,

    S. Levine and V. Koltun, “Guided policy search,” in International conference on machine learning , pp. 1–9, PMLR, 2013

    2013

  77. [85]

    Glas: Global-to-local safe autonomy synthesis for multi-robot motion planning with end-to-end learning,

    B. Rivi` ere, W. H¨ onig, Y. Yue, and S.-J. Chung, “Glas: Global-to-local safe autonomy synthesis for multi-robot motion planning with end-to-end learning,” IEEE Robotics and Automation Letters , vol. 5, no. 3, pp. 4249– 4256, 2020

    2020

  78. [86]

    M. L. Puterman, Markov Decision Processes: Discrete Stochastic Dynamic Programming . John Wiley & Sons, 2014

    2014

  79. [87]

    Non-asymptotic analysis of monte carlo tree search,

    D. Shah, Q. Xie, and Z. Xu, “Non-asymptotic analysis of monte carlo tree search,” in Abstracts of the 2020 SIG- METRICS/Performance Joint International Conference on Measurement and Modeling of Computer Systems , pp. 31–32, 2020

    2020

  80. [88]

    Mastering the game of go without human knowledge,

    D. Silver, J. Schrittwieser, K. Simonyan, I. Antonoglou, A. Huang, A. Guez, T. Hubert, L. Baker, M. Lai, A. Bolton, Y. Chen, T. P. Lillicrap, F. Hui, L. Sifre, G. van den Driessche, T. Graepel, and D. Hassabis, “Mastering the game of go without human knowledge,” Nature, vol. 5...

    2017

  81. [89]

    S. Boyd, L. El Ghaoui, E. Feron, and V. Balakrishnan, Linear Matrix Inequalities in System and Control Theory. SIAM, 1994

    1994

  82. [90]

    Zhou and J

    K. Zhou and J. C. Doyle, Essentials of Robust Control , vol. 104. Prentice Hall Upper Saddle River, NJ, 1998. 23

    1998

  83. [91]

    Neural tree expansion for multi-robot planning in non-cooperative environments,

    B. Riviere, W. H¨ onig, M. Anderson, and S.-J. Chung, “Neural tree expansion for multi-robot planning in non-cooperative environments,” IEEE Robotics and Automation Letters , vol. 6, no. 4, pp. 6868–6875, 2021

    2021

  84. [92]

    Online tree-based planning for active spacecraft fault estimation and collision avoidance,

    J. Ragan, B. Riviere, F. Hadaegh, and S.-J. Chung, “Online tree-based planning for active spacecraft fault estimation and collision avoidance,” Science Robotics, 2024. To appear

    2024

  85. [93]

    Neural-fly enables rapid learning for agile flight in strong winds,

    M. O’Connell, G. Shi, X. Shi, K. Azizzadenesheli, A. Anandkumar, Y. Yue, and S.-J. Chung, “Neural-fly enables rapid learning for agile flight in strong winds,” Science Robotics, vol. 7, no. 66, 2022

    2022

  86. [94]

    Dinov2: Learning robust visual features without supervision,

    M. Oquab, T. Darcet, T. Moutakanni, H. Vo, M. Szafraniec, V. Khalidov, P. Fernandez, D. Haziza, F. Massa, A. El-Nouby, M. Assran, N. Ballas, W. Galuba, R. Howes, P.-Y. Huang, S.-W. Li, I. Misra, M. Rabbat, V. Sharma, G. Synnaeve, H. Xu, H. Jegou, J. Mairal, P. Labatut, A. Joul...

    2023 arXiv

  87. [95]

    J.-J. E. Slotine and W. Li, Applied Nonlinear Control, vol. 199. Prentice Hall Englewood Cliffs, NJ, 1991

    1991

  88. [96]

    Polynomial trajectory planning for aggressive quadrotor flight in dense indoor environments,

    C. Richter, A. Bry, and N. Roy, “Polynomial trajectory planning for aggressive quadrotor flight in dense indoor environments,” in Robotics Research: The 16th International Symposium ISRR , pp. 649–666, Springer, 2016

    2016

  89. [97]

    Trajectory planning for quadrotor swarms,

    W. H¨ onig, J. A. Preiss, T. K. S. Kumar, G. S. Sukhatme, and N. Ayanian, “Trajectory planning for quadrotor swarms,” IEEE Trans. Robotics, vol. 34, no. 4, pp. 856–869, 2018

    2018

  90. [98]

    Optimal guidance and control with nonlinear dynamics using sequential convex programming,

    R. Foust, S.-J. Chung, and F. Y. Hadaegh, “Optimal guidance and control with nonlinear dynamics using sequential convex programming,” Journal of Guidance, Control, and Dynamics , vol. 43, no. 4, pp. 633–644, 2020

    2020

  91. [99]

    Magic-vfm meta adaptive control for ground vehicle with visual foundation models,

    E. S. Lupu, F. Xie, J. Preiss, M. Anderson, J. Alindogan, and S.-J. Chung, “Magic-vfm meta adaptive control for ground vehicle with visual foundation models,” IEEE Transactions on Robotics, 2024. Under review

    2024

  92. [100]

    D. P. Bertsekas, Dynamic Programming and Optimal Control , vol. I. Belmont, MA, USA: Athena Scientific, 3rd ed., 2005

    2005

  93. [101]

    Stuart and A

    A. Stuart and A. R. Humphries, Dynamical Systems and Numerical Analysis , vol. 2. Cambridge University Press, 1998

    1998

  94. [102]

    On contraction analysis for non-linear systems,

    W. Lohmiller and J. E. Slotine, “On contraction analysis for non-linear systems,” Automatica, vol. 34, no. 6, pp. 683–696, 1998

    1998

  95. [103]

    Exploration–exploitation tradeoff using variance estimates in multi-armed bandits,

    J.-Y. Audibert, R. Munos, and C. Szepesv´ ari, “Exploration–exploitation tradeoff using variance estimates in multi-armed bandits,” Theoretical Computer Science, vol. 410, no. 19, pp. 1876–1902, 2009

    1902

  96. [104]

    Contraction theory for nonlinear stability analysis and learning- based control: A tutorial overview,

    H. Tsukamoto, S. Chung, and J. E. Slotine, “Contraction theory for nonlinear stability analysis and learning- based control: A tutorial overview,” Annual Reviews in Control , vol. 52, pp. 135–169, 2021

    2021

  97. [105]

    search then optimize

    D. Kirk, Optimal control theory: An introduction . Dover Books on Electrical Engineering, Dover Publications, 2012. Acknowledgements We thank the DARPA Learning Introspective Control (LINC) team at Caltech and JPL, who contributed to the full autonomy stack of the results show...

    2012

  98. [107]

    ∃t ∈ L(i, ℓ) s.t. T (j, t) > w, Q(j, t) + cd 1T (i, t)cd 3 T (j, t)cd 2 ≥ Q∗(j∗), w≥ u | T (i, ℓ) = τ # (187) ≤ X t∈L(i,ℓ) P

    ≥ 2, (172) ≤ u + cd+1 7 (2γ)cd+1 8 (cd 1)cd+1 8 ∞X s=1 s−2 = u + cd+1 7 (2γ)cd+1 8 π2 6(cd 1)cd+1 8 (173) Plug the definition of u into Equation (173) and note that (173) =   2cd 1τ cd 3 ∆(j) ! 1 cd 2 + 2γcd+1 4 cd 1 ! 1 cd 3 +cd+1 6 −cd 2   + cd+1 7 (2γ)cd+1 8 π2 6(cd...

  99. [108]

    − 1 ! (212) ≤ cd+1 7 (2γ)cd+1 8 (cd 1)cd+1 8 (w + 1)1−cd+1 8 (cd 3 +cd+1 6 −cd 2 ) cd+1 8 (cd 3 + cd+1 6 − cd

  100. [109]

    − 1 ! (213) where we constrain cd+1 8 (cd 3 + cd+1 6 − cd

  101. [110]

    As such, (213) ≤ cd+1 7 (2γ)cd+1 8 (cd 1)cd+1 8 (cd+1 8 (cd 3 + cd+1 6 − cd

    − 1 > 0. As such, (213) ≤ cd+1 7 (2γ)cd+1 8 (cd 1)cd+1 8 (cd+1 8 (cd 3 + cd+1 6 − cd

  102. [111]

    − 1) 1 w(cd+1 8 (cd 3 +cd+1 6 −cd 2 )−1) (214) Substituting the bounds of terms I and II into Equation (178) and letting cd 8 ≤ (cd+1 8 (cd 3 + cd+1 6 − cd

  103. [112]

    − 1) yields: P [T (j, ℓ) > w| T (i, ℓ) = τ ] (215) 43 ≤ ucd 8 wcd 8 + cd+1 7 (2γ)cd+1 8 (cd 1)cd+1 8 (cd+1 8 (cd 3 + cd+1 6 − cd

  104. [113]

    − 1) 1 wcd 8 (216) ≤ 1 wcd 8     2cd 1τ cd 3 ∆(j) ! 1 cd 2 + 2γcd+1 4 cd 1 ! 1 cd 3 +cd+1 6 −cd 2 + 1   cd 8 + cd+1 7 (2γ)cd+1 8 (cd 1)cd+1 8 (cd+1 8 (cd 3 + cd+1 6 − cd

  105. [114]

    − 1)   (217) ≤ τ cd 3 cd 8 cd 2 wcd 8     2cd 1 ∆(j) 1 cd 2 + 2γcd+1 4 cd 1 ! 1 cd 3 +cd+1 6 −cd 2 + 1   cd 8 + cd+1 7 (2γ)cd+1 8 (cd 1)cd+1 8 (cd+1 8 (cd 3 + cd+1 6 − cd

  106. [115]

    − 1)   (218) Letting ξd(j) =     2cd 1 ∆(j) 1 cd 2 + 2γcd+1 4 cd 1 ! 1 cd 3 +cd+1 6 −cd 2 + 1   cd 8 + cd+1 7 (2γ)cd+1 8 (cd 1)cd+1 8 (cd+1 8 (cd 3 + cd+1 6 − cd

  107. [116]

    X t∈F Q∗(j∗) − q(j∗, t) | T (i, ℓ) = τ, L(i, ℓ) = L, T(j∗, ℓ) = s, L(j∗, ℓ) = F # (233) ≤ E

    − 1)   (219) completes the proof. Supplemental Inductive Step: V alue Convergence Lemma 11. Assume Assumption 1. Then exists constants cd 4, cd 5 such that for all τ : V ∗(i) − E [V (i, ℓ) | T (i, ℓ) = τ ] ≤ cd 4 τ cd 5 (220) Proof. We use the definition of V (i, ℓ), and sp...

  108. [117]

    Recall that all constants are non-negative: cd k ≥ 0, ∀k ∈ [1, 8], ∀d ∈ [1, D]. Base Case: cD−1 4 = (b − 1)   cD−1 1 ∆min(i) !1/cD−1 2 + 1   (265) cD−1 5 = cD−1 6 = 1 − cD−1 3 cD−1 2 (266) cD−1 7 = (b − 1) max j̸=j∗ ξD−1(j) + (2(b − 1))cD−1 8 + (2cD−1 4 )cD−1 8 (267) where...

  109. [118]

    − 1)   (273) cd 8 = cd+1 8 (cd 3 + cd+1 6 − cd

  110. [119]

    − 1 (274) cd+1 8 (cd 3 + cd+1 6 − cd

  111. [120]

    As cD−1 8 is arbitrary, we pick cD−1 8 = 2 (0.5−c3)D +PD−1 d=1 1 (0.5−c3)d so that Equations (274) and (275) are satisfied for all d ∈ [1, D]

    ≥ 2 (275) cd 2 ≥ cd+1 6 (276) Selecting our exploration law as c1 = 1, c3 ∈ [ 1 4 , 1 2 ), c2 = 2c3 yields cd 5 = cd 6 = 1 2 for all d ∈ [1, D]. As cD−1 8 is arbitrary, we pick cD−1 8 = 2 (0.5−c3)D +PD−1 d=1 1 (0.5−c3)d so that Equations (274) and (275) are satisfied for all d...

  112. [2011]

    433–445, Springer, 2011

    Selected Papers 5 , pp. 433–445, Springer, 2011

    2011

Pith tools

Reviewed August 11, 2026 · model on record in the stance chip above.