Pith. sign in

REVIEW 3 major objections 5 minor 63 references

Mixed Discrete and Continuous Planning using Shortest Walks in Graphs of Convex Sets

T0 review · 3 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash

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

Pith's one-line read This paper shows that allowing vertex revisits in graphs of convex sets yields a unified, fast approximate solver for mixed discrete-continuous planning problems.

desk verdict A solid extension of GCS planning to walks, with a real admissibility gap in the SDP lower bounds that should be fixed before relying on the heuristic. read the letter →

arxiv 2507.10878 v1 pith:42ODNBND submitted 2025-07-15 cs.RO

Savva Morozov , Tobia Marcucci , Bernhard Paus Graesdal , Alexandre Amice , Pablo A. Parrilo , Russ Tedrake This is my paper · ORCID
classification cs.RO
keywords shortest-walkproblemgraphsofconvexsetscost-to-golowerboundssemidefiniteprogrammingmixeddiscrete-continuousplanningmotionhybridsystemsincrementalsearch
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

The paper introduces the Shortest-Walk Problem in a Graph of Convex Sets and argues that it is a natural, unified language for mixed discrete-continuous planning problems in robotics. Unlike shortest paths, walks may revisit vertices, which lets a fixed-duration trajectory piece be reused and lets contact or skill modes repeat in hybrid control. To solve the NP-hard walk problem, the paper synthesizes piecewise-quadratic lower bounds on the cost-to-go via semidefinite programming and uses those bounds to guide incremental greedy search. Experiments in collision-free motion planning, skill chaining, and footstep planning report faster solve times than path-based alternatives with comparable trajectory quality. A sympathetic reader would take this as evidence that one formulation can replace several specialized planners.

What carries the argument

The load-bearing object is the cost-to-go lower bound synthesized by the SDP relaxation of the Bellman equation. For each vertex $v$, $J_v(x_v)$ is a convex quadratic underestimator of the true cost-to-go to the target; the SDP maximizes $J_s$ at the source while enforcing $J_u(x_u) \le l_u(x_u) + l_e(x_u,x_v) + J_v(x_v)$ on every edge. The search then uses these bounds in a greedy $n$-step lookahead: at each step it minimizes the cost of the next $n$ segments plus the residual bound, commits to the first segment, and repeats. The restrictions that make the SDP finite-dimensional, quadratic costs, sets that are intersections of polyhedra and ellipsoids, and convex quadratic $J_v$, are precisely what must hold for the bound to remain a true lower bound.

What would settle it

Solve the restricted SDP program (4) on a small GCS with a non-quadratic cost, such as $l_e = \|x_u - x_v\|^3$, then compute the true cost-to-go at many sampled points by solving the layered $K$-step SPP for growing $K$ or by exact enumeration; if any sampled point has $J_v(x)$ greater than the true cost-to-go, the heuristic is inadmissible and the paper's claim that the approximations sacrifice only tightness, not validity, is broken.

Watch

Extended reading notes

Core claim

The central discovery is that the Shortest-Walk Problem in a GCS, where a walk may repeat vertices and pick a new continuous point at each visit, has a practical approximate solution method, and that this formulation captures problems the Shortest-Path formulation does not handle naturally. The method computes, once per GCS, a piecewise-quadratic lower bound on the cost-to-go at each vertex by solving a single SDP over the whole graph, then runs greedy multi-step lookahead search guided by those bounds, re-optimizing the trajectory on the chosen walk and removing unnecessary cycles as post-processing. The paper claims this yields a natural language for motion planning with derivative constraints, skill chaining, and hybrid-system optimal control, and reports average query times 1.5 times faster than shortest-path planning with time-optimal path parameterization and 2.3 times faster than shortest-path planning with non-convex post-processing, with trajectory durations within 1-2 percent.

Load-bearing premise

The SDP cost-to-go lower bounds remain true lower bounds after costs are replaced by quadratic approximations, sets are restricted to intersections of polyhedra and ellipsoids, and each $J_v$ is forced to be convex quadratic; if any of these restrictions makes $J$ overestimate the true cost-to-go, the greedy heuristic can be misled and solution quality degrades with no detection mechanism.

Editorial extensions

