Pith. sign in

REVIEW 5 major objections 4 minor 25 references

Evacuation of equilateral triangles by mobile agents of limited communication range

T0 review · 5 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Adding O(1/r) relay agents makes triangle evacuation time optimal.

desk verdict A plausible extension of evacuation theory to limited communication range, but the central optimal-time theorem is currently a sketch rather than a proof. read the letter →

arxiv 1908.07315 v1 pith:CWP3S62Y submitted 2019-08-20 cs.DC cs.DScs.MA

Iman Bagheri , Lata Narayanan , Jaroslav Opatrny This is my paper · ORCID
classification cs.DCcs.DScs.MA
keywords evacuationproblemmobileagentslimitedcommunicationrangeequilateraltrianglerelaynetworkoptimaltimeperimetersearchlowerbound
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

5 major / 4 minor

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.

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 (5)
  1. [Theorem 5.2, Figure 14] 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.
  2. [Theorem 5.1] 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.
  3. [Lemmas 3.11–3.13, Theorem 3.3] 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.
  4. [Tables 1 and 2, Section 3.2.2] 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.
  5. [Section 4, Tables 3] 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.
minor comments (4)
  1. [Abstract and Section 1.1] 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.
  2. [Theorem 5.2, Figure 14] 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.
  3. [Lemma 3.8] 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.
  4. [Lemma 3.1] 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.

Circularity Check

0 steps flagged · score 1.0 of 10

No circularity found: the central upper bounds are independent constructions, and the relay-schedule gap in Theorem 5.2 is a proof omission rather than a circular reduction.

full rationale

The paper's main new results for 0 < r < 1 are derived from explicit trajectories, critical-point analyses, and parameter balancing, not from fitting the claimed answer. For example, the two-agent algorithms in Section 3 optimize detour lengths by equating worst-case times t1 = t2, and the X3C/X1C analyses in Section 4 solve trajectory equations to minimize worst-case evacuation time. The optimal-time claim in Theorem 5.2 does rest on the lower bound 1 + 2y imported from the authors' prior wireless-model paper [14], which is a self-citation, but that citation supplies an external baseline result rather than this paper's own definition or fitted parameter. Theorem 5.1's lower bound and Theorem 5.2's agent count k = 6 + 2ceil(1/r − 1) both follow from the elementary spacing requirement that a communication chain of length 1 with range r needs about 1/r agents; this is the tradeoff being proved, not a self-fulfilling construction. The genuine weakness in Theorem 5.2 is that the proof only asserts that the relay agents 'can perform the relay function' and 'are also able to reach the exit when it is found within the bound 1 + 2y' without giving their trajectories, speeds, or a connectivity argument. That is an omitted proof and a correctness risk, not circular reasoning: no equation in the paper reduces the conclusion to an input by construction, no parameter is renamed as a prediction, and the same-author citations are used as baselines, not as an unverified uniqueness theorem that forces the result. The paper is therefore substantially self-contained against external benchmarks, with only minor reliance on prior same-author results for baseline cases.

Assumptions & free parameters 2 free parameters · 4 assumptions · 0 invented entities

The paper introduces no new physical or mathematical entities; it only reuses standard geometric and algorithmic structures. The main dependence is on prior results and on numerical optimization without exposed code.

free parameters (2)
  • Detour geometry parameter |BQ1| = varies with r; examples in Table 2, e.g., threshold at r≈0.7374 gives |BQ1|≈0.18435
    The 1-Detour and 2-Detour algorithms' evacuation times are derived after optimizing Q1 (and related points) by equating t1 and t2; the paper gives no closed-form solution and no code, only computed values.
  • X3C segment and meeting-point positions = computed per r via Maple from equal-time equations
    The X3C algorithm's claimed times in Table 3 depend on solving a system of nonlinear equations numerically; no coordinates are given.
