{"id":"75c8f8a6-58ac-4110-8dcc-45d56d8bf056","arxiv_id":"2505.08593","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":6,"one_line_summary":"MC-Swarm plans safe, deadlock-free quadrotor swarm trajectories with asynchronous updates and no inter-agent communication during flight, backed by collision-avoidance and deadlock-resolution theorems.","lead":"MC-Swarm is a distributed quadrotor-swarm planner that lets agents plan trajectories asynchronously and, in one variant, exchange nothing after the mission starts. It combines grid-based waypoints with per-agent subgoal optimization and claims mathematical guarantees for collision avoidance and deadlock resolution in cluttered environments.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Modified BVC inclusion asserted in Sec. IV-C can fail when the two subgoal segments are closer than 2r, so the safety and deadlock proofs rest on an unproved geometric claim.","rationale":"The reader's weakest_assumption identifies the same load-bearing gap: the modified BVC's segment-inclusion property is asserted, not proved, and it can fail when subgoal segments come closer than 2r. My constructed state shows the failure is not merely hypothetical under the paper's grid parameters. This gap undermines the proof chain for Theorems 1, 2, and Lemma 6, which all rely on the agent's own position and subgoal segment lying inside V_i. I do not recommend rejection because the algorithm may be repairable: one could replace the modified BVC with a construction that provably contains the agent's subgoal segment, or add an invariant ensuring L >= 2r, or inflate the radius used in the BVC separation. The secondary concern about the validation parameters violating T < T_r is real but less fundamental; it affects the applicability of Theorem 2 to the reported experiments, not the theorem's internal logic. The same issue was noted by the reader, and my check would settle whether the promised guarantees are currently supported.","tokens_in":19120,"tokens_out":11662,"duration_ms":124494,"concrete_test":"Recompute Eq. (11) for the two-agent state with d=0.5, r=0.15, p_i=(0.2,0), g_i=(0.5,0), p_j=(0.5,0.2), g_j=(0.5,0.5). Compute c_{i,j}, c_{j,i}, n_{i,j}, d_{i,j}, and check whether p_i ∈ V_i and p_j ∈ V_j. If either membership fails, the Sec. IV-C inclusion assertion is false. If the authors claim this state is unreachable, run an exhaustive search over all two-agent states on a small grid that satisfy the Algorithm 2 coordination-state rules; if any pair has subgoal-segment distance L < 2r while agent positions are at least 2r apart, the asserted inclusion is not guaranteed and the proofs must be repaired.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central guarantee depends on the claim after Eq. (11) that each modified BVC contains the segment [p_i, g_i^(h-1)]. From Eq. (11), for any x on that segment the achievable margin (x - c_{j,i})·n_{i,j} is at most L = ||c_{i,j} - c_{j,i}||, the distance between the two subgoal segments, while the required margin is d_{i,j} = r + L/2. Thus the inclusion holds only if L >= 2r. The coordination-state update never establishes such a separation. Subgoal segments can lie on adjacent grid edges that approach or meet at a vertex; Lemma 4 forbids two interior subgoals on the same edge but does not prevent subgoal segments on different edges from being arbitrarily close. A concrete valid-looking state with the paper's own parameters d=0.5, r=0.15 is: p_i=(0.2,0), g_i=(0.5,0); p_j=(0.5,0.2), g_j=(0.5,0.5). Here ||p_i - p_j||=0.36 > 2r, but L=0.2 < 2r, and p_i gives margin 0.2 < 0.25, so p_i is not in V_i. When this happens, the trajectory optimization (15) can be infeasible at the agent's own position, the 'no optimization failure' premise of Theorem 1 can fail, and Theorem 2's failure-recovery argument also relies on p_i^(h) ∈ V_i. Lemma 6's feasible-control construction uses the same segment-inclusion claim. Without an additional invariant maintaining L >= 2r, the safety and deadlock guarantees are not established.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper presents MC-Swarm, a distributed asynchronous multi-agent trajectory planning framework for quadrotor swarms. It consists of a coordination state updater that computes waypoints, safe flight corridors, modified buffered Voronoi cells, and optimized subgoals, and a trajectory optimizer that solves a quadratic program with conservative collision constraints sampled over a window of past coordination states. Two variants are proposed: MC-Swarm-N, which requires no communication after initialization, and MC-Swarm-C, which uses lightweight communication to accelerate waypoint updates. The central claims are Theorem 1 (collision avoidance under asynchronous replanning when optimization succeeds), Theorem 2 (collision avoidance regardless of optimization failure under a horizon condition), and Theorem 3 (deadlock resolution). Experiments compare against MADER, EGO-v2, DREAM, and GCBF+ in obstacle-free, forest, and maze environments, plus hardware tests with eight Crazyflies.","tokens_in":19556,"tokens_out":9454,"duration_ms":87544,"significance":"The paper addresses an important problem: formal guarantees for communication-free asynchronous swarm trajectory planning. The proof structure is coherent and the empirical validation is extensive, including real-world experiments. If the theorems were valid, the contribution would be significant for multi-robot systems. However, the main safety and deadlock guarantees rest on a geometric segment-inclusion property that is not proved and is in fact false under the paper's own assumptions; in addition, the validation parameters violate the hypothesis of Theorem 2. As a result, the paper's central formal claims are not established.","major_comments":[{"comment":"The sentence asserting that the modified BVC 'includes the line segment between \\hat{p}_i and g_i^{(h-1)}' is made without proof, and the asserted inclusion is false when the two subgoal segments come closer than 2r. From Eq. (11), for any x on [\\hat{p}_i, g_i^{(h-1)}], the left-hand side of (11a) is at most L = ||c_{i,j} - c_{j,i}||, while the required margin is d_{i,j} = r + L/2; hence the inclusion holds only if L >= 2r. The coordination-state update never establishes this separation. In particular, adjacent grid edges can meet at a vertex, so subgoal segments on different edges can be arbitrarily close; Lemma 4 excludes only two interior subgoals on the same grid edge. A concrete counterexample with the paper's simulation parameters d=0.5, r=0.15 is: p_i=(0.2,0), g_i=(0.5,0); p_j=(0.5,0.2), g_j=(0.5,0.5). Here ||p_i - p_j|| ≈ 0.36 > 2r = 0.3, but the distance between the two segments is L = 0.2, and (p_i - c_{j,i})·n_{i,j} = 0.2 < d_{i,j} = 0.25, so p_i ∉ V_i. Thus an agent's own position can lie outside its own safety cell, the constraint in (15) can be infeasible at k=0, and the 'no optimization failure' premise of Theorem 1 can fail. Theorem 2's recovery argument also assumes \\hat{p}_i^{(h)} ∈ V_i^{(h)}, and Lemma 6's feasible-control construction assumes [p_{i,d}, g_{i,d}] ⊂ V_i. Without an additional invariant enforcing L >= 2r, the proofs of Theorems 1, 2, and 3 are not valid.","section":"Section IV-C, after Eq. (11)"},{"comment":"Theorem 2 states its conclusion under the hypothesis that 'the planning horizon T and trajectory replanning period are less than the maximum replanning period T_r.' The validation in Section VI, however, sets T = 1.0 s and T_r = 0.2 s, so T > T_r. The proof of Theorem 2 explicitly uses the inequality t_j - t_i < T < T_r in Case 1 and relies on the stopping argument in Case 2; with T = 1.0 > T_r = 0.2, the stated guarantee does not apply to any of the reported simulations or experiments. This is a load-bearing mismatch between the theoretical claim and the empirical validation.","section":"Section V-B, Theorem 2 and Section VI parameters"}],"minor_comments":[{"comment":"The text reports 'Δth = 0.1 s' but later specifies 'time step Δt = 0.2 s' and T = M Δt = 5 × 0.2 = 1.0 s; the symbol Δth appears to be a typo and should be Δt = 0.2 s.","section":"Section VI, simulation parameters"},{"comment":"The sentence 'the weight parameters in the cost (16) are set as w_e = 0.01 and w_g = 0.1' should refer to w_e and w_a, matching the notation in Eq. (16).","section":"Section VI, cost weights"},{"comment":"There is a typo in 'MC-Swarm-C: Commnucation-based' which should read 'Communication-based.'","section":"Section VI, algorithm names"},{"comment":"The symbol M is used both for the number of planning steps and for the index set {0, ..., M}; using a different symbol, such as \\mathcal{M}, for the set would remove ambiguity in the statement of problem (15).","section":"Section V-A, notation"},{"comment":"The figure illustrates the claimed segment-inclusion property only for well-separated subgoal segments; adding a case where subgoal segments meet at a grid vertex would make the limitation discussed in Major Comment 1 visible.","section":"Section IV-C, Fig. 3"}],"recommendation":"reject","confidential_remarks":"The central formal claims of the paper are not supportable as written. The segment-inclusion property after Eq. (11) is demonstrably false under the paper's own assumptions, and the validation parameters violate the hypothesis of Theorem 2. These are load-bearing issues, not presentation concerns. The empirical results may still be valuable, but the theoretical contribution requires a substantial rework (e.g., adding and proving a separation invariant, and either changing the validation to satisfy T < T_r or extending the theory to T >= T_r). The reviewer also notes that much of the geometric machinery is drawn from the authors' prior work; the novel asynchronous analysis is the part that fails."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear colleague,\n\nQuick take: the paper's headline claim—formal collision avoidance and deadlock resolution with no inter-agent communication—does not hold as proven. The key geometric assertion, made right after Eq. (11), is that the modified BVC contains the line segment from the agent's current position to its previous subgoal. That is not true in general, and the paper gives no proof.\n\nWhat's genuinely new: this extends the authors' DLSC-GC line to asynchronous updates and no communication during flight, and the conservative constraint window (inspired by DSHT) is a sensible way to handle asynchrony. The two-module structure is clean, and the empirical section is solid: 100% success in the maze and forest benchmarks, where several SOTA methods fail, plus an eight-Crazyflie hardware demo. The communication-fast variant is a nice practical addition.\n\nNow the soft spot, and it's central. From Eq. (11), for any x on [p_i, g_i^(h-1)], the margin (x - c_{j,i})·n_{i,j} is at most L = ||c_{i,j} - c_{j,i}||, the distance between the two subgoal segments, while the required margin is d_{i,j} = r + L/2. So the segment is contained only if L >= 2r. Nothing in the coordination-state update maintains that separation. A concrete counterexample with the paper's own parameters (d=0.5, r=0.15): p_i=(0.2,0), g_i=(0.5,0); p_j=(0.5,0.2), g_j=(0.5,0.5). Then ||p_i-p_j||=0.36 > 2r, but L=0.2, and p_i gives margin 0.2 < 0.25, so p_i is not in V_i. The entire segment is outside V_i. This breaks the premise of Theorem 1 and the failure-recovery argument of Theorem 2, and Lemma 6's feasible-control construction uses the same inclusion. The subgoal optimization only puts g_i in V_i, not p_i, so the trajectory optimization (15) can be infeasible at the agent's own position.\n\nSeparately, the validation sets T=1.0 s and Tr=0.2 s, which violates Theorem 2's stated condition T < Tr. The theorem's proof may not actually need that condition, but as written it's a mismatch.\n\nThe paper is worth a serious referee: the idea is well motivated and the experiments are impressive, but the theoretical core needs repair. The authors need either to prove an invariant that keeps L >= 2r, modify the BVC to restore the inclusion property, or weaken the guarantee. As it stands, I wouldn't cite the formal results, though I'd point to the empirical comparison.\n\nMy call: accept for peer review, but expect major revision.","headline":"Solid engineering and experiments, but the central safety proof has a load-bearing gap: the modified BVC does not in general contain the agent's own position-to-subgoal segment.","tokens_in":20024,"tokens_out":6369,"would_cite":false,"duration_ms":56928,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"MC-Swarm guarantees collision avoidance and deadlock resolution for quadrotor swarms with zero in-flight communication.","keywords":["multi-agent trajectory planning","quadrotor swarm","asynchronous planning","deadlock resolution","buffered Voronoi cells","communication-free coordination","safe flight corridor","subgoal optimization"],"falsifier":"Record, at every coordination-state update in simulation, the closest-point distance between each pair of subgoal line segments; if any pair is ever below $2r$, the inclusion lemma behind Eq. (11) fails at that step, so the collision-avoidance theorems no longer apply. A stronger test is to construct start/goal assignments on the grid whose MAPF paths force two subgoal segments to cross in a corridor narrower than $2r$, and check whether the quadratic program (15) becomes infeasible or the agent's trajectory exits its own BVC.","tokens_in":18920,"feed_emoji":"🚁","tokens_out":8750,"duration_ms":78365,"temperature":0.7,"pith_summary":"MC-Swarm tackles a bottleneck in multi-agent swarm navigation: coordinating many quadrotors usually requires continuous communication and synchronized replanning, which breaks down under delays, packet loss, or jamming. The paper claims that a swarm can instead exchange nothing after an initial one-time exchange of start and goal positions, then fly asynchronously with formal guarantees of collision avoidance and deadlock resolution. Each agent senses the others' positions, builds the same safety constraints locally, and plans a trajectory with conservative constraints drawn from a short time window so that asynchronous replanning cannot create out-of-date overlaps. The algorithm is shown to complete goal-reaching missions in dense forests and narrow mazes where several state-of-the-art methods fail, and in hardware tests with eight quadrotors.","feed_headline":"Proof: quadrotor swarms can fly collision-free with zero in-flight talk","feed_subtitle":"After a one-time goal exchange, agents plan asynchronously with formal safety and deadlock guarantees.","key_machinery":"The load-bearing construction is the modified Buffered Voronoi Cell (BVC): a half-space intersection $V_i$ built from the closest points $c_{i,j}$ between the two line segments $[\\hat{p}_i, g_i^{(h-1)}]$ and $[\\hat{p}_j, g_j^{(h-1)}]$ (Eq. 11). The cell is intended to contain the whole segment from the agent's position to its previous subgoal, so the subgoal is never unreachable because of a neighbor's safety region. Subgoal optimization (Eq. 14) then chooses, along the grid edge toward the waypoint, the point closest to the waypoint that still lies inside the intersection of the SFC and the modified BVC, and Lemma 4 ensures no two agents' subgoals occupy the interior of the same grid edge. Finally, the trajectory optimizer (Eq. 15) enforces every collision constraint produced in the window $[t - T_r - T_s, t]$ and requires $v_{i,M}=0$, which makes asynchronous replanning safe: any two agents share at least one common constraint, and a stopped agent remains inside a recently valid cell.","core_discovery":"The paper's central claim is that asynchronous, communication-free operation does not cost safety or progress. It proves that if agents replan within a maximum period $T_r$ and the planning horizon is $T < T_r$, then no two agents ever violate the separation $\\|p_i(t)-p_j(t)\\| \\ge 2r$ and no agent collides with static obstacles—even when the trajectory QP fails, because the final stop constraint keeps a failed agent inside a recent safety cell. It then proves a deadlock-resolution theorem: under a solvable grid-based multi-agent pathfinding instance and grid spacing $d > 2\\sqrt{2}r$, every agent reaches its goal. These guarantees are obtained by constructing identical coordination states locally from sensed positions and by a subgoal rule that keeps agents on distinct grid edges, so that blocking cycles are impossible.","pith_inferences":["The guarantee effectively converts pairwise safety into a geometric separation requirement on subgoal segments; a natural extension is to enforce that separation explicitly in the subgoal optimization, which would close the proof gap identified around Eq. (11).","If the grid assumption is relaxed, an analogous deadlock argument may hold for any graph of short, separated 'edges' that agents traverse in discrete steps, suggesting a general distributed coordination-graph design.","One testable extension is to replace the assumed noiseless sensing with explicit measurement-error bounds and enlarge the BVC margin accordingly, which would let the formal guarantee survive realistic perception noise rather than the heuristic radius inflation used in experiments."],"forward_implications":["A quadrotor swarm can operate in communication-denied or high-latency environments, such as underground or jammed areas, while retaining formal safety guarantees, provided agents can sense each other's positions and share goals once.","The condition $d > 2\\sqrt{2}r$ gives designers a direct rule relating grid resolution to robot radius; missions on coarser grids lose the deadlock-free guarantee.","Asynchronous replanning itself is not an obstacle to provable collision avoidance: the time-window constraint trick used here can be applied to other decentralized planners that suffer from outdated information.","The subgoal-optimization layer (unique grid-edge subgoals) is independent of the trajectory optimizer and could be reused with other local trajectory planners to prevent deadlock.","The communication-based variant MC-Swarm-C shows that even exchanging a tiny consensus bitmask about which agents reached their waypoints cuts mission time noticeably, because agents no longer wait for the slowest peer."],"supporting_citations":[{"why":"PIBT provides the grid-based MAPF with a goal-reachability guarantee that Theorem 3 relies on.","marker":"[36]"},{"why":"Original buffered Voronoi cells supply the half-space construction that Eq. (11) modifies for subgoal segments.","marker":"[39]"},{"why":"Safe flight corridors give the obstacle-avoidance convex sets used in the SFC construction (Eq. 8).","marker":"[37]"},{"why":"The authors' prior DLSC-GC guarantees collision avoidance and deadlock resolution under synchronization; this paper extends it to asynchronous, communication-free operation.","marker":"[24]"},{"why":"The DLSC coordination-state concept (waypoints, subgoals, collision constraints) is the foundation of the update module.","marker":"[33]"},{"why":"The previous deadlock-free decentralized planner is the direct source of the modified BVC and subgoal optimization approach.","marker":"[35]"},{"why":"DREAM's discretized separating hyperplane trajectories inspire the conservative time-window constraints used in the trajectory optimizer.","marker":"[20]"},{"why":"DSHT's asynchronous separating-hyperplane technique supplies the conservative-constraint rationale for replanning asynchrony.","marker":"[40]"}],"fun_headline_variants":["Formal proof: quadrotor swarms fly safe with zero mid-air messages","Guaranteed collision-free and deadlock-free: zero communication during flight","Asynchronous quadrotor swarm: safety and deadlock resolution without talking","No in-flight chatter: provably safe and deadlock-free swarm planning"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The safety proof assumes that each agent can always draw a straight line from its own position to its subgoal without leaving its private safety region, and this only holds if the straight-line segments of different agents stay at least two robot radii apart—something the paper states but does not prove its update rule preserves.","fun_headline_variants_meta":{"raw":{"variants":["Formal proof: quadrotor swarms fly safe with zero mid-air messages","Guaranteed collision-free and deadlock-free: zero communication during flight","Asynchronous quadrotor swarm: safety and deadlock resolution without talking","No in-flight chatter: provably safe and deadlock-free swarm planning"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000372,"raw_usage":{"total_tokens":1979,"prompt_tokens":922,"completion_tokens":1057,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":538,"completion_tokens_details":{"reasoning_tokens":976}},"tokens_in":538,"tokens_out":1057,"duration_ms":8206,"temperature":1.0,"reasoning_tokens":976,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T21:52:16.793923+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Record, at every coordination-state update in simulation, the closest-point distance between each pair of subgoal line segments; if any pair is ever below $2r$, the inclusion lemma behind Eq. (11) fails at that step, so the collision-avoidance theorems no longer apply. A stronger test is to construct start/goal assignments on the grid whose MAPF paths force two subgoal segments to cross in a corridor narrower than $2r$, and check whether the quadratic program (15) becomes infeasible or the agent's trajectory exits its own BVC.","supporting_citations":[{"cited_title":"Real-time trajectory generation for constrained nonlinear dynamical systems using non-uniform rational b-spline basis functions,","cited_arxiv_id":null,"evidence_quote":"Safe flight corridors give the obstacle-avoidance convex sets used in the SFC construction (Eq. 8)."},{"cited_title":"Decentralized trajectory planning for quadrotor swarm in cluttered environments with goal convergence guarantee,","cited_arxiv_id":null,"evidence_quote":"The authors' prior DLSC-GC guarantees collision avoidance and deadlock resolution under synchronization; this paper extends it to asynchronous, communication-free operation."},{"cited_title":"Dlsc: Distributed multi-agent trajectory planning in maze-like dynamic environments using linear safe corridor,","cited_arxiv_id":null,"evidence_quote":"The DLSC coordination-state concept (waypoints, subgoals, collision constraints) is the foundation of the update module."},{"cited_title":"Dream: Decentralized real-time asynchronous probabilistic trajectory planning for collision-free multi- robot navigation in cluttered environments,","cited_arxiv_id":null,"evidence_quote":"DREAM's discretized separating hyperplane trajectories inspire the conservative time-window constraints used in the trajectory optimizer."},{"cited_title":"Asynchronous real-time decentral- ized multi-robot trajectory planning,","cited_arxiv_id":null,"evidence_quote":"DSHT's asynchronous separating-hyperplane technique supplies the conservative-constraint rationale for replanning asynchrony."}],"review_version":1}