PaperlayerView exact revision on arXiv

Source-linked AI summary

Distributed Relative Localization Based on Ultra-WideBand and LiDAR for Multi-robot with Limited Communication

Zhiqiang Cao, Ran Liu, Billy Pik Lik Lau, Chau Yuen, U-Xuan Tan

arXiv:2610.11141v1cs.RO

TL;DR

Similar-looking robots are difficult to localize relative to one another when GPS and communication are constrained. The paper combines UWB ranging and LiDAR through graph matching and distributed recovery of unestimated robots. Experiments report localization errors in both LOS and NLOS conditions.

  • Problem

    Relative position is essential for multi-robot decision-making and collaboration, but similar appearance challenges teammate identification in GPS-denied, communication-limited settings.

    Source: §I · p. 1

  • Method

    The approach builds UWB and LiDAR connection graphs, matches common subgraphs, rejects suspicious correspondences, and uses well-matched robots with UWB ranges to localize unestimated robots.

    Source: §I · p. 2

  • Results

    Approximately 0.05m average relative position error was achieved in LOS, and below 0.25m in NLOS, across varying numbers of robots.

    Source: E. Evaluation with different numbers… · p. 10

  • Takeaways & Limitations

    The experiments demonstrate distributed relative localization in LOS and NLOS scenes with UWB assistance and limited information exchange.

    Source: §I · p. 2

    The authors identify UWB ranging stability and stronger spatial relationships among objects as targets for improving accuracy and robustness.

    Source: §V · p. 11

Abstract

from arXiv · show

Relative localization is crucial for a multi-robot system to collaboratively perform tasks, such as exploration and formation. However, this is highly challenging for homogeneous robots with similar appearance in GPS-denied and communication-limited environments. In this paper, we propose a fully distributed relative position estimation approach for a team of robots based on onboard UWB and LiDAR sensors, in which LiDAR is utilized to obtain the position of anonymous objects in Line-of-Sight (LOS), and UWB is used for ranging between robots. We construct two graphs, namely UWB connection graph and LiDAR connection graph, to represent the spatial relationship among objects (robots and obstacles) based on UWB and LiDAR measurements. Identification and relative position estimation are formulated as a common subgraph matching problem. A falsely-matched robot identification approach is designed to recognize the falsely-matched results caused by obstacle blockage in LiDAR field of view. These robots are then localized by leveraging the well-matched robots and the UWB ranging measurements in the UWB connection graph. We conducted experiments to evaluate the performance of our approach. The results show that the proposed approach is capable of achieving satisfactory positioning accuracy for a team of robots in a distributed manner with only exchanging limited information.

I. INTRODUCTION

The paper addresses relative localization for similar-looking robots in settings where communication and positioning infrastructure are limited. It combines onboard UWB and LiDAR in a distributed method and evaluates localization in LOS and NLOS scenes.

I. INTRODUCTION

  • Distributed localization uses local measurements and small amounts of neighboring-robot data, suiting settings with limited communication bandwidth.Source: §I · p. 1
  • Similar robot appearance complicates teammate identification; LiDAR and cameras work in LOS, while UWB provides unique node identification, ranging, and limited data transmission.The paper targets communication-constrained scenes without external communication or positioning infrastructure.Source: §I · pp. 1–2
  • The method combines UWB ranging and LiDAR measurements, formulating robot identification and relative position estimation as common subgraph matching.It constructs separate UWB and LiDAR connection graphs, then identifies falsely matched robots and localizes unestimated robots using well-matched robots and UWB ranges.Source: §I · p. 2
  • The approach recognizes falsely matched robots caused by obstacle occlusion and re-localizes them using well-matched robots and relevant UWB ranges.Source: §I · p. 2
  • Experiments report effective robot localization in both LOS and NLOS scenes with UWB assistance.Source: §I · p. 2

II. RELATED WORK

Prior work uses visual, LiDAR, or UWB sensing for relative localization, but faces data-association, communication, visibility, or hardware constraints. The paper's system overview organizes its approach into four processing modules.

