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

The gist Distributed relative localization based on Ultra-WideBand and LiDAR for multi-robot with limited communication proposes a fully distributed relative position estimation approach for homogeneous robots using onboard UWB and LiDAR sensors to overcome challenges in GPS-denied and communication-limited environments.

How it works

1. The system constructs two graphs: the UWB connection graph and the LiDAR connection graph, using distance information between objects as input for each (Fig. 3).

2. Identification and relative position estimation are formulated as a common subgraph matching problem between these two graphs (Section III-B).

3. A falsely-matched robot identification approach is designed to recognize false matches caused by obstacle blockage in the LiDAR field of view (Section III-C). This involves comparing the normalized Euclidean distance dissimilarity-based approach to identify falsely-matched robots (Equation 4) <ref:2610.11141#pg8>.

4. The system then localizes robots by leveraging well-matched robots and the UWB ranging measurements in the UWB connection graph for those not estimated (Section III-D). This localization is achieved by minimizing the residual error of UWB ranging measurements based on well-matched robots (Equation 5) <ref:2610.11141#pg9>.

Key Components and Methodology

** The UWB sensor is utilized to measure the range between robots and broadcast a few ranging data to nearby robots, while the LiDAR detects and localizes the surrounding objects in Line-of-Sight (LOS) (Fig. 3) <ref:2610.11141#pg3>. The UWB connection graph is constructed using UWB ranging directly measured by itself and those shared by peer robots based on a customized protocol (a) <ref:2610.11141#pg4>. The LiDAR connection graph is constructed using the adaptive clustering algorithm to cluster objects (including robots and obstacles) and obtain their positions in the local robot frame (b) <ref:2610.11141#pg4>. **

** Module 2 employs a common subgraph matching approach to find all common subgraphs M between the UWB connection graph Guwb and the LiDAR connection graph Glidar, and then discloses optimal vertex correspondences Q, which includes M**

Performance Evaluation

The experiments validate the approach in real-world and simulation environments using two metrics: relative position error (meter) and solution rate (%) <ref:2610.11141#pg8>.

** 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 <ref:2610.11141#pg6>. In LOS scenarios, the average relative position error is approximately 0.05m, and for NLOS scenarios, it is below 0.25m when using the proposed approach under specific conditions (Fig. 9) <ref:2610.11141#pg10>. **

** The performance of the system is highly dependent on communication rate; for instance, at a communication rate of 71%, robots in LOS achieve a relative positioning accuracy of under 0.3m, while NLOS robots obtain an error of approximately 0.5m (Table V) <ref:2610.11141#pg10>. **

** The system demonstrates robustness across varying numbers of robots, consistently achieving a solution rate of 100% even in simulation scenarios with up to 12 robots (Fig. 9) <ref:2610.11141#pg9>. **

Communication Protocol and Scalability

The UWB communication protocol is specified as a simple protocol where the communication rate is defined as Nshared over Ntotal multiplied by 100% (Equation 6) <ref:2610.11141#pg8>. A fixed order protocol for sharing UWB ranging measurements is adopted to ensure robustness and accuracy, as it consistently outperforms random order when the communication rate reaches or exceeds 43% (Table VI) <ref:2610.11141#pg10>. The approach shows scalability with varying numbers of robots, with computational cost and time increasing as the number of robots scales (Table VII) <ref:2610.11141#pg8>.

Conclusion

The proposed distributed relative localization method provides accurate relative positions for robots in both LOS and NLOS cases within communication-limited environments through a combination of UWB ranging and LiDAR measurements without external infrastructure <ref:2610.11141#pg6>. The approach demonstrates the ability to provide accurate and effective localization in varying numbers of robots (Fig. 9) <ref:2610.11141#pg9>. The system is robust, consistently achieving a solution rate of 100% across different conditions (Fig. 9) <ref:2610.11141#pg9>. Future work includes extending the approach to 3D applications using 3D LiDAR or camera and improving UWB ranging stability (Section V). The system is effective in dynamic scenarios, maintaining low errors even when robots transition between NLOS and LOS states (Fig. 11) <ref:2610.11141#pg9>. The approach is feasible for multi-robot systems with limited communication bandwidth (Section I).

