Adaptive coverage control for multi-USV system in complex environment with unknown obstacles

Abstract

Aiming at the shortcomings of the existing control law based on the global information, this article studies the coverage problem of a given region in the plane using a team of USVs. The coverage goal, which is to cover a given search domain using multiple mobile sensors so that each point is surveyed until a certain preset level is achieved, is formulated in a mathematically precise problem statement. The adaptive control law is presented which enables multi-USV to navigate in a complex environment in the presence of unknown obstacles and guarantees that a fully connected multi-USV system attains the coverage goal. In particular, the dangerous area was divided into two different parts in order to enhance the searching efficiency. Finally, simulation results are presented to validate the feasibility and efficiency of the proposed approach.

Keywords

Adaptive searching control multi-USV potential field method obstacle avoidance USV

Introduction

In recent years, with the rapid development of sensor technology,^1,2 intelligent system guidance and control technology,^3–5 information processing technology between sensor networks⁶ and communication technology, people have formed a certain scientific understanding of the generation mechanism and implementation strategy of regional environmental reconnaissance and monitoring.⁷ They believe that its essence is to ensure that the agent moves along a specific track by studying its control methods and make use of the relevant information collected by the sensors it carries to realize the regional reconnaissance and monitoring. Therefore, the problem of regional reconnaissance and monitoring is essentially a multi-USV regional coverage control problem.

At present, the research on regional coverage control of marine environment has been widely valued in both military and civilian areas. In the military aspect, area coverage control can be used for multi-USV seabed topographic mapping, mine detection, and so on.^7–9 In the civil aspect, it can be used for underwater search and rescue, sunken ship salvage, cleaning up oil leakage on the sea surface, and so on.^10–12 Because underwater detection mainly relies on sonar means, unmanned surface vehicle (USV) has become the most important carrying platform. Due to the limited detection and endurance of a single USV, it is unable to efficiently complete the search task in large area of sea,^13–15 so the autonomous search system of multi-USV has become an inevitable development trend. In complex environment, the cooperation among multi-USV is the bottleneck problem of autonomous search system. At present, the main solution to the problem of cooperation among multi-USV is the area division and route planning based on the global information,^16–18 that is, when the number and location information of obstacles are known, the search area is divided into sub areas, and then the command center assigns search tasks of different sub areas to the unmanned vessels, so as to realize the cooperation of multi-USV system.

The task assignment scheme for multi-USV cooperation based on global information is not flexible, and the shape of obstacles and the navigation route of USVs are fixed, so it is unable to complete the search task in complex environment. Therefore, in order to meet the practical application requirements of the search task in complex environment, the multi-USV adaptive search system must be based on its own real-time perception of local information, as well as part of the environment information obtained by real-time interaction with other USVs, so that each USV can adaptively plan the route, and achieve the functions of collision avoidance, obstacle avoidance and target search.

The rest of this article is organized as follows: In section “Problem formulation,” we formulate the problem and then define the sensing area of USV and the function of the sensing ability. The adaptive searching method was presented in section “Adaptive control law.” The control law of driving force and repulsion force based on potential field method is given to make the coverage operation feasible in complex environments in the presence of unknown obstacles. Section “Simulation results” demonstrates the effectiveness and feasibility of the proposed approach via computer simulations, performed on a team of USVs. Section “Conclusion” summarizes the article and draws some conclusions.

Problem formulation

This article studies the problem of detecting underwater target in a fixed water area by cooperation of multi-USV under ideal conditions .Therefore, the following assumptions are given:

Assumption 1

The total number of USVs is N and $i \in I_{N} = {1, 2, 3, \dots, N}$ . The communication of multi-USV system is fully connected.

Assumption 2

The water surface is smooth, and every USV moves on a plane.

Assumption 3

The detection probability of the on-board sensor is 100%, that is, the detection probability of the sensor detection equipment has no effect on the results.

Assumption 4

The sensing range of each agent is a limited circular area, the divergence angle of detector is $θ_{i}$ , the detection depth is h_i, then the sensing radius is R_i, as shown in Figure 1.

Figure 1.

Diagram of the circle sensing region.

The sensing area model of agent $A_{i}$ can be specifically described as follows

