{"id":"514ae57f-a8c3-44fc-b725-2e31b2d87f47","arxiv_id":"1908.07315","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"For 0<r<1, the paper gives new evacuation algorithms for 2, 3, 4 agents and proves that 6+2⌈(1/r−1)⌉ agents can evacuate an equilateral triangle in the optimal time 1+√3/3≈1.577.","lead":"This paper designs and analyzes search strategies for mobile agents with limited radio range seeking an exit on the perimeter of an equilateral triangle. It shows how adding agents can compensate for short communication range to reach the optimal evacuation time.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 5.2's optimal-time upper bound depends entirely on an unspecified relay-agent movement schedule; no trajectories, speeds, or connectivity argument are given for the 2i relay agents.","rationale":"The reader's weakest assumption and my concern coincide: Theorem 5.2 provides only a sketch of the relay-agent motion, and the entire optimal-time result rests on that sketch. The proof text explicitly says 'In this way the relay agents can perform the relay function' without demonstrating that the moving relays preserve connectivity or meet the evacuation deadline. This is an internal proof gap, not a disagreement with the literature. The surrounding material—the two-agent detour analysis and the X3C/X1C comparisons—is detailed and plausible, but it does not compensate for the missing core construction. The paper has no machine-checked proof and no reproducible simulation, so the central claim is conditional on the existence of the relay schedule. My proposed check (explicit construction for r=1/2 followed by simulation) would settle whether the gap is fillable. If the schedule exists, the theorem stands and the verdict can be upgraded; if not, the main contribution collapses. Hence I recommend keeping the conditional verdict, consistent with the reader's assessment.","tokens_in":19001,"tokens_out":5570,"duration_ms":58151,"concrete_test":"For the smallest nontrivial case r=1/2, k=8, explicitly construct the trajectories: give starting positions of the two relay agents on AB/AC, their piecewise-linear motion (with speeds ≤1) as exploring agents pass, and the timing of all messages; then verify by exhaustive simulation over the continuum of exit positions and discovery times that the relay network remains connected and every agent reaches the exit within 1+√3/3. If no such schedule exists, Theorem 5.2 is false; if it exists, extend the construction to r=1/3 (k=10) to confirm the scaling pattern.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The central claim is Theorem 5.2: for every r>0, k=6+2⌈(1/r−1)⌉ agents can evacuate in time 1+2y≈1.5773. The proof is one paragraph. After stating that '2i agents go to edges AB and AC into equidistant positions to form a relay network for the 6 agents doing the exploration,' it says only: 'When an exploring agent reaches a relay agent, the relay agent starts to move to its final position on the interior dashed triangle. In this way the relay agents can perform the relay function for the exploring agents, and are also able to reach the exit when it is found within the bound 1+2y.' No initial coordinates, movement times, speeds, or proof that the communication graph stays connected while relays move are supplied, and no worst-case analysis of relay evacuation distances is given. The claim that every relay can still reach the exit by 1+2y is nontrivial because a relay that leaves the perimeter may open a gap in the chain, and if the exit is found late (near time 2y+0.5), relays may be far from the exit. The lower bound in Theorem 5.1 is also asserted with a static-chain argument that ignores the possibility of agents moving toward each other before communication, but the main load-bearing gap is the unproven relay schedule in Theorem 5.2. Since no formal verification or simulation is provided, the optimal-time result is currently unsupported.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies evacuation of k mobile agents from the centroid of a unit-sided equilateral triangle when the exit is at an unknown perimeter point and agents have communication range r. It proposes and analyzes two-agent algorithms (No-Detour, 1-Detour, 2-Detour), explores X3C and X1C strategies for three and four agents, and gives a CXP strategy for larger k. The central claim is that for every r>0, k=6+2⌈(1/r−1)⌉ agents can evacuate in time 1+2y≈1.5773, which matches the lower bound of [14] and is asymptotically optimal in the number of agents. The paper also claims a lower bound for two agents and reports numerical comparisons showing which strategy is best for which ranges of r.","tokens_in":19336,"tokens_out":13096,"duration_ms":128385,"significance":"If the central claim is correct, the paper establishes a clean tradeoff: O(1/r) additional agents can compensate for an arbitrarily small communication radius, and the optimal wireless-model evacuation time remains achievable. The two-agent upper-bound analysis is detailed and identifies critical points explicitly, and the paper makes falsifiable numerical predictions in Tables 1–3. However, the main optimal-time theorem is currently a one-paragraph sketch, the numerical sections are not reproducible from the text, and some lower-bound lemmas are imported from the r=0 setting without adaptation. The significance is therefore conditional on substantial additional proof.","major_comments":[{"comment":"The proof of Theorem 5.2 does not specify the initial coordinates of the 2i relay agents, the times at which they leave the perimeter, their trajectories or speed schedules, or a connectivity invariant during the transition to the interior dashed triangle. The assertion that the relay agents 'can perform the relay function for the exploring agents, and are also able to reach the exit when it is found within the bound 1+2y' is therefore unsupported. In particular, if the exit is found near time 2y+0.5, a relay that has left its perimeter position may open a gap in the communication chain, and no bound is given on the distance from that relay to the exit. The sentence claiming that other exploration agents are at distance at most 1−t from the finder is also not justified for agents on an adjacent side when t>1/3, since the perimeter distance between those agents can be 2t. The proof must supply explicit trajectories, worst-case relay-to-exit distances, and a connectivity argument.","section":"Theorem 5.2, Figure 14"},{"comment":"The lower-bound proof assumes that the first vertex must be reached at exactly t=2y and that another agent must already be at B or C with an instant communication chain, but it does not rule out schedules in which the exit is found later and the other agents have positioned themselves to reach it quickly. The step claiming that 'an additional 1/r−1 agents are needed' also ignores the ceiling and the exact geometric placement of relay agents along the side, and the total count 1/r+1 is asserted rather than derived. As written, the claimed Ω(1/r) lower bound on the number of agents is not established.","section":"Theorem 5.1"},{"comment":"Lemmas 3.11 and 3.13 are dismissed with 'Identical to the proof of Lemma 5/7 in [9]', but the proof setting here has r>0, whereas [9] treats r=0. The generalized meeting lemma changes the timing inequalities, and the r-interception geometry on which the original lemmas rely is different for positive r. Since these lemmas are load-bearing for the two-agent lower bound of Theorem 3.3, the manuscript does not currently provide a complete proof of that lower bound.","section":"Lemmas 3.11–3.13, Theorem 3.3"},{"comment":"The numerical tables are internally inconsistent with the stated formulas and text. For r=0.1, Theorem 3.1 gives E_No-Detour = y+0.5+0.1+2(0.99)/1.2 ≈ 2.5387, yet Table 2 lists 2.25424 as the No-Detour time and 2.53867 as the 2-Detour time. Moreover, Table 2 shows the 1-Detour time as larger than the No-Detour time for every listed r, which contradicts the text assertion in Section 3.2.2 that the 1-Detour algorithm improves on No-Detour for 0<r<0.7. These discrepancies make the claimed two-agent algorithm comparisons unverifiable and need to be corrected.","section":"Tables 1 and 2, Section 3.2.2"},{"comment":"The X3C and X1C results for three and four agents are reported only as decimal values obtained by solving equations with Maple; no derivations, closed-form expressions, or code are provided, so the reader cannot verify the crossover points such as r≈0.22589 for three agents and r≈0.1721 for four agents. In addition, Section 4.4 asserts that 'it is very critical for R2 to reach point P3 before R1 does' without a proof, and this assertion underpins the X3C four-agent evacuation-time calculation. The numerical claims in Tables 3 should either be accompanied by explicit formulas or by reproducible code and formal verification.","section":"Section 4, Tables 3"}],"minor_comments":[{"comment":"The abstract states the two-agent lower bound applies for r<0.336, while Section 1.1 and Section 3.3 give r<0.366; these should be reconciled.","section":"Abstract and Section 1.1"},{"comment":"Figure 14 is referenced in the proof of Theorem 5.2, but no figure appears in the manuscript; since the proof relies on the figure, it should be included.","section":"Theorem 5.2, Figure 14"},{"comment":"The proof of Lemma 3.8 contains an incomplete sentence: 'the angle β is between Then we get 2cos(β)+cos(γ) = ...' The missing phrase should be supplied.","section":"Lemma 3.8"},{"comment":"Lemma 3.1 is called a 'simple generalization' of Theorem 1 in [6], but its proof is omitted with only 'See [6]'; because the manuscript uses this lemma repeatedly, a self-contained proof or a precise statement of the generalization should be included.","section":"Lemma 3.1"}],"recommendation":"major_revision","confidential_remarks":"The paper's headline theorem is currently a sketch, the key figure is missing, and the numerical comparisons are not reproducible. I recommend a major revision rather than rejection because the core idea may be salvageable: the main theorem needs a full relay-movement schedule and connectivity analysis, and the lower-bound and numerical claims need to be either proved or clearly delimited as experimental. The inconsistencies in Tables 1 and 2 should be resolved before the paper is reconsidered."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: send it to a serious referee, but tell the authors that Theorem 5.2 needs real work before the main claim can stand. The limited-range communication model is a genuine addition to the evacuation literature, and the 2-agent analysis is mostly solid, but the paper's headline result about O(1/r) agents is supported by a few sentences, not a proof.\n\nWhat's actually new: the paper interpolates between the known face-to-face (r=0) and wireless (r=1) cases for 0<r<1. The three 2-agent algorithms (No-Detour, 1-Detour, 2-Detour) give a clean tradeoff between detour complexity and communication range, and the X3C/X1C comparison for 3 and 4 agents is a reasonable first map of the strategy space. The high-level insight that a relay chain of O(1/r) agents can recover the optimal wireless evacuation time of 1+2y is interesting and plausible.\n\nWhere it gets soft: Theorem 5.2, the main optimal-time upper bound, is proven in one paragraph. It asserts that the 2i relay agents move from their initial positions to an interior dashed triangle and 'perform the relay function' without specifying trajectories, speeds, or connectivity maintenance. That is not a proof; it is a research plan. The lower bound in Theorem 5.1 is similarly loose: 'for this communication to happen, an additional 1/r−1 agents are needed' ignores the possibility that agents move toward each other during the search, so the asymptotic lower bound is not established either. The X3C/X1C numeric comparisons come from Maple with no formal crossing analysis, but that is a minor issue since the equations are there for a reader to verify. The Generalized Meeting Lemma for two agents looks correct, and the reliance on 'identical to [9]' for two sublemmas is acceptable.\n\nBottom line: worth a serious referee. The model and the 2-agent results deserve publication if the authors either prove Theorem 5.2 properly or downgrade it to a conjecture. As written, the advertised optimal-time claim is unsupported, and a referee should ask for a full analysis of the CXP relay schedule, including worst-case evacuation times for relay agents, before accepting it.","headline":"A plausible extension of evacuation theory to limited communication range, but the central optimal-time theorem is currently a sketch rather than a proof.","tokens_in":19844,"tokens_out":2308,"would_cite":true,"duration_ms":22536,"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":"Adding O(1/r) relay agents makes triangle evacuation time optimal.","keywords":["evacuation problem","mobile agents","limited communication range","equilateral triangle","relay network","optimal evacuation time","perimeter search","lower bound"],"falsifier":"For r = 1/2, write down explicit trajectories for eight agents under CXP and check the worst-case exit position by direct calculation or simulation: if some relay agent cannot both preserve connectivity and reach the exit by time 1 + 2y ≈ 1.5773 for every possible exit on the perimeter, then Theorem 5.2 is false. A smaller symbolic check is to solve for the relay positions after each explorer passes them and verify the information-propagation deadline at the last relay.","tokens_in":18833,"feed_emoji":"📡","tokens_out":8172,"duration_ms":84742,"temperature":0.7,"pith_summary":"This paper asks how many robots with a short communication range r need to search a unit equilateral triangle for an exit on its perimeter, starting from the centroid. Its central claim is that a limited communication range does not have to raise the worst-case evacuation time once enough agents are available: with k = 6 + 2⌈(1/r − 1)⌉ agents, a connected relay-chain strategy reaches the same optimal time 1 + √3/3 ≈ 1.5773 that six agents achieve with unlimited range. The paper also proves that at least 1/r + 1 agents are necessary to attain that optimal time, so the construction is asymptotically optimal in the number of agents. For two, three, and four agents, it gives algorithms whose best choice depends on r.","feed_headline":"Adding O(1/r) relay agents makes evacuation time optimal","feed_subtitle":"A relay chain of agents lets short-range radios match the wireless lower bound of 1.5773.","key_machinery":"The load-bearing construction is the Connected Exploration of Perimeter (CXP) strategy with its relay network. Six exploring agents start at the centroid, two per vertex, and sweep the three sides from the vertices to the midpoints; the remaining 2⌈(1/r − 1)⌉ agents are placed at equally spaced positions along two sides and then move to an inner triangle when an explorer reaches them, so that the exploring group stays connected. The parameter i = ⌈(1/r − 1)⌉ sets the number of relay agents per side; one relay is needed for each unit of distance by which the sweep can outpace the radio range, and the relay movement is what converts a perimeter discovery into a message that reaches every agent in time to join the exit run.","core_discovery":"The paper's central discovery is that a single unknown exit on a triangle can be found and all agents brought to it in the absolute lower bound time 1 + 2y = 1 + √3/3 for any positive communication range r, provided the agent count grows like 1/r. In the CXP strategy, six exploring agents move from the centroid to the vertices in pairs and sweep each side toward its midpoint, while 2⌈(1/r − 1)⌉ relay agents take equally spaced positions along two sides and then move inward to an interior triangle, keeping the exploring agents within communication range. The relay spacing is chosen so that a sweep of each half-side can be relayed in time, and the whole schedule finishes by 1 + 2y. The matching lower bound argues that to finish in exactly 1 + 2y, information found at one vertex must reach the first agent at another vertex quickly enough, which forces at least 1/r + 1 agents; hence the relay construction is tight up to constants.","pith_inferences":["A natural next question, which the paper does not answer, is the exact minimum number of agents for optimal time; the gap between the 1/r + 1 lower bound and the 6 + 2⌈(1/r − 1)⌉ construction leaves room for improvement.","The relay-chain idea should transfer to other regions whose wireless-optimal evacuation is known, such as squares or other convex polygons, giving O(1/r)-agent constructions with a similar constant-factor trade-off.","Because the lower bound 1/r + 1 applies only to the exact optimal time 1 + 2y, allowing a small slack ε might permit a constant number of agents to come within ε of optimal; whether this is possible is left open."],"forward_implications":["For any fixed r > 0, optimal-time evacuation is achievable with finitely many agents; in particular, k = 8 agents suffice for r = 1/2, k = 10 for r = 1/3, and k = 12 for r = 1/4.","The trade-off between communication range and team size is tight up to constants: the paper's agent count is O(1/r), and its lower bound is Ω(1/r), so no strategy using asymptotically fewer agents can match the optimal time.","For small teams, the best strategy depends on the radio range: two agents should use no detours for r > 0.737, one detour for intermediate r, and two detours for small r; for three or four agents, X3C wins for small r and X1C for larger r.","The paper's algorithms reduce at the endpoints to the known face-to-face and wireless evacuation algorithms, so the limited-range results bridge the two previously studied communication models."],"supporting_citations":[{"why":"Supplies the lower bound 1 + 2y on evacuation time for any number of agents and the six-agent wireless construction that the CXP strategy extends to limited range.","marker":"[14]"},{"why":"Defines the wireless evacuation model for triangles and squares and gives the no-detour two-agent trajectory used as a benchmark in the two-agent analysis.","marker":"[15]"},{"why":"Provides the face-to-face (r = 0) evacuation algorithms with detours and the meeting-lemma lower-bound method that the two-agent results adapt to r > 0.","marker":"[9]"},{"why":"Provides the angle-based lemma used to locate worst-case exit points in the two-agent evacuation-time analysis.","marker":"[6]"}],"fun_headline_variants":["Relay agents hit optimal evacuation time","Optimal escape with O(1/r) relay agents","Short-range radios, optimal triangle evacuation","Relay chain makes evacuation time optimal"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The central theorem's proof assumes that the 2i relay agents can move from their initial equally spaced perimeter positions to the interior triangle while keeping the exploring agents connected and still reach any discovered exit within the same 1 + 2y deadline, but no explicit paths, timings, or speed schedule for those relay movements are given.","fun_headline_variants_meta":{"raw":{"variants":["Relay agents hit optimal evacuation time","Optimal escape with O(1/r) relay agents","Short-range radios, optimal triangle evacuation","Relay chain makes evacuation time optimal"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000756,"raw_usage":{"total_tokens":3398,"prompt_tokens":1018,"completion_tokens":2380,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":634,"completion_tokens_details":{"reasoning_tokens":2325}},"tokens_in":634,"tokens_out":2380,"duration_ms":19711,"temperature":1.0,"reasoning_tokens":2325,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T12:20:10.547983+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For r = 1/2, write down explicit trajectories for eight agents under CXP and check the worst-case exit position by direct calculation or simulation: if some relay agent cannot both preserve connectivity and reach the exit by time 1 + 2y ≈ 1.5773 for every possible exit on the perimeter, then Theorem 5.2 is false. A smaller symbolic check is to solve for the relay positions after each explorer passes them and verify the information-propagation deadline at the last relay.","supporting_citations":[{"cited_title":"Czyzowicz, E","cited_arxiv_id":null,"evidence_quote":"Supplies the lower bound 1 + 2y on evacuation time for any number of agents and the six-agent wireless construction that the CXP strategy extends to limited range."},{"cited_title":"Czyzowicz, E","cited_arxiv_id":null,"evidence_quote":"Defines the wireless evacuation model for triangles and squares and gives the no-detour two-agent trajectory used as a benchmark in the two-agent analysis."},{"cited_title":"Chuangpishit, S","cited_arxiv_id":null,"evidence_quote":"Provides the face-to-face (r = 0) evacuation algorithms with detours and the meeting-lemma lower-bound method that the two-agent results adapt to r > 0."},{"cited_title":"Brandt, F","cited_arxiv_id":null,"evidence_quote":"Provides the angle-based lemma used to locate worst-case exit points in the two-agent evacuation-time analysis."}],"review_version":1}