PaperlayerView exact revision on arXiv

Source-linked AI summary

Dynamic, Decentralized Spatial Code Reuse for OCDMA LiDAR in Robot Swarms

Mohammad Hani Alomari

arXiv:2609.28172v1cs.RO

TL;DR

LiDAR swarms face mutual interference, while static code assignment requires codes for the full robot count. This paper introduces dynamic reuse from a live interference-neighborhood graph and proves sublinear code growth, with simulations showing widening peak-code-usage reductions over static assignment.

  • Problem

    Static code-domain schemes require at least N distinguishable codes even when fewer robots are within interference range, leaving code-assignment scaling unresolved.

    Source: §I · p. 1

  • Method

    Robots dynamically reassign spatial reuse codes using a live, locally maintained interference-neighborhood graph rather than permanent per-robot assignments.

    Source: §I · p. 1

  • Results

    2× reduction at N=15 grows to 12× at N=120 in peak simultaneous code usage versus static assignment; under an identical constrained code budget, collision-time fraction is lower than for the coordination-free baseline.

    Source: B. Realistic Headline Result · p. 6, C. Comparison Against a… · p. 7

  • Takeaways & Limitations

    Under the tested comparison, informed coordinated selection achieves both greater code efficiency and lower collision risk than blind coordination-free reassignment under the same constrained budget.

    Source: §I · p. 1, C. Comparison Against a… · p. 7

    Evaluation uses one representative warehouse aisle layout, so topology sensitivity of the neighbor-arrival-rate constant remains unexplored.

    Source: §IX · p. 7

Abstract

from arXiv · show

Robots in a LiDAR-equipped swarm mutually interfere when their optical ranging codes collide. Existing mitigations either assign codes statically -- requiring $L=N$ distinguishable codes for $N$ robots -- or react to detected interference without a scalable, coordinated assignment rule beneath them; prior work explicitly identifies the code-assignment scaling problem as unsolved. We propose a decentralized protocol in which robots dynamically reassign spatial reuse codes based on a live, beacon-maintained interference-neighborhood graph, and prove that the number of codes required grows as $O(\log N/\log\log N)$ under constant robot density -- an unbounded improvement over the $\Theta(N)$ growth of static assignment. We validate this result under conditions substantially beyond the idealized proof -- robot mobility, imperfect beacon-based detection, and reactive reassignment -- via Monte Carlo simulation (30 seeds per condition, 95% confidence intervals): the advantage over static assignment widens from roughly $2\times$ at 15 robots to $12\times$ at 120. Against a structurally faithful, fairly constructed model of an existing coordination-free approach, our protocol achieves both substantially greater code-reuse efficiency and 30--40% lower collision risk under an identical, constrained code budget, demonstrating that coordination -- not merely reactivity -- is what closes the scaling gap.

I. INTRODUCTION

LiDAR mutual interference becomes more frequent and severe as swarms grow. Existing approaches address corrupted returns or signal separation, while the code-assignment scaling problem remains unresolved.

II. RELATED WORK

  • Mitigation approaches are organized by mechanism: post-hoc filtering, waveform randomization, independent timing desynchronization, and code-domain assignment.Code-domain approaches use orthogonal or carrier-hopping families to keep interfering signals distinguishable.Source: §I · p. 1, §II · p. 2

I. INTRODUCTION

  • The protocol replaces permanent assignments with graph-driven dynamic reuse, proving O(log N/log log N) code growth under constant density versus Θ(N) for static assignment.Its novelty is dynamic reassignment, not decentralization alone.Source: §I · p. 1

A. Post-Hoc Detection

  • Post-hoc filtering uses spatio-temporal consistency across frames to remove corrupted point-cloud returns and is complementary to code reuse.It addresses residual interference after assignment, not the assignment problem itself.Source: A. Post-Hoc Detection · p. 2

B. Waveform-Domain Randomization

  • Waveform-domain randomization uses true-random analog signals and correlation-based detection, while explicitly identifying code-assignment scaling as an unresolved limitation.The cited work reports an analytically derived false-alarm probability and hardware validation via a laboratory prototype.Source: B. Waveform-Domain Randomization · p. 2

C. Decentralized Time-Domain Desynchronization

Prior approaches include static code assignment, reactive time-domain desynchronization, and swarm systems that do not assign LiDAR interference-avoidance codes. The section distinguishes these mechanisms from the paper’s scaling gap.

C. Decentralized Time-Domain Desynchronization

  • D2SR independently desynchronizes duty cycles without beacon or neighbor information; its reported interference reduction falls from 70.3% at two LiDAR units to 3.5% at five.The paper uses this coordination-free structure as the basis for its baseline comparison.Source: C. Decentralized Time-Domain… · p. 2

