J Intell Robot Syst
DOI 10.1007/s10846-016-0461-x
DARP: Divide Areas Algorithm for Optimal Multi-Robot Coverage Path Planning
Athanasios Ch. Kapoutsis · Savvas A. Chatzichristofis · Elias B. Kosmatopoulos
Received: 6 December 2016 / Accepted: 15 December 2016 © Springer Science+Business Media Dordrecht 2017
Abstract This paper deals with the path planning problem of a team of mobile robots, in order to cover an area of interest, with prior-defined obsta- cles. For the single robot case, also known as single robot coverage path planning (CPP), an O(n) optimal methodology has already been proposed and evalu- ated in the literature, where n is the grid size. The majority of existing algorithms for the multi robot case (mCPP), utilize the aforementioned algorithm. Due to the complexity, however, of the mCPP, the best the existing mCPP algorithms can perform is at most 16 times the optimal solution, in terms of time needed for the robot team to accomplish the coverage task, while the time required for calculating the solution is poly- nomial. In the present paper, we propose a new algo- rithm which converges to the optimal solution, at least in cases where one exists. The proposed technique transforms the original integer programming prob- lem (mCPP) into several single-robot problems (CPP), the solutions of which constitute the optimal mCPP
A. Ch. Kapoutsis () · S. A. Chatzichristofis ·
E. B. Kosmatopoulos
Department of Electrical and Computer Engineering, Democritus University of Thrace, Xanthi, Greece e-mail: athakapo@iti.gr
A. Ch. Kapoutsis · S. A. Chatzichristofis · E. B. Kosmatopoulos
Information Technologies Institute, CERTH, Thessaloniki, Greece
solution, alleviating the original mCPP explosive com- binatorial complexity. Although it is not possible to analytically derive bounds regarding the complexity of the proposed algorithm, extensive numerical analysis indicates that the complexity is bounded by polyno- mial curves for practical sized inputs. In the heart of the proposed approach lies the DARP algorithm, which divides the terrain into a number of equal areas each corresponding to a specific robot, so as to guar- antee complete coverage, non-backtracking solution, minimum coverage path, while at the same time does not need any preparatory stage (video demonstration and standalone application are available on-line http:// tinyurl.com/DARP-app).
Keywords mCPP · Multi-robots · Complete coverage · Minimum coverage paths · Terrain sub-division
1 Introduction
Since the 1970s, autonomous robots have been in daily use at very low and very high altitudes, for deep-sea and space exploration and in almost all air- crafts [20]. Today, in the era of multi robots, many of the robotic challenges, with a definite solution for the case of single robot, have to be revised so as to optimally incorporate the multi-robot dynamics. One of the fundamental problems in robotics is to determine an optimal path involving all points of a
J Intell Robot Syst
given area of interest, while avoiding sub-areas with specific characteristics (e.g., obstacles, no-fly zones, etc.). In the literature, this problem is often refer- eed to as coverage path planning problem (CPP), but can also be found as sweeping, exhaustive geo- graphical search, area patrolling etc. This task is directly related with a plethora of robotic applications, such as vacuum cleaning robots [1, 26], autonomous underwater vehicles [22, 23], unmanned aerial vehi- cles [31], demining robots [4], automated harvesters [28], planetary exploration [6], search and rescue operations [34].
The usual abstraction of the problem, consists of a robot with an associated tool (e.g. sensor, actuator), which is able to spatially cover at least the size of the robot itself. Therefore, one of the most common area representation techniques is to separate the field into identical cells (e.g. in the size of robot), such that the coverage of each cell can be easily achieved. Appar- ently, for any arbitrary shaped area, the union of the cells only approximates the target region, thus this technique, which is also adopted in our approach (see Section 3), is termed as approximate cellular decom- position. A comprehensive analysis of the different area decomposition techniques along with the major representatives from each class can be found in [11].
During the previous decade, researchers focus their effort to the aforementioned single robot coverage planning problem (inside an already known terrain), producing a lot of different approaches (e.g. [10, 36, 38]). One of the dominant approaches is the span- ning tree coverage (STC) algorithm [18], which is able to guarantee an optimal covering path in lin- ear time, constructing a minimum spanning tree for all the free cells. The term optimal encapsulates that, the generated path does not revisit the same cell (non-backtracking property), completely covers the area of interest and it achieves all the above with- out any preparatory effort (the robot can be initiated at any non-occupied cell). This major accomplish- ment comes with the assumption that the operation area does not get “more narrow” than the double of the robot’s size. Our approach utilizes the STC algo- rithm, thus it inherits this requirement, which is more formally described in the Section 4 of the paper.
The recent advances in robotics technology, both in the hardware and in the associated software, expand the variety of robots that can be deployed for a cover- age task. As a consequence, the usage of multi-robots
teams in the coverage path planning problem (form- ing the multi-CPP or mCPP problem), has recently received a lot of attention. Unfortunately, the mCPP problem was proven to be extremely more difficult to be adequately addressed. As a matter of a fact, solving mCPP with the minimal covering time has been proven to be NP-hard [39]. Previous investi- gations attempt to overcome the NP nature of the problem by proposing algorithms that solve a relaxed version of the original mCPP problem, mostly focus- ing only on one of the main coverage objectives (see Section 2 for more details). Moreover, in the mCPP problem, besides the optimality features that characterize a solution and derived directly from the single-CPP, the challenge to design the paths in a way to fully exploit the available multi-robot dynam- ics arises. In essence, this condition is one of the holy grails in any multi-robot system, since the unlock of such a feature would allow the fully cooperation of the robots with the ultimate utilization of their capa- bilities. In many of the proposed approaches, the fully exploitation of multi-robots dynamics is sacrificed for the sake of the main coverage objective (complete- ness, non-backtracking). Additionally, in multi-robot approaches, an often omitting issue is the needed cost/time in order to “transfer” the robots in their start- ing cells, excluding the initial robots location from the problem. Overall, the best of the proposed approaches can achieve coverage time which can be 16 times greater than the optimal one, in strictly polynomial time.
In the present paper we propose a methodology that is able to deliver the optimal solution for the mCPP problem – at least where one exists- in terms of cov- erage time, without overlooking any of the aforemen- tioned aspects. In contrary to the traditional addressing of this problem [14] (usually referred as allocate- then-decompose or decompose-then-allocate), where the building and allocation of the tasks are tack- led in a separated fashion [29], a new method in which the building task is robot-oriented is presented. Simultaneously, extended numerical analysis in realis- tic environments indicates that the computational time is polynomial in the size of grid times the #robots. In essence, the original mCPP is transformed into an optimization problem, where the satisfaction of a well- defined set of constraints will eventually give rise to the optimal solution. More precisely, the proposed scheme is separated into two phases.
J Intell Robot Syst
– First, the available cells are divided into distinct classes, as many as the #robots, by utilizing a constraint satisfaction scheme. The aim of this clustering is to preserve the following attributes a) the complete coverage, b) the operation with- out any preparatory effort and – most importantly – c) the fully exploitation of multi-robots dynam- ics. In the heart of the proposed algorithm, lies the Divide Areas based on Robot’s initial Positions (DARP) algorithm which is able to produce the optimal cells assignment with respect to the initial positions of the robots. The later can be achieved by employing a – specifically tailored to the prob- lem at hand – cyclic coordinate descent approach [35] with the known convergence properties.
– During the second phase, the STC algorithm designs the optimal path for every robot’s cluster, in a distributed manner.
The outline of the paper is as follows. The related work is described in Section 2, presenting alternative works on the mCPP. The mCPP problem is trans- formed into an optimization problem in Section 3, introducing all the essential notation. In Section 4 are briefly summarized the main steps of the STC algo- rithm, regarding the optimal solution of CPP problem. The findings of that section are going to be utilized in order to relax the original mCPP problem in Section 5. On the same section, are formally described the essen- tial conditions of the optimal solution. In Section 6 is proposed the DARP algorithm, with a comprehen- sive discussion about its performance. The complete scheme for the mCPP problem is outlined in Section 7. As proof of concept, in Section 8 is presented the per- formance of the proposed scheme in comparison with two of the state-of-the-art algorithms, regarding the mCPP problem. Finally, the concluding remarks are drawn in Section 9 together with an outlook to the future work.
2 Related Work
2.1 Multi-Robot Coverage Path Planning Problem Inside Known Terrain
Despite the fact that mCPP is a relative young field of research, there is a plethora of works that attempt to address the limitations and the restrictions of this
problem. An in-depth discussion of this field is beyond the scope of this paper, thus, in oder to construct a more appropriate and homogeneous pool of alternative works, only publications that are in line with our prob- lem formulation (Section 3) are included. For a more detailed and complete survey with regards to the latest achievements on the CPP/mCPP problem the reader should refer to [19].
The authors in [21] transformed, for the first time, the single robot Spanning Tree Coverage (STC) Algo- rithm [18] into a method that is able to incorporate team of robots. Their centralized algorithm (referred as MSTC) guarantees the complete coverage of the operational area while avoids a-priori known obsta- cles. Moreover, the non-backtracking version pro- duces a solution that visits every cell only once, while it is robust to robot’s failures. Unfortunately, the path length for each robot is critically depended on the ini- tial position of the robots and indeed in the worst case scenario, the maximum path length for the one robot is almost equivalent to that of a single robot case, even though there may exist alternative optimal paths configurations.
The same authors, in an attempt to alleviate the aforementioned shortcoming, proposed an enhanced version (referred as OPT-MSTC) [5], in which the form of the spanning tree is modified so as to mini- mize the maximum distance between every two con- secutive robots along the spanning tree path. This technique performs statistically better than the random generated tree, but again without any guarantee with respect to the initial robots’ positions.
An alternative technique that also utilizes span- ning trees, was presented in [39]. In this work, the authors provide an upper bound on the performance of a multi-robot coverage algorithm on known ter- rain, guaranteeing a performance at most sixteen times the optimal cost, preserving at the same time the key feature of complete coverage. Although the non- backtracking guarantee has been now removed, the MFC algorithm performs significantly better from both MSTC and OPT-MSTC in terms of minimizing the maximum robot’s path length, revealing that solu- tions without the equality constraint in the robot’s path length are far away from the optimal team utilization.
The authors in [17], developed a methodology that attempts to solve the problem of patrolling a known environment by a team of mobile robots, which can be translated to visiting all the points of the terrain
J Intell Robot Syst
with a certain frequency. Indeed, the patrol problem is closely related to the mCPP problem, therefore solu- tions that are used for patrolling might be used for mCPP as well. In this work, the authors first produce a minimal cyclic path, similar to [18], that traverse every single cell of the operation area and afterwards they search for the best “new” robots initial positions. These new locations are calculated so as to minimize the maximum distance from their initial positions and these to-be-traveled distances to be more or less the same. Unfortunately, this separation into two indepen- dent tasks, restricts the performance of the proposed algorithm. As a matter of fact, there is no upper bound regarding of number of the cells that are going to be visited in the worst case scenario, in order to fulfill the condition about the equality in robots’ paths, even in cases where an alternative optimal solution actually exists.
2.2 Area Division, for Multi-Robot Tasks
This subsection presents the dominant area division techniques, in order to assist multi-robot tasks – not limited to coverage.
An interesting method that falls in this class, has been presented in [25]. The operation area is divided using sweep-line approach and in the sequel, each sub- area is assigned to the most appropriate robot, based on their relative capabilities. However, the approach assumes as essential the unrealistic condition that the robots are initially located on the boundaries of the operation area. Moreover, the presented algorithm considers only convex areas without obstacles.
In [8], the authors proposed a complete approach for multi-UAV area coverage problem with a direct application to the task of remote sensing in agri- culture. As first step, the authors proposed an area subdivision method, which expands the well-known alternate-offer protocol [30]. This technique, aims to perform the tasks of area division and assign- ment simultaneously, but in a distributed effective way. Despite the well establishment of the method in terms of implementation details, there is no per- formance guarantee. The authors state that the final subareas assignment is a perfect equilibrium, but there is no reference on how the approach overcomes sub- optimal cases, which will be inevitably appeared in cases of non-convex areas or “difficult” initial robots’ placement.
The authors in [3], presented an alternative method using a heuristic algorithm to tackle the problem of arbitrary polygon division. Despite the fact that the results are rather promising and their algorithm runs in polynomial time, the produced solution has two main disadvantages. On the one hand, there is no specific guarantee about the optimality of the area division, while at the other hand the initial robots’ positions are not taking into account.
The algorithm described in [29], aims to achieve an enhanced multi-robot exploration by dividing workplace into separated regions for each avail- able robot. The authors, by employing the K-means algorithm, divide the available terrain into distance- related, convex subregions and afterwards apply a robot-subregion assignment mechanism to the trans- formed linear programming problem, utilizing LP- solve software [2]. Unfortunately, this two stage pro- cedure may end up with highly sub-optimal solu- tions, where it might be required for the robots to travel long distances (in comparison to the whole operation area) in order to reach their assigned subareas.
Many of the state-of-the-art approaches regarding the area division problem in multi robot context (e.g. [9, 13, 16]), have been relied on the Lloyd’s [24] algo- rithm, with the known convergence properties [15], and/or the Voronoi partitioning [7]. Although, these approaches seem suitable for the mCPP problem, and especially for the area division problem, they differ at a quite important aspect. These approaches seek to answer the following question: “Which are the most preferable positions to place the robots, so as to cover the non-occupied space with their on-board sensors?” On the contrary, in the present paper the term “cover” implies that the respective robot has to physically visit the corresponding assigned area. The aforementioned approaches are better suited for problems, such as to position a team of robots in a terrain so that any loca- tion is as close as possible to at least one robot [12] or to optimally monitoring a dynamic event with het- erogeneous sensory interest (e.g. oil spill) [32]. Thus, the majority of these approaches solves the area divi- sion problem independently of the robots/agents initial positions. Therefore, the direct appliance of these algorithms to the mCPP problem may lead to quite sub-optimal results as the robots’ areas may be equally divided, but the time/cost to reach these sub-areas has been left out of the equation.
J Intell Robot Syst
The fine-grained analysis of the related literature clearly indicates that there is room for contributions, so as to enhance the fully exploitation of the robots capabilities without jeopardizing important features of the already produced solutions. According to this necessity, this work proposes a grid-based multi-robot path planning algorithm inside known terrains, per- forming an area subdivision, according to both the number of robots and to their initial locations. In a subsequent stage, the exact paths inside each robot- exclusive area are defined in a completely distributed manner. The proposed algorithm is an approximate polynomial-time algorithm (for practical sized inputs) for the mCPP problem, which is able to guarantee that the solution i) complete covers all the area ii) without backtracking in already visited sub-areas iii) guar- antees the minimum coverage time exploiting all the available robots iv) and does not need any preparatory stage (the robots can start their journeys from their initial positions).
3 Multi-Robot Coverage Path Planning Formulation
For ease of understanding, it is assumed that the terrain to be covered is constrained within a rect- angle1 in the (x , y )-coordinates and it is dis- cretized into finite set of equal cells, the number of which represent both the level of required spa- tial resolution and the sensing capabilities of the robots.
U = {x,y : x ∈ [1,rows],y ∈ [1,cols]} (1)
where rows, cols are the number of rows and columns after the discretization of the terrain to be covered. Apparently, the number of all the terrain’s cells is given by n = rows × cols.
It is also assumed that there are no obstacles placed in a-priori known positions of U. The set of unknown obstacles is represented as:
B = {(x,y) ∈ U : (x,y) is occupied} (2) Robots cannot traverse obstacles, thus the overall set
of cells that need to be covered is reduced to: L=U\B (3)
1However, the problem formulation along with the proposed algorithm could be straightforwardly applied to different area shapes, not necessarily convex
and the number of cells to be covered is reduced to
l=n−no
Definition 1 Two cells (xi , yi ) and xj , yj
sidered adjacent if:
∥xi −xj∥+∥yi −yj∥≤1
As typical in many multi-robot coverage approaches, it is assumed that the robot can perfectly localize itself inside U and at each time- stamp, it can travel from its current cell to any unblocked (∈ L) adjacent cell, without any motion uncertainty.
Definition 2 As valid robot path of length m is con- sidered every sequence of cells
X = ((x1,y1),…,(xm,ym))
where the following constraints are hold
– –
(xi,yi) ∈ L, ∀ i ∈ {1,…,m}
every two sequential cells, i.e. (xi , yi ) and (xi+1, yi+1), are adjacent (Definition1),∀i ∈{1,…,m−1}.
Moreover, a closed path of length m is a path, as defined in Definition 2, where the additional condition is hold
–
(x1, y1) and (xm, ym) are adjacent The robot positions are defined as:
χi(t) = (xi,yi) ∈ L, ∀i ∈ {1,…,nr} (5)
where t denotes the specific time-stamp of the cov- erage path and nr denotes the number of operational robots. The (given) initial position of the ith robot inside L is represented as χi(t0).
Having the above formulation in mind, the mCPP problem2 can be transformed to calculate the robots’ paths Xi∗ ∀i ∈ {1,…,nr} so as,
minimize maxi∈{1,…,nr} |Xi| X
subjectto X1 ∪X2 ∪···∪Xnr ⊇L where |Xi | denotes the length of the path Xi .
(6)
are con-
(4)
2The aforementioned formulation may include cases, where the optimal solution does not exist and therefore are neglected for the analysis. The interest reader is kindly referred to the Appendix A.
4 Single Robot Coverage Inside Unstructured Environment
Disregarding for the moment the problem of optimal movement for a team of robots, let us consider the problem of covering a continuous unstructured area, utilizing only a single robot. Following the notation of optimization problem in Eq. 6, the aforementioned single robot CPP can be defined as:
minimize |X1|
X1 (7)
subject to X1 ⊇ L
It has been proved in the literature that the CPP
problem has an O(n) algorithm [18], where n is the size of grid, that is able to produce always the optimal solution. In other words, the Spanning Tree Coverage (STC) algorithm is able to construct the minimum path that coverages all the operation area L, starting from any arbitrary unoccupied cell.
Figure 1 illustrates the basic steps of an example designing trajectory. In this approach, the ter- rain’s cells are grouped into large square-shaped cells, each of which is either entirely blocked or entirely unblocked, and contains four of the initially
Fig. 1 Spanning tree coverage algorithm, sample execution
discretized cells (Fig. 1b). More precisely, the obstructed areas cannot be smaller than 4 times the size of grid’s cell and this condition consists of the only algorithm’s requirement. As next step, every unobstructed large cell is translated into a node (Fig. 1b) and for every adjacent cell, an edge is introduced. For the resulting graph, a minimal spanning tree is con- structed, using any minimum-spanning-tree algorithm, such as Kruskal’s or Prim’s algorithms [33], as it is illustrated in Fig. 1c. The robot then circumnavigates the spanning-tree along a (counter) clockwise direc- tion (Fig. 1d). The circumnavigation of the spanning tree generates a simple closed path X1∗, producing an optimal -in terms of coverage time- solution.
5 Reduce the Original mCPP Problem
Utilizing the findings of STC algorithm for the case of one robot, the original mCPP problem, as defined in Eq. 6, can be reduced to
minimize maxi∈{1,…,nr} |Li| L
subjectto L1 ∪L2 ∪···∪Lnr ⊇L
(8)
J Intell Robot Syst
(a) Initial cells’ discretiza- tion, robot’s cell and obsta- cles
(b) Subdivide the terrain into large square cells of 4 cells and represent them as nodes
(c) Construct a Minimum Spanning Tree for all the unblocked nodes
(d) Apply the ST to the orig- inal terrain and circumnavi- gate the robot around it
J Intell Robot Syst
where L1, L2, . . . , Lnr denote the robot sets (and not
strict paths). As next step, nr instances of the STC algorithm could be employed -in a completely dis- tributed manner- in order to calculate the robots’ exact paths inside these sets (problem (7)). Therefore, the exploitation of STC algorithm allows the removal of the severe adjacency constraint (Definition 2) regard- ing the produced robot sets. In other words, only the problem of building the Li sets, without any concern about the actual robot’s movement, inside the L world has to be addressed.
In the rest of this section we investigate the funda- mental conditions, that have to be hold regrading the Li sets, so as the optimal solution to the overall mCPP (6) problem to be guaranteed.
initial position of each robot χi (t0 ) must be contained on its own set Li , providing the ultimate layer of effec- tiveness, ensuring zero preparation time and energy. Any algorithm that is able to construct the Li sets, ensuring the Definition’s 3 conditions, can be utilized (in combination with the STC) to construct optimal solutions to the original mCPP problm (6).
Regarding to the existence of these solutions, it has been proved [27] that, a fair partition, which does not require convex pieces, always exists for any poly- gon and any number of partitions. The problem which is formulated here is a variation of the aforemen- tioned one, with an extra condition, that indicates the inclusion of any arbitrary point of the polygon inside each partition. Apparently, the above problem cannot always have a solution and strongly depends on the arrangement of the arbitrary points, that need to be included in the produced fair partitions. The overall formulation of the problem along with proposed algo- rithm are referred to cases where at least, one optimal solution exists.
6 Divide Areas Based on Robots Initial Positions (DARP)
In this section is described the DARP (Divide Areas
based on Robots Initial Positions) algorithm, a specif-
ically tailored, optimality preserving technique that
divides the terrain into nr robot-exclusive regions. To
start with, DARP algorithm adopts the following cell-
to-robot assignment scheme. For every ith operational
robot an evaluation matrix Ei is maintained. This eval-
uation matrix E expresses the level of reachability i
(e.g. distance) between the cells of L and the ith robot’sinitialpositionχi(t0).Duringeachiterationthe assignment matrix A is constructed as follows:
Ax,y = argmin Ei|x,y, ∀(x,y)∈L (9) i∈{1,…,nr }
Afterwards, each robot’s region Li can be computed straightforwardly by the assignment matrix A as fol- lows:
Li = {(x,y) ∈ L : A(x,y) = i}, ∀i ∈ {1,…,nr} (10)
Additionally, the number of assigned cells per robot can be defined as the cardinality of the Li set
ki = |Li|, ∀i ∈ {1,…,nr} (11)
Definition 3 A selection L1, L2, . . . , Lnr poses an optimal solution for the mCPP, iff
1. Li∩Lj =∅,∀i,j∈1,…,nr,i̸=j
com-
2. L1 ∪L2 ∪···∪Lnr =L
3. |L|≈|L|···≈L 1 2 nr
4. Li is connected ∀i ∈ 1,…,nr
5. χi(t0)∈Li
The first condition secures that every cell must be contained strictly in one robot’s set, constituting the non-backtracking guarantee for the produced solution. The second condition states that the union of all Li sets must contain every unblocked cell of the area to be covered (3) and depicts the fundamental cov- erage objective of completeness. The third condition establishes the fully exploitation of the multi-robot dynamics, by making certain that the number of cells |Li| in each robot’s set are more or less the same.3 The forth condition declares that the cells inside each robot’s set Li should be compact, forming a solid sub-region. In other words, this condition ensures that the division is absolutely fair and guarantees a seamlessness navigation scheme, inside spatially cohesive areas. According to that statement, no robot may spend extra/non-inclusive time to travel between unconnected areas. The final condition refines that the
3This ambiguity is introduced mainly for two reasons. On one hand, it might be impossible to perfect divide the number of cells to be covered |L| with the number of robots nr . On the other hand, even in cases where the perfect division is pos- sible the initial configuration – placement of both the robots and obstacles – may raise limitations according to the optimal solution.
By adopting the aforementioned cells assignments policy, regardless of the robots’ evaluation matrices E, the first, second and fifth conditions of Definition 3 are always satisfied. Concretely, one cell can only be assigned to one robot (first condition), every cell has been assigned to some robot’s operation plan (second condition) and it is assumed that the initial robot posi- tions are always assigned to the corresponding robot area (fifth condition). In a nutshell, DARP algorithm is an iterative process, which appropriately modifies the robots’ evaluations Ei in a coordinated fashion, in order to meet the two remaining -and in many cases conflicting- requirements.
Furthermore, the aforementioned cells’ assignment policy automatically undertakes an additional task related to the robots’ trajectories time-scheduling. If it is allowed for robots to occupy the same cells, then a fine-grained analysis should take place to prevent robot-to-robot collisions. This fact could result in a serious downgrade regarding the quality of the overall solution, even in case where the sets Li are equal.
6.1 Equally Divide the Space
Initially, the robots evaluation matrices Ei contain distance only information:
Ei|x,y = d χi(t0),[x,y]τ, ∀i ∈ {1,…,nr} (12)
where d(·) denotes the chosen distance function (e.g. Euclidean). Thus, the initial assignment matrix A (9) should be a classical Voronoi diagram.
The DARP algorithm’s core idea is that each evalu- ation matrix Ei can be appropriately “corrected” by a term mi as follows:
Ei=miEi (13)
where mi is a scalar correction factor for the ith robot. The third condition of Definition 3 is equivalent
(15), two shortcomings arise. At first, ∂ J /∂ mi can- not be computed algebraically, as the analytical form that relates J with mi is not available. On the other hand, there is no guarantee that J has only one (global) minimum.
To overcome the above problems, a cyclic Coordinate Descent (CD) methodology is adopted [35, Algorithm 1]. Coordinate descent algorithms solve optimization problems by successively perform- ing approximate minimization along coordinate direc- tions or coordinate hyperplanes. The global cost func- tion is minimized cyclically over each of one of the coordinates while fixing the remaining ones at their last updated values. Each such subproblem is a scalar minimization problem, and thus can typically solved more easily than the full problem.
To start with, the global minimum of this function willalwaysbeincasewherek1 =k2 =···=knr = f . Therefore, the global minimum of Eq. 14 can be obtained if we solve nr single dimension optimization problems with the following objective function:
Ji=1(ki−f)2 (16) 2
By applying the above transformation, we can achieve the following:
First and foremost, the above search is performed in local-minima free space.
Lemma 1 All sub-problems of Eq. 16 are convex to the corresponding controllable parameter mi .
Proof Let’s assume that the ith robot during the pre- vious iteration, based on its evaluation matrix Ei, occupied less cells than the desirable threshold (< f ). It is obvious from Eqs. 13 and 9 that a “small” decrease in the corresponding correction factor, mi (< 1), will lead to an increase in the number of assigned cells ki, assuming that the other robots’ evaluation matrices E remain the same. Therefore, the corresponding objective function Ji (16) will be decreased. Although, if we “over-decrease” the mi factor “many” cells will be assigned to the ith robot. Now, the Ji will start to rise again, as the ki will be greater that the f . From this point and after, if we con- tinue to decrease mi , the i th robot will be assigned to more and more cells, as ki can only be increased in response to mi decrease. The value of Ji is saturated
with the minimization of the:
nr
r=1
where f denotes the global “fair share”: f (#Unoccupied cells divided by the #robots).
12 J=2 (ki−f)
(14)
J Intell Robot Syst
= l / nr A standard gradient descent method for updating m
mi=mi−η∂J,η>0,∀i∈{1,…,nr} (15) ∂mi
can be employed, in an attempt to minimize the value of the cost function (14). When attempting to apply
J Intell Robot Syst
when all the available cells4 (l − nr + 1) have been assigned to the ith cell, and further decreases of mi cannot affect neither ki nor Ji. Hence, Ji will mono- tonically be increased, as mi is decreased until the
6.2 Build Spatial Connected Areas
Although, the aforementioned procedure can be eas- ily converge to share the available cells L among the different robots, it cannot guarantee the continuity of each robot’s sub-region (condition 4, Definition 3). In oder to deal with such situations, for every ith robot that occupies more than one distinct regions the following matrix is introduced
Ci|x,y =min(||[x,y]−r||)−min(||[x,y]−q||), ∀r ∈ Ri , q ∈ Qi
(20) where Ri denotes the connected set of cells where
the i th robot actual lies in (χi (t0 )) and Qi denotes the union of all other connected sets, which have been assigned to the ith robot but they do not have spatial connectivity with Ri set. In a more abstract concep- tualization, the Ci is constructed in a way, to reward the regions around the ith robot location’s subset, and to penalize the regions around other unconnected subsets, constructing gradually a closed-shape region. If all the assigned cells to ith robot belong to the same closed-shape region, the Ci is set to be the all-one-matrix.
The final update in the ith evaluation matrices is calculated as
Ei =Ci ⊙(miEi) (21)
where ⊙ denotes the element-wise multiplication. The findings of the previous subsections are illustrated in Fig. 2, where a flowchart of the proposed algorithm is presented.
6.3 Performance Discussion
Although simple in concept, the DARP algorithm aims to provide the optimal cells’ assignment, in cases where at least one exists. A sample execution is illus- trated in Fig. 3, where the terrain is constituted of 42× 42cellsandthenumberofrobotsisnr =5.Theinitial robots’ positions were squeezed inside a sub-region of the whole operation area, at the left bottom space of the grid, with dimension 10×10 cells. Each sub-figure illustrates the condition of the assignment matrix A (9)
maximumpossibleJi |k =l−n +1 = 1 (l−nr)(nr−1)2. i r 2 nr
Therefore, the previously encountered minimum is the global one. The proof continues to hold if, instead, we had assumed that the ith robot had been assigned to more cells than f .
Additionally, the update rule of mi can be straight- forwardly calculated for each objective function (16) separately as:
mi =mi−η∂Ji ∂mi
= mi −η(ki −f) ∂ki ∂mi
(17)
Due to the nature of the problem, the changes in
ki with respect to mi will always be negative (see
proof in Lemma 1) and they are almost identical for
each robot (for a given sub-problem (16)). Addition-
ally, two sets of evaluation matrices E1, . . . , Enr
and αE1, . . . , αEnr , where α denotes any posi- tive constant, correspond to the identical assignment matrices (9). Therefore, the influence of |∂ ki /∂ mi | can be securely omitted and the final update policy can be approximated as follows:
mi =mi +c(ki −f) (18)
where c denotes a positive tunable parameter. Summarizing, using Lemma 1 we can establish that even thought the global cost function f can be generally non-convex – depending of the robots and obstacles formation – with many local minima, each robot’s contribution Ji is a convex function with respect to the controllable parameter mi . As shown in [37], cyclic Coordinate Descent methodologies, where the above property holds, are able to converge to a
global optimal solution set m∗, i.e.
J(m∗) ≤ J(m), ∀m ∈ dom(J) (19) with respect to the initial evaluation matrices Ei (12).
4The available cells are l − nr + 1 as the initial robot cells are a-priori allocated to the corresponding robot.
at the corresponding iteration. Apparently, the algo- rithm was terminated after 260 iterations, fulfilling all the conditions of Definition 3.5
It is worth highlighting, that contrary to robot’s evaluation matrix Ei which is continuous, the pro-
5The interested readers are kindly referred to http://tinyurl.com/ DARP-live to watch an additional recorded execution of the DARP algorithm.
duced sub-areas that are finally assigned to each robot, may be arbitrary unconnected (at least temporary, e.g. Fig. 3b) non-convex areas. In fact, this DARP algo- rithm’s key feature, allows the gradually inclusion to each robot’s sub-region, of any arbitrary located cell. More precisely, DARP algorithm is capable of escap- ing the local minima by temporarily violating the condition about the connectivity of the each ith robot assignment matrix. Afterwards, the algorithm grad- ually eliminates the presence of unconnected areas,
J Intell Robot Syst
Fig. 2 DARP algorithm flowchart – divide areas based on robots initial positions
J Intell Robot Syst
(a) T = 0 (b) T = 40 (c) T = 80
(d) T = 120 (e) T = 200 (f) T = 260 Fig. 3 Progression of the robots sub-regions over iterations
by reinforcing the robot’s evaluation Ei around the original (the one that the robot actually lies in) sub- area. By the time, the connectivity inside the exclusive robot sets Li is restored, the evaluation matrices Ei will have completely changed their forms, and ideally towards to the optimal cells assignment.
The proposed algorithm diverges from the general class of local search algorithms in the sense that, it changes its current state, mainly based on the global optimal one and not only by evaluating information from the current and the candidate states. Over and above, DARP algorithm approximates the behavior of a gradient decent algorithm, with an extra capability to search effectively and reach the global optimal, even in case with multiple local minima.
6.4 Computational & Memory Complexity Analysis from an Approximation Point of View
The memory needs of the algorithm can be calcu- lated straightforwardly, as it utilizes a constant number β of matrices with dimensions (nr × n). In other words, the algorithm’s memory complexity is linear tothesizeofinput(nr ×n),i.e.O(β×nr ×n).The main optimization loop performs α × nr × n oper- ations, where α is a constant number, resulting in
O (α × nr × n)6 computational complexity. However, the number of times which the main optimization loop is executed (MaxIter) is not constant or linear, but it depends on the specific characteristics of the current problem in a non-linear fashion. As it is not possible to find the closed form that relates the maximum needed (main optimization loop) iterations with the number of robots nr , initial deployments χi (t0 ) and the grid size n, the following approximation scheme for the algorithm’s computational needs is adopted.
A series of simulations were conducted in order to measure the MaxIter (main optimization loop) iter- ations that were needed for the construction of the optimal solution (Definition 3). For each configura- tion (nr and n) the results were validated by repeating the experiment with different, randomly chosen, initial χi (t0 ), in order to be able to approximate the MaxIter for the worst case scenario.
Please note that, it is practically infeasible to com- pute exhaustively, the actual worst case for each con- figuration, due to the vast number of possible combi- nations of the initial robots positions. Nonetheless, in
6Please note that, in both complexity calculations, there is an additive constant which is omitted, due to its negligible influence
every different set-up the number of randomly created instances was proportional to the input parameters (nr and n). By doing so, it is ensured that the computed worst case complexity is representative of the number of possible occurring configurations.
The number of the experiments for each configura- tion starts form 50 for {nr = 3, n = 500} and reaches up to 5000 for {nr = 20, n = 5000}, constructing a pool of more than 120000 different experiments.
In order to present the overall approximation on the DARP’s complexity (MaxIter × nr × n), for each {nr , n} scenario was extracted the worse-case (maxi- mum) of the needed iterations (MaxIter). These worse cases for each scenario are translated into a surface by applying a polynomial least squares curve fitting tech- nique. The produced surface is illustrated with blue color in Fig. 4, where the operations’ needs growth, with respect to the input, is representing both in lin- ear and logarithmic scale. Moreover, and in order to evaluate the produced complexity results a number of polynomial surfaces is utilized. More specifically, with yellow, magenta and green color is illustrated the complexity curves in cases of f1 (nr , n) = n2r × n2 , f2(nr,n) = n3r ×n2, and f3(nr,n) = n2r ×n3, respec- tively. The evidences of this representation indicate that DARP’s complexity is cubic with respect to the input of the problem (nr × n), as the approximation
on the complexity curve is strictly bounded under the n3r × n2 curve, at least until the maximum simulated parameters nr = 20 and n = 5000.
Concluding this section, it is worth mentioned that the proposed algorithm cannot bypass the NP-nature of the mCPP problem, but it provides an approxi- mately polynomial algorithm until a specific (practical interesting) input. If both the size of the robots and number of the cells grow beyond the aforementioned order of magnitude of the input, the algorithm may lose its polynomial behavior.
6.5 Beyond the Classical mCPP
It is worth to point out that, the DARP algorithm is an optimization based one, which allows the inclu- sion of other secondary objectives, depending on the final multi-robot application, such as robot’s subareas smoothing etc., by just revising the appropriate per- formances’ criteria. In the literature, the problem of mCPP is usually defined as in Section 3, where it is desirable to produce balanced paths, in order to exploit all the available robots’ capabilities. However, there might be cases where specific robots’ characteristics (e.g. sensing module, battery life, etc.) impose dif- ferent utilization portions among the different robots. The proposed approach is able to straightforwardly
Fig. 4 Approximation on DARP’s complexity, a comparison with known polynomial surfaces
J Intell Robot Syst
J Intell Robot Syst
encompass this additional information, by appropri- ately modifying the calculation of Ji (16). More pre- cisely, the objective function for the ith robot is going to alternate as
1
Ji=2(ki−pi)2 (22)
where pi is the corresponding portion of the map that
In essence, this can be attained by the original con- struction, during the first phase (Section 6), of the Li sets, ensuring that the conditions of the Definition 3 are satisfied. The aforementioned feature of the algo- rithm not only allows the fully parallelization of the algorithm, but dramatically reduces the complexity of the initial mCPP problem to the order of magnitude of the STC algorithm.
Figure 5 depicts an example execution of the pro- posed algorithm. Figure 5a illustrates the initial robots positions along with the placements of the fixed obstacles. The Fig. 5b represents the result from the area division approach, as described in Fig. 2. Each sub-area’s Minimum Spanning Tree is represented in Fig. 5c with spatial information about the nodes inside the L world. Finally, the proposed algorithm let the robots move along the path that circumnav- igates the corresponding spanning tree, as is shown in Fig. 5d. It is worth noticing that, the produced paths constitute an optimal solution, as the number of cells that have been assigned to each robots are [12 13 12 12 12 13 12 12 12 ] (Definition 3, condi- tion 3)). The corresponding summation, translated to the operational world, is 4 (12 ∗ 7 + 13 ∗ 2) = 440, which is exactly the number of cells to be covered (Definition 3, condition 2)).
8 Simulation Results
This section presents a comparison study between the
proposed DARP+STC algorithm and two of the state- of-the-art methods (“MFS” and “Optimized MSTC” see related work). In order to produce comparable results, we adopt the same simulation set-up as in [39]. More precisely:
– The size of the terrain is always [rows,cols] = 98×98.
– We considered two kind of terrains: 1) The empty terrain [empty] and 2) the one, which has the 10 % of its cells occupied by obstacles [outdoor]. The obstacles’ arrangement follows a random uniform distribution.
– The number of robots varies from 2, 8, 14 to 20 robots.
– The robots initial placement can take three different types, according to their in-between maximum distance (clustering). More precisely,
the ith robot has to covered based on its capabilities or
limitations nr pi = 1. i=1
However in order to be in-line with the ordinary mCPP formulation we limit our simulation evaluation (Section 8) only to scenarios where an equal cells’ division between the robots is considered desirable.
7 Overview of the Proposed Multi-Robot Coverage Path Planning Algorithm
This section summarizes the complete algorithm for mCPP problem (6), by fusing the findings of the DARP and STC algorithms. The proposed algorithm is separated into two phases: During the first phase, the DARP algorithm divides the cells of L set into nr exclusive areas Li, for each available robot, as explained in Section 6. The outcome Li of that process serves as the operational area for each robot separately (Section 4).
After the applying of DARP algorithm and the cor- responding production of Li sets, the original multi robot optimization problem (6) is downgraded to nr single robots CPP problems, alleviating its explosive combinatorial complexity. Each one of these problems can be expressed as:
minimize |Xi|
Xi (23)
subject to Xi ⊇ Li
where Xi denotes a robot path as defined in Defini- tion 2. As shown in Section 4 this class of optimization problems (single robot inside grid connected environ- ments) can be solved in an optimum manner (optimal solution – polynomial time), utilizing the STC Algo- rithm.
con- struction takes place in a fully distributed manner, the union of the produced solutions is actually an optimal solution for the Eq. 6 problem, without any compro- mise in the quality or the generality of the solution.
Even though the final path X1, X2, . . . , Xnr
(c) Constructing Minimum Spanning Trees for each one of (d) Final Paths, designed to circumnavigate the MSTs the robots sets
Fig. 5 DARP+STC Proposed Approach, sample execution with 24×24 grid size, 9 robots and 100 obstacles
the maximum distance between two robots can be at most 1) 30 % [30] or, 2) 60 % [60] of the maxi- mum terrain’s dimension correspondingly, and 3) without any distance constraint (free selection) [none].
In order to obtain a fair comparison with MFC
and Optimized MSTC algorithm, we repeated each
scenario 100 times. The results for each combina-
tion of different evaluation scenario and algorithm, are
illustrated in Table 1, where it is reported the maxi-
mum [Max] and minimum [Min] coverage time for all
robots, in terms of paths lengths. Simultaneously, for each scenario we provide the idealized coverage time
[Ideal Max], which represents the optimal solution to
the problem. In other words, this value is simply cal- culated by dividing the number of unoccupied cells
with the number of robots (f ). Apparently, the larger deviations from the ideal coverage time, the bigger the difference between the robots paths, resulting in unbalanced, sub-optimal routes. The overall scoring for each scenario per algorithm, against the ideal cov- erage time, is depicted in [Ratio] column and reports the ratio of actual (maximum) traveled path and the ideal coverage time.
The direct observation is that the performance of the proposed algorithm DARP+STC seems to be immune to the number of robots and/or the obsta- cles and/or the initial clustering of the robots, as it
J Intell Robot Syst
(a) Initial cells discretization, robots cell and obstacles (b) DARP outcome – robots’ exclusive areas
J Intell Robot Syst
Table 1
Cover time (in terms of path length) for DARP+STC, compared with MFC and optimized MSTC
Terrain Robots
Empty 2
2 60 4801
2 none 4801 8 30 1200 8 60 1200 8 none 1200 14 30 685 14 60 685 14 none 685 20 30 479 20 60 479 20 none 479
Clustering Ideal
Max
DARP+STC MFC Max (Min) Ratio Max
4803 (4799) 1.001 4878 4803 (4799) 1.001 4886 4803 (4799) 1.001 4888 1203 (1199) 1.003 1399 1203 (1199) 1.003 1415 1203 (1199) 1.003 1394 687 (683) 1.006 841 687 (683) 1.006 819 687 (683) 1.006 830 483 (479) 1.008 615 483 (479) 1.008 604 483 (479) 1.008 604 4321 (4321) 1 4380 4321 (4321) 1 4382 4321 (4321) 1 4377 1082 (1078) 1.003 1263 1082 (1078) 1.003 1278 1082 (1078) 1.003 1247 620 (616) 1.006 746 620 (616) 1.006 750 620 (616) 1.006 746 434 (430) 1.007 572 434 (430) 1.007 557 434 (430) 1.007 551
Optimized MSTC
Max (Min) Ratio
5337 (4410) 1.11 5513 (4241) 1.15 5602 (4168) 1.17 3817 (45) 3.18 3539 (93) 2.95 3281 (146) 2.73 3756 (5) 5.48 3461 (16) 5.05 3072 (40) 4.48 3685 (3) 7.69 3439 (9) 7.18 2867 (18) 5.99 4772 (4031) 1.10 4854 (3954) 1.12 4923 (3903) 1.14 3561 (26) 3.30 3229 (70) 2.99 3099 (94) 2.87 3452 (6) 5.60 3228 (20) 5.24 2819 (37) 4.58 3437 (3) 7.97 3140 (9) 7.29 2740 (18) 6.36
Outdoor 2
2 60
2 none 8 30
8 60
8 none 14 30 14 60 14 none 20 30 20 60 20 none
30 4801
(Min) Ratio
(4731) 1.02 (4720) 1.02 (4725) 1.02 (838) 1.17 (904) 1.18 (956) 1.16 (431) 1.23 (522) 1.20 (513) 1.21 (307) 1.28 (332) 1.26 (321) 1.26 (4269) 1.01 (4266) 1.01 (4269) 1.01 (789) 1.17 (790) 1.18 (873) 1.16 (450) 1.24 (482) 1.22 (464) 1.21 (280) 1.33 (285) 1.29 (296) 1.28
30 4321 4321
4321
1079
1079
1079
616
616
616
431
431
431
performs with almost the same ratio over the differ-
ent scenarios. Additionally, all the results are close
to the [Ideal Max], and the maximum difference
between two robots path is at most 4 cells, indepen-
dent of the number of robots or/and the grid size,
Fig. 6 Cases where the robots and/or obstacles arrangement, do not allow the acquisition of optimal solution
above effectiveness bound is straightforwardly incom- ing from the DARP algorithm optimality guarantee. The DARP algorithm calculates the Li areas, having at most 1 cell difference among the different ith robots (see Fig. 2). This maximum discrepancy is translated into 4 cells after the appliance of STC algorithm
i.e. |X |−X ≤ 4, ∀i,j ∈ 1,…,n . The ijr
(a) The robots ini-
tial placement lim- and robots place- do not allow the its some robots op- ment forms two ex- fully coverage of eration plans clusive sub-areas the area of interest
(b) The obstacles
(c) The obstacles
J Intell Robot Syst
(Section 4). Overall, these findings seal experimen- tally, the performance of the proposed algorithm.
The afore-mentioned optimal performance does not come without shortcomings. In all cases, initial con- figurations that lead to sub-optimal results are dis- carded from the pool of test cases, while both the other two algorithms are able to straightforwardly produce some sub-optimal operation plans. A proper categorization of the cases where optimal solutions cannot be obtained, is provided in Appendix A, where also preliminary solutions, in-line with the proposed approach, are also presented.
9 Conclusions and Future Work
The proposed approach orchestrates the optimal coor- dination of a multi-robot team, so as to completely cover an area of interest. During the preliminary analysis, the underlying mCPP problem is translated into a constraint satisfaction problem, by formally define the exact attributes that have to be hold in order to achieve the optimal performance. In heart of the proposed approach lies the DARP methodol- ogy, a search algorithm, which finds the optimal cells assignment for each robot utilizing a cyclic coordi- nate descent approach, which takes into account both the robots initial positions and the obstacles forma- tion. The outcome of the DARP algorithm constitutes a set of exclusive operation areas for each mobile robot. These well-defined regions, are forwarded to each robot’s planner, where by employing STC algo- rithm, the exact route that covers the assigned area is calculated. The overall navigation scheme achieves to traverse the complete operation area, without back- tracking in already visited areas, starting from the exact initial robot positions. To the best of our knowl- edge, no other method from the literature exhibits all the aforementioned features at the same time.
Several avenues of exploration are left open for future work. One direction could be the relaxing of one or more constraints of Definition 3. For instance, in expense of the non-backtracking attribute, the pro- duced paths can be constructed to be convex only (less messy) or/and the shape of the STC can be appropri- ately modified in order of the turns in robots’ paths to be minimized. In addition, we intend to include in our methodology another stage, which will be in charge for the automatic recognition/detection of non-optimal
cases, in order to directly apply the appropriate, pre- defined solution scheme. Finally, in our future plans is the development of an online version of DARP algo- rithm, so as to be able to operate inside completely unknown terrains.
Acknowledgments This project is funded by the European Commission (FIRE+ challenge, Horizon 2020) that aims to pro- vide for research, technological development and demonstration under grant agreement no 645220 (RAWFIE).
Appendix A: Cases Where the Optimal Solution does not Exist
The problem formulation, as it is defined in Section 3, it may contain cases where the given placement of the obstacles or the robots blocks the access to one or more cells. Although these cases are considered out of the scope of the paper, and excluded from the con- sidered scenarios, here in the appendix we categorize them and propose some preliminary solutions in-line with the proposed approach.
The first class consists of cases where an optimal solution to the mCPP problem can not be attained, due to the initial placements of the robots (Fig. 6a). In these cases, one could spend some preparatory steps in order to rearrange the robots, so as to transform the problem into a solvable scenario (by the pro- posed approach DARP+STC). This rearrangement is not trivial and is forming another optimization prob- lem, where now the objective is to find the minimum path to travel in order to render the problem tractable. Alternatively, one could apply a relaxed version of DARP algorithm by removing its non-backtracking property (Definition 3, condition 1).
Another case, where the coverage task cannot be equally separated among the available robots, might be occurred, where one or more robots are trapped inside non-avoided, bounded sub-areas (Fig. 6b). In these cases one could straightforwardly apply the pro- posed approach, as many times as the number of bounded zones, and the optimal attainable solutions is again guaranteed. Apparently, in this case it is highly unlikely to end up having a balanced path length across all the robots’ planners. In fact, now the pro- duced path lengths are highly dependent on the size of the corresponding bounded area. However, differ- ent robots that lie in same sub-area should have almost the same workload (Definition 3, condition 3).
J Intell Robot Syst
Moreover, there are non-recoverable cases, where one or more sub-areas cannot be reached (Fig. 6c). In such situations the proposed algorithm can be applied on the remaining terrain, ensuring the optimal robots’ path construction. Finally, it might be occurred a combination of the above scenarios and then one could apply a hybrid version of the aforementioned solutions.
Over and above, it should be highlighted that, in all these cases the fact that the proposed approach is not able to deliver an optimal set of paths, is not some kind of weakness, but it is due to the fact that the opti- mal solution, at least with the properties as defined in Definition 3, does not exist.
References
1. irobot web site. http://www.irobot.com. Accessed: 2016-4- 1
2. Mixed integer linear programming (milp) solver, software. http://lpsolve.sourceforge.net/. Accessed: 2016-4-1
3. The area partitioning problem. In: Proceedings of the 12th Canadian Conference on Computational Geometry, Freder- icton, New Brunswick, Canada (2000)
4. Acar,E.,Zhang,Y.,Choset,H.,Schervish,M.,Costa,A.G., Melamud, R., Lean, D.C., Graveline, A.: Path planning for robotic demining and development of a test platform. In: International Conference on Field and Service Robotics, vol. 1, pp. 161–168 (2001)
5. Agmon, N., Hazon, N., Kaminka, G., et al.: Constructing spanning trees for efficient multi-robot coverage. In: Pro- ceedings 2006 IEEE International Conference on Robotics and Automation, 2006. ICRA 2006, pp. 1698–1703. IEEE (2006)
6. Apostolopoulos, D.S., Pedersen, L., Shamah, B.N., Shillcutt, K., Wagner, M.D., Whittaker, W.L.: Robotic antarctic meteorite search: outcomes. In: IEEE Interna- tional Conference on Robotics and Automation, 2001. Proceedings 2001 ICRA, vol. 4, pp. 4174–4179. IEEE (2001)
7. Aurenhammer, F.: Voronoi diagrams—a survey of a fun- damental geometric data structure. ACM Comput. Surv. (CSUR) 23(3), 345–405 (1991)
8. Barrientos, A., Colorado, J., del Cerro, J., Martinez, A., Rossi, C., Sanz, D., Valente, J.: Aerial remote sensing in agriculture: a practical approach to area coverage and path planning for fleets of mini aerial robots. J. Field Rob. 28(5), 667–689 (2011)
9. Breitenmoser, A., Schwager, M., Metzger, J.-C., Siegwart, R., Rus, D.: Voronoi coverage of non-convex environments with a group of networked robots. In: IEEE International Conference on Robotics and Automation (ICRA), 2010, pp. 4982–4989. IEEE (2010)
10. Butler, Z.J., Rizzi, A.A., Hollis, R.L.: Contact sensor-based coverage of rectilinear environments. In: Proceedings of the
1999 IEEE International Symposium on Intelligent Con- trol/Intelligent Systems and Semiotics, 1999, pp. 266–271. IEEE (1999)
11. Choset, H.: Coverage for robotics–a survey of recent results. Ann. Math. Artif. Intell. 31(1–4), 113–126 (2001)
12. Corte ́s, J.: Coverage optimization and spatial load bal- ancing by robotic sensor networks. IEEE Trans. Autom. Control 55(3), 749–754 (2010)
13. Cortes, J., Martinez, S., Karatas, T., Bullo, F.: Coverage control for mobile sensing networks. In: IEEE International Conference on Robotics and Automation, 2002. Proceed- ings. ICRA’02, vol. 2, pp. 1327–1332. IEEE (2002)
14. BernardineDias,M.,Zlot,R.,Kalra,N.,Stentz,A.:Market- based multirobot coordination: a survey and analysis. Proc. IEEE 94(7), 1257–1270 (2006)
15. Du, Q., Emelianenko, M., Ju, L.: Convergence of the lloyd algorithm for computing centroidal voronoi tessellations. SIAM J. Numer. Anal. 44(1), 102–119 (2006)
16. Durham, J.W., Carli, R., Frasca, P., Bullo, F.: Discrete par- titioning and coverage control for gossiping robots. IEEE Trans. Robot. 28(2), 364–378 (2012)
17. Elmaliach, Y., Agmon, N., Kaminka, G.A.: Multi-robot area patrol under frequency constraints. Ann. Math. Artif. Intell. 57(3-4), 293–320 (2009)
18. Gabriely, Y., Rimon, E.: Spanning-tree based coverage of continuous areas by a mobile robot. Ann. Math. Artif. Intell. 31(1-4), 77–98 (2001)
19. Galceran,E.,Carreras,M.:Asurveyoncoveragepathplan- ning for robotics. Robot. Auton. Syst. 61(12), 1258–1276 (2013)
20. Goldberg, K.: Robotics: countering singularity sensational- ism. Nature 526(7573), 320–321 (2015)
21. Hazon, N., Kaminka, G., et al.: Redundancy, efficiency and robustness in multi-robot coverage. In: Proceedings of the 2005 IEEE International Conference on Robotics and Automation, 2005. ICRA 2005, pp. 735–741. IEEE (2005)
22. Kapoutsis, A., Chatzichristofis, S.A., Doitsidis, L., de Sousa, J.B., Kosmatopoulos, E.B., et al.: Autonomous nav- igation of teams of unmanned aerial or underwater vehicles for exploration of unknown static & dynamic environ- ments. In: 21st Mediterranean Conference on Control & Automation (MED), 2013, pp. 1181–1188. IEEE (2013)
23. Kapoutsis, A.Ch., Chatzichristofis, S.A., Doitsidis, L., de Sousa, J.B., Pinto, J., Braga, J., Kosmatopoulos, E.B.: Real-time adaptive multi-robot exploration with applica- tion to underwater map construction. Auton. Robot. 40(6), 987–1015 (2016)
24. Lloyd, S.P.: Least squares quantization in pcm. IEEE Trans. Inf. Theory 28(2), 129–137 (1982)
25. Maza, I., Ollero, A.: Multiple uav cooperative searching operation using polygon area decomposition and efficient coverage algorithms. In: Distributed Autonomous Robotic Systems 6, pp. 221–230. Springer (2007)
26. Moloney, D., Suarez, O.D.: A vision for the future [soap- box]. IEEE Consumer Electronics Magazine 4(2), 40–45 (2015)
27. Nandakumar, R., Ramana Rao, N.: Fair partitions of poly- gons: an elementary introduction. Proc. Math. Sci. 122(3), 459–467 (2012)
28. Ollis, M., Stentz, A.: Vision-based perception for an auto- mated harvester. In: Proceedings of the 1997 IEEE/RSJ
J Intell Robot Syst
International Conference on Intelligent Robots and Sys-
tems, 1997. IROS’97, vol. 3, pp. 1838–1844. IEEE (1997)
29. Puig,D.,Garc ́ıa,M.A.,Wu,L.:Anewglobaloptimization strategy for coordinated multi-robot exploration: devel- opment and comparative evaluation. Robot. Auton. Syst.
59(9), 635–653 (2011)
30. Rubinstein, A.: Perfect equilibrium in a bargaining model.
Econometrica: Journal of the Econometric Society, 97–109
(1982)
31. Scaramuzza, D., Achtelik, M.C., Doitsidis, L., Fraundorfer,
F., Kosmatopoulos, E.B., Martinelli, A., Achtelik, M.W., Chli, M., Chatzichristofis, S.A., Kneip, L., et al.: Vision- controlled micro flying robots: from system design to autonomous navigation and mapping in gps-denied envi- ronments. IEEE Robot. Autom. Mag., 1–10 (2014)
32. Schwager, M., Rus, D., Slotine, J.-J.: Decentralized, adap- tive coverage control for networked robots. Int. J. Robot. Res. 28(3), 357–375 (2009)
33. Tarjan, R.E.: Data Structures and Network Algorithms, vol. 14. SIAM (1983)
34. Waharte, S., Trigoni, N.: Supporting search and rescue operations with uavs. In: International Conference on Emerging Security Technologies (EST), 2010, pp. 142– 147. IEEE (2010)
35. Wright, S.J.: Coordinate descent algorithms. Math. Pro- gram. 151(1), 3–34 (2015)
36. Xu, A., Viriyasuthee, C., Rekleitis, I.: Efficient complete coverage of a known arbitrary environment with applications to aerial operations. Auton. Robot. 36(4), 365–381 (2014)
37. Xu, Y., Yin, W.: A block coordinate descent method for regularized multiconvex optimization with applications to nonnegative tensor factorization and completion. SIAM J. Imag. Sci. 6(3), 1758–1789 (2013)
38. Yao, Z.: Finding efficient robot path for the complete cov- erage of a known space. In: 2006 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 3369– 3374. IEEE (2006)
39. Zheng, X., Jain, S., Koenig, S., Kempe, D.: Multi-robot forest coverage. In: IEEE/RSJ International Conference on Intelligent Robots and Systems, 2005. (IROS 2005). 2005, pp. 3852–3857. IEEE (2005)
Athanasios Ch. Kapoutsis graduated from the Department of Electrical and Computer Engineering of the Democritus Uni- versity of Thrace (D.U.Th.) (2007-2012). He is currently a PhD candidate at the Automatic Control Systems and Robotics Lab at the same department, as well as research assistant with the Centre for Research and Technology Hellas, Information Tech- nologies Institute, Thessaloniki, Greece. During the past years, he has been involved in several EU FP7 and H2020 funded IP Research and Development projects. His research is mainly focused on robotics, machine intelligent, nonlinear and adaptive control, pattern recognition and image processing.
Savvas A. Chatzichristofis received the Diploma and Ph.D. degrees from the Department of Electrical and Computer Engi- neering, Democritus University of Thrace, Xanthi, Greece, in 2005 and 2010, respectively. He is currently a postdoctoral researcher with the Democritus University of Thrace, as well as a post-doctoral researcher with the Centre for Research and Technology Hellas, Information Technologies Institute, Thessa- loniki, Greece. During the past years, he has been involved in several EU FP6, FP7 and H2020 funded IP and STReP Research and Development projects.
Elias B. Kosmatopoulos received the Diploma, M.Sc. and Ph.D. degrees from the Technical University of Crete, Greece, in 1990, 1992, and 1995, respectively. He is currently a Pro- fessor with the Department of Electrical and Computer Engi- neering, Democritus University of Thrace, Xanthi, Greece. Previously, he was a faculty member of the Department of Production Engineering and Management, Technical Univer- sity of Crete (TUC), Greece, a Research Assistant Professor with the Department of Electrical Engineering- Systems, Uni- versity of Southern California (USC) and a Postdoctoral Fellow with the Department of Electrical & Computer Engineering, University of Victoria, B.C., and Canada. Dr. Kosmatopoulos research interests in the areas of nonlinear and adaptive control, robotics, energy-efficient buildings and intelligent transporta- tion systems. He is the author of over 40 journal papers. He has been currently leading many research projects funded by the European Union with a total budget of about 10 Million Euros.