Distributed Approach for Coverage and Patrolling Missions with a Team of Heterogeneous Aerial Robots under Communication Constraints

Abstract

Using aerial robots in area coverage applications is an emerging topic. These applications need a coverage path planning algorithm and a coordinated patrolling plan. This paper proposes a distributed approach to coordinate a team of heterogeneous UAVs cooperating efficiently in patrolling missions around irregular areas, with low communication ranges and memory storage requirements. Hence it can be used with small-scale UAVs with limited and different capabilities. The presented system uses a modular architecture and solves the problem by dividing the area between all the robots according to their capabilities. Each aerial robot performs a decomposition based algorithm to create covering paths and a ‘one-to-one’ coordination strategy to decide the path segment to patrol. The system is decentralized and fault-tolerant. It ensures a finite time to share information between all the robots and guarantees convergence to the desired steady state, based on the maximal minimum frequency criteria. A set of simulations with a team of quad-rotors is used to validate the approach.

Keywords

Multi-Robot Systems Aerial Robots

1. Introduction

In recent years, the use of unmanned aerial vehicles (UAVs) in surveillance and monitoring tasks has been increased significantly. Missions, such as area coverage, may be repetitive or dangerous and as such can be solved in a more efficient and safe way using a controlled fleet of UAVs, as is highlighted in Bernard et al. (2011); Maza et al. (2011).

Area and perimeter surveillance are some of the most well-known UAV applications. Perimeter surveillance missions can be approached as a patrolling mission along a defined path - the perimeter - as in Elmaliach et al. (2008). On the other hand, area surveillance missions could be divided in two different problems: an area coverage path planning problem and a patrolling mission along that path.

The patrolling mission is useful in monitoring and surveillance applications. In this mission, the area has to be covered again and again. A frequency-based patrolling approach involves the frequency of visits as the parameter to optimize. In this paper, the maximal minimum frequency will be minimized, as in Baseggio et al. (2010).

Coverage path planning tries to build an efficient path for the UAVs which ensures that every point in the area can be monitored from at least one position along the path, as in Huang (2001). Minimizing the path length will be the criterion to optimize.

Area coverage is used in many applications such as monitoring in natural, industrial or civilian environments Daniel et al. (2011), search and rescue missions in distressing situations Wong et al. (2010), automated inspections, planetary explorations, intruder detection, and domestic applications such as vacuum cleaning Zhang et al. (2007).

The area coverage problem with sensor networks has been widely studied in the literature: Di Giamberardino & Gabriele (2008); Gobel & Krzesinski (2008); Hung & Lui (2010); Kordari & Blankenship (2008); Li et al. (2009); Saravi & Kahaei (2011). In this case, the challenge is to maximize the area to cover with a given amount of sensors, assuming a defined coverage range for each sensor. In a multi-UAV system - each UAV equipped with communication, navigation and sense capabilities allowing it to become a node of the mobile sensor network which can be steered to the region of interest.

In this paper, as in Maza & Ollero (2007), the area coverage problem is proposed with a team of aerial mobile robots. Then, the objective is not to maximize the covered area, but to minimize the time in which the whole area is monitored. A second objective could be to reduce the overlapping or redundancy in the covered area.

The multi-UAV approach potentially offers some technical benefits, such as easy and fast deployment, higher spatial coverage, ability to run repetitive missions, robustness against robot failures, etc. In addition, a multi-UAV system can perform the area coverage faster than a single UAV, as shown in Hazon et al. (2006).

So, the use of fleets of small UAVs in the surveillance problem, as in Beard et al. (2006) potentially increases the efficiency of the system to complete the mission. However, UAVs have limited communication range and memory capacity. Additionally, as they are more fragile, the loss of any UAV during the mission is more probable. Then, the coordination problem between all the robots, assuming that limitations, is an interesting issue.

The coordination problem involves two challenges: ‘What information should the UAVs interchange?' and ‘How should each UAV read that information?’ The ‘coordination variables’ and ‘coordination functions’, defined in McLain & Beard (2003), can be used to solve the problem. In this paper a ‘one-to-one’ strategy, where each pair of neighbours solve an independent coordination problem, is applied to obtain the whole team cooperation in the mission. In the previous work Acevedo et al. (2012) this approach is used for simple area surveillance and considering a homogeneous team of robots and rectangular areas without obstacles.

In this paper it is assumed that the UAVs can be heterogeneous since they can have different capabilities, such as different speeds, as in Meuth et al. (2009). The area coverage mission can be divided into sub-area coverage tasks and assigned to the UAVs depending of their capabilities.

Therefore, a distributed and decentralized approach, where each UAV can survey a section of the coverage path in an independent but coordinated way, is proposed in this paper. The presented algorithm forces UAV meetings where they exchange the minimum necessary information. The system allows obtaining an efficient, dynamic, fault-tolerant and scalable global solution from local algorithms. Also, it has to be robust to the loss of UAVs and adaptable to the UAVs' capabilities.

The paper is organized as follows. Section 2 summarizes other related work. Section 3 describes the adopted approach to optimize the solution and poses the problem to solve. Section 4 proposes an algorithm to coordinate the robots in the patrolling mission. Section 5 explains the coverage algorithm used to generate the covering path. Section 6 describes the proposed system for area and perimeter surveillance with aerial robots. Section 7 analyses the more important features of the obtained solution. Finally, section 8 offers some results of simulations to validate the approach and section 9 contains the conclusions and future developments.

