<figure><img src="image_1.png" /></figure>

HAL
open science

# Multi-robot Distributed Cooperative Monitoring of Mobile Targets

J. Q. Jiang, B. Xin, L. H. Dou, Y. L. Ding

► To cite this version:

J. Q. Jiang, B. Xin, L. H. Dou, Y. L. Ding. Multi-robot Distributed Cooperative Monitoring of Mobile Targets. 2nd International Conference on Intelligence Science (ICIS), Nov 2018, Beijing, China. pp.362-372, 10.1007/978-3-030-01313-4_39. hal-02118795

HAL Id: hal-02118795

https://inria.hal.science/hal-02118795

Submitted on 3 May 2019

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Multi-robot distributed cooperative monitoring of mobile
targets

J. Q. Jiang*, B. Xin**, L. H. Dou***, Y. L. Ding*

*School of Automation,
Beijing Institute of Technology
Beijing 100081,
China
976798059@qq.com, dingyvlong@163.com

**State Key Laboratory of Intelligent Control and Decision of Complex Systems
Beijing Institute of Technology
Beijing 100081,
China
brucebin@bit.edu.cn

***Beijing Advanced Innovation Center for Intelligent Robots and Systems
Beijing Institute of Technology
Beijing 100081,
China
doulihua@bit.edu.cn

**ABSTRACT.** Cooperative monitoring targets of mobile robots is of great importance in military, civil, and medical applications. In order to achieve multi-robot coordinated monitoring, this paper proposes a new distributed path planning algorithm. In this algorithm, a method of dynamic sequential decision making is used firstly to determine which robots should be moved to the neighbourhoods of the target path. A distributed cooperative path planning algorithm is then proposed in which the robots can only utilize their local information to make the joint monitoring areas of robots cover the target path. To reduce the chance of detection and ensure enough time to implement monitoring handover, our distributed algorithm can guarantee enough overlapped monitoring areas between adjacent robots. The effectiveness of the algorithm was verified by simulation experiments and a comparison experiment in typical scenarios.

**KEYWORDS:** Cooperative monitoring, Dynamic sequential decision making, Distributed coverage

# 1 Introduction

Target monitoring has a wide range of application prospects and potential economic value, including search and rescue program[9], path planning[6], decision problems of
different types of unmanned aerial and ground vehicles systems (UAGVS) [2], Dubins
Traveling Salesman Problem (DTSPN)[8] and Cooperative multi-area coverage
(CMAC)[7]. Khan et al. reviews control techniques for cooperative mobile robots
monitoring multiple targets[5]. In recent years, the problem has been studied
extensively in the centralized setting. Chakrabarty et al. [1] proposed a distributed
method which is used to monitor the targets using a robot network. They adopted a grid
coverage strategy. Although the targets can be monitored in a wider range, they used
too many robots and the cost is too high. Y. Fu et al. [4], distributed methods are used
to enhance the scalability of the network, reduce the communication costs, Y. Fu et al
[4] establish an integer programming model, and obtains the optimal value. But there
is no monitoring handover in their research, robots are easily found by the targets.

This paper will study the monitoring problem of multiple mobile robots for moving objects. Each robot needs to monitor an area. After the target (see the red car) moves, the monitoring handover takes place and the next robot continues to monitor. As shown in Figure 1.

<figure><img src="image_3.png" /><figcaption>**Figure 1.** Monitoring of moving targets by multiple mobile robots, the dotted circular area represents the monitoring range of the robot. The curve represents the path of the moving target</figcaption></figure>

This paper propose a novel distributed target monitoring algorithm. When solving this monitoring problem, we apply a decoupling strategy to decompose the problem into two subproblems: one is to select suitable robots and quickly move near the target by a distributed algorithm based on dynamic sequential decision making, and the other is to achieve the full coverage of the target trajectory by a distributed path planning algorithm. In addition, the distributed path planning algorithm can generate enough overlaps between the monitoring ranges of robots to effectively reduce the probability that robots is monitored and ensures enough time for robots to implement monitoring handover. As far as the author knows, target monitoring with monitoring handover has not been studied.

