Paper deep dive
Connectivity Preservation and Graph Stretching in Range-Only Swarm Dispersion
Ariel Barel
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 92%
Last extracted: 9/24/2026, 3:52:39 AM
Summary
This paper presents a connectivity-preserving dispersion protocol for anonymous, identical, and oblivious agents using only range-only sensing. The proposed rule moves each agent by half the remaining visibility margin in a random direction, ensuring that all existing visibility edges are preserved. Theoretical analysis proves edge preservation, boundary locking, and almost-sure convergence for two-agent systems. Monte Carlo simulations validate these findings and demonstrate topology-dependent stretching in larger swarms.
Entities (6)
Relation Signals (5)
Range-Only Swarm Dispersion → preserves → Visibility Graph
confidence 96% · The rule preserves every existing visibility edge under synchronous finite motion and therefore preserves connectivity.
Range-Only Swarm Dispersion → uses → Visibility Radius
confidence 95% · Each agent measures only the distances to its visible neighbors... The resulting rule requires only the distance to the farthest visible neighbor... moves by half of its remaining visibility margin.
Two-Agent System → exhibits → Almost-Sure Convergence
confidence 94% · For two agents, we prove positive conditional drift in squared distance, almost-sure convergence to the visibility boundary
Monte Carlo Experiment → validates → Range-Only Swarm Dispersion
confidence 90% · A one-million-run Monte Carlo experiment agrees with the exact first-round moments... For general swarms, 1,000 runs... reproduce the deterministic safety guarantee
Bellman Equation → validates → Range-Only Swarm Dispersion
confidence 88% · an independent Bellman-equation computation gives the same estimate.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:We study connectivity-preserving finite-jump dispersion of anonymous, identical, and oblivious agents under an idealized range-only sensing model. Each agent measures only the distances to its visible neighbors, without bearings, identifiers, communication, memory, or a shared coordinate system. We derive the largest isotropic displacement certifiable as safe from these measurements alone. The resulting rule requires only the distance to the farthest visible neighbor: each agent selects a random direction and moves by half of its remaining visibility margin. The rule preserves every existing visibility edge under synchronous finite motion and therefore preserves connectivity. For two agents, we prove positive conditional drift in squared distance, almost-sure convergence to the visibility boundary, and finite expected time to reach any fixed neighborhood of that boundary. A one-million-run Monte Carlo experiment agrees with the exact first-round moments and estimates approximately 9.5 rounds to reach distance 0.97V from coincident initial positions; an independent Bellman-equation computation gives the same estimate. For general swarms, 1,000 runs across five initial-topology classes reproduce the deterministic safety guarantee at implementation level and reveal a consistent topology-dependent ordering of attainable diameter under the tested protocol. These results provide a theoretical foundation for connectivity-preserving multi-robot dispersion under minimal sensing, while isolating the guarantees achievable from anonymous range measurements alone.
Tags
Links
- Source: https://arxiv.org/abs/2609.28190v1
- Canonical: https://arxiv.org/abs/2609.28190v1
Trouble viewing inline? Open PDF directly →
Full Text
38,083 characters extracted from source content.
Expand or collapse full text
Connectivity Preservation and Graph Stretching in Range-Only Swarm Dispersion Ariel Barel Affiliation: Faculty of Computer Science, Technion Israel Institute of Technology, Haifa, Israel. Email: arielba@technion.ac.il Abstract We study connectivity-preserving finite-jump dispersion of anonymous, identical, and oblivious agents under an idealized range-only sensing model. Each agent measures only the distances to its visible neighbors, without bearings, identifiers, communication, memory, or a shared coordinate system. We derive the largest isotropic displacement certifiable as safe from these measurements alone. The resulting rule requires only the distance to the farthest visible neighbor: each agent selects a random direction and moves by half of its remaining visibility margin. The rule preserves every existing visibility edge under synchronous finite motion and therefore preserves connectivity. For two agents, we prove positive conditional drift in squared distance, almost-sure convergence to the visibility boundary, and finite expected time to reach any fixed neighborhood of that boundary. A one-million-run Monte Carlo experiment agrees with the exact first-round moments and estimates approximately 9.59.5 rounds to reach distance 0.97V0.97V from coincident initial positions; an independent Bellman-equation computation gives the same estimate. For general swarms, 1,0001,000 runs across five initial-topology classes reproduce the deterministic safety guarantee at implementation level and reveal a consistent topology-dependent ordering of attainable diameter under the tested protocol. These results provide a theoretical foundation for connectivity-preserving multi-robot dispersion under minimal sensing, while isolating the guarantees achievable from anonymous range measurements alone. I Introduction Without directional information, a mobile agent cannot identify a direction away from a neighbor, reconstruct local geometry, or determine whether a visible edge is redundant for global connectivity. Under finite synchronous motion, losing one critical edge can disconnect a swarm. We study anonymous, identical, oblivious agents that know only the current distances to visible neighbors. Agents have no identifiers, memory, communication, compass, common coordinates, or bearings. We ask for the largest finite displacement certifiable from scalar ranges alone while preserving every current edge for every feasible bearing arrangement, and whether repeated maximal safe jumps create systematic stretching. Here, dispersion means increasing the spatial extent of the connected swarm and stretching preserved edges. It does not mean maximizing minimum pairwise distance; individual pairs may temporarily approach, and collisions are not modeled. If the farthest visible neighbor of agent i is at distance dimaxd_i and the visibility radius is V, our rule jumps (V−dimax)/2(V-d_i )/2 in an independent uniform direction. This is the largest bearing-independent isotropic displacement certifiable from current ranges. It preserves every current edge and hence connectivity. An edge at distance V permanently immobilizes both endpoints, and every absorbing configuration contains at least n/2n/2 boundary edges. Preserving every edge is stronger than preserving connectivity alone, but anonymous current ranges do not reveal which edges are globally redundant. Thus preserving a strict subset cannot be locally certified under the stated model. For two agents, squared distance has positive conditional drift below V, yielding almost-sure convergence and finite expected near-boundary hitting time. For larger swarms we provide a multi-run empirical topology study rather than a convergence claim. Our main contributions are as follows. • We derive the maximal isotropic displacement that can be certified using anonymous current range measurements. Although an agent can observe several ranges, the safe-action certificate depends only on the farthest one. • We prove deterministic preservation of every current visibility edge for arbitrary swarm size and every realization of the random directions. Connectivity preservation follows immediately for an initially connected swarm. • We prove exact locking at the visibility boundary and show that every absorbing configuration contains at least n/2n/2 boundary edges. • For two agents, we prove positive conditional drift in squared distance, almost-sure convergence to the visibility boundary, and finite expected time to reach every fixed boundary neighborhood. • We complement the analytical results with large-scale Monte Carlo validation, an independent Bellman computation of the near-boundary hitting time, and extensive empirical studies showing topology-dependent stretching across multiple swarm sizes and initial graph classes. The paper separates three levels of claim. The safety and structural results hold for arbitrary n. The stochastic convergence results are proved only for the analytically tractable two-agent system. For general coupled swarms, we make no convergence claim; the contribution is an empirical characterization of topology-dependent expansion and edge stretching. I Related Work Connectivity-preserving coordination commonly uses relative positions, interaction graphs, potential fields, or learned navigation policies. Ji and Egerstedt preserve connectedness of dynamic interaction graphs [1]. Zavlanos and Pappas use differentiable constraints and artificial potential fields [2]; Dimarogonas and Johansson propose bounded distributed connectivity control [3]; and Li et al. learn a decentralized navigation policy [4]. These approaches require relative positions, graph information, navigation functions, or a trained policy with richer observations. Ando et al. restrict pair destinations to a midpoint-centered disk [5], but locating the midpoint requires relative direction. Gordon et al. study bearing-only and crude near/far sensing [6, 7]; continuous-time bearing-only gathering appears in [8]. Flocchini et al. consider anonymous oblivious robots with limited visibility under asynchrony but assume orientation [9]. The broader geometric-consensus taxonomy surveyed in [10] considers the corresponding bearing-only setting but does not address range-only gathering, for which no solution under this severe sensing restriction was identified at the time. Recent work moves closer to scalar-distance sensing. Lee et al. use an ultrasonic tracker that supplies both range and bearing [11]. Brandstätter et al. use imperfect scalar distances, but each agent updates a directional-response model and uses state estimation and a target distance [12]. Chen et al. provide range-only safety-critical formation control, but reconstruct bearing relative to a landmark and use an estimator, control barrier functions, and a prescribed formation [13]. Yang et al. combine online communication learning with Gaussian processes, barrier functions, and bi-level optimization [14]. Manor et al. release redundant interactions using local geometry [15], which is unavailable here. The contribution is not the triangle inequality alone, but the maximality of the resulting action certificate under anonymous range-only information, its reduction to one scalar statistic, and the stochastic behavior induced by repeatedly exhausting that certificate. I Model and Motion Rule Let =1,…,nA=\1,…,n\, n≥2n≥ 2, and pi(t)∈ℝ2p_i(t) ^2. The visibility graph G(t)=(,E(t))G(t)=(A,E(t)) satisfies (i,j)∈E(t)⇔‖pi(t)−pj(t)‖≤V.(i,j)∈ E(t) \|p_i(t)-p_j(t)\|≤ V. (1) Define Ni(t)=j∈∖i:(i,j)∈E(t).N_i(t)=\j \i\:(i,j)∈ E(t)\. (2) We assume G(0)G(0) is connected. Each agent observes only the multiset of current ranges and need not associate measurements with persistent identities; it only computes the maximum. For a pair at distance d, the total margin is V−dV-d. In the worst case both agents jump directly apart, so each receives (V−d)/2(V-d)/2. Any larger common isotropic radius permits loss of the edge. Proposition 1 (Maximal isotropic range-only radius) For a visible pair at distance d, the largest common isotropic displacement radius that guarantees preservation of the edge for every feasible pair of bearings and synchronous moves is V−d2. V-d2. (3) Proof: Sufficiency follows from the triangle inequality. For maximality, let both agents use any radius r>(V−d)/2r>(V-d)/2 and consider the feasible motion in which they move directly away from one another. Their new distance is d+2r>Vd+2r>V, so the edge is lost. ∎ With several neighbors, the farthest is most restrictive: dimax(t) d_i (t) =maxj∈Ni(t)‖pi(t)−pj(t)‖, = _j∈ N_i(t)\|p_i(t)-p_j(t)\|, (4) ri(t) r_i(t) =V−dimax(t)2. = V-d_i (t)2. Corollary 1 (Agent allowable region) The complete isotropic range-only allowable region of agent i is ARi(t)=D(pi(t),V−dimax(t)2),AR_i(t)=D\! (p_i(t), V-d_i (t)2 ), (5) where D(p,r)D(p,r) denotes the closed disk of radius r centered at p. Hence the full multiset of current neighbor ranges reduces to the single statistic dimax(t)d_i (t). Proof: Each visible neighbor j induces a concentric safe disk of radius (V−dij(t))/2(V-d_ij(t))/2. Their intersection is the disk with the smallest radius. Since d↦(V−d)/2d (V-d)/2 is decreasing, this radius is induced by the farthest current neighbor. ∎ Agent i samples Ui(t)U_i(t) uniformly on the unit circle and updates pi(t+1)=pi(t)+ri(t)Ui(t).p_i(t+1)=p_i(t)+r_i(t)U_i(t). (6) The boundary is selected to exhaust the certified displacement budget. This does not imply that every pairwise distance rises in every round. Safety is provided by the radius, while the random direction explores the safe set without a bearing estimate. Since all pairwise safety disks are concentric at the agent, the complete current neighborhood reduces to the single scalar dimaxd_i . Let ℱtF_t denote the history immediately before round-t directions are sampled. I-A Information Use and Design Rationale The rule is deliberately minimal. It does not require neighborhood ordering, persistent measurement association, geometric reconstruction, or a target formation. All pairwise range-only safety disks are centered at the current agent, so their intersection is determined by the smallest radius, equivalently by the farthest measured neighbor range. Thus the full current range multiset reduces to one scalar statistic, dimax(t)d_i (t). Safety and dispersion are separated. The radius certifies that every possible direction is safe, while the random direction explores the safe set without reconstructing a bearing. Choosing the boundary uses the entire certified displacement budget. A random move can increase some neighbor distances and decrease others, but no current edge can be lost. The following analytical ablation makes the boundary choice precise. Proposition 2 (Step-length ablation) For ri(α)=α(V−dimax)/2r_i^(α)=α(V-d_i )/2, α∈[0,1]α∈[0,1], every α preserves all edges. For two agents, [Dt+12−Dt2∣ℱt]=α2(V−Dt)22.E[D_t+1^2-D_t^2 _t]= α^2(V-D_t)^22. (7) Thus α=1α=1 maximizes one-step expected squared-distance progress in this safe isotropic family. Proof: Safety follows from ri(α)≤rir_i^(α)≤ r_i. Scaling both movement vectors by α multiplies the quadratic drift term by α2α^2.∎ IV Safety and Structural Guarantees Theorem 1 (Edge preservation) For every t≥0t≥ 0, E(t)⊆E(t+1)E(t) E(t+1). Proof: For (i,j)∈E(t)(i,j)∈ E(t), write dij=‖pi−pj‖d_ij=\|p_i-p_j\|. Then ri,rj≤(V−dij)/2r_i,r_j≤(V-d_ij)/2, and ‖pi(t+1)−pj(t+1)‖≤dij+ri+rj≤V.\|p_i(t+1)-p_j(t+1)\|≤ d_ij+r_i+r_j≤ V. (8) ∎ Corollary 2 If G(0)G(0) is connected, then G(t)G(t) is connected for all t. Proof: Theorem 1 gives E(0)⊆E(t)E(0) E(t), so G(t)G(t) contains connected G(0)G(0) as a spanning subgraph.∎ The edge-preservation proof is independent of the distribution of the selected directions. Uniform random directions are used for the stretching analysis, not for safety. In particular, any direction-selection policy remains safe as long as each displacement respects the same certified radius. This modularity allows the range-only safety layer to be separated from future task-specific direction policies. Theorem 2 (Boundary locking) If ‖pi(t)−pj(t)‖=V\|p_i(t)-p_j(t)\|=V for some (i,j)∈E(t)(i,j)∈ E(t), then pi(s)=pi(t),pj(s)=pj(t)p_i(s)=p_i(t), p_j(s)=p_j(t) (9) for every s≥ts≥ t. Proof: Since (i,j)∈E(t)(i,j)∈ E(t) has length V, both endpoints have a visible neighbor at distance V. No visible-neighbor distance can exceed V, so dimax(t)=djmax(t)=V.d_i (t)=d_j (t)=V. (10) Equation (4) therefore gives ri(t)=rj(t)=0r_i(t)=r_j(t)=0. By the update rule (6), neither endpoint moves at round t. Their mutual distance consequently remains V, and the same argument applies recursively at every subsequent round. ∎ Definition 1 A configuration is absorbing if ri=0r_i=0 for every agent. Theorem 3 Every absorbing configuration contains at least n/2n/2 edges of length V. Proof: Let EV=(i,j)∈E:‖pi−pj‖=VE_V=\(i,j)∈ E:\|p_i-p_j\|=V\ (11) denote the set of visibility-boundary edges. In the graph (,EV)(A,E_V), every vertex has degree at least one. Hence 2|EV|=∑i=1ndegEV(i)≥n.2|E_V|= _i=1^n _E_V(i)≥ n. (12) ∎This is conditional on absorption and does not prove general-swarm convergence. It nevertheless shows that if the swarm fully immobilizes, stretching is structural rather than transient: every agent is incident to at least one visibility-boundary edge. Exact equality is a property of the idealized model; numerical implementations must treat a tolerance band separately. Boundary locking is irreversible in the ideal exact-arithmetic model. Once one incident edge reaches V, the corresponding agent has farthest-neighbor distance V and can no longer move. The lower bound on boundary edges is conditional on the system reaching an absorbing configuration, but it shows that complete immobilization necessarily contains a linear amount of exact edge stretching rather than merely a transient increase in diameter. In numerical implementations, near-boundary edges must be distinguished from exact locked edges because tolerance and finite precision can otherwise create apparent locking or unlocking events. V Two-Agent Stochastic Stretching Let Xt=p2(t)−p1(t)X_t=p_2(t)-p_1(t) and Dt=‖Xt‖D_t=\|X_t\|. Then Xt+1=Xt+V−Dt2(U2(t)−U1(t)).X_t+1=X_t+ V-D_t2(U_2(t)-U_1(t)). (13) Because Dt≤VD_t≤ V by edge preservation, the process remains in the compact interval [0,V][0,V]. The boundary V is absorbing, while the next distance below V depends only on the current relative displacement and two fresh independent directions. Rotational symmetry therefore reduces the stochastic state relevant to distance evolution to the scalar DtD_t. Lemma 1 (Positive drift) [Dt+12∣ℱt]=Dt2+(V−Dt)22.E[D_t+1^2 _t]=D_t^2+ (V-D_t)^22. (14) Proof: Conditioning on ℱtF_t and expanding the squared norm gives Dt+12 D_t+1^2 =Dt2+(V−Dt)⟨Xt,U2(t)−U1(t)⟩ =D_t^2+(V-D_t) X_t,U_2(t)-U_1(t) +(V−Dt)24‖U2(t)−U1(t)‖2. + (V-D_t)^24\|U_2(t)-U_1(t)\|^2. (15) Uniformity gives [Ui(t)]=0E[U_i(t)]=0, so the conditional expectation of the cross term vanishes. Independence gives [⟨U1(t),U2(t)⟩]=0E[ U_1(t),U_2(t) ]=0, and therefore [‖U2(t)−U1(t)‖2]=2,E[\|U_2(t)-U_1(t)\|^2]=2, (16) which yields the claim. ∎ Theorem 4 (Almost-sure convergence) For every D0∈[0,V]D_0∈[0,V], Dt→VD_t→ V almost surely. Proof: Summing (14) gives ∑t=0∞[(V−Dt)2]≤2(V2−D02)<∞. _t=0^∞E[(V-D_t)^2]≤ 2(V^2-D_0^2)<∞. (17) Markov’s inequality gives ∑tPr(V−Dt≥ε)<∞ _t (V-D_t≥ )<∞. Borel–Cantelli [16], applied to positive rational ε , proves convergence.∎ Proposition 3 (No finite exact hit) If D0<VD_0<V and the directions are continuously uniform, then Pr(τV<∞)=0,τV=inft≥0:Dt=V. ( _V<∞)=0, _V= \t≥ 0:D_t=V\. (18) Proof: Condition on ℱtF_t and Dt<VD_t<V. Equality at round t+1t+1 requires maximum relative-step magnitude and equality in the triangle inequality. For Xt≠0X_t≠ 0, the directions must be antipodal and aligned with the current separation line; for Xt=0X_t=0, antipodality is still required. These direction pairs form a measure-zero subset of 1×1S^1×S^1. A countable union over finite rounds proves the claim. ∎Hence the agents almost surely approach the boundary without hitting it exactly in finite time, and their allowable radii converge to zero. Let τε=inft:Dt≥V−ε _ = \t:D_t≥ V- \. Theorem 5 (Near-boundary hitting time) If D0=d0<V−εD_0=d_0<V- , then [τε∣D0=d0]≤2(V2−d02)ε2.E[ _ D_0=d_0]≤ 2(V^2-d_0^2) ^2. (19) Proof: Let σT=T∧τε _T=T _ . On t<τε\t< _ \, the agents still execute the original maximal safe jump of radius (V−Dt)/2(V-D_t)/2; the proof does not replace this radius by ε/2 /2. Since V−Dt>εV-D_t> before target entry, Lemma 1 gives conditional drift at least ε2/2 ^2/2. Summing the stopped drift yields [DσT2]−d02≥ε22[T∧τε].E[D_ _T^2]-d_0^2≥ ^22E[T _ ]. (20) Because DσT≤VD_ _T≤ V, [T∧τε]≤2(V2−d02)ε2.E[T _ ]≤ 2(V^2-d_0^2) ^2. (21) Letting T→∞T→∞ and applying monotone convergence proves the result. ∎The bound establishes finite expected hitting time but can be highly conservative because it discards the substantially larger drift obtained when DtD_t is far below V−εV- . For D0=0D_0=0, both agents initially move with radius V/2V/2. If Δ is the difference between their independent uniform directions, then D1=V|sin(Δ2)|.D_1=V | ( 2 ) |. (22) The two endpoints form a random chord of the radius-V/2V/2 circle. Direct integration gives [D1]=2V/π,[D12]=V2/2.E[D_1]=2V/π, [D_1^2]=V^2/2. (23) VI Experimental Evaluation The general-swarm study uses five N=10N=10 topology groups: complete, path, and sparse, medium, and dense random-connected graphs. Each has 200200 independent runs of 5,0005,000 rounds, totaling five million rounds. We record connectivity, edge changes, normalized diameter, and stretching of a fixed initial spanning tree. Diameter sensitivity uses 100100 runs per group for N=20N=20 and N=50N=50. We use V=50V=50. Complete configurations lie in a radius-1010 disk; paths use consecutive edges of length 0.9V0.9V. Random-connected candidates use sampling-disk radii 9090, 5555, and 4242, are retained only if connected, and are classified by initial edge density as sparse [0.05,0.35][0.05,0.35], medium [0.35,0.65][0.35,0.65], or dense [0.65,0.95][0.65,0.95]. The base seed is 72,010,00172,010,001. For general swarms, this is an empirical topology study rather than a convergence claim. The topology classes serve distinct purposes. Complete and path graphs are structural extremes: preserving every pairwise edge confines a complete graph to diameter V, whereas a path constrains only local consecutive separations. The three random-connected strata test whether the resulting geometry changes gradually with initial edge density rather than only between two hand-selected cases. The N=20N=20 and N=50N=50 experiments test whether the qualitative ordering persists beyond the main N=10N=10 setting. For every run, the identities of the edges in a fixed spanning tree of the initial visibility graph are retained and their lengths are tracked throughout the execution. Aggregate statistics include medians, interquartile ranges, and 55th–9595th percentile ranges. Time-series measurements are sampled every ten rounds. The same base seed and fixed group-specific offsets are used throughout. No edge or connectivity loss was observed, reproducing the deterministic guarantee at implementation level over five million rounds. This is an implementation check rather than independent evidence for the theorem. Beyond safety, the experiments quantify the geometric cost of preserving the initial constraints. Complete graphs remain confined to diameter V, whereas paths expand over many visibility ranges. For N=10N=10, median final diameters of dense, medium, and sparse random-connected groups are approximately 1.65V1.65V, 2.2V2.2V, and 3.6V3.6V. Diameter measures global expansion, while stretching of a fixed initial spanning tree measures deformation of an initially connectivity-sufficient structure. Fig. 1: Final normalized diameter for five N=10N=10 topology groups, 200200 runs per group. Fig. 2: Initial edge density versus final diameter and fixed-tree stretching for random-connected N=10N=10 swarms. Within the random-connected family, greater initial density is associated with smaller final diameter under the tested initialization protocol. Fixed-tree stretching is more variable, showing that global spatial extent and local edge stretching are related but distinct observables. Figure 2 compares two outcomes within the random-connected family. Final diameter measures global spatial expansion, while the final-to-initial mean length ratio of the fixed tree measures stretching of a connectivity-sufficient initial structure. Their visibly different variability shows that global expansion and local edge stretching are related but not interchangeable summaries. Most observed expansion occurs during the first 500500 rounds, followed by substantially slower variation through round 5,0005,000. The percentile bands computed in the full evaluation show that the topology-dependent differences persist across independent runs rather than being driven by isolated executions. Fixed-tree edges stretch substantially in every topology group, with the strongest normalized growth for path and sparse random-connected initial graphs. These trends support the interpretation that global diameter and deformation of the preserved connectivity structure capture distinct aspects of the dynamics. Across all tested sizes, median final diameter follows Complete<Dense<Medium<Sparse<Path.Complete<Dense<Medium<Sparse<Path. (24) For paths, the median rises from approximately 17.22V17.22V at N=20N=20 to 44.23V44.23V at N=50N=50. Fig. 3: Final diameter for N=20N=20 and N=50N=50, 100100 runs per group. For two agents we simulate one million runs with D0=0D_0=0, V=1V=1, and 100100 rounds. The empirical first-round moments are 0.636830V0.636830V and 0.500073V20.500073V^2, matching (23) and directly validating the simulation. For Dt≥0.97VD_t≥ 0.97V, first-hitting time has mean 9.51439.5143, median 77, standard deviation 8.64838.6483, and quantiles (1,3,13,26)(1,3,13,26) at probabilities (0.05,0.25,0.75,0.95)(0.05,0.25,0.75,0.95). Only 1.2×10−51.2× 10^-5 of runs have not entered by round 100100. The mean distance first exceeds 0.97V0.97V at round 2121; at that round 82.6507%82.6507\% of runs are currently in the region and 90.8140%90.8140\% have entered at least once. The quantities differ because DtD_t is not monotone along individual trajectories. (a) Current occupancy versus cumulative entry. (b) First-hitting-time distribution. Fig. 4: Finite-round behavior in one million two-agent runs for Dt≥0.97VD_t≥ 0.97V. The empirical first-round moments closely reproduce the exact values and therefore provide a direct implementation check. The hitting-time distribution is concentrated in early rounds but has a right tail. Current occupancy and cumulative first entry are distinct because an individual trajectory can leave the 0.97V0.97V region after first entering it. The cumulative entry fraction is monotone by definition, whereas current occupancy need not be monotone. The theoretical bound is 2/(0.03)2≈2222.222/(0.03)^2≈ 2222.22. To retain the exact state-dependent transition law, normalize V=1V=1 and write a(z)=(1−z)/2a(z)=(1-z)/2. By rotational symmetry, represent the current relative position as (z,0)⊤(z,0) . For independent θ1,θ2∼Unif[0,2π) _1, _2 [0,2π), the next normalized distance is F(z,θ1,θ2) F(z, _1, _2) =[(z+a(z)(cosθ2−cosθ1))2 = [ (z+a(z)( _2- _1) )^2 (25) +a(z)2(sinθ2−sinθ1)2]1/2. +a(z)^2 ( _2- _1 )^2 ]^1/2. For Zt=Dt/VZ_t=D_t/V and a normalized target b=0.97b=0.97, define τbZ=inft≥0:Zt≥b,hb(z)=[τbZ∣Z0=z], _b^Z= \t≥ 0:Z_t≥ b\, h_b(z)=E[ _b^Z Z_0=z], with hb(z)=0h_b(z)=0 for z≥bz≥ b. Here, τ0.97Z=τ0.03V _0.97^Z= _0.03V under the earlier boundary-margin notation. Conditioning on the first transition gives, for z<bz<b, hb(z)=1+1(2π)2∫02π∫02πhb(F(z,θ1,θ2))dθ1dθ2,h_b(z)=1+ 1(2π)^2 _0^2π\! _0^2πh_b(F(z, _1, _2))\,d _1d _2, (26) Equation (26) has a direct first-step interpretation. Starting from a normalized distance z<bz<b, the agents first execute one round, which contributes the term 11. Their independently sampled directions θ1 _1 and θ2 _2 determine the next normalized distance F(z,θ1,θ2)F(z, _1, _2) through (25). From that new state, the expected number of additional rounds required to reach the target is hb(F(z,θ1,θ2))h_b(F(z, _1, _2)). Since both directions are uniformly distributed, the double integral averages this remaining time over all possible direction pairs, with the factor 1/(2π)21/(2π)^2 providing the required normalization. If F(z,θ1,θ2)≥bF(z, _1, _2)≥ b, the target is reached during the current round, so the remaining-time contribution for that direction pair is zero. Thus, the equation states that the expected hitting time equals one current round plus the expected remaining hitting time from the random next state. We discretize [0,b)[0,b) into M cells and use Q periodic quadrature points for each angular variable. The resulting substochastic transition matrix P(M,Q)P^(M,Q) yields (I−P(M,Q))=.(I-P^(M,Q))h=1. (27) Solving this system gives approximately 9.509.50 rounds, independently corroborating the Monte Carlo estimate for the same first-hitting-time quantity. TABLE I: Bellman approximation of h0.97(0)h_0.97(0). M Q h0.97(M,Q)(0)h_0.97^(M,Q)(0) 400 256 9.4896 800 512 9.4943 1200 1024 9.4964 The Bellman values stabilize near 9.509.50 under successive state and angular refinements. The calculation retains the full state-dependent one-step transition law, whereas the analytical hitting-time bound replaces the drift by its minimum value before target entry. Their large numerical difference is therefore expected: the theorem proves finite expected hitting time but is not intended as a tight finite-round prediction. The agreement between Bellman and Monte Carlo concerns the same first-hitting-time quantity and provides two independent numerical estimates. For the finest discretization, the maximum absolute residual of the computed linear system is below 5×10−145× 10^-14. This verifies the numerical solve but does not bound discretization error. A separate one-million-run implementation yields mean 9.50339.5033 with estimated standard error 0.00860.0086 and reproduces the reported median and quantiles. Fig. 5: Monte Carlo validation of Lemma 1. TABLE I: Theory and numerical results for two initially coincident agents. Quantity Analysis Monte Carlo [D1]/VE[D_1]/V 2/π=0.6366202/π=0.636620 0.6368300.636830 [D12]/V2E[D_1^2]/V^2 1/2=0.5000001/2=0.500000 0.5000730.500073 [τ0.03V]E[ _0.03V] Bellman: ≈9.50≈ 9.50 9.51439.5143 median(τ0.03V)median( _0.03V) – 77 The exact first-round moments show that maximal safe random jumps produce substantial separation immediately, even when the agents start without a defined separation direction. The near-boundary results provide a complementary finite-round characterization. Although Theorem 5 gives the conservative bound [τ0.03V]≤2(0.03)2≈2222.22,E[ _0.03V]≤ 2(0.03)^2≈ 2222.22, (28) the Bellman computation and the one-million-run Monte Carlo experiment independently estimate the same mean hitting time at approximately 9.59.5 rounds. The large gap reflects the conservatism of replacing the state-dependent drift by its minimum pre-hitting value, rather than slow behavior of the actual process. VII Discussion and Limitations The policy separates safety from dispersion. The radius is a deterministic certificate; random directions explore the safe set. For general swarms, pairs are coupled through farthest-neighbor ranges. Our general guarantees are edge preservation, connectivity, boundary locking, and the boundary-edge lower bound conditional on absorption. The experiments show topology-dependent stretching but not general convergence. Preserving every edge is deliberately conservative. Complete graphs retain every pairwise constraint and therefore cannot exceed diameter V, while sparse connected graphs can expand over many visibility ranges. Safely releasing redundant constraints from anonymous current ranges remains open. We assume exact ranges and synchronous motion. Noise, actuation errors, asynchrony, collisions, and dynamics are outside scope. Existing range-only and communication-aware systems illustrate complementary mechanisms using estimation, barrier functions, online learning, and optimization [13, 14]. Robustification requires a noise-aware safety margin and delayed or asynchronous analysis. VII-A Interpretation of the General-Swarm Results For larger swarms, the radius of each endpoint of an edge depends on its own farthest visible neighbor, not necessarily on the edge under examination. Pairwise progress is therefore coupled through the rest of the graph, and the scalar two-agent drift does not extend directly. The experiments indicate that the initial topology strongly constrains the attainable geometry: preserving many initial edges imposes stronger geometric confinement, while sparse connected structures permit expansion over several visibility ranges. The observed ordering should be interpreted under the stated initialization protocol. It is not a theorem that edge density alone determines the final diameter, nor does the experiment establish convergence to an absorbing state. A theoretical characterization of limiting configurations for coupled swarms remains open. VII-B Limitations of Preserving Every Edge The never-lose-a-neighbor requirement is deliberately conservative. Without bearings, identifiers, communication, or graph topology, an agent cannot certify that a particular visible edge is redundant. Consequently, redundant initial edges remain active constraints throughout execution. A complete initial graph preserves every pairwise distance below V and therefore cannot exceed diameter V, while a sparse connected graph can expand over several visibility ranges. Designing a range-only mechanism that safely releases redundant edges remains an open problem. VII-C Scope and Future Robustification The exact range and synchronous-jump assumptions isolate the information question addressed here: what finite motion can be certified without bearings? They do not model all limitations of a physical platform. A robust implementation would need a safety margin derived from a stated range-error model, treatment of delayed or asynchronous observations, and motion execution consistent with robot dynamics. Collision avoidance would also require an additional mechanism because the present objective preserves visibility edges rather than enforcing positive pairwise clearance. VIII Conclusion We derived the maximal isotropic displacement certifiable from anonymous current ranges while preserving every visibility edge under synchronous finite motion. The resulting farthest-neighbor rule uses one scalar statistic, preserves connectivity for arbitrary swarm size, and creates permanent anchors when edges reach the visibility limit. Every absorbing configuration contains at least n/2n/2 boundary edges. For two agents, maximal safe random jumps yield positive conditional drift in squared distance, almost-sure convergence to the boundary, and finite expected time to reach every fixed boundary neighborhood. Exact first-round moments, one million Monte Carlo runs, drift validation, and an independent Bellman calculation provide mutually consistent analytical and numerical characterizations. For general swarms, aggregate experiments reproduce the deterministic safety guarantee and show a consistent topology-dependent ordering of attainable diameter across the tested swarm sizes. Establishing convergence for coupled swarms, characterizing limiting configurations, and developing robust noise-aware variants remain open problems. References [1] M. Ji and M. Egerstedt (2007) Distributed coordination control of multiagent systems while preserving connectedness. IEEE Transactions on Robotics 23 (4), p. 693–703. External Links: Document Cited by: §I. [2] M. M. Zavlanos and G. J. Pappas (2007) Potential fields for maintaining connectivity of mobile networks. IEEE Transactions on Robotics 23 (4), p. 812–816. External Links: Document Cited by: §I. [3] D. V. Dimarogonas and K. H. Johansson (2008) Decentralized connectivity maintenance in mobile networks with bounded inputs. In Proceedings of the 2008 IEEE International Conference on Robotics and Automation, p. 1507–1512. External Links: Document Cited by: §I. [4] M. Li, Y. Jie, Y. Kong, and H. Cheng (2022) Decentralized global connectivity maintenance for multi-robot navigation: a reinforcement learning approach. In Proceedings of the 2022 International Conference on Robotics and Automation, p. 8801–8807. External Links: Document Cited by: §I. [5] H. Ando, Y. Oasa, I. Suzuki, and M. Yamashita (1999) Distributed memoryless point convergence algorithm for mobile robots with limited visibility. IEEE Transactions on Robotics and Automation 15 (5), p. 818–828. External Links: Document Cited by: §I. [6] N. Gordon, I. A. Wagner, and A. M. Bruckstein (2004) Gathering multiple robotic a(ge)nts with limited sensing capabilities. In Ant Colony Optimization and Swarm Intelligence, Lecture Notes in Computer Science, Vol. 3172, p. 142–153. External Links: Document Cited by: §I. [7] N. Gordon, Y. Elor, and A. M. Bruckstein (2008) Gathering multiple robotic agents with crude distance sensing capabilities. In Ant Colony Optimization and Swarm Intelligence, Lecture Notes in Computer Science, Vol. 5217, p. 72–83. External Links: Document Cited by: §I. [8] L. Bellaiche and A. M. Bruckstein (2017) Continuous time gathering of agents with limited visibility and bearing-only sensing. Swarm Intelligence 11 (3–4), p. 271–293. External Links: Document Cited by: §I. [9] P. Flocchini, G. Prencipe, N. Santoro, and P. Widmayer (2005) Gathering of asynchronous robots with limited visibility. Theoretical Computer Science 337, p. 147–168. External Links: Document Cited by: §I. [10] A. Barel, R. Manor, and A. M. Bruckstein (2019) COME TOGETHER: multi-agent geometric consensus (gathering, rendezvous, clustering, aggregation). Note: arXiv preprint arXiv:1902.01455Available: https://arxiv.org/abs/1902.01455 Cited by: §I. [11] C. Lee, U. Suh, K. Lee, I. Whang, and W. Ra (2023) Practical distance-based multi-robot formation control using low-cost ultrasonic source tracker. Journal of Electrical Engineering & Technology 18 (4), p. 3219–3236. External Links: Document Cited by: §I. [12] A. Brandstätter, S. A. Smolka, S. D. Stoller, A. Tiwari, and R. Grosu (2024) Flock-formation control of multi-agent systems using imperfect relative distance measurements. In Proceedings of the 2024 IEEE International Conference on Robotics and Automation, p. 12193–12200. External Links: Document Cited by: §I. [13] J. Chen, M. Li, M. Marcantoni, B. Jayawardhana, and Y. Wang (2025) Range-only distributed safety-critical formation control based on contracting bearing estimators and control barrier functions. IEEE Internet of Things Journal 12 (19), p. 40968–40979. External Links: Document Cited by: §I, §VII. [14] Y. Yang, Y. Lyu, Y. Zhang, I. Gao, and W. Luo (2024) Integrating online learning and connectivity maintenance for communication-aware multi-robot coordination. In Proceedings of the 2024 IEEE/RSJ International Conference on Intelligent Robots and Systems, p. 5770–5776. External Links: Document Cited by: §I, §VII. [15] R. Manor, A. Barel, and A. M. Bruckstein (2019) Local interactions for cohesive flexible swarms. Note: arXiv preprint arXiv:1903.09259Available: https://arxiv.org/abs/1903.09259 External Links: Document Cited by: §I. [16] R. Durrett (2019) Probability: theory and examples. 5 edition, Cambridge Series in Statistical and Probabilistic Mathematics, Cambridge University Press. External Links: ISBN 9781108473682 Cited by: §V.