D. Static Code-Domain Reuse

  • CHPC and UID-augmented schemes use fixed code families, while patented zone-based reuse assigns codes statically by location.CHPC has L(N) = N; UID augmentation changes collision probability by a constant multiplier, not the growth rate.Source: D. Static Code-Domain Reuse · p. 2

E. Adjacent, Non-Competing Domains

  • Kaushal et al. coordinate robot behavior and Chen et al. [10] localize neighbors, but neither performs LiDAR ranging or assigns interference-avoidance codes.Infra-Swarm targets perception-pipeline scalability rather than code-assignment scalability.Source: E. Adjacent, Non-Competing Domains · p. 2

F. Summary of the Gap

  • The reviewed approaches lack the combination of dynamic informed reassignment, a live coordinated interference-neighborhood graph, and a formal scaling proof.The paper identifies that combination as its contribution.Source: F. Summary of the Gap · p. 2

A. Robots and Interference

  • Two robots interfere when their separation falls within range D, which is determined by transmit power, receiver sensitivity, and ranging waveform.Robot positions vary over time, so the interference relation can change as the swarm moves.Source: A. Robots and Interference · p. 2

B. Codes and the Interference Graph

The system models interference as a changing graph whose valid code assignments are proper colorings. The protocol aims to maintain that validity with minimal code cardinality and no global coordinator.

B. Codes and the Interference Graph

  • A valid code assignment is a proper coloring of the unit disk interference graph: every pair of adjacent robots must have different codes.An edge connects robots whose separation is at most D.Source: B. Codes and the Interference Graph · p. 3

C. Collision and Conflict

  • A collision is a same-code interference event, whereas a conflict is its detected control-plane counterpart followed by protocol reaction.With perfect instantaneous neighbor knowledge, detection and collision are simultaneous; realistic beacon-limited detection creates a gap.Source: C. Collision and Conflict · p. 3

D. Design Objective

  • The objective is to maintain a valid coloring as robot motion changes the graph, using the smallest code family that supports one with high probability.The analysis assumes instantaneous knowledge; the implementation is evaluated with beacon-limited knowledge.Source: D. Design Objective · p. 3

IV. PROTOCOL DESIGN

  • The protocol combines beacon-based neighbor discovery, deterministic conflict resolution, ID-seeded code selection, and a bounded fallback for local exhaustion.These are the four specified protocol components.Source: §IV · p. 3

A. Control Channel and Neighbor Discovery

  • Robots broadcast identifier, position, current code, and code age over a separate low-rate control channel every beacon period.Local neighbor sets may lag or omit true neighbors because of beacon loss or channel error.Source: A. Control Channel and Neighbor… · p. 3

B. Conflict Detection and Seniority Resolution

Robots detect conflicts from locally observed neighbor codes and resolve them deterministically. Code selection then uses an ID-seeded search bounded by local crowding.

B. Conflict Detection and Seniority Resolution

  • A robot detects a conflict when its current code appears in the set of codes believed to be in use by its observed neighbors.Resolution uses deterministic seniority rather than randomized backoff.Source: B. Conflict Detection and Seniority… · p. 3
  • Seniority is determined by code age, with robot ID breaking ties; the junior robot vacates its code.This preserves established assignments when a newer robot arrives.Source: B. Conflict Detection and Seniority… · p. 3

C. ID-Seeded First-Fit Code Selection

  • ID-seeded first-fit rotates through a candidate window sized to the local exclusion set, avoiding symmetric choices without spreading use across a large fixed pool.The candidate window is based on |Ui(t)| plus a margin.Source: C. ID-Seeded First-Fit Code Selection · p. 4

D. Local Exhaustion: Bounded Time-Duplex Fallback

The scaling analysis bounds code demand for a density-preserving, expanding swarm and contrasts dynamic reuse with static assignment. A bounded time-duplex fallback handles local code exhaustion without growing the code pool.

D. Local Exhaustion: Bounded Time-Duplex Fallback

  • When no valid reassignment exists, affected robots share transmission frames with a guard interval, reducing their ranging update rate by 1/m for m sharing robots without perturbing others.The fallback keeps code-pool growth from undermining the sub-linear scaling claim.Source: D. Local Exhaustion: Bounded… · p. 4

E. Novelty With Respect to Static Reuse

  • The claimed novelty is dynamic, live-graph-driven reassignment, not decentralization, which existing static zone-based schemes also support.Decentralization is described as an engineering property that avoids a fleet-server single point of failure.Source: E. Novelty With Respect to Static Reuse · p. 4