The paper is structured as follows. Section 1 introduces the research background and related work of cooperative target monitoring. Section 2 describes the problem and modelling. Section 3 introduces a algorithm based on sequential decision making. Section 4 proposes the distributed cooperative path planning algorithm of the robots. Section 5 gives the experimental results and analysis. Section 6 concludes the paper.
## 2 Problem Description

We consider a set of $n$ robots $S=\{s_1, s_2, \cdots, s_n\}$. Let $s_i^x, s_i^y$ and $R_i$ be the x-coordinate, y-coordinate and the monitoring radius of the robot $s_i$, respectively. We consider a set of $m$ targets $T = \{T_1, T_2, \cdots, T_m\}$. Let $T_j^x, T_j^y, V_j$ and $\theta$ be the x-coordinate, y-coordinate, the speed of the target $T_j$ and its horizontal angle, respectively.

The target path is modeled as multiple polyline segments. Note that if the target trajectory is an arbitrary curve, multiple polyline segments can approximate the curve. The objective function $g$ of the problem is the shortest movement distance for all robots, that is,

$$g = \min \left\{ \sum_{j=1}^{n} V_j \cdot t_j \right\} \qquad (1)$$

subject to:

$$\forall t, (T_i^x(t) - s_i^x(t))^2 + (T_i^y(t) - s_i^y(t))^2 \le R_i^2 \qquad (2)$$

$$\sum_{i=0}^{N_k} R_i \cdot \cos \theta_k \ge len_{r_k} + f, s_i \in T_k \qquad (3)$$

where $T_k$ is the set of robots for selecting the polygonal segment $r_k$, there are $N_k$ elements in $T_k$, and $f$ is the overlapped area between the all robots.

The constraint (2) indicates that the target is within the monitoring range of the robots, and can be monitored by the robots. Constraint (3) indicates that the length of the monitoring range projection of all the platforms which select a polygonal segment, is greater than the length of the polygonal segment. This problem confronts us with the following challenges:

(i) The problem is a mixed-variable optimization problem. Whether the platform or line segment is selected is an integer variable. The guiding position of the platform is a continuous variable.

(ii) There is a coupling relationship between selecting polyline segments and selecting monitoring points near the polyline segments for each robot.

## 3 Distributed cooperative path planning algorithm

In this section, a two-stage method is designed. The first stage is a distributed robot selection method based on sequential decision making, which can make the robots move towards the target path. The second stage is a robot cooperative path planning algorithm. The multi-robot monitoring areas fully cover target path.
## 3.1 Distributed robot selection method

The distance from each robot $s_i$ to each polygonal segment $r_k$ is denoted by $D_{i,k}$, and $D_{i,k}$ will be sorted by polyline segments. The distance $D_i$ from each robot $s_i$ to the target path is

$$D_i = \min_k D_{ik}. \qquad (4)$$

Each robot broadcasts its own distance $D_i$ to the target path to other robots. Each robot receives information from other robots and sorts them. In this way, each robot will get the same sequence of the robots selection polyline segments.

The $i$-th robot calculates the objective function for each polyline segment $r_k$ when selecting the appropriate polyline segment

$$g_k = \frac{slen_{r_k}}{R_i} \cdot d. \qquad (5)$$

In the above formula, $R_i$ is the radius of the monitoring range of the $i$-th robot. Then the $k$-th polyline segment is selected by the $i$-th robot, and

$$k = \arg \min \{g_k\}. \qquad (6)$$

After each robot selects a polyline segment, the remaining length of the polyline segment is updated to its original value minus the projection of the robot on the polyline, that is

$$slen_{r_k} \leftarrow slen_{r_k} - R_i \cdot \cos \theta_k. \qquad (7)$$

