Sensor-based Multi-agent Coverage Control with Spatial Separation in Unstructured Environments

Let $\mathcal{O}=\{\mathbf{q}_{o}\in\mathcal{W}|\mathbf{q}_{o}=(q_{o,x},q_{o,y},q_{o,z}),1\leq o\leq m\}$ be the set of obstacles, where $m$ is the number of all point clouds. The free configuration space is defined as $\mathcal{W}_{\mathrm{free}}=\mathcal{W}\backslash\mathcal{O}.$ Suppose the robot’s perception is solely sensor-based, with the sensor equipped having a fixed sensing range denoted as $R_{\mathrm{sensor}}\in\mathbb{R}_{>0}$. This implies that the robot’s knowledge about the location of environmental obstacles is restricted to the structure it perceives within a nearby area around its current position. Let the robot be surrounded by $m_{r}$ point clouds of obstacles inside the sensor range $R_{\mathrm{sensor}}$. The observable obstacles environment, represented by a series of discrete points and denoted as the set $\mathcal{Q}=\{\mathbf{q}_{o}\in\mathcal{W}\mid\|\mathbf{q}_{o}-\mathbf{p}_{i}\|\leq R_{\mathrm{sensor}},1\leq o\leq m_{r}\}$, constitutes a spherical region centered at the robot’s position $\mathbf{p}_{i}$. Any region outside the robot’s sensory footprint is assumed to be obstacle-free until updated when the robot perceives it.

To evaluate the coverage of the target of interest (ToI) by a multi-robot system, two key factors must be considered: the value of each sensed point and the sensing capability, which is influenced by the distance between the robot and the point on the grid to be sensed. The value of these points is indicative of the importance of the information to be covered. To quantify this, we introduce a density function $\phi(\cdot):\mathcal{W}\rightarrow\mathbb{R}^{+}$ based on a Gaussian mixture model for reference coverage information. As the distance between the robot and the point to be sensed increases, the sensing capability generally diminishes. To optimize the deployment locations of the multi-robot system, we utilize a cost function based on $\phi(\mathbf{p})$ [8, 11, 24]

$\displaystyle\mathcal{H}(\mathbf{P})=\sum_{i=1}^{n}\mathcal{H}_{i}(\mathbf{P})=\sum_{i=1}^{n}\int_{\mathcal{V}_{i}}\|\mathbf{p}-\mathbf{p}_{i}\|^{2}\phi(\mathbf{p})d\mathbf{p}.$

(2)

The derivative of $\mathcal{H}$ indicates that moving to the centroids of the sensors’ corresponding Voronoi cells can reduce the coverage cost. Hence, a gradient decent control policy $\mathbf{u}_{i}$ is designed to steer robots to a CVT:

$\displaystyle\mathbf{u}_{i}=-u_{\max}\frac{\mathbf{p}_{i}-\mathbf{C_{\mathcal{V}_{i}}}}{\|\mathbf{p}_{i}-\mathbf{C_{\mathcal{V}_{i}}}\|}.$

(3)

where $\mathbf{C}_{\mathcal{V}_{i}}=\underset{\mathbf{p}_{i}}{\arg\min}\mathcal{H}_{i}(\mathbf{P}).$

To separate the movement space of multi-robots into some security domains without executing duplicated tasks, a safe convex region needs to be constructed for each robot at discrete time $k\Delta t$, where $\Delta t$ is the time interval. For each time, the Voronoi cell for each robot is only determined by neighboring robots and obstacles, and can thus be formed as the intersection of half-spaces separating robot $i$ from obstacles or other robots with linear separator $\mathbf{a}_{ij}$, $b_{ij}$, and $\mathbf{a}_{io}$,$b_{io}$, where $i,j\in 1,\dots,n$ and $o\in 1,\dots,m$.

Based on above, $\mathbf{a}_{io}$ can be quickly calculated by solving the following low-dimensional quadratic programming (QP) problem:

	$\displaystyle\min$	$\displaystyle\mathbf{a}_{io}^{\mathrm{T}}\mathbf{a}_{io}$		(6)
	s.t.	$\displaystyle(\mathbf{q}_{o}-\mathbf{p}_{i})^{\mathrm{T}}\mathbf{a}_{io}\geq 1,\quad\forall o\in 1,\dots,m_{c}.$

We then shift the hyper-plane to be tight with the target. Thus, $b_{io}=\min{\mathbf{a}_{io}^{\mathrm{T}}\mathbf{q}_{o}}$. Solving a QP problem requires $O(N^{3})$ time, where $N$ denotes the number of decision variables [26]. These decision variables are linearly correlated with the number of obstacle points $m_{c}$ in our method. Consequently, the total computational complexity for each robot, influenced by the local density of obstacles, is $O(m_{c}^{3})$. Leveraging advanced optimization utilities, such as CVXOPT, we can solve the problem in tens of milliseconds.