assumptions (4)
  • domain assumption Lemma 3.1 from [6] (Brandt et al.) characterizing critical points on two search lines.
    Used in Lemmas 3.2-3.8 to identify where worst-case exit placement occurs; proof is not reproduced.
  • domain assumption Observation 1 from [9] linking unvisited boundary points to a lower bound of 1+4y.
    Used in lower-bound proof of Theorem 3.3 and Lemma 3.12; accepted from prior face-to-face model work.
  • domain assumption Lower bound of 1+2y on evacuation time for any r from [14]/[15].
    Used in Section 5 to establish optimality of CXP; the citation [14] is an in-preparation extended version.
  • domain assumption Agents are non-faulty and can always exchange information when within distance r.
    This is the core model assumption defining the communication capability, stated in Section 2.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Evacuation of equilateral triangles by mobile agents of limited communication range." pith.science (2026). https://pith.science/paper/CWP3S62Y

@misc{pith2026190807315,
  author       = {Pith},
  title        = {Pith review of: Evacuation of equilateral triangles by mobile agents of limited communication range},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/CWP3S62Y}},
  note         = {Machine review of arXiv:1908.07315}
}
abstract

We consider the problem of evacuating $k \geq 2$ mobile agents from a unit-sided equilateral triangle through an exit located at an unknown location on the perimeter of the triangle. The agents are initially located at the centroid of the triangle and they can communicate with other agents at distance at most $r$ with $0\leq r \leq 1$. An agent can move at speed at most one, and finds the exit only when it reaches the point where the exit is located. The agents can collaborate in the search for the exit. The goal of the {\em evacuation problem} is to minimize the evacuation time, defined as the worst-case time for {\em all} the agents to reach the exit. We propose and analyze several algorithms for the problem of evacuation by $k \geq 2$ agents; our results indicate that the best strategy to be used varies depending on the values of $r$ and $k$. For two agents, we give three algorithms, each of which achieves the best performance for different sub-ranges of $r$ in the range $0 \leq r \leq 1$. Finally, we show that for any $r$, evacuation of $k=6 +2\lceil(\frac{1}{r}-1)\rceil$ agents can be done in time $1+\sqrt{3}/3$, which is optimal in terms of time, and asymptotically optimal in terms of the number of agents.

Figures

Figures reproduced from arXiv: 1908.07315 by the authors.

