TIME-OPTIMAL MINEFIELD COVERAGE BY AIR-SEA COOPERATION FOR MINE COUNTERMEASURE TASK

​ABSTRACT

To enhance the efficiency of a mine countermeasure task utilizing unmanned groups, a time-optimal coverage planning algorithm is proposed. Considering the speed advantage of unmanned aerial vehicles (UAV), a UAV group is assigned for reconnoitering the region of interest. The Gaussian process regression method is applied to estimate the mine distribution. Meanwhile, in order to improve the operational efficiency, the cost function is designed based on speed weighted Voronoi partitions for optimal coverage configuration. In addition, this paper further considers the effect of the underactuated kinematic model of the unmanned surface vessel. Based on the proposed speed weighted Voronoi partitions, each unmanned surface vessel is driven to weighted centroid of its own partition to minimize the temporal cost of mine-elimination task. The time consumption of mine countermeasure task is optimized by taking the unmanned surface vessel’s maneuverability into account. Finally, the effectiveness of the proposed method is demonstrated by numerical simulations. Compared with the traditional coverage method, the proposed method performs advantages in mine countermeasure efficiency.

Keywords: Gaussian process regression (GPR), time optimal coverage, speed difference, sea- air cooperation, under-actuated unmanned surface vessel (USV)

1. Introduction

Mine countermeasures currently face high risks, low efficiency and complex processes due to their concealment, ease of deployment, and high cost effectiveness [1]. In the future of naval warfare, in order to ensure that operations are not affected by the threat of mines, speed has become the first key to anti-mine operations [2]. Compared to traditional large mine hunting vessels, unmanned anti-mine equipment has many advantages such as zero casualties, high mobility and low cost [3]. For example, mine detection drones can quickly scan the minefield and generate a clearer distribution of mines, while mine suppression drones can carry large mine suppression equipment to perform mine hunting and sweeping tasks. In order to give full play to the advantages of the capabilities of unmanned aircraft, boats and other air and sea heterogeneous equipment, it is necessary to optimise the design of air-sea coordinated anti-mine programmes to complete the reconnaissance and coverage of mined areas, so as to achieve efficient mine clearance.

Existing studies generally divide a given area by designing a coverage cost function and perform trajectory planning to drive the intelligences to the optimal location. Cortés et al [4] first used the vino partitioning method in the coverage problem and proved that the center of mass of each vino cell is the optimal sensing location. On this basis, a large number of scholars have conducted research on various factors affecting coverage control, such as coverage area characteristics [5], intelligent body dynamics models [6] and specific task requirements [7]. In order to give full play to the advantages of heterogeneous equipment capabilities, such as the manoeuvring capability of UAVs and the carrying capability of unmanned boats, it is necessary to further study the coverage problem of heterogeneous multi-intelligent bodies. At present, studies on the coverage problem of heterogeneous smart bodies consider attributes such as smart body dynamics [8, 9], energy consumption [10], and sensing capabilities [11, 12]. Such studies focus on adjusting the cost function in the coverage cost and the partitioning of the coverage according to the performance differences of heterogeneous intelligences to meet different mission requirements. In anti-mine missions, rapidity is the first priority. Therefore, the manoeuvrability of unmanned equipment becomes a key factor influencing the design of the coverage planning algorithm. In the literature [13] and [14], the individual capability differences of the intelligences are considered in the design of the algorithm, and the boundaries of each partition are adjusted by an additive weighted Venn diagram so that the dominant area size of the intelligences is positively correlated with their capability attributes. In order to ensure the rapidity of the process, this paper takes the manoeuvring capability of the unmanned boat as the main basis for the division of the dominant area, and proposes a speed multiplication weighted Vino partitioning method, so as to adapt to the anti-mine task requirements.