If this is right

  • A single GCS construction supports many queries after one cost-to-go synthesis step, so multi-query settings amortize the SDP cost: the motion-planning experiment spends about 45 seconds on synthesis and 0.46 seconds per query.
  • Acceleration limits and, in principle, higher-order derivative constraints can be enforced during search rather than in a separate post-processing stage.
  • Hybrid optimal control can be posed directly as a walk over contact-mode vertices, making the mode sequence and the continuous state and control trajectories jointly optimizable.
  • Because greedy search is heuristic, the quality of the returned walk depends on how tight the lower bounds are, and the paper's cycle-removal post-processing improves that quality in practice.
  • The formulation unifies collision-free motion planning, skill chaining, and footstep planning, problems that previously required specialized solution strategies.

Reading between the lines

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

  • Beyond the paper: if the same SDP lower bounds are used inside a complete search such as a walk-version of A* rather than greedy lookahead, the precomputation could supply optimality guarantees instead of heuristic solutions.
  • Editorial extension: the fixed-duration, vertex-revisiting representation suggests a testable extension to changing environments, where only the affected vertex's bound would need to be recomputed and the SDP warm-started.
  • Editorial inference: the many-to-many cost-to-go variant mentioned in the paper could support receding-horizon replanning under disturbances, since a new target reuses the existing bound instead of requiring a fresh SDP solve.
  • Editorial extension: the formal connection between revisits and repeated skills points toward task-and-motion planning where the same manipulation primitive must be applied multiple times; the skill-chaining experiment is the first instance of that use.
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

3 major / 5 minor

Summary. This paper introduces the Shortest-Walk Problem (SWP) in a Graph of Convex Sets (GCS), a generalization of the shortest-path problem in which vertex revisits are allowed and each visit selects a continuous point from a convex set. The authors derive a Bellman equation for the cost-to-go (Section IV-A), relax it to an infinite-dimensional LP (Section IV-B), and obtain finite-dimensional piecewise-quadratic lower bounds via semidefinite programming (Section IV-C). These lower bounds guide an incremental greedy search with multi-step lookahead (Section IV-D). The method is demonstrated on three robotics applications: collision-free motion planning with acceleration limits, skill chaining, and footstep planning for a hybrid ZMP walker. The central claim is that the SWP in GCS is a natural and computationally efficient unifying formulation for mixed discrete-continuous planning problems.

Significance. If the lower bounds remain valid after the restrictions in Section IV-C, the paper provides a reusable multi-query planning framework that extends the authors' earlier SPP-in-GCS work to the walk setting. The Bellman derivation in Section IV-A is clean, the SDP relaxation is well motivated, and the three application domains illustrate genuine breadth. The paper is also commendably explicit that the extraction search lacks completeness and optimality guarantees. However, the absence of a conservatism check for the quadratic cost and set approximations, together with unspecified hyperparameters and potentially unfair timing comparisons, leaves the central performance claims under-supported. The contribution is promising and within the scope of the journal, but it requires substantive additional verification and reporting before acceptance.

major comments (3)
  1. [IV-C (Eq. (4c))] The paper replaces non-quadratic costs l_v, l_e with 'quadratic approximations' and restricts sets to intersections of polyhedra and ellipsoids, but it never proves or verifies that these replacements are conservative. For the SDP solution to be a valid lower bound, constraint (4c) must hold for the true costs and true feasible sets; if an approximating cost overestimates the true cost at any feasible point, the optimized J can exceed the true cost-to-go, making the heuristic in Eq. (5) non-admissible. Since the search in Section IV-D has no completeness or optimality guarantee, solution quality can degrade silently. Please add a proof of conservatism under the stated approximations, or a pointwise verification procedure (e.g., checking (4c) on the true costs and sets for the actual instances), and state how each quadratic approximation was constructed.
  2. [IV-D, V-B, V-C] The reported performance depends on several unspecified or simulated choices. The lookahead horizon n in Eq. (5) is never given; the edge-cost offset epsilon from Section II-D is never quantified; and the SDP objective used in the experiments (e.g., 'maximizing the average value' in Sections V-B and V-C) differs from the single-source objective of program (4) without explanation. In addition, Section VI discloses that solve times assume solving up to 10 convex programs in parallel and are simulated rather than measured. Please specify all hyperparameters, give the exact SDP solved in each experiment, and report actual wall-clock times.
  3. [V, Figure 7] The timing comparison in Figure 7 is not apples-to-apples. For the SWP, the 45-second cost-to-go synthesis is excluded from the reported 0.46-second average, while the SPP baselines include all their computation as single-query methods. Over the 100-query battery, amortizing the synthesis adds roughly 0.45 second per query, which is comparable to the reported speedup. The paper should report total time over the batch with and without amortization, include per-query variability (error bars or distributions), and provide statistical support for the 'within 1-2 percent' duration claim.