In the above formula, $\theta_k$ is the angle with the horizontal direction when the target moves on the $k$-th polyline segment.

At the same time, it is ensured that the length $R_i \cdot \cos \theta_k$ of the projection of the robots for selecting each polyline segment $r_k$ is larger than the length $len_{r_k}$ of the polyline segment. Also there is enough monitoring overlapping area between the robots, that is

$$\sum_{i=0}^{N_k} R_i \cdot \cos \theta_k \geq len_{r_k} + f, s_i \in T_k. \qquad (8)$$

In the above formula, $T_k$ is the set of robots for selecting the polygonal segment $r_k$, there are $N_k$ elements in $T_k$, and $f$ is the overlapped area between the all robots.

In order to shorten the robots' movement distance, the idea of dynamic sequential decision-making was introduced. When the length of a polyline segment is no more than 0 according to (7), that is $slen_{r_k} \leq 0$, all robots need to redetermine the selected
sequence. At this time, when calculating the distance $D_{i,k}$ of the polyline segments, all robots should remove the polyline segment whose length is reduced to 0 or less than 0.

Near the target motion path, two safety lines parallel to the path are generated, and randomly $N_k$ points are generated on two safety lines as the candidate monitoring points of the robots. Every robot needs to select the closest monitoring point and moves to it.

## 3.2 Multi-robot distributed cooperative path planning algorithm

The previous section completed selection of the polyline segments and the initial monitoring points on the safety lines near the polyline segments. In this section, we mainly design a distributed cooperative path planning algorithm [3], which will allow robots that have moved to the initial monitoring point to achieve full coverage of the target path through distributed cooperative path planning, and at the same time ensure that there is sufficient monitoring handover area. This paper models the problem of coverage of the target path by the robots’ monitoring area as a barrier coverage problem.

A line segment of length $L$ is used to represent the target path$[0, L]$ on the $x$ axis. There are $n$ robots, each of which is equivalent to one node $S_i$. In order to avoid separate considerations for the first robot and the last robot, we set two virtual robots $s_{-1}$ and $s_{n+1}$ on the left of $x=0$ and right of $x=L$, respectively. We denote $L_1$ as one of the multiple polyline segments of the target path, $L_2$ as the safety line nearby $L_1$, and $D$ as the vertical distance from the point on $L_2$ to $L_1$, $\theta$ as the angle between $L_1$ and the horizontal direction, $R$ is the radius of the robot guidance area, and $r$ as the radius of the robot monitoring area when projected onto a one-dimensional straight line, as shown in Figure 2.

$$r = \sqrt{R^2 - D^2} \cos \theta \qquad (9)$$

<figure><img src="image_4.png" /><figcaption>Figure 2. Coordinate transformation diagram</figcaption></figure>
At this time, all robots' sensing range is mapped to one dimension. Eftekhari et al. [3] studied the problem of covering a straight line with nodes with a length on a one-dimensional line when robots have an identical monitoring radius. In this study, we expand their previous work to make robots with different monitoring radius cover the straight line (the monitoring radius of robot $s_i$ is denoted as $r_i$). In addition, the robot $s_i$ ($i \in [-1, n+1]$) needs to judge whether the overlap between its monitoring areas and that of its neighbourhood satisfies Formula (3). Therefore, every robot needs to make decisions on whether and where to move according to the following conditions:

$$ \text{If } s_{i+1}^x - s_i^x \ge r_i + r_{i+1} + f \text{ and } s_i^x - s_{i-1}^x \le r_i + r_{i-1} + f, \text{ then } d = -1, s_i^x = s_i^x + vd $$

$$ \text{If } s_{i+1}^x - s_i^x \le r_i + r_{i+1} + f \text{ and } s_i^x - s_{i-1}^x \ge r_i + r_{i-1} + f, \text{ then } d = 1, s_i^x = s_i^x + vd $$