In addition, the prerequisite for unmanned boat formations to perform mine hunting missions is the initial acquisition of the mine distribution posture, which corresponds to the density function of key information in the area in the coverage problem. Existing studies generally predict the density function within the target area through algorithms such as Gaussian estimation and Bayesian estimation, which enable modelling of environmental information. However, the above algorithms are difficult to balance the elements of estimation accuracy, computational complexity and estimation time , and cannot be directly applied to mine distribution estimation in the minefield reconnaissance process. The Gaussian Process Regression (GPR) algorithm is a non-parametric Bayesian machine learning method that is able to predict unknown functions using partially sampled data while taking into account observation noise. The study provides high-precision prediction of environmental density functions based on the variance properties of the GPR algorithm to provide support for optimal area coverage. This paper applies the Gaussian process regression algorithm to estimate the mine distribution density function based on the sampling data acquired by the UAV formation during reconnaissance, providing key situational information for the mine suppression task of the UAV formation.

2. Algorithm design

2.1 Optimal coverage planning based on multiplicative weighting of speed differences

Landing on water is a two-phase flow problem involving two impermeable media, i.e., water and air. Among many multiphase flow models, the VOF method[4]is relatively simple and stable. Therefore, this paper adopts the VOF method to capture the liquid level. VOF method, also called fluid volume fraction method, uses the ratio of fluid volume in the grid cell to the grid volume to determine the position of the free liquid surface.

Figure 1. Sea-air cooperation mine countermeasures scenario

The key to improving the efficiency of mine destruction is to minimise the time it takes for random point  to be responded to, i.e. to match each point in the plane with an unmanned boat that can reach it as quickly as possible at full speed. Therefore, in order to fully utilise the manoeuvrability of the unmanned boat, the faster unmanned boat should be responsible for monitoring a larger area, thus increasing the overall mine clearance efficiency. Defining the time for the ith unmanned boat to move to any point in the dominant area as , the time-optimal boundary condition is introduced in the definition of the Vino partition as:

                                              （1）

In general, the distribution of unmanned boat formations in the target area is relatively sparse, so the area that the  unmanned boat can reach per unit time can be approximated by its maximum speed :

where  denotes the distance from the current position  of the unmanned boat to any target position . As a result, each Vino partition can be further expressed as

Here  represents a multiplicatively weighted Vino region which uses time instead of distance as a boundary condition and takes the reciprocal of the maximum velocity  , as the weight of each region. By definition, if each unmanned boat has the same maximum velocity, this multiplicatively weighted Vino region will become the standard Vino region. The boundary line of each of the two multiplicatively weighted partitions is denoted byand is expressed as:

                                                    （2）

It can be seen that the boundary line is part of a circle,  is the centre of the circle, and  is the radius of the circle.

As mentioned earlier, the improvement of the coverage effect can be achieved by reducing its cost function. In addition to the optimised partitioning mentioned above, the location cost function in the cost function needs to be minimised by solving for:

                                                     （3）

Here  is the measured position cost function,  is the probability density value of the mine distribution,  is the dominant area covered by each unmanned boat, and  is the position coordinates of each unmanned boat, then . Using the gradient descent method to minimise the cost function (8) we have

By introducing different maximum velocities of the unmanned boats into the cost function and choosing the time cost  to replace the position cost, we have:

                                                       （4)

where  is the weighted multiplicative Vino region for which the unmanned boat gain is . The time cost can be interpreted as the sum of the squared time required for the UAV to reach each point in the Vino region in an integral sense.

In order to satisfy the objective of optimal coverage of potential minefields by unmanned boats, the time cost in (4) needs to be minimised using the gradient descent method. Since the time cost can be substituted for the location cost in the Vino region in (8), using a generalised multiplicative weighted location cost function to calculate the gradient, the global cost function can be defined as

                                                    (5)

Here  is the weight value of the multiplicatively weighted Vino partition dominated by each unmanned boat (i.e. the maximum speed value of each unmanned boat) and  is the gain on the distance function of unmanned boat i. Without loss of generality, it is assumed that the vector sets  and  contain vectors greater than 0. Also,  is the density function detected by each unmanned boat.

Figure 2. Standard Voronoi Diagram

Using the gradient descent method to minimise the cost function of the coverage control algorithm, the gradient expression of equation (10) can be simplified as:

                                                                (6)

 and  are the mass and centre of mass of the weighted multiplicative Vino region of the  unmanned boat, respectively. Assuming the single integral dynamics of the unmanned boat , the gradient descent controller of the ith unmanned boat based on the time cost is

                                                                  (7)

