{"id":"e6b45fb7-4eeb-4b52-887d-5494f870eadf","arxiv_id":"2507.19210","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"A measure-based convex relaxation, built from graphs of convex sets, provides near-optimal lower bounds and scalable mode planning for hybrid optimal control.","lead":"This paper constructs a convex optimization formulation for optimal control of hybrid, mode-switching systems by combining occupation-measure relaxations with graph-of-convex-sets theory. It reports lower bounds close to nonconvex solutions on several planning benchmarks, with large speedups over mixed-integer formulations.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Eq. (6f) places boundary measures on Xi×Ui, but (6b)–(6e) require state-space measures; as written the GMP is ill-posed and the lower-bound claim is not supported.","rationale":"The paper's claimed contribution is a convex measure relaxation of hybrid optimal control with a global lower-bound guarantee. The derivation of that claim hinges on the substitution that produces the GMP (6). The weakest point in that derivation is the status of the boundary measures: constraints (6b)–(6e) are only meaningful if μij0 and μijT are measures on Xi, and the transition equalities require support on Xi∩Xj, whereas (6f) places them in M+(Xi×Ui). This is not a cosmetic issue, because the mismatch first affects the degree-2 moment relaxations used in the numerical results. The public implementation and reproducible benchmarks are genuine independent evidence in the paper's favor, and the gap is repairable by correcting the measure spaces and adding support constraints, but until that repair is stated and checked the lower-bound property is not established. This is precisely the assumption the reader identified, and my read does not change the conditional verdict.","tokens_in":9236,"tokens_out":7412,"duration_ms":81283,"concrete_test":"Re-derive the GMP from (2) with boundary measures declared as state measures: take μij0, μijT ∈ M+(Xi) and add the support condition supp(μkiT) ∪ supp(μik0) ⊆ Xi∩Xk for every coupled transition before imposing (6c)–(6e). Compare this corrected GMP with the printed formulation (6f) on a two-mode scalar example (X=[0,1], U=[-1,1], f1=x+u, f2=-x+u, μ0=δ_{0.5}, free μT, quadratic stage costs, degree 2). If the feasible sets or optimal values differ, the reformulation as stated in the paper is incorrect. As a complementary check, inspect the public repository to determine whether the implemented boundary moment variables include input moments; if they do not, (6f) is a notation error that still needs the missing intersection support constraints.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central construction substitutes edge measures (μij0, μij, μijT) into the graph-of-convex-sets program (5) and claims the resulting GMP (6) is a reformulation of the hybrid optimal control problem (1). For this substitution to be valid, the boundary terms in the transport equation (6b) must be measures on the state space Xi, exactly as in (2b)–(2c), where μ0, μT ∈ M+(X). The transition constraints (6c)–(6e) then require these state measures to be equated across modes that meet only on Xi∩Xj, as the dual continuity constraint (7c) makes explicit. Yet (6f) declares μij0, μij, μijT ∈ M+(Xi×Ui). Taken literally, equality (6d) with a given state-only μ0 cannot hold, because no measure on Xi×Ui is a measure on Xi as an equality of measures on the same space; even under a marginal interpretation, the input component of μij0 is unconstrained and no support condition confines μijT to Xi∩Xj before it is identified with an initial measure of the next mode. Either reading breaks the chain of inclusions used to argue that every feasible trajectory of (1) embeds into (6) and that every feasible (6) yields a valid occupation-measure certificate. The degree-0 equivalence to (4) does not expose the problem, because at degree 0 only the total mass of the boundary measures is visible, so the missing input moments and missing intersection support constraints first bite at the degree-2 relaxations actually used in the experiments.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a convex formulation for optimal control of piecewise-polynomial hybrid systems by instantiating the graphs of convex sets framework with occupation measures. The construction assigns to each mode transition a triple of initial, trajectory, and terminal measures, and concatenates them through node constraints analogous to the shortest-path LP, yielding the generalized moment problem (6). The authors claim that (6) is a relaxation of the hybrid optimal control problem (1), that its truncated moment hierarchy provides lower bounds on the optimal cost, and they demonstrate the approach on temporal-logic planning benchmarks and two INTERACTION traffic scenarios, comparing solve times against an MIQP formulation and objective values against a nonconvex QCQP. The paper also provides code at a public repository.","tokens_in":9598,"tokens_out":10114,"duration_ms":117281,"significance":"If the central construction is corrected and the lower-bound claim is proven, the paper would offer a useful convex relaxation route for hybrid optimal control that scales to large mode counts, in contrast to mixed-integer encodings. A notable strength is that the method is implemented and evaluated on realistic benchmarks, with solve times of seconds for several problems where the MIQP is reported as intractable. The experimental comparison is also honest in reporting a weak bound for rover-2, although the paper's general 'typically in the vicinity' claim is stronger than that row supports. The reliance on established tools from [17] and [21] rather than on fitted parameters is a methodological strength. However, the main theorem-like claim is presently not supported because of an inconsistency in the stated domains of the boundary measures in Eq. (6f), which affects the embedding and lower-bound arguments.","major_comments":[{"comment":"The boundary measures μij0 and μijT are declared to live in M+(Xi×Ui), but the transport equation (6b) and the transition constraints (6c)–(6e) require them to be state-space measures on Xi, exactly as μ0 and μT are state measures in (2c). As written, the equality in (6c) compares measures on different spaces, namely Xi×Ui and Xk×Uk, so it is not a well-posed equality of measures; if one instead interprets it through marginalization to Xi∩Xk, then the input components are unconstrained and nothing forces the support of the boundary measures to the intersection that the dual constraint (7c) assumes. This inconsistency breaks the claimed embedding of feasible trajectories of (1) into (6) and therefore the lower-bound assertion in §IV-D. The fix is to declare μij0, μijT ∈ M+(Xi), μij ∈ M+(Xi×Ui), and to add support or equality conditions on Xi∩Xk for the boundary measures; a proof of the lower-bound claim should then be supplied.","section":"§III-A, Eq. (6f)"},{"comment":"The statement that 'at relaxation degree 0, (6) is identical to (4)' is not correct for the quadratic costs used in the experiments. A degree-0 moment relaxation sees only the total mass of each measure, so it cannot represent the inner product ⟨ci, μij⟩ unless ci is constant, whereas the edge weights lij in (4) already encode costs. What coincides at degree 0 is only the flow-conservation structure of the mode sequence, not the cost objective. The text should be reworded accordingly, otherwise it overstates the equivalence between the shortest-path LP and the degree-0 relaxation.","section":"§III-A1, paragraph after Eq. (6)"},{"comment":"The claim that the lower bound is 'typically in the vicinity' of the nonconvex solution is not supported by the rover-2 row: the GMP reports 0.16 while the QCQP reports 2.26, a gap of roughly a factor of 14, or more than 90%. The paper's tie hypothesis is plausible but is not tested, and the discussion should either report a higher-degree relaxation for rover-2 or explicitly qualify this outlier before making a general statement about tightness.","section":"§IV-D, Table I"}],"minor_comments":[{"comment":"The phrase 'edge costs lij associated with each vertex (i,j)' should read 'each edge (i,j)', since the indices in (4) denote edges of the graph.","section":"§II-C, Eq. (4)"},{"comment":"The text says it restates [21, Theorem 5.3], but the displayed program (5) is a specialization to affine vertex constraints and linear costs; please state explicitly that it is a special case.","section":"§II-D, Eq. (5)"},{"comment":"The min/max over i in the dual objective and the index conventions for Vsi and Vit are not derived or explained; a short derivation or a clarification of the notation would help the reader verify the duality claim.","section":"§III-A2, Eq. (7a)"},{"comment":"For benchmarks with '–' in the MIQP columns, the paper should state explicitly whether the MIQP was not formulated or whether it exceeded a time or memory limit; 'intractable' is not a measured quantity.","section":"Table I"},{"comment":"The MIQP comparison fixes h = 0.3 and N = 30 to match stlcg-2; please state whether the same discretization was attempted for the larger benchmarks and why it was not reported.","section":"§IV-D"},{"comment":"The statement that 'the optimal solution collapses to the path of minimal dynamical cost' is presented as a property of the relaxation; it would be clearer to say whether this is observed in the experiments or guaranteed by the theory, since the theory itself is not proved in the paper.","section":"Figure 2 and §III-A"}],"recommendation":"major_revision","confidential_remarks":"The paper fits the journal's scope and the open-source implementation is a concrete asset. The main obstacle is the unaddressed inconsistency in the boundary-measure domains in Eq. (6f), which is central to the lower-bound claim. The degree-0 equivalence claim is also too strong. I would not reject the paper because the construction appears repairable with a standard measure-theoretic argument, but the revision needs to make that argument explicit. The rover-2 gap should be handled carefully to avoid overclaiming practical tightness."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things you should know. The synthesis—occupation-measure relaxations inside the graphs-of-convex-sets framework—is genuinely new and practically promising, with a public implementation. But the central formulation, Eq. (6f), puts the boundary measures in the wrong space; as written, the lower-bound proof does not go through.\n\nWhat it does well: it handles mode-dependent input spaces, which Zhao et al. explicitly did not, and it demonstrates strong degree-2 lower bounds on four of five temporal-logic benchmarks. The traffic scenarios are a nice touch, and the MIQP speedup, when the MIQP is tractable, is real (2.8 s vs. 62 s on stlcg-1). The code is public, which makes the experiments reproducible.\n\nThe soft spot is the measure-domain error. Eq. (6f) declares μij0, μij, μijT ∈ M+(Xi×Ui). The transport equation (6b) then equates div_fi μij (a signed measure on Xi) to a difference of measures on Xi×Ui, which is not a well-defined equation. The concatenation constraints (6c)-(6e) try to equate these product measures with the state-only μ0 and μT. The dual constraint (7c) shows the intended domain: boundary measures should live on Xi∩Xj. Until this is corrected, the claimed inclusion of feasible hybrid trajectories into (6), and the converse, are unsupported. It is fixable—replace (6f) with M+(Xi) and add support constraints—but it is the load-bearing statement of the paper.\n\nTwo lesser concerns. The rover-2 lower bound is 0.16 vs. 2.26 for the upper bound, so the 'typically in the vicinity' claim has a conspicuous exception. And the MIQP comparison is only on two small cases; on stlcg-2 the GMP has no speed advantage (both 0.7 s). The intractability argument for the other cases is plausible, but the scaling claim rests on one favorable benchmark.\n\nMy take: the idea deserves a serious referee. The error is real and must be fixed, and the empirical claims need sharper qualifiers, but the direction is sound and the implementation is a solid start. I would not cite it in its current form, but I would read the revision.","headline":"A genuinely new synthesis of occupation-measure relaxations with graph-of-convex-sets, but the central formulation as written has a measure-domain error that breaks the lower-bound proof.","tokens_in":10098,"tokens_out":7279,"would_cite":false,"duration_ms":64488,"reading_group":"maybe","serious_thinker":"no","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C22","49J15","93C30"],"pacs":[],"model":"deepseek-v4-flash","headline":"A hybrid optimal control problem over many discrete modes can be relaxed to one convex semidefinite program whose optimum is a global lower bound on the true cost.","keywords":["hybrid optimal control","occupation measures","generalized moment problem","piecewise polynomial systems","semidefinite programming","temporal logic planning","convex relaxation","lower bound"],"falsifier":"Take a two-mode system with equal dynamics but different input spaces across modes and an optimal trajectory that switches while using a nonzero input at the switching instant. Solve the degree-2 GMP (6); if, because the boundary measures in (6f) sit on $X_i \\times U_i$ rather than $X_i$, the relaxation cannot represent the switch, its optimum will lie above the true optimum, falsifying the universal lower-bound statement. A direct check is whether the dual transition constraint (7c), which uses $X_i \\cap X_j$, is violated for any feasible boundary measure.","tokens_in":9069,"feed_emoji":"🧮","tokens_out":9984,"duration_ms":93934,"temperature":0.7,"pith_summary":"This paper claims that optimal control of piecewise polynomial hybrid systems—systems that switch among finitely many continuous dynamics—can be reformulated as one convex optimization problem rather than a mixed-integer one. The reformulation places, on every possible mode transition, an occupation-measure relaxation of the continuous dynamics, then links those edge measures with mass-conservation constraints that mirror the flow balance of a shortest-path linear program. The result is a generalized moment problem whose moment truncations are semidefinite programs; solving one gives a global lower bound on the true hybrid optimal cost, and its dual yields piecewise-polynomial value functions. If the claim holds, hybrid trajectory planning with large numbers of discrete modes, including temporal-logic and traffic specifications, becomes tractable in seconds where mixed-integer encodings are intractable.","feed_headline":"Measure relaxation turns hybrid control into a fast lower bound","feed_subtitle":"A convex program bounds mode-switching trajectories in seconds, where mixed-integer planning stalls.","key_machinery":"The load-bearing object is the hybrid occupation-measure GMP (6): each possible mode transition carries three measure variables, and the graph's node balance equations become mass-conservation constraints on those measures. The two structural ingredients are the transport equation $\\mathrm{div}_{f_i} \\mu^{ij} = \\mu^{ij}_0 - \\mu^{ij}_T$, which forces each segment measure to be consistent with the mode dynamics, and the exchange condition that the total terminal measure of incoming transitions equals the total initial measure of outgoing ones, with source and sink equations fixing the global initial and terminal measure. Moment truncation turns this infinite-dimensional convex program into a semidefinite program by requiring Hankel moment matrices and localizing matrices to be positive semidefinite; at degree zero the shortest-path LP is recovered. The dual certificates are piecewise-polynomial value functions satisfying a Hamilton-Jacobi-Bellman inequality in each mode and a nonnegativity continuity condition across shared state boundaries.","core_discovery":"The central discovery is that the hybrid optimal control problem (1) can be rewritten exactly as the generalized moment problem (6) by introducing, for each transition $(i,j)$, a triple of nonnegative measures—initial, trajectory, and terminal—on $X_i \\times U_i$. The transport equation $\\mathrm{div}_{f_i} \\mu^{ij} = \\mu^{ij}_0 - \\mu^{ij}_T$ enforces consistency of each segment with the continuous dynamics, while constraints (6c)–(6e) conserve measure at mode switches exactly as edge flows are conserved in the shortest-path LP. Truncating moments yields a convex semidefinite program whose optimum is argued to be a lower bound on the optimal cost, with dual piecewise-polynomial value functions. In the reported benchmarks, degree-2 relaxations produce lower bounds close to the nonconvex upper bounds—3.28 versus 3.45 on the first navigation task and 74.20 versus 75.40 on the roundabout—while mixed-integer formulations become intractable on the large-mode instances.","pith_inferences":["The paper does not spell out that the boundary measures in (6f) must be marginalized to the state space before the transition constraints are imposed; if that marginalization is added, the lower-bound claim would hold even for modes with different input spaces.","The near-tight degree-2 bounds suggest an anytime planning loop: solve the GMP for a lower bound, recover a mode sequence from its transition masses, and refine with the biconvex trajectory optimization until the gap is small; the paper reports these two steps separately rather than as a loop.","Because the relaxation directly yields transition probabilities $y_{ij}$, one could rank multiple likely mode sequences instead of only the maximum-likelihood one, making trajectory recovery more robust in problems with near-ties such as rover-2."],"forward_implications":["Hybrid optimal control can be lower-bounded by a convex semidefinite program without enumerating mode sequences, so a candidate trajectory's suboptimality gap can be certified.","The dual value functions give a feedback controller for each mode, so the solution is not only a cost but a policy that can be rolled out.","Temporal-logic specifications and multi-agent traffic scenarios with dozens of discrete modes become solvable in seconds, where fixed-horizon mixed-integer encodings are intractable.","The degree-zero relaxation is exactly a shortest-path LP, so the method connects classical graph search to continuous optimal control in one hierarchy.","Because the method inherits the computational burden of semidefinite programming, real-time use would require exploiting problem structure or symmetry."],"supporting_citations":[{"why":"supplies the weak occupation-measure formulation of optimal control, including the transport equation and its dual, on which every edge relaxation is built.","marker":"[17]"},{"why":"provides the shortest-path-in-convex-sets theorem whose vertex and edge structure the hybrid GMP instantiates.","marker":"[21]"},{"why":"gives the moment/sum-of-squares hierarchy that makes truncated measure relaxations converge and gives the lower-bound certificate.","marker":"[23]"},{"why":"the prior hybrid extension with identical input spaces, whose restrictive assumption the present formulation removes.","marker":"[19]"},{"why":"supplies the temporal-logic planning benchmarks whose automata define the discrete modes in the experiments.","marker":"[32]"},{"why":"provides the real-world traffic scenarios used for the roundabout and merge evaluations.","marker":"[35]"}],"fun_headline_variants":["Convex measure relaxation speeds up hybrid trajectory planning","Measure relaxation gives near-optimal hybrid trajectories in seconds","Tight lower bounds for hybrid control via convex measure relaxation","From NP-hard mixed-integer to convex SDP for hybrid control","Occupation-measure relaxation yields fast lower bounds for hybrid control"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the boundary measures entering and leaving a mode switch may be treated as living on the combined state-and-input space $X_i \\times U_i$, when the underlying transport equation only defines boundary mass on the state space $X_i$; if these measures are not marginalized to states before the transition constraints are imposed, the relaxed problem can exclude valid switching trajectories and the claimed lower bound is not guaranteed.","fun_headline_variants_meta":{"raw":{"variants":["Convex measure relaxation speeds up hybrid trajectory planning","Measure relaxation gives near-optimal hybrid trajectories in seconds","Tight lower bounds for hybrid control via convex measure relaxation","From NP-hard mixed-integer to convex SDP for hybrid control","Occupation-measure relaxation yields fast lower bounds for hybrid control"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000751,"raw_usage":{"total_tokens":3325,"prompt_tokens":909,"completion_tokens":2416,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":525,"completion_tokens_details":{"reasoning_tokens":2336}},"tokens_in":525,"tokens_out":2416,"duration_ms":18625,"temperature":1.0,"reasoning_tokens":2336,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T17:58:34.343563+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a two-mode system with equal dynamics but different input spaces across modes and an optimal trajectory that switches while using a nonzero input at the switching instant. Solve the degree-2 GMP (6); if, because the boundary measures in (6f) sit on $X_i \\times U_i$ rather than $X_i$, the relaxation cannot represent the switch, its optimum will lie above the true optimum, falsifying the universal lower-bound statement. A direct check is whether the dual transition constraint (7c), which uses $X_i \\cap X_j$, is violated for any feasible boundary measure.","supporting_citations":[{"cited_title":"Nonlinear Optimal Control via Occupation Measures and LMI-relaxations,","cited_arxiv_id":null,"evidence_quote":"supplies the weak occupation-measure formulation of optimal control, including the transport equation and its dual, on which every edge relaxation is built."},{"cited_title":"Shortest Paths in Graphs of Convex Sets,","cited_arxiv_id":null,"evidence_quote":"provides the shortest-path-in-convex-sets theorem whose vertex and edge structure the hybrid GMP instantiates."},{"cited_title":"Global Optimization with Polynomials and the Problem of Moments,","cited_arxiv_id":null,"evidence_quote":"gives the moment/sum-of-squares hierarchy that makes truncated measure relaxations converge and gives the lower-bound certificate."},{"cited_title":"Optimal Control of Polynomial Hybrid Systems via Convex Relaxations,","cited_arxiv_id":null,"evidence_quote":"the prior hybrid extension with identical input spaces, whose restrictive assumption the present formulation removes."},{"cited_title":"Multi-agent Motion Planning from Signal Temporal Logic Specifications,","cited_arxiv_id":null,"evidence_quote":"supplies the temporal-logic planning benchmarks whose automata define the discrete modes in the experiments."}],"review_version":2}