If $s_{i+1}^x - s_i^x \ge r_i + r_{i+1} + f$ and $s_i^x - s_{i-1}^x \ge r_i + r_{i-1} + f$, then $d = -1$, $s_i^x = s_i^x + vd$ where $d$ indicates the movement direction of the robot after each movement, $d = -1$ indicates that the robot moves to the left, $d = 1$ indicates that the robot moves to the right, $v$ is the movement speed of the robot, and $f$ is the projection of the overlapping area between the robots in $T_k$ on one dimension.

According to the above algorithm, full coverage of the target path can be achieved on each polyline segment, and sufficient monitoring of the handover area is ensured. However, at the turning point of each of the two polyline segments, the robots located at both ends of the two polyline segments do not have any interaction with each other, and there is no guarantee that there will be enough areas for monitoring handover. Therefore, The turning points of two polyline segments are also required to be analyzed. The schematic diagram at the turning point is shown in Figure 3, judging whether $|AB| + |BC| \ge f$ is satisfied or not.

<figure><img src="image_5.png" /><figcaption>Figure 3. Inflection point</figcaption></figure>

If $|AB| + |BC| \ge f$, two robots' positions do not need to be adjusted. If $|AB| + |BC| < f$, $s_1$ will move to the turning point B until $|AB| + |BC| \ge f$; If during the movement, the intersection with the guidance junction is no longer satisfied between the robot on the left side and $s_1$, $s_2$ should move to the turning point B until $|AB| + |BC| \ge f$. According to the above ideas, we proposed Algorithm 1.

**Algorithm 1** Improved barrier coverage algorithm based on mobile robots
1: for $k=1:q$

Set two virtual robots $s_{-1}$ and $s_{n+1}$

for $i=1:N_k$

if $s_i$ moved last stage

if there is a gap in the direction of movement before

$s_i$ move one unit toward the gap

else

$s_i$ do not move

end if

else if

if $s_{i+1}^x - s_i^x \ge r_i + r_{i+1} + f$ and $s_i^x - s_{i-1}^x \le r_i + r_{i-1} + f$

$s_i$ move one unit toward the left gap

else if $s_{i+1}^x - s_i^x \le r_i + r_{i+1} + f$ and $s_i^x - s_{i-1}^x \ge r_i + r_{i-1} + f$

$s_i$ move one unit toward the right gap

end if

else

if $s_{i+1}^x - s_i^x \ge r_i + r_{i+1} + f$ and $s_i^x - s_{i-1}^x \ge r_i + r_{i-1} + f$

$s_i$ move one unit toward the left gap

else

$s_i$ do not move

end if

end if

end for

end for

2: if the projection target path is fully covered

Convert the motion of the robots into a motion on a two-dimensional plane

else

Goto step1

end if

3: if the requirements for the guidance handover area at the turning point satisfy

end

else

Adjust the positions of the robots at the turning points, goto step3

end if
# 4 Comparative Experiment

In this section, we simulate the program, and obtain experimental results, then analyze the experimental results. Through comparison experiment, it is verified that we can shorten the movement distance of the robots by dynamic sequential decision making.

## 4.1 Experimental results

The experimental results are shown in Figure 4.a. The robots move to the safety line near the target path from their initial positions. The red line indicates the target path, the green line indicates the safety line near the target path, and the blue dots indicates the robot's initial positions, and the connections between the robots and the initial points on the safety line (grey line) represent the paths taken by each robot to reach its proper initial monitoring point.

<figure><img src="image_6.png" /><figcaption>**Figure 4.a** The results of the robots have selected the polyline segments.</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>**Figure 4.b** The target trajectory obtained after the robots has moved through distributed path planning algorithms</figcaption></figure>

From Figure 4.b, after the selection of the polyline segments based on the sequential decision making is completed, the robot most suitable for the initial monitoring point can be selected and moves towards the target path. Distributed and coordinated movement between the robots achieves full coverage of the target path. At the same time, it can ensure that two adjacent robots meet the requirements for monitoring overlapping areas. The experimental results is shown in Table 1.