To facilitate subsequent calculations, the above controller is simplified while ensuring the maximum speed constraint of the unmanned boat. The controller in Eq. (7) multiplied by the gain , gives:

                                                                          (8)

Here  is chosen as the saturation function to ensure that the velocity of each unmanned boat moving is less than its maximum value, i.e.:

where  is the gain of the  unmanned boat until it reaches maximum speed.

Figure 3. Flowchart of sea-air cooperation time-optimal coverage algorithm

2.2 Trajectory tracking based on underdriven models

The kinematic equations for unmanned boats are:

As shown in Figure 4, assume that the position of the centre of mass of the weighted Vino region dominated by the   unmanned boat is  and its current actual position is  and define  as the angle between the line connecting the two coordinates and the horizontal direction:

Figure 4. Schematic diagram of ASV

Set the rotation matrix :

To solve for the tracking error, the following error equation is defined:

where θ is the given heading angle of the UAV motion, the UAV motion controller under the underdriven kinematic model is obtained as:

                                                                                           (9)

                                                                           (10)

Here  are the linear and angular velocity control gains for the ith unmanned boat, respectively. With controllers (9) and (10), the unmanned boat using the underdriven kinematic model eventually converges to the centre-of-mass position of the weighted Vino partition.

3. Simulation experiments and analysis

The specific experimental setup is as follows: four mines are randomly distributed in a region with coordinates in the range x,y∈[0,500]. The coordinates of the initial positions of the six unmanned boats to be covered are set as follows:

All unmanned boats have the same configuration except for speed. Assuming that the minimum speed of the unmanned boat is the unit speed, the maximum speed of the unmanned boat formation can be expressed as  and, in addition, the controller gains  for linear and angular velocities.

3.1 Analysis of the effect of Gaussian process regression in estimating mine posture

Figure 5 shows the water mine posture diagram, where Figure 5(a) shows the reference values of the set water mine posture distribution. The colour and height gradients in the graph indicate the change in the probability of the presence of mines, which is proportional to the height in the vertical direction.

5(a) Realistic mine distribution map                                 5(b) Estimated probability

                                                                                            density distribution of GPR mines

5(c) GPR error estimation diagram

Figure 5．Mine Distribution map

It is assumed that the distribution of mines detected by the UAV is as follows:

Figure 5(b) shows a plot of the mine distribution dynamics created by the UAV from the sampled data through a Gaussian process regression algorithm. Figure 5(c) shows the GPR estimation error distribution, where the difference from the true value is only 3.5% at the maximum value of the estimation error. Thus, the GPR algorithm is able to provide highly accurate offline estimates of the mine distribution density based on the sampled data.

3.2 Comparison of overlay algorithms

To verify the effectiveness of the algorithm proposed in this paper, the performance of the three coverage algorithms is compared in this paper for the application of speed-differentiated unmanned boat formations. As shown in Figure 6, the unmanned boat formations form three different coverage configurations and movement paths with the same initial position. In Figure 6, the colour gradient is the mine distribution density estimated by the GPR algorithm in Section 3.1. In Figure 6(a), the unmanned boat uses standard Vino partitioning for area coverage. In Figure 6(b), the minefield partitioning algorithm with speed as the weight takes full advantage of the manoeuvrability of the unmanned boat formations and the smoother movement path of the unmanned boats. The faster UAV 3 covers a significantly larger area than the slower UAV 1. Building on Figure 6(b), Figure 6(c) further considers the constraints of the UAV underdriven kinematic model. Compared to the trajectory in Fig. 6(b) using the full-drive kinematic model, the trajectory of the unmanned boat in Fig. 6(c) has a turning radius, which is more suitable for practical application scenarios.

6(a) Standard Vino zoning overlay

6(b) Speed adaptive zoning overlay map

6(c) Underdriven Speed Adaptive Partition Overlay 

Figure 6. unmanned surface vessel coverage result map

4. Summary

