Line-of-Sight-Constrained Multi-Robot Mapless Navigation via Polygonal Visible Regions

Ruofei Bai; Shenghai Yuan; Xinhang Xu; Xingyu Ji; Xiaowei Li; Hongliang Guo; Wei-Yun Yau; Lihua Xie

cs.ROMar 27, 2026

Line-of-Sight-Constrained Multi-Robot Mapless Navigation via Polygonal Visible Regions

Authors: Ruofei Bai, Shenghai Yuan, Xinhang Xu, Xingyu Ji, Xiaowei Li, Hongliang Guo, Wei-Yun Yau, Lihua Xie

Abstract

Multi-robot systems rely on underlying connectivity to ensure reliable communication and timely coordination. This paper studies the line-of-sight (LoS) connectivity maintenance problem in multi-robot navigation with unknown obstacles. Prior works typically assume known environment maps to formulate LoS constraints between robots, which hinders their practical deployment. To overcome this limitation, we propose an inherently distributed approach where each robot only constructs an egocentric visible region based on its real-time LiDAR scans, instead of endeavoring to build a global map online. The individual visible regions are shared through distributed communication to establish inter-robot LoS constraints, which are then incorporated into a multi-robot navigation framework to ensure LoS-connectivity. Moreover, we enhance the robustness of connectivity maintenance by proposing a more accurate LoS-distance metric, which further enables flexible topology optimization that eliminates redundant and effort-demanding connections. The proposed framework is evaluated through extensive multi-robot navigation and exploration tasks in both simulation and real-world experiments. Results show that it reliably maintains LoS-connectivity between robots in challenging environments cluttered with obstacles, even under large visible ranges and fragile minimal topologies, where existing methods consistently fail. Ablation studies also reveal that topology optimization boosts navigation efficiency by around $20\%$ , demonstrating the framework's potential for efficient navigation under connectivity constraints.

Figures & tables

Fig. 1: (a) Four robots navigate in a simulation environment cluttered with small irregular obstacles while always maintaining LoS-connectivity ( $100m\times 50m$ ). (b) The trajectories of four robots and snapshots of their connectivity graphs when exploring an initially unknown garage environment [ 3 ] ( $87m\times 69m$ ). (c) Three robots exploring an outdoor forest environment adapted from [ 7 ] ( $86m\times 95m$ ).

Fig. 2: Framework of LoS-connectivity constrained multi-robot navigation method. Each robot independently constructs its visible region with the polygonal approximation, based on real-time LiDAR scans. After sharing with immediate neighbors, three types of connectivity constraints are formulated as the weight of the robots’ connectivity graph, which is then proceeded with topology optimization. Next, the masked graph Laplacian matrix is used to derive the connectivity velocity $\boldsymbol{u}_{i}^{c}$ , which is then fused with external navigational velocity $\boldsymbol{u}_{i}^{n}$ through the role-based scaling module, following the design in [ 12 ] . Finally, each robot is driven independently by the fused velocity command to maintain LoS-connectivity between robots while navigating to its own target. The navigational velocity is obtained from a mapless path planner proposed in [ 18 ] . The framework can also be extended for multi-robot exploration by integrating a multi-robot mapper for frontier extraction and a navigation-target assigner, as exemplified in Fig. 1 (b)(c).

Fig. 3: (a): A robot (denoted by $+$ ) with its visible region and polygonal approximation, whose boundaries are highlighted by purple and green dotted lines in (b) and (c), respectively. The radial angle-based interpolation adapts to the boundary geometry by placing denser points (green dots in (a)) along boundaries of high curvature and sparser points along flatter boundaries. (b) and (c) also show the gradient field of $d^{\text{hull}}$ (purple arrows) and $\tilde{d}^{\text{los}}$ (green arrows) respectively, in a zoomed-in area. A probe point (denoted by $\blacktriangle$ ) in (a) has the exact $d^{\text{los}}=1.08m$ and $\tilde{d}^{\text{los}}=1.07m$ , while $d^{\text{hull}}=12.50m$ showing significant metric error. Moreover, the gradient of $d^{\text{hull}}$ tends to trap a robot within a small radial sector.

$r_{\text{flip}}$	Metrics	$\Delta\theta$	$\|\mathcal{V}_{\text{hull}}\|$	$t_{\text{avg}}\downarrow$	$e_{\text{avg}}\downarrow$	$e_{\text{max}}\downarrow$
150	$d^{\text{los}}$	–	428	1157.84	0.00	0.00
	$\tilde{d}^{\text{los}}$	–	428	0.16	53.25	253.94
		2	471( $+10\%$ )	0.16	1.49	4.58
		1	526( $+23\%$ )	0.17	0.34	1.20
500	$d^{\text{los}}$	–	577	2243.31	0.00	0.00
	$\tilde{d}^{\text{los}}$	–	577	0.17	19.76	119.32

TABLE I: Approximation error of LoS-distance