<table><thead><tr><th>Target's number</th><th>Example</th><th>Robot's number</th><th>Total moving distance</th><th>Average distance per robot</th><th>Percentage per robot</th></tr></thead><tbody><tr><td rowspan="3">1</td><td>Example 1</td><td>12</td><td>1714.21</td><td>142.851</td><td>8.33%</td></tr><tr><td>Example 2</td><td>14</td><td>1621.84</td><td>115.846</td><td>7.14%</td></tr><tr><td>Example 3</td><td>13</td><td>1677.95</td><td>129.073</td><td>7.69%</td></tr><tr><td rowspan="3">2</td><td>Example 1</td><td>25</td><td>3676.01</td><td>147.0404</td><td>4%</td></tr><tr><td>Example 2</td><td>27</td><td>3800.16</td><td>140.747</td><td>3.7%</td></tr><tr><td>Example 3</td><td>27</td><td>3709.03</td><td>137.371</td><td>3.7%</td></tr><tr><td rowspan="3">3</td><td>Example 1</td><td>40</td><td>6443.7</td><td>161.0925</td><td>2.5%</td></tr><tr><td>Example 2</td><td>41</td><td>6018.23</td><td>146.786</td><td>2.44%</td></tr><tr><td>Example 3</td><td>42</td><td>6230.53</td><td>148.346</td><td>2.38%</td></tr></tbody></table>
<caption>**Table 1.** *Experimental result*</caption>

Percentage per robot in Table 1 is the ratio of average moving distance per robot and total moving distance of all robots. We expanded the number of targets from 1 to 3 for testing. From the above table, it can be seen that when the number of targets is 1, the robot has a shorter movement distance, but as the number of targets increases, the robot moving distance gradually increases because the initial position of the robot and the total number of robots in the space are fixed. When the number of targets increases, the available robots decrease, and the available robots' positions gradually move away from the target path, so the robot needs to move longer distance to the path.

**4.2 Dynamic decision sequence vs fixed decision sequence**

In Section 3, we mentioned the idea of dynamic sequential decision-making. If there is update of the order of platform selection in the solution, just a fixed order method is used. In this way, when the order is determined in the next phase, there is no practical meaning for the distance of robots to the polyline segment whose length is 0. Although the robots can still determine the order of selecting, the original task can still be completed, but the robot movement distance will increase, the value of the objective function will increase greatly. Table 2 shows the experimental results when a fixed sequential decision making is used.

<table><caption>**Table 2.** *Experimental results during fixed sequence decision making*</caption><thead><tr><th rowspan="2">Target's number</th><th rowspan="2">Example</th><th rowspan="2">Robot's number</th><th colspan="2">Movement distance</th><th rowspan="2">Percentage</th></tr><tr><th>Fixed sequence</th><th>Dynamic sequence</th></tr></thead><tbody><tr><td rowspan="3">1</td><td>Example 1</td><td>15</td><td>3618.21</td><td>1714.21</td><td>47.38%</td></tr><tr><td>Example 2</td><td>14</td><td>3414.95</td><td>1621.84</td><td>47.49%</td></tr><tr><td>Example 3</td><td>15</td><td>4464.26</td><td>1677.95</td><td>37.59%</td></tr><tr><td rowspan="3">2</td><td>Example 1</td><td>28</td><td>5903.12</td><td>3676.01</td><td>62.27%</td></tr><tr><td>Example 2</td><td>29</td><td>7163.65</td><td>3800.16</td><td>53.05%</td></tr><tr><td>Example 3</td><td>30</td><td>7369.85</td><td>3709.03</td><td>50.33%</td></tr><tr><td rowspan="3">3</td><td>Example 1</td><td>46</td><td>9575.96</td><td>6443.7</td><td>67.29%</td></tr><tr><td>Example 2</td><td>43</td><td>9121.53</td><td>6018.23</td><td>65.98%</td></tr><tr><td>Example 3</td><td>44</td><td>10756.4</td><td>6230.53</td><td>57.92%</td></tr></tbody></table>

