{"id":"da3d9552-4722-4294-b362-f46bee513683","arxiv_id":"2504.19330","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"A discrete-time control barrier function and a polynomial control policy are synthesized jointly for polynomial systems via an iterative sum-of-squares program that bypasses the bilinear terms blocking earlier approaches.","lead":"This paper presents an iterative sum-of-squares optimization method that constructs safety certificates and polynomial controllers together for discrete-time polynomial systems with input limits. A generalist reader might care because this automates a step that previously required hand-picked candidate functions in safety-critical control.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Hidden vanishing condition in Propositions 2–3 can make Step 1 infeasible even for valid initial DTCBFs","rationale":"The paper's quadratic DTCBF core is internally consistent when Step 1 is feasible, and the reported numerical results are plausible but not independently verifiable because no code or data are shipped. The reader's weakest assumption was the unguaranteed feasibility of the first Step 1 problem; the present review sharpens that concern by identifying a specific, previously unstated algebraic obstruction: the simultaneous use of Propositions 2 and 3 forces policy components to vanish on the zero sets of the cross coefficients a_{i,j}. This makes the practical applicability of the method narrower than the text suggests and weakens the claim that the reformulation introduces no conservatism. However, it does not demonstrate that the algorithm produces invalid DTCBFs when it does terminate, nor does it refute the numerical examples. The higher-degree extension in Section 6.1 also remains a sketch, but the vanishing-condition issue already justifies a conditional verdict. No change to the reader's CONDITIONAL recommendation is needed.","tokens_in":17411,"tokens_out":26089,"duration_ms":242022,"concrete_test":"Build the 2D system x+ = g(x)u with g1(x) = [x1; 0], g2(x) = [0; 1], U = [-1,1]^2, and h^(0) = -x1^2 - x2^2 + x1*x2 + 0.2. For this h^(0), the cross coefficient is a_{1,2}^(0)(x) = 0.5*x1, which has a zero at x1 = 0 inside C^(0) where h^(0) > 0. Solve (35) with this h^(0) while increasing the degrees of the multiplier and auxiliary polynomials. If (35) is infeasible for all degrees, the hidden vanishing condition is confirmed; if it is feasible, inspect the returned policy and verify whether π1 and π2 vanish identically on x1 = 0, which would still confirm the restriction.","verdict_should_be":"UNCHANGED","load_bearing_attack":"At any x in C^(k-1) with h^(k-1)(x) > 0 and a_{i,j}(x) = 0, the SOS constraints of Propositions 2 and 3 are both active. From (24)-(27), one obtains 2*eπ_{i,j}(x) >= π_i(x)^2 + π_j(x)^2 plus nonnegative multiplier terms. From (28)-(31), one obtains 2*eπ_{i,j}(x) <= -π_i(x)^2 - π_j(x)^2 minus nonnegative multiplier terms. Hence π_i(x) = π_j(x) = 0 and the relevant multipliers vanish at x. Thus feasibility of (35) implicitly forces every pair of policy components π_i, π_j to vanish on the set {x in C^(k-1) : a_{i,j}(x) = 0}. The same conflict appears for diagonal terms via Proposition 1 at zeros of a_{i,i}(x). This is an unstated algebraic restriction. It also contradicts the claim that 'condition (19) does not introduce conservatism since eπ_{i,j}(x) can be equal to π_i(x)π_j(x)': at a zero of a_{i,j}, even the exact choice eπ_{i,j} = π_i π_j violates the conjunction of Propositions 2 and 3 unless both π_i and π_j vanish. For nonlinear systems with state-dependent g, a_{i,j} generically changes sign inside C, so Step 1 can be infeasible even when a valid DTCBF-triple exists. This is a concrete mechanism behind the admitted non-guarantee of (35) in Remark 6, and it directly limits the central synthesis claim.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper addresses the synthesis of discrete-time control barrier functions (DTCBFs) and associated polynomial control policies for control-affine polynomial systems with polyhedral input constraints and semi-algebraic safe sets. The authors propose an alternating-descent SOS scheme for quadratic DTCBFs: after initializing a valid quadratic DTCBF, Step 1 fixes the barrier candidate and searches for a polynomial policy and γ via SOS constraints, introducing auxiliary polynomials eπ_{i,j} to replace bilinear products π_iπ_j, while Step 2 fixes the policy and enlarges the zero-superlevel set. Theorem 2 assembles sufficient SOS conditions from Propositions 1–3; Theorem 3 claims the iteration is lossless once the first Step 1 is feasible. Two extensions to higher-degree polynomial barrier functions are sketched, and numerical results are given for a linearized cart-pole system and a two-dimensional nonlinear system.","tokens_in":17778,"tokens_out":17514,"duration_ms":165932,"significance":"If correct, the proposed method would be a valuable contribution to DTCBF synthesis: it offers a computationally tractable SOS formulation that handles the bilinear term h(f(x)+g(x)π(x)) without restricting to affine barrier functions or set-valued policies, provides complete proofs for the quadratic case, and validates the approach against an independent maximal invariant set computation (MPT3) in the linear example. The losslessness argument in Theorem 3 is a useful feature, conditional on initial feasibility. However, the higher-degree extension is only sketched, and the hidden algebraic restrictions in Propositions 2–3 substantially weaken the claim that the relaxation is non-conservative and may cause Step 1 infeasibility in cases not exercised by the numerical examples.","major_comments":[{"comment":"Propositions 2 and 3 together impose an unstated vanishing condition on the policy components. At any x in C^{(k-1)} with h^{(k-1)}(x)>0 and a^{(k-1)}_{i,j}(x)=0, constraints (24)–(27) imply 2 eπ_{i,j}(x) ≥ π_i(x)^2 + π_j(x)^2 plus nonnegative multiplier terms, while constraints (28)–(31) imply 2 eπ_{i,j}(x) ≤ -π_i(x)^2 - π_j(x)^2 minus nonnegative multiplier terms. Hence every feasible solution must satisfy π_i(x)=π_j(x)=0 at such x. Consequently, whenever a coefficient a_{i,j} changes sign on C^{(k-1)}, Step 1 (35) forces each pair of policy components to vanish on the algebraic set {x in C^{(k-1)} : a_{i,j}(x)=0}; the same phenomenon appears for the diagonal terms via Proposition 1 at zeros of a_{i,i}. This is a genuine algebraic restriction that is not stated in Theorem 2 or Remark 6. It also contradicts the sentence after (19) that condition (19) 'does not introduce conservatism since eπ_{i,j}(x) can be equal to π_i(x)π_j(x)': at a zero of a_{i,j}, even the exact choice eπ_{i,j}=π_iπ_j cannot satisfy the conjunction of (24)–(27) and (28)–(31) unless π_i and π_j vanish (or at least until (π_i−π_j)^2=0 and all multiplier terms vanish). Since for nonlinear systems with state-dependent g the coefficients a_{i,j}(x) generically change sign inside a nontrivial controlled invariant set, this hidden condition can make (35) infeasible even when a valid DTCBF-triple exists, providing a concrete mechanism behind the admitted non-guarantee in Remark 6. Please characterize this condition explicitly and assess its impact on the central synthesis claim.","section":"§5.1, Eqs. (24)–(31) and Eq. (19)"},{"comment":"The extension to higher-degree polynomial DTCBFs is not proved. The text treats only the monomial µ_i^3 and states that 'all other bilinear terms can be handled in a similar manner,' but no general recursion is specified and no proof is given that the recursively introduced auxiliary polynomials eµ_{i,i}, eµ_{i,i,i}, ... preserve linearity of the SOS programs and maintain the required sign conditions for mixed monomials such as µ_i^2 µ_j. Since the abstract and Problem 1 explicitly claim higher-degree DTCBF synthesis, and Theorem 3's guarantee depends on the Step 1 formulation being correct at every degree, this is a load-bearing gap. The numerical example in Section 7.1 uses a degree-four barrier function, but the manuscript does not state whether Section 6.1 or Section 6.2 was used, nor how the quartic terms were encoded, so the demonstration does not fill the gap. Please provide a complete treatment for the general monomial case or clearly restrict the main claims to quadratic DTCBFs.","section":"§6.1"},{"comment":"The algorithm cannot start without a valid initial quadratic DTCBF h^{(0)}, and Remark 6 concedes that feasibility of (35) at k=1 is not guaranteed. The paper does not give a systematic procedure for constructing h^{(0)} or for certifying that Step 1 will be feasible. As a result, for a general polynomial system the proposed method is an iterative enlargement procedure from a user-supplied feasible certificate rather than a synthesis method in the sense of Problem 1. This limitation should be stated clearly at the outset, together with a concrete initialization strategy (for example, small ellipsoidal estimates around a stable equilibrium) and a discussion of when such a strategy can be certified.","section":"§5.2, Step 0 and Remark 6"}],"minor_comments":[{"comment":"The word 'admissibe' is a typo for 'admissible'; the manuscript should be proofread for similar mechanical errors.","section":"§5.2, after Eq. (35)"},{"comment":"The heading reads 'Apendix B' instead of 'Appendix B'.","section":"Appendix B heading"},{"comment":"In the displayed feasibility problem (37), it is not immediately clear which variables are decision variables and which are fixed from the previous Step 1 solution; Remark 4 explains this verbally, but the display should list the fixed variables explicitly to avoid ambiguity.","section":"Remark 4 and Eq. (37)"},{"comment":"The termination condition says the algorithm stops when (37) is infeasible 'due to violation of (37e)', but the behavior for infeasibility caused by other constraints is not specified; please clarify whether such infeasibility is treated as failure or as another stopping criterion.","section":"Step 2 and termination"}],"recommendation":"major_revision","confidential_remarks":"The core quadratic formulation (Propositions 1–3 and Theorem 2) is coherent, but the relaxation is substantially more conservative than claimed because of the hidden vanishing conditions at zeros of a_{i,j}, and the higher-degree extension is incomplete. The numerical examples do not exercise the problematic sign-changing coefficient case, so adding such a case would be particularly informative. I would not reject outright, but the authors need to either fix the SOS constraints, prove the higher-degree recursion, or substantially narrow the claims."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First thing to know: the quadratic core is a real step forward for SOS-based DTCBF synthesis, but the central claim is weaker than it looks. The stress-test note checks out. At any x in C^(k-1) with a_{i,j}(x) = 0, Proposition 2 forces 2 eπ_{i,j}(x) >= π_i(x)^2 + π_j(x)^2 plus nonnegative terms, while Proposition 3 forces 2 eπ_{i,j}(x) <= -π_i(x)^2 - π_j(x)^2 minus nonnegative terms. Together they imply π_i(x) = π_j(x) = 0 and eπ_{i,j}(x) = 0. The diagonal case does the same through Proposition 1. So feasibility of (35) carries an unstated algebraic restriction: every policy component pair must vanish on the zero set of the corresponding a_{i,j} inside C. For nonlinear systems with state-dependent g, these zero sets are generically nontrivial curves, which gives a concrete mechanism behind the non-guarantee admitted in Remark 6. The claim in Section 5.1 that (19) introduces no conservatism because eπ can equal π_i π_j is not accurate at those zeros: the exact choice is excluded by the conjunction of Propositions 2 and 3 unless both policy components are zero.\n\nWhat is genuinely new and good: replacing each π_i π_j with an auxiliary polynomial eπ and splitting the constraints by the sign of a_{i,j} does make the DTCBF condition affine in decision variables, and the proofs of Propositions 1-3 and Theorem 2 are coherent. The MPT3 comparison for the cart-pole is a fair independent benchmark and gives some evidence that the iteration actually grows the invariant set in practice.\n\nSoft spots, in proportion: the hidden vanishing condition is load-bearing and needs to be stated and discussed, not left implicit. Section 6.1 only proves the μ_i^3 case and asserts the rest by analogy, so the higher-degree extension is a sketch, not a proof. No code or data are shipped, which makes the numerical claims hard to reproduce. And initialization still requires a valid quadratic DTCBF with no systematic construction. None of this makes the quadratic result false, but it means the paper as written supports a narrower statement: the method works when Step 1 is feasible and the coefficients avoid the vanishing obstruction.\n\nThis paper deserves a serious referee, not a desk reject. It is for people working on SOS safety filters and invariant sets for discrete-time polynomial systems. I would send it out with a clear request to address the vanishing condition, give full proofs for the higher-degree claims or explicitly mark them as conjectural, and release code.","headline":"A genuinely new quadratic DTCBF synthesis scheme, but the central claim is narrower than stated because Step 1 silently forces policy components to vanish at zeros of the cross coefficients, and the higher-degree extension is only sketched.","tokens_in":733,"tokens_out":892,"would_cite":true,"duration_ms":59157,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["93C55","93D30","90C22"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims an alternating-descent SOS algorithm can synthesize quadratic and higher-degree DTCBFs with polynomial control policies for discrete-time control-affine polynomial systems, and that the procedure is lossless once it starts.","keywords":["discrete-time control barrier functions","sum-of-squares programming","control-affine polynomial systems","controlled invariance","safety-critical control","alternating descent","input constraints","semialgebraic safe sets"],"falsifier":"Run the first Step-1 feasibility problem (35) on the scalar control-affine system x+ = x + u with U = [-1,1], safe set S = {x : $x^{2}$ <= 1}, and initial barrier h^(0)(x) = 1 - $x^{2}$, where the known triple (h^(0), gamma(r)=r, pi(x)=0) satisfies the DTCBF inequality and input admissibility. If (35) is infeasible for this data, the auxiliary conditions are strictly conservative; conversely, a successful run that later returns a triple violating the barrier inequality or input admissibility on a sampled grid would refute the losslessness claim.","tokens_in":17211,"feed_emoji":"🛡️","tokens_out":10131,"duration_ms":95143,"temperature":0.7,"pith_summary":"Discrete-time control barrier functions are a standard way to make safety guarantees, but no computationally systematic way to construct them for polynomial systems had been available, and existing candidates often ignore input limits. This paper proposes an alternating-descent method based on sum-of-squares programming that, starting from a conservative valid barrier, alternately updates the control policy and then enlarges the barrier's zero-superlevel set. The central difficulty is bilinear products of barrier and policy coefficients in the next-state evaluation; the paper dissolves those products by introducing auxiliary polynomials and SOS constraints that certify the required inequality without bilinear decision variables. It proves that once the first policy update succeeds, every later iterate is a valid DTCBF-triple and the certified safe sets grow strictly until no further enlargement is possible. The same machinery extends to higher-degree barriers, and the paper demonstrates the procedure on a cart-pole system and a two-input nonlinear example.","feed_headline":"New SOS algorithm builds discrete-time safety barriers automatically","feed_subtitle":"A convex SOS routine certifies quadratic and higher-degree barriers with polynomial control policies.","key_machinery":"The engine of the method is a replacement rule for the problematic term h^(k-1)(f(x)+g(x)pi(x)). Because h is quadratic, once h^(k-1) is fixed this term expands as a sum of coefficient polynomials a_{i,j}(x) times pi_i(x)pi_j(x). The paper replaces each product pi_i(x)pi_j(x) with a fresh polynomial e_pi_{i,j}(x), then imposes SOS constraints, built from 2 by 2 positive-semidefinite matrix inequalities and the generalized S-procedure, that guarantee a_{i,j}(x)(pi_i(x)pi_j(x) - e_pi_{i,j}(x)) >= 0 on the current zero-superlevel set C^(k-1). This makes the true next-step barrier value no smaller than the tractable substitute, so an SOS certificate for the substitute implies the DTCBF inequality for the real system. All decision variables enter linearly, so each substep is a semidefinite program.","core_discovery":"On its own terms, the paper's central claim is Theorem 3: the proposed three-step algorithm is lossless. Starting from an initial quadratic DTCBF h^(0), allowed to be very conservative, Step 1 fixes h^(k-1) and searches for gamma^(k) and a polynomial policy pi^(k), together with auxiliary multipliers that remove bilinearities. Step 2 fixes the policy and gamma, finds an SOS multiplier, and solves a feasibility problem for a new h^(k) with C^(k-1) strictly inside C^(k) and C^(k) inside the safe set S. Theorem 3 states that if Step 1 succeeds at the first iteration, then at every later iteration before termination the triple (h^(l), gamma^(l), pi^(l)) is a genuine DTCBF-triple satisfying the barrier inequality and input admissibility on C^(l), and the only possible halt is condition (37e), which encodes that the zero-superlevel set can no longer be enlarged. The paper further claims that higher-degree polynomial DTCBFs can be synthesized in two ways: applying the product-replacement propositions repeatedly on a shifted nonnegative input, or first building a quadratic barrier and then running only the barrier-update step with the policy fixed.","pith_inferences":["The admitted first-step feasibility gap points to the real design bottleneck: the method needs a valid starting barrier, and a natural extension is a preliminary SOS routine that searches for h^(0) as a small ellipsoidal Lyapunov-like set, or adaptively scales one from a stabilizing policy.","Because the replacement technique only uses the quadratic structure of h and the polynomial structure of f and g, the same mechanism should transfer to discrete-time control Lyapunov functions and to non-polyhedral controlled invariant sets for polynomial systems, a problem the paper itself calls open.","A sharper test of the method's conservatism would compare, on the cart-pole example, the terminal zero-superlevel set against the true maximal controlled invariant subset of the safe set; the paper only compares with a maximal polyhedral invariant set from a linear analysis.","The fixed-policy higher-degree route suggests a cheap two-stage design: first enlarge with a quadratic barrier under tight input limits, then re-fit a higher-degree barrier for the same fixed policy; if the input set is tight this is likely to enlarge the safe set less aggressively than the full repeated-proposition route."],"forward_implications":["Once the algorithm starts, it never needs to re-check safety: every intermediate pair (h^(l), pi^(l)) is certified, so the method can be stopped early and still yield a valid safety guarantee.","The certified safe region grows monotonically from the initial conservative set, so the user can trade computation time against conservatism by choosing when to stop.","Because each subproblem is an SOS feasibility program with linear decision variables, the overall method is a sequence of convex semidefinite programs and can be implemented with standard SOS toolboxes.","Higher-degree barriers can be produced from a quadratic start without solving the hard bilinear problem again, by keeping the control policy fixed.","A successful synthesis yields a DTCBF-triple that guarantees controlled invariance of its zero-superlevel set and safety for every initial state inside that set, so the barrier can serve directly as a safety filter or as a terminal ingredient in model predictive control."],"supporting_citations":[{"why":"Defines the DTCBF condition and proves that a DTCBF's zero-superlevel set is controlled invariant, giving the paper its safety framework.","marker":"[1]"},{"why":"Supplies the DTCBF definition variant and the gamma parametrization used throughout the synthesis problem.","marker":"[30]"},{"why":"Provides the generalized S-procedure SOS formulation and the affine-DTCBF alternating-descent baseline that the paper extends to quadratic and higher-degree barriers.","marker":"[23]"},{"why":"Establishes the standard SOS alternating-descent template for continuous-time CBFs whose bilinearity the paper must overcome in discrete time.","marker":"[2]"},{"why":"Supports the generalized S-procedure lemma used to convert nonnegativity on semi-algebraic sets into SOS constraints.","marker":"[19]"},{"why":"Is the numerical toolbox used to solve the SOS feasibility problems in the paper's case studies.","marker":"[17]"},{"why":"Is the prior conference version containing the quadratic DTCBF algorithm without proofs, extended here with full proofs and higher-degree methods.","marker":"[21]"},{"why":"Is the existing nonlinear polynomial DTCBF synthesis method with set-valued policies that the paper's explicit polynomial-policy framework improves on.","marker":"[13]"},{"why":"Provides the maximal polyhedral controlled invariant set used as a benchmark in the cart-pole numerical study.","marker":"[12]"}],"fun_headline_variants":["Lossless SOS descent builds discrete-time control barriers","Alternating SOS crafts polynomial safety barriers automatically","Higher-degree DTCBFs via lifted SOS steps","Input-constrained safety sets from SOS optimization","Exact barrier synthesis using sum-of-squares alternation"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole procedure presupposes that the very first search for a control policy succeeds for the chosen initial barrier function; the paper states this success is not guaranteed, so the algorithm can fail to start even when a valid barrier exists.","fun_headline_variants_meta":{"raw":{"variants":["Lossless SOS descent builds discrete-time control barriers","Alternating SOS crafts polynomial safety barriers automatically","Higher-degree DTCBFs via lifted SOS steps","Input-constrained safety sets from SOS optimization","Exact barrier synthesis using sum-of-squares alternation"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000252,"raw_usage":{"total_tokens":1545,"prompt_tokens":917,"completion_tokens":628,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":533,"completion_tokens_details":{"reasoning_tokens":556}},"tokens_in":533,"tokens_out":628,"duration_ms":6624,"temperature":1.0,"reasoning_tokens":556,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T05:55:10.129424+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the first Step-1 feasibility problem (35) on the scalar control-affine system x+ = x + u with U = [-1,1], safe set S = {x : $x^{2}$ <= 1}, and initial barrier h^(0)(x) = 1 - $x^{2}$, where the known triple (h^(0), gamma(r)=r, pi(x)=0) satisfies the DTCBF inequality and input admissibility. If (35) is infeasible for this data, the auxiliary conditions are strictly conservative; conversely, a successful run that later returns a triple violating the barrier inequality or input admissibility on a sampled grid would refute the losslessness claim.","supporting_citations":[{"cited_title":"Agrawal and K","cited_arxiv_id":null,"evidence_quote":"Defines the DTCBF condition and proves that a DTCBF's zero-superlevel set is controlled invariant, giving the paper its safety framework."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the DTCBF definition variant and the gamma parametrization used throughout the synthesis problem."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the generalized S-procedure SOS formulation and the affine-DTCBF alternating-descent baseline that the paper extends to quadratic and higher-degree barriers."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes the standard SOS alternating-descent template for continuous-time CBFs whose bilinearity the paper must overcome in discrete time."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supports the generalized S-procedure lemma used to convert nonnegativity on semi-algebraic sets into SOS constraints."},{"cited_title":"Shakhesi, W.P.M.H","cited_arxiv_id":null,"evidence_quote":"Is the prior conference version containing the quadratic DTCBF algorithm without proofs, extended here with full proofs and higher-degree methods."},{"cited_title":"Jagtap, S","cited_arxiv_id":null,"evidence_quote":"Is the existing nonlinear polynomial DTCBF synthesis method with set-valued policies that the paper's explicit polynomial-policy framework improves on."},{"cited_title":"Herceg, M","cited_arxiv_id":null,"evidence_quote":"Provides the maximal polyhedral controlled invariant set used as a benchmark in the cart-pole numerical study."}],"review_version":1}