Ω_{i} ({\vec{A}}_{i}, θ) = {q \in S : ‖ \vec{q} - {\vec{q}}_{i} ‖ \leq R_{i}}

(1)

where $q \in S$ represents the point within the sensing range $Ω_{i}$ of the ith USV and S represents the given area to be covered on $OXY$ plane.

Assumption 5

Within the sensing range of the agent, the perceptual ability of all points is constant $c_{0}$ , for points outside the perception range, the perceptual ability of the agent is 0

g_{i} (h_{i}, q) = {\begin{matrix} c_{0} & , q \in Ω_{i} \\ 0 & , q \notin Ω_{i} \end{matrix}

(2)

Since the information accumulation of a point in the fixed area obtained by USV using the sensor increases with time, that is, the level of effective coverage of a point in the area increases with time, for any point $q \in Ω_{i}$ , the effective coverage of USV $A_{i}$ from the initial time $t = 0$ to t is defined as follows

γ_{i} (q, t) = \int_{0}^{t} g_{i} (h_{i}, q) d τ

(3)

Adaptive control law

The rationale of adaptive control law is to drive each agent to move toward the direction of low coverage level by establishing the potential energy function about the error between the expected coverage level and the actual coverage level, so as to complete the coverage task. Gradient descent method is often used to design control laws for agent.

Optimum coverage velocity

Let C^* be the desired attained effective coverage at all points $q \in S$ . The goal is to attain a network coverage of $γ_{I_{N}} (q, t) = C *$ for all points $q \in S$ at some time t. $γ_{I_{N}}$ means the summation of the coverage of each USV. Consider the following error function

J (t) = \int_{S} h (C * - γ_{I_{N}} (q, t)) d q

(4)

where $h (x)$ is a penalty function, which is twice differentiable, positive definite and strictly convex in the interval (0,*], That is, $h (x) > 0, h' (x) > 0$ , $h ″ (x) > 0, \forall x \in (0, C *]$ . And that satisfies $h (x) = h' (x) = h ″ (x) = 0$ for all $x \leq 0$ . When $J (t) = 0$ , it means that the coverage task in the sensing area Ω_i is completed.

To guarantee the coverage of the entire domain S with an effective coverage of C* under appropriate assumptions, USV has to move toward the area where $γ_{I_{N}} (q, t) < C *$ . In order to improve the coverage efficiency, the area coverage problem can be described as the optimization problem of seeking the minimum $J (t)$ in formula (5)^16,17

Minimize J (t) = \int_{S} h (C * - γ_{I_{N}} (q, t)) d q, q \in Ω_{i}

(5)

The gradient descent method can be used to solve formula (5) to obtain the optimal coverage speed of the USV. Therefore, the optimal coverage speed of the USV can be designed as follows

\begin{matrix} v_{i} (t) = - k_{c} \cdot \frac{dJ (t)}{dt} \\ = - k_{c} \cdot \int_{Ω_{i}} h' (C^{*} - γ_{i} (q, t)) g_{i} (z_{0}, q) d q \end{matrix}

(6)

where $k_{c} > 0$ is the fixed coverage velocity adjustment gain.

Since the optimal coverage speed of the USV is based on local information, when the points in the perception area of the USV are effectively covered, the USV will tend to be stationary. If the whole area has not been covered effectively at this point, a traction speed is required for the USV to avoid to get stuck in a local minimum.

First, the points in the task area that are not covered effectively are defined as the following set

Ω_{e} (t) = {q \in S : 0 < γ_{I_{N}} (q, t) < C *}

(7)

Set $Ω_{e} (t)$ represents a set of points that are not effectively covered in the area S at time t. Let ${\bar{Ω}}_{e} (t)$ be the closure of set $Ω_{e} (t)$ . For agent $A_{i}$ , let ${\hat{Ω}}_{e}^{i} (t)$ be the set of points with the shortest distance from $q_{i} (t)$ in set ${\bar{Ω}}_{e} (t)$ , that is

{\hat{Ω}}_{e}^{i} (t) = {q * \in {\bar{Ω}}_{e} (t) : q * = argmi n_{q \in {\bar{Ω}}_{e} (t)} | | q_{i} - q | |}

(8)

A rule can be set to choose a unique point from the set to calculate the speed of the USV at the next moment. The traction speed ${\vec{v}}_{s}$ of the agent can be designed according to the artificial potential field method^19,20 as follows

\begin{matrix} {\vec{v}}_{s} = - k_{t} \cdot ({\vec{q}}_{i} - {\vec{q}}_{m}), & k_{t} > 0 \end{matrix}

(9)

where $k_{t} > 0$ is the traction velocity adjustment gain, ${\vec{q}}_{i}$ is the position vector of the USV projected on the $OXY$ plane, and ${\vec{q}}_{m}$ is the position vector of point $q_{m} \in S$ on the $OXY$ plane.

In summary, the expected optimal coverage velocity of each USV in multi-USV system is

{\vec{v}}_{i}^{*} = {\begin{matrix} \begin{matrix} - k_{c} \cdot \frac{dJ (t)}{dt} \\ - k_{t} \cdot ({\vec{q}}_{i} - {\vec{q}}_{m}), \end{matrix} & \begin{matrix} 0 < γ_{i} < C^{*} \\ γ_{i} = C^{*} and J (t) \neq 0 \end{matrix} \end{matrix}

(10)

Repulsion

We now return to the fully connected network of multi-USV system. To avoid collision, it is necessary to consider a control strategy that ensures that the distances between two USVs or between USV and obstacle are not too close.

In order to ensure the safety of the USV navigation mission, local obstacle avoidance path planning algorithm is used for autonomous obstacle avoidance. The avoidance process of USV can be divided into the following steps:

Identify obstacles within the perception range by sensors;

Calculate the relative distance and speed between the USV and the obstacle;

Establish a local coordinate system and determine if it is in a dangerous area;

If it is in a dangerous area, take corresponding measures to avoid collision; otherwise, continue to navigate.

The main idea of collision avoidance algorithm is to measure the relative distance and speed of other nearby USVs and itself through the sensors carried by the USV. When the relative distance is less than the safe distance, calculate the velocity vector difference between the other USVs and itself, and determine whether it is in the dangerous area where collision may occur. If it is in the dangerous area, change its own velocity vector to get away from the dangerous area, so as to achieve the purpose of collision avoidance..

Assume two USVs navigate with velocity ${\vec{V}}_{A}$ and ${\vec{V}}_{B}$ , respectively. The relative velocity ${\vec{V}}_{AB} = {\vec{V}}_{A} - {\vec{V}}_{B}$ . R is the radius of a disk centered at the USV’s location in which other USVs and obstacles can be detected. r is the smallest safe distance between USV and other object. Let $α = \tan^{- 1} (r / R)$ , $β$ is the angle between relative velocity ${\vec{V}}_{AB}$ and X axis. And $α, β \in (0, 2 π]$ . The collision avoidance area division of USV is shown in Figure 2.

Figure 2.

The diagram of dangerous area.

The orange area and the blue area in Figure 2, respectively, represent the different types of dangerous area that means the collision would take place without velocity change. For local repulsion, we choose a simple half-spring model,²¹ that is, a linear distance-dependent central velocity term with a cutoff at a maximum interaction range. For collision avoidance, the repulsion law was designed as follows

{\vec{V}}_{r} = {\begin{matrix} k_{r} \cdot (R - d_{AB}) \frac{{\vec{r}}_{A} - {\vec{r}}_{B}}{d_{AB}} & , & r < d_{AB} \leq R & | β | < α \\ k_{r} \cdot (r - d_{AB}) \frac{{\vec{r}}_{A} - {\vec{r}}_{B}}{d_{AB}} & , & d_{AB} \leq r \\ 0 & , & otherwise \end{matrix}

(11)

where ${\vec{V}}_{r}$ is the repulsion velocity. ${\vec{r}}_{A}$ is the position vector of the USV A. ${\vec{r}}_{B}$ is the position vector of obstacle B or another USV. $d_{AB} = | {\vec{r}}_{A} - {\vec{r}}_{B} |$ is the distance between USV A and obstacle B.

According to the above content, the pseudo-code of the adaptive control law of the multi-USV system is presented as follows:

Algorithm 1: Adaptive control law of fixed area with unknown obstacles covered by multi-USV.
Input: coverage area S, initial state of multi-USV system, control gain parameters; Output: Output the optimal trajectory of each USV; 1: Initialization: establishing an USV object, and inputting initial position information and initial speed information of the USV; Gain parameters of control rate, etc: 2: Build a task area model: 3: Calculating respectively the motion state information of each USV A_i, i∈I_N, and setting the initial time k = 1; 4: while J(t) > 0 do 5: For each USV do 6: If H(t) ≠ 0; 7: Calculate the expected optimal speed of USV A_i, i∈I_N according to formula (6); 8: else 9: Calculate the expected optimal speed of USV A_i, i∈I_N according to formula (9); 10: End 11: Calculate the repulsion velocity according to formula (11); 12: Calculate the total velocity of USV; 13: Use formula (11) to calculate the acceleration U_i of USV A_i; 14: Calculate the actual speed of USV A_i at this time; 15: Calculate the position information X_i (k + 1) of the USV A_i at the next moment; 16: End 17: k = k + 1; 18: End

Algorithm 1: Adaptive control law of fixed area with unknown obstacles covered by multi-USV.

Input: coverage area S, initial state of multi-USV system, control gain parameters;
Output: Output the optimal trajectory of each USV;
1: Initialization: establishing an USV object, and inputting initial position information and initial speed information of the USV; Gain parameters of control rate, etc:
2: Build a task area model:
3: Calculating respectively the motion state information of each USV A_i, i∈I_N, and setting the initial time k = 1;
4: while J(t) > 0 do
5: For each USV do
6: If H(t) ≠ 0;
7: Calculate the expected optimal speed of USV A_i, i∈I_N according to formula (6);
8: else
9: Calculate the expected optimal speed of USV A_i, i∈I_N according to formula (9);
10: End
11: Calculate the repulsion velocity according to formula (11);
12: Calculate the total velocity of USV;
13: Use formula (11) to calculate the acceleration U_i of USV A_i;
14: Calculate the actual speed of USV A_i at this time;
15: Calculate the position information X_i (k + 1) of the USV A_i at the next moment;
16: End
17: k = k + 1;
18: End

Simulation results

In this section, we provide simulation results for the fully connected network case. Assume that task area S is a square region of side length d = 20 km. Let the desired effective coverage C^* be 60. The initial velocity of each USV is 0 m/s. To amplify the process of collision avoidance, Let the sensing radius of a USV R is 2 km, the safe radius r is 1 km. There are 6 USVs with initial deployment as shown in Table 1.

Table 1.

Initial conditions of agents.

Agents	Initial conditions (km)
A1	(1.2, 0.2)
A2	(6, 1)
A3	(7.2, 1.2)
A4	(1, 19)
A5	(19, 18)
A6	(19, 1)

The trajectories of these USVs at different times are shown in Figure 3.

Figure 3.

Trajectory of agents at different time: (a) trajectory of agents at t = 1 min, (b) trajectory of agents at t = 20 min,(c) trajectory of agents at t = 40 min, and (d) trajectory of agents at t = 56.88 min.

The coverage of the whole task area at different times is shown in Figure 4.

Figure 4.

Diagram of area coverage at different time: (a) coverage effect at t = 1 min, (b) coverage effect at t = 20 min,(c) coverage effect at t = 40 min, and (d) coverage effect at t = 56.88 min.

It can be seen from the trajectory of USVs at different times in Figure 3 that there is no one USV collides with the obstacles or go through the obstacles. Each USV can keep a safe distance from obstacles and other USVs. And all USVs can do their searching mission without beyond the boundaries. Clearly, as can be seen from Figure 4, the domain is completely covered in the limited time, which shows that the adaptive control law is feasible and effective in controlling the multi-USV system to complete the searching task of the designated area.

Conclusion

This article studies the rationale behind multi-USV adaptive searching system under the complex environment with unknown obstacles. The adaptive control law is given. The feasibility and effectiveness of the law are verified by numerical simulation. First, the sensing area of a single USV was defined. And then, the driving force of USV was designed by the error function between actual coverage in the sensing area of USV and the effective coverage. Therefore, each USV in the searching system was driven to the area with lower coverage. Second, the repulsion law of USV was designed to avoid collision with other objects. To improve the searching efficiency, the dangerous area was divided into 2 different parts in order to reduce total times of avoidance of the multi-USV system.

In conclusion, compared with the existing control law based on the global information, the adaptive searching law of multi-USV is more adaptive to execute the task in the complex environment with unknown obstacles. USV can automatically navigate and avoid the collision based on the local information in the sensing area of USV. Therefore, the multi-USV system with adaptive control law will be the trend of development in the application of searching task under the complex environment.

Footnotes

Handling Editor: Lyudmila Mihaylova

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This research was funded by the Scientific Research Staring Foundation of Shantou University (No: NTF19028).

ORCID iD

Ke Li

References

Grattan

KTV

Meggitt

. Optical fiber sensor technology. Opt Acta Int J Opt 2000; 42(4): 938.

Meixner

Jones

. Micro- and nanosensor technology: trends in sensor markets. Sensors 2008; 8: 275–293.

Nakai

Naitou

Kidera

. Control for vehicle navigational system. US20050128102A1 Patent, 2000.

Zhang

Liu

Yao

. Target assignment via switching scheme for multiple flight vehicles in cooperative guidance. In: Proceedings of the AIAA guidance, navigation, and control conference, Boston, MA, 19–22 August 2013. Reston, VA: American Institute of Aeronautics and Astronautics.

Chen

. Problems and countermeasures of maritime search and rescue. Water Transp Chin 2019; 19(8): 41–42.

Falcone

Borrelli

Asgari

, et al. Predictive active steering control for autonomous vehicle systems. IEEE Trans Control Syst Technol 2007; 15(3): 566–580.

Burciu

. Reliability and uncertainty in determining search area during search and rescue action. Pol Marit Res 2012; 19(1): 21–30.

Zweck

. Analysis of methods used to reconstruct the flight path of Malaysia Airlines flight 370. SIAM Rev 2016; 58(3): 555–574.

Cheng

Savkin

Javed

. Decentralized control of a group of mobile robots for deployment in sweep coverage. Robot Auton Syst 2011; 59(7–8): 497–507.

10.

Das

Fierro

Kumar

, et al. A vision-based formation control framework. IEEE Trans Robot Autom 2002; 18(5): 813–825.

11.

Cortés

JKT

Martínez

Bullo

. Spatially-distributed coverage optimization and control with limited-range interactions. ESAIM Control Optim Calc Var 2005; 11: 691–719.

12.

Wang

Cao

La Porta

. Movement-assisted sensor deployment. IEEE Trans Mob Comput 2006; 5(6): 640–652.

13.

Zhang

, et al. Optimal mileage based AGC dispatch of a GenCo. IEEE Trans Pow Syst 2020; 35(4): 2516–2526.

14.

Stergiopoulos

Tzes

. Cooperative positioning/orientation control of mobile heterogeneous anisotropic sensor networks for area coverage. In: Proceedings of the IEEE international conference on robotics & automation, Hong Kong, China, 31 May–7 June 2014, pp.1106–1111. New York: IEEE.

15.

Papatheodorou

Tzes

Stergiopoulos

. Collaborative visual area coverage using unmanned aerial vehicles, 2016, https://arxiv.org/pdf/1612.02065.pdf

16.

Fan

Fang

, et al. MOEA/D with angle-based constrained dominance principle for constrained multi-objective optimization problems. Appl Soft Comput 2019; 74(1): 621–633.

17.

Zhang

Tan

Zhou

, et al. Adaptive distributed auction-based algorithm for optimal mileage based AGC dispatch with high participation of renewable energy. Int J Electr Pow Energ Syst 2021; 124: 106371.

18.

Frappier

. A repeated Leibniz integral rule. Int J Pure Appl Math 2008; 44(2): 151–154.

19.

Zou

Fan

. Distributed fixed-time attitude coordination control for multiple rigid spacecraft. Int J Robust Nonlin Control 2020; 30(1): 266–281.

20.

Zou

. Fixed-time output-feedback consensus tracking control for second-order multi-USV systems. Int J Robust Nonlin Control 2019; 29(13): 4419–4434.

21.

Vásárhelyi

Virágh

Somorjai

, et al. Optimized flocking of autonomous drones in confined environments. Sci Robot 2018; 3: 1–13.