The percentage in Table 2 refers to the ratio of the robot's movement distance in the fixed sequential decision making to the robot's movement distance in the dynamic sequential decision making. By comparison with Table 1, it can be seen that when the fixed sequential decision is made, the robot's movement distance is always longer than making the dynamic sequential decision making (see Table 2), no matter how many the target is. Because the number of robots in space is increasing, when the number of
targets increases, the distance of dynamic sequential decision-making moves closer to
a fixed sequential decision making. But it is always shorter than fixed-order decision-
making. Therefore, it can be concluded that dynamic sequential decision making is
beneficial to shorten the robot's movement distance.

5 Conclusion

This paper studies the cooperative monitoring problem for multiple moving
robots, and proposes a strategy for multiple robots to achieve full coverage of the target
path, so that the intrusion targets can be monitored by the robots in real time. An
in-depth analysis is performed on the comparison of the time of the robots moving
to the monitoring points and the time when the targets moved to the same
monitoring points.

6 Acknowledgment

This work was supported in part by the National Natural Science Foundation
of China under Grant 61673058, in part by NSFC-Zhejiang Joint Fund for the
Integration of Industrialization and Informatization under Grant U1609214, in
part by the Foundation for Innovative Research Groups of the National Natural
Science Foundation of China under Grant 61621063, in part by the Projects of
Major International (Regional) Joint Research Program NSFC under Grant
61720106011, and in part by International Graduate Exchange Program of
Beijing Institute of Technology.

References

1. Chakrabarty, K., Iyengar, S. S., Qi, H., et al., "Grid Coverage for Monitoring and Target Location in Distributed Sensor Networks", vol. 51, no. 12, pp. 1448-1453, IEEE Transactions on Computers, 2002.

2. Chen, J., Zhang, X., Xin, B., Fang, H., "Coordination between unmanned aerial and ground vehicles: A taxonomy and optimization perspective", vol. 46, no. 4, pp. 959-972, IEEE Transactions on Cybernetics, Apr. 2016.

3. Eftekhari, M., Kranakis, E., Krizanc, D., et al., "Distributed algorithms for barrier coverage using relocatable sensors", vol. 29, no. 5, pp. 361-376, Distributed Computing, 2013.

4. Fu, Y., Ling, Q., Tian, Z., "Distributed sensor allocation for multi-target pathing in wireless sensor networks", vol. 48, no. 4, pp. 3538-3553, IEEE Transactions on Aerospace & Electronic Systems, Oct. 2012.

5. Khan, A., Rinner, B., Cavallaro, A., "Cooperative Robots to Observe Moving Targets: Review", vol. 48, no. 1, pp. 187-198, IEEE Transactions on Cybernetics, 2016.

6. Qi, M. F., Dou, L. H., Xin, B., et al., "Optimal path planning for an unmanned aerial vehicle under navigation relayed by multiple stations to intercept a moving target", pp. 2744-2749, 56th IEEE Conference on Decision and Control, 2017.
7. Xin, B., Gao, G. Q., Ding, Y. L., et al., "Distributed multi-robot motion planning for cooperative multi-area coverage", pp. 361-366, IEEE International Conference on Control and Automation, Aug. 2017.

8. Zhang, X., Chen, J., Xin, B., et al., "A memetic algorithm for path planning of curvature-constrained UAVs performing surveillance of multiple ground targets", vol. 27, no. 3, pp. 622-633, Chinese Journal of Aeronautics, 2014.

9. Zhao, W., Meng, Q., Chung, P. W. H., "A heuristic distributed task allocation method for multivehicle multitask problems and its application to search and rescue scenario", vol. 46, no. 4, pp. 902-915, IEEE Transactions on Cybernetics, Apr. 2016.