{"id":"2db4ecf5-346b-4d5d-96bb-104e77b6befa","arxiv_id":"2505.14760","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"A two-stage method computes relay chains and cluster-visit orders that let large robot teams reach many goals while keeping intermittent connectivity to a base station.","lead":"This paper presents a two-stage planner that tells a team of robots where to stand as relays and in what order to visit target locations, so the team can stay connected to a fixed base station while covering hundreds of goals. A generalist might care because it addresses how to coordinate large robot teams for tasks like disaster-area inspection when direct wireless links are impossible.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Relay-chain construction in §4.2 has no validity guarantee: sampling a Voronoi path every d_gamma meters does not ensure consecutive relays have line of sight around bends, so one infeasible branch invalidates the corresponding cluster.","rationale":"The reader's verdict is CONDITIONAL with moderate confidence, and the reader identifies the same weakest assumption: the relay-chain construction in §4.2 has no demonstrated validity guarantee. The central claim is a scalable heuristic, so approximate clustering and ordering are acceptable; what cannot be relaxed is that each computed plan must be physically executable. The load-bearing point is that a deployment plan is valid only if every branch provides a multi-hop LoS connection from the BS to its maximum-connectivity relay. Section 4.2 merely asserts relay placement 'with LoS along the path' without specifying a verification step or a fallback, and no failure count is reported in the experiments. This is a missing support rather than an internal contradiction, and the proposed test directly checks feasibility on the same scenario plus an adversarial map. If the test passes, the concern is minor and the claims stand as stated; if it fails, the method requires either a repair or an explicit caveat. Other noted issues, such as the MST-equivalence claim, would affect optimality or comparison strength but not the basic validity of the produced plans, so they are less load-bearing than the relay-chain feasibility gap.","tokens_in":9973,"tokens_out":3979,"duration_ms":38079,"concrete_test":"Implement the relay-chain placement from Section 4.2 on the original map of Fig. 3(a) with dγ = 10 m and grid resolution 0.2 m, and also on a synthetic U-shaped corridor with a bend tighter than dγ. For each xmc, sample the Voronoi path from the BS at arc-length intervals of dγ and test line of sight between every consecutive relay pair and both endpoints using the same LoS model. Count the number of clusters for which no valid chain results. If the count is zero in both maps, the concern does not land; if any branch fails, the method needs a fallback or a validity proof.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim — that the method produces deployment plans under connectivity constraints for up to 50 robots and 500 goals — depends on every computed relay chain being physically realizable. Section 4.2 says only that after obtaining Voronoi Paths from xBS to each xmc, the algorithm computes relay positions 'placing the relay positions with an interval dγ and with LoS along the path from xmc to xBS.' No algorithm, proof, or failure-handling is given for the LoS condition. A Voronoi path can bend sharply around obstacles; if the straight segment between two consecutive relay positions separated by path length dγ leaves free space, the radio link between those relays (or between a relay and an endpoint) is blocked. The paper does not state that such placements are verified, nor what happens for a branch where no LoS-compliant placement exists. If even one branch fails, the goals in that cluster cannot transmit to the BS, invalidating the deployment plan for that cluster. This is not merely a theoretical gap: the FMM Voronoi-path construction in §3.3 is not shown to have the property that arc-length samples are mutually visible, and the simulation section reports no check or count of infeasible branches. The method may still work on the tested maps, but the feasibility condition is asserted rather than established.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper addresses the problem of deploying a team of robots to reach primary goals while maintaining multi-hop connectivity to a static base station. The proposed method has two stages: first, it computes 'maximum-connectivity' relay positions and builds relay chains along Fast Marching Method (FMM) Voronoi paths, grouping goals into clusters; second, it allocates goals to robots via a Hungarian-method assignment and orders cluster visits using several sequential or concurrent heuristics. The evaluation is carried out in a single simulated scenario, with up to 50 robots and 500 goals, and reports mission time and computation time results. The central claims are that the method is fast and scalable, and that concurrent heuristics reduce mission time by 17-31% compared with sequential ones in the tested settings.","tokens_in":10243,"tokens_out":7729,"duration_ms":76742,"significance":"The problem is practically relevant for CBRNE, exploration, and monitoring missions where a team must connect to a fixed base station. The paper's strongest asset is its explicit algorithmic pipeline (Alg. 1) combining FMM-based Voronoi paths with a small set of visit-ordering heuristics; Table 2 does show that the method can produce plans for large instances in seconds. If the correctness gap in relay-chain construction were closed and the experimental comparison strengthened, the approach would be a useful practical tool. However, in its current form, the paper does not establish that every generated relay chain is physically realizable under line-of-sight constraints, and this directly affects the validity of the main contribution.","major_comments":[{"comment":"The construction of relay chains is not shown to be feasible. The text states only that relay positions are placed 'with an interval dγ and with LoS along the path' from xmc to xBS, but no algorithm or proof verifies that the straight segment between consecutive relay positions lies in free space. A Voronoi path can bend sharply around obstacles, and sampling it every dγ meters does not guarantee mutual visibility of consecutive relays; if one branch is infeasible, the associated goals cannot reach the base station. Please specify the LoS verification/repair procedure and, in Sec. 6, report how often such failures occur, or provide a proof that the FMM Voronoi paths used here have the required visibility property.","section":"§4.2"},{"comment":"The claim that the greedy maximum-connectivity selection 'correspond[s] to the points of MST' is unsupported and, in general, false. Selecting, at each iteration, the grid position covering the most not-yet-covered primary goals is a set-cover-like heuristic; it does not minimize the number of relay positions or compute a minimum Steiner tree. Since the paper states the objective of 'minimizing the number of robots devoted as relays' (§1) and the number of relays affects mission feasibility, the statement in §4.1 should be rephrased as a heuristic claim, or a proof of optimality should be supplied.","section":"§4.1"},{"comment":"The cost modification D*_relay = D_relay · min(D)/max(D_relay) does not guarantee that relay goals are always assigned before primary goals. If a primary goal has distance equal to min(D), a relay goal at distance max(D_relay) receives the same scaled cost, and the Hungarian method may break the tie by assigning a robot to the primary goal first, contrary to the statement that 'the Hungarian algorithm always allocates first the relay goals.' The authors should either add an explicit tie-breaking rule favoring relays or prove that such ties cannot affect the relay-priority order.","section":"§5.1, Eq. (1)"},{"comment":"The performance claims are not statistically supported. Mission-time results in Fig. 5 are means over 10 random goal configurations without standard deviations, confidence intervals, or significance tests, so statements such as 'a clear improvement ... being 30% and 21%' and '17% and 31%' cannot be assessed as reliable. In addition, the comparison with prior work in §6.2 is anecdotal: times for [1] and [11] are taken from different environments, problem sizes, and hardware. Please add variance/interval information and a quantitative baseline on the same benchmark, or at least an optimal/lower-bound comparison for small instances.","section":"§6.1 and §6.2"}],"minor_comments":[{"comment":"The notation for numbers of robots and goals is inconsistent: §3.1 defines M robots and N goals, while §6.1 uses N robots and M goals; please make the notation uniform throughout.","section":"§3.1 and §6.1"},{"comment":"The thresholds for switching among the TSP solvers (12 and 20 instances) are said to be 'empirically adjusted for our computer,' but no sensitivity analysis is provided; a brief note on how these thresholds affect solution time or quality would help reproducibility.","section":"§5.2.1"},{"comment":"The grid resolution is 0.2 m and the communication range is dγ = 10 m; please clarify how relay positions are represented when dγ is not an integer multiple of the grid resolution, and whether any interpolation is applied.","section":"§6"},{"comment":"The phrase 'sub-optimal solutions' is used in the abstract, but the paper also claims in §4.1 that the relay positions correspond to a minimum Steiner tree; please make the optimality status of different components consistent.","section":"Abstract and §2"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Let me tell you what to expect from this paper. It is an engineering contribution, not a theory advance: a two-stage heuristic pipeline for multi-robot deployment with intermittent connectivity. Stage one builds relay chains from an FMM-computed Voronoi path to greedy max-connectivity points; stage two orders cluster visits with 17 sequential or concurrent heuristics. The new part is the combination and the scale—up to 50 robots and 500 goals, with computation times in seconds. The simulation study is systematic, and the 17–31% mission-time improvement of concurrent over sequential heuristics in the tested layouts is plausible and useful for practitioners.\n\nThe pipeline is clearly specified, and the FMM cost model, Hungarian allocation, and TSP thresholds are all standard and reasonably presented. But there is a real soft spot in §4.2. Relay positions are placed along the Voronoi path every d_gamma meters, with the assertion of line-of-sight along the path. The paper supplies no algorithm for checking or enforcing LoS between consecutive samples, no fallback if the path bends around an obstacle, and no report of infeasible branches in the experiments. Since each cluster's plan depends on its chain being physically realizable, this is a load-bearing assertion that is currently unproven. It is likely patchable—verify visibility and locally adjust the sampling or route—but as written it is a gap.\n\nTwo smaller issues. The runtime claim that a solution is found 'in less than a second' is contradicted by the authors' own Table 2 (5.67 s for relay goals with 500 goals). And the statement that the greedy max-connectivity points 'correspond to the points of MST' is not established; the heuristic may be a reasonable Steiner tree proxy, but the MST equivalence is overclaimed. There are no external baselines, so all performance claims are internal comparisons between heuristics.\n\nOverall, the core method is sensible and the scalability claim is worth checking under adversarial maps. The citation pattern is fine; the self-citation is a legitimate continuation of prior work. I would send this to peer review, asking the authors to fix the LoS verification, add a baseline, and correct the runtime statement.","headline":"A practical, moderately novel engineering paper whose relay-chain construction has an unverified LoS condition that needs patching.","tokens_in":10739,"tokens_out":3352,"would_cite":false,"duration_ms":29574,"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":"A two-stage planner can deploy up to 50 robots to reach hundreds of goals while keeping a link to the base station, computing sub-optimal but fast solutions within seconds.","keywords":["multi-robot deployment","relay chain planning","connectivity constraints","line-of-sight communication","Fast Marching Method","Voronoi path","cluster visit ordering","task allocation"],"falsifier":"In a map with a large obstacle that forces the Voronoi path to turn sharply, compute the relay chain by the paper's interval-$d_\\gamma$ sampling and check line-of-sight between consecutive relays and to the base station and maximum-connectivity point; if any pair fails, that cluster's goals cannot be connected, so the method's coverage guarantee for that scenario fails.","tokens_in":9770,"feed_emoji":"🤖","tokens_out":5008,"duration_ms":49946,"temperature":0.7,"pith_summary":"This paper tackles a practical bottleneck in multi-robot missions: a team must reach many target locations and stream information back to a fixed base station, but obstacles and limited radio range usually prevent direct links. The authors propose a two-stage planning method. First, it computes a small set of relay positions and chains of intermediate relay points that connect every target to the base station, grouping them into clusters. Second, it orders cluster visits with several fast heuristics, choosing between sequential and concurrent deployment. The central claim is that this decomposition yields sub-optimal but workable deployment plans in seconds for teams of up to 50 robots and 500 goals, with concurrent heuristics cutting mission time by 17-31 percent over sequential ones when the team is large enough.","feed_headline":"Planner links 500 robot goals to base in seconds","feed_subtitle":"Two-stage planner builds relay chains, then orders cluster visits; concurrent deployment beats sequential by up to 31 percent.","key_machinery":"The load-bearing machinery is the Voronoi Path (VP), an obstacle-avoiding path from the base station to each maximum-connectivity point, computed with the Fast Marching Method on the grid. Placing relay positions every $d_\\gamma$ meters along this path, with line-of-sight between consecutive points, turns a single path into a chain of robots that maintains communication. Around this sit the maximum-connectivity relay points, chosen iteratively to cover the most not-yet-connected primary goals, the clusters formed by each chain plus its goals, and the cost heuristics (distance between clusters, required relays, mean and worst cluster cost, primary-goal count) that drive the visit order.","core_discovery":"The paper's discovery is that connectivity-constrained deployment can be made scalable by separating relay placement from visit scheduling. For relay placement, the method computes maximum-connectivity positions where as many primary goals as possible can be linked, then extends relay chains from the base station to those positions along Voronoi paths that keep relays away from obstacles. For scheduling, it groups each chain with its primary goals into clusters and tests eight sequential and nine concurrent heuristics for visiting them, using the Hungarian method to allocate goals to robots with relay goals prioritized. In the tested scenarios, the best concurrent methods (notably C1, relay-number level with level-by-level chain extension) reduce total mission time by about 17 to 31 percent relative to the best sequential methods for teams of 20 and 50 robots when the base station is centered, while the sequential distance-only heuristic S1 is the most reliable across base-station positions.","pith_inferences":["The Voronoi-path relay construction could be stress-tested in obstacle-dense environments with narrow corridors; if line-of-sight breaks between consecutive $d_\\gamma$-spaced relays, a fallback such as re-sampling at finer resolution or local re-routing would be needed, which the paper does not address.","Because the method treats communication as intermittent and ignores bandwidth, extending it to permanent connectivity or streaming video would require adding capacity constraints and continuous link maintenance, likely changing the optimal ordering.","The heuristic comparison is empirical and scenario-specific; the 17-31 percent gains for concurrent deployment would likely shrink or reverse in maps where the base station sits at an extreme corner or where clusters are distributed unevenly, so the ordering rules may need tuning per environment.","One testable extension is to replace the fixed TSP/heuristic ordering with an online re-planning loop that recomputes visit order as robots move, exploiting the seconds-level computation time the paper reports."],"forward_implications":["For large teams (20 or 50 robots), concurrent relay-chain deployment reduces total mission time by about 17-31 percent compared with sequential deployment when the base station is centrally placed.","Relay and allocation computation stays in seconds even at the largest tested scale: relay-goal computation takes roughly 1.7-5.7 seconds and goal allocation 0.2-4.1 seconds for up to 50 robots and 500 goals.","Sequential ordering based only on distances between clusters (S1) is the most dependable sequential heuristic across base-station positions and goal counts.","The concurrent heuristics that extend chains one level at a time (LC) outperform those that push chains toward maximum primary-goal coverage (MP), which tend to cause oscillatory behavior."],"supporting_citations":[{"why":"Supplies the Fast Marching Method used to compute Voronoi paths and distance costs.","marker":"[14]"},{"why":"Defines the LoS communication model and the discretization baselines the paper compares against.","marker":"[1]"},{"why":"Benchmark for relay placement cost; the paper contrasts its seconds-level runtime with ILP-based exploration.","marker":"[11]"},{"why":"Cited for concurrent exploration with connectivity and bandwidth, motivating the paper's future-work direction and comparison.","marker":"[12]"},{"why":"The authors' earlier formulation that this work scales to larger robot and goal counts.","marker":"[13]"},{"why":"Establishes the orienteering problem baseline whose minutes-long solution times motivate the heuristics.","marker":"[15]"},{"why":"Provides the 2-opt local optimization used in the TSP-based cluster ordering.","marker":"[16]"}],"fun_headline_variants":["Relay-chain planner cuts multi-robot mission time by up to 31%","Concurrent deployment beats sequential by 31% in robot relay planning","Two-stage method: place relays, then schedule visits, for faster robot teams","Voronoi paths keep relays safe, concurrent visits save 31% in deployment","Scalable connectivity planner: relay clusters + parallel visits trim mission time"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The method assumes that sampling an obstacle-avoiding path every communication range $d_\\gamma$ yields consecutive relay positions that are actually within range and in line of sight of each other and of the path endpoints, with no proof or fallback given for paths that bend around obstacles.","fun_headline_variants_meta":{"raw":{"variants":["Relay-chain planner cuts multi-robot mission time by up to 31%","Concurrent deployment beats sequential by 31% in robot relay planning","Two-stage method: place relays, then schedule visits, for faster robot teams","Voronoi paths keep relays safe, concurrent visits save 31% in deployment","Scalable connectivity planner: relay clusters + parallel visits trim mission time"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000378,"raw_usage":{"total_tokens":1984,"prompt_tokens":891,"completion_tokens":1093,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":507,"completion_tokens_details":{"reasoning_tokens":994}},"tokens_in":507,"tokens_out":1093,"duration_ms":10543,"temperature":1.0,"reasoning_tokens":994,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T15:31:22.670585+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"In a map with a large obstacle that forces the Voronoi path to turn sharply, compute the relay chain by the paper's interval-$d_\\gamma$ sampling and check line-of-sight between consecutive relays and to the base station and maximum-connectivity point; if any pair fails, that cluster's goals cannot be connected, so the method's coverage guarantee for that scenario fails.","supporting_citations":[{"cited_title":"A fast marching level set method for monotonically advancing fronts,","cited_arxiv_id":null,"evidence_quote":"Supplies the Fast Marching Method used to compute Voronoi paths and distance costs."},{"cited_title":"Visibility-based deployment of robot formations for communication maintenance,","cited_arxiv_id":null,"evidence_quote":"Defines the LoS communication model and the discretization baselines the paper compares against."},{"cited_title":"Asynchronous multirobot exploration under recurrent connectivity con- straints,","cited_arxiv_id":null,"evidence_quote":"Benchmark for relay placement cost; the paper contrasts its seconds-level runtime with ILP-based exploration."},{"cited_title":"Coordinated multi-robot real-time exploration with connec- tivity and bandwidth awareness,","cited_arxiv_id":null,"evidence_quote":"Cited for concurrent exploration with connectivity and bandwidth, motivating the paper's future-work direction and comparison."},{"cited_title":"Communication-aware planning for robot teams deployment,","cited_arxiv_id":null,"evidence_quote":"The authors' earlier formulation that this work scales to larger robot and goal counts."},{"cited_title":"The orienteering problem: A survey,","cited_arxiv_id":null,"evidence_quote":"Establishes the orienteering problem baseline whose minutes-long solution times motivate the heuristics."},{"cited_title":"A method for solving traveling- salesman problems,","cited_arxiv_id":null,"evidence_quote":"Provides the 2-opt local optimization used in the TSP-based cluster ordering."}],"review_version":1}