The paper proposes an optimal coverage planning algorithm based on the multiplicative weighting of the speed difference, which provides a basis for optimal coverage through fast sampling of the minefield by the UAV and the estimation of the mine distribution trend using Gaussian process regression, and then designs a time-optimal coverage strategy with the multiplicative weighting of the speed by taking into account the difference in the manoeuvrability of the UAV formation and the underdrive characteristics. Simulation results show that the proposed method can generate mine distribution patterns with small estimation errors in the mine detection phase, and in the mine destruction phase, the unmanned boat can visit any mine location in the area as fast as possible in a probabilistic sense through the time-optimal coverage configuration. Compared with traditional coverage strategies that do not take into account speed variability, the method proposed in this paper gives full play to the mobility of heterogeneous equipment, resulting in a significant increase in mine destruction efficiency, and can provide strategic support for future unmanned anti-mine operations.

References:

1. J. Cortes, S. Martinez, T. Karatas and F. Bullo, "Coverage control for mobile sensing networks," in IEEE Transactions on Robotics and Automation, vol. 20, no. 2, pp. 243-255, April 2004.
2. А. Breitenmoser, M. Schwager, J. -C. Metzger, R. Siegwart and D. Rus, "Voronoi coverage of non-convex environments with a group of networked robots," 2010 IEEE International Conference on Robotics and Automation, Anchorage, AK, USA, 2010, pp. 4982-4989.
3. H. Mahboubi, J. Habibi, A. G. Aghdam and K. Sayrafian-Pour, "Distributed coverage optimization in a network of static and mobile sensors," 2013 American Control Conference, Washington, DC, USA, 2013, pp. 6877-6881.
4. Y. Ru and S. Martinez, "Coverage control in constant flow environments based on a mixed energy-time metric," 2012 IEEE 51st IEEE Conference on Decision and Control (CDC), Maui, HI, USA, 2012, pp. 112-117.
5. Q. Wang, Y. Z. Hua, X. W. Dong, P. X. Shu, J. H. Lu, and Z. Ren, "Finite-Time Time-Varying Formation Tracking for Heterogeneous Nonlinear Multiagent Systems Using Adaptive Output Regulation,” Ieee Transactions on Cybernetics.
6. А. Kwok and S. Martinez, "Deployment algorithms for a power-constrained mobile sensor network," 2008 IEEE International Conference on Robotics and Automation, Pasadena, CA, USA, 2008, pp. 140-145.
7. M. Santos and M. Egerstedt, "Coverage Control for Multi-Robot Teams with Heterogeneous Sensing Capabilities Using Limited Communications," 2018 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Madrid, Spain, 2018, pp. 5313-5319.
8. B. Reily, T. Mott, and H. Zhang, “Adaptation to Team Composition Changes for Heterogeneous Multi-Robot Sensor Coverage,” in 2021 IEEE International Conference on Robotics and Automation (ICRA), 2021, pp. 9051-9057.
9. А. Pierson, L. C. Figueiredo, L. C. A. Pimenta and M. Schwager, "Adapting to performance variations in multi-robot coverage," 2015 IEEE International Conference on Robotics and Automation (ICRA), Seattle, WA, USA, 2015, pp. 415-420.
10. Pierson A, Figueiredo LC, Pimenta LC, Schwager M. "Adapting to sensing and actuation variations in multi-robot coverage," The International Journal of Robotics Research. 2017, pp.337-354.
11. W. Luo and K. Sycara, "Adaptive Sampling and Online Learning in Multi-Robot Sensor Coverage with Mixture of Gaussian Processes," 2018 IEEE International Conference on Robotics and Automation (ICRA), Brisbane, QLD, Australia, 2018, pp. 6359-6364.
12. Xu Y,Choi J, Dass S. and Maiti T. "Effcient bayesian spatial prediction with mobilesensor networks using gaussian markov random felds. Automatica," 2013, pp. 3520-3530.
13. J. Fink and V. Kumar, "Online methods for radio signal mapping with mobile robots," 2010 IEEE International Conference on Robotics and Automation, Anchorage, AK, USA, 2010, pp. 1940-1945.
14. А. Benevento, M. Santos, G. Notarstefano, K. Paynabar, M. Bloch and M. Egerstedt, "Multi-Robot Coordination for Estimation and Coverage of Unknown Spatial Fields," 2020 IEEE International Conference on Robotics and Automation (ICRA), Paris, France, 2020, pp. 7740-7746.