Pith. sign in

REVIEW 5 major objections 6 minor 1 cited by

Global Contact-Rich Planning with Sparsity-Rich Semidefinite Relaxations

T0 review · 5 major / 6 minor · reviewed 2026-08-09 · deepseek-v4-flash

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

Pith's one-line read This paper shows that contact-rich motion planning, reformulated as polynomial optimization, can be solved to near global optimality by exploiting sparsity in semidefinite relaxations.

desk verdict The sparsity toolbox and robotics-specific patterns are real contributions, but the certified-gap claim is not backed up because the upper-bound trajectories are never checked for feasibility against the exact polynomial problem. read the letter →

arxiv 2502.02829 v4 pith:G6VVHZBA submitted 2025-02-05 cs.RO math.OC

Shucheng Kang , Guorui Liu , Heng Yang This is my paper · ORCID
classification cs.ROmath.OC MSC 90C2290C2690C23
keywords contact-richmotionplanningpolynomialoptimizationsemidefiniterelaxationmoment-SOShierarchycorrelativesparsitytermexploitationglobal
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

Contact-rich motion planning is usually treated as a hard hybrid control problem with combinatorial contact modes and nonsmooth complementarity constraints. This paper argues that, when written as polynomial optimization, such problems are also sparsity-rich, and that exploiting correlative, term, and robotics-specific sparsity can make high-order semidefinite relaxations small enough to solve in seconds. The result is a pipeline that computes near-globally optimal trajectories with small certified suboptimality gaps across five simulated benchmarks, and a real-world push-T experiment that succeeds even when the model is deliberately wrong. A sympathetic reader would care because this is evidence that global optimality certificates, not just local heuristics, are within reach for contact-rich manipulation.

What carries the argument

The load-bearing mechanism is the sparse moment/sums-of-squares relaxation hierarchy. Correlative sparsity groups problem variables into cliques via chordal-graph extensions, breaking one enormous positive-semidefinite moment matrix into many small ones; term sparsity further partitions monomial bases into blocks so that only a reduced basis, such as the $2n+1$ monomials for $n$ separable contact modes, has to be carried. Robotics-specific patterns (kinematic chains, separating planes, separable contact forces) inject cliques that automatic sparsity detection misses and that keep clique sizes constant rather than growing with the number of bodies or obstacles. The GNS-based minimizer extraction is the second half of the machinery: when the relaxation is not tight or admits multiple solutions, it still produces a feasible approximate minimizer that feeds a local solver for the upper bound.

What would settle it

Solve a small contact-rich instance with a known global optimum (for example, the double integrator with soft walls over a short horizon, where exhaustive enumeration is possible) using the same sparse relaxation pipeline: if the certified gap does not shrink as the relaxation order increases, or if the SDP solver fails to reach high accuracy on a verifiable instance, the paper's near-global-optimality claim for its problem class would be refuted.

Watch

Extended reading notes

Core claim

The paper's central claim is that many instances of contact-implicit planning can be solved to near global optimality. The route is to formulate the planning problem as a polynomial optimization problem -- polynomial objective, polynomial dynamics on Lie-group discretizations, and polynomial constraints for control limits, collision avoidance, and contact complementarity -- and then build sparse moment/sums-of-squares relaxations. Two generic sparsity layers (correlative sparsity over variables and term sparsity over monomials) are augmented with robotics-specific sparsity from kinematic chains, separating hyperplanes, and separable contact modes, which shrink the semidefinite blocks dramatically. With these sparsity-rich relaxations, off-the-shelf SDP solvers return lower bounds in seconds, and a new minimizer extraction routine based on the GNS construction turns the SDP solution into a feasible trajectory whose cost gives a small certified suboptimality gap. The authors also release the SPOT toolbox that automates sparsity detection, visualization, and relaxation generation.

Load-bearing premise

The argument stands on the assumption that the polynomial optimization model in problem (1) -- with Lie-group discretized dynamics and the polynomial surrogate for Coulomb friction and complementarity -- faithfully represents the contact-rich planning task, because the certified suboptimality guarantees apply to that model, not to the physical robot.

Editorial extensions

If this is right

  • For the five benchmark problems with horizon 30, the reported relaxations solve in seconds to minutes, with mean certified suboptimality gaps below 10 percent on four of five tasks and below 1 percent on Push Bot and Push Box.
  • Term sparsity with minimum-fill chordal extension gives near-real-time solve times (1.7 to 5.2 seconds) on the three simpler pushing tasks, at the cost of larger gaps.
  • A receding-horizon planner using a 5-step horizon and 3.7-second replanning achieves 100 percent success in 20 real-world push-T trials, including cases with cable wraps, irregular surfaces, boxes, and stacked T-blocks.
  • Robotics-specific sparsity, especially kinematic-chain cliques, yields both tighter lower bounds and shorter solve times than purely automatic sparsity on the Planar Hand task.
  • The SPOT toolbox makes sparsity patterns visible and user-modifiable, so the same relaxation machinery can be applied to new polynomial optimization problems without hand-coding the chordal extension.