Fig. 4: (a) Error distribution of different LoS-distance metrics at uniformly sampled points in a visible region shown in Fig. 3 , under various flipping radius $r_{\text{flip}}$ . Here we set $\Delta\theta=0.5^{\circ}$ . (b) and (c): Ablation study of using Topo-Opt when four robots are exploring a garage environment in Fig. 1 (b), where (b) compares the temporal variation of $\lambda_{2}$ and (c) shows the histogram of the number of connections between four robots during exploration.

Metrics	Topo-Opt	$d^{\text{los}}_{\text{max}}$ (m) $\downarrow$	$r_{\text{flip}}$ (m) $\uparrow$
Metrics	Topo-Opt	$d^{\text{los}}_{\text{max}}$ (m) $\downarrow$	150	500	1000
$d^{\text{hull}}$ [ 8 , 22 ] ; $d^{\text{hull}}\cdot\cos{\theta_{k}}$ [ 12 ]	w/o	$3.0$	$\checkmark$	$\checkmark$	$\checkmark$
	w/o	$1.2$	$\checkmark$	$\times$	$\times$
	w/	$3.0$	$\times$	$\times$	$\times$
	w/	$1.2$	$\times$	$\times$	$\times$
$\tilde{d}^{\text{los}}$ (Proposed)	w/o	$1.2$	$\checkmark$	$\checkmark$	$\checkmark$

TABLE II: Connectivity maintenance in multi-robot navigation

Fig. 5: Relative time and distance efficiency of compared methods with four robots navigating in a cluttered environment shown in Fig. 1 (a). Dashed lines indicate the average performance. The indices of different runs are sorted in ascending order based on the total distance to the targets. (a) and (b): only one robot is assigned a random target; (c) and (d): all four robots have their targets.

Fig. 6: Snapshots of connectivity graphs with the Fixed, Laplacian, and the proposed methods. The figure highlights the robots (green circles), selected connections (green edges), and redundant connections (blue edges). The Fixed method fails to adapt to a better topology to facilitate navigation efficiency; the Laplacian method tends to maintain redundant connections, and can lead to occasional livelock around obstacles; the proposed method adaptively optimizes the topology that facilitates navigation efficiency. The results are best appreciated with the video in supplementary materials.

Fig. 7: Snapshots of real-world experiments where three drones navigate in an environment with obstacles. More details are in the attached videos.

Fig. 8: Illustration of notations used in the proof of Prop. 3 .

Fig. 9: Illustration of notations used in the proof of Cor. 1 .

Explore similar work

Mar 9, 2026

Perception-Aware Communication-Free Multi-UAV Coordination in the Wild

We present a communication-free method for safe multi-robot coordination in complex environments such as forests with dense canopy cover, where GNSS is unavailable. Our approach relies on an onboard anisotropic 3D LiDAR sensor used for SLAM as well as for detecting obstacles and neighboring robots. We develop a novel perception-aware 3D navigation framework that enables robots to safely and effectively progress toward a goal region despite limited sensor field-of-view. The approach is evaluated through extensive simulations across diverse scenarios and validated in real-world field experiments, demonstrating its scalability, robustness, and reliability.

Manuel Boldrer, Michal Kamler, Afzal Ahmad +1

Department of Cybernetics, Czech Technical University in Prague, Karlovo namesti 13, 121 35 Prague 2, Czechia.

Multi-Robot Coordination UAV Navigation Safe Robot Navigation Multi-Robot Motion Planning

Ask PDF

Jun 15, 2026

SGM-SLAM: Scene Graph Matching for Data-Efficient Distributed SLAM

We introduce a data-efficient distributed Simultaneous Localization and Mapping (SLAM) framework designed for a team of robots equipped with LiDAR, cameras, and inertial sensors. Our framework uses scene graph matching to identify inter-robot measurement constraints. Unlike prior approaches that rely on feature-level matching, our framework is the first to perform scene graph matching using only object labels and centroids. Our approach constructs a scene graph by using fused RGB-LiDAR point clouds to generate both a semantically segmented point cloud layer, and a layer of discrete bounded objects, to accompany estimated robot trajectories. Scene graph matching is performed collaboratively through exchanging and matching object data with neighboring robots. To maximize communication efficiency, we utilize a multi-step data exchange and optimization process. We demonstrate the effectiveness and efficiency of our approach using both simulation and real-world datasets collected by legged robots in indoor and outdoor environments.

Yewei Huang, Tixiao Shan, Abhinav Rajvanshi +4

Dartmouth College, 100 N Main St, Hanover, NH 03755, USA · SRI International, 201 Washington Rd, Princeton, NJ 08540, USA · Stevens Institute of Technology, 1 Castle Point Terrace, Hoboken, NJ 07030, USA

Simultaneous Localization and Mapping Multi-Robot Systems

Ask PDF

Oct 8, 2026

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

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.

Zhiqiang Cao, Ran Liu, Billy Pik Lik Lau +2

Engineering Product Development, Singapore University of Technology and Design, Singapore 487372 · School of Electrical and Electronic Engineering, Nanyang Technological University, Singapore 639798

Cooperative Localization Multi-Robot Systems

Ask PDF