minor comments (5)
  1. [IV-B] The sentence 'the optimal solution to program (4) yields an exact solution to the Bellman equation' is only true for the infinite-dimensional LP; the finite-dimensional SDP of Section IV-C is a restricted problem, so this wording should be qualified to avoid implying that the numerical solution is exact.
  2. [IV-D] The statement 'we consider all candidate n-step decision sequences' can involve an exponential number of walks when the graph has high out-degree; a brief discussion of this complexity or a bound on the practical choice of n would help readers assess scalability.
  3. [III-C] There is a typo in 'evolves evolves according to different affine dynamics'; also, the spacing in 'PW A' is inconsistent throughout the paper and should be normalized to 'PWA'.
  4. [V and VI] The caveat that solve times are simulated parallelized times appears only in Section VI; it should be stated prominently where the timing results are first reported in Section V.
  5. [Figure 7] The figure shows box-whisker-style plots, but the caption does not explain what the boxes, whiskers, and points represent; please add this information for clarity.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the SDP-synthesized cost-to-go lower bounds are not fitted to experimental outcomes, and the evaluation is against external SPP+TOPP baselines.

full rationale

The derivation chain is self-contained. The paper defines the SWP, derives the Bellman optimality condition (Eq. 3), relaxes it to the convex program (4) over functions J_v, and then restricts J_v to convex quadratics in Section IV-C. The resulting J_v are used only as guiding heuristics in the greedy lookahead (Eq. 5); they are not fit to the reported solve times or trajectory durations. The experimental comparisons in Section V-A are against independently motivated baselines (SPP with TOPP and with non-convex post-processing), so the claimed speedups are not forced by construction. The main caveat — Section IV-C uses "quadratic approximations for non-quadratic l_v, l_e" and the paper never proves these approximations preserve the lower-bound property — is a correctness/admissibility risk, not a circularity: a non-conservative heuristic would degrade solution quality rather than tautologically certify it. Section VI's limitation notes concern computational practicality and parallel-timing assumptions, not circular derivation. Self-citations to [34] and [39] provide background and methodology from prior work, but the load-bearing claim of this paper (SWP as a useful model and fast solver) is tested against external baselines. No equation reduces to its own input by construction.

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

The central method rests on a modest set of modeling choices: positive edge costs to keep walks finite, convex and quadratic restrictions for the SDP, the principle of optimality, and convex decompositions of the application domains. No hidden physical entities are introduced. The main unverified premise is that the quadratic approximations preserve lower bounds on cost-to-go.

free parameters (6)
  • Fixed Bezier duration Delta_t = 125 ms = 125 ms
    Chosen by the user in Section V-A to make acceleration constraints convex; it controls discretization error and the length of optimal walks, but is not fitted to data.
  • Lookahead horizon n in greedy search = not reported
    Section IV-D introduces n in equation (5); the experiments never report the value used, yet it directly affects solution quality and solve time.
  • Number of parallel convex solves assumed for timing = 10
    Section VI states solve times are simulated assuming up to 10 programs run in parallel; this is an assumption, not actual wall-clock time on the reported laptop.
  • Small positive edge-cost offset epsilon = not specified
    Section II-D requires every edge cost to have positive minimum; the paper says an epsilon can be added but never gives its value, and the lower bound depends on it.
  • Quadratic degree of cost-to-go lower bounds = 2
    Section IV-C fixes J_v to convex quadratics, and uses quadratic approximations for non-quadratic costs; this order choice is a modeling restriction.
  • Objective for many-source lower bounds = average over source vertices
    In Sections V-B and V-C the paper maximizes the average value of lower bounds across multiple source vertices, a heuristic choice not derived from program (4).
assumptions (6)
  • ad hoc to paper Every edge cost has a strictly positive minimum value (Section II-D).
    Needed to guarantee finite optimal walks; if zero-cost edges exist, the infimum may require infinitely many steps.
  • domain assumption The principle of optimality for SWP in GCS (Section IV-A).
    Assumes subwalks of a shortest walk are shortest; stated without proof, though reasonable given additive costs and a stationary target.
  • domain assumption GCS vertex sets are compact and costs are convex quadratics, or can be convex-quadratically approximated (Section IV-C).
    Required for the SDP formulation; the paper assumes such approximations are available for non-quadratic costs.
  • domain assumption Hybrid dynamics can be arbitrarily well approximated by piecewise affine systems (Section III-C).
    Basis for casting hybrid control as SWP on GCS, citing prior literature [49,50,3].
  • standard math Semidefinite programming and LMI nonnegativity enforcement for polynomials over basic semialgebraic sets (Section IV-C).
    Standard SOS/SDP machinery, but invoked with reference [39] and not proved in this paper.
  • domain assumption Convex decompositions of skills and collision-free space exist and are available, e.g. via IRIS (Sections III-B, V-A).
    The whole pipeline depends on preprocessing that may require manual tuning, as acknowledged in Section VI.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Mixed Discrete and Continuous Planning using Shortest Walks in Graphs of Convex Sets." pith.science (2026). https://pith.science/paper/42ODNBND