II. RELATED WORK

  • Visual methods can depend on image overlap or favorable communication; proposed ID aids include randomly reassigned tracker IDs and pre-designed infrared LEDs.The LED-based approach is described as less conducive to multi-robot scalability.Source: §II · p. 2
  • LiDAR clustering estimates object positions but assigns random cluster IDs; prior tracking needs non-parallel motion and favorable communication, while another method cannot localize occluded robots.Source: §II · pp. 2–3
  • UWB can operate in NLOS and provide unique robot identification, while cited methods face limited accuracy, small-robot suitability, or continuous sequence requirements.The cited least-squares approach uses multiple UWB nodes at different robot positions; optimization approaches use odometry and UWB sequences collected over the network.Source: §II · p. 3

III. SYSTEM OVERVIEW

  • The system overview comprises graph construction, common-subgraph vertex matching, suspicious-correspondence recognition, and UWB-assisted localization of unestimated robots.Source: §III · p. 3

A. Module 1: graph construction

Each robot independently constructs UWB and LiDAR connection graphs from ranging and cluster-position measurements. The resulting graphs support common-subgraph matching and disclosure of optimal vertex correspondences.

A. Module 1: graph construction

  • Each robot independently constructs connection graphs whose edges represent measured distances between vertices.The UWB sensor measures nearby robot distances and broadcasts a limited amount of data within communication range.Source: A. Module 1: graph construction · p. 3
  • The UWB graph uses robot-ID vertices and ranging edges, whereas the LiDAR graph contains detected robot and obstacle clusters connected by pairwise distances.LiDAR cluster IDs are random except for the local robot; occluded or out-of-range robots are not detected, and large clusters are removed.Source: A. Module 1: graph construction · pp. 3–4
  • UWB and LiDAR graphs may differ because UWB can penetrate some obstacles, LiDAR detects only LOS objects, and communication limits can remove UWB edges.Source: A. Module 1: graph construction · p. 4

B. Module 2: optimal vertex correspondences disclosure based on common subgraph matching

  • Common-subgraph matching finds shared induced subgraphs, then selects correspondences from the highest-similarity maximum subgraph and scattered matches in remaining subgraphs.Partial overlap is possible because of obstacle blockage and limited communication; the resulting correspondences help identify robots detected by LiDAR.Source: B. Module 2: optimal vertex… · p. 4

1) Common subgraph matching:

Common subgraph matching searches for vertex correspondences between the UWB and LiDAR graphs. It initializes from the known correspondence for the local robot, extends matches using label sequences, and uses recursive updates and backtracking to find common subgraphs.

1) Common subgraph matching:

  • The search starts from the known correspondence between the local robot’s UWB vertex and LiDAR vertex, initializing unmatched-vertex labels by adjacency.Adjacent vertices receive the measured distance in their label sequence; non-adjacent vertices receive infinity.Source: 1) Common subgraph matching · p. 4
  • A vertex pair extends the current common subgraph when corresponding label-sequence elements differ by less than the distance threshold λ.The recursive search updates the graphs and remaining label sequences after each extension.Source: 1) Common subgraph matching · p. 4
  • The recursive procedure backtracks after finding a common subgraph, removes the latest correspondence, and continues searching for another.Found subgraphs are incorporated into the accumulated set before the search continues.Source: 1) Common subgraph matching · p. 4
  • A common subgraph is found when the bound computed from the remaining unmatched-vertex label sequences reaches zero.The unmatched vertices form the set S used in the bound.Source: 1) Common subgraph matching · pp. 4–5

2) Optimal vertex correspondences disclosure:

The method selects the largest, most-similar common subgraph as its primary correspondence set and recovers additional correspondences from remaining candidates. It then checks matched robots against UWB ranges to identify false matches caused by occlusion or constrained communication.

2) Optimal vertex correspondences disclosure:

  • Among equally sized maximum common subgraphs, the method selects the one with the lowest dissimilarity score and collects additional correspondences from remaining subgraphs into O.The primary set M* may contain only partial correspondences under obstacle occlusion or limited communication.Source: 2) Optimal vertex correspondences… · p. 5

C. Module 3: falsely-matched robot recognition

  • The resulting correspondence set maps robots to anonymous LiDAR clusters, while the verification step addresses false matches from obstacle occlusion and constrained communication.The correspondence set supports identifying robots and obtaining their positions in the local robot frame.Source: C. Module 3: falsely-matched robot… · p. 5
  • Robots in M* serve as trusted benchmarks; a robot in O is flagged as falsely matched when its position-based and UWB distance vectors exceed the dissimilarity threshold.The vectors compare distances from the candidate robot to benchmark robots, using the corresponding UWB ranges.Source: C. Module 3: falsely-matched robot… · p. 5