Moreover, we take into account the geometric dimensions of robots by employing a buffered term [27]. We introduce safety buffer variables $\beta_{ij}=r_{i}\|\mathbf{a}_{ij}\|$ and $\beta_{io}=r_{i}\|\mathbf{a}_{io}\|$ to ensure the body of each robot within its corresponding buffered Voronoi cells (BVCs). It should be noted that these buffer variables can be further generalized to accommodate robots of varying dimensions along different axes. Then, Eq. (1) is extended to the following definition.

Proof: According to Section II-A in [26], 1) - 4) have been proved. 5) According to Eq. (7) and Eq. (6), $\mathbf{a}_{io}^{\mathrm{T}}\bar{\mathbf{p}}_{i}\leq b_{io}-\beta_{io}$, $\mathbf{a}_{oi}^{\mathrm{T}}\mathbf{q}_{o}\leq b_{oi}$. Since $\mathbf{a}_{io}=-\mathbf{a}_{oi}$ and $b_{io}=-b_{oi}$, by adding them, we get $\mathbf{a}_{io}^{\mathrm{T}}(\bar{\mathbf{p}}_{i}-\mathbf{q}_{o})\leq-\beta_{io}$. Due to $\beta_{io}=r_{i}\|\mathbf{a}_{io}\|\in\mathbb{R}^{+}$, we have $\|\mathbf{a}_{io}^{\mathrm{T}}(\bar{\mathbf{p}}_{i}-\mathbf{q}_{o})\|\geq r_{i}\|\mathbf{a}_{io}\|$. Since $\|\mathbf{a}_{io}\|\|\bar{\mathbf{p}}_{i}-\mathbf{q}_{o}\|\geq\|\mathbf{a}_{io}^{\mathrm{T}}(\bar{\mathbf{p}}_{i}-\mathbf{q}_{o})\|$ Therefore, $\|\bar{\mathbf{p}}_{i}-\mathbf{q}_{o}\|\geq r_{i}$. 6) If $\mathbf{q}_{o}\in\bar{\mathcal{V}}_{i}$, then Eq. (7) should be satisfied, i.e., $\mathbf{a}_{io}^{\mathrm{T}}\mathbf{q}_{o}\leq b_{io}-\beta_{io}$. Rewritten this, we have $\mathbf{a}_{io}^{\mathrm{T}}\mathbf{q}_{o}+r_{i}\|\mathbf{a}_{io}\|\leq b_{io}$. According to 5), $\mathbf{a}_{oi}^{\mathrm{T}}\mathbf{q}_{o}\leq b_{oi}$, i.e., $\mathbf{a}_{io}^{\mathrm{T}}\mathbf{q}_{o}\geq b_{io}$, which contradicts to the definition of $\bar{\mathcal{V}}_{i}$.

$\Box$

By combining separating hyperplane theorem and sphere flipping transformation, our method can efficiently extract a collision-free region using only raw measurement points, as shown in Fig. 3 (b). Consequently, each robot is capable of independently calculating its operational domain $\mathcal{V}_{i}$ based on the relative positioning of its peers in a decentralized fashion at each time step.

Proof: Given that the robot is initially collision-free, according to Lemma 1, safe $\bar{\mathcal{V}}_{i}$ can be calculated considering obstacle and other robots information using Eq. (7). Since the policy Eq. (3) ensures the robot’s position $\mathbf{p}_{i}$ is updated inside its corresponding Voronoi cell, i.e., $\mathbf{C}_{\bar{\mathcal{V}}_{i}}\in\bar{\mathcal{V}}_{i}$, by employing mathematical induction, it can be easily proved that the robots’ movements will remain confined to a sequence of secure convex regions for all future time [26].

$\Box$

Therefore, constructing these safe convex regions, the multi-robot system is designed to strictly prevent duplicated task execution and collisions.

Despite its efficiency in convex environments, the control policy in Eq. (3) may let the robot get stuck in many realistic scenarios. These challenges arise primarily due to the complex, non-convex arrangements of obstacles. To address this, we introduce a real-time constructed guided map that is dynamically adjusted in response to environmental changes, thereby enabling the robot to avoid pitfalls and enhancing both the efficiency of coverage and the system’s adaptability.

In the proposed method, we consider the density map $\phi$ in Eq. (2), which characterizes the distribution of information. Each point on the grid map is assigned a corresponding value. As the robot moves, it employs local sensing to identify a point $\mathbf{p}_{g}$ within its sensor range $R_{\mathrm{sensor}}$ that represents a local maximum in the information distribution, which then becomes the robot’s navigation goal. To facilitate reaching this local objective, we define the navigation function (NF) $\mathcal{M}_{\text{go}}:\mathcal{W}_{\mathrm{free}}\rightarrow\mathbb{R}^{+}$ as a continuous function that approximates the minimum length of a collision-free path from any point $\mathbf{q}\in\mathcal{W}_{\text{free}}$ to $\mathbf{p}_{g}$, i.e., cost-to-goal function.