Reading between the lines

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

  • The same separable-contact-mode sparsity likely applies to any polynomial optimization problem with a 'choose one of n modes' structure, such as locomotion gait scheduling, grasping mode selection, or task-and-motion planning; this is an extension the paper gestures at but does not develop.
  • Because the real-world success persists under model mismatch, the practical value may come less from certified optimality of the exact model than from global search over a cheap surrogate model; testing this distinction would require comparing against a local solver with identical replanning and the same surrogate.
  • A straightforward stress test is to take a short-horizon instance with a brute-force verifiable optimum and check whether the certified gap converges to zero as the relaxation order increases; the paper does not report such a convergence study.
  • The paper's per-problem hand-crafted cliques suggest a natural next step: learning or automatically detecting kinematic-chain and contact-mode sparsity from the problem structure, so the 'robotics-specific' layer becomes part of the automatic pipeline.
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

5 major / 6 minor

Summary. The paper formulates contact-rich motion planning as polynomial optimization (POP) and applies Lasserre's Moment-SOS hierarchy with correlative sparsity (CS), term sparsity (TS), and user-injected robotics-specific sparsity (kinematic chains, separable contact modes, separating planes). It introduces SPOT, a C++ toolbox with Python and Matlab interfaces, and reports experiments on Push Bot, Push Box, Push T, Push Box with Tunnel, Planar Hand, plus real-world Push T. The main claims are that high-order sparse SDP relaxations can be solved in seconds by off-the-shelf solvers and yield near-globally optimal solutions with small certified suboptimality, where the suboptimality gap (Eq. 37) is the relative difference between the SDP lower bound and an upper bound obtained by rounding with the local solver CRISP.

Significance. The paper is a substantial empirical/systems contribution: the SPOT toolbox is released, the tutorial-style description of CS-TS is useful, the robotic-specific sparsity patterns are intuitive, and the real-world push-T results are impressive. If the certificates are valid, the paper demonstrates a meaningful step toward global contact-rich planning. The main mathematical machinery (sparse Moment-SOS hierarchy) is standard, and the lower-bound computation does not depend on the authors' prior results. However, the central claim of small certified suboptimality is not uniformly supported by Table II, and the upper-bound feasibility needed for the certificate is not verified; these issues are fixable but currently make the strongest claims premature.

major comments (5)
  1. [§IV, Table II, Eq. (37)] Eq. (37) defines the suboptimality gap ηg as the relative difference between the SDP lower bound flower and an upper bound fupper, which is only a valid certificate if fupper is attained at a feasible point of (1). The paper states that the in-house local solver CRISP [23] is used to 'round a feasible solution', but it never reports any verification that the rounded trajectory satisfies the exact polynomial dynamics and complementarity constraints of (1), e.g. the Lie-group dynamics (A15)-(A18), the complementarity condition (A86), and the friction cone (A88)-(A90). The reported metric -log10(ηkkt) is a KKT residual of a sequential-convex/penalty solver and is not a feasibility certificate for a nonsmooth complementarity problem. If the upper-bound trajectory violates any constraint, fupper can lie below the true optimum and every gap in Table II becomes an underestimate rather than a certified suboptimality. Please add explicit maximum constraint violations for the rounded trajectories and describe how exact feasibility is ensured.
  2. [Abstract and §V vs Table II] The abstract and conclusion assert that the method computes 'near globally optimal solutions ... with small certified suboptimality'. Table II does not support this uniformly: Planar Hand has average gaps of 22.26%, 23.97%, and 25.61% for the three settings, and the SELF+MF rows for Push Box (13.77%) and Push T (35.98%) are also far from small. The claim should be qualified to the tasks and settings where the gaps are small, or the experiments should report instance-level distributions to clarify how often large gaps occur.
  3. [§IV, paragraph after Table II] The text notes that MOSEK failed to solve the SDP to high accuracy for Push Bot (SELF+MAX) and Planar Hand (SELF+MF), yet the corresponding rows are included in Table II without marking. For these rows the lower bound flower is not computed to a certified accuracy, so the reported ηg values are not certified gaps. These rows should either be excluded from the gap averages or be accompanied by solver termination/accuracy diagnostics.
  4. [§III-A and Appendix D] The SELF cliques for Planar Hand are manually defined and are claimed to exploit kinematic-chain sparsity, but the paper does not prove that the resulting clique family satisfies the running intersection property (RIP) required for the sparse Moment-SOS lower bound to be valid. In §III-A the kinematic-chain decomposition is explicitly described as producing a graph that is not chordal. Because all SELF rows of Table II rely on these cliques, a proof or numerical validation that the relaxation remains a valid lower bound for (1) is needed.
  5. [§IV, 'Robust minimizer extraction'] Contribution (III) claims that the GNS-based minimizer extraction has 'superior robustness' over the naive extraction used in TSSOS [25] and [15], but no comparison experiment is reported. The only discussion is qualitative. Since this is presented as a standalone contribution, please add a direct comparison (e.g., per-instance suboptimality gaps and feasibility of extracted candidates for both extraction methods).