D. Module 4: unestimated robots positioning

Unestimated robots within UWB communication range are positioned using well-matched robots as anchors. Their positions are estimated by minimizing residuals between candidate positions and UWB range measurements.

D. Module 4: unestimated robots positioning

  • Well-matched robots verified by the preceding module serve as anchors for positioning unestimated robots within UWB communication range.The paper identifies the remaining position information as important for multi-robot tasks such as cooperative exploration.Source: D. Module 4: unestimated robots… · p. 6
  • The method estimates an unestimated robot’s position by minimizing the residual error of its UWB ranging measurements to known robots.It uses nonlinear least-squares optimization to find a position configuration satisfying the range constraints.Source: D. Module 4: unestimated robots… · p. 6
  • The anchor set K must contain more than three well-matched robots for the nonlinear least-squares localization.The estimated position is expressed in the local frame of another robot.Source: D. Module 4: unestimated robots… · p. 6

IV. EXPERIMENTAL RESULTS

The experiments evaluate the approach’s feasibility, reliability, and scalability with homogeneous robots in communication-limited scenes. They cover its modules, communication conditions and protocols, team size, and a dynamic scenario.

IV. EXPERIMENTAL RESULTS

  • Experiments with homogeneous robots in communication-limited scenes are designed to evaluate feasibility, reliability, and scalability.The evaluation section introduces the metrics and UWB communication protocol used by the approach.Source: §IV · p. 6
  • The evaluation examines the performance of proposed modules and the approach under different communication conditions and UWB ranging-sharing protocols..Source: §IV · p. 6
  • Scalability is studied across varying robot-team sizes, and the approach is also evaluated in a simple dynamic scenario..Source: §IV · p. 6

A. Evaluation metrics and UWB communication protocol

The evaluation uses relative position error and solution rate to assess localization accuracy and effectiveness. Communication rate measures the portion of each robot’s UWB ranging data shared under the protocol.

A. Evaluation metrics and UWB communication protocol

  • Solution rate is the ratio of successful solutions to roughly 130 trials, while relative position error averages a robot’s results across timestamps.The two metrics quantify effectiveness and accuracy, respectively.Source: A. Evaluation metrics and UWB… · p. 6
  • The protocol arranges each robot’s UWB ranging data in a fixed order for sharing at different communication rates.The protocol is shown in Fig. 4.Source: A. Evaluation metrics and UWB… · p. 6, Figure 4 · p. 6
  • Communication rate is Nshared divided by Ntotal, the number of ranging measurements shared versus measured; Ntotal is seven in this setup.Robots share only a portion of their UWB ranging data with nearby robots.Source: A. Evaluation metrics and UWB… · p. 6

B. Evaluation of different modules

Experiments evaluate the modules with eight robots and obstacles, including two robots occluded from Robot 1. Module 2’s matching threshold trades accuracy and coverage against false matches and computation, while Module 3 can reject false matches while preserving correct results at suitable thresholds.

B. Evaluation of different modules

  • The evaluation used eight Turtlebot2 robots and static obstacles in a 6 m × 17 m indoor area; Robot 1 was NLOS to Robots 3 and 4.The setup used 2D LiDAR and unique-ID UWB sensors; analysis was from Robot 1’s perspective.Source: B. Evaluation of different modules · pp. 6–7

1) Optimal vertex correspondences disclosure based on common subgraph matching module (Module 2):

  • At λ = 1.5 m, LOS robots achieved around 0.25 m positioning accuracy and a 100% solution rate; larger thresholds also increase matching time and can admit false matches.Across λ = 0.2, 0.5, 1.0, and 1.5 m, matching took 0.03, 0.13, 0.36, and 2.84 seconds, respectively; larger thresholds can produce errors greater than 0.5 meters.Source: 1) Optimal vertex correspondences… · p. 7, Figure 6 · p. 7
  • At λ = 0.2 m, false matches reduced accuracy for Robots 2 and 4; at λ = 0.5 m, Robot 4’s error was 6.43 m and Robot 3 was not matched.At λ = 1.0 m, Robot 2 was correctly matched throughout, and LOS Robots 5–8 were accurately estimated with a 100% solution rate.Source: 1) Optimal vertex correspondences… · p. 7, Figure 6 · p. 7