From Lemma 2, it can be observed that the NF exhibits no local minima other than at the goal, ensuring a cycle-free execution of actions that inevitably leads to the goal position. According to [28], the NF determined by Dijkstra’s algorithm working backward from the goal yields an optimality. Here, to balance the efficiency and optimality, we utilize A^∗ algorithm to compute cost-to-go values for each grid on a voxel-based map representation. Consequently, based on $\mathcal{M}_{\text{go}}$, the map $\phi$ in the definition of $\mathcal{H}(\mathbf{P})$ in the Eq. (2) is appropriately modified as follows:

$\displaystyle\phi=e^{-\gamma\mathcal{M}_{\text{go}}(\mathbf{p})},\forall\mathbf{p}\in\mathcal{W}_{\mathrm{free}},$

(8)

where gain $\gamma\geq 0$ serves as a design parameter that influences the magnitude of the value. By integrating centroid Voronoi tessellation with $\phi$ and computing $\mathbf{C}_{\bar{\mathcal{V}}_{i}}$, the regions are shifted to align with higher values in the density map, thereby providing feasible heading directions for coverage. The negative gradient of $\mathcal{M}_{\text{go}}$ always effectively shortens the shortest path to the destination.

This approach synergizes local sensing with global information distribution, resulting in more optimal coverage outcomes. Finally, a sequence of coverage path during the time interval reflecting the optimized location of deployment for each robot can be obtained.

Unlike other coverage methods, like Obstacle-aware Voronoi Cells (OAVC) [10, 11], which are restricted to hyperspherical object models, or the method in [12], which presumes obstacles to be convex polytopes, our approach allows for a broader range of obstacle shapes with various obstacle densities.

We execute tests utilizing high-fidelity point cloud data, sourced from forested areas by the University of Hong Kong and facilitated by the MARSIM simulator [29]. This dataset is characterized by extensive cluttered and thin structural elements. We expanded the scope of the forest environment to large-scale dimensions of 140m $\times$ 140m $\times$ 10m, and the coverage result is depicted in Fig. 4. We also use data from indoor office settings, courtesy of the Technical University of Munich [30] with dimensions of 80m $\times$ 80m $\times$ 5m. This environment featured narrow passageways and multiple layers, and the coverage result is depicted in Fig. 4.

We tested the above mentioned two scenarios with randomized initialization and ToI. We evaluate the two most time-consuming components, local map and Voronoi cell generation, and consider both neighboring robots and obstacles for evaluating collision avoidance performance. One trial test in the forest is shown in Fig. 4 (a) and Fig. 5. The time required for generating a local map depends on the complexity of computing a feasible path. This complexity increases with a high density of obstacles, where conditions such as non-convex obstacles can potentially trap the robots. Despite these challenges, our proposed method can still enable robots to create a secure area in real-time while ensuring safety margins (1.95m) that substantially exceed the robot’s radius (0.25m).

We also tested with varying robot numbers (n=2, 4, 8, 16), each configuration undergoing 10 trials, as depicted in Fig. 6. Due to the decentralized nature of our algorithm, computational time remains largely invariant as the number of robots scales up. Additionally, in more expansive environments—nearly double in obstacle density, the algorithm still satisfies real-time processing criteria. The incidence of collisions remains zero, even when covering obstacle-dense areas, and there are only negligible fluctuations in the minimum distance as the number of robots increases. This demonstrates both scalability in larger contexts and robustness in intricate environments of the proposed method.

We undertake comparative evaluations with other Voronoi-based coverage methods: 1) OAVC method in [11], formulates secure areas by computing tangential boundary lines to circular obstacles and adheres to the gradient of target information; 2) Adaptive coverage method in [9], utilizes a repulsive density function concerning detected obstacles, ensuring that the newly computed centroid is positioned away from the obstacle. To be fair, the obstacles are modeled as the same shape in [11]. We evaluate these methods over 30 trials, each with randomly initialized starting positions within an 80m $\times$ 80m $\times$ 16m workspace. The ToI is defined by a Gaussian distribution featuring three peaks. The performance metrics are as follows: 1) Coverage ratio: The ratio of detected peaks to the total number of peaks; 2) Success rate: The fraction of trials where robots successfully converge to the ToI without experiencing deadlock or collisions within a limited time (30s) or until all peaks are detected; 3) Average time: Task execution time, considering only successful trials. The results are shown in Tab. I.

As shown in Fig. 7, utilizing the proposed method, even in highly irregular environments, all robots can maintain safe distances between each other and prevent both local minima and potential collisions. In contrast, in Fig. 8 (a), the OAVC method directs the robots toward areas of high density without accounting for the obstacle effect, thereby resulting in getting stuck in corners. In Fig. 8 (b), when multiple repulsive fields and attractive fields (target coverage) interact with each other, the adaptive method in [9] predisposes robots to entrapment. Its constrained avoidance space further exacerbates this issue, as it can reduce the navigable space and lead a group of robots to be trapped when moving collectively, thereby increasing the risk of failure.