minor comments (6)
  1. [§II-D] The word 'pipleline' should be 'pipeline'.
  2. [§I] In the first section, the phrase 'maximal coordinates [?]' contains a missing citation placeholder.
  3. [§III-B] The fourth binary mask in Eq. (31) is labeled Bh_{2,1,2}, duplicating the label of Eq. (30); it should presumably be Bh_{2,1,3}.
  4. [Appendix C2] In the sentence before Eq. (A27), 'fucus' should be 'focus'.
  5. [Table I] The row labeled 'Tunnel' should be labeled 'Push Box with a Tunnel' for consistency with the text.
  6. [Table II] All reported statistics are means only; for random initial states, please report standard deviations or instance-level values to assess variability and worst-case gaps.

Circularity Check

0 steps flagged · score 2.0 of 10

No significant circularity: the lower bounds come from the externally grounded Lasserre Moment-SOS hierarchy, and the upper-bound rounding is done by a code-released local solver. The only weak point is self-reliance on the authors' companion CRISP solver for feasibility, which is a validity risk rather than a definitional circularity.

full rationale

The paper's derivation chain is: model contact-rich planning as the polynomial optimization problem (1); build dense and sparse Moment-SOS relaxations (Propositions 7 and 8) whose lower bounds converge to the POP optimum by standard Lasserre theory [18,19]; solve the SDP with MOSEK to obtain a lower bound flower; extract a candidate solution using a GNS-inspired routine based on the external reference [16]; round it with the local solver CRISP [23] to obtain an upper bound fupper; and report the gap eta_g := |flower - fupper| / (1 + |flower| + |fupper|). None of these steps defines the prediction in terms of a fitted quantity, and no equation in the paper reduces to its own input by construction. The relaxation itself is independent of the authors' prior results; the sparsity patterns, including the robotics-specific cliques, are structural choices rather than parameters fitted to the reported gaps. Self-citations appear in two places that matter: [15] (same research group) for the chain-like sparsity and the 'naive' extraction baseline, and [23] (companion CRISP paper) for the feasible upper bound. Both are code-released and externally reproducible, so under the stated rules they count as independent evidence rather than circular support. A legitimate correctness concern is that the paper never verifies that the CRISP-rounded trajectory exactly satisfies the polynomial dynamics, complementarity, and friction-cone constraints of (1); if the candidate is infeasible, fupper could lie below the true optimum and the certified gaps in Table II would be optimistic. Similarly, MOSEK failed to solve two SDP instances to high accuracy, which can also make the bounds unreliable. These are validity risks, however, not circularity: the gap formula is not rigged, and the lower bound is externally grounded. The real-world 'dirty' push-T experiments are explicitly outside the model, so they do not bear on the certificate's internal validity. Overall, the central claim is not circular; the score of 2 reflects only the minor self-reliance on companion-tool outputs and the authors' earlier sparsity analysis, neither of which is definitionally load-bearing.

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

The central claim rests on standard Moment-SOS theory, chordal-graph decomposition, and domain-specific modeling choices. The hand-selected relaxation orders, chordal extension heuristics, TS options, and manual cliques are the effective free parameters; they substantially change the reported gaps (0.08% to 35.98%). No new physical entities are introduced.

free parameters (4)
  • Relaxation order d = 2 for most tasks, 3 for Tunnel
    Hand-chosen trade-off between tightness and SDP size; directly controls the reported gaps and solve times.
  • CS/TS sparsity option = SELF + NON / MAX / MF
    Each experiment uses a different hand-selected combination; gaps range from 0.08% to 35.98% depending on this choice (Table II).
  • Manual variable cliques for Planar Hand = 14 cliques of size 6-14
    Hand-crafted cliques (Appendix D) are required to avoid the over-one-million-constraint SDP from automatic sparsity; the method's strongest result depends on this manual input.
  • GNS minimizer selection rule = highest-weight minimizer averaged across cliques
    Heuristic adaptation of [16]; its success is empirical and no ablation vs. naive extraction is shown.
