{"id":"b7e4de41-bda7-4537-bdd6-945f45548ebb","arxiv_id":"2502.06623","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"A deterministic optimization framework that maximizes how long multiple candidate targets remain reachable, shown equivalent to a cardinality minimization problem and solved via QCVX, MICP, and SCP methods.","lead":"This paper introduces a trajectory optimization framework that keeps a list of candidate target destinations reachable for as long as possible, deferring the final choice until more information arrives. It proves an equivalence between this reachability problem and a cardinality minimization problem, and uses the result to build convex, mixed-integer, and sequential-convex solvers demonstrated in quadrotor simulations.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorems 1–3 appear sound, but DDTO-MICP's exactness rests on an uncertified big-M bound (Assumption 2); without a computable M, constraint (18) can silently exclude the true optimum or degrade conditioning.","rationale":"Good-faith reading: the paper proves a clean equivalence between the constrained-reachability problems (4)/(5) and the cardinality minimizations (11)/(15). I checked Lemma 4, Lemma 6, and Theorems 2-3 for hidden assumptions about clumping/re-convergence, terminal overlap, and the 'replace by the i-trajectory' arguments, and found no contradiction. The QCVX and SCP methods are avowedly approximate or heuristic, so the main exact solver is DDTO-MICP in Section 5.1. Its correctness hinges on Assumption 2 and the implication constraint (18). No M is specified or derived in the text, and Table 1 gives no M for the numerical example. If the user's M is smaller than some true pairwise difference, the feasible set of (19) is a strict subset of that of (11), and the reported optimal deferred-decision trajectory need not be optimal for the claimed problem; if M is overly conservative, the MICP can suffer from numerical conditioning. The proposed test computes a certified M from the affine dynamics and control constraints, over a finite horizon where the reachable set is bounded, and checks sensitivity to that choice. A secondary gap is that the variable-horizon extension in (19) is not covered by Theorem 2, but since Table 1 sets all N_j = 20, the big-M issue is the more immediate threat to the reported result. This does not change the reader's verdict: the theoretical core seems correct, while the exact solution method needs this practical gap closed, so CONDITIONAL remains appropriate.","tokens_in":22373,"tokens_out":22264,"duration_ms":194232,"concrete_test":"Re-solve the DDTO-MICP example in Appendix B.1 with a certified upper bound M_cert computed from the affine dynamics and the control constraints, e.g., M_cert = 2 max_{z,w in R_N} ||z - w||, where R_N is a conservative over-approximation of the N-step reachable set from z0 under constraints (33). Compare the branch times, objective value, and zeta patterns against runs using M_cert/10 and 10*M_cert. If any run changes the optimal trajectory or the zeta pattern, the reported MICP results are sensitive to an unreported parameter; if all three runs coincide, the big-M choice is not load-bearing for this example.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central equivalence Theorems 2–3 are internally consistent, but the paper's only exact numerical method, DDTO-MICP, rests on Assumption 2 (Section 5.1): a finite scalar M bounding ||x^i_k - x^j_k|| for all k and all feasible trajectories. The implication constraint (18), ||x^i_k - x^j_k||_p <= zeta^k_j M, is exact only if M actually dominates every feasible pair. If M is chosen too small, the true optimum of the cardinality problem (11) is cut out by the MICP (19); if M is chosen too large, numerical conditioning degrades. The manuscript states Assumption 2 but provides no construction, formula, or certified bound for M, e.g., from the geometry of X, U, and the affine dynamics. The numerical section in Appendix B.1 also reports no value of M. Since (19) is presented as the MICP representation of the equivalent cardinality problem, the practical exactness of DDTO-MICP is not established by the paper as written.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces DDTO, a framework for generating feedforward trajectories that keep a set of candidate terminal targets reachable as long as possible, thereby allowing the decision among targets to be deferred. The authors propose constrained-reachability problems (4) and (5), prove their equivalence to cardinality-minimization problems (11) and (15), and show that optimal solutions have a monotone tree structure (Lemmas 4 and 6, Theorems 1-3). They then present three solution strategies: a quasiconvex bisection method (DDTO-QCVX), a mixed-integer conic program (DDTO-MICP), and a sequential convex programming method (DDTO-SCP), with demonstrations on two quadrotor motion-planning examples.","tokens_in":22581,"tokens_out":20215,"duration_ms":169072,"significance":"The main theoretical contribution---the equivalence between constrained reachability and cardinality minimization, together with the monotonicity/tree-structure characterization---is proven cleanly from the stated definitions; the identity (13) and the arguments for Lemmas 4 and 6 are internally consistent. The paper is honest about which methods are exact and which are heuristics, and the code is released. If the big-M issue is resolved, the DDTO-MICP method would provide a practically useful exact solver for the affine-convex case. The QCVX quasiconcavity argument is also sound. The contribution appears significant for the trajectory-optimization community.","major_comments":[{"comment":"The exactness of the MICP reformulation depends on the existence of a known finite M bounding all feasible pairwise state differences. The paper gives no method to compute or certify M from X, U, and the affine dynamics, and the experimental appendix does not report the value used. If M is chosen too small, the implication constraint (18) can render (19) infeasible even when the original problem (11) is feasible, or it can exclude the true optimum; if M is too large, numerical conditioning degrades. This is load-bearing for the claim that (19) is an exact MICP representation of (11). Please provide a constructive bound or explicitly position M as a per-instance validation requirement.","section":"Section 5.1, Assumption 2 and Eq. (18)-(19)"},{"comment":"The equivalence theorems are stated for a common horizon N. Equation (19) uses different horizon lengths N_j and truncates the objective at N_ij = min(N_i, N_j). As written, the statement that (19) is 'the MICP representation for (11)' holds only when all N_j coincide. Please either state the equivalence for equal horizons and present (19) as an extension, or extend the theorems to the unequal-horizon case.","section":"Section 5.1, Eq. (19) vs Section 4.2"}],"minor_comments":[{"comment":"The horizon update should subtract the previously computed branch time k_{lambda_{n-k+2}}, not k_{lambda_{n-k+1}}, which has not yet been assigned at that point in the loop.","section":"Algorithm 1, line 3"},{"comment":"Setting k_{lambda_1} to k_{lambda_2} conflicts with Definition 8, where k_j is the latest time target j is reachable; for the highest-priority target this should be N_{lambda_1}. The pseudocode appears to use k_{lambda_1} as the start of the final branch, so please clarify or rename the variable.","section":"Algorithm 1, line 11"},{"comment":"Please state explicitly whether (19) is equivalent to (11) only when N_j = N for all j, and how the unequal-horizon case relates to the theorems.","section":"Section 5.1"},{"comment":"Report the value of M used for DDTO-MICP and the criterion used to select it, since the exactness claim depends on this choice.","section":"Appendix B.1"},{"comment":"The line and legend markers for trunks and branches appear to be missing in the rendered figures; please restore them so that the captions and the text referring to the markers are interpretable.","section":"Figures 5-7"},{"comment":"The text 'CT-SC VX' should read 'CT-SCvX' to match the citation in Section 5.3.","section":"Algorithm 2, comment line 5"},{"comment":"The notation ||x||_diamond is an indicator function, not a norm; consider calling it an indicator to avoid confusion with the p-norm notation used later in Eq. (18) and Remark 7.","section":"Section 1.2, notation"}],"recommendation":"major_revision","confidential_remarks":"The core equivalence theorems are sound and the paper is a good fit for the journal. The main revision need is the big-M certification issue and the clarification of the unequal-horizon MICP; both are addressable within the manuscript's scope. The pseudocode index errors are typos but should be fixed in revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Read it. The real contribution is the equivalence theorems: the set-based reachability problems (4)/(5) and the cardinality minimization problems (11)/(15) are shown to be equivalent, and the proofs are self-contained and, as far as I can tell, correct. The monotonicity lemma is the key structural insight—optimal solutions have nested target sets and a tree-like trunk/branch form. The paper deserves credit for turning the QCVX heuristic from the authors' own prior work into a clean formal statement, and for shipping code.\n\nThe soft spot is exactly where the stress-test note points: DDTO-MICP's exactness rests on Assumption 2, an unknown bound M on pairwise state differences, and the paper gives no recipe, formula, or certification procedure for M. If M is too small, constraint (18) can exclude the true optimum; if too large, conditioning degrades. In many convex problems X is bounded and M could be computed from the constraint data, so the issue is fixable, but as written the exactness claim is not fully supported. The numerical appendix does not report M either.\n\nA second, related gap: the equivalence theorems are for (11)/(15) without the cumulative-cost constraint, but (19) and the algorithms add that constraint. The paper gestures at Remark 2 (augment the state) but never proves the equivalence goes through with cumulative constraints in the loop. The replacement argument in Lemma 6 can fail if the swapped-in prefix has a larger cumulative cost than the original branch. I think this is repairable, but it is a missing step.\n\nBeyond that, the numerical section is thin—no baselines, no solve times, no sensitivity to M or tolerance—but the public code and the examples do demonstrate the intended behavior. The heavy reliance on the authors' CT-SCvX framework is disclosed and is not by itself a problem.\n\nVerdict: send it to peer review. The theoretical core is solid and novel relative to [9], the methods are plausible, and the open issues are concrete and fixable. A good referee should push on big-M selection and the cumulative-constraint gap. I would cite the revised version.","headline":"A principled formalization of deferred-decision trajectory optimization with sound equivalence theorems; the main practical caveats are an uncertified big-M bound and an unclosed gap between the theory and the cost-constrained solvers—send it to review.","tokens_in":23144,"tokens_out":3659,"would_cite":true,"duration_ms":35623,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["93B03","90C25","90C11","49J15"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that keeping a menu of targets reachable is equivalent to minimizing how often trajectories diverge, and that optimal solutions branch off a shared trunk at branch times.","keywords":["deferred-decision trajectory optimization","constrained reachable sets","k-reach set","cardinality minimization","branch time","tree-structured trajectories","mixed-integer conic programming","sequential convex programming"],"falsifier":"Take a small affine system, say three scalar states with horizon N=5 and two or three singleton targets, enumerate all feasible trajectories, and solve the reachability problem and the cardinality problem exactly. If the optimal values differ, or if a minimizer of the cardinality problem yields active sets that are not monotonically shrinking, the claimed equivalence fails. For the MICP method specifically, setting M below the true maximal pairwise state difference should make the reformulation exclude the true optimum, which would test Assumption 2's role.","tokens_in":1548,"feed_emoji":"🎯","tokens_out":2006,"duration_ms":72690,"temperature":0.7,"pith_summary":"DDTO asks how a vehicle should move when it knows several possible goals but will only learn which one is viable later. The paper formalizes this as constrained reachability: maximize, in a cumulative sense, how many candidate targets remain reachable from the trajectory at each time step. It proves that these set-valued formulations are equivalent to minimizing the number of time steps at which trajectories to different targets diverge, a cardinality minimization over pairwise state differences. That equivalence reveals that optimal deferred-decision trajectories form a tree: one shared trunk, then branch trajectories peeling off at branch times. The paper then turns the structure into three algorithms, quasiconvex optimization, mixed-integer conic programming, and sequential convex programming, and demonstrates them on quadrotor motion planning examples.","feed_headline":"Delaying the target choice reduces to counting splits","feed_subtitle":"Trajectories that keep every landing site reachable branch off a shared trunk at provably optimal times.","key_machinery":"The carrying object is the k-reach set, the set of all states that can be reached from the start in k-1 steps and still reach a given target in the remaining steps. Its multi-target intersection tells whether every target in a chosen collection is still reachable at time k, and the branch time is the last such k. The equivalence argument uses the indicator norm, which is 0 when two states coincide and 1 otherwise, to convert the reachability condition into the counting objective of summed pairwise divergences. Lemma 5 makes the bridge exact: for n trajectories, the summed cardinality of the coincident sets plus the number of pairwise divergences equals nN at every time step.","core_discovery":"The central claim is Theorem 2 and Theorem 3: the constrained-reachability problems (4) and (5), whose decision variables include sets of target indices, are equivalent to the cardinality minimization problems (11) and (15), whose variables are only the trajectories themselves. Concretely, maximizing the summed size of the active target sets equals minimizing the summed number of nonzero pairwise state differences; a minimizer of the cardinality problem delivers active sets through (12) that solve the reachability problem, and conversely any reachability solution yields trajectories via Corollary 1. A consequence of the proof is that along an optimal solution the active sets shrink monotonically, so the trajectories coincide on a common trunk and split at branch points. The paper does not claim to solve the cardinality problems in general; it uses the equivalence to justify three specialized solution methods for convex and nonconvex settings, with numerical demonstrations on quadrotor planning.","pith_inferences":["The paper leaves implicit that the same equivalence can be used to measure the price of deferral: with the cumulative-cost constraint active, the gap between the unconstrained and constrained branch time quantifies how much fuel buys extra information gathering.","Because the optimal solution is a tree, the trunk segments computed for one priority order can be reused when a target is added or removed, so online re-planning might only need to resolve the local branch.","A testable extension is to treat the target set as data: every time perception eliminates a candidate, re-solve the cardinality problem from the current branch point with the remaining targets; the monotonicity lemma suggests the old trunk remains valid until the next branch time.","In a stochastic setting, one could average the same divergence-counting objective over an ensemble of target-viability hypotheses, producing a risk-sensitive deferred-decision planner; the paper does not pursue this."],"forward_implications":["With the theorem true, any algorithm producing a tree-structured solution is certifiably optimal for the deferred-decision objective, not just a heuristic.","DDTO-QCVX recursively computes branch times by quasiconcave maximization, so the trunk segments are found by a sequence of convex feasibility checks via bisection.","DDTO-MICP solves an exact mixed-integer convex reformulation when dynamics are affine and constraints are convex; its convex relaxation gives an approximate solution.","DDTO-SCP extends the tree structure to continuous-time nonlinear systems with nonconvex constraints by maximizing trunk duration with sequential convex programming.","In closed loop, the branch times computed online can be recomputed as perception updates arrive, lengthening the information-gathering phase before a target is selected."],"supporting_citations":[{"why":"Supplies the constrained forward and backward reachable set definitions on which the k-reach sets and the reachability lemmas are built.","marker":"[29]"},{"why":"Provides the sequential convex programming machinery with time-dilation and isoperimetric constraint reformulation used by DDTO-SCP.","marker":"[8]"},{"why":"Introduced the quasiconvex branch-time heuristic that DDTO-QCVX generalizes and for which this paper proves optimality.","marker":"[9]"},{"why":"Gives the bisection method for quasiconvex optimization used to solve the branch-time problem in DDTO-QCVX.","marker":"[30]"},{"why":"Documents the intractability of reachable sets for high-dimensional nonlinear systems, motivating the reformulation.","marker":"[5]"}],"fun_headline_variants":["Delaying target choice reduces to counting splits","Counting splits proves when to defer targets","Trajectory branch points from cardinality count","Deferred decisions shrink reachable sets to a trunk","Optimize trajectories by counting split choices"],"cache_read_input_tokens":25344,"weakest_assumption_plain":"Assumption 2: a known finite scalar M bounds the norm of the state difference between any two feasible trajectories at every time; the MICP reformulation relies on this bound, yet the paper gives no procedure to compute or certify it.","fun_headline_variants_meta":{"raw":{"variants":["Delaying target choice reduces to counting splits","Counting splits proves when to defer targets","Trajectory branch points from cardinality count","Deferred decisions shrink reachable sets to a trunk","Optimize trajectories by counting split choices"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.0005,"raw_usage":{"total_tokens":2399,"prompt_tokens":847,"completion_tokens":1552,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":463,"completion_tokens_details":{"reasoning_tokens":1485}},"tokens_in":463,"tokens_out":1552,"duration_ms":11005,"temperature":1.0,"reasoning_tokens":1485,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-08T14:54:04.239114+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a small affine system, say three scalar states with horizon N=5 and two or three singleton targets, enumerate all feasible trajectories, and solve the reachability problem and the cardinality problem exactly. If the optimal values differ, or if a minimizer of the cardinality problem yields active sets that are not monotonically shrinking, the claimed equivalence fails. For the MICP method specifically, setting M below the true maximal pairwise state difference should make the reformulation exclude the true optimum, which would test Assumption 2's role.","supporting_citations":[{"cited_title":"Predictive Control for Linear and Hy- brid Systems","cited_arxiv_id":null,"evidence_quote":"Supplies the constrained forward and backward reachable set definitions on which the k-reach sets and the reachability lemmas are built."},{"cited_title":"Successive Convexification for Trajectory Optimization with Continuous-Time Constraint Satisfaction","cited_arxiv_id":"2404.16826","evidence_quote":"Provides the sequential convex programming machinery with time-dilation and isoperimetric constraint reformulation used by DDTO-SCP."},{"cited_title":"Deferring Decision in Multi- target Trajectory Optimization","cited_arxiv_id":null,"evidence_quote":"Introduced the quasiconvex branch-time heuristic that DDTO-QCVX generalizes and for which this paper proves optimality."},{"cited_title":"Disciplined quasiconvex programming","cited_arxiv_id":null,"evidence_quote":"Gives the bisection method for quasiconvex optimization used to solve the branch-time problem in DDTO-QCVX."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Documents the intractability of reachable sets for high-dimensional nonlinear systems, motivating the reformulation."}],"review_version":1}