2) Falsely-matched robot recognition module (Module 3):

  • For 0.2 ≤ ϵ ≤ 1.0, Module 3 identified all erroneous Robot 4 results and preserved correct results for Robots 2 and 5–8.At ϵ = 0.0, Robot 4’s results were rejected but Robot 8’s solution rate fell to 97.7%; at ϵ ≥ 1.3, some Robot 4 errors were missed.Source: Table III · p. 7, 2) Falsely-matched robot recognition… · pp. 7–8

3) Unestimated robots positioning module (Module 4):

The evaluation tests the unestimated-robot module and the effect of sharing different amounts of UWB ranging data. At a 71% communication rate, positioning reaches its reported peak, while performance remains dependent on sufficient UWB measurements.

3) Unestimated robots positioning module (Module 4):

  • The unestimated-robot module localized Robot3 and Robot4 with a 100% solution rate and approximately 0.5m positioning accuracy, despite both being NLOS to Robot1.They may be LOS to other robots, whose UWB ranges provide localization constraints.Source: 3) Unestimated robots positioning… · p. 8

C. Evaluation with different communication rates

  • Each UWB range uses 2 Bytes; for eight robots, the theoretical maximum at 100% communication is 51 robots under the stated 100-Byte packet limit.The data transmitted per robot is 2(N −1) × communication rate Bytes, and higher rates increase computation time.Source: C. Evaluation with different… · p. 8, Table IV · p. 8
  • At 0% communication, most robots were wrongly localized, and the false-match and unestimated-robot modules performed poorly because the UWB graph was sparse.The common-subgraph matching module also struggled to estimate Robot3.Source: C. Evaluation with different… · p. 8, Table V · p. 9
  • At 43% communication, Robot4 had 4.52m average relative positioning accuracy and a 98.07% solution rate before remaining false results were addressed.After false-match filtering, 7.05% of false results remained; Module 4 localized Robot3 and Robot4 at 0.37m and 1.04m average accuracy, respectively.Source: C. Evaluation with different… · pp. 8–9, Table V · p. 9
  • At 71% communication, LOS robots achieve under 0.3m positioning error, NLOS robots approximately 0.5m, and every robot a 100% solution rate.Robot4 improves from 1.04m at 43% to 0.53m at 71%, with no significant improvement from 71% to 100%.Source: C. Evaluation with different… · p. 9, Table V · p. 9

D. Evaluation under different UWB communication protocols

The evaluations compare fixed-order and random-order UWB sharing, then test localization as the simulated team size varies. Fixed-order sharing is more stable at communication rates of at least 43%, and the approach maintains a 100% solution rate across the tested team sizes.

D. Evaluation under different UWB communication protocols

  • At communication rates of 43% or higher, fixed-order sharing consistently outperforms random order and achieves stable results; both protocols perform poorly below 43%.Random selection can reduce UWB graph connectivity and density through redundant sharing of ranges with the same attributes.Source: D. Evaluation under different UWB… · p. 9, Table VI · p. 10

E. Evaluation with different numbers of robots

F. Evaluation in dynamic scenario

In the dynamic experiment, robots’ positioning errors changed as they moved into and out of LiDAR range or became occluded. The conclusion reports accurate relative positions in LOS and NLOS cases and identifies improved UWB stability and stronger spatial relationships as future work.

F. Evaluation in dynamic scenario

V. CONCLUSION AND FUTURE WORKS

  • The conclusion reports accurate relative positions for robots in both LOS and NLOS cases in communication-limited environments, based on experiments in real and simulated settings.The approach constructs UWB and LiDAR connection graphs, uses common subgraph matching, filters suspicious matches, and localizes remaining robots using well-matched robots and UWB ranges.Source: §V · p. 11
  • Future work targets 3D applications and improved accuracy and robustness through more stable UWB ranging and stronger spatial relationships among objects.The authors also propose using 3D LiDAR or a camera for robot detection without changing robot structure.Source: §V · p. 11

Related papers

Loading 2610.11141v1…