2. Related work

The robot surveillance problem is the subject of many papers in the literature from designing a surveillance robot, as in Beainy & Commuri (2009), to proposing a complete frontier system to detect and avoid intruders, Darbha et al. (2010). In this paper, as in Bernard et al. (2011); Hsieh et al. (2007); Maza et al. (2011), the surveillance problem is approached using aerial systems.

The area coverage problem with mobile robots can be solved from two different approaches: on-line or off-line algorithms. In the on-line coverage algorithms the area to cover is unknown a priori, and step-by-step has to discover obstacles, compute their paths and avoid collisions. In Guruprasad et al. (2012), an on-line solution is proposed, in which both Voronoi spatial partitioning and coverage are handled in a distributed manner, with minimal communication overhead. On the other hand, in the off-line algorithms, as in Huang (2001), the robots have a map of the area and the obstacles, and can plan the path to cover the whole area.

Different approaches have been developed in the literature to solve area coverage path planning. Gabriely & Rimon (2001) and Hazon & Kaminka (2008) propose a method which creates a spanning tree and generate the coverage paths as the boundary around it. A neural network which creates a gradient field is proposed in Yang & Luo (2004), and the coverage path is obtained from the gradient field.

The Boustrophedon Cellular Decomposition, Choset & Pignon (1997), is one of the most well-known methods to obtain a coverage path. This technique implies the area division in smaller sub-areas that can be covered with a simple back and forth method. This method is extended to a multi-robot system with limited communications in I. Rekleitis & Choset (2004).

The use of a multi-robot system in the coverage problem has been addressed by many researchers in recent years. Hazon et al. (2006) proposes an on-line multi-robot algorithm based on approximation cell decomposition. Increasing the number of robots allows better performance and robustness when compared to single robot coverage. Multi-robot area coverage and patrolling has gained interest in recent years due to its relevance to various security applications. Many authors have focused on a frequency-based approach, maximizing the minimal frequency or guaranteeing uniform frequency, Elmaliach et al. (2008), or a maximal minimum frequency as in Baseggio et al. (2010), and others maximizing the chances of detecting an adversary trying to penetrate through the patrol path, Agmon et al. (2011).

In a similar way, authors such as Kingston et al. (2008) solve the patrolling mission using an approach based on ‘coordination variables’. The ‘coordination variables' can be defined as the minimum information that all the robots need to share to solve a problem in a coherent way from a distributed approach Ren (2006). Then, they allow coordinating the multi-robot system in a distributed and decentralized way to cooperate on common objectives using the minimum information exchange. The authors of Geng (2009) analyse how the ‘coordination variables' allow achieving consensus between the robots in few iterations. Based on the concept of ‘coordination variables’, but with less storage requirements, the ‘one-to-one' coordination is proposed in Acevedo et al. (2012) to solve an area surveillance mission with a team of homogeneous aerial robots in rectangular areas.

Other authors, as in Cheng & Dasgupta (2010); Cheng et al. (2009), address the area coverage problem with multiple robots using a team formation technique, i.e., a formation control instead of patrolling motion coordination.

Finally, given a set of aerial robots with different capabilities, the problem can be addressed as a coverage mission to divide into several different tasks to assign to the different robots according to their capabilities. So, the area coverage problem can be addressed as a task allocation problem, as proposed in Meuth et al. (2009) which uses probability decomposition in a system with different aerial and ground robots. In kook Yun & Rus (2010), the authors propose a decentralized task allocation to assign different workspaces to the robots. Also, other authors, as in Viguria et al. (2010), propose a distributed task allocation problem assuming communication constraints for surveillance missions with a group of aerial robots.

3. Frequency-based approach

A team of UAVs that has to monitor a defined area or perimeter to detect any unexpected event is considered. That event is assumed independent of the UAVs' motions, i.e., it is not an enemy which knows the defence strategy. Then, the probability f that an event happens in a position r without being detected can be defined as a Poisson Counter Process related to the elapsed time in that position since the last monitoring visit, h(r, t).

f (h (r, t)) = 1 - e^{- λ h (r, t)},

(1)

This definitions means that the probability f:ℝ→[0,1] that an event appears in a position is strictly increasing with the elapsed time. Now, assuming a path which covers the entire area or perimeter, this problem can be approached as a frequency-based patrolling mission.

A patrolling mission along a given path implies repetitive visits to any position along the path by the patrolling agents (in this case mobile aerial robots) to optimize a defined parameter.

A frequency-based approach looks for a solution where the parameter to optimize is the frequency of visit to the path positions. There are some different frequency-based performance criteria, for example:

Uniformity criteria, where the aim is to obtain the same minimum frequency for all the points along the path.

Average frequency, which tries to maximize the average frequency for all the points along the path.

Maximal minimum frequency where the aim is to maximize the minimum frequency in which any point along the path is monitored.

3.1 Problem formulation

A patrolling mission with a team of heterogeneous aerial mobile robots to monitor an entire area or perimeter can be formally described as follows (see Fig. 1):

Figure 1.

An area is surveyed by a team of quad-rotors with communication and storage limitations.

A set of N aerial mobile robots {A₁,A₂,…,A_N}. Each one A has defined its position at time t as p_i(t)∈ℝ³, which projection on the plane z = 0 is r_i(t)∈ℝ², and its maximum speed as ν_i^max

Each aerial robot A_i, at each time t, can monitor a limited area C_i ∈ ℝ²:

C_{i} (t) : = {r \in ℝ^{2} : | r - r_{i} (t) | < c (z_{i} (t))}

(2)

where c(z) defines as the coverage range of the aerial robot A.

The coverage range function c(z):ℝ⁺→ℝ is the same proportional function for all the aerial robots, with a proportionality constant related to its field of view angle θ. It is assumed a maximum altitude a^max to be able to monitor the area. Then, it can be defined as follows:

c (z) = {\begin{cases} z \cdot \tan (θ), if 0 < z \leq a^{\max} \\ 0, if z > a^{\max} \end{cases}

(3)

Each aerial robot A_i can compute the same closed path P_i to cover a defined area or perimeter S, based on its altitude z_i:

\begin{array}{r} {z_{i}, S} \to P^{\min} : {l (t) \in ℝ^{2}, t \in [0, T^{υ}]} \\ r_{i} (t) = l (t) \Rightarrow \cup_{t = 0}^{T^{υ}} C_{i} (t) \supseteq S, \forall i = 1, \dots, N \\ l (0) = l (T^{υ}) \end{array}

(4)

where T^v is the time that the robot takes to cover the whole path P^min at a speed ν. • Each aerial robot A_i can move along any path P in the direction d_i with a variable speed ν_i, verifying:

\begin{array}{r} \frac{d r_{i} (t)}{d t} = d_{i} (t) υ_{i} (t), \forall i = 1, 2, \dots, N \\ d_{i} (t) = {- 1, 1}, \\ υ_{i} (t) \in [0, υ_{i}^{\max}] \\ r_{i} (t) \in P \end{array}

(5)

where r_i(t) is the position in the path.

Each aerial robot A stores a local information vector infoi. A pair of aerial robots can only share their information vectors if they are within a communication range.

The same communication range is considered for all the robots, R, such that robot A contacts with another robot A_j if:

| p_{i} - p_{j} | < R_{c o m m} \Rightarrow A_{i} \leftrightarrow A_{j} .

(6)

The function h(r, t) is defined as the elapsed time from the last monitoring visit of a location r by any aerial robot. Hence

h (r, t) = {\begin{cases} {h (r, t - δ t) + δ t, if r \notin \cup_{i = 1}^{N} C_{i} (t), \\ 0, in other case \end{cases}

(7)

where δt→0⁺ and h(r,0)=0,∀r∈S

The criterion to solve the problem will be to obtain a motion planning for each robot A, such that the function h(r, t) is optimized on a frequency-based approach. In addition, another criterion will be to guarantee a continuous information interchange between all the teammates.

Figure 2.

An area is surveyed by a team of quad-rotors in an optimal manner.

3.2 Efficient solutions

Assuming a closed path defined as (4), a large enough communication range R_comm and a team of homogeneous aerial robots, where v_i^max = v_i^max = v_i^max,∀i,j it is possible to compute a solution which accomplishes jointly the uniform, average and maximal minimum frequency-based criteria. In this case, the optimal motion plan of the different robots require the next assumptions:

Each aerial robot A should fly with a constant altitude z_i(t) = a^max,∀t, which defines the same path P^min for all the robots to cover the whole area S.

Each aerial robot A_i has to move through the path P^minwith its maximum speed v_i(t) = v_i^max,∀t. So, all the robots cover the entire path P^min in the same time T^min.

All the aerial robots move - equally spaced - in the same direction along the path P^min. Then, all the robots cover the entire area S.

r_{i} (t) = r_{j} (t + n \frac{T^{\min}}{N}), \forall n \in ℕ, \forall i, j

(8)

where r(t)∈P^min,∀t≥0

Figure 2 shows a team of quad-rotors performing this solution.

In Acevedo et al. (2012), it is proved that the above solution minimizes the elapsed time since the last monitoring visit to all the positions along the path and that time can be computed as:

h^{o p t} = \frac{L (P^{\min})}{N υ^{\max}}

(9)

where L(P^min) is the path length.

The uniform point-visit frequency is defined as

The work described in this paper looks for an extension of Acevedo et al. (2012) to teams of heterogeneous aerial robots, i.e., it is possible that not all the aerial robots can move with the same maximum speeds v_imax^≠v_jmax,∀i,j.

Then, applying the previous solution implies either reducing the speeds of faster robots or adopting a solution without the slower robots. Namely, a fixed speed would be chosen, such as only the aerial robots with a greater speed could join the mission.

Assuming that the set of robots is ordered such as

ν₁^max ≤ ν₂^max ≤… ν_N^max, the problem is to choose the fixed speed ν^max which optimizes the frequency criteria.

υ^{\max} = υ_{i}^{\max} \to \frac{L (P^{\min})}{(N - i + 1) υ_{i}^{\max}} \leq \frac{L (P^{\min})}{(N - j + 1) υ_{j}^{\max}}, \forall j

(10)

On the other hand, assuming that the communication range is not large enough, the previous solution does not ensure a continuous information exchange between all the robots.

\exists t \in [0, T^{\min}] \to | l^{\min} (t) - l^{\min} (t + \frac{T^{\min}}{N}) | < R_{c o m m}

(11)

Then a different solution, where the neighbour robots contact periodically, is proposed.

Each aerial robot A has to fly with a constant altitude z_i(t)= a^max,∀t, which defines the same path P^min for all the robots to cover the whole area S.

Each aerial robot A_i should move along the path P^min with its maximum speed z_i (t)= a_i^max,∀t. So, all the robots cover the entire path P^minin the same time

Each. mobile robot Ai patrols only one segment P_i =[e_i-₁,e_i], such that

\begin{array}{l} P_{1} \cup P_{2} \cup \dots \cup P_{N} = P \\ P_{1} \cap P_{2} \cap \dots \cap P_{N} = \emptyset^{\cdot} \end{array}

(12)

The length L_i of the segment P_i covered for each mobile robot A is related to its own maximum speed ν_i^max by.

L_{i} = υ_{i}^{\max} \frac{L (P^{\min})}{Σ_{j = 1}^{N} υ_{j}^{\max}}, \forall i = 1, \dots, N,

(13)

Neighbour robots have to travel in different directions, d_j=-dj+1,∀t > 1.

The solution, keeping a periodical information interchange, is performed by a team of quad-rotors as shown in Fig. 3.

Figure 3.

An area is patrolled by a team of quad-rotors in an efficient manner maintaining a periodical information interchange.

Using this solution, each robot spends the same time covering its own segment

T^{'} = \frac{L_{i}}{υ_{i}^{\max}} = \frac{L (P^{\min})}{Σ_{j = 1}^{N} υ_{j}^{\max}} .

(14)

The motion plan cannot accomplish the uniform criteria, however, it tries to optimize the maximal minimum frequency criteria. Then, it is possible to calculate the maximum elapsed time.

In the steady state, each aerial robot covers its own segment P from an endpoint to the other endpoint. So, it reverses direction and travels to the first endpoint. This motion is continuously repeated. Then, the maximum elapsed time can be computed as the time in which the aerial robot covers its own segment P_i twice.

h_{o p t}^{\max} = 2 \frac{L (P^{\min})}{Σ_{j = 1}^{N} υ_{j}^{\max}} .

(15)

The above solution ensures the periodical information exchange between all the UAVs.

4. Distributed patrolling algorithm

A distributed and decentralized algorithm should guarantee that a multi-agent system obtains a common objective from local decisions. In this case, the agents are the aerial robots and the common objective is that the robots move according to the distribution and motion plan described in the previous section to cover efficiently a path P.

In this case a ‘one-to-one’ coordination strategy is used. The ‘one-to-one’ coordination is based in the concept of ‘coordination variables’, but applied independently for each pair of contacting robots. The ‘one-to-one’ coordination strategy implies that when a pair of aerial robot contact, they share information about their actual tasks. Then the whole shared set of tasks is divided between each robot according to their capabilities.

In this case, each aerial robot shares the segment that they are covering. Then a new larger segment, consisting of the union of the two previous segments, is divided between the two aerial robots related to their maximum speeds (see Fig. 4).

Figure 4.

When two quad-rotors contact, they share their actual patrolling segments and redistribute them according to their maximum speeds.

To apply the distributed algorithm, each aerial robot A_i only needs to store its own actual segment to cover P_i=[a_i, b_i]. In addition, each robot can maintain monitored information about the area in f o_i and its own state information, such as its position, speed, direction, etc. Then, each aerial mobile robot A_i can run independently the Algorithm 1.

The aerial robot tries to move at its maximum speed to cover its own segment in the minimum time, updating its local information meanwhile. Even if a robot knows it has reached the end of its own segment, it keeps on moving until it comes into contact with another robot or fixed station. A robot Ai contacts with another robot if they can interchange information. Then, the expression (6) is verified.

When an aerial robot A_i contacts with another robot A_j, they exchange information about their actual segments (a _i,b _i), maximum sp eeds (ν_i^max) and monitored information (in f o_i), using 'send’ and ‘receive’ functions. The aerial robots can use fusion information methods to create a more reliable information vector in f o_i.

Algorithm 1. Distributed patrolling algorithm.

Now, the aerial robot can compute its new segment to cover based on local and received information, see Algorithm 2.

Algorithm 2. Division segment algorithm.

Then, if any of the robots is out of its own segment, they travel together to the common endpoint between their segments, adapting their speeds. In the steady state, the neighbouring robots move in the opposite direction to force a periodical contact.

Finally, when an aerial robot arrives at the end of the path, it initializes its local information according to its direction and reverses it.

5. Area coverage path planning

An area coverage path planning should compute a path such that a robot travelling along it can monitor the whole area. Then, given an area S, an aerial robot flying with an altitude of z_i should be able to use the path planning algorithm to calculate a path defined in the expression (4).

In this paper, a decomposition-based algorithm is proposed to calculate the coverage path. If the area to be covered is irregular and has obstacles, it is approximated by many regular areas without obstacles.

Then, the problem is to cover rectangular areas (four vertexes) and a list of rectangular (four vertexes) obstacles. Depending on the resolution, any irregular area with zones that cannot be accessed can be approximated, such as Fig. 5 shows.

Figure 5.

Area approximation according to the circumscribing rectangle and the list of obstacles.

The Algorithm 3 receives the coverage range c(z_i), the list of maps map[] and the list of obstacles obst[]. The list of maps initially only stores the approximated rectangular area.

For each obstacle obst[i], the area where it is located in the list of mapsmap[]is found. Then that area is divided in four rectangular areas according to the obstacle shape and using the function ‘partition’ (see Fig. 6). The old containing area is removed from the list map and the new four created areas (if they are not an empty set) are included in the list.

Figure 6.

A rectangular area is divided into a list of sub-areas according to the list of inside obstacles.

Then, all the areas in the list map are rectangular areas without obstacles. Now, the ‘coverage’ function executes a slightly modified ‘back and forth’ strategy to calculate a closed coverage path for each rectangular area, as shown in Fig. 7.

Figure 7.

Simple coverage path planning strategy for simple rectangular areas.

Finally, the function ‘join’ is used repeatedly to join the nearest points along the paths in order to combine them into a single coverage path to survey the entire irregular area with obstacles.

Algorithm 3. Coverage Path Planning algorithm.

5.1 Coverage path quality

It is assumed that all the aerial robots move with their maximum speeds either if they move in a straight line or they are turning. Then, given that the entire area is always covered by the path, the best path will be the shortest path.

If the entire area without obstacles to cover measures Am² and the instantaneous covered area for a single robot measures 2πc(z_i)², the shortest coverage path will be limited.

L^{o p t} = \frac{A}{2 π c {(z_{i})}^{2}}

(16)

The above optimal length is sometimes infeasible, but it can be used as a reference to calculate the quality of a coverage path of length L:

Q = \frac{L^{o p t}}{L}

(17)

6. Proposed system

A distributed system which takes into account the communications constraints will be proposed to solve the surveillance mission. Both the area and the perimeter surveillance problem will be solved as a patrolling mission. The path to patrol will be defined by the objective to survey: a perimeter or an area.

A modular system is proposed to solve the surveillance problem in a decentralized manner. The system can be applied to irregular areas with obstacles. Each module is in charge of different functions. Figure 8 defines the architecture.

Figure 8.

Proposed system defined as set of independent modules.

The area S has to be distributed between the N aerial robots, e.g., quad-rotors. As there is only a minimal path to cover the whole area, the problem can be solved distributing that path instead of the area. Assuming the ‘one-to-one’ approach, the only required coordination information will be related to the definition of the segment P_ij to be covered by each pair of neighbours A_i and A_j.

The control and navigation module stabilizes the UAV and guides it along a path, running the ‘move’ function. Also this module computes the robot's current position. The control and navigation module uses a model of the aerial robot.

The communication module runs the 'send’ and ‘receive’ functions to exchange information with any other aerial robot close enough (6).

The monitoring module executes the ‘update’ function. This module can update the information about the area which verifies the expression (2).

Given an area to cover, the path generator module calculates a path defined by expression (4), executing the Algorithm 3 described in section 5. If the mission is not an area of surveillance, but a perimeter surveillance, this module will compute the path as the defined perimeter.

Finally, the decision module executes the Algorithm 1 described in section 4, using the rest of the modules. In addition, the decision module executes the ‘divide’ and ‘fusion’ functions. Then, this module is in charge of coordinating the whole team in a distributed and decentralized way to cooperate in the surveillance mission. This module decides the altitude, speed, direction, etc. of the aerial robot, both to coordinate the patrolling mission and to select a different action according to the monitoring information in f o_i.

7. Solution analysis

The proposed system coordinates a team of heterogeneous aerial mobile robots to cooperate in surveillance missions, in such a way that any position in the area or perimeter to survey is monitored periodically.

One of the most interesting features offered by the system is that it is totally distributed, which is a useful approach when there is no permanently opened communication channel between all the robots. It is also a decentralized system as there is no leader which rules the rest of the team.

The proposed system allows each aerial robot to decide in a local manner its own next action to enhance the global performance. When two robots meet, they divide the path to patrol in order to reduce the elapsed time until any given point along the path is visited again. However, when a robot does not meet another one it continues patrolling, ensuring that there are no segments along the path not being patrolled.

The following subsections summarize other interesting features.

7.1 Convergence

The presented approach, where all the robots have the same coverage range, implies that all the robots will calculate the same covering path. Also, the proposed system forces the aerial robots to change direction in the path endpoints. So, it is ensured that all the robots will exchange information with their neighbour and each one can execute the distributed patrolling algorithm.

Then, it is necessary to check if the distributed algorithm converges to the desired solution (13). In Acevedo et al. (2012), it is proved that by using ‘one-to-one’ coordinations, the whole area can be distributed correctly between all the robots.

7.2 Robustness

Since the proposed system is decentralized, any robot failure can be recovered by the whole team. So, the proposed approach is dynamic and can deal with changes in the environment (number of robots, speed of robots, path length, etc.). The system is robust, flexible and fault-tolerant.

For example, assuming a fully steady state in the system, each robot A_i patrols a segment according to its maximum speed and periodically neighbour robots meet. If at any time t a robot A_j breaks down, robots A_j₋₁ and A_j-₂ do not meet A_j. The patrolling algorithm forces the robots to continue in the same direction and, then, they meet between them.

Now, they share the sum of their own segment plus the A_j segment and divide it between both according to their capabilities. When A_j-₁ meets A_j-₂ or A_j₊₁ meets A_j₊₂, they share a larger segment than in the previous meeting. In the same way, the process is repeated with the rest of robots. Finally, in a finite time, the team without A_j covers the whole area correctly. The process is similar if the path changes or if the performance of any robot changes (i.e., speed).

7.3 Shared information in a finite time at the whole team level

Let us compute now the maximum time in which any information related to an event detected by a robot A_j is shared between the whole team. Consider a path of length L surveyed by a team of N aerial robots in a steady and optimal distribution. In the worst case scenario, A_j is in one of the end segments and detects an event just after it has contacted with its neighbour. Assuming the definitions from the previous section, A_j takes a time of T' to meet its endpoint of the perimeter and reverses its direction. Then, it takes T' to share the information with its neighbour. The same logic is applicable until the last robot in the other end segment (which does not have to share information with any other neighbour) and hence the time to share the information between all the robots is limited to:

T_{s h a r e} < T^{'} + (N - 1) T^{'} = N T^{'} .

(18)

7.4 Cooperative approach with heterogeneous robots

In the approach presented in this paper, the robots of the team cooperate to fulfil the surveillance mission. A cooperative approach allows taking advantage of the different capabilities of each robot. For instance, all the mobile robots have capabilities to detect intrusions, but only some of them can go to the intrusion position, some robots can move faster than others, etc.

The proposed approach tries to take advantage of the different capabilities of each robot to obtain a more efficient cooperative solution. For example, the fastest robots patrol larger segments than the slowest robots. Each robot covers a length according to its own maximum speed (13), optimizing the maximal minimum frequency-based criteria.

Also, assuming a team of N robots where all the robots can detect unexpected events but only one of them, A_k, can solve that event, in a non-cooperative approach the mission should be performed only by that robot. In a cooperative system, the N aerial robot can survey the path to detect the event and alert the robot which can solve it.

7.5 Scalable system

The proposed system is theoretically fully scalable. Each robot does not have to store information about all the rest of the team, but only its own local information. Also, each robot only has to interchange information with its neighbours, independently of the full size of the team. So, for each aerial robot the problem is always: a segment to cover and one or two neighbours to exchange information.

8. Simulation results with a team of heterogeneous quad-rotors

The Matlab simulations presented here are based on the ones performed by Etter et al. (2011), to test a leader-following algorithm. The authors have included some modifications to be able to test the proposed system. Therefore, the system has been implemented to be executed by each quad-rotor with a radio to exchange information.

A set of simulations has been performed with a team of six heterogeneous aerial robots to monitor an urban area with buildings (see Fig. 9). The aerial robot can fly with an altitude of 5 metres, so the buildings should be considered as obstacles. All the robots have low storage and communications capabilities. Pairs of robots can only communicate if the distance between them is less than 2 metres. Each aerial robot can only store information about the path to follow, the segment to cover, its own local states variables (speed, position,…) and an info vector about monitored events detected in the area. However, they cannot store information from other robots.

Figure 9.

Simulation snapshots where the quad-rotors, the buildings and a black cylinder representing the path initial position are shown. A video with the simulation can be downloaded from http://grvc.us.es/staff/jjacevedo/IJARS2012/

Furthermore, all the robots have the same angle of vision to monitor the area: π/8. On the other hand, each robot could move with a different speed (between 0.25 and 0.5 m/s) along the path. As all the robots fly with the same altitude and have the same angle of vision, all of them compute the same covering path to survey the area (using the Algorithm 3), as shown in Fig. 10.

Figure 10.

The closed path generated with the Algorithm 3) is drawn in grey. The fixed obstacles are represented in black.

Now, the complete simulations will be detailed. In the first step of the simulation, five of the aerial robots start surveying the area, using the decentralized system proposed in section 6. Each robot executes the Algorithm 1 to patrol the same path. Figure 11 shows the positions along the path for all the robots. The system converges with a team of heterogeneous robots, from a distributed approach. All the aerial robots cooperate to survey the area. At time 1200 seconds, a sixth aerial robot goes into the area and runs the distributed algorithms to patrol the zone. The simulation results show how the system performs with the new team composition and converge to a more efficient solution. Finally, at time t = 3000 seconds, one of the robots leaves the mission but it cannot report it to the rest. The system is robust and adapts to that loss converging to a new efficient solution.

Figure 11.

Five heterogeneous quad-rotors perform an area coverage mission and the system converges to an efficient solution where the path length is correctly distributed according to their maximum speeds. At time t = 1200 seconds, a new quad-rotor goes into the area to help in the patrolling mission. The new system converges to a more efficient solution. Each colour represents a different aerial robot. Finally, at time t = 3000 seconds, the yellow quad-rotor has to leave the area and the rest of the robots redistribute the path to continue patrolling the whole area efficiently.

Finally, we present how information is detected and shared between all the aerial robots. Then, a simple variable (initialized to ‘zero') is included in the model, and when an aerial robot knows that someone is in its covering zone (defined by its position, its altitude and its angle of vision), this variable changes to ‘one’. When two robots come into contact, they interchange their info variables and store the maximum value.

Figure 12 shows how, at t = 2000 seconds, a simulated person going into the area to a defined position and how the information about this intrusion is detected and shared between all the robots.

Figure 12.

Each colour represents a different aerial robot. When the value changes from ‘0’ to ‘1’, it means that a new robot has detected an event or has received information about a new event. The first ‘black’ change does not represent a robot, but indicates when the event happens.

The simulation results presented here show the convergence and the robustness (with dynamic team of robots). Also it is shown that the system performs well with heterogeneous UAVs (different capabilities) and that any information detected is shared among the whole team. The team of aerial robots works in a coordinated and cooperative manner. Figure 13 shows the maximum and average elapsed time, defined as (7), in the area.

Figure 13.

The blue line indicates for each time the maximum elapsed time since the last monitoring visit to any position in the area along the time. The red line indicates the average value of the elapsed times in all the positions into the area along the time.

A non-cooperative approach is tested in the same scenario, where each aerial robot surveys independently the entire area (following the same path) without communication with the rest of the team. Figure 14 shows the maximum and average elapsed time in the area, using a non-cooperative approach where each aerial robot follows a random direction to travel along the path. Furthermore, the times in which the detection is known by each robot are shown in Fig. 15.

Figure 14.

Figure 15.

Comparing the obtained results for the cooperative and the non-cooperative approach, it can be deduced that the proposed cooperative approach offers a more efficient solution (see figures 13 and 14) both for detecting or sharing event information (see figures 12 and 15). The maximum and average elapsed time is better using the proposed system.

On the other hand, the results show that when another aerial robot is included in the area the total performance of the cooperative approach is improved. However, with the inclusion of another aerial robot in the non-cooperative approach, the performance of the system has not been improved (see Fig. 14).

9. Conclusions

The area coverage problem with a team of heterogeneous mobile robots is studied in this paper, using a frequency-based approach.

A distributed system with a module architecture is proposed to solve the mission. Each module is in charge of different and independent tasks. The two main issues in the area coverage problem are the coverage path planning and the patrolling mission.

A decomposition-based approach and a slightly modified ‘back and forth’ strategy are used to generate a closed path which covers entirely any irregular area with fixed obstacles, minimizing the path length.

Assuming that all the aerial robots can calculate the same coverage path, the problem can be defined as a multi-robot patrolling mission where the maximal minimum frequency is the parameter to optimize. A ‘one-to-one’ coordination technique is proposed to distribute the whole area between the aerial robots in a decentralized manner and exchanging the minimum information.

The system offers some interesting features: it is robust against change in the team composition, converges to an efficient solution, is useful with teams of heterogeneous robot, is scalable and allows obtaining the cooperation of multiple robots in a distributed and decentralized manner. The Matlab simulation validates these features and shows how a cooperative approach is better than a non-cooperative approach.

Future developments will be aimed at obtaining a more efficient coverage system, considering the problem in a adversarial setting and applying the ‘one-to-one’ coordination in other kinds of task allocation problems from a distributed approach.

Footnotes

10. Acknowledgements

This work has been developed in the framework of the project of excellence of the Junta de Andalucía WSAN-UAV (P09-TEP-5120), the CLEAR (DPI2011-28937-C02-01) Spanish National Research Project and the EC-SAFEMOBIL (FP7-ICT-288082) EU-funded project.

References

Acevedo

Arrue

Maza

& Ollero

(2012). Cooperative large area surveillance with a team ofaerial mobile robots for long endurance missions, To appear in Proc. of the International Conference on Unmanned Aircraft Systems.

Agmon

Kaminka

G. A.

& Kraus

(2011). Multi-robot adversarial patrolling: Facing a full-knowledge opponent, J. Artif. Int. Res. 42(1): 887–916. URL: http://dl.acm.org/citation.cfm?id=2208436.2208459

Baseggio

Cenedese

Merlo

Pozzi

& Schenato

(2010). Distributed perimeter patrolling and tracking for camera networks, Decision and Control (CDC), 2010 49 th IEEE Conference on, pp. 2093–2098.

Beainy

& Commuri

(2009). Development of an autonomous atv for real-life surveillance operations, Control and Automation, 2009. MED '09. 17th Mediterranean Conference on, pp. 904–909.

Beard

McLain

Nelson

Kingston

& Johanson

(2006). Decentralized cooperative aerial surveillance using fixed-wing miniature uavs, Proceedings of the IEEE 94(7): 1306–1324.

Bernard

Kondak

Maza

& Ollero

(2011). Autonomous transportation and deployment with aerial robots for search and rescue missions, Journal of Field Robotics 28(6): 914–931. URL: https://dx-doi-org.web.bisu.edu.cn/10.1002/rob.20401

Cheng

& Dasgupta

(2010). Multi-agent coalition formation for distributed area coverage: Analysis and evaluation, Web Intelligence and Intelligent Agent Technology (WI-IAT), 2010 IEEE/WIC/ACM International Conference on, Vol. 3, pp. 334–337.

Cheng

Wang

& Dasgupta

(2009). Distributed area coverage using robot flocks, Nature Biologically Inspired Computing, 2009. NaBIC 2009. World Congress on, pp. 678–683.

Choset

& Pignon

(1997). Coverage path planning: The boustrophedon decomposition, International Conference on Field and Service Robotics.

10.

Daniel

Rohde

Goddemeier

& Wietfeld

(2011). Cognitive agent mobility for aerial sensor networks, Sensors Journal, IEEE 11(11): 2671–2682.

11.

Darbha

Krishnamoorthy

Pachter

& Chandler

(2010). State aggregation based linear programming approach to approximate dynamic programming, Decision and Control (CDC), 2010 49th IEEE Conference on, pp. 935–941.

12.

Di Giamberardino

& Gabriele

(2008). Mobile sensors networks: A distributed solution to the area coverage problem, Control and Automation, 2008 16th Mediterranean Conference on, pp. 1844–1849.

13.

Elmaliach

Shiloni

& Kaminka

G. A.

(2008). A realistic model of frequency-based multi-robot polyline patrolling, Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems - Volume 1, AAMAS '08, International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC, pp. 63–70. URL: http://dl.acm.org/citation.cfm?id=1402383.1402397

14.

Etter

Martin

& Mangharam

(2011). Cooperative flight guidance of autonomous unmanned aerial vehicles, CPS Week Workshop on Networks of Cooperating Objects (CONET), CPS Week 2011, Chicago.

15.

Gabriely

& Rimon

(2001). Spanning tree based coverage of continuousareas by a mobile robot, Annals of Mathematics and Artificial Intelligence.

16.

Geng

(2009). Consensus-reaching of multiple robots with fewer interactions, Computer Science and Information Engineering, 2009 WRI World Congress on, Vol. 5, pp. 249–253.

17.

Gobel

& Krzesinski

(2008). A model of autonomous motion in ad hoc networks to maximise area coverage, Telecommunication Networks and Applications Conference, 2008. ATNAC 2008. Australasian, pp. 258–263.

18.

Guruprasad

Wilson

& Dasgupta

(2012). Complete coverage of an initially unknown environment by multiple robots using voronoi partition, International Conference on Advances in Control and Optimization in Dynamical Systems.

19.

Hazon

& Kaminka

G. A.

(2008). On redundancy, efficiency, and robustness in coverage for multiple robots, Robot. Auton. Syst. 56(12): 1102–1114. URL: https://dx-doi-org.web.bisu.edu.cn/10.1016/j.robot.2008.01.006

20.

Hazon

Mieli

& Kaminka

(2006). Towards robust on-line multi-robot coverage, Robotics and Automation, 2006. ICRA 2006. Proceedings 2006 IEEE International Conference on, pp. 1710–1715.

21.

Hsieh

M. A.

Chaimowicz

Cowley

Grocholsky

Keller

J. F.

Kumar

Taylor

C. J.

Endo

Arkin

R. C.

Jung

Wolf

D. F.

Sukhatme

& MacKenzie

D. C.

(2007).

22.

Adaptive teams of autonomous aerial and ground robots for situational awareness, Journal of Field Robotics 24(11): 991–1014. URL: https://dx-doi-org.web.bisu.edu.cn/10.1002/rob.20222

23.

Huang

(2001). Optimal line-sweep-based decompositions for coverage algorithms, Proceedings of the IEEE International Conference on Robotics and Automation, Vol. 1, Seoul, Korea, pp. 27–32.

24.

Hung

K.-S.

& Lui

K.-S.

(2010). On perimeter coverage in wireless sensor networks, Wireless Communications, IEEE Transactions on 9(7): 2156–2164.

25.

Rekleitis

Lee-Shue

A.N.

& Choset

(2004). Limited communication, multi-robot team based coverage, ICRA.

26.

Kingston

Beard

& Holt

(2008). Decentralized perimeter surveillance using a team of uavs, Robotics, IEEE Transactions on 24(6): 1394–1404.

27.

Yun

S. Kook

& Rus

(2010). Adaptation to robot failures and shape change in decentralized construction, Robotics and Automation (ICRA), 2010 IEEE International Conference on, pp. 2451–2458.

28.

Kordari

& Blankenship

(2008). Perimeter coverage with wireless sensor networks, Military Communications Conference, 2008. MILCOM 2008. IEEE, pp. 1–6.

29.

Wang

R. Chuan

Huang

H. Ping

& Sun

L. Juan

(2009). Voronoi based area coverage optimization for directional sensor networks, Electronic Commerce and Security, 2009. ISECS '09. Second International Symposium on, Vol. 1, pp. 488–493.

30.

Maza

Caballero

Capitan

de Dios

J. M.

& Ollero

(2011). A distributed architecture for a robotic platform with aerial sensor transportation and self-deployment capabilities, Journal of Field Robotics 28(3): 303–328. URL: https://dx-doi-org.web.bisu.edu.cn/10.1002/rob.20383

31.

Maza

& Ollero

(2007). Distributed Autonomous Robotic Systems 6, Vol. 6 of Distributed Autonomous Robotic Systems, Springer Verlag, chapter Multiple UAV cooperative searching operation using polygon area decomposition and efficient coverage algorithms, pp. 221–230.

32.

McLain

& Beard

(2003). Cooperative path planning for timing-critical missions, American Control Conference, 2003. Proceedings of the 2003, Vol. 1, pp. 296–301 vol.1.

33.

Meuth

Saad

Wunsch

& Vian

(2009). Adaptive task allocation for search area coverage, Technologies for Practical Robot Applications, 2009. TePRA 2009. IEEE International Conference on, pp. 67–74.

34.

Ren

(2006). Decentralization of coordination variables in multi-vehicle systems, Networking, Sensing and Control, 2006. ICNSC '06. Proceedings of the 2006 IEEE International Conference on, pp. 550–555.

35.

Saravi

& Kahaei

(2011). Adaptive distance constrained deployment algorithm for mobile sensor networks, Signal Processing, IET 5(1): 27–32.

36.

Viguria

Maza

& Ollero

(2010). Distributed service-based cooperation in aerial/ground robot teams applied to fire detection and extinguishing missions, Advanced Robotics 24(1–2): 1–23. URL: https://dx-doi-org.web.bisu.edu.cn/10.1163/016918609X12585524300339

37.

Wong

C. Y.

Seet

Sim

S. K.

& Pang

W. C.

(2010). A framework for area coverage and the visual search for victims in usar with a mobile robot, Sustainable Utilization and Development in Engineering and Technology (STUDENT), 2010 IEEE Conference on, pp. 112–118.

38.

Yang

& Luo

(2004). A neural network approach to complete coveragepath planning, IEEE Transactions on Man and Cybernetics Systems.

39.

Zhang

Wang

& zhao

(2007). A topological area coverage algorithm for indoor vacuuming robot, Automation and Logistics, 2007 IEEE International Conference on, pp. 2645–2649.