{"id":"811d6833-afe7-4a44-bf5e-4345671afe4b","arxiv_id":"2501.01559","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"K-ARC solves multi-robot kinodynamic planning by planning cheap paths, splitting them into segments, optimizing each segment, and resolving only local conflicts, scaling to 32 simulated robots with faster runtimes than two reimplemented baselines.","lead":"This paper presents K-ARC, a planning algorithm that lets teams of up to 32 robots with realistic movement limits find collision-free paths faster than two existing methods. The speed comes from splitting each robot's route into segments, optimizing each segment individually, and only re-planning around the places where robots actually collide.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No continuous-time collision guarantee: constraints (5)-(6) and conflict checks are only at discrete timesteps, so the reported speedups may be for trajectories that interpenetrate between samples.","rationale":"The reader's weakest assumption is exactly this gap, so no new objection changes the verdict. I considered other concerns: no released code, author reimplemented baselines, and hand-chosen parameters. Those affect reproducibility and fairness but do not, by themselves, invalidate the algorithm's outputs. The discrete-time safety gap does: if a continuously interpolated trajectory collides, then K-ARC has not solved the planning problem, so runtime comparisons to K-CBS and CB-MPC are comparisons to methods that at least attempt feasible solutions. The proposed test is decisive: successful validation across many trials would substantiate the empirical claim, while any violation would make the feasibility claim false. Because the paper provides no continuous-time argument and the test is not in the manuscript, the correct status remains conditional: accept only if such validation is added and passes. The verdict is unchanged from the reader's CONDITIONAL.","tokens_in":10613,"tokens_out":6642,"duration_ms":71026,"concrete_test":"Instrument a successful K-ARC run (e.g., open-cross 32-robot) and post-check the exact returned trajectories with a continuous-time collision checker: for each pair of robots and each interval [t_k, t_{k+1}], densely sub-sample the interpolated state (e.g., 100 points) and compute pairwise distances; additionally perform swept-volume tests between consecutive states against obstacles and against other robots. If any violation of d_min or obstacle clearance is found, K-ARC is returning infeasible trajectories and the speedup claims do not transfer to valid plans. If all trials across scenarios pass, the concern is empirically resolved; a proof or formal bound would still be needed for the method to be generally safe.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is that K-ARC outputs valid, collision-free multi-robot kinodynamic trajectories. That requires the continuous-time curves to respect obstacle and inter-robot separation. The paper only enforces this at sampled states: Eq. (5) and (6) constrain c_i,k and pairs (x_i,k, x_j,k) at each timestep k, Algorithm 1 line 20 defines conflicts as tuples of states at a timestep, and the subproblem solvers in Section IV-C impose separation on 'each state' of the paths. No swept-volume check, interpolation bound, or continuous-time validation is described. Because the trajectory optimizer in Section IV-B minimizes total time and can use a coarse discretization to reduce cost, two robots can pass through each other between consecutive nodes while every discrete constraint is satisfied. If that occurs, the returned 'solutions' are infeasible and the speedup comparison is against a non-solution. This is load-bearing because it attacks the correctness of every reported success, not just computational efficiency.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper presents K-ARC, a multi-robot kinodynamic planning algorithm that extends the authors' earlier ARC framework. K-ARC first computes individual kinematic paths, segments them into m pieces, and processes the segments sequentially. For each segment it uses a single-robot trajectory optimizer to obtain kinodynamically feasible trajectory segments, checks those segments for inter-robot conflicts at discrete timesteps, and resolves conflicts through a subproblem solver hierarchy that combines prioritized trajectory optimization with decoupled and composite kinodynamic RRT variants. The experiments compare K-ARC against reimplementations of K-CBS and CB-MPC in four scenarios (open cross, cluttered cross, quadrotor cross, quadrotor inlet) and report substantial runtime speedups, including scaling to 32 robots in the open cross scenario. The central claim is that the segment-wise interleaving of optimization and sampling yields an order-of-magnitude speedup while preserving feasibility.","tokens_in":10812,"tokens_out":7455,"duration_ms":73354,"significance":"The proposed segmentation idea is a genuinely useful way to combine optimization and sampling in multi-robot kinodynamic planning, and the empirical scaling to 32 robots in open environments is noteworthy. The paper also gives a clear account of why a direct ARC extension fails for kinodynamic problems, namely the exact-goal discontinuity problem, and the sequential segment construction is a sensible resolution. A strength of the experimental design is that all planners are implemented in a common open-source library, which facilitates head-to-head comparison if the code is released. However, the significance of the reported speedups depends on two conditions that are not currently established: the output trajectories must be collision-free in continuous time, and the baselines must be faithful to the published methods they represent. If these conditions are met, the work would be a solid contribution to multi-robot kinodynamic planning.","major_comments":[{"comment":"The formal problem definition in §II-C only imposes obstacle avoidance and inter-robot separation at discrete timesteps (constraints (5)-(6)), and the same discrete notion is used throughout: Algorithm 1 line 20 defines a conflict as a tuple (xi,k, xj,k), and the subproblem solvers in §IV-C enforce separation on individual states. No swept-volume check, interpolation bound, or continuous-time validation is described anywhere in the paper. Because the trajectory optimizer in §IV-B minimizes total time and can choose a coarse time step, two robots could pass through each other, or a robot could clip an obstacle, between consecutive samples while every discrete constraint is satisfied. This is load-bearing for the correctness of every reported success: the output is described as a set of 'valid, kinodynamically feasible paths' in Algorithm 1, so the reported speedups may be for trajectories that are not actually collision-free. The authors should add continuous-time collision checking or a formal bound on the interpolation error, and rerun or reanalyze the experiments with that check in place.","section":"§II-C, §IV-C, Algorithm 1"},{"comment":"The contribution statement claims speedups 'compared to baseline methods from recent literature,' but the baselines are reimplementations. Section V-A states that the implementations of K-CBS and CB-MPC follow the same high-level CBS framework and 'does not include the further improvements on the framework.' Without knowing which improvements from [6] and [5] are omitted, it is impossible to determine whether the comparison is against the published algorithms or against weakened versions of them. This directly affects the validity of the headline runtime comparison; the authors should either use the original implementations, or report precisely which components were omitted and justify why those omissions cannot materially change the comparison.","section":"§V-A"},{"comment":"Several experimental parameters and solver details that are essential for reproducing the claimed speedups are not reported. The number of path segments m (Algorithm 1 line 6), the discretization timestep ∆t, the local goal tolerance, and the cost weight β1 are never given in Section V, and the three subproblem solvers in Section IV-C are described only by name, with no termination criteria, sampling budgets, or success/failure thresholds. Since K-ARC's runtime and success rate are sensitive to these choices, the experimental section as written does not provide enough information to assess whether the comparison is fair or to reproduce the results. Please report these values and specify the subproblem solver configurations.","section":"§V-A and §IV-C"}],"minor_comments":[{"comment":"The state transition equation contains a typo: 'xi,k+1 = xi,t + f (xi,k, ui,k)∆t' should reference xi,k on the right-hand side, not xi,t.","section":"§II-C"},{"comment":"The cost function is written as J(xi,k, ui,k) = β1∥ui,k∥2 + ∆t, but the text says the optimizer minimizes ∆T; clarify whether the optimizer's time step is a decision variable and how it relates to the fixed simulation timestep ∆t defined in §II-C.","section":"§IV-B"},{"comment":"The symbol glast is used to define qlocal before it is formally introduced; define the previous segment's terminal state before line 16.","section":"Algorithm 1, lines 16-23"},{"comment":"The table caption contains a typo ('he quadrotor inlet' instead of 'the quadrotor inlet'). Also, since the runtime standard deviations are large (e.g., 81.98 for K-ARC in Table I), the paper should state whether the reported speedups are statistically significant.","section":"Table I"}],"recommendation":"major_revision","confidential_remarks":"The continuous-time safety gap in the current manuscript is the main obstacle to acceptance. It is not merely a theoretical subtlety: because the optimizer minimizes time and can use a coarse discretization, discrete-only checking can certify unsafe trajectories. I recommend requesting a revision that adds continuous-time checking or an interpolation bound and re-evaluates the experiments. If the authors can show the reported trajectories remain collision-free under continuous-time validation, the paper would be a suitable contribution. The baseline reimplementation issue should also be addressed before the speedup claims can be taken at face value."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear colleague,\n\nQuick take: K-ARC is a real algorithmic contribution and the experiments back the runtime picture as far as they go, but the paper's correctness claim stops at discrete timesteps. The stress-test note is on target: constraints (5)-(6), the conflict definition, and every collision check are evaluated at sampled states only. No swept-volume check, interpolation bound, or continuous-time validation is given. Since the optimizer minimizes total time and treats Delta t as a decision variable, nothing prevents a coarse discretization where two robots pass through each other between samples. That is load-bearing, because the abstract claims collision-free trajectories.\n\nWhat is actually new: the per-segment interleaving of single-robot trajectory optimization with sampling-based conflict resolution, plus the adaptation of ARC's subproblem structure to kinodynamic constraints. The local-goal discontinuity problem they identify is real, and their sequential construction is a sensible fix. They also earn credit for an honest design-choice discussion and for reporting conflict counts and success rates, not just runtime.\n\nThe soft spots, in proportion: (1) the continuous-time gap is the biggest issue; a serious revision should add a post-hoc swept-volume check or a formal bound. (2) The baselines are reimplementations without 'further improvements' from the original papers, as they admit; that limits the comparison but is not misleading if readers treat it as indicative. (3) No code or data release, so the one-to-two order-of-magnitude speedup is conditional on independent verification.\n\nWho this is for: researchers working on multi-robot kinodynamic planning, especially CBS-style conflict resolution. It deserves a serious referee; the central idea has merit and the gaps look fixable. My recommendation: send it to peer review, with a clear request to resolve the continuous-time collision issue and, if possible, release code.","headline":"A genuine extension of ARC with promising speedups, but the absence of a continuous-time collision check makes the core correctness claim only as strong as the discretization.","tokens_in":11339,"tokens_out":2041,"would_cite":false,"duration_ms":21377,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"K-ARC decomposes multi-robot kinodynamic planning into chained segments, achieving one to two orders of magnitude speed-ups and scaling to 32 simulated robots.","keywords":["multi-robot kinodynamic planning","adaptive robot coordination","trajectory optimization","sampling-based planning","conflict-based search","path segmentation","robot dynamics","scalability"],"falsifier":"Run K-ARC on a pair of robots crossing paths with a coarse timestep and small clearance, then re-sample the returned trajectories at much finer temporal resolution; finding any pair of states closer than $d_{\\min}$ between consecutive checked timesteps would show the returned plan is not collision-free.","tokens_in":10396,"feed_emoji":"🤖","tokens_out":10756,"duration_ms":87604,"temperature":0.7,"pith_summary":"K-ARC is an algorithm for planning trajectories for many robots that must obey dynamic constraints, such as unicycle and quadrotor models. The paper argues that planning should not be done once on full paths: instead, each robot's rough kinematic guide path is cut into segments, each segment is made dynamically feasible by a trajectory optimizer alone, and inter-robot collisions are handled only when they appear, by solving a small local subproblem with sampling-based planners. The claim is that this segment-wise interleaving of optimization and sampling makes multi-robot kinodynamic planning much faster, giving one to two orders of magnitude speed-ups over conflict-based-search baselines and allowing up to 32 robots in the simplest simulated scenario. A sympathetic reader would care because scalability to dozens of dynamically constrained robots is the bottleneck for warehouse, delivery, and surveillance applications.","feed_headline":"Segment-wise planner runs 32 robots 10-100x faster","feed_subtitle":"K-ARC splits paths, optimizes segments, resolves local conflicts, beats whole-path planners.","key_machinery":"The central mechanism is segment-wise interleaving: a kinematic guide path is divided into m equal segments, each segment is passed to a trajectory optimizer that minimizes control effort and duration under hard dynamic constraints, and conflicts are then resolved locally by a subproblem solver. The subproblem follows the pattern of ARC, Adaptive Robot Coordination, in which only robots involved in a conflict are merged into a local multi-robot query, but with kinodynamic adaptations: the local environment is not shrunk, and the start and goal queries are expanded to previous and next segment goals. The solver hierarchy is the load-bearing part of conflict resolution: cheap prioritized optimization is tried first, and sampling-based Kinodynamic RRT variants provide fallback exploration when optimization cannot find a feasible local trajectory.","core_discovery":"On its own terms, K-ARC establishes that multi-robot kinodynamic planning can be decomposed into a sequence of independent segment problems without losing feasibility. The algorithm first computes conflict-unaware kinematic paths with any sampling-based motion planner, splits them into m segments, and then for each segment runs a single-robot trajectory optimizer that respects dynamics and obstacle constraints. The resulting segment endpoints are chained as starts for the next segment, which solves the discontinuity problem that a direct extension of ARC would face. If two robots' optimized segments collide at a sampled timestep, K-ARC builds a local subproblem containing those robots and tries a hierarchy of solvers: prioritized trajectory optimization, then decoupled Kinodynamic RRT, then composite Kinodynamic RRT, expanding the local query only if all fail. In experiments, K-ARC is the only method to reach 32 robots in the open-cross scenario, and it reports one to two orders of magnitude runtime improvement over K-CBS and CB-MPC, a sampling-based and an optimization-based conflict-based-search planner respectively, on most tested configurations; it also succeeds in a constrained quadrotor inlet scenario where one baseline always fails.","pith_inferences":["An implication the paper leaves implicit is that the number of segments is a direct computation-quality trade-off: more segments shrink optimization problems but create more segment boundaries and coordination overhead, so per-scenario tuning of this parameter is a natural next experiment.","Because safety is only verified at discrete timesteps, a stress test with a deliberately coarse timestep and fine-grained post-sampling of returned trajectories would reveal whether the planner's guarantee covers continuous time.","The hybrid pattern suggests a modular recipe: a kinematic guide planner, a dynamics-aware optimizer, and a conflict-resolution oracle can be mixed and matched, which could extend to heterogeneous teams where robots have different dynamics and different optimizers."],"forward_implications":["If the reported results hold, K-ARC-type segment decomposition gives a practical way to push multi-robot kinodynamic planning well beyond the roughly 8 to 16 robot limits of the tested whole-trajectory conflict-based-search planners.","Because each segment optimizer handles only a short trajectory, the per-call nonlinear program is small, which is the stated reason optimization remains fast even as robot count grows.","The solver hierarchy means the framework degrades gracefully: cheap optimization handles easy local conflicts, and sampling-based planners are invoked only when the optimizer fails.","Sequential segment chaining makes the method applicable to any kinodynamic system for which a single-robot trajectory optimizer and a multi-robot kinodynamic planner exist."],"supporting_citations":[{"why":"ARC, the subproblem-based coordination framework that K-ARC extends to kinodynamic planning and whose discontinuity problem motivates the segment chaining.","marker":"[7]"},{"why":"K-CBS, the sampling-based baseline method that K-ARC is compared against in the experiments.","marker":"[6]"},{"why":"CB-MPC, the optimization-based baseline method that K-ARC is compared against in the experiments.","marker":"[5]"},{"why":"CBS, the high-level conflict-based search framework underlying both baselines and the main contrast for K-ARC's local subproblem approach.","marker":"[2]"},{"why":"Kinodynamic RRT, the sampling-based planner used inside K-ARC's fallback solver hierarchy.","marker":"[1]"},{"why":"Prioritized trajectory optimization, the first solver in K-ARC's local conflict-resolution hierarchy.","marker":"[4]"},{"why":"A recent CBS-based kinodynamic planner whose duration-minimizing trajectory optimization formulation K-ARC's optimizer mirrors.","marker":"[3]"}],"fun_headline_variants":["K-ARC runs 32 robots 10-100x faster","Segment-wise planner speeds up kinodynamic planning","K-ARC plans 32 robots with local conflict resolution","10-100x faster multi-robot planning with K-ARC","Segment-based approach scales to 32 robots"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole safety argument rests on checking collisions only at the fixed timesteps of the discretized dynamics, with no verification that the continuous trajectories between those timesteps stay separated.","fun_headline_variants_meta":{"raw":{"variants":["K-ARC runs 32 robots 10-100x faster","Segment-wise planner speeds up kinodynamic planning","K-ARC plans 32 robots with local conflict resolution","10-100x faster multi-robot planning with K-ARC","Segment-based approach scales to 32 robots"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001075,"raw_usage":{"total_tokens":4526,"prompt_tokens":998,"completion_tokens":3528,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":614,"completion_tokens_details":{"reasoning_tokens":3449}},"tokens_in":614,"tokens_out":3528,"duration_ms":24558,"temperature":1.0,"reasoning_tokens":3449,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T22:25:41.130436+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run K-ARC on a pair of robots crossing paths with a coarse timestep and small clearance, then re-sample the returned trajectories at much finer temporal resolution; finding any pair of states closer than $d_{\\min}$ between consecutive checked timesteps would show the returned plan is not collision-free.","supporting_citations":[{"cited_title":"Adaptive robot coordination: A subproblem-based approach for hybrid multi-robot motion planning,","cited_arxiv_id":null,"evidence_quote":"ARC, the subproblem-based coordination framework that K-ARC extends to kinodynamic planning and whose discontinuity problem motivates the segment chaining."},{"cited_title":"Conflict-based search for multi-robot motion planning with kinodynamic constraints,","cited_arxiv_id":null,"evidence_quote":"K-CBS, the sampling-based baseline method that K-ARC is compared against in the experiments."},{"cited_title":"Conflict-based model predictive control for scalable multi-robot motion planning,","cited_arxiv_id":null,"evidence_quote":"CB-MPC, the optimization-based baseline method that K-ARC is compared against in the experiments."},{"cited_title":"Conflict- based search for optimal multi-agent pathfinding,","cited_arxiv_id":null,"evidence_quote":"CBS, the high-level conflict-based search framework underlying both baselines and the main contrast for K-ARC's local subproblem approach."},{"cited_title":"Randomized kinodynamic planning,","cited_arxiv_id":null,"evidence_quote":"Kinodynamic RRT, the sampling-based planner used inside K-ARC's fallback solver hierarchy."},{"cited_title":"Efficient trajectory planning for multiple non- holonomic mobile robots via prioritized trajectory optimization,","cited_arxiv_id":null,"evidence_quote":"Prioritized trajectory optimization, the first solver in K-ARC's local conflict-resolution hierarchy."},{"cited_title":"db- cbs: Discontinuity-bounded conflict-based search for multi-robot kin- odynamic motion planning,","cited_arxiv_id":null,"evidence_quote":"A recent CBS-based kinodynamic planner whose duration-minimizing trajectory optimization formulation K-ARC's optimizer mirrors."}],"review_version":1}