assumptions (4)
  • standard math Lasserre Moment-SOS hierarchy converges to the POP optimum under compactness
    Invoked in Prop. 7 and Prop. 8 to justify lower bounds and asymptotic convergence.
  • standard math Chordal extension and clique decomposition preserve the equivalence of sparse and dense moment relaxations under RIP
    Used throughout Section II; RIP is explicitly checked only for the separation-plane pattern in Section III-A, not for all injected cliques.
  • domain assumption Contact-rich dynamics are representable as polynomial dynamics with semi-algebraic constraints
    Stated as assumptions in Section I; Lie-group discretization and Coulomb friction polynomialization in Appendix C are approximations.
  • ad hoc to paper The reduced basis for separable contact modes (size 2n+1) remains valid under the chosen chordal extension and partial TS options
    Derived for n=3, d=2 in Section III-B; asserted for general n without proof and without verifying that chordal extension does not reintroduce cross terms.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Global Contact-Rich Planning with Sparsity-Rich Semidefinite Relaxations." pith.science (2026). https://pith.science/paper/G6VVHZBA

@misc{pith2026250202829,
  author       = {Pith},
  title        = {Pith review of: Global Contact-Rich Planning with Sparsity-Rich Semidefinite Relaxations},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/G6VVHZBA}},
  note         = {Machine review of arXiv:2502.02829}
}
read the original abstract

We show that contact-rich motion planning is also sparsity-rich when viewed as polynomial optimization (POP). We can exploit not only the correlative and term sparsity patterns that are general to all POPs, but also specialized sparsity patterns from the robot kinematic structure and the separability of contact modes. Such sparsity enables the design of high-order but sparse semidefinite programming (SDPs) relaxations--building upon Lasserre's moment and sums of squares hierarchy--that (i) can be solved in seconds by off-the-shelf SDP solvers, and (ii) compute near globally optimal solutions to the nonconvex contact-rich planning problems with small certified suboptimality. Through extensive experiments both in simulation (Push Bot, Push Box, Push Box with Obstacles, and Planar Hand) and real world (Push T), we demonstrate the power of using convex SDP relaxations to generate global contact-rich motion plans. As a contribution of independent interest, we release the Sparse Polynomial Optimization Toolbox (SPOT)--implemented in C++ with interfaces to both Python and Matlab--that automates sparsity exploitation for robotics and beyond.

Figures

Figures reproduced from arXiv: 2502.02829 by the authors.