--- Page 9 ---

The results show that the proposed approach is able to provide accurate relative positions for robots in both LOS and NLOS cases in communication-limited environments <ref:2610.11141#pg10>. Moreover, our approach demonstrates the ability in scalability <ref:2610.11141#pg9>. The system is robust, consistently achieving a solution rate of 100% across varying numbers of robots (Fig. 9) <ref:2610.11141#pg9>. While the performance in terms of relative position accuracy and solution rate demonstrates robustness, the communication cost and computational time increases as the number of robots scales, as summarized in Table VII <ref:2610.11141#pg8>. The approach is feasible for multi-robot systems with limited communication bandwidth (Section I) <ref:2610.11141#pg6>.

--- Page 8 ---

The results show that the proposed approach is able to provide accurate relative positions for robots in both LOS and NLOS cases in communication-limited environments <ref:2610.11141#pg10>. Moreover, our approach demonstrates the ability in scalability <ref:2610.11141#pg9>. The system is robust, consistently achieving a solution rate of 100% across varying numbers of robots (Fig. 9) <ref:2610.11141#pg9>. While the performance in terms of relative position accuracy and solution rate demonstrates robustness, the communication cost and computational time increases as the number of robots scales, as summarized in Table VII <ref:2610.11141#pg8>.

--- Page 7 ---

The results show that our approach can effectively localize the robots in both LOS and NLOS scenes with the assistance of UWB (Section II) <ref:2610.11141#pg6>. The occluded Robot4 was still falsely-matched and achieved a positioning accuracy of 6.43m, while another occluded Robot3 was not matched through Module 2 (Section IV-B) <ref:2610.11141#pg8>.

--- Page 6 ---

The results show that our approach can effectively localize the robots in both LOS and NLOS scenes with the assistance of UWB (Section II) <ref:2610.11141#pg6>. The occluded Robot4 was still falsely-matched and achieved a positioning accuracy of 6.43m, while another occluded Robot3 was not matched through Module 2 (Section IV-B) <ref:2610.11141#pg8>.

--- Page 5 ---

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 <ref:2610.11141#pg6>.

--- Page 3 ---

The system framework can be divided into two main categories, namely Z. Cao, B. P. L. Lau, and U-X. Tan are with the Engineering Product Development, Singapore University of Technology and Design, Singapore 487372 <ref:2610.11141#pg4>.

--- Page 4 ---

The main contributions of this paper are summarized as follows: • We propose a distributed relative position estimation method for a group of homogeneous robots, leveraging UWB ranging and LiDAR measurements. The identification and relative position estimation are formulated as a common subgraph matching problem <ref:2610.11141#pg3>. • We present an approach to recognize the falsely-matched robots due to obstacle occlusion, then re-localize these robots using the well-matched robots and the relevant UWB ranging measurements (Section III-C).

1. textbfIdentify False Matches via Positional Verification: The system can verify suspicious correspondences by calculating a normalized Euclidean distance dissimilarity between robot position information and relevant UWB ranging measurements, as described in Section III-C, to distinguish true matches from those caused by obstacle occlusion and constrained communication.

2. textbfAnchor Localization for Unestimated Robots: The system can localize robots not estimated through the matching process by leveraging the well-matched robots and the relevant UWB ranging measurements, formulating the estimation as minimizing a residual error based on Equation 5, which finds the best position configuration to satisfy the UWB ranging constraints.

3. textbfScalable Distributed Localization: The system can perform accurate relative positioning in varying numbers of robots (N) by employing a common subgraph matching approach, demonstrating that our approach is able to accurately and effectively localize surrounding robots in varying N with an average relative position error of approximately 0.05m in LOS scenarios.

4. textbfCommunication Rate Optimization: The system can dynamically adjust its performance based on communication constraints, achieving peak reliability when the communication rate reaches or exceeds 71%, as this is where the solution rate for robots in LOS becomes 100%.