An Efficient Distributed Area Division Method for Cooperative Monitoring Applications with Multiple UAVs

Abstract

This article addresses the area division problem in a distributed manner providing a solution for cooperative monitoring missions with multiple UAVs. Starting from a sub-optimal area division, a distributed online algorithm is presented to accelerate the convergence of the system to the optimal solution, following a frequency-based approach. Based on the "coordination variables" concept and on a strict neighborhood relation to share information (left, right, above and below neighbors), this technique defines a distributed division protocol to determine coherently the size and shape of the sub-area assigned to each UAV. Theoretically, the convergence time of the proposed solution depends linearly on the number of UAVs. Validation results, comparing the proposed approach with other distributed techniques, are provided to evaluate and analyze its performance following a convergence time criterion.

Keywords: area division; coordination variables; distributed system; frequency-based approach; monitoring; multi-UAV; unmanned aerial vehicles.

Figure 1

A team of 6 UAVs in charge of monitoring a given area in a cooperative manner.

Figure 2

Area division between two identical agents. Yellow, blue and gray indicate the area assigned to the first UAV, the second UAV and unassigned, respectively. Image on the left shows a sub-optimal division where $S_1\cup S_2\ne S$. Image in the middle shows a sub-optimal division because $S_1\cap S_2\ne \varnothing$. Image on the right shows an optimal area division matching the conditions shown in Equation (1).

Figure 3

The area is divided into 6 non-overlapping sub-areas which are assigned to the different UAVs.

Figure 4

Area division and grouping depending on the side with respect to the sub-area assigned to the UAV $Q_i$, considering a $4\times 5$ grid configuration.

Figure 5

A synchronized multi-UAV system performing an area partitioning strategy, where neighbor UAVs patrol their closed paths in opposite directions. Each UAV meets periodically with each of its neighbors.

Figure 6

Area division protocol used by each UAV $Q_i$ to self-assign its own sub-area $S_i$. For each step, gray lines are used to make divisions and the green polygon is the chosen one.

Figure 7

Required peer-to-peer communications to share an information between the two farthest UAVs, considering a $4\times 5$ grid configuration.

Figure 8

Initial area division considered during the simulations. The solid black lines define the irregular area to monitor. The dashed black lines determine the initial sub-areas assigned to the UAVs and the dashed blue lines their initial coverage paths generated using the path planning method proposed in Acevedo et al. [23].

Figure 9

Evolution along the time of the maximum difference between the assigned area and the optimal one, using different coordination methods. The gray dashed lines determine a maximum relative difference of 10%, 5% and 1%

Figure 10

Final area division obtained during the simulation using the coordination algorithms: (a) based on the one-to-one coordination, and (b) based on the (2,2)-block-sharing strategy. (c) based on the column-row decoupling, and (d) based on the coordination variables. The dashed red lines determine the final sub-area shapes assigned to the UAVs, the dashed blue lines indicate their coverage paths generated using the path planning method proposed in Acevedo et al. [23] and the thick dashed black circles highlight two examples of the edges of shapes of the computed sub-areas.

Figure 11

Average number of meetings (±its standard deviation) required to converge to the specified area partition strategy depending on the number of UAVs and considering a $1\times c$ configuration and different coordination algorithms.

Figure 12

Average number of meetings (±its standard deviation) required to converge to the specified area partition strategy considering a $r\times r$ configuration and depending on the number of UAVs and different coordination algorithms.