@misc{pith2026250710878,
  author       = {Pith},
  title        = {Pith review of: Mixed Discrete and Continuous Planning using Shortest Walks in Graphs of Convex Sets},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/42ODNBND}},
  note         = {Machine review of arXiv:2507.10878}
}
read the original abstract

We study the Shortest-Walk Problem (SWP) in a Graph of Convex Sets (GCS). A GCS is a graph where each vertex is paired with a convex program, and each edge couples adjacent programs via additional costs and constraints. A walk in a GCS is a sequence of vertices connected by edges, where vertices may be repeated. The length of a walk is given by the cumulative optimal value of the corresponding convex programs. To solve the SWP in GCS, we first synthesize a piecewise-quadratic lower bound on the problem's cost-to-go function using semidefinite programming. Then we use this lower bound to guide an incremental-search algorithm that yields an approximate shortest walk. We show that the SWP in GCS is a natural language for many mixed discrete-continuous planning problems in robotics, unifying problems that typically require specialized solutions while delivering high performance and computational efficiency. We demonstrate this through experiments in collision-free motion planning, skill chaining, and optimal control of hybrid systems.

Figures

Figures reproduced from arXiv: 2507.10878 by the authors.

Figure 1
Figure 1. Application of the SWP in GCS to a variety of robotics [PITH_FULL_IMAGE:figures/full_fig_p001_1.png] view at source ↗
Figure 2
Figure 2. A GCS where a shortest walk is not a path. [PITH_FULL_IMAGE:figures/full_fig_p002_2.png] view at source ↗
Figure 3
Figure 3. Contrasting the SPP and SWP formulations for the [PITH_FULL_IMAGE:figures/full_fig_p003_3.png] view at source ↗
Figures from the paper (6 more)
Figure 4
Figure 4. Figure 4: An actuated pendulum with a soft wall (a) can be [PITH_FULL_IMAGE:figures/full_fig_p004_4.png]
Figure 5
Figure 5. Figure 5: A naive approach to solving the SWP in GCS in (a) [PITH_FULL_IMAGE:figures/full_fig_p005_5.png]
Figure 6
Figure 6. Figure 6: Visual comparison of SPP in GCS with TOPP (a,b) and SWP in GCS (c) formulations. Both planners are tasked with [PITH_FULL_IMAGE:figures/full_fig_p007_6.png]
Figure 7
Figure 7. Figure 7: For collision-free planning scenario (Section [PITH_FULL_IMAGE:figures/full_fig_p007_7.png]
Figure 8
Figure 8. Figure 8: An 8-step plan where the top-down suction-cup arm is tasked with sorting three objects into the green target region. [PITH_FULL_IMAGE:figures/full_fig_p008_8.png]
Figure 9
Figure 9. Figure 9: Visualizations of the footstep plans across stepping stones for the Atlas bipedal robot. The SWP in GCS jointly [PITH_FULL_IMAGE:figures/full_fig_p009_9.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

63 extracted references · 55 canonical work pages

  1. [1]

    The MOSEK optimization toolbox for MATLAB manual

    MOSEK ApS. The MOSEK optimization toolbox for MATLAB manual. Version 10.1., 2024. URL http://docs. mosek.com/latest/toolbox/index.html

    work page 2024

  2. [2]

    Generation of collision-free trajectories for a quadrocopter fleet: A sequential convex programming approach

    Federico Augugliaro, Angela P Schoellig, and Raffaello D’Andrea. Generation of collision-free trajectories for a quadrocopter fleet: A sequential convex programming approach. In 2012 IEEE/RSJ international conference on Intelligent Robots and Systems , pages 1917–1922. IEEE, 2012

    work page 2012

  3. [3]

    Control of systems integrating logic, dynamics, and constraints

    Alberto Bemporad and Manfred Morari. Control of systems integrating logic, dynamics, and constraints. Automatica, 35(3):407–427, 1999

    work page 1999

  4. [4]

    Survey of numerical methods for trajectory optimization

    John T Betts. Survey of numerical methods for trajectory optimization. Journal of guidance, control, and dynam- ics, 21(2):193–207, 1998

    work page 1998

  5. [5]

    Semidefinite optimization and convex algebraic geometry

    Grigoriy Blekherman, Pablo A Parrilo, and Rekha R Thomas. Semidefinite optimization and convex algebraic geometry. SIAM, 2012

    work page 2012

  6. [6]

    Sequential composition of dynamically dexterous robot behaviors

    Robert R Burridge, Alfred A Rizzi, and Daniel E Koditschek. Sequential composition of dynamically dexterous robot behaviors. The International Journal of Robotics Research, 18(6):534–555, 1999

    work page 1999

  7. [7]

    A hybrid approach to intricate motion, manipulation and task planning

    Stephane Cambon, Rachid Alami, and Fabien Gravot. A hybrid approach to intricate motion, manipulation and task planning. The International Journal of Robotics Research, 28(1):104–126, 2009

    work page 2009

  8. [8]

    GCS*: Forward heuristic search on implicit graphs of convex sets

    Shao Yuan Chew Chia, Rebecca H Jiang, Bernhard Paus Graesdal, Leslie Pack Kaelbling, and Russ Tedrake. GCS*: Forward heuristic search on implicit graphs of convex sets. arXiv preprint arXiv:2407.08848 , 2024

    arXiv 2024

Show all 63 references
  1. [9]

    Non-Euclidean motion planning with graphs of geodesically-convex sets

    Thomas Cohn, Mark Petersen, Max Simchowitz, and Russ Tedrake. Non-Euclidean motion planning with graphs of geodesically-convex sets. Robotics: Science and Systems, 2023

    2023

  2. [10]

    Footstep planning on uneven terrain with mixed-integer convex optimization

    Robin Deits and Russ Tedrake. Footstep planning on uneven terrain with mixed-integer convex optimization. In 2014 IEEE-RAS international conference on humanoid robots, pages 279–286. IEEE, 2014

    2014

  3. [11]

    Computing large con- vex regions of obstacle-free space through semidefinite programming

    Robin Deits and Russ Tedrake. Computing large con- vex regions of obstacle-free space through semidefinite programming. In Algorithmic Foundations of Robotics XI: Selected Contributions of the Eleventh International Workshop on the Algorithmic Foundations of Robotics , pages 1...

    2015

  4. [12]

    Efficient mixed-integer planning for uavs in cluttered environments

    Robin Deits and Russ Tedrake. Efficient mixed-integer planning for uavs in cluttered environments. In 2015 IEEE international conference on robotics and automa- tion (ICRA), pages 42–49. IEEE, 2015

    2015

  5. [13]

    Sampling-based robot motion planning: A review

    Mohamed Elbanhawi and Milan Simic. Sampling-based robot motion planning: A review. IEEE Access, 2:56–77, 2014

    2014

  6. [14]

    Scottyactivity: Mixed discrete-continuous plan- ning with convex optimization

    Enrique Fernandez-Gonzalez, Brian Williams, and Erez Karpas. Scottyactivity: Mixed discrete-continuous plan- ning with convex optimization. Journal of Artificial Intelligence Research, 62:579–664, 2018

    2018

  7. [15]

    PDDLStream: Integrating symbolic planners and blackbox samplers via optimistic adaptive planning

    Caelan Reed Garrett, Tom ´as Lozano-P ´erez, and Leslie Pack Kaelbling. PDDLStream: Integrating symbolic planners and blackbox samplers via optimistic adaptive planning. In Proceedings of the international conference on automated planning and scheduling , volume 30, pages 440–...

    2020

  8. [16]

    Integrated task and motion plan- ning

    Caelan Reed Garrett, Rohan Chitnis, Rachel Holladay, Beomjoon Kim, Tom Silver, Leslie Pack Kaelbling, and Tom´as Lozano-P ´erez. Integrated task and motion plan- ning. Annual review of control, robotics, and autonomous systems, 4(1):265–293, 2021

    2021

  9. [17]

    SNOPT: An SQP algorithm for large-scale constrained optimization

    Philip E Gill, Walter Murray, and Michael A Saunders. SNOPT: An SQP algorithm for large-scale constrained optimization. SIAM review, 47(1):99–131, 2005

    2005

  10. [18]

    Optimal sampling-based planning for linear-quadratic kinodynamic systems

    Gustavo Goretkin, Alejandro Perez, Robert Platt, and George Konidaris. Optimal sampling-based planning for linear-quadratic kinodynamic systems. In 2013 IEEE International Conference on Robotics and Automation , pages 2429–2436. IEEE, 2013

    2013

  11. [19]

    Towards tight convex relaxations for contact-rich manipulation

    Bernhard P Graesdal, Shao YC Chia, Tobia Marcucci, Savva Morozov, Alexandre Amice, Pablo A Parrilo, and Russ Tedrake. Towards tight convex relaxations for contact-rich manipulation. Robotics: Science and Systems, 2024

    2024

  12. [20]

    Sequential quadratic programming for task plan optimization

    Dylan Hadfield-Menell, Christopher Lin, Rohan Chitnis, Stuart Russell, and Pieter Abbeel. Sequential quadratic programming for task plan optimization. In 2016 IEEE/RSJ international conference on intelligent robots and systems (IROS) , pages 5040–5047. IEEE, 2016

    2016

  13. [21]

    Fast marching tree: A fast marching sampling-based method for optimal motion planning in many dimensions

    Lucas Janson, Edward Schmerling, Ashley Clark, and Marco Pavone. Fast marching tree: A fast marching sampling-based method for optimal motion planning in many dimensions. The International journal of robotics research, 34(7):883–921, 2015

    2015

  14. [22]

    Hierar- chical task and motion planning in the now

    Leslie Pack Kaelbling and Tom ´as Lozano-P´erez. Hierar- chical task and motion planning in the now. In2011 IEEE International Conference on Robotics and Automation , pages 1470–1477. IEEE, 2011

    2011

  15. [23]

    Biped walking pattern generation by using preview control of zero-moment point

    Shuuji Kajita, Fumio Kanehiro, Kenji Kaneko, Kiyoshi Fujiwara, Kensuke Harada, Kazuhito Yokoi, and Hirohisa Hirukawa. Biped walking pattern generation by using preview control of zero-moment point. In 2003 IEEE international conference on robotics and automation (Cat. No. 03CH...

    2003

  16. [24]

    Sampling-based al- gorithms for optimal motion planning

    Sertac Karaman and Emilio Frazzoli. Sampling-based al- gorithms for optimal motion planning. The international journal of robotics research , 30(7):846–894, 2011

    2011

  17. [25]

    Reducibility among combinatorial problems

    Richard M Karp. Reducibility among combinatorial problems. Springer, 2010

    2010

  18. [26]

    Probabilistic roadmaps for path planning in high-dimensional configuration spaces

    Lydia E Kavraki, Petr Svestka, J-C Latombe, and Mark H Overmars. Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE transac- tions on Robotics and Automation , 12(4):566–580, 1996

    1996

  19. [27]

    Skill discovery in continuous reinforcement learning domains using skill chaining

    George Konidaris and Andrew Barto. Skill discovery in continuous reinforcement learning domains using skill chaining. Advances in neural information processing systems, 22, 2009

    2009

  20. [28]

    Efficiently solving general rearrangement tasks: A fast extension primitive for an incremental sampling-based planner

    Athanasios Krontiris and Kostas E Bekris. Efficiently solving general rearrangement tasks: A fast extension primitive for an incremental sampling-based planner. In 2016 IEEE International Conference on Robotics and Automation (ICRA), pages 3924–3931. IEEE, 2016

    2016

  21. [29]

    Temporal logic motion plan- ning with convex optimization via graphs of convex sets

    Vince Kurtz and Hai Lin. Temporal logic motion plan- ning with convex optimization via graphs of convex sets. IEEE Transactions on Robotics, 39(5):3791–3804, 2023

    2023

  22. [30]

    Global optimization with polynomials and the problem of moments

    Jean B Lasserre. Global optimization with polynomials and the problem of moments. SIAM Journal on opti- mization, 11(3):796–817, 2001

    2001

  23. [31]

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

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

    1998

  24. [32]

    Strong formulations for hybrid system control

    Jisun Lee, Hyungki Im, and Alper Atamt ¨urk. Strong formulations for hybrid system control. arXiv preprint arXiv:2412.11541, 2024

    2024 arXiv

  25. [33]

    Funnel libraries for real-time robust feedback motion planning

    Anirudha Majumdar and Russ Tedrake. Funnel libraries for real-time robust feedback motion planning. The International Journal of Robotics Research , 36(8):947– 982, 2017

    2017

  26. [34]

    Graphs of Convex Sets with Applications to Optimal Control and Motion Planning

    Tobia Marcucci. Graphs of Convex Sets with Applications to Optimal Control and Motion Planning . PhD thesis, Massachusetts Institute of Technology, 2024

    2024

  27. [35]

    Motion planning around obstacles with convex optimization

    Tobia Marcucci, Mark Petersen, David von Wrangel, and Russ Tedrake. Motion planning around obstacles with convex optimization. Science robotics , 8(84):eadf7843, 2023

    2023

  28. [36]

    Fast path planning through large collections of safe boxes

    Tobia Marcucci, Parth Nobel, Russ Tedrake, and Stephen Boyd. Fast path planning through large collections of safe boxes. IEEE Transactions on Robotics , 2024

    2024

  29. [37]

    Shortest paths in graphs of convex sets

    Tobia Marcucci, Jack Umenberger, Pablo Parrilo, and Russ Tedrake. Shortest paths in graphs of convex sets. SIAM Journal on Optimization , 34(1):507–532, 2024

    2024

  30. [38]

    Mixed-integer quadratic program trajectory generation for heterogeneous quadrotor teams

    Daniel Mellinger, Alex Kushleyev, and Vijay Kumar. Mixed-integer quadratic program trajectory generation for heterogeneous quadrotor teams. In 2012 IEEE inter- national conference on robotics and automation , pages 477–483. IEEE, 2012

    2012

  31. [39]

    Multi-query shortest-path problem in graphs of convex sets

    Savva Morozov, Tobia Marcucci, Alexandre Amice, Bernhard Paus Graesdal, Rohan Bosworth, Pablo A Parrilo, and Russ Tedrake. Multi-query shortest-path problem in graphs of convex sets. arXiv preprint arXiv:2409.19543, 2024

    2024 arXiv

  32. [40]

    Implicit graph search for planning on graphs of convex sets

    Ramkumar Natarajan, Chaoqi Liu, Howie Choset, and Maxim Likhachev. Implicit graph search for planning on graphs of convex sets. arXiv preprint arXiv:2410.08909, 2024

    2024 arXiv

  33. [41]

    Structured semidefinite programs and semialgebraic geometry methods in robustness and opti- mization

    Pablo A Parrilo. Structured semidefinite programs and semialgebraic geometry methods in robustness and opti- mization. California Institute of Technology, 2000

    2000

  34. [42]

    Semidefinite programming relaxations for semialgebraic problems

    Pablo A Parrilo. Semidefinite programming relaxations for semialgebraic problems. Mathematical programming, 96:293–320, 2003

    2003

  35. [43]

    Growing convex collision-free regions in configuration space using non- linear programming

    Mark Petersen and Russ Tedrake. Growing convex collision-free regions in configuration space using non- linear programming. arXiv preprint arXiv:2303.14737 , 2023

    2023 arXiv

  36. [44]

    A mixed-integer conic pro- gram for the moving-target traveling salesman prob- lem based on a graph of convex sets

    Allen George Philip, Zhongqiang Ren, Sivakumar Rathi- nam, and Howie Choset. A mixed-integer conic pro- gram for the moving-target traveling salesman prob- lem based on a graph of convex sets. arXiv preprint arXiv:2403.04917, 2024

    2024 arXiv

  37. [45]

    Aircraft tra- jectory planning with collision avoidance using mixed integer linear programming

    Arthur Richards and Jonathan P How. Aircraft tra- jectory planning with collision avoidance using mixed integer linear programming. In Proceedings of the 2002 American Control Conference (IEEE Cat. No. CH37301), volume 3, pages 1936–1941. IEEE, 2002

    2002

  38. [46]

    Mixed integer programming for multi- vehicle path planning

    Tom Schouwenaars, Bart De Moor, Eric Feron, and Jonathan How. Mixed integer programming for multi- vehicle path planning. In 2001 European control confer- ence (ECC), pages 2603–2608. IEEE, 2001

    2001

  39. [47]

    Motion planning with sequential convex optimization and convex colli- sion checking

    John Schulman, Yan Duan, Jonathan Ho, Alex Lee, Ibrahim Awwal, Henry Bradlow, Jia Pan, Sachin Patil, Ken Goldberg, and Pieter Abbeel. Motion planning with sequential convex optimization and convex colli- sion checking. The International Journal of Robotics Research, 33(9):1251...

    2014

  40. [48]

    SMC: Satisfiability modulo convex program- ming

    Yasser Shoukry, Pierluigi Nuzzo, Alberto L Sangiovanni- Vincentelli, Sanjit A Seshia, George J Pappas, and Paulo Tabuada. SMC: Satisfiability modulo convex program- ming. Proceedings of the IEEE , 106(9):1655–1679, 2018

    2018

  41. [49]

    Nonlinear regulation: The piecewise linear approach

    Eduardo Sontag. Nonlinear regulation: The piecewise linear approach. IEEE Transactions on automatic control, 26(2):346–358, 1981

    1981

  42. [50]

    Interconnected automata and linear systems: A theoretical framework in discrete-time

    Eduardo D Sontag. Interconnected automata and linear systems: A theoretical framework in discrete-time. In International Hybrid Systems Workshop, pages 436–448. Springer, 1995

    1995

  43. [51]

    Combined task and motion planning through an extensible planner- independent interface layer

    Siddharth Srivastava, Eugene Fang, Lorenzo Riano, Ro- han Chitnis, Stuart Russell, and Pieter Abbeel. Combined task and motion planning through an extensible planner- independent interface layer. In 2014 IEEE international conference on robotics and automation (ICRA) , pages 6...

    2014

  44. [52]

    A ∗ for graphs of convex sets

    Kaarthik Sundar and Sivakumar Rathinam. A ∗ for graphs of convex sets. arXiv preprint arXiv:2407.17413 , 2024

    2024 arXiv

  45. [53]

    Between MDPs and semi-MDPs: A framework for tem- poral abstraction in reinforcement learning

    Richard S Sutton, Doina Precup, and Satinder Singh. Between MDPs and semi-MDPs: A framework for tem- poral abstraction in reinforcement learning. Artificial intelligence, 112(1-2):181–211, 1999

    1999

  46. [54]

    LQR-trees: Feedback motion plan- ning on sparse randomized trees

    Russ Tedrake et al. LQR-trees: Feedback motion plan- ning on sparse randomized trees. In Robotics: Science and Systems, volume 2009, 2009

    2009

  47. [55]

    Logic-geometric programming: An optimization-based approach to combined task and mo- tion planning

    Marc Toussaint. Logic-geometric programming: An optimization-based approach to combined task and mo- tion planning. In IJCAI, pages 1930–1936, 2015

    1930

  48. [56]

    Time-optimal path tracking for robots: A convex optimization approach

    Diederik Verscheure, Bram Demeulenaere, Jan Swevers, Joris De Schutter, and Moritz Diehl. Time-optimal path tracking for robots: A convex optimization approach. IEEE Transactions on Automatic Control , 54(10):2318– 2327, 2009

    2009

  49. [57]

    Using graphs of convex sets to guide nonconvex trajectory optimiza- tion

    David von Wrangel and Russ Tedrake. Using graphs of convex sets to guide nonconvex trajectory optimiza- tion. In 2024 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 9863–9870. IEEE, 2024

    2024

  50. [58]

    Zero- moment point—thirty five years of its life

    Miomir Vukobratovi ´c and Branislav Borovac. Zero- moment point—thirty five years of its life. International journal of humanoid robotics , 1(01):157–173, 2004

    2004

  51. [59]

    Kinody- namic RRT*: Asymptotically optimal motion planning for robots with linear dynamics

    Dustin J Webb and Jur Van Den Berg. Kinody- namic RRT*: Asymptotically optimal motion planning for robots with linear dynamics. In 2013 IEEE inter- national conference on robotics and automation , pages 5054–5061. IEEE, 2013

    2013

  52. [60]

    Approximating robot configura- tion spaces with few convex sets using clique covers of visibility graphs

    Peter Werner, Alexandre Amice, Tobia Marcucci, Daniela Rus, and Russ Tedrake. Approximating robot configura- tion spaces with few convex sets using clique covers of visibility graphs. International Conference on Robotics and Automation, 2024

    2024

  53. [61]

    Faster algorithms for growing collision-free convex polytopes in robot configuration space

    Peter Werner, Thomas Cohn, Rebecca H Jiang, Tim Seyde, Max Simchowitz, Russ Tedrake, and Daniela Rus. Faster algorithms for growing collision-free convex polytopes in robot configuration space. arXiv preprint arXiv:2410.12649, 2024

    arXiv

  54. [62]

    R3T: Rapidly-exploring random reachable set tree for optimal kinodynamic planning of nonlinear hybrid systems

    Albert Wu, Sadra Sadraddini, and Russ Tedrake. R3T: Rapidly-exploring random reachable set tree for optimal kinodynamic planning of nonlinear hybrid systems. In 2020 IEEE International Conference on Robotics and Automation (ICRA), pages 4245–4251. IEEE, 2020

    2020

  55. [63]

    Optimization-based collision avoidance

    Xiaojing Zhang, Alexander Liniger, and Francesco Bor- relli. Optimization-based collision avoidance. IEEE Transactions on Control Systems Technology, 29(3):972– 983, 2020

    2020

Pith tools

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