Figure 1
Figure 1. Equilateral triangle T. agents in the wireless model was considered in [14], and in the face-to-face communication model in [9]. We should also mention the work on polygons [19], evacuation of circle with faulty agents [12], and the case of multiple exits on a circle [10, 25]. The evacuation problem is related to many other problems that have been considered previously. It can be seen as a variation of a search prob… view at source ↗
Figure 2
Figure 2. No-Detour algorithm R1 N Q L 1 2L R 2 S γ β [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. Illustration for Lemma 3.1. A B M C O S1 S2 W1 W2 N Q (a) Exit is located on segment MC A B M C O S1 S2 W1 W2 N Q (b) Exit is located on segment CS2 [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗
Figures from the paper (9 more)
Figure 4
Figure 4. Figure 4: Trajectories of agents based on the position of the exit point. [PITH_FULL_IMAGE:figures/full_fig_p007_4.png]
Figure 5
Figure 5. Figure 5: 1-Detour algorithm Lemma 3.4 If the exit is located at some point N on segment MC, then R1 will be r￾intercepted at or prior to reaching J1. Proof. (See Figure 6a) If the exit is located at C then, by the choice of J1, agent R1 will be r-intercepted at point J1. Hence …
Figure 6
Figure 6. Figure 6: Trajectories in One -Detour algorithm, and trajectories of agents based on the [PITH_FULL_IMAGE:figures/full_fig_p010_6.png]
Figure 7
Figure 7. Figure 7: 2-Detour algorithm solving that equation we get the values of 0.1843512042 and 0.7374048168 for |BQ1| and r respectively. If we increase r, we get negative value for |Q1J1| which is invalid. ✷ 3.2.3 The 2-Detour Algorithm: It is shown in [9], that for r = 0, i.e., the …
Figure 8
Figure 8. Figure 8: Modified Meeting Lemma Lemma 3.10 (Generalized Meeting Lemma) Assume that p1, p2 ∈ T and they have oppo￾site positions, e.g. points M3 and C in [PITH_FULL_IMAGE:figures/full_fig_p013_8.png]
Figure 9
Figure 9. Figure 9: Illustration of (a) possible trajectories of [PITH_FULL_IMAGE:figures/full_fig_p016_9.png]
Figure 10
Figure 10. Figure 10: Trajectories when R2 visits B before M3 and R1 visits M1 before C r Ev. Time Ev. Time Ev. Time Lower bound of No-Detour of 1-Detour of 2-Detour Th. 3.3 0.10 2.25424 2.27422 2.53867 2.0547 0.20 2.18584 2.19427 2.36010 2.0447 0.30 2.12325 2.12651 2.22617 2.0347 0.40 2.0…
Figure 11
Figure 11. Figure 11: Comparison of evacuation time of 2 agents with transmission range of [PITH_FULL_IMAGE:figures/full_fig_p018_11.png]
Figure 14
Figure 14. Figure 14: Trajectories of k agents for k = 12, where 6 agents (red) are exploring, and the remaining agents form a relay network. Case2, 1/3 ≤ r < 0.6436493404: In this case, since |P1P2| > r, when R2 and R3 reach points P1 and P2, they have to move toward each other to be in c…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

25 extracted references · 25 canonical work pages

  1. [9]

    Chuangpishit, S

    H. Chuangpishit, S. Mehrabi, L. Narayanan, and J. Opatrny. Evacuating an equilateral triangle in the face-to-face model. In Proceedings of OPODIS 2017 , pages 11:1–11:16, 2017

    work page 2017

  2. [14]

    Czyzowicz, E

    J. Czyzowicz, E. Kranakis, D. Krizanc, L. Narayanan, J. Opatrny, and S. Shende. Wireless autonomous robot evacuation from equilateral triangles and squares, extended version, in preparation. pages 181–194

    work page

  3. [1]

    Agmon and D

    N. Agmon and D. Peleg. Fault-tolerant gathering algorithms for autonomous mobile robots. SIAM Journal on Computing , 36(1):56–82, 2006

    work page 2006

  4. [2]

    Baeza Yates, J

    R. Baeza Yates, J. Culberson, and G. Rawlins. Searching in the plane. Information and Computation, 106(2):234–252, 1993

    work page 1993

  5. [3]

    A. Beck. On the linear search problem. Israel Journal of Mathematics, 2(4):221–228, 1964

    work page 1964

  6. [4]

    Beck and D

    A. Beck and D. Newman. Yet more on the linear search problem. Israel J. of Mathematics, 8(4):419–429, 1970

    work page 1970

  7. [5]

    Bonato and R

    A. Bonato and R. Nowakowski. The Game of Cops and Robbers on Graphs . American Mathematical Society, 2011

    work page 2011

  8. [6]

    Brandt, F

    S. Brandt, F. Laufenberg, Y. Lv, D. Stolz, and R. Wattenhofer. Collaboration without communication: Evacuating two robots from a disk. In Proceedings of CIAC 2017, LNCS, volume 10236, pages 104–115, 2017. 24

    work page 2017

Show all 25 references
  1. [7]

    Brandt, J

    S. Brandt, J. Uitto, and R. Wattenhofer. A Tight Bound for Semi-Synchronous Collabo- rative Grid Explorat ion. In 32nd International Symposium on Distributed Computing ( DISC), 2018

    2018

  2. [8]

    Chrobak, L

    M. Chrobak, L. Gasieniec, Gorry T., and R. Martin. Group search on the line. In SOFSEM

  3. [10]

    Czyzowicz, S

    J. Czyzowicz, S. Dobrev, K. Georgiou, E. Kranakis, and F. MacQuarrie. Evacuating two robots from multiple unknown exits in a circle. Theor. Comput. Sci. , 709:20–30, 2018

    2018

  4. [11]

    Czyzowicz, L

    J. Czyzowicz, L. Gasieniec, T. Gorry, E. Kranakis, R. Martin, and D. Pajak. Evacuating robots from an unknown exit located on the perimeter of a disc. In Proceedings DISC, Austin, Texas, pages 122–136. Springer, 2014

    2014

  5. [12]

    Czyzowicz, K

    J. Czyzowicz, K. Georgiou, E. Kranakis, L. Narayanan, J. Opatrny, and B. Vogtenhuber. Evacuating robots from a disc using face to face communication. In Proceedings of CIAC 2015, LNCS, volume 9079, pages 140–152, 2015

    2015

  6. [13]

    Czyzowicz, E

    J. Czyzowicz, E. Kranakis, D. Krizanc, L. Narayanan, and Opatrny J. Search on a line with faulty robots. In proceedings of PODC, pages 405–413. ACM, 2016

    2016

  7. [15]

    Czyzowicz, E

    J. Czyzowicz, E. Kranakis, K. Krizanc, L. Narayanan, J. Opatrny, and S. Shende. Wireless autonomous robot evacuation from equilateral triangles and squares. In ADHOCNOW. Springer, 2015

    2015

  8. [16]

    E. D. Demaine, S. P. Fekete, and S. Gal. Online searching with turn cost. Theoretical Computer Science, 361(2):342–355, 2006

    2006

  9. [17]

    Dieudonn´ e, A

    Y. Dieudonn´ e, A. Pelc, and D. Peleg. Gathering despite mischief. ACM Transactions on Algorithms (TALG), 11(1):1, 2014

    2014

  10. [18]

    Y. Emek, T. Langner, D. Stolz, J. Uitto, and R. Wattenhofer. How many ants does it take to find the food? Theor. Comput. Sci. , 608:255–267, 2015

    2015

  11. [19]

    Fekete, C

    S. Fekete, C. Gray, and A. Kr¨ oller. Evacuation of rectilinear polygons. In Combinatorial Optimization and Applications , pages 21–30. Springer, 2010

    2010

  12. [20]

    Flocchini, G

    P. Flocchini, G. Prencipe, and N. Santoro. Distributed computing by oblivious mobile robots (Synthesis Lectures on Distributed Computing Theory) . Morgan & Claypool Publishers, 2016

    2016

  13. [21]

    Flocchini, G

    P. Flocchini, G. Prencipe, N. Santoro, and P. Widmayer. Arbitrary pattern formation by asynchronous, anonymous, oblivious robots. Theoretical Computer Science, 407(1–3):412– 447, 2008. 25

    2008

  14. [22]

    Fraigniaud, D

    P. Fraigniaud, D. Ilcinkas, G. Peer, A. Pelc, and D. Peleg. Graph Exploration by a Finite Automaton. Theoretical Computer Science, 345(2-3):331–344, 2005

    2005

  15. [23]

    M.-Y. Kao, J. H. Reif, and S. R. Tate. Searching in an unknown environment: An optimal randomized algorithm for the cow-path problem. Information and Computation , 131(1):63–79, 1996

    1996

  16. [24]

    Koutsoupias, C

    E. Koutsoupias, C. Papadimitriou, and M. Yannakakis. Searching a fixed graph. In ICALP 96, pages 280–289. Springer, 1996

    1996

  17. [25]

    Pattanayak, H

    D. Pattanayak, H. Ramesh, P.S. Mandal, and S. Schmid. Evacuating two robots from two unknown exits on the perimeter of a disk with wireless communication. In Proceedings of ICDCN 2018, pages 20:1–20:4, 2018. 26

    2018

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.