A. Growth Regime and Density Model

  • The proof models an expanding swarm at fixed density with Poisson-distributed positions and interference between robots within distance D.The model uses a toroidal region to isolate density effects from boundary effects.Source: A. Growth Regime and Density Model · p. 4

B. Code Demand as Greedy Coloring

C. A Finite-N Refinement

The asymptotic scaling bound converges slowly at tested swarm sizes, so the paper also uses a finite-N estimate. Its static comparison is grounded in CHPC, whose code-family size grows linearly with chip length.

C. A Finite-N Refinement

  • The asymptotic bound underestimates simulated values by a roughly constant multiplicative factor at tested swarm sizes; a Poisson survival-function inversion gives a closer finite-N estimate.The refinement solves for the smallest k satisfying N · Pr[Poisson(µ) ≥ k] ≤ 1.Source: C. A Finite-N Refinement · p. 4

D. Static Baseline

  • CHPC cardinality equals chip length exactly, so a chip length of 31 supports 31 sequences.The paper selects CHPC as a physically validated, field-standard baseline from the closest prior art.Source: D. Static Baseline · p. 5
  • Dynamic reuse therefore has an unbounded advantage over static assignment, not merely a constant-factor improvement.The comparison uses a static baseline whose code requirement grows linearly with N.Source: D. Static Baseline · p. 5

E. Scope of the Proof

The scaling proof assumes perfect, immediate knowledge of the true interference graph, while operation relies on delayed and potentially erroneous beacon-based estimates. The collision model separates three ways this gap can produce collisions.

E. Scope of the Proof

  • The proof’s code-demand bound is a lower bound for practice because it assumes perfect, immediate neighbor knowledge, unlike the protocol’s lagging and error-prone estimated graph.The proof does not claim to close the gap between its bound and operational code demand.Source: E. Scope of the Proof · p. 5

A. Three Collision Types

  • The collision model distinguishes silent misses from beacon loss, structural detection lag, and handoff transients when reassignment selects a code used by an undetected third robot.Detection lag persists even with zero detection error when the beacon period is positive.Source: A. Three Collision Types • · p. 5

B. Encounter Duration

  • In the warehouse model, two robots sharing an aisle move relative to one another in one dimension, and encounter duration depends on their relative speed.The duration estimate describes the exposure window relevant to detection-lag collisions.Source: B. Encounter Duration · p. 5

C. Grounded Parameters

The evaluation uses grounded simulation parameters and combines graph-constrained mobility, imperfect detection, and Monte Carlo testing. Its warehouse layout constrains robot motion to a network of aisles and intersections.

C. Grounded Parameters

  • Simulation parameters are anchored to measured sources, while detection-error rates are swept rather than fixed because they depend on deployment geometry.Table II is identified as the source of the grounded parameter values.Source: C. Grounded Parameters · p. 5

D. Collision Probability

  • The per-robot collision probability is bounded by a union bound, with Type I and II probabilities approximated analytically and Type III characterized empirically.The handoff-transient case depends on third-party state outside one robot’s detection horizon.Source: D. Collision Probability · p. 5

VII. SIMULATION METHODOLOGY

  • The simulator combines validated interference-graph and code-assignment, graph-constrained mobility, imperfect-detection, and Monte Carlo components.Each component was validated against known ground truth before composition.Source: §VII · p. 5

A. Warehouse Layout

  • The warehouse tile has two main aisles, five cross aisles, and ten intersections; racking blocks direct motion between aisles, motivating graph-constrained movement.Repeating the tile along its length grows the area while holding local aisle density fixed.Source: A. Warehouse Layout · p. 6, Figure 1 · p. 6

B. Mobility Model

The study tests the protocol under aisle-constrained motion, imperfect beacon-based neighbor detection, and a structurally matched coordination-free baseline. Simulated maximum degree across N=50–6400 closely matches the finite-N theoretical refinement.

B. Mobility Model

  • Robots move at fixed speed along aisle edges and choose a random adjacent edge at each intersection, preserving the constant-density assumption.This graph-constrained motion was chosen instead of open-plane random waypoint motion, which concentrates robots toward the region center.Source: B. Mobility Model · p. 6

C. Detection Error Model

  • Neighbor beliefs update at beacon intervals and may omit true neighbors or add phantom ones, with detection lag preserved by enforcing Δt < Tb.A coarser initial step caused beacons to fire every simulation step and erase lag; the corrected model was retested across the sweep.Source: C. Detection Error Model · p. 6

D. Monte Carlo Discipline

  • Reported results use at least 30 independent seeds per condition with 95% confidence intervals, and metrics were checked for convergence under step-size refinement.Collision episodes and total collision time replaced raw event tallies, which scale as 1/Δt; peak simultaneous code usage was also empirically validated for convergence.Source: D. Monte Carlo Discipline · p. 6