Figure 1
Figure 1. Contact-rich planning is sparsity-rich. (a) Sparsity graph of planar hand manipulation showing two types of sparsity. (b) Sparsity enables high-order and tight, yet small-scale, semidefinite programming (SDP) relaxations solvable by off-the-shelf SDP solvers, computing certified near globally optimal trajectories for a suite of simulated problems. (c) Real-world validation on push-T. Planning powered by global optim… view at source ↗
Figure 3
Figure 3. An example of chordal extension and maximal cliques. [PITH_FULL_IMAGE:figures/full_fig_p004_3.png] view at source ↗
Figure 2
Figure 2. Double integrator with soft wall. A. Chordal Graph Definition 2 (Chordal graph). A graph G = (V, E) is chordal if every cycle of four or more vertices has a chord—an edge connecting two non-adjacent vertices in the cycle. For a quick example, the graph in [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figures from the paper (8 more)
Figure 4
Figure 4. Figure 4: CSP graph of the toy Example 1. Red circle: maxi￾mal clique {x0, v0, λ1,0, λ2,0}. Orange circle: maximal clique {x0, x1, v0}. Only variables in the first and last planning steps are shown for simplicity. Before we present the sparse Moment-SOS hierarchy, it is useful t…
Figure 5
Figure 5. Figure 5: Comparison of the moment matrices in dense and [PITH_FULL_IMAGE:figures/full_fig_p006_5.png]
Figure 6
Figure 6. Figure 6: (a) G g 2,1,1 : support extension for g1 in clique I1; (b) G g 2,2,0 : support extension for g0 in clique I2. We shall illustrate this using our robotics example. Example 9 (TSP Graph of Example 1). Consider the toy example’s two cliques: I1 := {x0, v0, λ1,0, λ2,0} and…
Figure 7
Figure 7. Figure 7: Overall pipeline of the Sparse Polynomial Optimization Toolbox (SPOT). Blue curves: the automatic detection of [PITH_FULL_IMAGE:figures/full_fig_p008_7.png]
Figure 8
Figure 8. Figure 8: Robotics-specific sparsity patterns. B. Term-level Robotics-Specific Sparsity Separable contact modes. Frequently in contact-rich plan￾ning, we will have to “select one out of a bunch of modes” (cf. §C2 and§C3). It can be modelled as polynomial equalities: h0 ≜ X i∈[n]…
Figure 9
Figure 9. Figure 9: illustrations of five contact-rich planning tasks. (a) Push [PITH_FULL_IMAGE:figures/full_fig_p009_9.png]
Figure 10
Figure 10. Figure 10: More globally optimal trajectories from S [PITH_FULL_IMAGE:figures/full_fig_p011_10.png]
Figure 11
Figure 11. Figure 11: More demonstrations from real-world “dirty” push-T tasks. From top to bottom: T-block (1) contained in a box; (2) [PITH_FULL_IMAGE:figures/full_fig_p012_11.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. A Curvature-Aware Rank-Adaptive Distributed Augmented-Lagrangian Solver for Large-Scale SDPs

    math.OC 2026-07 conditional novelty 7.0 of 10

    CARDAL grows the rank of a Burer–Monteiro factorization only when dual-slack curvature is negative and distributes the resulting low-rank augmented-Lagrangian solver across GPUs.

Reference graph

Works this paper leans on

59 extracted references · 52 canonical work pages · cited by 1 Pith paper

  1. [23]

    On the surprising robustness of sequential convex optimization for contact-implicit motion planning

    Yulin Li, Haoyu Han, Shucheng Kang, Jun Ma, and Heng Yang. On the surprising robustness of sequential convex optimization for contact-implicit motion planning. arXiv preprint arXiv:2502.01055, 2025. 10

    arXiv 2025

  2. [25]

    Tssos: a julia library to exploit sparsity for large-scale polynomial optimization

    Victor Magron and Jie Wang. Tssos: a julia library to exploit sparsity for large-scale polynomial optimization. arXiv preprint arXiv:2103.00915 , 2021. 2, 3

    arXiv 2021

  3. [15]

    Fast and certifiable trajectory optimiza- tion

    Shucheng Kang, Xiaoyang Xu, Jay Sarva, Ling Liang, and Heng Yang. Fast and certifiable trajectory optimiza- tion. arXiv preprint arXiv:2406.05846, 2024. 2, 3, 7, 10, 12

    arXiv 2024

  4. [1]

    Mosek optimization toolbox for matlab

    Mosek ApS. Mosek optimization toolbox for matlab. User’s Guide and Reference Manual, Version, 4(1), 2019. 9

    work page 2019

  5. [2]

    Real-time multi- contact model predictive control via admm

    Alp Aydinoglu and Michael Posa. Real-time multi- contact model predictive control via admm. In 2022 International Conference on Robotics and Automation (ICRA), pages 3414–3421. IEEE, 2022. 2

    work page 2022

  6. [3]

    Stabilization of complementarity systems via contact-aware controllers

    Alp Aydinoglu, Philip Sieg, Victor M Preciado, and Michael Posa. Stabilization of complementarity systems via contact-aware controllers. IEEE Transactions on Robotics, 38(3):1735–1754, 2021. 2

    work page 2021

  7. [4]

    Bodlaender and Arie M.C.A

    Hans L. Bodlaender and Arie M.C.A. Koster. Treewidth computations i. upper bounds. Information and Compu- tation, 208(3):259–275, 2010. ISSN 0890-5401. 4

    work page 2010

  8. [5]

    Trajectory optimization of contact-rich motions using implicit dif- ferential dynamic programming

    Iordanis Chatzinikolaidis and Zhibin Li. Trajectory optimization of contact-rich motions using implicit dif- ferential dynamic programming. IEEE Robotics and Automation Letters, 6(2):2626–2633, 2021. 2

    work page 2021

Show all 59 references
  1. [6]

    Trajectotree: Trajectory optimization meets tree search for planning multi-contact dexterous manipulation

    Claire Chen, Preston Culbertson, Marion Lepert, Mac Schwager, and Jeannette Bohg. Trajectotree: Trajectory optimization meets tree search for planning multi-contact dexterous manipulation. In 2021 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) , pag...

    2021

  2. [7]

    Contact mode guided motion planning for quasidynamic dexterous manipulation in 3d

    Xianyi Cheng, Eric Huang, Yifan Hou, and Matthew T Mason. Contact mode guided motion planning for quasidynamic dexterous manipulation in 3d. In 2022 International Conference on Robotics and Automation (ICRA), pages 2730–2736. IEEE, 2022. 2

    2022

  3. [8]

    Dynamic locomotion in the mit cheetah 3 through convex model-predictive control

    Jared Di Carlo, Patrick M Wensing, Benjamin Katz, Gerardo Bledt, and Sangbae Kim. Dynamic locomotion in the mit cheetah 3 through convex model-predictive control. In 2018 IEEE/RSJ international conference on intelligent robots and systems (IROS) , pages 1–9. IEEE,

    2018

  4. [9]

    Kino- dynamic motion planning for multi-legged robot jumping via mixed-integer convex program

    Yanran Ding, Chuanzheng Li, and Hae-Won Park. Kino- dynamic motion planning for multi-legged robot jumping via mixed-integer convex program. In 2020 IEEE/RSJ In- ternational Conference on Intelligent Robots and Systems (IROS), pages 3998–4005. IEEE, 2020. 2

    2020

  5. [10]

    Inci- dence matrices and interval graphs

    Delbert Ray Fulkerson and Oliver Alfred Gross. Inci- dence matrices and interval graphs. Pacific Journal of Mathematics, 15:835–855, 1965. 4

    1965

  6. [11]

    Algorithmic graph theory and perfect graphs

    Martin Charles Golumbic. Algorithmic graph theory and perfect graphs. Elsevier, 2004. 4

    2004

  7. [12]

    Towards tight convex relax- ations for contact-rich manipulation

    Bernhard P Graesdal, Shao YC Chia, Tobia Mar- cucci, Savva Morozov, Alexandre Amice, Pablo A Par- rilo, and Russ Tedrake. Towards tight convex relax- ations for contact-rich manipulation. arXiv preprint arXiv:2402.10312, 2024. 2, 17

    2024 arXiv

  8. [13]

    The development of honda humanoid robot

    Kazuo Hirai, Masato Hirose, Yuji Haikawa, and Toru Takenaka. The development of honda humanoid robot. In Proceedings. 1998 IEEE international conference on robotics and automation (Cat. No. 98CH36146) , vol- ume 2, pages 1321–1326. IEEE, 1998. 1

    1998

  9. [14]

    Sparse polynomial optimization with unbounded sets

    Lei Huang, Shucheng Kang, Jie Wang, and Heng Yang. Sparse polynomial optimization with unbounded sets. arXiv preprint arXiv:2401.15837 , 2024. 2

    2024 arXiv

  10. [16]

    Minimizer extraction in polynomial optimization is robust

    Igor Klep, Janez Povh, and Jurij V olcic. Minimizer extraction in polynomial optimization is robust. SIAM Journal on Optimization , 28(4):3177–3207, 2018. 3, 10

    2018

  11. [17]

    Balance control and locomotion planning for humanoid robots using nonlinear centroidal models

    Frans Anton Koolen. Balance control and locomotion planning for humanoid robots using nonlinear centroidal models. PhD thesis, Massachusetts Institute of Technol- ogy, 2020. 2

    2020

  12. [18]

    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. 2

    2001

  13. [19]

    Convergent sdp-relaxations in poly- nomial optimization with sparsity

    Jean B Lasserre. Convergent sdp-relaxations in poly- nomial optimization with sparsity. SIAM Journal on optimization, 17(3):822–843, 2006. 6

    2006

  14. [20]

    Convergent sdp-relaxations in poly- nomial optimization with sparsity

    Jean B Lasserre. Convergent sdp-relaxations in poly- nomial optimization with sparsity. SIAM Journal on optimization, 17(3):822–843, 2006. 2, 7

    2006

  15. [21]

    Fast contact-implicit model predictive control

    Simon Le Cleac’h, Taylor A Howell, Shuo Yang, Chi- Yen Lee, John Zhang, Arun Bishop, Mac Schwager, and Zachary Manchester. Fast contact-implicit model predictive control. IEEE Transactions on Robotics, 2024. 2

    2024

  16. [22]

    Computational geometric mechanics and control of rigid bodies

    Taeyoung Lee. Computational geometric mechanics and control of rigid bodies . PhD thesis, University of Michigan, 2008. 2, 16

    2008

  17. [24]

    Manipulation and active sensing by pushing using tactile feedback

    Kevin M Lynch, Hitoshi Maekawa, and Kazuo Tanie. Manipulation and active sensing by pushing using tactile feedback. In IROS, volume 1, pages 416–421, 1992. 18

    1992

  18. [26]

    Sparse polynomial opti- mization: theory and practice

    Victor Magron and Jie Wang. Sparse polynomial opti- mization: theory and practice . World Scientific, 2023. 2

    2023

  19. [27]

    Variational contact-implicit trajectory optimization

    Zachary Manchester and Scott Kuindersma. Variational contact-implicit trajectory optimization. In Robotics Re- search: The 18th International Symposium ISRR , pages 985–1000. Springer, 2020. 2

    2020

  20. [28]

    Warm start of mixed- integer programs for model predictive control of hybrid systems

    Tobia Marcucci and Russ Tedrake. Warm start of mixed- integer programs for model predictive control of hybrid systems. IEEE Transactions on Automatic Control , 66 (6):2433–2448, 2020. 2

    2020

  21. [29]

    Mechanics and planning of manip- ulator pushing operations

    Matthew T Mason. Mechanics and planning of manip- ulator pushing operations. The International Journal of Robotics Research, 5(3):53–71, 1986. 1, 17

    1986

  22. [30]

    Crocoddyl: An efficient and versatile framework for multi-contact optimal control

    Carlos Mastalli, Rohan Budhiraja, Wolfgang Merkt, Guilhem Saurel, Bilal Hammoud, Maximilien Naveau, Justin Carpentier, Ludovic Righetti, Sethu Vijayakumar, and Nicolas Mansard. Crocoddyl: An efficient and versatile framework for multi-contact optimal control. In 2020 IEEE Inte...

    2020

  23. [31]

    Discovery of complex behaviors through contact- invariant optimization

    Igor Mordatch, Emanuel Todorov, and Zoran Popovi ´c. Discovery of complex behaviors through contact- invariant optimization. ACM Transactions on Graphics (ToG), 31(4):1–8, 2012. 2

    2012

  24. [32]

    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. 2

    2024 arXiv

  25. [33]

    Apriltag: A robust and flexible visual fiducial system

    Edwin Olson. Apriltag: A robust and flexible visual fiducial system. In 2011 IEEE international conference on robotics and automation , pages 3400–3407. IEEE,

    2011

  26. [34]

    Global planning for contact-rich manipulation via local smoothing of quasi-dynamic contact models

    Tao Pang, HJ Terry Suh, Lujie Yang, and Russ Tedrake. Global planning for contact-rich manipulation via local smoothing of quasi-dynamic contact models. IEEE Transactions on robotics, 2023. 2

    2023

  27. [35]

    A direct method for trajectory optimization of rigid bodies through contact

    Michael Posa, Cecilia Cantu, and Russ Tedrake. A direct method for trajectory optimization of rigid bodies through contact. The International Journal of Robotics Research, 33(1):69–81, 2014. 2, 20

    2014

  28. [36]

    Algorithmic aspects of vertex elimination on graphs

    Donald J Rose, R Endre Tarjan, and George S Lueker. Algorithmic aspects of vertex elimination on graphs. SIAM Journal on computing , 5(2):266–283, 1976. 4

    1976

  29. [37]

    Synthesis and stabilization of complex behaviors through online trajectory optimization

    Yuval Tassa, Tom Erez, and Emanuel Todorov. Synthesis and stabilization of complex behaviors through online trajectory optimization. In 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems , pages 4906–4913. IEEE, 2012. 2

    2012

  30. [38]

    Control-limited differential dynamic programming

    Yuval Tassa, Nicolas Mansard, and Emo Todorov. Control-limited differential dynamic programming. In 2014 IEEE International Conference on Robotics and Automation (ICRA), pages 1168–1175. IEEE, 2014. 2

    2014

  31. [39]

    Convex geometric motion planning on lie groups via moment relaxation

    Sangli Teng, Ashkan Jasour, Ram Vasudevan, and Maani Ghaffari. Convex geometric motion planning on lie groups via moment relaxation. In Robotics: Science and Systems, 2023. 2, 3, 16

    2023

  32. [40]

    Convex geometric motion planning of multi- body systems on lie groups via variational integrators and sparse moment relaxation

    Sangli Teng, Ashkan Jasour, Ram Vasudevan, and Maani Ghaffari. Convex geometric motion planning of multi- body systems on lie groups via variational integrators and sparse moment relaxation. The International Journal of Robotics Research, page 02783649241296160, 2024. 2

    2024

  33. [41]

    Sums of squares and semidef- inite program relaxations for polynomial optimization problems with structured sparsity

    Hayato Waki, Sunyoung Kim, Masakazu Kojima, and Masakazu Muramatsu. Sums of squares and semidef- inite program relaxations for polynomial optimization problems with structured sparsity. SIAM Journal on Optimization, 17(1):218–242, 2006. 4

    2006

  34. [42]

    An introduction to polynomial optimization

    Jie Wang. An introduction to polynomial optimization

  35. [43]

    Tssos: A moment-sos hierarchy that exploits term spar- sity

    Jie Wang, Victor Magron, and Jean-Bernard Lasserre. Tssos: A moment-sos hierarchy that exploits term spar- sity. SIAM Journal on optimization , 31(1):30–58, 2021. 2, 6

    2021

  36. [44]

    Cs-tssos: Correlative and term sparsity for large-scale polynomial optimization

    Jie Wang, Victor Magron, Jean B Lasserre, and Ngoc Hoang Anh Mai. Cs-tssos: Correlative and term sparsity for large-scale polynomial optimization. ACM Transac- tions on Mathematical Software , 48(4):1–26, 2022. 6, 16

    2022

  37. [45]

    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. 2

    2020

  38. [46]

    Semidefinite optimization and relax- ation

    Heng Yang. Semidefinite optimization and relax- ation. Lecture notes: https://hankyang.seas.harvard.edu/ Semidefinite/, 2024. 6

    2024

  39. [47]

    Certifiably optimal outlier- robust geometric perception: Semidefinite relaxations and scalable global optimization

    Heng Yang and Luca Carlone. Certifiably optimal outlier- robust geometric perception: Semidefinite relaxations and scalable global optimization. IEEE transactions on pattern analysis and machine intelligence , 45(3):2816– 2834, 2022. 2

    2022

  40. [48]

    A new semidefinite relaxation for linear and piecewise-affine optimal control with time scaling

    Lujie Yang, Tobia Marcucci, Pablo A Parrilo, and Russ Tedrake. A new semidefinite relaxation for linear and piecewise-affine optimal control with time scaling. 2

  41. [49]

    Dynamic on-palm manipulation via controlled sliding

    William Yang and Michael Posa. Dynamic on-palm manipulation via controlled sliding. arXiv preprint arXiv:2405.08731, 2024. 2

    2024 arXiv

  42. [50]

    Computing the minimum fill-in is np-complete

    Mihalis Yannakakis. Computing the minimum fill-in is np-complete. SIAM Journal on Algebraic Discrete Methods, 2(1):77–79, 1981. 4

    1981

  43. [51]

    K. Yunt. Optimal trajectory planning for structure- variant mechanical systems. In International Workshop on Variable Structure Systems, 2006. VSS’06. , pages 298–303, 2006. doi: 10.1109/VSS.2006.1644534. 2

    2006 arXiv

  44. [52]

    A combined con- tinuation and penalty method for the determination of optimal hybrid mechanical trajectories

    Kerim Yunt and Christoph Glocker. A combined con- tinuation and penalty method for the determination of optimal hybrid mechanical trajectories. In Iutam Sym- posium on Dynamics and Control of Nonlinear Systems with Uncertainty: Proceedings of the IUTAM Symposium held in Nanjin...

    2006

  45. [53]

    The outer level is governed by CS’s relaxation order d

  46. [54]

    Define the optimal value of (A3) as ρk d

    The inner level is controlled by TS’s sparse order k, which corresponds to the number of iterations used to generate new Bg d,l,j and Bh d,l,j. Define the optimal value of (A3) as ρk d. The sequence {ρk d}k≥1 is monotonically non-decreasing and satisfies ρk d ≤ ρd for all k. W...

  47. [55]

    The configuration is shown in Figure 9 (a)

    Push Bot: Push bot is essentially cart-pole with soft wall. The configuration is shown in Figure 9 (a). a is cart’s position, θ is pole’s angle, k1 and k2 is soft wall’s elastic modulus, λ1 and λ2 is two contact forces between two walls and pole’s tip. The goal is to stabilize...

  48. [56]

    Our goal is to push the box from one configuration ((sx, sy, θ)) to another

    Push Box: Consider a simple pusher-slider system illustrated in Figure 9 (b). Our goal is to push the box from one configuration ((sx, sy, θ)) to another. From [12], given (1) the pusher’s position (px, py) and the contact force (Fx, Fy) in the slider frame; (2) the slider’s p...

  49. [57]

    Unlike 4 modes in the box setting, now we have 8 modes to assign

    Push T-block: Now we consider a more complicated pushing task: push a T-block, as illustrated in Figure 9 (c). Unlike 4 modes in the box setting, now we have 8 modes to assign. From [24], when µ1 is uniformly distributed between the slider and the table, the friction center co...

  50. [58]

    To model the collision avoidance constraints, we approximate the box as a union of two circles, as shown in Figure 9 (d)

    Push Box with a Tunnel: Everything is the same as Push Box setting, except that the box needs to avoid two circle obstacles this time. To model the collision avoidance constraints, we approximate the box as a union of two circles, as shown in Figure 9 (d). For each obstacle-sl...

  51. [59]

    r" and "l

    Planar Hand: The geometric and mechanical information of the Planar Hand system is illustrated in Figure 9 (e). The goal is to rotate the circle disk 360◦ with planar hand’s two finger tips, while minimize the translation of the disk’s center of mass. Kinematics of the fingers...

Pith tools

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