E. Baseline Construction

  • The coordination-free baseline has no beacon or neighbor list, relies on per-robot self-diagnosis, and blindly uniformly random-reassigns, unlike the protocol’s informed, exclusion-based selection.Both protocols share the identical warehouse layout, mobility model, and physical interference check. Baseline detection reliability is grounded in reported recall of ≈82–83% and precision of ≈99%.Source: E. Baseline Construction · p. 6

A. Theory-Simulation Agreement

  • The finite-N refinement closely matches simulated maximum degree across N=50–6400, while the leading-order asymptotic estimate underestimates it by a roughly constant factor.The comparison used 30 seeds per point; the gap is consistent with slow convergence of log/log-log bounds.Source: A. Theory-Simulation Agreement · p. 6

B. Realistic Headline Result

Under mobility, worst-case detection error, and reactive reassignment, the protocol’s code-use advantage over static assignment widens with swarm size; comparison with a coordination-free baseline and five stated scope limitations qualify the results.

B. Realistic Headline Result

  • A 2× reduction at N=15 grows to a 12× reduction at N=120 versus the static baseline under mobility, pfn=0.25 detection error, and reactive reassignment.Fig. 3 reports peak simultaneous code usage across 15, 30, 60, and 120 robots, with 30 seeds per point.Source: B. Realistic Headline Result · p. 6, Figure 3 · p. 7

IX. DISCUSSION AND LIMITATIONS

  • The interference model uses Euclidean separation without rack-occlusion checks; adjacent-aisle robots remain plausibly in range at the 5 m cross-aisle spacing.A full geometric line-of-sight model based on rack placement is identified as a simulator extension.Source: §IX · p. 7

C. Comparison Against a Coordination-Free Baseline

  • Under an identical constrained code budget, informed coordinated selection has a consistently lower collision-time fraction than blind selection, while the coordination-free baseline tracks the static baseline under a generous pool.The generous-pool comparison shows little genuine reuse by the coordination-free baseline.Source: Figure 5 · p. 7, Figure 4 · p. 7, C. Comparison Against a… · p. 7

IX. DISCUSSION AND LIMITATIONS

  • The scaling proof covers constant-density growth with expanding operating area, not fixed-area growth in which local vertex degree can depend on N.The fixed-area, increasing-density regime is left to future work because it requires a distinct proof.Source: §IX · p. 7
  • Evaluation uses one representative warehouse aisle graph; alternative topologies may change the unresolved neighbor-arrival-rate constant, though the scaling result is layout-independent.The cited scope includes irregular aisle spacing, non-rectangular footprints, and multiple main-aisle pairs.Source: §IX · p. 7
  • The coordination-free baseline is a simplified, structurally faithful model, not a full reproduction of the source’s sensor-level detection pipeline.It isolates coordination using the source’s reported detection reliability; the underlying pipeline is outside this paper’s scope.Source: §IX · pp. 7–8
  • All results are from Monte Carlo simulation; no physical hardware validation is presented, leaving real beacon hardware, uncontrolled RF interference, and additional sensor noise untested.The paper states that physical deployment validation remains necessary before making an operational deployment claim.Source: §IX · p. 8

X. CONCLUSION

The paper presents decentralized dynamic spatial code reuse, proves sublinear code growth under constant robot density, and reports better code efficiency and lower collision risk than a coordination-free approach. It identifies dense-swarm scaling, asynchronous beaconing, environmental modeling, hardware validation, and longer-horizon extensions as future work.

X. CONCLUSION

  • The protocol achieves O(log N/ log log N) code growth under constant robot density, versus Θ(N) for static assignment, and performs better than a coordination-free approach under an identical resource budget.The evaluation includes robot mobility, imperfect beacon-based detection, and reactive reassignment.Source: §X · p. 8
  • Dense-swarm scaling in a fixed footprint requires a distinct proof from the constant-density result and is planned as follow-on work.Source: §X · p. 8
  • The protocol assumes synchronous, clock-aligned beaconing; relaxing this toward event-driven coordination is future work.Source: §X · p. 8
  • Future environmental modeling includes full geometric line-of-sight occlusion and a broader sweep of warehouse layout topologies.Source: §X · p. 8
  • Physical-robot deployment with real beacon hardware and uncontrolled RF conditions remains a next step toward an operational deployment claim.Source: §X · p. 8
  • Longer-horizon work includes adversarial detection failure, three-dimensional aerial swarms with different neighbor-graph degree scaling, and learned reuse policies.Source: §X · p. 8
Loading 2609.28172v1…