Decentralized Collision-Free Control of Multiple
Robots in 2D and 3D Spaces

arXiv:1709.05843v1 [cs.RO] 18 Sep 2017

by

Xiaotian Yang

2017

Abstract
Decentralized control of robots has attracted huge research interests. However, some
of the research used unrealistic assumptions without collision avoidance. This report
focuses on the collision-free control for multiple robots in both complete coverage and
search tasks in 2D and 3D areas which are arbitrary unknown. All algorithms are
decentralized as robots have limited abilities and they are mathematically proved.
The report starts with the grid selection in the two tasks. Grid patterns simplify
the representation of the area and robots only need to move straightly between
neighbor vertices. For the 100% complete 2D coverage, the equilateral triangular
grid is proposed. For the complete coverage ignoring the boundary effect, the grid
with the fewest vertices is calculated in every situation for both 2D and 3D areas.
The second part is for the complete coverage in 2D and 3D areas. A decentralized
collision-free algorithm with the above selected grid is presented driving robots to
sections which are furthest from the reference point. The area can be static or
expanding, and the algorithm is simulated in MATLAB.
Thirdly, three grid-based decentralized random algorithms with collision avoidance are provided to search targets in 2D or 3D areas. The number of targets can be
known or unknown. In the first algorithm, robots choose vacant neighbors randomly
with priorities on unvisited ones while the second one adds the repulsive force to
disperse robots if they are close. In the third algorithm, if surrounded by visited
vertices, the robot will use the breadth-first search algorithm to go to one of the
nearest unvisited vertices via the grid. The second search algorithm is verified on
Pioneer 3-DX robots. The general way to generate the formula to estimate the
search time is demonstrated. Algorithms are compared with five other algorithms
in MATLAB to show their effectiveness.

i

Contents
Abstract

i

List of Figures

vii

List of Tables

viii

1 Introduction
1.1 Multiple Robots . . . . . . . . . . . . . .
1.2 Centralized vs. Decentralized Algorithms
1.3 Complete Coverage and Search . . . . .
1.4 Mapping . . . . . . . . . . . . . . . . . .
1.5 Collision-Free Navigation . . . . . . . . .
1.6 Contribution Highlights . . . . . . . . .
1.7 Report Outline . . . . . . . . . . . . . .

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

1
. 2
. 4
. 5
. 8
. 10
. 12
. 13

2 Grid Selection for Coverage in 2D and 3D Areas
2.1 Grids for 2D Areas . . . . . . . . . . . . . . . . .
2.1.1 Definitions and Assumptions . . . . . . . .
2.1.2 The Strict Requirement . . . . . . . . . .
2.1.3 The Loose Requirement . . . . . . . . . .
2.1.4 The Choice for the Pioneer 3-DX Robot .
2.2 Grids for 3D Areas . . . . . . . . . . . . . . . . .
2.2.1 Definitions and Assumptions . . . . . . . .
2.2.2 The Loose Requirement . . . . . . . . . .
2.2.3 The Choice for the Bluefin-21 Robot . . .
2.3 Summary . . . . . . . . . . . . . . . . . . . . . .

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

15
16
17
17
20
22
25
26
27
30
30

.
.
.
.
.
.
.
.
.
.
.

32
33
33
34
39
43
44
44
44
45
51
51

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

3 Optimal Collision-Free Self-Deployment for Complete Coverage
3.1 Completer Coverage in 2D . . . . . . . . . . . . . . . . . . . . . . .
3.1.1 Problem Statement . . . . . . . . . . . . . . . . . . . . . . .
3.1.2 Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1.3 Simulation Results . . . . . . . . . . . . . . . . . . . . . . .
3.1.4 Section Summary . . . . . . . . . . . . . . . . . . . . . . . .
3.2 Completer Coverage in 3D . . . . . . . . . . . . . . . . . . . . . . .
3.2.1 Problem Statement . . . . . . . . . . . . . . . . . . . . . . .
3.2.2 Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2.3 Simulation Results . . . . . . . . . . . . . . . . . . . . . . .
3.2.4 Section Summary . . . . . . . . . . . . . . . . . . . . . . . .
3.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
ii

CONTENTS
4 A Collision-Free Random Search Algorithm
4.1 2D Tasks . . . . . . . . . . . . . . . . . . . .
4.1.1 Problem Statement . . . . . . . . . .
4.1.2 Procedure and Algorithm . . . . . .
4.1.3 Stop Strategies . . . . . . . . . . . .
4.1.4 Broken Robots and Reliability . . . .
4.1.5 Simulation Results . . . . . . . . . .
4.1.6 Section Summary . . . . . . . . . . .
4.2 3D Tasks . . . . . . . . . . . . . . . . . . . .
4.2.1 Problem Statement . . . . . . . . . .
4.2.2 Procedure and Algorithm . . . . . .
4.2.3 Simulation Results . . . . . . . . . .
4.2.4 Section Summary . . . . . . . . . . .
4.3 Summary . . . . . . . . . . . . . . . . . . .

iii

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

5 A Collision-Free Random Search with the Repulsive Force
5.1 2D Tasks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.1.1 Problem Statement . . . . . . . . . . . . . . . . . . . . .
5.1.2 Procedure and Algorithm . . . . . . . . . . . . . . . . .
5.1.3 Simulations with the Strict Requirement . . . . . . . . .
5.1.4 Comparison with Other Algorithms . . . . . . . . . . . .
5.1.5 Robot Test . . . . . . . . . . . . . . . . . . . . . . . . .
5.1.6 Factors in Choosing a Grid under the Loose Requirement
5.1.7 Section Summary . . . . . . . . . . . . . . . . . . . . . .
5.2 3D Tasks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2.1 Problem Statement . . . . . . . . . . . . . . . . . . . . .
5.2.2 Procedure and Algorithm . . . . . . . . . . . . . . . . .
5.2.3 Simulation Results . . . . . . . . . . . . . . . . . . . . .
5.2.4 Section Summary . . . . . . . . . . . . . . . . . . . . . .
5.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

6 A Collision-Free Random Search with the Breath-First Search
gorithm
6.1 2D Tasks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.1.1 Problem Statement . . . . . . . . . . . . . . . . . . . . . .
6.1.2 Procedure and Algorithm . . . . . . . . . . . . . . . . . .
6.1.3 Simulations with the Strict Requirement . . . . . . . . . .
6.1.4 Comparison with Other Algorithms . . . . . . . . . . . . .
6.1.5 Section Summary . . . . . . . . . . . . . . . . . . . . . . .
6.2 3D Tasks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.2.1 Problem Statement . . . . . . . . . . . . . . . . . . . . . .
6.2.2 Procedure and Algorithm . . . . . . . . . . . . . . . . . .
6.2.3 Simulation Results . . . . . . . . . . . . . . . . . . . . . .
6.2.4 Section Summary . . . . . . . . . . . . . . . . . . . . . . .
6.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

52
52
53
55
59
59
60
64
65
65
67
68
71
71

.
.
.
.
.
.
.
.
.
.
.
.
.
.

74
74
74
76
77
86
90
94
99
99
99
100
101
105
106

Al107
. . 108
. . 109
. . 110
. . 111
. . 112
. . 117
. . 117
. . 118
. . 119
. . 119
. . 125
. . 125

7 Conclusion
126
7.1 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127

CONTENTS

iv

Appendix

146

A Acronyms

147

List of Figures
2.1
2.2
2.3
2.4
2.5
2.6
2.7
2.8
2.9
2.10
2.11
2.12
2.13

Three regular tessellation patterns . . . . . . . . . . .
The illustration for a, rsaf e and rso . . . . . . . . . .
rso , rc and the selection order in search . . . . . . . .
Curvature example for the equilateral triangular grid
Example of the curvature in the S grid . . . . . . . .
A narrow path . . . . . . . . . . . . . . . . . . . . . .
The Pioneer 3-DX robot . . . . . . . . . . . . . . . .
Layout of 8 sonars in the front . . . . . . . . . . . . .
Range of the laser SICK-200 . . . . . . . . . . . . . .
Four uniform honeycombs . . . . . . . . . . . . . . .
a, rsaf e , rso , rc and the order of selection in search. .
Bluefin-21 . . . . . . . . . . . . . . . . . . . . . . . .
Passage width for a 2D area . . . . . . . . . . . . . .

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

16
18
18
19
20
21
24
24
25
26
28
30
31

3.1
3.2
3.3
3.4
3.5
3.6
3.7
3.8
3.9
3.10
3.11
3.12
3.13
3.14

The multilevel rotary parking system . . . . . . . . . . . . .
The launcher for multiple UAVs in the LOCUST project . .
The flow chart for the 2D complete coverage . . . . . . . . .
Judge obstacles . . . . . . . . . . . . . . . . . . . . . . . . .
The task area and the initial setting . . . . . . . . . . . . . .
Positions of robots when k = 30, |Va | = 256, Ni = 3 . . . . .
Positions of robots when k = 60, |Va | = 256, Ni = 3 . . . . .
Positions of robots when k = 86, |Va | = 256, Ni = 3 . . . . .
An example of the narrow path with k = 3, |Va | = 6, Ni = 3 .
The task area and the initial setting . . . . . . . . . . . . . .
Positions of robots when k = 15, |Va | = 129, Ni = 3 . . . . .
Positions of robots when k = 30, |Va | = 129, Ni = 3 . . . . .
Positions of robots when k = 44, |Va | = 129, Ni = 3 . . . . .
An example of the narrow path with k = 3, |Va | = 6, Ni = 3

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

35
35
36
37
40
41
41
42
42
46
47
48
49
50

4.1
4.2
4.3
4.4
4.5
4.6
4.7
4.8
4.9
4.10

Initial settings of the map . . . . . . . . . . . .
The flow chart for situation I . . . . . . . . . .
The flow chart for situation II . . . . . . . . . .
The route of robot 1 in a simulation of 3 robots
The route of robot 2 in a simulation of 3 robots
The route of robot 3 in a simulation of 3 robots
Combined routes in a simulation of 3 robots . .
Time and steps . . . . . . . . . . . . . . . . . .
3D area and initial settings . . . . . . . . . . . .
The route of robot 1 in a simulation of 3 robots

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

53
56
57
61
62
62
63
64
66
68

v

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

LIST OF FIGURES
4.11
4.12
4.13
4.14
4.15

The route of robot 2 in a simulation of 3 robots
The route of robot 3 in a simulation of 3 robots
The combined routes of 3 robots . . . . . . . . .
Time and steps for situation I . . . . . . . . . .
Time and steps for situation II . . . . . . . . . .

5.1
5.2
5.3
5.4
5.5
5.6
5.7
5.8
5.9
5.10
5.11

vi
.
.
.
.
.

.
.
.
.
.

69
69
70
72
72

. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
sit. .
sit. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .
. .

.
.
.
.
.
.
.
.
.
.

78
78
79
79
80
80
81
82
83
84

5.13
5.14
5.15
5.16
5.17
5.18
5.19
5.20
5.21
5.22
5.23
5.24
5.25
5.26
5.27
5.28
5.29
5.30
5.31
5.32
5.33
5.34

Route of robot 1 in a simulation of three robots . . . . . . . . .
Route of robot 2 in a simulation of three robots . . . . . . . . .
Route of robot 3 in a simulation of three robots . . . . . . . . .
Combined routes in a simulation of three robots . . . . . . . . .
Choice in the first step of the simulation of three robots . . . . .
Initial setting of the map . . . . . . . . . . . . . . . . . . . . . .
The order and initial positions of robots . . . . . . . . . . . . .
Search time for 1-13 robots with 1, 3, 5, 7 and 9 targets . . . . .
Search time for 9 targets with 1-13 robots in 5 areas . . . . . . .
Time ratio based on 100 vertices for 1-13 robots in five areas . .
Search 9 targets in 900 vertices area with different allocations in
uation I . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Search 9 targets in 900 vertices area with different allocations in
uation II . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
The order of allocation for 13 robots in a curve . . . . . . . . .
Search time for 1 target using 6 algorithms . . . . . . . . . . . .
Search time for 1 target using algorithms R and RW . . . . . .
Search time for 9 targets using 6 algorithms . . . . . . . . . . .
Search time for 9 targets using algorithms R and RW . . . . . .
The test area . . . . . . . . . . . . . . . . . . . . . . . . . . . .
The average result for 10 tests with 1-3 robots . . . . . . . . . .
The example route for one robot with legends (13 loops) . . . .
Example routes for two robots (10 loops) . . . . . . . . . . . . .
Example routes for three robots (6 loops) . . . . . . . . . . . . .
Nvt for a T grid: star-4 green-5 purple-6 red-7 . . . . . . . . . .
Nvt for an S grid: purple-4 yellow-5 green-6 star-7 . . . . . . . .
Nvt for an H grid: star-2 red-3 green-4 yellow-5 purple-6 . . . .
A T grid with no obstacles . . . . . . . . . . . . . . . . . . . . .
Time for a T grid with Nvt =4 and Nvt =6 . . . . . . . . . . . . .
Time for three grids with one target . . . . . . . . . . . . . . . .
Time for three grids with nine targets . . . . . . . . . . . . . . .
The route of robot 1 in a simulation with 3 robots . . . . . . . .
The route of robot 2 in a simulation with 3 robots . . . . . . . .
The route of robot 3 in a simulation with 3 robots . . . . . . . .
The combined routes in a simulation with 3 robots . . . . . . .
Time for four algorithms with 9 targets . . . . . . . . . . . . . .

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

85
85
88
88
89
89
91
92
93
93
93
95
95
96
96
97
98
98
102
102
103
104
105

6.1
6.2
6.3
6.4
6.5
6.6

The route of robot 1 in a simulation with 3 robots .
The route of robot 2 in a simulation with 3 robots .
The route of robot 3 in a simulation with 3 robots .
The combined routes in a simulation with 3 robots
All algorithms except R for 1-13 robots . . . . . . .
Time for 3 search algorithms . . . . . . . . . . . . .

.
.
.
.
.
.

.
.
.
.
.
.

112
113
113
114
115
116

5.12

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.

. 84

LIST OF FIGURES
6.7
6.8
6.9
6.10
6.11
6.12
6.13

Search time for search algorithm 2 and 3 . . . . . .
The route of robot 1 in a simulation with 3 robots .
The route of robot 2 in a simulation with 3 robots .
The route of robot 3 in a simulation with 3 robots .
The combined routes in a simulation with 3 robots
Compare 4 algorithms in situation I . . . . . . . . .
Compare 4 algorithms in situation II . . . . . . . .

vii
.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

117
120
121
121
122
123
124

List of Tables
2.1
2.2
2.3
2.4

Wpass and rst for each grid . . . . . . . . . .
Wpass and the area occupied by each polygon
rst for each 3D grid . . . . . . . . . . . . . .
The area occupied by each cell . . . . . . . .

3.1
3.2
3.3
3.4
3.5
3.6

Parameters of robots and simulation .
Steps from calculations and simulations
Steps from calculations and simulations
Parameters of robots and simulation .
Steps from calculations and simulations
Steps from calculations and simulations

4.1
4.2

Wpass and rst for each grid . . . . . . . . . . . . . . . . . . . . . . . . 64
The ratio of calculation time to total time . . . . . . . . . . . . . . . 71

5.1

5.3
5.4

Results of RU for 1-13 Robots in 900 vertices area with 1 target. (RU
in Figure 5.14) . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Results of S2 for 1-13 Robots in 900 vertices area with 9 targets. (5.1
& 5.2 in Figure 5.16) . . . . . . . . . . . . . . . . . . . . . . . . . .
Parameters of robots and in experiment . . . . . . . . . . . . . . . .
Search time for algorithm LFP and RU with 9 targets . . . . . . . .

6.1

Search time for algorithm R and RU in situation II . . . . . . . . . . 124

5.2

viii

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

. . . . . . . . . . . . .
with |Va | = 256 . . . .
for different areas with
. . . . . . . . . . . . .
with |Va | = 129 . . . .
for different areas with

.
.
.
.

.
.
.
.

. .
. .
Ni
. .
. .
Ni

.
.
.
.

.
.
.
.

21
23
27
29

. .
. .
=3
. .
. .
=3

39
43
43
47
49
51

. 90
. 91
. 92
. 106

Chapter 1
Introduction
The recent improvements of technologies and algorithms in robotics enable robots to
be widely used in various applications. The civilian usages include the vacuum cleaning at home [217, 229, 203, 72], manufacturing and material handling in factories
[50, 107], fire detection in the forest [108] and warehouse [30], pollution estimation in
the sea [47, 83] and the air [88], and data harvest [65]. There are also some military
applications such as the border patrol [121, 119, 94], the deployment of robots for
intruder detection [97, 132, 224, 226, 218, 57, 151, 18], intelligence, surveillance and
reconnaissance missions [1, 157], mine clearance [134, 31, 32, 127, 104, 105, 70, 21],
boundary monitoring [191], and the terrorist threat detection in ports [212]. Most
of the reference above is about search, coverage and path planning tasks. In the
employed robots, the autonomous mobile robots, including Unmanned Underwater
Vehicles (UUVs), Unmanned Ground Vehicles (UGVs), and Unmanned Aerial Vehicles (UAVs), have attracted the most research interests as they can be programmed
to execute certain tasks without further control from the human. Sometimes, a
team of multiple robots is used in a task as it has certain advantages compared to a
single robot. When a team of autonomous robots is employed, the ways that robots
coordinate to perform cooperative tasks become the main research topic. The algorithms can be divided into decentralized methods and centralized methods. Another
issue raised by a team of robots is collision avoidance. However, many algorithms
ignored this problem or use unrealistic assumptions thus cannot be applied to real
robots. Thus, to ensure a safe navigation through the task, standard robot models
or actual robots need to be considered as the base of the assumptions. The task area
can be two-dimensional (2D) or three-dimensional (3D), so the suitable method to
represent the 2D or 3D environments, as well as obstacles inside should be carefully
considered.
This report studied the problems of complete coverage and search using multiple
robots. The task area is arbitrary unknown, and robots move without collisions
based on a grid pattern. The best grids under different situations are discussed. One
decentralized algorithm for the complete coverage and three decentralized random
algorithms for search tasks are provided. The algorithms are initially designed in
2D area and can be used in 3D area with easy modification. The convergence of
each algorithm is proved, and all algorithms are verified by extensive simulations
and comparisons with other methods. Algorithms are designed based on datasheets
of real robots, and one search algorithm is applied to Pioneer 3-DX robots to show
the effectiveness.

1

1.1 Multiple Robots
Sections below are the literature review on the related topics in this report.

1.1

Multiple Robots

When finishing some tasks using a single robot, the robot usually needs to have
strong abilities with advanced sensors and complex algorithm. One kind of popular ground robots in research is the quadruped robot such as BigDog designed
by Boston Dynamics [155] and Mountainous Bionic Quadruped Robot from China
North Industries Corporation [160]. These robots are designed for rough-terrain
with different obstacles which may be too steep, muddy and snowy to use common
wheeled robots. They are also stable with heavy loads and external interference
such as pushes from different directions. Correspondingly, those robots need various
sensors for the environments, complicated computing and power systems, advanced
actuators and sophisticated dynamic controllers. For UAVs, the Parrot AR. Drone
has been widely used in research and education [91]. In [162], a trajectory tracking
and 3D positioning controller was designed for this drone using its onboard video
camera to building the map of the task area. A single robot path planning algorithm
for complete coverage using this robot is developed in [52]. A famous UUV used in
search of Malaysia Airline MF370 is the Bluefin-21 robot [21]. Some other robots in
research can be found in the survey paper [96].
However, there are many tasks which cannot be done by a single robot. For
the time-sensitive works, such as search and rescue after a disaster or the detection
of dangerous leaking biological, chemical, and radioactive materials, a single robot
may be unable to finish the task on time. For the coverage or data collection
task in a vast area, only one robot would not be able to have such a large sensing
range, and a larger sensing range means more expensive equipment should be used.
Sometimes, a task is designed for multiple members such as the soccer game and
the targets tracking mission with multiple aims moving in different directions where
one robot is not enough to follow each of them. Thus, the cooperation of multiple
robots is required. The recent developments in Micro-electro-mechanical systems,
integrated circuits, wireless communication, as well as the swift progress in algorithm
innovation also attracts researchers to focus on the control problem of the robots
network. As cheaper robots [5, 81, 152, 72] with simple functions are available [32]
to finish a task by cooperation, an expensive robot with advanced capability may
be unnecessary.
A system with multiple robots sometimes may be called as a Wireless Mobile
Sensor Network (WMSN) in some papers such as [128, 138, 99, 41, 42, 39, 184, 170,
164, 40]. In this report, both of them refer to a group of autonomous mobile robots
which carry sensors to detect targets or cover an area. The energy of the robots
comes from its battery. Robots can also build the local network to communicate with
neighbors to share information. Based on those detected or received information,
a robot moves dynamically to finish a task based on the control algorithm. As a
considerable number of robots can be used, each of them should have a reasonable
price, a carry-on battery, limited sensing ranges for obstacles and targets, and a
limited communication range.
The robots in a team do not always need to be homogeneous. They can be
heterogeneous as in the algorithms and experiments in [183, 76, 35, 110]. Due to
the complexity of the tasks, especially search and rescue, and the limited abilities
2

1.1 Multiple Robots
of each robot, members of a multi-robot system can have different functions. For
example, the HELIOS team with five robots were proposed by Guarnieri et al. for
the search and rescue task [66]. In the system, only three robots have laser range
finders and cameras to create the virtual 3D map of the task area. The other two
robots with manipulators are used to execute the special tasks including handling
objects and opening doors. Sugiyama et al. [189, 190] developed the chain network
in a rescue system with multiple robots. The system consists of a base station,
some search robots and some relay robots. Different robots have their behavior
algorithms to form the chain network. The method of the classification and the
behavior algorithm is based on the forwarding table of each robot constructed for adhoc networking. Then the robots recognized as relay robots will act as information
bridges, and frontier robots will search the area. Luo et al. [27] exploited a team
with both ground and aerial vehicles for search and rescue tasks. The environment
mapping was executed by the ground vehicle. The search and localization were
finished simultaneously by the micro aerial vehicle with a vertical camera and a
horizontal camera. Another two micro ground vehicles equipped with color sensors,
sonar, and compasses were used as the backup team. [35] proposed a hierarchical
system consisting of managers with advantages in computation and worker with
limited ability. This system allows the processing resources to be shared and global
environment to be divided into local sections for the workers. Worker robots can be
separated into planners, explorers or robots with both jobs based on their ability to
only deal with their assigned tasks. Algorithms in this report only require the robots
to satisfy certain assumptions about their sensing ranges, the communication range,
and the maximum swing radius but the robots can be different. In search tasks, all
robots are doing the same task without further actions on the found targets so there
is no need to separate robots to distinct roles.
Multiple robots have many advantages comparing to a single robot [219, 161, 59,
152, 214, 11, 12]. Firstly, a system with multiple robots is more efficient as discussed
above because they can share information with neighbors so that they can cooperate to know the environment faster and better. Multiple cooperative robots can be
separated spatially and temporally. Therefore, they can fulfill the complex, decomposable task efficiently such as cleaning floor and surveillance. Correspondingly, it
may save the total consumed energy. Secondly, it is reliable as more robots provide
more redundancy than a single robot. If one robot is not working, other robots could
finish the task if they use an independent algorithm. Through communication, the
robot failure may even be detected. Thirdly, the system is robust to errors because
the information of one robot can be judged or rectified using information from other
robots. Also, the system can be flexible to different tasks with different areas maybe
by reassigning the task for each robot. Finally, a robot team can be scalable with
various numbers of members to satisfy the task requirement, but the expense of
robots need to be considered.
While using a group of robots, many algorithms for a single robot may not be
available, and it is challenging to design the algorithm in different aspects. The later
sections will discuss them one by one.

3

1.2 Centralized vs. Decentralized Algorithms

1.2

Centralized vs. Decentralized Algorithms

In the robot teamwork, communication and control methods are significant and
complex topics. The algorithms for multiple robots can be divided into centralized algorithms and decentralized algorithms. In centralized control tasks such as
[100, 15, 16], the communication center or the leader robot collects and distributes
the information to all the others, which is relatively easy to control and to design algorithms. Thus, the leader robot has a larger memory and stronger communication
ability which will be expensive. However, on this occasion, global information such
as the Global Positioning System (GPS) data may be needed for synchronization
and localization. This method also requires all robots to have good communication ability. However, those demands may be unrealistic in some occasions such
as in caves, under water and in areas without control such as drones in enemys
airspace. In another type of centralized control method, the leader-follower algorithm [45, 75, 67, 68], robots need to keep a very restrictive type of communication
topology [48, 53], namely, they need to stay in the communication range of each
other. In the rescue network of [189], communication chains must be continuously
existing from the base station through the relay path to the distant rescue robots
to reconnoiter disaster areas, and those chains must be transformed to a suitable
topology if the target area of exploration is changed. Some other papers assumed
that the communication graph is minimally rigid [92, 209] or time-invariant and
connected [122]. Thus, they are used in formation control or achieving some consensus variables such as the same speed, the same direction, but they cannot work
independently in a large area. A deadly disadvantage of the centralized scheme is
that if the leader robot is broken, the whole system will stop working. Therefore,
the centralized control and communication algorithms have limited applications and
lead researcher to the decentralized methods.
Decentralized control of multiple robots is an attractive and challenging area
[138, 6, 137, 82, 196, 125], however, it provides the system with benefits in robustness,
flexibility, reliability, and scalability according to Zhu [232]. Specifically speaking,
this problem describes a group of dynamically decoupled robots, namely, each robot
is independent and will not be affected by others directly according to Savkin [163].
Research in this area is largely inspired by the animal aggregation problem which
belongs to ecology and evolution branches of biology. It is believed by Shaw [180],
Okubo [139] and Flierl [58] et al., that some simple local coordination and control
laws were exploited to achieve the highly intelligent aggregation behavior by a group
of bees, a school of fish and a swarm of bacteria. Those laws may be used in formation
control. Described by [193], efficient foraging strategy of animal can be used in a
coverage and search problem for animals. The evolutionary process through the
natural selection led to highly efficient and optimal foraging strategies even with
physical and biological constraints. It can be seen in the method that lobsters used
to localize and track odor plumes or in the bacterial chemotaxis mechanism used
by e-coli to response the nutrition concentration gradient. Similarly, robots only
need a local communication range and small sensing ranges which are achievable
for many cheap robots. Also, less communication is necessary compared to the
centralized method in which gathering information from and sending tasks to each
terminal need much time. Moreover, in some steps, using a decentralized algorithm,
different members of the team can execute their missions in parallel to improve

4

1.3 Complete Coverage and Search
the efficiency of the work. Both centralized and decentralized communications are
used in this report to improve the efficiency of the search or coverage task as well
as to save the total energy. The centralized communication is only used to deliver
the significant information such as the positions of targets or the positions of the
failed robots, which is like the usage of the flare gun for delivering distress signal
in the real rescue scenarios. Decentralized control and communication is the main
part of the algorithms in this report to save time and money and thus, making
the algorithms more applicable. Initially, the information of the environment is
unknown. Then a robot will gradually record its sensed map and exchange the map
with neighbor robots that it can communicate with. Thus, the robots only use local
information to make the decision and will have different neighbors in later steps
[82, 125, 11, 12, 42, 170, 176, 77].
In literature from the perspective of control engineering, ideal communication situations were usually considered. However, research in the area of telecommunication
discussed the non-ideal communication including the transmission delay due to the
limited bandwidth, the propagation delay because of the long transmission distance
or the information loss caused by inference especially in a battlefield where severe
interference is generated by the enemy. [140] considered the multi-agent system with
communication time-delays. It used switching topology and undirected networks.
Then a direct connection between the robustness margin to time-delays and the maximum eigenvalue of the network topology is provided. In [68] with the leader-follower
structure, the state of the considered leader not only kept changing but also might
not be measured. Thus, a state estimation method for getting the leader’s velocity
is proposed. In systems with communication constraints such as limited capacity in
communication channels, estimation of the necessary information are needed using
methods of Kalman state estimation in [167, 102, 171, 172, 146, 143, 147, 115, 169].
Other hardware limitations may include the insufficient memory for a large global
map. [34] solved this problem by describing the global map by local maps which
was explored by a two-tiered A* algorithm. This algorithm can be executed entirely on the robots with limited memory. As the energy of the mobile robots is
limited [98], [99] researched the area covered during the cover procedure instead of
the final result. It considered coverage rate at a specific time instant or during a
time interval. It also showed how long a location is covered and uncovered. Then
a relation between detection time for a randomly located target and parameters of
the hardware were given to help a user to decide the number of robots to use. Ideal
communication is assumed in this work and propagation delay would not happen as
local communication is fast enough to ignore that delay. The problem caused by the
limited bandwidth is also solved by designing a suitable mapping method to minimize the information needed for the area. The memory is considered as sufficient
and the search time with different parameters is discussed.

1.3

Complete Coverage and Search

Popular tasks for cooperation of multiple robots include coverage control, search
and rescue, formation control [176, 177, 201, 6, 154], flocking [196, 197, 198, 159],
and consensus [57, 74, 140]. This report focuses on the complete coverage tasks,
and search and rescue tasks. Coverage problems were defined differently by various
researchers [17, 215, 26, 230] from their research interests which are lack of generality.
5

1.3 Complete Coverage and Search
It could be concluded as going through a target area by utilizing the sensors on the
robots and achieving the requirements as consuming the least time, going through
the shortest path or having the least uncovered area. As defined by Gage [62],
there are three types of coverage problem namely, barrier coverage [15, 16, 41, 40],
sweep coverage [178, 40, 43] and blanket coverage [170, 42, 168, 224, 226]. Another
two coverage types are dynamic coverage [99] and search. Barrier coverage means
the robots are arranged as a barrier, and it will detect the invader when they pass
through the barrier. Sweep coverage can be thought as a moving barrier to cover a
particular area which maximizes the detections in a time slot as well as minimizes
the missed detections per area. Blanket coverage is the most difficult one. It aims
at deploying robots in the whole area so that each point of the area is covered by
at least one robot at any time [170] in which the selected deployment locations are
designed to minimize the uncovered area and the deployment procedure should be
as short as possible to reach the blanket coverage early. In the three-dimensional
area, the term blanket is not suitable for the same coverage problem and is called
complete coverage or complete sensing coverage in general for both types of areas.
For complete coverage, there are two types of self-deployment strategies based
on the survey [228] which are the static deployment and the dynamic deployment.
In the static deployment, robots move before the network start to operate. However,
the deployment result such as the coverage rate or the connectivity of the network
is assessed under the fixed network structure, or the assessment is irrelevant to
the state of the network. For the dynamic one, the condition of the network may
change such as the load balance of the nodes leading to the repositioning of the
mobile robotic sensors [179]. The complete coverage in this report firstly considered
100% coverage between nodes for a fixed area as the static deployment. Then the
dynamic self-deployment in an extending area, such as the demining area in the
battlefield which could be enlarged, is considered by a simple modification of the
static method. Some deployment methods deployed all robotic sensors manually
[84], however, the cost is high if the area is large, so the applications are usually in
an indoor area as in [93, 148, 24]. Moreover, in some applications in a dangerous
or unknown environment, such as demining, human actions are impossible. Thus,
in some papers, mobile sensors were randomly scattered from helicopters, clustered
bombs or grenade launchers with assumptions of the distribution pattern [228] such
as the uniform distribution in [195], the simple diffusion, and the R random in [80].
Dynamic coverage in [99] is similar to a search task. They both describe the
coverage problem with continuously moving sensors to find targets. Movements of
sensors are required because, in a vast area, blanket coverage is not realistic as
it needs a significant number of robots which is expensive. Therefore an algorithm
should be designed which uses only a selected number of robots to cover the unknown
area completely dynamically. Thus, a section of the area will be covered sometimes
and be uncovered in other time slots. However, the dynamic coverage ensures that
each point is visited at least once through the whole search procedure. Note that
in dynamic coverage or search, mobile sensors do not need to move together in a
formation like in the sweep coverage. Note that, a search task may also be named
as an area exploration task [126, 190, 17, 25, 35, 76, 108] in the mapping related
topics or be called as a foraging strategy for animals [185, 149].
In both complete coverage and search problems, some papers used the assumption about the boundary effect [221, 224, 3, 4]. The assumption claims that the
6

1.3 Complete Coverage and Search
length, width (and height if it is a 3D area) of the search area is much larger than
the sensing range so that the gaps between the sensed area and the boundary are
small enough to be ignored so targets would not appear in those gaps [3]. However,
some other papers ignored this assumption but still claimed they reached the complete coverage or a complete search [223, 132, 131, 128, 129, 130, 133, 12, 10, 14, 11].
Those papers could only be correct by having assumptions about the shape of the
boundary and passage width. For example, the boundary is simple and smooth to
allow the equilateral triangle grid to stay inside the border. In this report, complete
coverage without exceeding the board is considered by either providing some assumptions about the shape of the area [225, 222, 226] or employing the assumption
for the boundary effect [221, 224].
Current research about coverage and search were mainly in 2D areas which had a
relatively easy geographical feature and can be applied to the plane ground and the
surface of the water. However, there are a considerable number of applications in 3D
terrains, such as detection of the location of the forest fire [30], underwater search
and rescue [110], oceanographic data collection [211] ocean sampling, ocean resource
exploration, tactical surveillance [2, 150, 157] and hurricane tracking and warning
[44, 157]. The problems in the 3D area bring challenges in many aspects [55]. The
area of interest in 3D spaces, such as underwater area or airspace, is usually huge
and the telecommunication and sensing ranges need to be improved from circular
ranges to spherical ranges which may be solved by attaching more sensors on robots
or using better sensors. The mobility of robots needs to have more Degrees of
Freedom (DOF), which requires entirely different mechanical structure as well as
advanced controllers and sensors. Thus, tasks in 3D spaces require more expensive
hardware on autonomous robots with higher mobility [210]. For the connectivity
and coverage in algorithms, some comprehensively researched tasks in 2D areas are
still waiting to be proved in 3D areas which will be discussed in detail in the next
section. The complex system and task in 3D search and complete coverage lead to
extra computational complexity and larger memory space needed. Some algorithms
in 2D may not be applied to 3D tasks with simple extensions or generalizations
[79]. However, several work researched the coverage [216, 145, 213, 3, 128, 224,
111, 129, 133, 55, 79, 150], search [132, 131] and trajectory tracking [162] problems
in 3D areas [130]. Those algorithms can be used in the flight in a 3D terrain
[162, 52, 188, 208] and the exploration in underwater environment for rescue tasks
[110, 16, 182, 194, 213, 3]. Inspired by the search for MH370 in the underwater
environment, this report develops algorithms in a 2D area first and modifies them
to be suitable to be applied on a 3D area.
In complete coverage and search, the ranges of sensors are critical parameters.
There are various assumptions for the sensing ability of sensors [207]. Most papers
[223, 132, 131, 128, 129, 130, 133, 12, 10, 14, 11, 221, 224, 221, 224] assumed a fixed
circular sensing range in 2D tasks and a spherical range in 3D tasks. However, some
papers used a directional sensing range especially for some surveillance tasks using
cameras [55, 101, 56, 199]. Reference [153, 36] considered the sensor with a flexible
sensing range so that the combination of different ranges may reach the maximum
coverage rate and save the energy. [123] examined the adjustment for both the
direction and the range. [9] discussed the situation that sensors are positioned with
only approximate accuracy because of practical difficulties and provided the method
to set (near-)optimal radius or errors allowed in the placement. Boukerche and Fei
7

1.4 Mapping
[22] used irregular simple polygon assumption for the sensing range and solved the
problem in recognizing the completely covered sensors and finding holes. In this
report, all the sensors for both targets and obstacles are ideal and omnidirectional.

1.4

Mapping

Geometric maps [20] and topological maps [215, 106] are two kinds of methods for
robots to describe the environment. Although the geometric map is more accurate
containing detailed information of every point of the area, it needs a significant
amount of memory and considerable time for data processing, especially for data
fusion which deals with a huge amount of data collected from other robots. This kind
of work can be seen in navigation using Simultaneous Localization And Mapping
(SLAM) such as [20, 89, 95]. In contrast, the topological map only needs certain
points of the area which is more efficient and applicable. To reduce the memory
load, simplify the control law and save energy in calculations, a topological map
should be used.
Grid map is a kind of topological map. There are three common ways to generate
the grid map from literature. The first way to get the topological map is generating
a Voronoi tessellation [213, 184, 23, 124, 49]. According to Aurenhammer [7] and
Wang [207], a Voronoi diagram with N sensors form s1 to sN in an area can be defined
as a separation of the plane into N subsection with one sensor in each subarea. In a
subarea, the distance from the sensor to a point should be smaller than the distance
from any other sensor to that point. If the subsections of two sensors have a common
border, these two sensors are called neighbor sensors. Voronoi cells are usually used
in sensor deployment to reach a complete coverage. However, with initial random
deployment, the mobile sensors may not be able to communicate with others due
to a limited communication range. Another cell division can be seen in [33] which
used the square grid map. The robots go from the center of one cell to another cell
and visited cells are remembered. This square grid representation is usually used in
the graph search and the tree search algorithms see, e.g., [126]. The third way to
generate the coverage grid is based on uniform tessellation in 2D area and uniform
honeycomb in 3D space.
The third method is used in this report thus it is discussed in detail. Using this
approach, robots will move between the vertices of the 2D grid or the center of the 3D
cells in each step to search the area or reach the complete coverage. Therefore, only
the coordinates and visitation states of the vertices need to be included in the map
which is simpler than the grid generated by Voronoi partition. The uniform division
is used as each robot has the same ability so each cell a robot occupied in complete
coverage or visited in search needs to be the same to maximize the available sensing
range. It also simplifies the algorithm design as each step has a similar pattern. To
cover a 2D area with the grid, a topological map can be made using an equilateral
triangular (T) grid, a square (S) grid or a regular hexagonal (H) grid. [87] proposed
that the T grid pattern is asymptotically optimal as it needs the fewest sensors to
achieve the complete coverage of an arbitrary unknown area. With collisions allowed
and the assumption that robots have no volume, Baranzadeh [11, 10, 14, 12] used
√
the T grid which contains the fewest vertices as the communication range equals 3
times the sensing range. However, in the simulation of those papers, that relation
was not always used. In fact, when considering collision avoidance, the volume of the
8

1.4 Mapping
robot and the obstacle sensing range, the T grid could not always contain the fewest
vertices in different conditions and could only guarantee the complete coverage with
the assumption of the boundary effect [222, 225].
Unlike the proved result in 2D coverage, there is no proven conclusion to shown
which grid pattern could use the smallest number of sensors to cover a 3D space
completely. Coverage related works in 3D include Kelvin’s conjecture [200] for finding the space-filling polyhedron which has the largest isoperimetric quotient and
Kepler’s conjecture [69] for sphere packing in cuboid area [213]. Based on proposed
cells in these two conjecture and considering uniform honeycomb, truncated octahedral (TO) cells, rhombic dodecahedral (RD) cells, hexagonal prismatic (HP) cells,
and cubic (C) cells could be used, and the honeycomb with the minimum number
of cells under different relations between the communication range and the target
sensing range is given in [3, 4]. Then [131, 132, 128, 129, 130, 133] chose the TO
grid based on their common assumption of the large ratio of the communication
range to the target sensing range. However, [129] did not provide the ratio and all
these paper ignore collisions. In this report, to guarantee a strict 100% 2D complete
coverage of the task area, only the T grid could be used with assumptions about
the passage, the relations between different parameters and the curvature of the
boundaries based on [222, 225]. When a complete coverage is not required and the
assumption of the boundary effect is used, the way to choose the suitable grid under
different situations for both 2D and 3D areas is discussed. In simulations, the grid
pattern is chosen based on the parameters of the potential test robots so that the
simulation results can be applied and verified directly in experiments.
When designing the grid map, there are some papers considering the connectivity
of the network [64, 213, 3, 4, 8, 231]. A mobile sensor may need to have more than
one communication neighbors in case some sensors fail. Thus, the extra communication neighbors could provide redundancy of the network and improve the reliability.
However, some papers only considered the general space-filling problem with the
assumption of boundary effect but with no obstacles [3, 4, 8]. The area could be a
convex polygon in 2D areas or a convex polyhedron in 3D spaces [64, 231] as the
assumption of passage width and the volume of robots are not given. [213] limited
the shape of the area further to a cuboid based on the sphere packing problem.
So, in a real task area with irregular shape with obstacles inside, their methods for
multi-connectivity is invalid. In this report, a realistic unknown area is considered,
one sensor only needs to have at least one communication neighbor.
There are also some algorithms without map especially the algorithm inspired
by animals [71, 205, 227, 135, 19]. Animal foragers need to explore the area by only
detecting the randomly located objects in the limited vicinity using the random
walk. The best statistical strategy of optimizing the random search depends on the
probability distribution of the flight length given by [29, 204, 149, 135, 19]. When
the targets are sparsely and randomly distributed, the optimum strategy is the Lévy
flight (LF) random walk which can be seen in marine predators, fruit flies, and honey
bees [136]. It uses the Lévy distribution to generate the step length and the normal
distribution to generate the rotation angle so that robots have fewer chances to go
back to previously visited sites [193, 38, 186, 63, 85, 33, 28]. Thus, robots could
move freely and detect all points in the task area. This scheme means the Lévy
flight algorithm does not need a map to guarantee a complete search of the area
so that exchanging information on the visited areas is also unnecessary and only
9

1.5 Collision-Free Navigation
the positions of visited targets need to be communicated. This algorithm, on the
one hand, largely decreased the demand for memory and on the other hand, is a
kind of a waste of the communication ability. If the number of targets is unknown,
the Lévy flight algorithm could not be used as robots will not know when the area
is completed searched as no map are recorded. Reference [132, 131] considered a
combination of the Lévy flight algorithm and the TO grid for both static target and
moving target. In those two papers, the step lengths were some fixed distances from
one vertex to any other vertex, and the directions were the corresponding direction
from current vertex to the destination vertex. The combined algorithm decreased
the search time comparing to each single algorithm. However, the algorithm only
considered the situation that the number of targets is known but did not consider
obstacle avoidance, so the search area was simple. The algorithm also did not claim
the sensing range for the boundary thus how to reject the long step which would
exceed the boundary is unknown. This report will compare the proposed algorithm
with animal inspired algorithms in [193, 192] and always consider collision avoidance.
The algorithm is available for both when the number of targets is given and when
it is unknown.
Some current algorithms in coverage problems were heuristic [33, 123, 37] but
there were still several papers with grid maps having rigorous proofs [43, 39]. [170]
achieved 100% coverage of an unknown 2D area with a mathematical proof, but
it exceeded the boundary of the area which only has limited applications such as
using the UAV in open airspaces to cover the ground or the sea surface. If there
are solid walls or coastlines and ground robots are used, this algorithm could not
work. If the boundary of the area is a borderline in a military application, exceeding
the boundary is also forbidden. Although [11] used a T grid inside the boundary,
the routes of robots still exceeded the boundary which can be seen in its simulation
figures. The reason for this problem is that the author thought the assumption that
all accessible vertices are connected equals to the assumption that accessible vertices
can be reached by moving along the shortest path, however, there may be no vertices
to go through in that path. Even if there were vertices in the shortest passage, they
might be too close to the boundary considering the volume of the robots. Thus,
those vertices should be thought as blocked so that robots should choose a longer
path. If two vertices are reached from two unconnected edges, the section between
the two vertices may still be undetectable because of the short sensing range which
is only set to be greater than zero in [11]. This report proves the convergence of all
the proposed algorithms without asking robots to go beyond the boundary.

1.5

Collision-Free Navigation

For a multi-robot system, the increased number of robots leads to a higher possibility for robots to encounter each other also rises. However, some algorithms for
single robot navigation are no longer available. Therefore, collision avoidance is a
significant and attractive research topic in multi-robot systems.
Navigation strategies can be categorized into global methods and local methods.
The global one is off-line path planning. Given the global information about the
environment and obstacles as a priori, the robots will build a model of the scenario
[166] and find an optimal traceable path to solve the problem and avoid collisions
[206]. If a path is known, an appropriate velocity profile will be planned for col10

1.5 Collision-Free Navigation
lision avoidance [144]. This problem can be thought as resource allocation thus
corresponding algorithms can be utilized. Although this method is robust to deadlock situation, the disadvantages of it are clear that the environment of the system
should be known and be structured for the algorithm to segment it to separated
pieces [77]. These disadvantages lead to a centralized thought of the problem and
cannot be conveniently and easily modified to a decentralized approach. [142] proposed an algorithm in a known area. It used ring-shaped local potential fields to
have a path-following control of a nonholonomic robot. In some situations, a part
of the information is given. For instance, the edge of the area in [220] was known
and in [128, 133], the equation to describe the covered area was given. [46] provided
semantic information to assist the exploration. In many path planning and navigation problems like [51], the limited knowledge was given which was the direction
from the starting point to the target. This is possible in a workspace or factory floor
by installing radio beacons at the target so that the robot can track the beacon to
plan the path.
For the local or reactive method, algorithms are based on sensed and shared
local information. The drawback of some algorithms with this approach is that
they are not based on the kinematic model with realistic constraints of the robot.
Instead, they used heuristic methods. Without justification and mathematical proof,
some methods may fail in special circumstance. For example, the control algorithm
in [61] would work for two or more robots under the conditional that the robot
had a constant speed. If the acceleration was limited for a holonomic robot, a
potential field approach could support the control of three robots at most based on
[73]. To control an unlimited number of robots with no collision, [187] used robots
with unbounded velocity and [202] assigned the velocity of the robot as the control
input. In reactive methods, the artificial potential field algorithm is widely used
[18, 182, 54, 109, 158, 142, 73] as it generates a safe path to the target with little
computational effort. It generates a gradient field between robots and targets to
direct the movement of robots [181]. In that field, goals like the targets generate
the attractive force and act like valleys in the field. Obstacles and boundaries
generate the repulsive force, acting like peaks in the field. So, the superposition of
the two fields will drive robots to go downhill towards targets while moving away
from obstacles. One disadvantage of the algorithm is that robots can be trapped in
local minima which results in the failure of the navigation task. Therefore, [193, 192]
only used the repulsive force between robots to disperse them to move in different
directions, which is also utilized in this report based on [222, 225, 221].
Examples in the above two paragraphs were all considering steady obstacles.
More methods in this category include dynamic window [60], the lane curvature
[90] and the tangent graph based navigation [166]. For dynamic obstacles including
moving and deforming obstacles, it is tough to solve. Thus, many methods put constraints on the moving velocity of obstacles or the changing speed of shapes. The
obstacles were usually explained as rigid bodies with a selected shape. Moreover, in
[166], the characteristic point of the robots in concern with its global geometry is
calculated, and velocity of the obstacles is achieved. A local method with range-only
measurements in [121] allowed the shape of obstacles to be a time-vary variable, but
it had a fierce limitation on the robots’ velocity. Inspired by binary interaction
model, a reactive approach with integrated sensed environment presentation was
illustrated in [166]. This method did not require approximation of the shapes of
11

1.6 Contribution Highlights
obstacles and velocity information of obstacles. It would find a path between obstacles without separating obstacles. In the deployment and complete coverage part
of this report, local navigation is needed. With a grid pattern, collision avoidance
is easier. In the beginning, robots only know their initial positions are within the
search area without other knowledge about the area. However, while moving, the
robots are generating their maps about the visited areas so that the global method
could also be used.
A large percentage of research in coverage, search, formation, and consensus did
not consider the problem of collision avoidance such as [11, 170, 132, 131, 128, 129,
130, 133]. Most of them used simulations to verify the algorithms, and a robot is
always assumed as a particle point without the volume. [170, 11] assumed that if
more than one robots chose the same vertex to go, those robots would stay around
the vertex and the vertex was thought as a parking lot. However, it did not show
how to choose a parking space. Even with a parking space choosing mechanism,
when the number of robots increased, there would be more robots choosing the
same vertex so that the car park model is not available. Therefore, in this report,
robots would not choose together, and the communication range should be designed
large enough so the choice can be known by all robots which may select the same
vertex in this step. Although there will be more communication cost, the robots can
avoid collisions while choosing the next step instead of during moving. In [10, 14],
robots could move with different distance in one step which resulted in collisions
during moving. However, the velocity of the movement was not stated, and the
strategy for collision avoidance was not stated clearly. Also, the proposed algorithm
in [14] could not match its result in its experiment. Therefore, in this report, robots
always move with the unit step length to avoid this problem.

1.6

Contribution Highlights

The main contributions of the report can be described as follows:
1. One decentralized algorithm for the complete coverage is proposed for multiple
mobile robotic sensors to deploy themselves in both 2D and 3D areas. The
detailed descriptions of the coverage algorithms are presented.
2. The report proposes three decentralized random algorithms for the search task
in 2D or 3D areas. They are improved step by step.
3. The task areas for the four algorithms are arbitrary unknown with obstacles
inside. For complete coverage in a 2D area, assumptions about a large target
sensing range and the curvature of boundaries are given. For other problems,
if the boundary effect is ignorable, these two assumptions are not needed.
4. All algorithms utilize grid patterns to cover the area and robots move between
vertices of a grid. The methods to choose the best grid, namely, the grid with
the fewest number of vertices in a 2D area and the fewest cells in a 3D area,
are proposed considering the relation between different parameters. In some
previous algorithms, the sensing range for obstacles was not considered.
5. All algorithms consider collision avoidance between robots and between robots
and boundaries. Also, realistic constraints of robots including the volume are
12

1.7 Report Outline
set based on potential test robots. Robots choose the next step in a sequence,
and they are always synchronized.
6. Simulations in MATLAB are used to demonstrate the performance of the
algorithms. Another complete coverage algorithm and other five algorithms
for search tasks are simulated in the same area to show the effectiveness of the
proposed algorithms.
7. The convergence of all algorithms are mathematically proved which is different
from many heuristic algorithms.
8. The algorithms are suitable for both 2D areas and 3D areas. Only slight
modification based on the grid structures are needed. So it is easy to adjust
them to apply to the other dimension.
9. For the three search algorithms, the number of targets can be known or unknown.
10. Using the simulation result of the second search algorithm, the way to generate
the mathematical relation between the search time, the size of the area and the
number of robots is given. The effects of other parameters are also discussed.
11. Experiments for the second search algorithm is conducted on Pioneer 3-DX
robots to verify its performance in real situations and to help design errors of
the algorithm.

1.7

Report Outline

The remainder of the report is organized as follows:
Chapter 2 describes the method to choose the best grid pattern to cover the area
for the four algorithms considering related parameters of robots. It introduces the
basic definitions about the task area with assumptions for complete coverage and
for coverage ignoring the boundary effect. The grid pattern for potential test robots
which are the Pioneer 3-DX in 2D and the Bluefin-21 in 3D are chosen. Chapter 3 provides a decentralized complete coverage algorithm for the self-deployment
of multiple robots in both 2D and 3D areas without collisions. The convergence
of the algorithms is proved with simulations to show its efficiency comparing to
another algorithm. Then three distributed search algorithms in 2D and 3D areas
are presented in Chapter 4, 5 and 6 respectively. Rigorous mathematical proofs
of the convergence of these algorithms are provided, and they are all simulated in
MATLAB with comparisons to other five algorithms to show the effectiveness. In
Chapter 4, a decentralized random algorithm for search task is provided by using
the visitation state of the neighbor vertices. The second search algorithm in Chapter
5 adds potential field algorithm on the first one to disperse robots and decrease the
repeated routes. In 2D area, some factors affecting the search time are analyzed and
the way to find the relation between search time and other parameters are given.
Also, experiment on Pioneer 3-DX robots is used to check the performance of the algorithm. Chapter 6 adds breadth-first search algorithm on the algorithm in Chapter
4. It helps robots to jump out of the visited area by looking for the nearest unvisited
vertex in their local maps. The three proposed search algorithms are also compared
13

1.7 Report Outline
with each other to analyze their own merits and demerits. Chapter 7 concludes the
report and provides some possible future research topics to improve or to extend the
presented work.

14

Chapter 2
Grid Selection for Coverage in 2D
and 3D Areas
For complete coverage of an unknown area, mobile sensors are put into the area
and need to move to some places which form a grid to maximize the coverage of
the team. For search problems, robots move around the area until all targets are
found, or the entire area is detected. To ensure the whole area is sensed, robots also
need to have a map. Moreover, to cover or search the area easily, the grid pattern
could be used as a topological representation of the area to decrease the information
needed during movement of the two tasks. Then in a 2D space, the robot can move
from a vertex of the grid to one of the nearest neighbor vertices straightly, and in
a 3D area, robots can move straightly from the center of a polyhedron to one of
the closest centers of another polyhedron. As the robot has a sensing range for the
target, after visiting all the vertices, the whole area can be searched if the distance
between two cells of the grid is set reasonably. Similarly, in the complete coverage
task, after mobile sensors are deployed to those nodes, the whole area is covered.
With a grid pattern, robots only need to record the positions of the vertices in a
2D area or the centers of polyhedrons in a 3D area to build their maps. Thus, this
topological method also decreases the memory and calculation load comparing to
the geometrical method.
Looking for a grid to cover an area is the same as the tessellation problem for
a plain and the honeycomb for a 3D space. As robots in the system have the same
sensing ranges and the same communication range, regular tessellation and spacefilling could be considered to simplify the design of the control rule further. Different
grids have different numbers of vertices. If the same control algorithm is applied, it
is intuitive that the search time will be affected by the number of vertices. When
robots select the next vertex, they need to ensure that there are no obstacles on the
path to that vertex, so the obstacle sensing range is considered in grid selection. In
the selected grid, robots also need to form the sensing coverage of the whole area and
communicate with neighbor robots to exchange information so the target sensing
range and the communication range should be considered.
This chapter finds the grid with the minimum number of vertices to cover the
area considering different coverage requirements and all kinds of relations between
parameters about ranges of the robots. The selection criteria are applicable for both
complete coverage and search tasks. Section 2.1 considers the problem in a 2D area
while Section 2.2 considers the selection criteria a 3D area. A summary of the grid

15

2.1 Grids for 2D Areas

(a) An equilateral triangular
grid

(b) A square grid

(c) A regular hexagonal grid

Figure 2.1: Three regular tessellation patterns
selection is shown in Section 2.3.

2.1

Grids for 2D Areas

This section illustrates that only the T grid can provide a 100% complete coverage. It
also proposes the general method to select the grid with the least number of vertices
in a 2D area if areas near boundary can be ignored by considering the communication
range, the target sensing range and the obstacle sensing range of robots. Then the
rule is applied to a Pioneer 3-DX robot to see which grid is suitable for it in a search
task.
The tessellation of a plane surface is tiling it with one or more geometric shapes.
Each of the shapes can be called as a tile. When considering the same tiles for
tessellation, three forms for regular tiling can be used which are square, equilateral
triangle, and hexagon as seen in Figure 2.1. If only considers the circular sensing
range for targets, this problem is the same as allocating base stations to get the
maximum coverage area in telecommunication. Then based on [156], the T grid
should have the least number of vertices. However, in this report, the communication
range and the obstacle sensing range are also discussed. Thus, the result in [156]
may no longer be available. However, [11, 170, 12, 10, 14] still used the T grid to
design the algorithm and based on this pattern to find the relation between the
target sensing range and the communication range. The sensing range for obstacles
was set equal to the side length of the tile. However, in real applications, the search
or coverage algorithms may be applied to different robots. Thus, the problem needs
to be thought oppositely, namely, choosing the grid based on the parameters of
robots. There are two kinds of requirements for selecting the grid. One is strict
as in [170], and the other is loose which can be seen in [11, 3, 4, 131]. Next, the
assumptions for different ranges are given followed by the discussion subjected to
these two requirements.

16

2.1 Grids for 2D Areas

2.1.1

Definitions and Assumptions

This section takes advantage of the method of definitions in [225]. Examples to
illustrate the relation between ranges are given using a T grid.
Assumption 2.1.1. The search area A ⊂ R2 is a bounded, connected and Lebesgue
measurable set. Robots know nothing about the area initially.
There are m robots labeled as rob1 to robm in A. For the basic tiling shape, the
side length of the shape is represented as a and robots can only move the distance a
along the side in each step from one vertex of the grid to one of the nearest neighbor
vertices.
Assumption 2.1.2. In the 2D area, all the ranges for robots are circular.
Robots have a swing radius rrob . Let the maximum possible error containing
odometry errors and measurement errors be e. Then a safety radius rsaf e can be
defined to avoid collision.
Definition 2.1.1. To avoid collisions with other things before move, a safe distance
rsaf e should include both rrob and e (see Figure 2.2). So rsaf e ≥ rrob + e.
Thus, vertices which are within rsaf e away from the boundaries or obstacles
should not be visited. In Figure 2.2, vertex2 is within rsaf e of the obstacle so it
cannot be reached. This means the obstacles around vertex2 need to be detected
from robi so it will not choose to move there. Thus, sensors on robots should have
a large enough sensing range rso for obstacles. So rso should satisfy the following
assumption and can be seen in Figure 2.2 and Figure 2.3.
Assumption 2.1.3. rso ≥ a + rsaf e .
The vertices which are within rso of robi are called sensing neighbors of robi .
Robots are equipped with wireless communication tools with the range rc . Those
robots within rc of robi are called communication neighbors of robi . The communication between robots is temporary as in an ad-hoc network so each robot can be
considered equal with a local communication range. To avoid having the same choice
with other robots in the same step, robots should choose in a certain order and tell
the choice to neighbor robots which are one or two vertices away from it. A possible
order for search tasks given in Figure 2.3 is that robots on the right side and the
top of the current robot should have higher priorities. This order will be explained
in Chapter 4 in detail. Considering the error e, rc should satisfy Assumption 2.1.4.
Assumption 2.1.4. rc ≥ 2 ∗ a + e.
Now, the length of a step can be shown as an inequality:
a ≤ min(rso − rsaf e , (rc − e)/2)

2.1.2

(2.1)

The Strict Requirement

This requires robots to have a complete search through the grid. Only a T grid can
be used under this circumstance with the assumptions 2.1.5 2.1.6 and 2.1.7 below.
17

2.1 Grids for 2D Areas

Figure 2.2: The illustration for a, rsaf e and rso

Figure 2.3: rso , rc and the selection order in search

18

2.1 Grids for 2D Areas

Figure 2.4: Curvature example for the equilateral triangular grid
Assumption 2.1.5. rst ≥ a + rsaf e .
This assumption for the sensing range for targets guarantees that areas around
inaccessible vertices can still be detected. For example, in Figure 2.4, black circles
have a radius of a + rsaf e and the red line is the boundary. It can be seen that
vertex v4 is less than rsaf e away from the boundary so it cannot be visited. But the
Assumption 2.1.5 guarantees that the area D near v4 can be detected by robots at
vertices v1 , v2 and v3 .
Assumption 2.1.6. The curvature of the concave part of the boundary should be
smaller than or equal to 1/rst .
Without this assumption, some parts of the searched area may not be detected
such as section A in Figure 2.4. In that figure, circles enclose all the sensed area
and section A, B and C have segments with curvatures greater than 1/rst . It can
be seen clearly that section A cannot be detected or visited although section B and
C can be detected luckily. The reason that the S grid and the H grid are not used
is that there are no such kinds of limitations to guarantee a complete coverage. For
the S grid, Figure 2.5 demonstrates that the setting of curvature will be useless as
there is no vertex near the intersection point p of sensing ranges. Thus, a curve with
any curvature could go beyond p and left a section being undetected like section A.
The H grid has the same problem.
Assumption 2.1.7. Let Wpass represents the minimum width of the passages between obstacles or between obstacles and boundaries. Then Wpass ≥ a + 2 ∗ rsaf e .
This assumption guarantees that there is always at least one accessible vertex in
the path. Otherwise, if the passage is not large enough as in Figure 2.6, robots at
19

2.1 Grids for 2D Areas

Figure 2.5: Example of the curvature in the S grid
va will not arrive at vb as robot can only move a in a step but vertices vc , vd , ve and
vf are inaccessible, leaving a section in between undetectable.

2.1.3

The Loose Requirement

This only requires that all vertices are sensed because it has an assumption about
the boundary effect which can be seen in [221, 224, 3, 4].
Assumption 2.1.8. The search area is usually very large. So, a is much smaller
than the length and the width of area A. Therefore, the boundary effect is negligible.
This assumption means that there are no targets in the area near the boundary
such as the slashed area under point p in Figure 2.5 so robots do not need to
completely sense the area and Assumption 2.1.6 is not needed. Thus, all the three
kinds of grids can be discussed. Then Assumptions 2.1.5 and 2.1.7 for rst and Wpass
are made differently based on the structure of each grid pattern. Here, Wpass is still
used to design the minimum passage width so the passage can be passed by a robot.
But the usage of rst is to ensure that all the sections between accessible vertices
are completely sensed which is different from the requirement that all sections are
completely sensed in the strict requirement. Table 2.1 shows the relation between
rst , a, rsaf e and rrob and the value of Wpass represented by a and rsaf e for each grid
pattern. The subscript of a is the notation for the name of the corresponding grid.
To use the least number of vertices in the search area, for the same a, one vertex
needs to have the fewest neighbor vertices so that the polygon (tile) occupied by each
20

2.1 Grids for 2D Areas

Figure 2.6: A narrow path

Shape

rst

T

aT ≤

S

aS ≤

H

Wpass

√
3(rst − rsaf e + rrob )
√

2(rst − rsaf e + rrob )

aH ≤ rst − rsaf e + rrob

aT + 2rsaf e
√

2aS + 2rsaf e

2aH + 2rsaf e

Table 2.1: Wpass and rst for each grid

21

2.1 Grids for 2D Areas
vertex has the maximum area. Also, the maximum a should be used. [8] found the
grid pattern which results in the minimum number of vertices using different rc /rst
for a static coverage problem. This report considers three parameters in choosing the
grid pattern, namely, rc , rso and rst , which will be different based on the used devices.
So, the discussion regarding these three parameters for general situations is provided
based on the maximum a in the primary results in Inequality 2.1 and in Table 2.1.
In this subsection, the result in Inequality 2.1 is labeled as a1 and the result from
Table 2.1 is labeled as a2 . To simplify the discussion and illustrate the procedure of
the calculation only, e and rsaf e which depend on the selected equipment are ignored
while collision avoidance is still considered.
results to maximize a are
√
√ So the primary
simplified as a1 = min(rso , rc /2), a2T = 3rst , a2S = 2rst and a2H = rst . Then the
maximum a can be written as a = min(a1 , a2 ). If a1 > a2 , the area is represented
by rst which is the same for the three grid patterns as it is a fixed parameter from
the chosen robot. Otherwise, a = a1 and the area is represented by a1 which is also
the same in the three grids. Table 2.2 demonstrates the area S occupied by each
vertex and Wpass in different conditions. S and Wpass have subscripts to indicate the
types of the grid. The data in the table have three colors representing the ranking
of the values with red for the large value, orange for the medium value and cyan for
the small one. According to this table, if a1 ≥ 1.52rst , the T grid should be used
to have the least number of vertices. If 1.52rst ≥ a1 ≥ 1.14rst , the S grid should be
used. An H grid will be used when 1.14rst ≥ a1 . Although larger a leads to fewer
vertices and less search time, it will increase Wpass and thus will shrink the scope of
applicability.

2.1.4

The Choice for the Pioneer 3-DX Robot

Pioneer 3-DX robots in Figure 2.7 is widely used in research. The second search
algorithm in this report also uses it to verify the performance. Therefore, this robot
is introduced and the suitable grid pattern for it will be selected. Based on the
above discussion, for a complete coverage, a T grid must be used, so only the grid
pattern under the loose requirement need to be chosen based on the parameters
of this robot. The robot has 16 sonars around which is the yellow circle in the
figure. The layout of the 8 sonars in the front can be seen in Figure 2.8. There
are other 8 sonars at the symmetrical rear side of the robots. Thus, the robots can
sense the environment through 360 degrees. The sonar is used to sense obstacles with
0.17m < rso ≤ 5m. The target is sensed by the laser which is the cyan part in Figure
2.7. The laser model is SICK-200 which has rst = 32m for a range of 180 degree
which is illustrated in Figure 2.9. To detect 360 degrees, the robot needs to turn
around after the detection of one side is finished. For communication, the robot uses
a Cisco Aironet 2.4 GHz Articulated Dipole Antenna AIR-ANT4941 with rc = 91.4
at 1Mbps typically in an indoor environment. In calculations, equality conditions of
the inequalities are used. Therefore, the maximum a1 = 5 as a1 ≤ min(5, 91.4/2).
As 1.14rst > a1 , the H grid should be used. Base on Table 2.2, this belongs to the
last (7th) situation. From Table 2.1, a2H = 32m. So the side length of the H grid is
a = min(a1 , a2H ) = 5m. Then Wpass = 10m.

22

2.1 Grids for 2D Areas

Range a1 ≥ 1.73rst

1.73rst ≥ a1 ≥
1.52rst

1.52rst ≥ a1 ≥
1.41rst

1.41rst ≥ a1 ≥
1.23rst

ST

2
2.60rst

0.87a1 2

0.87a1 2

0.87a1 2

SS

2rst 2

2rst 2

2rst 2

a1 2

SH

1.30rst 2

1.30rst 2

1.30rst 2

1.30rst 2

WpassT 1.73rst

a1

a1

a1

WpassS 2rst

2rst

2rst

1.41a1

WpassH 2rst

2rst

2rst

2rst

Range 1.23rst ≥ a1 ≥
1.14rst

1.14rst ≥ a1 ≥
rst

rst ≥ a1

ST

0.87a1 2

0.87a1 2

0.87a1 2

SS

a1 2

a1 2

a1 2

SH

1.30rst 2

1.30rst 2

1.30a1 2

WpassT a1

a1

a1

WpassS 1.41a1

1.41a1

1.41a1

WpassH 2rst

2rst

2a1

Table 2.2: Wpass and the area occupied by each polygon

23

2.1 Grids for 2D Areas

Figure 2.7: The Pioneer 3-DX robot

Figure 2.8: Layout of 8 sonars in the front

24

2.2 Grids for 3D Areas

Figure 2.9: Range of the laser SICK-200

2.2

Grids for 3D Areas

This section proposes the general method to select the grid pattern to cover a 3D
area with the fewest vertices. Different relations between the communication range,
the target sensing range, and the obstacle sensing range are discussed in a Table.
Then the suitable grid for the UUV, Bluefin-21, will be chosen using that table.
Tessellation in a 3D area is called honeycomb which is filling a 3D space with
cells. As discussed in 2D area, the same cell is used to simplify the representation of the area and the control algorithm design. Honeycomb is more complicated
than tessellation as there are no proven results for which grid pattern will use the
fewest cells to cover a grid if the same sensing range is employed in all grid patterns. However, based on similar problems such as Kepler’s conjecture and Kelvin’s
conjecture [3, 4], possible polyhedrons include the C grid, the HP grid, the RD grid
and the TO grid as seen in Figure 2.10. [3, 4] also discussed which grid should
be chosen under different rc /rst . Then [129] chose the TO √
grid√without giving the
communication range. However, rc ≥ 1.549rst (which is, 2 3/ 5rst ) is enough to
connect all vertices. But when 1.587rst ≥ rc ≥ 1.549rst , an HP grid should be
used. Then √
[131, 132, 128, 130, 133] considered the situation for rc ≥ 1.789rst
(which is, 4/ 5rst ). However, as collision avoidance was not discussed in detail,
these papers did not have rso . Moreover, they were considering the question of
designing the best grid pattern to cover the area and setting the ranges based on
this grid. But, in reality, the search or coverage algorithms should be applied to
different robots carrying devices with various ranges. So this chapter is based on
the range related parameters of the robots to find the corresponding suitable grid
pattern. Different from 2D problems, this section only discusses the grid selection
which complies with the loose requirement.

25

2.2 Grids for 3D Areas

(a) cubic

(b) hexagonal prismatic

(c) rhombic dodecahedral

(d) truncated octahedral

Figure 2.10: Four uniform honeycombs

2.2.1

Definitions and Assumptions

This section will take advantage of the method of definitions in [221]. Examples to
illustrate the relations between ranges are given in a C grid.
Assumption 2.2.1. A three-dimensional area A ⊂ R3 is a bounded, connected and
Lebesgue measurable set.
There are m robots labeled as rob1 to robm in A.
Definition 2.2.1. If there are edges with different lengths in the grid and robots can
visit all vertices through various sets of lengths of edges, then the maximum length
of each set is compared with others, and the smallest one is chosen to be the edge
length a. Then robots move the distance a from one vertex straightly to an accessible
neighbor vertex in one step.
3D grids based on a uniform honeycomb are used, and the center of the polyhedron is the vertex of the grid. Then the grid is built up by connecting the vertices
to its nearest surrounding neighbor vertices.
Assumption 2.2.2. All sensors and communication equipment on robots have spherical ranges. The range using the word radius also refers to a spherical radius .
Let the swing radius of robots be rrob . Then the total error of robots is represented as e and the safety radius is rsaf e . Then we have a similar definition as
Definition 2.1.1 and two similar assumptions for the obstacle sensing range rso and
the communication range rc as Assumptions 2.1.3 and 2.1.4. The only difference is
that the ranges in these definitions are spherical instead of circular.
26

2.2 Grids for 3D Areas

Shape

rst
aC ≤

C

√
3(rst − rsaf e + rrob )/2

HP

aHP ≤

RD

aRD ≤

TO

√
√

2(rst − rsaf e + rrob )

2(rst − rsaf e + rrob )

√
aT O ≤ 5(rst − rsaf e + rrob )/2/ 15
Table 2.3: rst for each 3D grid

Definition 2.2.2. rsaf e ≥ rrob + e so that the collisions with other things could be
avoid by path planning before a move (see Figure 2.11).
Assumption 2.2.3. rso ≥ a + rsaf e .
Assumption 2.2.4. rc ≥ 2 ∗ a + e.
So, the length of a step is
a ≤ min(rso − rsaf e , (rc − e)/2).

(2.2)

Vertices which are within rso of robi are called sensing neighbors of robi . Robots
within rc of robi are called communication neighbors of robi . The communication in
the 3D space also uses the ad-hoc network with an omnidirectional antenna to get
the spherical coverage.

2.2.2

The Loose Requirement

In the loose requirement, the area between vertices must be fully covered, and the
area between outer sensing spheres to the boundaries can be ignored as the following
assumption is used.
Assumption 2.2.5. The search task for a team of robots usually has a vast area.
So, a is much smaller than the length, the width and the height of area A. Therefore,
the boundary effect is negligible [3, 4].
When selecting the type of the polyhedron, the number of polyhedrons to fill the
3D space needs to be minimized, so the maximum a needs to be used. For the same
a, one vertex needs to have the fewest sensing neighbors to allow each polyhedron to
have the maximum volume. For the HP cell, there are two kinds of edges to connect
vertices and robots must move along both to visit all vertices so that a equals to the
longer one. For a TO cell, there are also two kinds of edges, but robots can visit all
vertices through the shorter one only so a equals to the shorter one to maximize the
volume of the polyhedron. The relation between rst and a and listed in Table 2.3.
In the 3D space, the three parameter of robots, namely, rc , rso and rst , are still
considered in the discussion to find the grid with the fewest vertices in different
situations. Thus, the results in [3, 4] which considered rc and rst only for a similar
27

2.2 Grids for 3D Areas

Figure 2.11: a, rsaf e , rso , rc and the order of selection in search.

28

2.2 Grids for 3D Areas

Range a1 ≤ 1.1547rst

1.1547rst
≤
a1 ≤ 1.2599rst

1.2599rst
≤
a1 ≤ 1.2961rst

1.2961rst
≤
a1 ≤ 1.4142rst

VC

a31

1.1547rst 3

1.1547rst 3

1.1547rst 3

VHP

0.7071a1 3

0.7071a1 3

0.7071a1 3

0.7071a1 3

VRD

0.7071a1 3

0.7071a1 3

0.7071a1 3

0.7071a1 3

VT O

0.7698a1 3

0.7698a1 3

0.7698a1 3

0.7698a1 3

1.5431rst
≤
a1 ≤ 1.5492rst

rst ≤ 1.5492a1

Range 1.4142rst
≤
a1 ≤ 1.5431rst
VC

1.1547rst 3

1.1547rst 3

1.1547rst 3

VHP

1.4142rst 3

1.4142rst 3

1.4142rst 3

VRD

1.4142rst 3

1.4142rst 3

1.4142rst 3

VT O

0.7698a1 3

0.7698a1 3

1.5492rst 3

Table 2.4: The area occupied by each cell
problem cannot be used. The discussion in this section uses the maximum a in
the primary results in Section 2.2.1 and in Table 2.3, which are represented as a1
and a2 here. Similarly, e and rsaf e are ignored as to simplify the discussion and
only illustrate the procedure of calculation. These two parameters are affected by
the accuracy of the equipment and the disturbance in the environment. However,
collision avoidance is still considered in the algorithm
design. The primary results
√
3(rst − rsaf e + rrob )/2, a2HP
to
so , rc /2), a2C =
√ maximize a are a1 = min(r
√
√ =
2(rst −rsaf e +rrob ,a2RD = 2(rst −rsaf e +rrob and a2T O = 5(rst −rsaf e +rrob )/2/ 15.
Thus, the maximum a = min(a1 , a2 ). To represent the volume occupied by each
polyhedral cell, the same method as in 2D is used. So when a1 > a2 , the area is
represented by rst which is a fixed parameter from the selected robot. Otherwise,
a = a1 and the area is represented by a1 which is calculated using the other fixed
parameter rso rso . Therefore, the value in the table are comparable for the four
grid patterns. Table 2.4 only shows the volume V with subscript to describe the
shape of the polyhedron occupied by each vertex. Colored values are also used
in the table to show the comparison result with red for the large value, orange
for the medium value and cyan for the small one. The table shows that the C
grid should be chosen when a1 ≤ 1.2599rst and the HP or RD grid should be
employed when 1.4142rst ≤ a1 ≤ 1.5431rst . For the TO grid, it is used when
1.2599rst ≤ a1 ≤ 1.4142rst and a1 ≤ 1.5431rst to have the least number of vertices.

29

2.3 Summary

Figure 2.12: Bluefin-21[21]

2.2.3

The Choice for the Bluefin-21 Robot

Bluefin-21 is a UUV (see Figure 2.12) which carries multiple sensors and payload for
tasks such as search, salvage and mine countermeasure [21]. It is famous in searching
MH370 which is also the inspiration of the research of this report. In the search task,
the sensor for underwater locator beacon has a target sensing range as rst = 1km
at least in the normal condition [86]. The sensor for obstacles is the EdgeTech
2200-M side scan sonar. It has different sensing ranges at different frequencies and
resolutions. To guarantee the obstacle avoidance is successful, the minimum one
rso = 75m is used to ensure the accuracy. For the local communication, there is
no information in the datasheet for the equipment used and for the range that it
can communicate in so that the parameter of the 2D robot is used which is a WiFi communication with rc = 91.4m. In calculations, all the equality conditions
of the inequalities are used. Thus, based on Inequality 2.2, the maximum a1 =
min(75, 91.4/2) = 45.7m. As a1 < 1.1547rst , the first column of Table 2.4 is used
and the C grid is chosen. Then a = min(a1 , a2 ) = 45.7m and the corresponding
assumptions for passage width Wpass is given.
Assumption 2.2.6. All passages between obstacles or between the obstacles
and
√
borders have a cross-section which can include a circle with a radius of 3a + 2rsaf e .
This can be seen in Figure 2.13
So the theoretical Wpass without rsaf e is 79.1547m. This guarantees that there
is always at least one accessible vertex in the cross-section which is illustrated in
Figure 2.13. In the figure, the robot moving from a blue vertex (x) to a red vertex
(+) must go through a black vertex (o) as the robot can only move a in a step.
Although it is obvious that decreasing a will expand the scope of applicability, the
number of vertices will increase so the search time will also increase.

2.3

Summary

In summary, this chapter proposed that a grid pattern should be used as the final
location to deploy the Wireless Mobile Sensor Network and the representation of
the area for both search and complete coverage tasks. Three regular tessellations
30

2.3 Summary

Figure 2.13: Passage width for a 2D area
in a 2D field and four uniform honeycombs in a 3D area were considered. Then
Table 2.2 for 2D and Table 2.4 for 3D are provided as the tables of selection criteria
for different relations between the communication range, the target sensing range
and the obstacle sensing range. Then typical robots which are Pioneer 3-DX robots
in 2D and Bluefin-21 robot in 3D were used to exemplify the selection procedure.
Based on the result, later simulation and experiment will mostly use the T grid in
2D tasks and the C grid in 3D tasks.

31

Chapter 3
Optimal Collision-Free
Self-Deployment for Complete
Coverage
Complete coverage is an attractive topic for multi-robot systems. It means each
point of the task area is detected by at least one robot so the team can cover the
area completely for surveillance or data collection. In this task, communication
between the robots is usually required so each robot should be connected to at least
one robot to form a network. Thus, any incident in the area or any intruder moving
into the area will be known by the whole network to take further action. The mobile
robotic sensor network in this chapter is an example of a networked control system
with limited communication [112, 113, 117, 116]. As the area to cover is unknown
or may be dangerous, robots could not be deployed manually and thus, need to be
released from a known entrance to the area. While moving to the final location, the
process should be as fast as possible, so the optimal algorithm to drive the robots
while avoiding collisions is found in this chapter.
Self-deployment algorithm for 2D and 3D areas can be found in [170] and [128]. In
their deployment phases, all robots applied the decenalized random (DR) algorithm
at the same time which is impossible to cover the area completely because the
algorithm could only work when there is a sequence of choice and robots inform the
selection to neighbor robots which, however, was not mentioned in [170, 128]. Thus,
the absorbing state in their proof may not be reached, and the algorithm may be
invalid. The DR algorithm has a disadvantage that robots need to convert received
coordinates to their coordinate system which leads to a large calculation load. To
compare to the DR algorithm, robots in this chapter also start from certain vertices
of a shared grid in some possible ways. Then, an optimal navigation algorithm is
designed to have the fewest steps for coverage.
This chapter presents a novel distributed algorithm for deploying multiple robots
in an unknown area to achieve complete coverage. The task area can be twodimensional or three-dimensional and it is bounded and arbitrary with obstacles and
certain assumptions. The robots with limited sensing ranges and a limited communication range move in sequence via grid patterns which were chosen in Chapter 2
to reach the complete coverage. The algorithm sets a reference point and drives the
furthest robot first to move to one of the most distant neighbor vertices in each step
with no collisions. Finally, every point of the area can be detected by at least one

32

3.1 Completer Coverage in 2D
robot and robots achieve this using the fewest steps. If the task area is enlarged
later, the algorithm can be modified easily to fit this requirement. The convergence
of the algorithm is proved with probability one. Simulations are used to compare
the algorithm with valid modification of the DR algorithm in different areas to show
the effectiveness and scalability of the algorithm.
The rest of the chapter will be divided into two sections for the 2D problem
and the 3D problem respectively. Each section will start with the problem statement followed by the description of the algorithm. Then MATLAB simulations and
the comparison with another algorithm are shown, and finally, a summary will be
provided.

3.1

Completer Coverage in 2D

This section provides a decentralized collision-free algorithm to deploy multiple
robotic sensors in a task area A with obstacles to achieve the 100% complete coverage using a T grid pattern based on Chapter 2. Thus, intruders entering the covered
area can be detected. This section takes advantage of the methods for the definition
and assumption in [11, 225, 168]. Some assumptions and definition about the area,
ranges, and the curvature under the strict requirement have been claimed in Section
2.1.1 so they are used directly without explaining. The original work of this section
comes from [225].

3.1.1

Problem Statement

Assumption 3.1.1. There are a finite number of obstacles O1 , O2 ,. . ., Ol and
obstacles Oi are non-overlapping, closed, bounded and linearly connected for any
i > 0. The obstacles are static, arbitrary, and unknown to the robots a priori.
S
Definition 3.1.1. Let O := Oi for all i > 0. Then Ac := A \ O represents the
area that needs to be covered. Area Ac can be static or be expanding.
In each move, a robot translates straightly from a vertex represented as vi of
the grid to the selected vertices vj which is one of the nearest neighbors. Thus,
the moved distance is the side length a of the basic grid pattern. In Ac , the set of
accessible vertices is denoted by Va . If |•| is used to represent the number of elements
in set •, |Va | will represent the number of accessible vertices. m robots with the same
sensing and movement ability are released from Ni initial known vertices to cover
Ac . Then for the optimal deployment, let No represent the number of steps needed.
For the complete coverage, the number of robots prepared needs to satisfy
Assumption 3.1.2. m ≥ |Va |.
The set containing sensing neighbors at discrete time k is denoted as Ns,i (k)
and its jth element is at position ns,i,j (k). Nc,i (k) denotes the set containing those
communication neighbors at time k. As all robots are equal, the ad-hoc network is
used for communication between robi and robots in Nc,i (k). These local networks are
temporary and need to be rebuilt when robots arrive at new vertices. In the future
tests on robots, Wi-Fi networks in ad-hoc mode will be used with Transmission
Control Protocol (TCP) socket communication.
33

3.1 Completer Coverage in 2D
At time k, the chosen position of robi is pi (k). A reference position pr is selected
from the initial positions. Some definitions about distances are provided below.
Definition 3.1.2. The distance from pi (k) to pr is denoted as d(pi (k), pr ). Similarly, the distance from an accessible neighbor vertex ns,i,j (k) to pr is d(ns,i,j (k), pr )
and the maximum distance for all ns,i,j (k) is denoted as max(d(Ns,i (k), pr )) with
Nmax sensing neighbors with this value. A random choice from those Nmax values is
represented by c.
Assumption 3.1.3. Wpass ≥ a + 2 ∗ rsaf e .

3.1.2

Algorithm

The algorithm includes two parts. The first part is to allocate robots to a common
T grid with a common coordinate system. In the second part, a decentralized
collision-free algorithm is designed to deploy robots using the grid.
3.1.2.1

Initial Allocation

Before deployment, [128, 168] could only build a common grid with small errors in
certain situations and one vertex can have more than one robot which means collisions are allowed. To compare to that algorithm and design a practical initialization
with a common coordinate system, this chapter manually selects a few vertices of a
grid near the known entrance of the area as initial positions to allocate robots and
uses one point from them as pr . Initial positions and pr are set to the place where
robots could have more choices in the first step based on the limited knowledge of
the area after applying the algorithm so that robots could leave the initial vertices
earlier without blocking each other. To allocate multiple robots at the same point
in different steps, the multi-level rotary parking system as in Figure 3.1 from [141]
could be used. Thus, if a robot moves away from a vertex, the empty parking place
will rotate up, and another robot will be rotated down to the same start position.
Another possible method is to release robots using the rocket launcher such as the
tubes employed in the LOCUST project for the Coyote unmanned aircraft system
[1] in Figure 3.2. As the relative positions of the tubes are fixed, the position of the
robot in one tube can be set as the reference to allow all robots to have the same
coordinate system and the same grid.
3.1.2.2

Distributed Algorithm

The distributed algorithm for deployment is designed based on the search algorithm
in [223, 225, 222, 221]. The flow chart of the algorithm is in Figure 3.3 and the
abbreviation ‘comm’ in that figure is short for communication. Step 6 and Step 7
only happen when the area is static. If the area will be extended, the algorithm only
includes the loop with Step 1 to Step 5. In both situations, robots will sense intruders
continuously and broadcast the positions of intruders when they are found. However,
for the static area, intruder detection may only be required after the deployment
phase is stopped in Step 7 in some applications.
1. Comm1, decide sequence: A robot calculates d(pi (k), pr ) at the beginning
of each loop and exchanges d(pi (k), pr ) and pi (k) with its communication neighbors.
34

3.1 Completer Coverage in 2D

Figure 3.1: The multilevel rotary parking system

Figure 3.2: The launcher for multiple UAVs in the LOCUST project

35

3.1 Completer Coverage in 2D

Figure 3.3: The flow chart for the 2D complete coverage
Then, the one with larger d(pi (k), pr ) has higher priority. If more than one robot
have the same d(pi (k), pr ), another parameter of robots needs to be used to decide
the selection sequence. As only addresses, such as IP addresses, are different between
robots, this chapter allows the robot with a lower IP address to choose with a higher
priority, however, if the one with higher address chooses first, the result should be
the same.
2. Find robot obstacles: The positions of robots are known, so robots within
rso of robi are thought as obstacles, and the occupied vertices are inaccessible for
robi . The Ni vertices to release robots are always considered as obstacles so robots
will not choose them as the next step, and new robots can be added to the area.
3. Wait, sense obstacles: A robot needs to wait for the choices from the
robots with higher priorities because the positions of those choices can be thought
as detected points in the next step and may also be obstacles for robi . If all robots
are connected, the last one in the choosing sequence needs to wait for every other
robot and the processing time for the whole selection process should be set to the
value in this condition because this is the longest time and using this time, all the
robots could be synchronized in each loop.
In the turn for robi , it detects the objects in rso but avoids the section occupied
by existing neighbor robots. The way to judge whether the object p is an obstacle
or not is illustrated in Figure 3.4. The general rule is that if there is any sensed
object on the way to vertex ns,i,j (k) in Ns,i (k), that object is treated as an obstacle.
So that vertex ns,i,j (k) cannot be reached and is removed from Ns,i (k).
q In Figure
3.4, rnew is the distance between pi (k) and the left arc where rnew =

2
(a2 + rsaf
e ).

dpr represents the distance from the sensed object p to the position of robi , pi (k).
dpn denotes the distance between p and ns,i,j (k) and dpe denotes the distance from
p to the nearest edge of the grid. Let the angle between the facing direction of robi
and the segment which connects pi (k) and p be θpr . Due to the safe distance rsaf e ,
when a robot goes straight to ns,i,j (k), it needs a related safe region which is the
light brown part in the figure. When an object is detected, dpr and θpr are known so
coordinates of that object can be calculated. Thus, dpn and dpe can be determined.
36

3.1 Completer Coverage in 2D

Figure 3.4: Judge obstacles
If (dpr < rnew &dpe < rsaf e )|dpn < rsaf e , point p is an obstacle. If no objects are
sensed, this robot will still wait for the same amount of processing time so all robots
are synchronized in this step.
4. Choose comm2: robi calculates max(d(Ns,i (k), pr )) for its sensing neighbors and randomly chooses one vertex from Nmax neighbor vertices which could
result in max(d(Ns,i (k), pr )). If there are no accessible vertices to visit for robi ,
namely Nmax = 0, robi will stay at its current position. Mathematically, it can be
written as:
(
c with prob. 1/Nmax , if Nmax 6= 0,
pi (k + 1) =
(3.1)
pi (k), if Nmax = 0.
Then, the choice will be sent to robots with lower priorities. For the static
area, a robot also records and sends the IP addresses of robots which will move
in the current step. After communication, the robot still waits until the time for
choice past. However, robots have no knowledge about the number of robots used
at time k. Thus, the total time for making a choice is equal to the time for selection
and communication of one robot multiples the total number of robots prepared for
deployment. In this way, robots can be synchronized.
5. Move: All robots move together and those who do not move need to wait
for the time for the movement to get synchronized. The movement includes rotating
the head of the robot to aim at the target vertex and translating to the vertex. All
robots should move in the same pattern at the same time, and the way to move
should match the realistic constraints.
Each movement step consists of two phases: phase I is the pure rotation, phase
II is the pure translation. The rotation will align the robot with the target vertex.
Specially, if robi was facing to its next vertex before phase I, it will not move but
wait for the rotation time. Then robi can go straight along the selected edge. Many
robots use the nonholonomic model with standard hard constraints on velocity and
acceleration. This report also considers the constraints of real robots so that both
phases use trapezoidal velocity profiles based on parameters of the area and the test
robots. In this section for 2D areas, Pioneer 3-DX robots are used, and parameters
are shown in simulations (Section 3.1.3).
6. Do all Stay? : Based on the sequence of choice, the robot at pr will be
the last to choose the next vertex. If no IP addresses from robots which go to new
vertices are received, and the choice of the robot at pr is also staying at the current
37

3.1 Completer Coverage in 2D
position, namely pi (k + 1) = pi (k) for all robots, then the self-deployment should be
stopped. Otherwise, all robots execute Step 5.
7. Stop: The stop procedure depends on the applications. In this chapter,
robots are designed to detect intruders into the area so the robot at pr could broadcast the stop signal, and all robots stop moving and obstacles sensing but only keep
the sensors for target intruders on. If an intruder is found, robots broadcast the position of the intruder, and other corresponding actions could be taken. Specially, under
the strict requirement, if the sensing range for the target is changeable, the sensors
which cannot sense the boundaries could decrease their sensing range
√ to the minimum value which can meet the loose requirement, namely, rst = aT / 3+rsaf e −rrob .
Thus, the energy of those sensors will be saved, and they can monitor the area for
a longer time.
Remark 3.1.1. The broadcast is only used for a few vital information including the
stop signal and positions of intruders, so it will not consume too much energy. If
only local communication could be used, the stop signal can still be transmitted to
all robots at the time slot for comm1 and receivers will do all the actions in Step 7
directly except broadcasting the stop signal.
By applying the above algorithm, robots which are further away from pr have higher
priorities to choose to go to the furthest accessible vertices, which leaves spaces for
the newly added robots near pr to go to. If there are enough available choices for
robots, Ni robots could be added in each loop and an optimal deployment with No
steps can be reached. Thus, the equation for No can be written as:
No = ceil(|Va |/Ni ).

(3.2)

In the above formula, the ceil() is the ceiling function because the result of the
division may be a decimal figure. However, less than one step means not all the
robots need to move in that step, but that should still be finished in one step.
Theorem 3.1.1. For a static area, suppose all assumptions in Section 2.1.1 and
3.1.1 hold for the loose requirement or the strict requirement, and algorithm 3.1 with
the judgment step is used. Then there exists such a time k0 > 0 with probability 1
that for any vertex vj ∈ Va where j = 1, 2, . . . , |Va |, the relationship vj = pi (k) holds
for some i = 1, 2, . . . , m and all k ≥ k0 .
Proof. The proposed Algorithm 3.1 and the judgment method in Step 6 form an
absorbing Markov chain with many transient states and absorbing states. The transient states are the states that robots have accessible sensing neighbors to choose.
The absorbing states are the states that all robots have no sensing neighbors to go
and stop at their current vertices forever, namely the states that they cannot leave.
The proposed algorithm continuously adds robots to the area to occupy every vertex,
which enables robots to reach the absorbing states from any initial states with any Ni .
This implies the absorbing state will be achieved with probability 1. This completes
the proof of Theorem 3.1.1.

38

3.1 Completer Coverage in 2D

P

rrob

rsaf e

rso

rst

a

R

0.26m

0.35m

5m

32m

4.65m

S

0.26

0.35

1.35

1.35

1

P

rc

vmax

ωmax

tmove

Wpass

R

91.4m

1.5m/s

300◦ /s

5.75s

5.35m

S

2.09

0.3/s

300

5.75s

1.7

Table 3.1: Parameters of robots and simulation

3.1.3

Simulation Results

The proposed algorithm for the complete coverage is simulated in MATLAB2016a
in an area with 20*20 vertices and |Va | = 256 as seen in Figure 3.5. Ni = 3, 5, 7 are
chosen to verify the results and those known initial vertices are at the bottom right
corner to release robots. The numbers in the graph are the order to add vertices,
and vertex 1 is the reference vertex at pr . In this arrangement, each robot will have
vacant vertices to go without blocking each other in the first loop.
The parameters in the simulation are designed based on parameters of Pioneer
3-DX robots in Figure 2.7 and the assumptions satisfying the strict requirement.
Table 3.1 shows the parameters in the simulation which are designed based on the
datasheet of the pioneer 3-DX robot. Row P, R, and S are the names of the parameters, parameters for robots and parameters in simulations respectively. The
underlined column names refer to the known values for robots. rsaf e and tmove need
to be estimated from the experiment. Then a and Wpass can be calculated in turn
based on assumptions in Section 2.1.1 and rsaf e . In calculations, equality conditions
of the inequalities are used. In the experiment, robots will have at most a 0.08m
shift to the left or right after moving 8 meters forward or backward, so e is set to
0.09m and rsaf e = 0.35m. In an experiment with a = 1m and vmax = 0.3m/s, moving time is roughly estimated as 5.75 seconds which is 4.5s for the translation and
1.25s for the rotation using trapezoidal velocity profile and the maximum rotation
speed ωmax = 300◦ /s of the robot. In simulations, rrob and ωmax from the robot
are used. a, vmax and tmove from the experiment are used. Although different areas
with different sizes will be simulated, for simplicity, the error in the simulation is
always set as e = 0.09 so rsaf e = 0.35. Then other values are calculated based on
assumptions in Section 2.1.1.
An example progress for Ni = 3 is shown in Figure 3.6, 3.7 and 3.8 for k = 30,
k = 60 and k = 86 respectively and the self-deployment finished in 86 loops. The
graph shows that robots tended to go to vertices which were far from pr and left
space for newly added robots, which made the deployment fast. In Figure 3.8, the
circles represent the rst of each robot and every point of the task area Ac was covered
at the end.
The proposed algorithm is compared to the modified version of the DR algorithm

39

3.1 Completer Coverage in 2D

Figure 3.5: The task area and the initial setting
in [170, 131]. To modify it, firstly, the IP addresses of the robots are used as the order
numbers to set the sequence of choice. Therefore, for robi and its communication
neighbors, the robot with the lowest address will choose first. Then the robot needs
to inform its communication neighbors with lower priorities about its choice in this
loop.
Table 3.2 illustrates the No calculated using formula 3.2, average results of 100
simulations for the proposed algorithm and average results of 100 simulations for the
DR algorithm. It also shows the ratio of the steps in the proposed algorithm to that
in the DR algorithm. It can be seen that the proposed algorithm is always better
than the DR algorithm, and the advantage is clearer when Ni is larger. Compared
to No , the simulation result of the proposed algorithm is equal to it when Ni = 3.
However, for Ni = 5 or 7, the simulation results are a little bit larger but no greater
than 1 step. This result means some loops had less than Ni robots added because
less than Ni robots found vacant vertices to go to. This can be caused by some
narrow vacant areas which can be seen in the example in Figure 3.9 where Ni = 3
and |Va | = 6. From formula 3.2, No = 2, however, the narrow path only allows one
robot to be added in each loop. So, robots need four loops to finish the complete
coverage. Another reason is that robi can choose a ns,i,j (k) whose d(ns,i,j (k), pr ) is
smaller than d(pi (k), pr ) but other robots within rso of robi have higher priorities so
they have finished choosing the next step. Thus, pi (k) would be vacant in step k + 1
and the movement of robi is towards the reference point. So it does not result in a
vacant vertex near initial vertices for adding a new robot.
To test the scalability of the algorithm, areas with the same shape but different
sizes are used with Ni = 3. So areas with 10*10 vertices and 30*30 vertices are
used with |Va | = 57 and |Va | = 598 respectively. The average results of the two
40

3.1 Completer Coverage in 2D

Figure 3.6: Positions of robots when k = 30, |Va | = 256, Ni = 3

Figure 3.7: Positions of robots when k = 60, |Va | = 256, Ni = 3

41

3.1 Completer Coverage in 2D

Figure 3.8: Positions of robots when k = 86, |Va | = 256, Ni = 3

Figure 3.9: An example of the narrow path with k = 3, |Va | = 6, Ni = 3

42

3.1 Completer Coverage in 2D

Ni

Type of Results
3

5

7

No

86

52

37

Proposed algorithm

86

52.06

37.96

DR algorithm

310.39

273.74

254.92

Proposed/DR

27.7%

19.0%

14.9%

Table 3.2: Steps from calculations and simulations with |Va | = 256
Size of the Area
Type of Results
10*10

20*20

30*30

No

19

86

200

Proposed algorithm

23.96

86

200

DR algorithm

70.62

310.39

766.71

Proposed/DR

36.0%

27.7%

26.1%

Table 3.3: Steps from calculations and simulations for different areas with Ni = 3
algorithms, the ratio between them, and No are shown in Table 3.3. The results
demonstrate that the proposed algorithm is scalable and effective. Its advantage
is clearer when the area is larger. The steps for the areas with 20*20 and 30*30
vertices is optimal, but the steps for the area with 10*10 vertices is larger than No
because the shrunk area has more narrow paths as discussed in Figure 3.9.

3.1.4

Section Summary

This section provided a decentralized algorithm for multiple robots to build a robotic
sensor network to completely cover an unknown task area without collisions using
an equilateral triangular grid pattern. The convergence of the proposed algorithm
was mathamatically proved with probability 1. Results of this algorithm were very
close to the least number of steps and were equal to that in some situations. So the
algorithm is optimal under the limitation of the area. Simulation results demonstrated that the proposed algorithm is effective comparing to another decentralized
algorithm and it is scalable for different sizes of areas.

43

3.2 Completer Coverage in 3D

3.2

Completer Coverage in 3D

This section solves the complete coverage problem in a 3D area by using a decentralized collision-free algorithm for robots to form a coverage network. Based on
Chapter 2, the C grid is used in this section for the Bluefin-21 robot. The assumptions and definition for the area and ranges from Section 2.2.1 are used directly.
Others are similar as Section 3.1.1 except the ranges are spherical, and the shape of
objects are three-dimensional which are based on [224]. However, these assumptions
and definitions are still claimed here to make the explanation and the proof clear
and will be used in later Chapters.

3.2.1

Problem Statement

Assumption 3.2.1. Area A has a finite number of three-dimensional obstacles O1 ,
O2 ,. . ., Ol and all these obstacles Oi are non-overlapping, closed, bounded and linearly connected for any i > 0. The obstacles are unknown to the robots.
S
Definition 3.2.1. Let O := Oi for all i > 0. Then the 3D area that needs to be
covered can be written as Ac := A \ O. Area Ac can be either static or be expanding.
In each step, robots move a from one vertex vi to an accessible nearest neighbor
vertex vj through the edge of the grid. The number of steps needed in the optimal
situation for the complete coverage is denoted as No . The set of accessible vertices
in Ac is denoted by Va and the number of members in Va is |Va |.
Assumption 3.2.2. To occupy every vertex in Ac , m ≥ |Va |. Robots are fed into
the area from Ni initial vertices near the boundary.
The set of sensing neighbors of robi at discrete time k (step k) is denoted as
Ns,i (k) in which the position of the jth member is ns,i,j (k). The set of communication
neighbors of robi in time k is denoted as Nc,i (k). The communication in 3D is also
employing ad-hoc network which is rebuilt after each robot reached its next vertex.
The position of robi at time k is pi (k). A reference position pr which belongs to
the Ni initial positions is set. Then some definitions about distances are given.
Definition 3.2.2. The distance from pi (k) to pr is represented by d(pi (k), pr ) and
the distance from ns,i,j (k) to pr is d(ns,i,j (k), pr ). The maximum d(ns,i,j (k), pr ) is
denoted by max(d(Ns,i (k), pr )) with Nmax neighbor vertices resulting to this value.
The position of the choice from those Nmax values is represented by c.
To allow robots to go through each passage to reach each vertex, the assumption
for passage width Wpass is needed.
√
Assumption 3.2.3. Wpass ≥ a 3 + 2rsaf e .

3.2.2

Algorithm

The algorithm starts with the method to set the initial locations of robots followed
by the decentralized self-deployment algorithm with collision avoidance to form the
complete coverage network to detect intruders.

44

3.2 Completer Coverage in 3D
3.2.2.1

Initial Allocation

The initialization in a 3D area is similar to that in a 2D area. Ni nearby vertices
of a grid near the known entrance of the area are selected as the initial positions to
allocate robots, and one of them is set as pr . The chosen points should allow robots
to leave the initial positions without blocking each other and it is better to give a
robot more choices. In practice, method in Figure 3.2 and 3.1 can be used. For the
marine applications, Ni ships or submarines could be used to carry robots and stop
at the selected places to launch UUVs.
3.2.2.2

Distributed Algorithm

The 3D algorithm is the same as that in a 2D area, so the flowchart in Figure 3.3 is
still available. So Algorithm 3.1 and Equation 3.2 are still used here.
(
c with prob. 1/Nmax , if Nmax 6= 0,
pi (k + 1) =
(3.3)
pi (k), if Nmax = 0.
No = ceil(|Va |/Ni ).

(3.4)

To apply them to the 3D area, the user needs to think all parameter in the 3D
situation such as the distance in obstacle detection and setting the priority. Then
the algorithm in 2D will handle the task in 3D successfully.

3.2.3

Simulation Results

The proposed algorithm is initially simulated in MATLAB2016a for a static area
with 7*7*7 vertices and |Va | = 129 in Figure 3.10. In the simulation, Ni = 3, 5, 7,
9, 11 and 13 are used with initial vertices at the bottom layer of the task area. In
the figure, numbers indicate the order to added vertices and the position of vertex
1 is selected as pr . In this setting, all robots have accessible sensing neighbors to go
in loop one.
The parameters in the simulation are based on the Bluefin-21 underwater vehicle
which was used in searching MH370 and details can be found in [21]. The data for
Bluefin-21 and simulation is shown in Table 3.4 where P, R, and S stands for parameter names, parameters for robots and parameters for simulations. The underlined
parameter names mean those parameters for robots are from the datasheet. As ωmax
is unknown in the datasheet, the tmove cannot be estimated. The length of the robot
is 4.93m, and the diameter is 0.53m, so rrob = 4.93m is set. rsaf e is calculated based
on the e. In the datasheet, real-time accuracy ≤ 0.1% of the distance traveled. So
rsaf e can be set using the distance traveled in simulations. Then a and Wpass are
calculated based on rsaf e and assumptions in Section 2.2.1. In simulations, rrob use
the data from robot directly. Then a = 15 is set to avoid collisions while robots are
moving. To find rsaf e of the robot, the maximum travel distance in simulations in
this section is used which is 155.885 as the body diagonal of the area with 8*8*8
vertices in comparison. So the corresponding e = 0.156 and rsaf e = 5.086. Then
other parameters in simulations can be calculated. Then rsaf e = 5.086m is set in the
parameters for the robot. The rotation speed of this UUV is unknown, and there
are no Bluefin-21 robots to test in the author’s lab. Thus, the simulation results
will not be compared to the experiment result so guess an angular speed and a total
45

3.2 Completer Coverage in 3D

Figure 3.10: The task area and the initial setting
move time is meaningless. So in simulations, tmove is still set as 5.75s with 4.5s for
translation and 1.25s for rotation to show the effect of the algorithm, although it
will be smaller than the actual value.
An example of the procedure with Ni = 3 is shown in Figure 3.11, 3.12 and 3.13
for k = 15, k = 30 and k = 44 separately and the deployment finished in 44 steps.
The graphs show that robots will occupy the sections which are far from pr first,
thus, vertices near initial positions are vacant for adding new robots. Therefore,
the self-deployment result could be close to the optimal result. In Figure 3.13, the
light grey spheres demonstrate the rst for each vertex. The result shows that only
the corners near the boundaries of the area are not covered. Based on Assumption
2.2.5, those corners are ignored, and the complete coverage of the area is achieved.
The modified DR algorithm in [128] is compared to the proposed algorithm. To
make that algorithm work in the practical situation, the IP address of the robot
which is unique for each robot is used as the order of choice. For robi and its neighbors in Nc,i (k), it is set that the one with lower IP address will choose earlier. robi
also informs its choice robots in Nc,i (k) with lower priorities. Thus, communication
neighbors will not choose the same vertex as robi in the same step.
The calculated No and the average simulation results of 300 tests for both the
proposed algorithm and the DR algorithm are shown in Table 3.5. It also shows

46

3.2 Completer Coverage in 3D

P

rrob

rsaf e

rso

rst

a

R

4.93m

5.086m

75m

1km

69.9140m

S

4.93

5.086

20.086

20.086

15

P

rc

vmax

ωmax

tmove

Wpass

R

91.4m

2.315m/s

N/A

N/A

131.2666m

S

30.156

N/A

N/A

5.75s

36.1528

Table 3.4: Parameters of robots and simulation

Figure 3.11: Positions of robots when k = 15, |Va | = 129, Ni = 3

47

3.2 Completer Coverage in 3D

Figure 3.12: Positions of robots when k = 30, |Va | = 129, Ni = 3
the ratios of steps in the proposed algorithm to the steps in the DR algorithm.
The numbers of steps of the proposed algorithm are less than 1/3 of that in the
DR algorithm, and the advantage is clearer when Ni is larger. The results of the
proposed algorithm are only less than two steps more than No , so they are very
close to the optimal numbers of steps. However, this also means, in some steps,
there were less than Ni robots added because less than Ni robots could find vacant
vertices to move to. One possible reason is that there were some narrow sections in
the task area. An example of narrow section is shown in Figure 3.14 where Ni = 3,
|Va | = 6 and vertex 1 is at pr . The area to be covered is made up of two cylinders,
and the balls show the rsaf e around each vertex so that it is clear that vertex 2 and
3 are blocked by boundaries and only vertex 1 can add new robots to the section
of the thin cylinder. So, based on rule 3.1, robots need four loops to finish the
complete coverage. However, according to formula 3.2, No =2. Another reason for
the nonoptimal result is that robi chose a ns,i,j (k) with the d(ns,i,j (k), pr ) which was
smaller than d(pi (k), pr ), which means robi moved toward pr . If other robots at
sensing neighbors of robi had higher priorities than robi , they should have finished
their choices so pi (k) could not be chosen in this step and would be left vacant in
step k + 1. Thus, the choice of robi did not result in an accessible vertex near initial
vertices to feed in a new robot.
To test the scalability of the proposed algorithm, areas with the same shape but
different sizes with Ni = 3 are used. The test areas have 6*6*6 vertices and 8*8*8
vertices with |Va | = 62 and |Va | = 210 respectively. The average results of 300
simulations of both algorithms, the ratios of the two algorithms and No are in Table
3.6. It shows that the proposed algorithm is always better than the DR algorithm.

48

3.2 Completer Coverage in 3D

Figure 3.13: Positions of robots when k = 44, |Va | = 129, Ni = 3

Ni

Type of Results
3

5

7

9

11

13

No

43

26

19

15

12

10

Proposed algorithm

44.27

27.84

20.29

16.57

13.53

11.66

DR algorithm

139.65

93.04

68.36

62.65

53.91

46.26

Proposed/DR

31.7%

29.9%

29.7%

26.5%

25.1%

25.2%

Table 3.5: Steps from calculations and simulations with |Va | = 129
49

3.2 Completer Coverage in 3D

Figure 3.14: An example of the narrow path with k = 3, |Va | = 6, Ni = 3

50

3.3 Summary

Size of the Area
Type of Results
6*6*6

7*7*7

8*8*8

No

21

43

70

Proposed algorithm

23.70

44.27

70.98

DR algorithm

66.03

139.65

248.24

Proposed/DR

35.9%

31.7%

28.6%

Table 3.6: Steps from calculations and simulations for different areas with Ni = 3
As the area expands, the ratio decreases which means the advantage is clearer than
that in a small area. The difference between the proposed algorithm and No also
decreases because there are less narrow areas. The above simulations demonstrate
that the algorithm is scalable and effective.

3.2.4

Section Summary

This section provided a decentralized self-deployment algorithm for multiple mobile
robotic sensors to cover a 3D area completely. The area is arbitrary unknown with
obstacles, and the coverage algorithm used a grid pattern to have the least number
of robots and avoid collisions. This section proved that the algorithm could converge
with probability 1 and the results of this complete coverage algorithm are very close
to the fewest number of steps. Comparing to another decentralized algorithm with
the same initial condition, the proposed algorithm is effective and scalable.

3.3

Summary

A decentralized complete coverage algorithm for the mobile robotic sensor network
was proposed for both 2D and 3D area. The task area is arbitrary unknown with
obstacles and robots deploy themselves using the grid without any collisions. In 2D
areas, the 100% coverage was reached under the strict requirement, and in 3D areas,
each grid point in the task area was occupied by a mobile sensor. Comprehensive
simulation of the algorithm for areas with different sizes and different initial points
were run based on the parameters of real robots. The simulation results illustrate
that the step in the algorithm is very close to the ideal value and this algorithm is
much better than the DR algorithm. This chapter also proved the convergence of
the algorithm with probability 1. The algorithm is applicable in both 2D and 3D
areas, and only slight changes in the dimension of some values are needed.

51

Chapter 4
A Collision-Free Random Search
Algorithm
Chapter 4, 5 and 6 provide three decentralized collision-free algorithms for search
tasks in an unknown area by multiple robots. They all use grid patterns as discussed
in Chapter 2 and all the targets are static. So the problem statement and the
algorithm in this chapter will be explained and discussed in detail. Although some
of them will be the same as those in the complete coverage, including them here will
make this chapter self-contained and make readers understand the discussion easier.
Chapter 5 and 6 will refer to this chapter and only describe the problem statement
and algorithm briefly and focus on the different parts.
According to Chapter 3, in a large task area, monitoring the whole area requires
a significant number of robots which will be costly. Therefore, with a limited number, robots need to move around to detect the entire area gradually or find some
targets which will be the search task. There are two types of search tasks in an
unknown environment. If the number of targets is known to the robot a priori,
robots only need to find all the targets to finish the work. This situation is called
situation I which can be seen in the search for a certain number of people lost in a
forest. Otherwise, the number of targets is unknown, it is called situation II, and
robots need to detect every corner of the area to achieve the goal such as the mine
countermeasures in the battlefield.
This chapter proposes a grid-based decentralized random algorithm for search
tasks in an unknown area. The performance of the algorithm will be analyzed using
simulations. The proposed algorithm is suitable for both 2D and 3D areas. The main
differences are the grid pattern and the dimension of some parameters as discussed
in Chapter 2. The problem in a 2D area will be discussed in Section 4.1, and the
task in a 3D space will be in Section 4.2.

4.1

2D Tasks

This section aims to design a collision-free decentralized algorithm for a group of
robots to search targets in an unknown area with static obstacles by visiting vertices
of a grid pattern.

52

4.1 2D Tasks

Figure 4.1: Initial settings of the map

4.1.1

Problem Statement

The searched area in this section is a two-dimensional area A ⊂ R2 with limited
number of obstacles O1 , O2 ,. . ., Ol . There are m robots labeled as rob1 to robn in
this area as shown in Figure 4.1. An arbitrary known T grid pattern with a side
length of a is used, and robots can only move along the edge connection neighbor
vertices in each step.
Assumption 4.1.1. The area A is a bounded, connected and Lebesgue measurable
set. The obstacles Oi are non-overlapping, closed, bounded and linearly connected
sets for any i ≥ 0. They are both unknown to the robots.
S
Definition 4.1.1. Let O := Oi for all i > 0. Then Ad := A \ O represents the
area that needs to be detected.
There are n static targets t1 to tn which are labeled as red stars in Figure 4.1.
Let T be the set of target coordinates and Tki represents the targets set known by
robi . The symbol |•| in this report represents the number of elements in set •. Then
|T | denotes the number of targets in the search area and |Tki | denotes the number
of targets known by robot robi . There are two kinds of targets searching problems.
In situation I, |T | is known and in situation II, no information about |T | is given.
Assumption 4.1.2. The initial condition is that all robots use the same T grid
pattern and the same coordinate system. They start from different vertices near the
boundary which can be seen as the only known entrance of the area.
Although [131, 132, 129, 130, 11, 12, 10, 14] provided a consensus algorithm to
achieve this assumption, it needs infinite time and has collisions between robots, so
53

4.1 2D Tasks
the algorithm is impractical. If it is only approximately reached in a short period,
the sensing range and the communication range should be designed large enough
to ignore small errors between coordinate systems, but this was not mentioned. In
MATLAB simulations, robots are manually set to start from vertices. In robot
tests, all robots could be released from the same vertex but configured to move
to different nearby vertices at the beginning. Another possible solution could be
using one robot and its coordinate system as a standard, and each other robot is
put close to a distinct vertex near the standard. After sensing and communication
with the standard robot directly or indirectly, other robots will know the positions
of themselves and the corresponding closest vertices. Thus, they can go to those
vertices without any collision.
Assumption 4.1.3. All the ranges and radius in 2D search problems are circular.
The swing radius of robots is rrob . To avoid collision with other objects such as
boundary and other robots, errors need to be considered. Let the maximum possible
error containing odometry errors and measurement errors be e. Then a safety radius
rsaf e which is larger than rrob for collision avoidance can be defined as follows.
Definition 4.1.2. To avoid collisions with other things before move, a safe radius
rsaf e should include both rrob and e (see Figure 2.2). So rsaf e ≥ rrob + e.
Assumption 4.1.4. As the T grid is used, all passages Wpass between obstacles or
between an obstacle and a boundary are wider than a + 2 ∗ rsaf e based on Table 2.1.
This guarantees that there is always an approachable vertex in the path and
robots can go through the passage with no collision. Obviously, decreasing a will
expand the scope of applicability. However, the number of vertices increases so
the search time will also increase. To search with collision avoidance, robots carry
sensors to detect the environment including both targets and obstacles.
Assumption 4.1.5. The sensing radius for obstacles is rso where rso ≥ a + rsaf e .
Therefore, if the neighbor vertices of a robot are less than rsaf e away from the
boundary or obstacle, rso is large enough to detect that so the robot will not visit
those vertices to avoid collision. rso can be seen in Figure 2.2 and 2.3. The vertices
which are within rso of robi are called sensing neighbors of robi . Let Va represents the
set which includes all the accessible vertices. Then let Ns,i (k) represents the sensing
neighbors set that contains the closest vertices ns,i,j (k) around robi at discrete time
k where j ∈ Z+ is the index of the neighbor vertices. In Ns,i (k), let the set of visited
vertices of robi be Vv,i (k) and the corresponding set for unvisited vertieces be Vu,i (k).
So 0 ≤ |Vv,i (k)| ≤ 6 and also 0 ≤ |Vu,i (k)| ≤ 6. Then let the choice from Vv,i (k) be
cv and the choice from Vu,i (k) be cu .
Apart from obstacle sensing, robots also need to have a sensor to detect targets
which has a range of rst . Under the strict requirement, it is similar to rso . An
assumption for rst is needed to guarantees that areas around inaccessible vertices
can still be detected.
Assumption 4.1.6. rst ≥ a + rsaf e .
In the strict requirement, each point should be detected, and a T grid is needed,
the curvature assumption will guarantee this.
54

4.1 2D Tasks
Assumption 4.1.7. The curvature of the concave part of the boundary should be
smaller than or equal to 1/rst .
For the loose requirement, the above two assumptions are not needed as rst
should be chosen based on Table 2.1 other than Assumption 4.1.6 and assumption
for boundary effect will replace 4.1.7 to ensure a complete search which is stated
below.
Assumption 4.1.8. The search task for a team of robots usually has a vast area.
So, a is much smaller than the length, the width and the height of area A. Therefore,
the boundary effect is negligible [3, 4].
The communication range of robots is represented as rc . Robots within rc of
robi are named as the communication neighbors of robi . As the range is limited, the
communication between robots is temporary as in an ad-hoc network, so each robot
is considered equal with local communication ability. To avoid choosing the same
vertex with other robots in the same step, robots could choose in sequence use the
proposed random algorithm and tell the choice to communication neighbors who
may select it. Thus, others will think that vertex as an obstacle. The way to set the
sequence of choice is described in Section 4.1.2. Based on the T grid, those robots
are one or two vertices away from it. Therefore, rc should satisfy Assumption 4.1.9
with error e considered.
Assumption 4.1.9. rc ≥ 2 ∗ a + e (see Figure 2.3).
Let Nc,i (k) denotes a set of communication neighbors around robi that it must
communicate with. According to Figure 2.3, max(|Nc,i (k)|) = 18.

4.1.2

Procedure and Algorithm

The algorithm directs the robots to explore the area gradually vertex by vertex. The
whole progress can be seen in Figure 4.2 for situation I and in Figure 4.3 for situation
II. The stop strategy and the time to do it in the two situations are different. The
description of the algorithm is based on situation I. Extra steps for situation II are
mainly about detection states of the vertices. From the previous section, a vertex
is said to be detected in two conditions. If a vertex has obstacles within rsaf e , the
detection state for this vertex and surrounding area is judged from robots at its
sensing neighbors. If the vertex is accessible, this vertex and surrounding area are
said to be detected after it is visited. They are underlined in Figure 4.3 and will be
specially noted if necessary.
4.1.2.1

Preparation for the Choice

Initially, robots exchange their positions with robots within rc . Based on the relative
positions, the recognized communication neighbors of robi will form the set Nc,i (k).
The recognized robots staying at sensing neighbors will be thought as obstacles by
robi and their occupied vertices will be removed from Ns,i (k). Then the sequence of
choice can be decided to avoid choosing the same next vertex by different robots.
For robi at pi (k) and its communication neighbor robj at pj (k), if pjx > pix | (pjy >
piy &pjx = pix ), robj will have higher priority to make choice. Figure 2.3 visualizes
the above relation. In that figure, robots with higher priorities should be on the
55

4.1 2D Tasks

Figure 4.2: The flow chart for situation I

56

4.1 2D Tasks

Figure 4.3: The flow chart for situation II
57

4.1 2D Tasks
vertices at the right side of the green curve. So, robots at vertices on the left will
choose later than robi . In this way, robots at half of the neighbor vertices will choose
earlier than robi and there will be no contradiction when judging relative orders from
the views of different robots.
Subsequently, robots sense the local area within rst to detect targets. As positions
of other robots are known, their occupied zone will not be detected. In situation
I, when a target is detected, the information will be broadcast to all robots. The
broadcast is used as the positions of targets are the key results to find for all robots,
and it only happens |T | times, so this will not consume too much energy. After
this, all robots will go to stop strategy. If robots are not ready to stop or no targets
are sensed, robots will go back to the regular loop on the left side of the figure.
In situation II, the information of targets will only be broadcast after the stop is
confirmed. Robots only need to move to the next step of the flowchart regardless of
the sensing results.
Next, the robot shares its explored map which is updated based on the position
received in the first step. Then robots can update their maps again. In situation II,
whether the sensing neighbors of the vertices are detected or not will also be sent
and received to update the detection states of all vertices.
4.1.2.2

Wait, Choose, and Communicate

robi needs to wait for the choices from the robots with higher priorities because the
positions of those choices can be thought as detected points in the next step and
may also be obstacle areas for robi . If all robots are connected, the last one in the
choosing sequence needs to wait for every other robot and the processing time for
the whole selection process should be set to the value in this condition because all
the robots should be synchronized in each loop. When it is the turn of robi , it will
detect the local area but avoid the section of existing neighbor robots. The way to
judge whether the object p is an obstacle or not is illustrated in Figure 3.4 in Section
3.1.2. If there is any sensed object on the way to the vertex ns,i,j (k) in Ns,i (k), that
object is treated as an obstacle. So that the vertex ns,i,j (k) cannot be reached and
is removed from Ns,i (k). For situation II, that vertex is also recorded as detected. If
no objects are sensed in these two situations, this robot will still wait for the same
amount of processing time, so all robots are synchronized in this step.
Choices are made using the following random decentralized algorithm.


6 0,
cu with prob. 1/|Vu,i (k)|, if |Vu,i (k)| =
pi (k + 1) = cv with prob. 1/|Vv,i (k)|, if (|Vu,i (k)| = 0)&(|Vv,i (k)| =
(4.1)
6 0),


pi (k), if |Ns,i (k)| = 0
This algorithm means when there are unvisited sensing neighbors, robi will choose
one from them randomly. If there are only visited sensing neighbors around, robi
will randomly choose one from them. If there are no vacant sensing neighbors to go,
robi will stay at the current position pi (k).
The choice of robi is also added to its map and sent to robots in Nc,i (k). The
receiver robj with lower priority needs to remove pi (k + 1) from Ns,j (k) if it was in
that set. In situation II, the detection state of vertices should also be updated after
making a choice and receiving the choice.

58

4.1 2D Tasks
In contrast to the random choice, there is also an algorithm with deterministic
choice, namely using the first available choice. The first choice is used as there may
not be another option. However, if the first choice is defined based on heading angle
of the potential movement, robots tend to move in the same direction instead of
searching all directions evenly which may lead to more repeated visitation. Thus, it
will have a longer search time.
4.1.2.3

Move

All robots should move in the same pattern at the same time, and the way to move
should match the realistic constraints.
Each movement step consists of two phases: phase I is the pure rotation, and
phase II is the pure translation. The rotation will aim the heading of the robot at
the target vertex. Specially, if robi has been facing to its selected vertex before phase
I, it will not turn but wait for the rotation time. Then robi can go straight along
the chosen edge. Robots have standard hard constraints on the velocity and the
acceleration so that both phases use trapezoidal velocity profiles based on parameters
of the area and the test robots. In this section, parameters from Pioneer 3-DX are
used in simulation as in Table 3.1.

4.1.3

Stop Strategies

For situation I, a robot judges the stop condition after exchanging target information. robi should stop at time k when the number of targets that it finds equals to
the number of targets in the area. The knowledge of |Tki | comes from its detection
and the information received from other robots. Namely, for any robot,
pi (k + 1) = pi (k), if |Tki | = |T |

(4.2)

In situation II, the judgment for stop condition happens in step 6 in the flowchart.
For each visited vertex, the detection states of its sensing neighbors need to be
checked. If all visited vertices have no undetected sensing neighbors, the robot
should stop. Namely,
pi (k + 1) = pi (k), if ∀vi ∈ Va , |Vu,i (k)| = 0

(4.3)

The aims of the tasks can be various. So robots may have different missions after
stop moving. However, this paper focuses on search tasks only so looking for the
coordinates of the targets is the only requirement. In situation I, when the judgment
condition of robi is satisfied, all robots stop the whole procedure as they have the
same information of targets which is broadcast every time. However, in situation II,
if robi satisfies the stop condition, it needs to broadcast its knowledge of targets and
a stop signal to inform all other robots. Then all robots will broadcast the positions
of targets that they know and terminate the search.

4.1.4

Broken Robots and Reliability

Waiting for information to choose means the failure of robots with higher priorities
will affect those with lower priorities and thus break the loop of the flowchart. To
improve the reliability of the algorithm, the failure of robots need to be found and a
59

4.1 2D Tasks
solution to tackle it is provided as follows. If robi has not received any information
from robots with higher priorities until the (n − 1) waiting loop, it means that at
least one robot is not working. Therefore, robi will broadcast that the robots which
should send their choices but did not do failed and claim that robi itself is still
working. If both failure and working states of one robot are received in this loop,
that robot will be judged as working. Then, those robots which send information will
stay at current positions and wait until the time slot for move passed. In the next
loop, robots will not wait for the failed robots but just consider it as an obstacle.
This scheme detects the failure after the first step in the flowchart and before the
movement. However, the detection does not include the fault in communication.
By having this broken robots detection scheme, this decentralized algorithm is more
robust than centralized algorithms and robots will still work even when there is only
one working robot left. Under this circumstance, the system could only fail in the
extreme condition where broken robots blocked all the paths to a target so that the
target cannot be detected.
Theorem 4.1.1. Suppose that all assumptions hold and the random decentralized
algorithms 4.1 with a related judgment strategy 4.2 or 4.3 are used. Then for any
number of robots, there is a time k0 > 0 such that all targets are detected with
probability 1.
Proof. The algorithms 4.1 & 4.2 or 4.1 & 4.3 forms an absorbing Markov chain
which includes both transient states and absorbing states. The transient states are the
steps that robots visit the approachable vertices of the grid but do not stop. Absorbing
states are the steps that all robots stop at the vertices. Applying this algorithm, robots
tend to go to the unvisited neighbor vertices. If all sensing neighbors of a robot
are visited before finding the targets, robots will choose a random sensing neighbor,
continue the regular loop and only stop when all targets are found in Situation I or all
approachable vertices are visited, and all inapproachable vertices are detected from
their sensing neighbors in situation II. For 4.1 & 4.2, the number of transient states
will decrease until all robots know |Tki | = |T |. For 4.1 & 4.3, absorbing states are
reached until |Vu,i (k)| = 0 for any accessible vertices. Based on Assumption 4.1.4,
absorbing states can be achieved from any initial state, namely with probability 1.
This completes the proof of Theorem 4.1.1.

4.1.5

Simulation Results

Simulations of the situation where the number of robots is known, namely situation
I, is used to verify the algorithm. The loose requirement is applied for the area,
and the T grid is used for the robot to move through. In simulations, there is one
target randomly put in the area A, and there are several robots to search it (see
Figure 4.1). The aim is to find the target position in A by robots via the T grid
pattern using the proposed algorithm. Based on this aim, when the target is found,
the corresponding robot stops and shares this as global information. The search
procedure should always have no collision. The bold black line made up by points
in the map displays the boundary of area A and obstacles. The distances between
neighbor points are small enough which is set according to Assumption 4.1.4 so that
no robots can pass the boundary. Parameters in the simulation are designed based
on the pioneer 3-DX robot. Notice that move time is roughly estimated as 5.75s
60

4.1 2D Tasks

Figure 4.4: The route of robot 1 in a simulation of 3 robots
based on Table 3.1. To test all the situations in algorithm 4.1, at least seven robots
are needed. So the simulations with one to seven robots for the same target starting
from similar places are run to check the relation between the number of steps of
choice, search time and the number of robots. To see the route clear and show the
collision avoidance. The target is put far from the starting points with obstacles in
between. For the test with seven robots, one robot will be enclosed by other robots
as shown in Figure 4.1. Then all six sensing neighbors will be seen as obstacles by
the middle one which is the third situation of algorithm 4.1. In later loops, the first
and second situations could happen.
Figure 4.4-4.7 show the routes of a simulation with 3 robots. Figure 4.4-4.6
display the route of each robot with arrows to illustrate the directions of the movements. Figure 4.7 is the combination of the three routes where the repeated sections
of routes can be found due to distributed decisions made when the communication
is not available. By analyzing the route of each robot which is recorded in each step,
no collisions between robots are found, and the algorithm is functioning well.
The results in Table 4.1 and corresponding Figure 4.8 are the average results of
100 tests for 1 to 7 robots. The row ‘Code’ shows the time for the calculation in the
algorithm. The row ‘Total’ includes both the calculation time and the movement
time. It demonstrates that if more robots are working together, the number of search
steps will decrease significantly at the beginning and gently later. However, both
the number of robots n and the choosing time increase, so the waiting time in each
step which is n multiplies the time for ‘choose’ also increases. It can be seen clearly
that the moving time is much larger than the algorithm time so that the trend of
total time is similar to that of the number of steps, namely descending sharply from
1 to 5 robots and decreasing gradually from 5 to 7 robots. It can be predicted that
if there are more robots in this search area, the total time may keep stable followed
by a moderate rise as the increased algorithm time takes up larger proportion in the

61

4.1 2D Tasks

Figure 4.5: The route of robot 2 in a simulation of 3 robots

Figure 4.6: The route of robot 3 in a simulation of 3 robots

62

4.1 2D Tasks

Figure 4.7: Combined routes in a simulation of 3 robots

63

4.1 2D Tasks

No.

1

2

3

4

5

6

7

Steps

2638

1572

1116

931

795

730

661

Code(s)

22.0

27.0

29.0

30.3

33.7

37.2

39.0

Total(s)

13211

7885

5607

4687

4009

3688

3345

Table 4.1: Wpass and rst for each grid

Figure 4.8: Time and Steps
total time.
In this algorithm, the number of robots is flexible, and the algorithm is scalable.
The search time is also affected by the initial positions of the robots and the shape
of the area. As that information is unknown in the problem discussed in this paper,
the suitable range of the number of robots may only be estimated in simulations
with a general area when the rough size is given. Even for a fixed map, the optimal
number of robots should be decided by comparing the benefits from the decline of
the time and the cost of adding robots.

4.1.6

Section Summary

This section presented a decentralized random algorithm for multiple robots to
search static targets in an unknown 2D area. This algorithm sets a sequence for
making choices to avoid collisions and uses assumptions based on realistic conditions. A T grid pattern and the loose requirement of the area were used as an
example. Robots started with a preset common T grid pattern and the same coordinate system. Then they used the proved algorithm with local information to
choose future steps even if some robots failed in the calculation. Simulation results
for 1-7 robots showed the flexibility and scalability of the algorithm.

64

4.2 3D Tasks

4.2

3D Tasks

This section describes a search task for multiple robots in a 3D area using the decentralized random algorithm proposed in the 2D situation. The main difference
between these two areas is the dimension of the area and parameters. So the assumptions and definitions are given directly without repeated explanation. The
performance of the algorithm will also be analyzed using simulation in MATLAB.
As said in Chapter 2, the data of Bluefin-21 robots will be utilized, and the C grid
will be employed in the simulations.

4.2.1

Problem Statement

Problems in this section is for a three-dimensional area A ⊂ R3 which has a limited
number of obstacles O1 , O2 ,. . ., Ol . They need to satisfy the following assumption:
Assumption 4.2.1. Area A is a bounded, connected and Lebesgue measurable set.
The obstacles Oi ⊂ R3 are non-overlapping, closed, bounded and linearly connected
sets for any i > 0. They are both static and unknown to robots.
S
Definition 4.2.1. Let O := Oi for all i > 0. Then Ad := A \ O is the area that
needs to be detected.
There are m robots labelled as rob1 to robm to search n static targets t1 to tn .
The coordinate of robi is pi (k) at time k. Let T be the set of coordinates of targets
and Tki represents the set of coordinates fo targets known by robi .
Assumption 4.2.2. Initially, all robots have the same grid with the same coordinate
system and are allocated at different vertices along the border of the search area. In
the simulation, robots are manually set at vertices of the C grid
Assumption 4.2.3. All sensors and communication equipment on robots have spherical ranges. Other radiuses mentioned are also spherical.
Let the swing radius of robots be rrob and the safety radius to avoid collisions be
rsaf e . The total error is e. Then
Definition 4.2.2. rsaf e ≥ rrob + e (see Figure 2.11).
The C grid has a side length of a. According to Chapter 2, the passage width
Wpass satisfies
√
Assumption 4.2.4. Wpass ≥ 3a + 2rsaf e (see Figure 2.13).
The initial state of simulations is demonstrated in Figure 4.9 in which robots
start from vertices near the boundary of the area. The colored net with curves is
the border of the search area, and the two spheres inside are the obstacles. The
vertices of the net are the discrete boundary points which are close enough so that
robots will not pass the border. Passages between spheres and borders are designed
to fit Assumption 4.2.4. Black dots are the vertices of the cubic grid, and 13 robots
are labeled with colored shapes in the black curve. Red stars are targets t1 to t9
evenly distributed in the space because the compared algorithm Lévy fight works
best for sparsely and randomly distributed targets.
To avoid collisions with both obstacles and borders in movements, the sensing
range for obstacles rso satisfies:
65

4.2 3D Tasks

Figure 4.9: 3D area and initial settings

66

4.2 3D Tasks
Assumption 4.2.5. rso ≥ a + rsaf e (see Figure 2.11).
If there is any obstacle on the way from robi to one of its sensing neighbors, that
neighbor will not be visited. Then, let Va represents the set which includes all the
accessible vertices. Let the set of sensing neighbors Ns,i (k) contains all the closest
vertices ns,i,j (k) around robi at discrete time k in which j ∈ Z+ is the index of a
neighbor robot. In Ns,i (k), let the set containing visited vertices of robi be Vv,i (k) and
the set containing unvisited vertices be Vu,i (k). Then the choice of robi from Vv,i (k)
is represented by cv and the choice from Vu,i (k) is cu . To avoid collisions resulting
from having the same choice by different robots, robots choose the next steps in
a certain order as described in section 4.2.2 and at least need to tell the choice to
those which are one vertex and two vertices away. Thus, the communication range
rc satisfies:
Assumption 4.2.6. rc ≥ 2 ∗ a + e(see Figure 2.11).
Robots which are in the range rc of robi are called communication neighbors of
robi . The communication uses ad-hoc networks, and all robots are in equal status.
As the network is temporary, it will be rebuilt at the beginning of each loop. Let
Nc,i (k) denotes the set of communication neighbors of robi that it must communicate
with.
By having the concepts above, a further explanation about Figure 2.11 is given.
This figure demonstrates some parameters and the priority of making choices using
a cubic grid centered at robi . The small sphere shows rso with 6 magenta asterisks
(*) as sensing neighbors. The larger sphere illustrates rc with 26 blue plus signs (+)
and 6 magnet asterisks in it. Then, max(|Nc,i (k)|) = 32. Half of them (16 vertices)
in the black circles (o) have higher priorities than robi in making choice.
Assumption 4.2.7. The search task for a team of robots usually has a huge area.
So, a is much smaller than the length, the width and the height of area A. Therefore, the boundary effect is negligible which means there are no targets between the
boundary and the frontiers of the target sensing spheres.
√
Assumption 4.2.8. rst ≥ 2a/ 3 + rsaf e − rrob based on Table 2.3.
The aim of the section is to design a collision-free decentralized algorithm for
robots to search targets in a 3D area which satisfies the above assumptions using a
cubic grid.

4.2.2

Procedure and Algorithm

The general procedure for the 3D task is similar to the 2D version. So, it uses the
same rules for making choice (4.1)


6 0,
cu with prob. 1/|Vu,i (k)|, if |Vu,i (k)| =
pi (k + 1) = cv with prob. 1/|Vv,i (k)|, if (|Vu,i (k)| = 0)&(|Vv,i (k)| =
(4.4)
6 0),


pi (k), if |Ns,i (k)| = 0
and (4.2 and 4.3) for stop.
In situation I: pi (k + 1) = pi (k), if |Tki | = |T |
67

(4.5)

4.2 3D Tasks

Figure 4.10: The route of robot 1 in a simulation of 3 robots
In situation : pi (k + 1) = pi (k), if ∀vi ∈ Va , |Vu,i (k)| = 0

(4.6)

But the way to set the selection sequence is different. The 2th step of flow chart
4.2 and 4.3 sets the order of choices as illustrated in Figure 2.11. Let robj at pj be
a communication neighbor of robi . Then if pjx > pix | (pjy > piy &pjx ≥ pix ) | (pjz >
piz &pjy ≥ piy &pjx ≥ pix ), robj will have the higher priority. Thus in the figure,
16 vertices which is half of the max|Nc,i (k)| in the black circles will have higher
priorities than the middle robot robi . This will result in no contradiction from the
views of different robots.

4.2.3

Simulation Results

The simulation of the algorithm is run in MATLAB2016a. To illustrate the detail
in the route of robots apparently, the 8*8*8 grid in Figure 4.9 is used with three
robots label with red, blue and green color respectively. The route for situation I
with 9 targets are shown in Figure 4.10, 4.11 and 4.12 for the route of each robot
and Figure 4.13 is the combination of the three figures. The routes are illustrated
with arrows to show the directions of movements, and the route of each robot has
a distinct color. The result indicates that each target was within rst of the sensing
range of a visited vertex and there was no collision between robots based on the
routes.
Then, the algorithm is tested in a larger area which has 12*12*12 vertices in the
grid and 1 to 13 robots are used which are still at the bottom layer of the area near
point (1,1,1). Both situation I with Algorithm 4.2 and situation II with Algorithm
4.3 are considered and the simulations is run for 500 times to get the average search
time. Figure 4.14 shows the result for situation I and Figure 4.15 demonstrate the
result for situation II. Table 4.2 is used to show the ratio of calculation time to total
68

4.2 3D Tasks

Figure 4.11: The route of robot 2 in a simulation of 3 robots

Figure 4.12: The route of robot 3 in a simulation of 3 robots

69

4.2 3D Tasks

Figure 4.13: The combined routes of 3 robots

70

4.3 Summary

No.

1

2

3

4

5

6

7

Situation I

0.28%

0.31%

0.34%

0.37%

0.41%

0.49%

0.49%

Situation II

0.79%

1.34%

1.56%

1.90%

2.27%

2.40%

2.99%

No.

8

9

10

11

12

13

Situation I

0.63%

0.56%

0.62%

0.66%

0.74%

0.76%

Situation II

3.42%

3.54%

4.17%

4.67%

4.69%

5.67%

Table 4.2: The ratio of calculation time to total time
time for the two situations.
The two figures illustrate that, as the number of robots increases, the amount
of search time and the number of search steps decreases sharply at the beginning
but slowly later. However, the time in wait step will increase as it equals the time
for the choice of one robot multiplies the number of robots. However, the algorithm
time only accounts for a small percentage (≤ 5.7%)of the total time, so the trend
of the total time follows the trend of steps needed. As the percentage is increasing,
it may need to be considered when there are a significant number of robots. When
comparing the two figures, we can see that the time in situation II is more than four
times of situation I. Thus, for time-sensitive tasks, it is better to spend some time
to find the number targets if possible.
The simulation shows that the algorithm is flexible with different numbers of
robots and is scalable with areas in various sizes. However, other factors such as
initial locations of robots, the number of robots, and the shape of the area are
unknown in the problem discussed in this paper. So it is still hard to predict the
time of a search task even with a fixed area. To choose the suitable number of
robots, the user needs to seek a balance between the search time and the cost of
robots.

4.2.4

Section Summary

This section presented a decentralized search algorithm for a robot team in 3D area.
A C grid is used to simplify the algorithm and avoid collisions with a selection order.
In the algorithm, robots use local information and a random rule to explore the area
with a reliable failure detection method. Performance of the algorithm is simulated
for both situation I and situation II with 1 to 13 robots. The results show that the
algorithm is flexible and scalable.

4.3

Summary

This chapter proposed the first decentralized random algorithm for search task using
multiple mobile robots. The area which satisfies the assumptions is unknown with

71

4.3 Summary

Figure 4.14: Time and steps for situation I

Figure 4.15: Time and steps for situation II

72

4.3 Summary
unknown arbitrary static obstacles and targets. Robots can move via a grid pattern
without collisions. They start with a preset common grid pattern and the same
coordinate system. With the assumed sensing ranges and the communication range,
robots use the proved algorithm to choose future steps in order and move with
no collision until the task is finished even if some robots failed. All assumptions
are based on realistic conditions such as the volume and physical constraints of
the robots. A rigorous mathematical proof of the convergence of the algorithm is
provided. Simulation results show that, for the same task, more robots will use
fewer steps and time. However, the time may stop decreasing when the number of
robots increases to a certain value. Conclusively, the algorithm is scalable, flexible,
and reliable. It is suitable for both 2D and 3D area and can be transferred between
these two dimensions easily.

73

Chapter 5
A Collision-Free Random Search
with the Repulsive Force
This chapter proposes the second grid based decentralized algorithm without collisions. Comparing to the 1st algorithm in Chapter 4, this algorithm still uses the
random decision rule, but it adds the repulsive force of artificial potential field algorithm which improves the algorithm. The artificial potential field algorithm is used in
many search and complete coverage problems such as [18, 182, 54, 109, 158, 142, 73]
as it is easy to apply.
In this chapter, problem formulation and algorithm description will be simplified
and refer to Chapter 4. Only the different parts will be emphasized. Similar works
with grid algorithms, such as [131, 132, 129, 130, 11, 12, 10, 14], will be compared.
However, algorithms in those papers did not consider collision avoidance well or just
ignored it. Other random algorithms are mainly inspired by animals such as random
work or Lévy flight related algorithms [193, 38, 186, 63, 85, 33, 28]. They will also
be compared. The factors related to search time will be discussed in depth for 2D
areas. Also, experiments with Pioneer 3-DX robots are used to verify the algorithm
in a 2D area.

5.1

2D Tasks

This part proposed the second collision-free random algorithm for search task with
potential field algorithm. The way to find the relation between the search time,
the number of robots and the size of the area will be demonstrated. Other factors
related to search time will also be discussed to have a deeper understanding of this
algorithm. Unlike Chapter 4 which only analyzed the performance of the algorithm
itself, the algorithm in this section will be compared to many other algorithms to
show the effectiveness. Then an experiment using Pioneer 3-DX robots is done to
check the performance of the algorithm in reality.

5.1.1

Problem Statement

In this section, the task area is a two-dimensional area A with a limited number of
static obstacles O1 , O2 ,. . ., Ol . There are m robots labelled as rob1 to robn to search
static targets t1 to tn . An arbitrary known grid pattern with a side length of a is used
for robots to move in each step with the following definitions and assumptions. All
74

5.1 2D Tasks
these setting can be seen in Figure 5.6. Further explanations were given in Chapter
4.
Assumption 5.1.1. The area A is a bounded, connected and Lebesgue measurable
set. The obstacles Oi are non-overlapping, closed, bounded and linearly connected
sets for any i ≥ 0. They are both unknown to the robots.
S
Definition 5.1.1. Let O := Oi for all i > 0. Then Ad := A \ O represents the
area that needs to be detected.
Assumption 5.1.2. The initial condition is that all robots use the same grid pattern
and the same coordinate system. They start from different vertices near the boundary
which can be seen as the only known entrance of the area.
Assumption 5.1.3. All the ranges and radius in 2D search problems are circular.
Definition 5.1.2. To avoid collisions with other things before a move, a safe distance rsaf e should include both rrob and e (see Figure 2.2). So rsaf e ≥ rrob + e.
Assumption 5.1.4. If the T grid is used, all passages Wpass between obstacles or
between an obstacle and a boundary are wider than a + 2 ∗ rsaf e . Other Wpass for
other grid patterns can be seen in Table 2.1.
Assumption 5.1.5. The sensing radius for obstacles is rso where rso ≥ a + rsaf e .
Assumption 5.1.6. rc ≥ 2 ∗ a + e (see Figure 2.3).
Va is the set of all the accessible vertices. Ns,i (k) represents the set of sensing
neighbors around robi . In Ns,i (k), Vv,i (k) and Vu,i (k) denote the two sets for visited
vertices and unvisited vertex and the choices from these two sets are cv and cu
respectively.
If the strict requirement is used,
Assumption 5.1.7. The curvature of the concave part of the boundary should be
smaller than or equal to 1/rst .
Assumption 5.1.8. rst ≥ a + rsaf e .
If the loose requirement is used, the above two assumptions are not needed and
following assumptions are needed.
Assumption 5.1.9. The search area is usually vast. So, the side length a is much
smaller than the length and the width of area A. Therefore, the boundary effect is
negligible.
√
Assumption 5.1.10. rst ≥ a/ 3 + rsaf e − rrob .
The following definition is about variables in calculating repulsive force which is
new.
Definition 5.1.3. In loop k, pi,ave (k) is defined as the average position of choices
made by robots which chose earlier and positions of communication neighbors which
have not chosen the next step yet. Then dcu ,pi,ave (k) is the distance from pi,ave (k) to
one unvisited vertex and dcv ,pi,ave (k) is the distance from pi,ave (k) to a visited one.
Then the maximum values of these two parameters about distance are represented as
max(dcu ,pi,ave (k) ) and max(dcv ,pi,ave (k) ) separately. The corresponding sets of vertices
which result in these maximum distances are represented as Vumax,i (k) and Vvmax,i (k).
The chosen position of robi at time k + 1 is pi (k + 1).
75

5.1 2D Tasks

5.1.2

Procedure and Algorithm

The algorithm directs the robots to explore the area gradually vertex by vertex.
The general progress in the second search algorithm is the same as the first search
algorithm and the flow charts in Figure 4.2 and 4.3 can still be used. The key
difference is how to choose the next step.
Choices are made using the following random decentralized algorithm with repulsive force which is improved based on Chapter 4. When a robot has no neighbor
robots in rso , Algorithm 5.1 from Chapter 4 will be applied. It means, when there
are vacant unvisited vertices, robi will choose one from them randomly. If there are
only visited sensing neighbors to go, robi will randomly choose one from the visited
vertices. If there is no vacant sensing neighbor around, robi will stay at the current
position pi (k).


6 0,
cu with prob. 1/|Vu,i (k)|, if |Vu,i (k)| =
pi (k + 1) = cv with prob. 1/|Vv,i (k)|, if (|Vu,i (k)| = 0)&(|Vv,i (k)| =
(5.1)
6 0),


pi (k), if |Ns,i (k)| = 0
When robots have neighbor robots in rso , they apply the algorithm 5.2 which uses
the repulsive force of the artificial potential field. After receiving choices of previous
robots, at time k, robi will calculate pi,ave (k). Then it will randomly choose one
vertex from those which result in max(dcu ,pi,ave (k) ) if there are unvisited vertices to
go, or from max(dcv ,pi,ave (k) ) if there are only visited vertices to visit. Under this
circumstance, robots near each other will try to leave each other. So if there are
many unvisited vertices which are within rc of robots at time k, robots may have
more choices at time k + 1 by using rule 5.2 than using rule 5.1. If all the vertices
around are visited, robots will try to leave this visited section in different directions
simultaneously to have less repeated vertices comparing to using Algorithm 5.1.
Thus, they may find unvisited sections earlier. These two algorithms ensure that all
the places in Ad are searched.


6 0,
cu with prob. 1/|Vumax,i (k)|, if |Vu,i (k)| =
pi (k + 1) = cv with prob. 1/|Vvmax,i (k)|, if (|Vu,i (k)| = 0)&(|Vv,i (k)| =
6 0),


pi (k), if |Ns,i (k)| = 0
(5.2)
The stop strategy for this search algorithm is the same as that in Chapter 4. So,
in situation I:
pi (k + 1) = pi (k), if |Tki | = |T |.
(5.3)
In situation II:
pi (k + 1) = pi (k), if ∀vi ∈ Va , |Vu,i (k)| = 0.

(5.4)

Theorem 5.1.1. Suppose that all assumptions hold and the random decentralized
algorithms 5.1 & 5.2 with a related judgment strategy 5.3 or 5.4 are used. Then for
any number of robots, there is a discrete time k0 > 0 such that all targets are found
or all vertices are detected with probability 1.
Proof. The algorithms 5.1 & 5.2 with a corresponding judgment method form an
absorbing Markov chain which includes both transient states and absorbing states.
The transient states are the approachable vertices of the grid that robots visit but do
76

5.1 2D Tasks
not stop. Absorbing states are the vertices that the robots stop. Applying algorithms
5.1 & 5.2, robots tend to go to the unvisited neighbor vertices. If all sensing neighbors are visited before finding the targets, robots will randomly choose an accessible
neighbor, continue to the next step and only stop when all targets are found, or all
vertices are detected. For 5.3, an absorbing state will be reached until all robots know
|Tki | = |T |. For 5.4, an absorbing state will be reached until |Vu,i (k)| = 0 for any
vertex. As robot stop moving after the judgment conditions are satisfied, so absorbing states are impossible to leave. The assumption about Wpass guarantees that all
the accessible vertices can be visited so absorbing states can be achieved from any
initial states, namely with probability 1. This completes the proof of Theorem 5.1.1

5.1.3

Simulations with the Strict Requirement

Simulations with algorithms 5.1 & 5.2 for both situation I and II are run to verify
the algorithm. For situation I, one to nine targets which are averagely allocated in
the area are tested.
For situation I, Figure 5.1, 5.2, 5.3 and 5.4 is an example of searching 9 targets
by 3 robots. There are 900 vertices (30*30) in total in the graph. The boundaries
of the search area and obstacles are illustrated by the bold black lines made up by
discrete points. Distances between those points are designed to be small enough so
robots cannot pass the boundaries. Table 3.1 shows the parameters in the simulation
which are designed based on the datasheet of the Pioneer 3-DX robot. Robots had
been one vertex away from each target which means every target is found.
Based on the recorded route, there were no collisions between robots. Figure
5.5 displays the initial step (k = 1) of the above example. Orange circles are the
vertices which cannot be accessed as they are less than rsaf e to the boundary points.
Based on the method to decide selection order in Section 4.1.2.1, the robot labeled
by the blue square was the first to choose, the red one was the second, and the green
one was the last. Then based on the first condition of the algorithm 5.2, the blue
robot chose the unvisited vertex at the top left corner which is the only unvisited
vertex in the six sensing neighbors. The vertex with target t3 can be detected as an
obstacle, so it does not need to be visited. Similarly, the red robot chose the vertex
on the top left corner based on the first condition in 5.2. For the green robot, there
were two accessible unvisited neighbors so it calculated p3,ave (k) which is the orange
square and chose the vertex which results in max(dcu ,pi,ave (k) ) , namely the vertex
on the left side.
Search time may be affected by many factors including the number of robots,
the size of the area, the number of targets, the initial allocation of robots and Wpass .
The result of each situation is the average result for 150 simulations. In order to test
every situation in rules 5.1 & 5.2, at least seven robots are needed to guarantee one
robot can be blocked by six neighbors, which is the third condition of Algorithm
5.2 and can be seen in Figure 5.6. The six neighbors are in the first and second
conditions of Algorithm 5.2 and other conditions will happen in later loops. In
simulations, 1 to 13 robots were used, and the order of allocating robots is shown
in Figure 5.7.
Initially, simulations for one to thirteen robots with one, three, five, seven and
nine targets in an area of 574.8243618m2 (900 vertices) are run to check the relation
77

5.1 2D Tasks

Figure 5.1: Route of robot 1 in a simulation of three robots

Figure 5.2: Route of robot 2 in a simulation of three robots

78

5.1 2D Tasks

Figure 5.3: Route of robot 3 in a simulation of three robots

Figure 5.4: Combined routes in a simulation of three robots

79

5.1 2D Tasks

Figure 5.5: Choice in the first step of the simulation of three robots

Figure 5.6: Initial setting of the map

80

5.1 2D Tasks

Figure 5.7: The order and initial positions of robots
between the search time and the number of robots as well as between the search
time and the number of targets (see Figure 5.8 ). Here, 900 vertices include all
the vertices in the graph, and this representation is clear to identify the relation
between different areas. The size of the area is for the search area only which does
not include the parts occupied by obstacles. The area and obstacles have random
shapes with both concave and convex parts, and they satisfy the assumptions for
the strict requirement. Thus, the result in Figure 5.8 can be thought as a general
result for areas with obstacles. For each curve in Figure 5.8, as the number of robots
rises, the search time falls fast for 1 to 6 robots and slowly for 7 to 13 robots. The
shape of the line is similar to an inverse proportional function and generally can be
written in the form of the power function.
time = b ∗ mc + d

(5.5)

where b, c and d are the unknown parameters and m is the number of robots. As
the search time for nine targets is compared with others in the next few paragraphs,
the function for that line is estimated using the least squares method with four
significance bits for accuracy, namely
time = 1295 ∗ 10 ∗ m−1.209 + 420.2.

(5.6)

This function is the red dotted line with asterisks in 5.8. When searching different
numbers of targets using the same number of robots, the search time increases with
the number of targets. However, it can be seen that time differences between five,
seven, and nine targets are smaller than that between one, three and five targets as
robots need to go to most parts of the area to find all the targets when there are
five, seven, and nine targets. This is because targets t2 , t3 , t4 and t5 have taken up
the four corners of the area.
81

5.1 2D Tasks

Figure 5.8: Search time for 1-13 robots with 1, 3, 5, 7 and 9 targets
Secondly, 1 to 13 robots with 9 targets in areas of 63.87m2 (100 vertices),
255.48m2 (400 vertices), 574.82m2 (900 vertices), 1021.91m2 (1600 vertices) and
1596.73m2 (2500 vertices) are tested to discover the relation between the search
time, the number of robots (Figure 5.9) and the size of the area (Figure 5.10). It
should be noted that these five areas are expanded or shrunk based on the 900 vertices area, so they have the same shape so the area ratio is the same as vertices
ratio which is 1:4:9:16:25. All robots start from the bottom right corner near target
t3 , so the starting points are controlled to have the minimal effect on the result.
The curvatures are initially designed to satisfy the requirement in the area with
900 vertices, so the curvatures in the expanded areas also meet this requirement.
Nonetheless, for the shrunk area, curves of some parts do not meet the requirement,
so the grids are slightly moved to guarantee a complete search. The result in Figure
5.9 agrees with Figure 5.8. It also illustrates that as the size of area increases, the
search time increases as well. If the search time for 100 vertices is considered as 1
for each number of robots, the ratio of search time in different areas to the search
time in the area with 100 vertices can be demonstrated by Figure 5.10. It can be
claimed that there is always a linear relation between the search time and the area.
The gradients of the lines are different, and there is no fixed relation between the
gradient and the number of targets. So the average trend of the 13 lines is calculated
using the least squares method and four significance bits,
ratio = area ∗ 0.02328 − 1.024.

(5.7)

This equation is the red dotted line in Figure 5.10. The base of this equation namely
the time function for 100 vertices is
time = 1401 ∗ m−1.146 − 10.35.

(5.8)

It is the red dotted line in Figure 5.9. So, the general time function should be the
82

5.1 2D Tasks

Figure 5.9: Search time for 9 targets with 1-13 robots in 5 areas
multiplication of ratio 5.7 and time 5.8:
timetotal = 32.62 ∗ m−1.146 ∗ area − 1435 ∗ m−1.146 − 0.2410 ∗ area + 10.60

(5.9)

Thirdly, search time of two kinds of allocations for 1 to 13 robots is compared
in the area of 900 vertices. Robots are allocated in a circle (Figure 5.5) and in a
curve (Figure 5.13) respectively. The results are displayed in Figure 5.11 and 5.12
for situation I and II. For Figure 5.13, robots still start from the bottom right corner
of the searching area, and every robot is in the obstacle sensing range of at least
one robot to ensure that robots can communicate with each other and the operator
does not need to move too far to deploy all robots. In both Figure 5.11 and 5.12,
for 1-4 robots, the search time are close since the allocations for 1 to 3 robots are
similar in a line near target 3 in both situations. For 5-13 robots, search time for
robots in a circle is more than robots in a line. The reason is that robots are easier
to block each other when allocated in a circle. Thus, some robots, for example, rob1
and rob2 , need to choose a visited neighbor vertex even in the first step. In the next
few steps, a robot may also repeat others choices, which is a waste of the resource.
The deployment in a line decreases the chance of repeating vertices in the first few
steps. It can be predicted that, if the distances between robots can be set larger
but less than the communication range, robots will repeat fewer vertices in the first
few steps as they could not only communicate to get explored map from others but
also have more unvisited vertices around. Thus, robots could spend less time in the
search task.
The widths of passages in the area also affect the search time. If narrow passages
with widths near Wpass are used to connect subareas, robots in one subarea will have
a lower chance to move through the passage and leave that subarea. Thus, longer
search time is needed compared to those using wide passages in a search area with
all other three factors controlled to be the same.
83

5.1 2D Tasks

Figure 5.10: Time ratio based on 100 vertices for 1-13 robots in five areas

Figure 5.11: Search 9 targets in 900 vertices area with different allocations in situation I

84

5.1 2D Tasks

Figure 5.12: Search 9 targets in 900 vertices area with different allocations in situation II

Figure 5.13: The order of allocation for 13 robots in a curve

85

5.1 2D Tasks
In the proposed algorithm, the number of robots is flexible, and the algorithm is
scalable. As the area is unknown, the function of search time may be estimated using
the least squares method for simulation results with all possible known information
and a long practical distance between robots in a line for initialization. Even for a
known area, the optimal number of robots should still be decided by comparing the
benefits from the decline of time with the cost of adding more robots.

5.1.4

Comparison with Other Algorithms

The proposed algorithm is also compared with other decentralized random algorithms for search task in [12, 193] in situation I. For [12], there are three methods
using the T grid which are the random choice (R) algorithm, the random choice
with unvisited vertices first (RU) algorithm and the random choice with path to the
nearest unvisited vertex (RUN) algorithm. However, in RUN, robots may not move
straightly along the edges of triangles resulting to problems in path planning and
collision avoidance. For example, how to use the repulsive force to plan the path
when there are obstacles and other robots in the path and when and where to stop
if the time for the movement step is used up without reaching the destination. But
[12] does not provide solutions for those problems. Therefore, this algorithm is unconvincing and could not be simulated so RUN is not compared with the proposed
algorithm. In [193], the random walk (RW) algorithm, the LF algorithm and the
Lévy flight with potential field (LFP) algorithm are discussed which are all compared with the proposed algorithm. In those algorithms, a normal distribution is
needed to generate turning angles. The parameters of the normal distribution are
set as µ = 0 and σ = 1 and the angle range is (−π, π]. The step length of the RW
algorithm will also be generated by the normal distribution with µ = a/2, σ = 1 and
a maximum step length a. The Lévy distribution is utilized to generate the lengths
of movements. Based on [38], it needs two independent random variables, f and
g, generated by standard normal distribution above for angles to get the medium
result h where
f
(5.10)
h = 1/α
|g|
Then the sum of h with an appropriate normalization
zn =

n
1 X

n1/α

hk

(5.11)

k=1

converges to the Lévy distribution with a large n which is 100 usually so n=100
is used. The constant α is a parameter in the Lévy distribution function ranges
from 0 to 2 which is 1.5 in the simulation. When α=2, the distribution will become
the Gaussian distribution. The repulsive force is needed to disperse robots in LFP
which has the following formula according to [40].

k ( 1 − 1 ) 1 q − qobstacle , if ρ(q) ≤ ρ
−−→
0
rep
ρ(q) ρ0 ρ2 (q)
ρ(q)
Frep = −∇Urep (q) =
(5.12)

0, if ρ(q) > ρ0
The repulsive force Frep is used as the weight of the velocity in a certain direction.
Urep (q) is a differentiable repulsive field function. krep is the scale factor. Without
86

5.1 2D Tasks
losing generality, it is chosen as krep = 1. ρ0 is the maximum distance to apply
the force and ρ(q) is the minimal distance from a robot to its nearest obstacle.
q = (x, y) represents the coordinate of the robot and qobstacle is the coordinate of
the obstacle.
Algorithms R, RU, RW and LF did not provide any solution for collisions between
robots. The applied strategy in the simulation is allowing collisions happen and
counting the number of collisions. It is assumed that one more loop is needed to
finish the search for each collision. In fact, if consecutive collisions happen, more
than one extra loops may be required.
To compare all methods in the same environment, all the algorithms are simulated in the area in Figure 5.6 with one (Figure 5.14 and 5.15) and nine targets
(Figure 5.16 and 5.17) separately. The results in the four figures are the average
result of at least 100 simulations. Nevertheless, [12] had contradicted descriptions in
the method of transmitting information of targets and [193] used targets as stations
to store and transmit information. These are different from the proposed method
in this paper. So, to control all the factors to be the same, equation 5.3 for stop
judgment, ad-hoc with rc for the communication and broadcasting for transmitting
positions of targets are applied in all the algorithms. The algorithm R is much slower
than the others. To see the small time difference between other methods, Figure
5.14 and Figure 5.16 compare all algorithms except R for one and nine targets separately. Time for R is only displayed in two additional figures, namely Figure 5.15
with one target and Figure 5.17 with nine targets, with the second slowest algorithm
RU to show how slow it is. [193] claimed that LF algorithm and LFP algorithm are
advantageous when targets are sparsely and randomly distributed. Therefore, the
nine evenly separated targets in the area allow those two algorithms to fully unfold
their potential, which makes the comparison more convincible.
In the line chart, the first algorithm in Chapter 4 is represented as S1 and the
second search algorithm in this chapter is labeled as S2. The four line charts show
that the proposed algorithm S2 is always the best under the strict requirement. The
general ranking of search time from the graph is S2<S1<LFP<RU<LF<RW<R.
For all the algorithms, as the number of robots ascended, the search time descended
significantly at the beginning but gently later because more time will be spent on
repeating visited vertices and collision avoidance instead of exploring new vertices
only. For R and RU, although the number of loops decreases, the number of collisions
grows and the time on dealing with collisions accounts for a larger proportion of the
total time. This leads to slower descending search time or even ascending time as
RU in Figure 5.14 and R in Figure 5.15. The detail of time and collisions for RU
in Figure 5.14 is shown in Table 5.1. In that table, all values are average values
for one simulation. The row ‘collision’ shows the number of collisions and the row
‘tc ’ is the time to deal with collisions. The ‘total time’ includes tc , algorithm time
and movement time. In RW, LF, and LFP, when there are more robots, robots
will have higher chance to encounter others. Thus, they will turn more frequently
without fully executing the translation part of the algorithm so that the efficiency of
the algorithm will decline resulting in a more moderate decrease in the search time.
As to the proposed algorithm in Table 5.2, ‘ta ’ represents the average time used in
the algorithm in a simulation, ‘ta /loop’ is the ta for each loop. To avoid collisions,
the time in waiting will increase with the rise in the number of robots, because the
wait time in each loop equals the number of robots multiplies the time for choosing.
87

5.1 2D Tasks

Figure 5.14: Search time for 1 target using 6 algorithms

Figure 5.15: Search time for 1 target using algorithms R and RW
88

5.1 2D Tasks

Figure 5.16: Search time for 9 targets using 6 algorithms

Figure 5.17: Search time for 9 targets using algorithms R and RW
89

5.1 2D Tasks

No.

1

2

3

4

5

6

7

Loop

303

143

110

81.1

74.8

63.6

56.3

Collisions

0.00

1.32

3.74

7.67

10.5

14.8

21.4

tc (s)

0.00

7.56

21.5

44.1

60.2

84.9

123

Total time (s)

1748

833

655

512

492

452

448

No.

8

9

10

11

12

13

Loop

53.4

49.1

48.2

43.3

42.9

42.3

Collisions

21.1

26.7

28.7

32.0

36.9

42.1

tc (s)

121

153

165

184

212

242

Total time (s)

429

437

443

434

476

499

Table 5.1: Results of RU for 1-13 Robots in 900 vertices area with 1 target. (RU in
Figure 5.14)
Therefore, ta /loop goes up as the number of robots increases. However, ta only
consists a small proportion of the total time even in the simulation with 13 robots
(0.5396%) so the trend of the total time is similar to the trend of the number of
loops. However, if there are hundreds of robots in real applications, this proportion
will increase to a level that needs to be considered.

5.1.5

Robot Test

Algorithm 5.1 & 5.2 in situation I is verified by one to three Pioneer 3-DX robots
(Figure 2.7) in a 429mm*866mm (maximum width*maximum length) area as seen
in Figure 5.18. The robot has 16 sonars around to cover 360 degrees for objects
with a height of 15.5cm-21.5cm and Figure 2.8 displays half of them. The robot also
has a SICK-200 laser to scan 180 degrees in the front (see Figure 2.9) for objects
higher than 21.5cm. Based on the difference of the heights, the test environment is
set as Figure 5.18. The three large triangular boxes are obstacles. Obstacles and
boundaries are set lower enough to be detectable for sonars only. Then a tall brown
triangle box at the left side of the end was set as the target and can be detected by
both sonars and the laser. Robots use Wi-Fi in ad-hoc mode to communicate with
others using TCP.
Parameters of the robot used in the test are in Table 5.3. The safety distance dsaf e
is calculated based on the odometry errors of robots. Based on the measurement,
if a robot moves forward straightly for 8m, it may shift 0.08m to the left or right
at most. As the moving distance from the bottom to the top of Figure 5.18 is less
than 8m, dsaf e =0.09m is large enough for collision avoidance even if there are errors.
90

5.1 2D Tasks

No.

1

2

3

4

5

6

7

ta (s)

36.62

17.71

12.48

10.88

8.00

6.92

6.95

ta /loop (s)

0.0161

0.0171

0.0182

0.0192

0.0207

0.0220

0.0231

Total time (s)

13117

5989

3965

2857

2279

1864

1589

No.

8

9

10

11

12

13

ta

6.08

5.83

5.50

5.71

5.53

5.59

ta /loop (s)

0.0243

0.0270

0.0270

0.0284

0.0302

0.0312

Total time (s)

1449

1337

1204

1154

1076

993

Table 5.2: Results of S2 for 1-13 Robots in 900 vertices area with 9 targets. (5.1 &
5.2 in Figure 5.16)

Figure 5.18: The test area

91

5.1 2D Tasks

P

rrob (m)

rsaf e (m)

rso (m)

rst (m)

a(m)

R

0.26m

0.35m

5m

32m

4.65m

S

0.26

0.35

1.44

1.35

1

P

rc (m)

vmax (m/s)

ωmax (◦ /s)

tmove (s)

Wpass (m)

R

91.4m

1.5m/s

300◦ /s

5.75s

5.35m

S

2.09

0.3/s

300

10s

1.7

Table 5.3: Parameters of robots and in experiment

Figure 5.19: The average result for 10 tests with 1-3 robots
Note that the rso in the test is different from simulations as the used sonars have a
minimum target sense range min(rso ) which is around 0.17m. Objects within this
range will be considered as having an infinite distance from the robot. Therefore,
the way to calculate rso is changed to the equality condition of the inequality rso ≥
a + min(rso ) + rsaf e .
The test is done for ten times for each number of robots, and the results are
illustrated in Figure 5.19. The example routes of experiments with one to three
robots are displayed in Figure 5.20-5.22 separately. Figure 5.20 also has legends
labeled on the corresponding items. The search time of the robot test agrees with the
result of simulations, namely having a descending trend which is gradually slower.
The experiment shows that by applying Algorithms 5.1 & 5.2 in situation I, the
target can be found successfully by 1 to 3 robots without any collision.

92

5.1 2D Tasks

Figure 5.20: The example route for one robot with legends (13 loops)

Figure 5.21: Example routes for two robots (10 loops)

Figure 5.22: Example routes for three robots (6 loops)

93

5.1 2D Tasks

5.1.6

Factors in Choosing a Grid under the Loose Requirement

Definition 5.1.4. Let Nvt represents the number of vertices within rst of one target.
Let Pt represents the proportion of the number of vertices within rst of all targets to
the total number of vertices.
Under the loose requirement, different grid patterns can be used with various
amounts of vertices. The number of vertices is a significant factor for search time.
However, fewer vertices do not always result in shorter search time. Three other
possible factors for choosing a grid pattern are Pt , the structure of the grid and
Wpass . Simulations and analyses in this section use situation I and the seventh
condition in Table 2.2 which satisfies the parameter of robots in Table 5.3.
Example of different Nvt are shown in Figure 5.23, 5.24 and 5.25 for a T grid, an
S grid and an H grid with different colors. In the examples, a = 1 and rst ≥ a + rsaf e
are set so that a target can be detected from different vertices and the setting could
work for all the three gird. The cyan hexagon, square, and triangle show the sections
which are occupied by the vertices in the middle of the areas. Circles which have
intersections with the cyan areas show all the related rst centered at nearby vertices.
Then labels with different colors are used to represent different Nvt values. As the
graphs are symmetrical, only parts of the area are marked. The effect of Pt will be
evident when there are many targets in a relatively small area. The area in Figure
5.26 is used with no obstacles to avoid the effect of Wpass . The average search time of
500 simulations using 1 to 13 robots via a T grid with Nvt =4 and Nvt =6 is presented
in Figure 5.27. The corresponding Pt values are around 4.5% and 6.7% respectively.
Figure 5.27 shows that when Pt is larger, the search time is smaller. To minimize
the effect of Pt in discussing other factors, this factor of the three kinds of grids
should be similar. The ratio between the numbers of vertices of the T grid, the S
grid, and the H grid is 1.5:1.3:1. So the corresponding integral Nvt values in future
simulations are set to be 6, 5 and 4 which lead to the ratio of Pt as 1.5:1.25:1. Note
that those Nvt values are also close to the average values for the three grids in the
selected condition, so the setting is practical.
The structure of the grid affects the search time by affecting the possible routes
to a target. This can be understood by looking at the shortest path as an example.
In the current situation and condition, all robots use a1 as the side length. Then an
H grid can be seen as a part of a T grid. Therefore the shortest path via an H grid
is equal to or longer than that via the corresponding T grid. However, the average
path length which determines the mean time cannot be calculated, so simulations are
used to see the effect. Figure 5.28 and 5.29 show the average time of 500 simulations
for searching one target in the middle or separated nine targets in the area of Figure
5.26 by one to 13 robots via three grids. There are no obstacles in the area so the
effect of Wpass can be ignored. Based on Table 2.2, the vertex in the H grid covers
the largest area, so the H grid has the least vertices. However, in Figure 5.28, the S
grid has the least time for three to five robots, and the H grid has the least time for
other numbers of robots. In Figure 5.29, the S grid has the least time. Therefore,
the fewest vertices do not guarantee the least search time, and the structure of the
grid can affect the time.
The third factor Wpass affects the search time by affecting the chances to enter
or leave an area as discussed in Section 5.1.3. For the same Wpass , the opportunity
94

5.1 2D Tasks

(a) Ranges and neighbors

(b) Color label

Figure 5.23: Nvt for a T grid: star-4 green-5 purple-6 red-7

(a) Ranges and neighbors

(b) Color label

Figure 5.24: Nvt for an S grid: purple-4 yellow-5 green-6 star-7

95

5.1 2D Tasks

(a) Ranges and neighbors

(b) Color label

Figure 5.25: Nvt for an H grid: star-2 red-3 green-4 yellow-5 purple-6

Figure 5.26: A T grid with no obstacles

96

5.1 2D Tasks

Figure 5.27: Time for a T grid with Nvt =4 and Nvt =6

97

5.1 2D Tasks

Figure 5.28: Time for three grids with one target

Figure 5.29: Time for three grids with nine targets

98

5.2 3D Tasks
for each grid is distinct. For example, if all these three grids use a as the side length
with a passage Wpass = 2a1 + 2rsaf e which is the largest one in Table 2.1, the width
can fit at least three vertices for a T grid and two vertices for both an S grid and
an H grid. However, the corresponding ratio of the number of vertices in the three
grids is 1.5:1.3:1. Thus, robots using an S grid may have less chance to enter or
leave a search section through this passage. So Wpass needs to be considered in the
simulation design.
From the above discussions, it is clear that when choosing the grid for the loose
requirement, the number of vertices is important but not the only determinant. The
average Nvt needs to be calculated based on the condition in Table 2.2. The given
Wpass or the minimum Wpass , which satisfies all the three grids, needs to be found.
Then the simulations with these Nvt and Wpass should be run to compare the search
time of the three grids and find the best one.

5.1.7

Section Summary

This section presented a random decentralized algorithm with the repulsive force
for multiple robots to search targets in 2D areas through a grid pattern without
any collision. The repulsive force could help robots to be away from each other if
they met to reduce repetition. The convergence of the algorithm is proved, and
simulations showed that the proposed algorithm is the best comparing to other six
algorithms. An example of how to estimate the relation between search time, the
number of robots and the size of the area was demonstrated for nine targets to help
decide the suitable number of robots. A test on Pioneer 3-DX robots also verified
the algorithm. When only detecting all the vertices is required, simulations need to
be used to find the best grid considering the grid with the least number of vertices,
structure of the grid pattern, suitable Wpass and Pt .

5.2

3D Tasks

This section presents a decentralized random algorithm for multiple robots to search
targets in an unknown 3D area with obstacles via the cubic lattice. The algorithm
is the same as the one in 2D. It considers the realistic physical constraints and
conditions of all parameters as well as collision avoidance so that it can be applied
to real robots. Robots choose vertices in sequence and move between vertices along
edges of the lattice based on local information. The convergence of the algorithm is
proved, and the effectiveness is shown in comparison with three other algorithms.

5.2.1

Problem Statement

The problem is the same as that in Chapter 4. So the definitions and assumptions
below are claimed without detailed description.
In the search task, a three-dimensional area A ⊂ R3 with a limited number of
obstacles O1 to Ol is used. m robots labelled as rob1 to robm are employed to search
n static targets t1 to tn through a cubic grid with a side length a. For robi , its
coordinate at time k is pi (k). Let T be the set of coordinates of targets and Tki be
the set of targets coordinates known by robi . The initial setting is in Figure 4.9.

99

5.2 3D Tasks
Assumption 5.2.1. Area A is a bounded, connected and Lebesgue measurable set.
The obstacles Oi ⊂ R3 are non-overlapping, closed, bounded and linearly connected
sets for any i > 0. They are both static and unknown to robots.
S
Definition 5.2.1. Let O := Oi for all i > 0. Then Ad := A \ O is the area that
needs to be detected.
Assumption 5.2.2. Initially, all robots have the same grid with the same coordinate
system and are allocated at different vertices along the border of the search area. In
simulations, robots are manually set at vertices of the C grid
Assumption 5.2.3. All sensors and communication equipment that robots carry
have spherical ranges. Other radiuses mentioned are also spherical.
Definition 5.2.2. Robots have a swing radius rrob and the total error is e. Then a
safety radius to avoid collisions is rsaf e ≥ rrob + e (see Figure 2.11).
√
Assumption 5.2.4. Wpass ≥ a 3 + 2rsaf e (see Figure 2.13).
Assumption 5.2.5. rso ≥ a + rsaf e (see Figure 2.11).
Assumption 5.2.6. rc ≥ 2 ∗ a + e(see Figure 2.11).
Assumption 5.2.7. The task area is vast. So, a is much smaller than the length,
the width and the height of area A. Thus, there are no targets between the boundary
and the frontiers of the target sensing range, which means the boundary effect can
be ignored.
√
Assumption 5.2.8. rst ≥ 2a/ 3 + rsaf e − rrob based on Table 2.3.
Va is the set of all the accessible vertices. Ns,i (k) represents the sensing neighbors
set around robi . In Ns,i (k), Vv,i (k) and Vu,i (k) denote the sets for visited vertices
and unvisited vertex and the choice from these two sets are cv and cu respectively.
Then a set of new definitions for the distances and vertices in this chapter are stated
as follows:
Definition 5.2.3. The average position of choices made by robots which chose earlier and current positions of communication neighbors who have not chosen yet is
pi,ave (k). Let dc,pi,ave (k) be the set of distances from pi,ave (k) to the possible choices.
Then, dcu ,pi,ave (k) is the set of distances to unvisited vertices and dcv ,pi,ave (k) is the set
of distances to visited ones. Then max(dcu ,pi,ave (k) ) and max(dcv ,pi,ave (k) ) are the maximum values in the two sets respectively. The corresponding sets of vertices which
result in these maximum distances are represented as Vumax,i (k) and Vvmax,i (k).

5.2.2

Procedure and Algorithm

The general procedure of the algorithm is the same as the 2D algorithm. So the
same flow charts in Figure 4.2 and 4.3 are available for Situation I and II. However,
the way to set the sequence is different from the 2D case and readers can refer to
Section 4.2.2 for detail. Comparing to the first search algorithm, the improvement
of this algorithm is on how to use local information to make choice. So, when there

100

5.2 3D Tasks
are no local neighbors in rso , Algorithm 5.13 is used but when there are neighbor
robots within rso of a robot, it will apply Algorithm 5.14 to make choice.


6 0,
cu with prob. 1/|Vu,i (k)|, if |Vu,i (k)| =
pi (k + 1) = cv with prob. 1/|Vv,i (k)|, if (|Vu,i (k)| = 0)&(|Vv,i (k)| =
(5.13)
6 0),


pi (k), if |Ns,i (k)| = 0


6 0,
cu with prob. 1/|Vumax,i (k)|, if |Vu,i (k)| =
pi (k + 1) = cv with prob. 1/|Vvmax,i (k)|, if (|Vu,i (k)| = 0)&(|Vv,i (k)| =
6 0),


pi (k), if |Ns,i (k)| = 0
(5.14)
Algorithm 5.15 and 5.16 are employed to judge the stop time.
In situation I: pi (k + 1) = pi (k), if |Tki | = |T |.

(5.15)

In situation II: pi (k + 1) = pi (k), if ∀vi ∈ Va , |Vu,i (k)| = 0.

(5.16)

Theorem 5.2.1. Suppose that all assumptions hold and the proposed decentralized
random algorithm, namely Algorithm 5.13 and 5.14 with related judgment strategy
5.15 or 5.16, are used. Then for any number of robots, with probability 1, there
exists such a time k0 > 0 that all targets or all vertices are detected.
Proof. The algorithm 5.13 and 5.14 with corresponding judgment methods form an
absorbing Markov chain including both transient states and absorbing states. The
transient states are all the approachable vertices of the C grid where robots visit but
do not stop forever. Absorbing states are the vertices where the robots finally stop.
By applying the proposed algorithm, robots start from some initial transient states
and move between different transient states with the probability from the algorithm.
The robot will go to the unvisited sensing neighbors if there are any with the help
of the repulsive force. If all sensing neighbors of a robot are visited, the robot will
randomly choose an accessible neighbor with the repulsive force. If no accessible
neighbor vertices are available, it stays at current vertices. For 5.15, robots stop
at an absorbing state if all robots know |Tki | = |T |. For 5.16, absorbing states are
reached until |Vu,i (k)| = 0 for all accessible vertices. Based on Assumption 5.2.4,
absorbing states can be achieved from any initial states, namely with probability 1.
This completes the proof of Theorem 5.2.1.

5.2.3

Simulation Results

A search task for situation I is simulated in MATLAB2016a. The parameters are
set based on Table 3.4. To display the details of the proposed algorithm, a small
area which has 8*8*8 vertices with 9 targets is used to be searched by 3 robots
using control laws 5.13, 5.14 & 5.15 as shown in Figure 5.30-5.33. The routes are
illustrated with arrows to show the directions of movements, and the path of each
robot has its color. By analyzing the route of each robot, no collisions were found,
and each target was within rst of a visited vertex.
To verify the algorithm further, the search time using different algorithms namely
the LFP algorithm in [193], the RU algorithm in [170], rules 4.4 & 4.5(S1 in line
charts) in Chapter 4 and rules 5.13, 5.14 & 5.15(S2 in line charts) in this chapter are
101

5.2 3D Tasks

Figure 5.30: The route of robot 1 in a simulation with 3 robots

Figure 5.31: The route of robot 2 in a simulation with 3 robots

102

5.2 3D Tasks

Figure 5.32: The route of robot 3 in a simulation with 3 robots
compared. LFP and RU are chosen as they are better than related algorithms based
on the simulation results in 2D. In RU, there are collisions so it is assumed that one
collision needs one more movement time to get solved although longer time may
be needed if there are consecutive collisions. According to the assumption 5.2.7,
targets are allocated in the detectable area as in Figure 4.9. Time in movement
in the simulation is 5.75s in total including 4.5s for a translation and 1.25s for a
rotation which is in Table 3.4.
The simulation for searching nine separated targets in a larger area (12*12*12
vertices) by 1 to 13 robots has been run for 500 times to get the average search
time. Algorithm LFP is always much slower than the others as no previous map
will be used. So, Table 5.4 is used to show the time for LFP and RU specially
and algorithms except LFP are drawn in 5.34 to make the graphs clear. The figure
demonstrates that time in the three algorithms for one robot is similar as they are
the same in that situation. For more robots, time for S2 is always smaller than S1
as robots are separated to different parts to find distributed targets. When there
are 1 to 6 robots, algorithm RU is the fastest because robots can move without
considering the collisions, which provides more choices in each step for robots to
search different areas and it has the simplest rule which saves the calculation time.
Also, its disadvantage that it needs extra time to deal with collisions is not severe as
the number of collisions is small. When there are more than six robots, algorithms
S2 is the fastest as the time saved in collision avoidance is larger than the increased
waiting time before choosing in the algorithm. So, the proposed algorithm is the
best comparing to those with the collision avoidance scheme. When there are a large
number of robots, it is even better than algorithm RU which does not avoid collisions
between robots. In all the four algorithms, when the number of robots ascended, the
search time descended sharply at the beginning and slowly later. It can be predicted
that if the number robots increases, the search time of the proposed algorithm may
have a stable period or even an increasing part at the end as the algorithm time in
103

5.2 3D Tasks

Figure 5.33: The combined routes in a simulation with 3 robots

104

5.2 3D Tasks

Figure 5.34: Time for four algorithms with 9 targets
the step ‘wait’ will increase and take up a larger proportion of the total time.
Therefore, the optimal number of robots should be decided based on comparing
the benefits of decreased search time and the cost of increased expense on robots.
The search time is also affected by unknown factors including the initial positions
of robots and the shape and the size of the area. If the size of the area is given,
simulations like those in this paper can be used to estimate the proper rough range
of the number of robots according to the limitation of the search time in a general
situation.

5.2.4

Section Summary

This section proposed a random decentralized search algorithm for multiple robots in
a 3D region which is based on the 2D algorithm. All robots move simultaneously with
a C lattice to avoid collision. The repulsive force helps robots to have less repeated
area. By comparing different algorithms in simulations, the proposed algorithm is
always the best in those with collision avoidance and the best in all the algorithms
when there are more than a certain number of robots.

105

5.3 Summary

No.

1

2

3

4

5

6

7

RU

5290

2701

1855

1402

1111

952

855

LFP

9624

5063

3389

2688

2004

1771

1476

No.

8

9

10

11

12

13

RU

748

692

646

611

571

552

LFP

1352

1193

1176

1005

903

874

Table 5.4: Search time for algorithm LFP and RU with 9 targets

5.3

Summary

This chapter proposed the second search algorithm for a group of mobile robots. The
robot moves via the selected grid pattern to select vertices in sequence and avoid
collisions in an unknown area. Compared to the first algorithm, the repulsive force
is added to disperse robots when they are neighbors in obstacle sensing range. So
they tend to leave for different directions to have less repeated area. The algorithm
is suitable for both 2D areas and 3D areas with differences in the selection sequence
and the dimension of parameters. A rigorous mathematical proof of the convergence
of the algorithm was provided with probability 1. In the 2D area, this chapter illustrated how to find the relation between the search time and other parameters. With
loose requirement, it suggested using simulations to find the best grid considering
different factors. Then, an experiment on three Pioneer 3-DX robots was conducted
to verify the algorithm. In both 2D and 3D area, the proposed algorithms were compared with other grid-based algorithm and Lévy flight related algorithm to show the
effectiveness. Conclusively, the algorithm is scalable, robust, reliable and effective.

106

Chapter 6
A Collision-Free Random Search
with the Breath-First Search
Algorithm
The third grid based collision-free search algorithm is proposed in this chapter. The
algorithm is decentralized with the help of a grid pattern in a 2D or 3D unknown
area. Robots choose their future steps based on random algorithm when there
are unvisited neighbors and use the breadth-first search algorithm when they are
surrounded by visited vertices. As the algorithm in this chapter is solving the same
problem as the task in Chapter 4, the way to state the problem and describe the
algorithm will be similar but simpler, and only the different parts will be emphasized.
In the two previous search algorithms, there are a considerable number of repeated
vertices in the search. So this chapter focuses on how to use the known information
to escape the visited area. Thus, a graph search algorithm, namely the breadthfirst search algorithm is added to find one of the nearest unvisited vertices and the
shortest way to it. The shortest way in this chapter means the route with the fewest
number of steps from the current vertex to the target vertex. To check the effect
of this algorithm, simulations of the algorithm will be carried out comparing to 7
other algorithms to show the effectiveness. Then the advantages and disadvantages
of the three proposed algorithms will be discussed.
Similar algorithms with a method to decrease the amount of repeated search
include [14] and [132, 131]. In [14], the grid pattern is also used for robots to move
through. Robots used the explored map to find the nearest vertices and ‘the nearest’
means the minimum Euclidean distance which can be represented by de . However,
with unknown obstacles in the area, a robot may need to move a longer actual step
ds to reach the target point, especially when the robot and the target vertex is
at the two sides of the narrow part of a long obstacle. With this method, robots
may walk without passing the edge of the grid, and a dynamic collision avoidance
method must be provided. However, [14] did not provide the detail of collision
avoidance method and only claimed it used the embedded repulsive force method
from Pioneer 3-DX robots. It also did not provide what a robot should do if it is
not on a vertex, but its algorithm with assumptions on ranges was based on the
implied assumption that robots are on the vertices. As the maximum speed is set,
the step with different lengths will use different time. If all robots waited for the
longest movement time which is estimated and designed for the one that leaves the

107

6.1 2D Tasks
visited area to move further, the normal robots which only move a can be thought
as wasting their time in waiting. If robots are not synchronized, the communication
time points in the algorithm are not synchronized either. Suppose that the blocking
mode communication was used to solve the synchronization problem, robots needed
to wait for each other in the step for communication which might also be thought
as a waste of time. In the experiment of [14], the result did not agree with the
algorithm as one robot moved five steps with one unit step length in each step but
another robot moved six steps with one step having two unit step lengths. With
blocking mode communication, these two robots should both go the sixth vertex as
they chose at the same time. Without blocking mode, the one with five steps should
go to the last vertex as it chose earlier. However, neither of these agrees with the
result of the provided experiment. So the experiment may be a fake one. Also, the
experiment did not show the situation to clarify its ambiguous collision avoidance
algorithm. In [132, 131], a Lévy flight algorithm is used to have less repetition than
the RW algorithm. However, the levy flight algorithm of a robot only ensures this
robot has less repetition than using the RW algorithm, but different robots may still
repeat the visited point of other robots. The reason is that robots are independent
and did not communicate the information about the visited area as the choice was
not based on that. Another disadvantage of [132, 131] is that they did not consider
any collision avoidance and the task area has no obstacles. So that algorithm is not
practical and could not be used on real robots.
The explored area of the robot is a known subarea of the task area. Therefore,
graph search algorithms are considered in this chapter. Except for the breadthfirst search algorithm, there are other related graph search algorithms such are A*
algorithm [34, 203], and greedy best first search algorithm. However, these two
algorithms are suitable to the situation for finding the path to a known target
position. In this situation, the greedy best first algorithm estimates the distance to
the target and only needs to explore a small area to find a path while the breadthfirst search calculates the distance to the start point in each direction evenly which
results in a large explored area but the shortest path. A* algorithm estimates the
sum of the estimated values of the two algorithms above, so it has the advantage of
both algorithms, namely smaller explored area, and shortest path. However, in the
problem discussed in this chapter, there may be many unvisited vertices around the
visited area, and the target vertex should be the one with the fewest steps (ds ) to
reach which is unknown. If the A* algorithm is used, it needs to be executed for
each unvisited vertex at the boundary of the explored area which may have repeated
explored parts. Then all paths need to be compared to find the one with the smallest
ds . The breadth-first search algorithm could find the paths to all locations without
repeated exploration and will explore different directions equally and generate the
route after exploration. So it could have less calculation and should be used to
ensure the found path has the smallest ds .

6.1

2D Tasks

This part proposes the third decentralized random search algorithm. It adds the
breadth-first search on the 1st search algorithm to help robots to jump out of the detected zone. The algorithm is compared with five algorithms from other authors and
two search algorithms in previous chapters to show the advantage of this proposed
108

6.1 2D Tasks
algorithm. The convergence of the algorithm is also proved.

6.1.1

Problem Statement

In this section uses a two-dimensional area A with a limited number of static obstacles O1 , O2 ,. . ., Ol . Here, the strict requirement is considered, and the T grid
is used. There are m robots labelled as rob1 to robm to search static targets t1 to
tn . An arbitrary known T grid pattern with a side length of a is used for robots to
move in each step with the following definitions and assumptions. All these initial
settings can be seen in Figure 5.6. The repulsive force is no longer needed, so the
related definitions are not needed either. Further explanation of the definitions and
assumptions below can be seen in Chapter 4.
Assumption 6.1.1. The area A is a bounded, connected and Lebesgue measurable
set. The obstacles Oi are non-overlapping, closed, bounded and linearly connected
sets for any i ≥ 0. Robots have no knowledge about them before exploration.
S
Definition 6.1.1. Let O := Oi for all i > 0. Then Ad := A \ O represents the
area that needs to be detected.
Assumption 6.1.2. The initial condition is that all robots use the same T grid
pattern and the same coordinate system. They start from different vertices near the
boundary which can be seen as the only known entrance of the area.
Assumption 6.1.3. All the ranges and radius in 2D search problems are circular.
Definition 6.1.2. To avoid collisions with other things before move, a safe distance
rsaf e should include both rrob and e (see Figure 2.2). So rsaf e ≥ rrob + e.
Assumption 6.1.4. All passages Wpass between obstacles or between the obstacle
and the boundary are wider than a + 2 ∗ rsaf e . Other Wpass for other grid patterns
can be seen in Table 2.1.
Assumption 6.1.5. The sensing radius for obstacles is rso where rso ≥ a + rsaf e .
Assumption 6.1.6. rst ≥ a + rsaf e .
Assumption 6.1.7. rc ≥ 2 ∗ a + e (see Figure 2.3).
Assumption 6.1.8. The curvature of the concave part of the boundary should be
smaller than or equal to 1/rst .
Va is the set of all the accessible vertices. Ns,i (k) represents the set of sensing
neighbors around robi . In Ns,i (k), Vv,i (k) and Vu,i (k) denote the two sets for visited
vertices and unvisited vertices and the choice from these two sets are cv and cu
respectively.
For the breadth-first search algorithm, the shortest route to the nearest unvisited
vertex is generated.
Definition 6.1.3. The route is represented as a set of vertices Vr,i for robi . Then
|Vr,i (k)| is the total number of steps in that route. Specially, if the route has not
been fully generated, |Vr,i (k)| = 0. Let vr,i (j) be the jth step in the route and cr,i
be the choice from the route Vr,i (k). The number of steps left in the route is then
|Vr,i (k)| − j.
109

6.1 2D Tasks

6.1.2

Procedure and Algorithm

The proposed algorithm drives robots to go through the area through a grid pattern.
If the breadth-first rule is not applied, the general progress in this search algorithm
is the same as the first search algorithm and follow the flow chart in Figure 4.2 and
4.3. However, there are also some differences.
The way to use the breadth-first search for the choice step of robi is described
as follows:
1. Update map: In the turn of robi , it updates its map based on received information
which include the choice from others if robi is not the first to choose in this loop.
2. check obstacles: robi check obstacles in the rso and calculates |Vu,i (k)|.
3. check |Vu,i (k)|: Is there any vacant unvisited neighbor?
3.1 |Vu,i (k)| =
6 0 and select pi (k +1): If |Vu,i (k)| is not 0, there are unvisited vertices
so robi choose one from Vu,i (k) randomly.
3.2 |Vu,i (k)|=0: check |Vv,i (k)|
3.2.1 |Vv,i (k)| = 0 and stay: stay at current position pi (k) as all neighbor vertices
are blocked.
3.2.2 |Vv,i (k)| 6= 0 and set flag: There are no unvisited neighbors and robi is
surrounded by visited neighbors. Thus, the flag bit for whether the route
map is generated or not is set. In the next step, robi will have higher
priority than others with the flag bit being zero. If multiple robots within
rc set their flag bits, they will judge the priority between them according
to the original method which is base on relative positions.
4. Check the old route: robi checks whether there is any previously generated route
map to follow.
4.1 No routes: robi will find a path using the breadth-first search algorithm
4.2 A route is being calculated: robi will continue calculation use the updated map
if it is updated.
4.3 A full route found: robi will check whether the selected vertex to go is still
unvisited or not based on the explored area.
4.2.1 Unvisited: If it is not visited, keep using the route and choose the next
vertex cr,i in the route map.
4.2.2 Visited: robi will redesign a route based on the explored area.
5. The loop for checking visitation states: robi checks the visitation states of the
sensing neighbors of current sensing neighbors. Each checked vertex is saved in a
list with its father node information and the number of steps from pi (k) to it.
5.1 No unvisited vertices: continue the loop and check one step length further until
an unvisited vertex is found. If a vertex is found more than once, only the first
will be recorded as the corresponding path has fewer steps from pi (k).
5.2 Found an unvisited vertex: break the check loop. Then following the father
vertices back, the shortest route Vr,i (k) from pi (k) to the unvisited vertex is
generated.
110

6.1 2D Tasks
6. Check the time for the selection: As the map may be large, the search may cost
a long time. The time for the selection step needs to be checked
6.1 ≤ time for normal selection: robi chooses the next step cr,i based on the route
Vr,i (k).
6.2 >time for normal selection: robi stays at current position pi (k). In the time slot
for the movement, continue its calculation. In the next loop, stop calculation
and do normal things based on the flow chart until it is the turn for robi .
The steps above in red will generate a choice. Mathematically, this can be
concluded as:


6 0,
cu with prob. 1/|Vu,i (k)|, if |Vu,i (k)| =
pi (k + 1) = cr,i , if (|Vu,i (k)| = 0)&((|Vv,i (k)| =
(6.1)
6 0)&(|Vr,i (k)| =
6 0)),


pi (k), if (|Ns,i (k)| = 0) | (|Vr,i (k)| = 0).
The stop strategy for this choosing rule is the same as Chapter 4.
In situation I: pi (k + 1) = pi (k), if |Tki | = |T |.

(6.2)

In situation II: pi (k + 1) = pi (k), if ∀vi ∈ Va , |Vu,i (k)| = 0.

(6.3)

Theorem 6.1.1. Suppose that all the above assumptions hold and the search algorithm 6.1 and a judgment strategy 6.2 or 6.3 are used for situation I or situation
II. Then, for any number of robots, there is such a time k0 > 0 that all targets are
detected with probability 1.
Proof. The algorithm 6.1 with a judgment method forms an absorbing Markov
chain. It includes both transient states and absorbing states. The transient states
are all the approachable vertices of the grid that robots visit but do not stop forever.
Absorbing states are the vertices that the robots stop forever. Applying Algorithm
6.1, robots select the unvisited neighbor vertices to go. If all sensing neighbors are
visited before finding the targets, robots will look for the shortest route to the nearest
unvisited vertex and only stop when all targets are found, or all vertices are detected.
For 6.2, the absorbing state will be reached when robots know |Tki | = |T |. For 6.3,
absorbing states are reached until |Vu,i (k)| = 0 for any vertex. The assumption about
Wpass guarantees that all the accessible vertices can be visited so absorbing states can
be achieved from any initial states, namely with probability 1. This completes the
proof of Theorem 6.1.1

6.1.3

Simulations with the Strict Requirement

Situation I of the proposed algorithm is simulated to verify the algorithm. For
situation I, one to nine targets which are averagely allocated in the area are tested,
and the initial setting is the same as Figure 5.6.
In situation I, an example of the routes of three robots in searching 9 targets
is shown in Figure 6.1-6.4. There are 30*30 vertices in total in the graph. The
three robots are at the bottom right corner which is the only known entrance to
allocate the robots, and the nine targets are labeled as red stars. The boundaries
111

6.1 2D Tasks

Figure 6.1: The route of robot 1 in a simulation with 3 robots
and obstacles are shown by the bold black lines of discrete dots which obey the
Assumption 6.1.4. Parameters used in the simulation are from Table 3.1 based on
the parameters of the Pioneer 3-DX robot. The figures demonstrate that each target
is within rst of a visited vertex, so the search task is finished successfully. Based
on the recorded trace (Figure 6.1-6.3), robots have no collisions with each other so
it is a collision-free algorithm. Also, the routes in Figure 6.4 have less repetition
compared to the Figure 5.4 in Chapter 5 and Figure 4.7 in Chapter 4. The route of
each robot occupied a larger percentage of the area than before which is the benefit
from the breadth-first search algorithm.

6.1.4

Comparison with Other Algorithms

In this section, the third search algorithm is compared with the previous two search
algorithms. It is also compared to the R and RU algorithms in [12] which used
the grid pattern but did not consider collision avoidance clearly. Algorithms in
[193] including RW, LF, and LFP are also compared because they are also random
algorithms in unknown areas with collision avoidance rules. The RUN algorithm in
[12] is not compared as discussed in the previous chapter. Algorithm LF and LFP
use Lévy distribution to generate step length and uniform distribution to generate
the moving direction. The way to generate Lévy distribution can be seen in Section
5.1.4 of Chapter 5
As there is no collision avoidance scheme in R, RU, RW, and LF for collision
between robots. In the simulation, the total number of collisions is counted, and
one more loop is added to the total number of loops for each collision. In reality,
one step may not be enough considering one vertex may be chosen by robots from
all sensing neighbors. So this is a relatively reasonable way to calculate the total
112

6.1 2D Tasks

Figure 6.2: The route of robot 2 in a simulation with 3 robots

Figure 6.3: The route of robot 3 in a simulation with 3 robots

113

6.1 2D Tasks

Figure 6.4: The combined routes in a simulation with 3 robots

114

6.1 2D Tasks

Figure 6.5: All algorithms except R for 1-13 robots
search time.
To compare all methods in the same environment, all the eight algorithms are
simulated in the 900 vertices area with nine targets. The results in the figures are
the average result of at least 100 simulations. Different communication methods are
used in [12] and [193], but all the factors need to be the same. So equation 6.2 is
used as the stop judgment, the ad-hoc mode with rc is used for communication and
the broadcasting mode is chosen for sending positions of found targets in all the
algorithms. [193] claimed that LF and LFP algorithm would perform better when
targets are sparsely and randomly distributed. Therefore, the nine evenly separated
targets are used. Thus, the proposed algorithm is compared to the optimal performance of these two algorithms, and the effectiveness of the proposed algorithm will
be more convincible. Two slowest algorithm R and RW were picked up to another
graph in Figure 5.17 in Chapter 5. So here we draw the other seven algorithms in
Figure 6.5 to see the effect of the proposed algorithm and compare the three search
algorithm in Figure 6.6 to show the small difference.
The Figure 6.5 and 5.17 illustrate that the proposed algorithm 6.1 in situation
I with judgment rule 6.2 is always the best under the strict requirement. If the
algorithms in Chapter 4, 5 and 6 are labeled as S1, S2, and S3. The general ranking
of search time of the eight algorithms is S3<S2<S1< LFP<RU<LF<RW<R. Generally speaking, as the number of robots increased, the search time in all algorithms
decreased drastically at the beginning but slowly later as more time was spent on

115

6.1 2D Tasks

Figure 6.6: Time for 3 search algorithms
other things instead of exploring new vertices only. Specifically, in Algorithm S2
and S1, robots need to spend time on visiting repeated vertices. For the RU and
RW algorithms, robots are set to deal with extra steps caused by collision avoidance.
Algorithm S3 requires robots to spend time on finding the route to leave the area
of repeated vertices. In the LF, the RW, and the LFP algorithm, robots will meet
each other more frequently which will break the generated route and create a new
move to avoid collisions.
Figure 6.6 demonstrate that the second search algorithm only improved the efficiency in a very limited range because robots would not meet each other frequently
especially in a larger area, so the potential field algorithm did not have enough
chance to show its effect. However, the third proposed algorithm largely decreased
the search time to less than half of the second search algorithm due to the breadthfirst search algorithm in reducing repeated visitation. So the proposed algorithm
is effective in Situation I. In Situation II, only the second search algorithm is compared with the third search algorithm in Figure 6.7 as Algorithm S2 is the best in
the seven algorithms to compare. It is clear that Algorithm S3 decreased the search
time significantly and it is the best search algorithm.
In the three search algorithms, the first one is the simplest with calculation like
set operations and generating random numbers. The robot only needs to keep a map
of visited area, so this method is suitable for robots with limited calculation speed
and memory. However, it will spend the longest time. The second algorithm will
add distance calculation on the first one. Nevertheless, it only adds some calculation
for the Euclidean distance when using the repulsive force. The repulsive force only
works when robots are close to each other, so the improvement is small. The third
algorithm needs a considerable amount of calculation especially when the known
map is huge. However, a time-consuming calculation will not affect the normal
116

6.2 3D Tasks

Figure 6.7: Search time for search algorithm 2 and 3
calculation of other robots so it will not change the waiting time of Algorithm
S1. However, a relatively larger waiting time will allow more robots to finish path
planning and move earlier. This algorithm outweighs all other algorithms and needs
to be used on robots with high computation ability and large memory.

6.1.5

Section Summary

This section presented a decentralized random search algorithm with the breadthfirst search algorithm in unknown 2D areas. The movements of robots are synchronized and are based on a grid pattern. When robots have unvisited sensing neighbors
to visit, they choose one from them randomly like the first search algorithm. However, if the surrounding vertices are all searched, the robot will use the breadth-first
search algorithm to find the shortest route to the nearest unvisited area using its
explored map of the area. It is proved that the algorithm converges with probability
1, and the proposed algorithm was compared with seven other related algorithms in
simulations. The result showed that the proposed algorithm is always the best and
it can decrease the search time greatly.

6.2

3D Tasks

This section presents a random search algorithm in 3D with the breadth-first search
algorithm. The control algorithm is decentralized only based on local information
and robots search the area with obstacles via the cubic lattice. The algorithm is the
same as the one in 2D. It considers the collision avoidance as well as real physical
constraints and conditions of all parameters. Therefore, it is a practical algorithm
for real robots. Robots choose vertices in sequence and move between vertices along
edges of the lattice based on local information. The convergence of the algorithm is

117

6.2 3D Tasks
proved, and the effectiveness is shown in the comparison with other fours algorithms
in both situation I and II.

6.2.1

Problem Statement

The problem is the same as that in Chapter 4. So the definitions and assumptions
below are claimed without detailed description.
In the search task, a three-dimensional area A ⊂ R3 with a limited number of
obstacles O1 to Ol is used. m robots labeled as rob1 to robm are used to search
n static targets t1 to tn through a cubic grid with a side length a. pi (k) is the
coordinate of robi at time k. Let T be the set of coordinates of targets and Tki be
the set of coordinates of targets which are known by robi . The initial setting is in
Figure 4.9.
Assumption 6.2.1. Area A is a bounded, connected and Lebesgue measurable set.
The obstacles Oi ⊂ R3 are non-overlapping, closed, bounded and linearly connected
sets for any i > 0. They are both static and unknown to robots.
S
Definition 6.2.1. Let O := Oi for all i > 0. Then Ad := A \ O is the area that
needs to be detected.
Assumption 6.2.2. Initially, all robots have the same grid with the same coordinate
system and are allocated at different vertices along the border of the search area. In
the simulation, robots are manually set at some vertices of the C grid.
Assumption 6.2.3. All sensors and communication equipment that robots carry
have spherical ranges. Other radiuses mentioned are also spherical.
Definition 6.2.2. Robots have a swing radius rrob and a total error e. Then a safety
radius to avoid collision is rsaf e ≥ rrob + e (see Figure 2.11).
√
Assumption 6.2.4. Wpass ≥ a 3 + 2rsaf e (see Figure 2.13).
Assumption 6.2.5. rso ≥ a + rsaf e (see Figure 2.11).
Assumption 6.2.6. rc ≥ 2 ∗ a + e (see Figure 2.11).
√
Assumption 6.2.7. rst ≥ 2a/ 3 + rsaf e − rrob based on Table 2.3.
Assumption 6.2.8. The task area is vast. So, a is much smaller than the length,
the width and the height of area A. Thus, there are no targets between the boundary
and the frontiers of the target sensing range which means the boundary effect can be
ignored.
Va is the set of all the accessible vertices. Ns,i (k) represents the set of sensing
neighbors around robi . In Ns,i (k), Vv,i (k) and Vu,i (k) denote the two sets for visited
vertices and unvisited vertex and the choices from these two sets are cv and cu
respectively.
For the breadth-first search algorithm, the following definitions are used for generating the shortest route to the nearest unvisited vertex.
Definition 6.2.3. The route is represented as a set of vertices Vr,i for robi . Then
|Vr,i (k)| is the total number of steps in that route. Specifically, if the route has not
been fully generated, |Vr,i (k)| = 0. Let vr,i (j) be the jth step in the route and cr,i
be the choice from the route Vr,i (k). The number of steps left in the route is then
|Vr,i (k)| − j.
118

6.2 3D Tasks

6.2.2

Procedure and Algorithm

The general procedure of the algorithm is the same as the 2D algorithm. The
difference is on the dimension of parameters and the way to decide the sequence of
choice which is in Section 4.2.2. So the same flow charts 4.2 and 4.3 are available
for situation I and II. Compared to the first search algorithm, this algorithm helps
robots to escape from a visited area by looking for the route with minimum steps
to the nearest unvisited vertices. The way to use the breadth-first search algorithm
can be seen in Section 6.1.2. The random algorithm with the breadth-first search
algorithm can be summaries as


6 0,
cu with prob. 1/|Vu,i (k)|, if |Vu,i (k)| =
pi (k + 1) = cr,i , if (|Vu,i (k)| = 0)&((|Vv,i (k)| =
6 0)&(|Vr,i (k)| =
6 0)),


pi (k), if (|Ns,i (k)| = 0) | (|Vr,i (k)| = 0)

(6.4)

The stop strategy for this choosing rule is the same as that in Chapter 4.
In situation I: pi (k + 1) = pi (k), if |Tki | = |T |.

(6.5)

In situation II: pi (k + 1) = pi (k), if ∀vi ∈ Va , |Vu,i (k)| = 0.

(6.6)

Theorem 6.2.1. Suppose that all above assumptions hold and the search algorithms
6.1 and a judgment strategy 6.5 or 6.6 are used for situation I or situation II. Then,
for any number of robots, there is such a time k0 > 0 that all targets are detected
with probability 1.
Proof. The algorithm 6.4 with a stop strategy forms an absorbing Markov chain. It
includes both transient states and absorbing states. The transient states are all the
accessible vertices of the grid that robots visit but do not stop. Absorbing states are
the vertices that the robots stop. Applying algorithms 6.4, robots select the unvisited
neighbor vertices to go. If all sensing neighbors are visited before finding the targets,
robots will look for the shortest route to the nearest unvisited vertex and only stop
when all targets are found, or all vertices are detected. For 6.5, absorbing states will
be reached until all robots know |Tki | = |T |. For 6.6, absorbing states are reached
when |Vu,i (k)| = 0 for any vertex. The assumption about Wpass guarantees that all
the accessible vertices can be visited so absorbing states can be achieved from any
initial states, namely with probability 1. This completes the proof of Theorem 6.2.1

6.2.3

Simulation Results

A search task for situation I is simulated in MATLAB2016a. According to the
assumption 6.2.8, targets are allocated within rst from the accessible vertices as in
Figure 4.9. Parameters in Table 3.4 are used, so the time in the movement part of
the simulation is set as 5.75s in total including 4.5s for the translation and 1.25s
for rotation. To check the performance of escaping the searched area from routes,
a small area which has 8*8*8 vertices with nine targets is searched by three robots
using the control law, Algorithm 6.4 and the stop strategy, Algorithm 6.5, as shown
in Figure 6.8 to 6.11. All routes use arrows to show the directions of movements,
119

6.2 3D Tasks

Figure 6.8: The route of robot 1 in a simulation with 3 robots
and the route of each robot has a different color. The figures for individual robot
show that there was no route with many repeated parts and in the combined routes
for the three robots, they tended to search their area without too much overlapping.
This effect is more evident if these fours figures are compared with Figure 5.30-5.33
in Chapter 5. By analyzing the route of each robot, no collisions were found, and
each target was within rst of a visited vertex. So the search task is finished with less
repetition than the second search algorithm.
In situation I, the search algorithm in chapter 4 and 5, namely, Algorithm 4.4 and
5.13 & 5.14 will be compared. Other algorithms include the best algorithm in [193]
which is the LFP algorithm and the RU algorithm in [170]. Collisions avoidance is
not stated clearly in RU, so it is assumed that it accepts collision and one collision
needs one more movement to solve although longer time may be needed if there
are consecutive collisions or if multiple robots choose the same vertex from different
directions.
Simulations for searching nine separated targets in a larger area (12*12*12 vertices) by 1 to 13 robots are run for 500 times to get the average search time. Based
on the simulation in a 3D area in Chapter 5, the search time for LFP algorithm
is always much larger than the others because no map can be used to assist the
search. As the proposed algorithm should be faster than other algorithms, LFP is
compared with RU only in Table 5.4 as a reference. So other three algorithms are
compared with the third search algorithm in Figure 6.12 to make the line graph
clear. Given by the figure, the proposed algorithm was always the best in all these
five algorithms. Although the algorithm TU outperformed the other two search algorithm for 1 to 6 robots because of its simplicity, the wide range of choice and few
collisions happened, it still had repeated routes, so it was slower than the proposed
algorithm in this chapter. However, comparing to the simulation results in a 2D

120

6.2 3D Tasks

Figure 6.9: The route of robot 2 in a simulation with 3 robots

Figure 6.10: The route of robot 3 in a simulation with 3 robots

121

6.2 3D Tasks

Figure 6.11: The combined routes in a simulation with 3 robots

122

6.2 3D Tasks

Figure 6.12: Compare 4 algorithms in situation I
area, the advantage of the proposed algorithm was not that clear. The possible reason is that, although the 3D area has a larger number of vertices than the 2D area
(12*12*12 VS. 30*30). The fewest number of steps needed to go across the body
diagonal of the cube is (12-1)*3=33 steps. Nevertheless, for the 2D area using a T
grid, the number of steps for going through the diagonal is (30-1)+(30-1)/2=43.5
steps, which is larger than that of the C grid. For the breadth-first search algorithm,
it means the total breadth of the 3D grid is smaller, so the effect of going out of a
large visited area is less significant.
For situation II, robots need to have a map to know when all parts of the area are
searched. Therefore, algorithms RW, LF, and LFP which do not need map cannot
be used. So algorithm R and RU are compared with the three proposed search
algorithms in this report. In the result, the search time for algorithm R is too long,
so the two slow algorithms are illustrated in Table 6.1. Algorithms except algorithm
R are displayed in Figure 6.13. The table and figure display that the third search
algorithm was the best, and its search time was less than half of the second best
search algorithm. Unlike situation I, situation II needed more steps. Thus, there
were more chances to utilize the breadth-first search algorithm to boost the search
speed.
The general trend of all the algorithms is that the search time had a dramatic

123

6.2 3D Tasks

Figure 6.13: Compare 4 algorithms in situation II

No.

1

2

3

4

5

6

7

R

79447

47067

32892

24373

19840

16840

13227

RU

24036

13584

8689

6445

5606

4334

4032

No.

8

9

10

11

12

13

R

12459

11321

10957

10748

8492

8791

RU

3562

3094

2825

2694

2547

2182

Table 6.1: Search time for algorithm R and RU in situation II

124

6.3 Summary
drop followed by a gentle descent as the number of robots increased. It can be
predicted that if the number of robots increases further, the search time of the
proposed algorithm may have a stable period or even a moderate rise because the
algorithm time in the ‘wait’ step will increase which may take up a larger proportion
of total time. Also, the number of steps will decrease slower. Therefore, when
choosing the suitable number of robots in applications, the balance between the
merits of decreased search time and the increased expense on robots should be
considered. The search time is also affected by unknown factors including the initial
positions of robots and the shape and the size of the area. If the size of the area is
given, simulations like those in this paper can be used to estimate the proper rough
range of the number of robots in a general situation.

6.2.4

Section Summary

This section proposed a grid-based decentralized algorithm for search task in 3D
area without collision. The algorithm uses a combination of random choice and
the breadth-first search algorithm to decrease the amount of repeated visitation.
The convergence of the algorithm is proved, and it is compared to all the related
algorithms in both situation I and situation II. The result showed that the proposed
algorithm is always the best in different situations.

6.3

Summary

This chapter proposed the third search algorithm for mobile robots which is suitable
for both 2D and 3D areas with small differences in the dimension of parameters and
the setting of the selection sequence. When a robot has unvisited neighbors to visit,
it uses the random algorithm to select an unvisited one like the first and second
search algorithms. When the robot is in a visited section, the breadth-first search
algorithm is employed to find the nearest unvisited vertex referring to the number of
steps. Then it plans a path for the robot to go to the unvisited vertice thus reducing
the repetition and search time. Robots move via a grid pattern to select vertices in
sequence and avoid collisions in the unknown area. In both 2D and 3D area, the
proposed algorithm was compared with all other related algorithms and showed that
the proposed algorithm in this chapter is the best in different situations.

125

Chapter 7
Conclusion
This report studied the problems of complete coverage and search by a team of
robots with collision avoidance. The task area in these two problems is arbitrary
and unknown with obstacles inside. One optimal decentralized complete coverage
algorithm and three decentralized random based search algorithms were proposed.
All algorithms are suitable for both 2D and 3D areas and utilized a grid pattern
to simplify the representation of the area and calculation. In each step, the robot
moves between vertices along edges of the grid with limitations on sensing ranges
and the communication range. Robots are always within the task area and do not
need to go through the boundary. All robots are synchronized so the robot failure
can be detected. With the sequence, the grid pattern and communication, collisions
are avoided while robots are making choices. Chapter 2 illustrated how to select the
grid with the minimum number of vertices to cover an area based on parameters
of robots. Tables with selection criteria are provided with examples of real robots.
Using the selected grid, multiple mobile robotic sensors can employ the optimal
self-deployment algorithm in Chapter 3 to have a complete coverage of a static or
expanding area. If the robots are fed into certain points of the area continuously
when the vertices are vacant, the algorithm which drives robots to the furthest available vertices will ensure the least number of feeding steps are needed. Then, Chapter
4, 5 and 6 proposed three decentralized random algorithms for search tasks. In the
search problem, the number of targets can be known or unknown, and a sequence of
selection is given based on the relative positions of robots. The first search algorithm
chooses a random unvisited neighbor to go if there is any. Otherwise, it randomly
selects a visited vertex. If no accessible neighbors are available, it keeps stable in
that step. In the second algorithm, the repulsive force is used on the robots which
are close to each other to disperse robots to move to different areas. Thus, there will
be less repeated vertices. In the third algorithm, the repetition is further descended
by adding the breadth-first search algorithm when a robot is surrounded by visited
vertices. The shortest route is planned to the nearest unvisited vertices based on
the explored map of the robot.
In Chapter 5, the second search algorithm was further discussed with an example
of generating the formula for search time based on the size of the area and the number
of robots. For the coverage with the loose requirement, factors related to the search
time were discussed based on simulations and analyses. The convergence of each
algorithm was proved with probability one, and they are simulated in MATLAB
to discover their features and compared to other related algorithms to show the

126

7.1 Future Work
effectiveness. Experiments on Pioneer 3-DX robots were used to test the second
search algorithm which verified the algorithm.

7.1

Future Work

1. In the initialization of the algorithms, robots need to be manually set to vertices of grids or robots have a reference point to build its coordinate system and
grid. Based on some consensus problems without collision avoidance [11, 170],
future works should consider finding an autonomous collision-free method for
multiple robots to form the same coordinate system.
2. The breadth-first search algorithm in Chapter 6 uses a considerable amount of
time, memory and energy. As robots need to be cheap with limited resource,
other graph search algorithms should be developed.
3. The obstacle in this report is static which limits the usage of the proposed algorithms. So another research direction could be developing a collision avoidance
search algorithm with moving or deforming obstacles [121, 78, 173, 118, 114,
174, 175]. Thus, the algorithm will not be limited to the ‘wait and choose’
scheme.
4. This report is restricted to the case of static targets. However, when the
targets are moving, the proposed algorithms may not be the best. So search
problems for moving targets like those in [132, 131] need to be considered.
5. The 3D algorithms in this report are not tested on real robots. Therefore,
experiments on UUVs or UAVs are required to verify the algorithms.
6. Formation control of multiple robots is also a related interesting area. A
possible topic can be adding collision avoidance to the formation control in 3D
areas based on [176, 177, 13].
7. With formation control algorithms, the sweep coverage or patrolling in a region
with changing width could be considered as in [43, 111, 178].
8. The odometry error and other errors should be discussed further. As the simulation and experiment environments were not large enough and the odometry
error is related to the distance traveled, the current error did not affect the result seriously. However, in applications in a vast area, that may be a problem.
A possible direction may be adding some buoyage for some UUV applications.
9. In this report, all robots have the same ability. However, in real search and
rescue tasks, a robot team consists of robots with different functions. Thus,
cooperation between heterogeneous robots will be a realistic research topic
[183, 76, 35, 110].
10. The communication in the proposed algorithms is ideal, however, in real environments such as a battlefield, there may be interference and limitations to
the bandwidth. Thus communication delay or data loss could be considered
with estimation of certain information [172, 146, 143].

127

7.1 Future Work
11. The movement of the robots in the algorithm is based on the ability of the
Pioneer 3-DX robot. However, some robots may not have the capability to
turn a particular angle while staying at the same position. Therefore, the
non-holonomic model in [103, 120, 165] and the dynamics of vehicles in a 3D
area (see, e.g., [48]) should be researched.

128

Bibliography
[1] N. Adde. Locust swarm. Sea Power, 58(4):51–53, 2015.
[2] K. Akkaya and A. Newell. Self-deployment of sensors for maximized coverage in underwater acoustic sensor networks. Computer Communications,
32(7):1233–1244, 2009.
[3] S. Alam and Z. J. Haas. Coverage and connectivity in three-dimensional underwater sensor networks. Wireless Communications and Mobile Computing,
8(8):995–1009, 2008.
[4] S. N. Alam and Z. J. Haas. Coverage and connectivity in three-dimensional
networks with random node deployment. Ad Hoc Networks, 34:157–169, 2015.
[5] A. I. N. Alshbatat. Behavior-based approach for the detection of land mines
utilizing off the shelf low cost autonomous robot. IAES International Journal
of Robotics and Automation, 2(3):83, 2013.
[6] B. D. Anderson, C. Yu, B. Fidan, and J. M. Hendrickx. Control and information architectures for formations. In IEEE International Conference on
Control Applications, pages 1127–1138. IEEE, 2006.
[7] F. Aurenhammer. Voronoi diagramsa survey of a fundamental geometric data
structure. ACM Computing Surveys (CSUR), 23(3):345–405, 1991.
[8] X. Bai, S. Kumar, D. Xuan, Z. Yun, and T. H. Lai. Deploying wireless sensors
to achieve both coverage and connectivity. In Proceedings of the 7th ACM
international symposium on Mobile ad hoc networking and computing, pages
131–142. ACM, 2006.
[9] A. Bar-Noy, T. Brown, M. P. Johnson, and O. Liu. Cheap or flexible sensor
coverage. In DCOSS, pages 245–258. Springer, 2009.
[10] A. Baranzadeh and A. V. Savkin. A distributed algorithm for grid-based search
by a multi-robot system. In 2015 10th Asian Control Conference (ASCC),
pages 1–6, 2015.
[11] A. Baranzadeh. A decentralized control algorithm for target search by a multirobot team. In Australasian Conference on Robotics and Automation, 2013.
[12] A. Baranzadeh. Decentralized autonomous navigation strategies for multirobot search and rescue. arXiv preprint arXiv:1605.04368, 2016.

129

BIBLIOGRAPHY
[13] A. Baranzadeh and V. Nazarzehi. A decentralized formation building algorithm with obstacle avoidance for multi-robot systems. In Robotics and
Biomimetics (ROBIO), 2015 IEEE International Conference on, pages 2513–
2518. IEEE, 2015.
[14] A. Baranzadeh and A. V. Savkin. A distributed control algorithm for area
search by a multi-robot team. Robotica, 35(6):1452–1472, 2017.
[15] S. Barr, B. Liu, and J. Wang. Underwater sensor barriers with auction algorithms. In Computer Communications and Networks, 2009. ICCCN 2009.
Proceedings of 18th Internatonal Conference on, pages 1–6. IEEE, 2009.
[16] S. Barr, J. Wang, and B. Liu. An efficient method for constructing underwater
sensor barriers. Journal of Communications, 6(5):370–383, 2011.
[17] M. A. Batalin and G. Sukhatme. The analysis of an efficient algorithm for
robot coverage and exploration based on sensor network deployment. In Proceedings of the IEEE International Conference on Robotics and Automation,
pages 3478–3485. IEEE, 2005.
[18] J. L. Baxter, E. Burke, J. M. Garibaldi, and M. Norman. Multi-robot search
and rescue: A potential field based approach, pages 9–16. Springer, 2007.
[19] S. Benhamou. How many animals really do the Lévy walk?
88(8):1962–1969, 2007.

Ecology,

[20] C. Berger. Toward rich geometric map for slam: online detection of planes in
2D lidar. Journal of Automation Mobile Robotics and Intelligent Systems, 7,
2013.
[21] Bluefin
Robotics.
Maritime-Bluefin-21-UUV-01-3.
https:
//gdmissionsystems.com/-/media/General-Dynamics/Bluefin/
PDF/Maritime-Bluefin-21-UUV-01-3.ashx?la=en&hash=
B1073240AF49EDBF95FE624F97AA6C16F7863472, 2017. [Online; accessed
20-August-2017].
[22] A. Boukerche and X. Fei. A coverage-preserving scheme for wireless sensor
network with irregular sensing range. Ad Hoc Networks, 5(8):1303–1316, 2007.
[23] A. Breitenmoser and A. Martinoli. On combining multi-robot coverage and
reciprocal collision avoidance, pages 49–64. Springer Japan, Tokyo, 2016.
[24] A. Brooks, A. Makarenko, T. Kaupp, S. Williams, and H. Durrant-Whyte.
Implementation of an indoor active sensor network. Experimental Robotics
IX, pages 397–406, 2006.
[25] W. Burgard, M. Moors, D. Fox, R. Simmons, and S. Thrun. Collaborative
multi-robot exploration. In Proceedings of the IEEE International Conference
on Robotics and Automation, volume 1, pages 476–481. IEEE, 2000.
[26] Z. J. Butler. Distributed coverage of rectilinear environments. Thesis, Robotics
Institute, 2000.
130

BIBLIOGRAPHY
[27] L. Cai, A. P. Espinosa, D. Pranantha, and A. D. Gloria. Multi-robot search
and rescue team. In 2011 IEEE International Symposium on Safety, Security,
and Rescue Robotics, pages 296–301, 2011.
[28] Y. Cai and S. X. Yang. An improved pso-based approach with dynamic parameter tuning for cooperative multi-robot target searching in complex unknown
environments. International Journal of Control, 86(10):1720–1732, 2013.
[29] D. Calitoiu. New search algorithm for randomly located objects: A noncooperative agent based approach. In 2009 IEEE Symposium on Computational Intelligence for Security and Defense Applications, pages 1–6, 2009.
[30] D. W. Casbeer, R. W. Beard, T. W. McLain, S.-M. Li, and R. K. Mehra. Forest
fire monitoring with multiple small uavs. In American Control Conference,
2005. Proceedings of the 2005, pages 3530–3535. IEEE, 2005.
[31] R. Cassinis, G. Bianco, A. Cavagnini, and P. Ransenigo. Strategies for navigation of robot swarms to be used in landmines detection. In Advanced Mobile
Robots, 1999. (Eurobot ’99) 1999 Third European Workshop on, pages 211–
218, 1999.
[32] R. Cassinis, G. Bianco, A. Cavagi, and W. Ransenigo. Landmines detection
methods using swarms of simple robots. In Proceedings of the 6th International
Conference on Intelligent Autonomous Systems, pages 212–218, 2000.
[33] Ö. Çayırpunar Ömer, V. Gazi, B. Tavlı, U. Witkowski, and J. Penders. Experimental study on the effects of communication on cooperative search in
complex environments. In Y. Baudoin and M. Habib, editors, Using robots in
hazardous environments, pages 535–557. Woodhead Publishing, Oxford, December 2010.
[34] P. Chand and D. A. Carnegie. A two-tiered global path planning strategy for
limited memory mobile robots. Robotics and Autonomous Systems, 60(2):309–
321, 2012.
[35] P. Chand and D. A. Carnegie. Mapping and exploration in a hierarchical
heterogeneous multi-robot system using limited capability robots. Robotics
and autonomous Systems, 61(6):565–579, 2013.
[36] C. T. Chang, C. Y. Chang, S. Zhao, J. C. Chen, and T. L. Wang. Sra: A
sensing radius adaptation mechanism for maximizing network lifetime in wsns.
IEEE Transactions on Vehicular Technology, 65(12):9817–9833, Dec 2016.
[37] C. Y. Chang, C. T. Chang, Y. C. Chen, and H. R. Chang. Obstacle-resistant
deployment algorithms for wireless sensor networks. IEEE Transactions on
Vehicular Technology, 58(6):2925–2941, 2009.
[38] L. Chang-Yong and Y. Xin. Evolutionary programming using mutations based
on the Lévy probability distribution. IEEE Transactions on Evolutionary
Computation, 8(1):1–13, 2004.

131

BIBLIOGRAPHY
[39] T. M. Cheng and A. V. Savkin. A distributed self-deployment algorithm for the
coverage of mobile wireless sensor networks. IEEE Communications Letters,
13(11):877–879, 2009.
[40] T. M. Cheng and A. V. Savkin. Decentralized control for mobile robotic sensor
network self-deployment: Barrier and sweep coverage problems. Robotica,
29(2):283–294, 2011.
[41] T. M. Cheng and A. V. Savkin. Self-deployment of mobile robotic sensor
networks for multilevel barrier coverage. Robotica, 30(04):661–669, 2012.
[42] T. M. Cheng and A. V. Savkin. Decentralized control of mobile sensor networks
for asymptotically optimal blanket coverage between two boundaries. IEEE
Transactions on Industrial Informatics, 9(1):365–376, 2013.
[43] T. M. Cheng, A. V. Savkin, and F. Javed. Decentralized control of a group
of mobile robots for deployment in sweep coverage. Robotics and Autonomous
Systems, 59(7):497–507, 2011.
[44] M. ChinnaDurai, S. MohanKumar, and S. Sharmila. Underwater wireless
sensor networks. Compusoft, 4(7):1899, 2015.
[45] K. Choi, S. Yoo, J. Park, and Y. Choi. Adaptive formation control in absence
of leader’s velocity information. IET Control Theory & Applications, 4(4):521–
528, 2010.
[46] R. Cipolleschi, M. Giusto, A. Q. Li, and F. Amigoni. Semantically-informed
coordinated multirobot exploration of relevant areas in search and rescue settings. In Mobile Robots (ECMR), 2013 European Conference on, pages 216–
221. IEEE, 2013.
[47] J. Clark and R. Fierro. Cooperative hybrid control of robotic sensors for
perimeter detection and tracking. In American Control Conference, 2005.
Proceedings of the 2005, pages 3500–3505. IEEE, 2005.
[48] L. Consolini, F. Morbidi, D. Prattichizzo, and M. Tosques. On a class of hierarchical formations of unicycles and their internal dynamics. IEEE Transactions
on Automatic Control, 57(4):845–859, 2012.
[49] J. Corts and F. Bullo. Coordination and geometric optimization via distributed
dynamical systems. SIAM Journal on Control and Optimization, 44(5):1543–
1574, 2005.
[50] D. Culler and J. Long. A prototype smart materials warehouse application
implemented using custom mobile robots and open source vision technology
developed using emgucv. Procedia Manufacturing, 5:1092–1106, 2016.
[51] A. Datta and S. Soundaralakshmi. On-line path planning in an unknown
polygonal environment. Information Sciences, 164(1):89–111, 2004.
[52] D. Dedousis and V. Kalogeraki. Complete coverage path planning for arbitrary number of unmanned aerial vehicles. In Proceedings of the 9th ACM
International Conference on PErvasive Technologies Related to Assistive Environments, page 5, Corfu, Island, Greece, 2016. ACM.
132

BIBLIOGRAPHY
[53] M. Defoort, T. Floquet, A. Kokosy, and W. Perruquetti. Sliding-mode formation control for cooperative autonomous mobile robots. IEEE Transactions
on Industrial Electronics, 55(11):3944–3953, 2008.
[54] B. Donald, P. Xavier, J. Canny, and J. Reif. Kinodynamic motion planning.
Journal of the ACM (JACM), 40(5):1048–1066, 1993.
[55] H. Dong, K. Zhang, and L. Zhu. An algorithm of 3D directional sensor network coverage enhancing based on artificial fish-swarm optimization. In The
2012 International Workshop on Microwave and Millimeter Wave Circuits and
System Technology, pages 1–4, 2012.
[56] X. Du, H. Li, and W. Li. A new coverage algorithm for directional movement
wireless sensor networks. In 2015 4th International Conference on Computer
Science and Network Technology (ICCSNT), volume 01, pages 1194–1199,
2015.
[57] A. Fagiolini, M. Pellinacci, G. Valenti, G. Dini, and A. Bicchi. Consensusbased distributed intrusion detection for multi-robot systems. In 2008
IEEE International Conference on Robotics and Automation, pages 120–127,
Pasadena, CA, USA, 2008.
[58] G. Flierl, D. Grnbaum, S. Levins, and D. Olson. From individuals to aggregations: the interplay between behavior and physics. Journal of Theoretical
Biology, 196(4):397–454, 1999.
[59] D. Fox, W. Burgard, H. Kruppa, and S. Thrun. A probabilistic approach
to collaborative multi-robot localization. Autonomous Robots, 8(3):325–344,
2000.
[60] D. Fox, W. Burgard, and S. Thrun. The dynamic window approach to collision
avoidance. IEEE Robotics & Automation Magazine, 4(1):23–33, 1997.
[61] A. Fujimori, M. Teramoto, P. N. Nikiforuk, and M. M. Gupta. Cooperative
collision avoidance between multiple mobile robots. Journal of Robotic Systems, 17(7):347–363, 2000.
[62] D. W. Gage. Command control for many-robot systems. Report, DTIC Document, 1992.
[63] M. Ghaemi, Z. Zabihinpour, and Y. Asgari. Computer simulation study of
the Lévy flight process. Physica A: Statistical Mechanics and its Applications,
388(8):1509–1514, 2009.
[64] A. Ghosh and S. K. Das. Coverage and connectivity issues in wireless sensor
networks. Mobile, Wireless, and Sensor Networks: Technology, Applications,
and Future Directions, pages 221–256, 2006.
[65] Y. Gu, D. Bozda, R. W. Brewer, and E. Ekici. Data harvesting with mobile
elements in wireless sensor networks. Computer Networks, 50(17):3449–3465,
2006.

133

BIBLIOGRAPHY
[66] M. Guarnieri, R. Kurazume, H. Masuda, T. Inoh, K. Takita, P. Debenest, R.
Hodoshima, E. Fukushima, and S. Hirose. Helios system: A team of tracked
robots for special urban search and rescue operations. In 2009 IEEE/RSJ
International Conference on Intelligent Robots and Systems, pages 2795–2800,
2009.
[67] J. Guo, Z. Lin, M. Cao, and G. Yan. Adaptive leader-follower formation control
for autonomous mobile robots. In American Control Conference (ACC), 2010,
pages 6822–6827. IEEE, 2010.
[68] T. C. Hales. A proof of the kepler conjecture.
162(3):1065–1185, 2005.

Annals of mathematics,

[69] T. C. Hales. A proof of the kepler conjecture.
162(3):1065–1185, 2005.

Annals of mathematics,

[70] I. A. Hameed. Motion planning for autonomous landmine detection and clearance robots. In Recent Advances in Robotics and Sensor Technology for Humanitarian Demining and Counter-IEDs (RST), International Workshop on,
pages 1–5. IEEE, 2016.
[71] J. M. Hereford and M. A. Siebold. Bio-inspired search strategies for robot
swarms. In Swarm Robotics from Biology to Robotics. InTech, 2010.
[72] J. Hess, M. Beinhofer, and W. Burgard. A probabilistic approach to highconfidence cleaning guarantees for low-cost cleaning robots. In 2014 IEEE
International Conference on Robotics and Automation (ICRA), pages 5600–
5605, Hong Kong, China, 2014.
[73] G. M. Hoffmann and C. J. Tomlin. Decentralized cooperative collision avoidance for acceleration constrained vehicles. In 47th IEEE Conference on Decision and Control, pages 4357–4363. IEEE, 2008.
[74] Y. Hong, J. Hu, and L. Gao. Tracking control for multi-agent consensus with
an active leader and variable topology. Automatica, 42(7):1177–1182, 2006.
[75] S. P. Hou and C. C. Cheah. Dynamic compound shape control of robot swarm.
IET Control Theory & Applications, 6(3):454–460, 2012.
[76] A. Howard, L. E. Parker, and G. S. Sukhatme. Experiments with a large
heterogeneous mobile robot team: Exploration, mapping, deployment and
detection. The International Journal of Robotics Research, 25(5-6):431–447,
2006.
[77] M. Hoy, A. S. Matveev, and A. V. Savkin. Collision free cooperative navigation
of multiple wheeled robots in unknown cluttered environments. Robotics and
Autonomous Systems, 60(10):1253–1266, 2012.
[78] M. Hoy, A. S. Matveev, and A. V. Savkin. Algorithms for collision-free navigation of mobile robots in complex cluttered environments: a survey. Robotica,
33(03):463–497, 2015.

134

BIBLIOGRAPHY
[79] C. F. Huang, Y. C. Tseng, and L. C. Lo. The coverage problem in threedimensional wireless sensor networks. Journal of Interconnection Networks,
8(03):209–227, 2007.
[80] M. Ishizuka and M. Aida. Performance study of node placement in sensor
networks. In Distributed Computing Systems Workshops, 2004. Proceedings.
24th International Conference on, pages 598–603. IEEE, 2004.
[81] A. Ismail, M. Elmogy, and H. ElBakry. Landmines detection using low-cost
multisensory mobile robot. Journal of Convergence Information Technology,
10(6):51, 2015.
[82] A. Jadbabaie, L. Jie, and A. S. Morse. Coordination of groups of mobile
autonomous agents using nearest neighbor rules. IEEE Transactions on Automatic Control, 48(6):988–1001, 2003.
[83] P. Jalalkamali. Distributed Tracking and Information-Driven Control for Mobile Sensor Networks. Dartmouth College, 2013.
[84] P. Jeongyeup, K. Chintalapudi, R. Govindan, J. Caffrey, and S. Masri. A
wireless sensor network for structural health monitoring: Performance and
experience. In The Second IEEE Workshop on Embedded Networked Sensors,
2005. EmNetS-II., pages 1–10, 2005.
[85] M. Keeter, D. Moore, R. Muller, E. Nieters, J. Flenner, S. E. Martonosi, A. L.
Bertozzi, A. G. Percus, and R. Lévy. Cooperative search with autonomous
vehicles in a 3D aquatic testbed. In American Control Conference (ACC),
2012, pages 3154–3160. IEEE, 2012.
[86] N. Kelland. Deep-water black box retrieval. Hydro International, 13(9), 2009.
[87] R. Kershner. The number of circles covering a set. American Journal of
Mathematics, pages 665–671, 1939.
[88] K. K. Khedo, R. Perseedoss, and A. Mungur. A wireless sensor network air
pollution monitoring system. arXiv preprint arXiv:1005.1737, 2010.
[89] A. Kim and R. M. Eustice. Active visual slam for robotic area coverage:
Theory and experiment. The International Journal of Robotics Research, 34(45):457–475, 2015.
[90] N. Y. Ko and R. G. Simmons. The lane-curvature method for local obstacle avoidance. In Proceedings of the IEEE/RSJ International Conference on
Intelligent Robots and Systems, volume 3, pages 1615–1621. IEEE, 1998.
[91] T. Krajnı́k, V. Vonásek, D. Fišer, and J. Faigl. AR-Drone as a Platform for
Robotic Research and Education, pages 172–186. Springer Berlin Heidelberg,
Berlin, Heidelberg, 2011.
[92] L. Krick, M. E. Broucke, and B. A. Francis. Stabilisation of infinitesimally
rigid formations of multi-robot networks. International Journal of Control,
82(3):423–439, 2009.
135

BIBLIOGRAPHY
[93] L. Krishnamurthy, R. Adler, P. Buonadonna, J. Chhabra, M. Flanigan, N.
Kushalnagar, L. Nachman, and M. Yarvis. Design and deployment of industrial sensor networks: experiences from a semiconductor plant and the north
sea. In Proceedings of the 3rd international conference on Embedded networked
sensor systems, pages 64–75. ACM, 2005.
[94] S. Kumar, N. H. Thach, and E. Suzuki. Understanding the behaviour
of reactive robots in a patrol task by analysing their trajectories. In
IEEE/WIC/ACM International Conference on Web Intelligence and Intelligent Agent Technology (WI-IAT), volume 2, pages 56–63, Toronto, ON,
Canada, 2010. IEEE.
[95] K. Lenac, A. Kitanov, I. Maurovi, M. Dakulovi, and I. Petrovi. Fast active
SLAM for accurate and complete coverage mapping of unknown environments,
pages 415–428. Springer, 2016.
[96] J. Li. The benefit of being physically present: A survey of experimental works
comparing copresent robots, telepresent robots and virtual agents. International Journal of Human-Computer Studies, 77:23–37, 2015.
[97] X. Liang and Y. Xiao. Studying bio-inspired coalition formation of robots for
detecting intrusions using game theory. IEEE Transactions on Systems, Man,
and Cybernetics, Part B (Cybernetics), 40(3):683–693, 2010.
[98] K. W. Lin, M. H. Hsieh, and V. S. Tseng. A novel prediction-based strategy
for object tracking in sensor networks by mining seamless temporal movement
patterns. Expert Systems with Applications, 37(4):2799–2807, 2010.
[99] B. Liu, O. Dousse, P. Nain, and D. Towsley. Dynamic coverage of mobile
sensor networks. IEEE Transactions on Parallel and Distributed Systems,
24(2):301–311, 2013.
[100] X. Liu, P. Zhang, and G. Du. Hybrid adaptive impedance-leader-follower
control for multi-arm coordination manipulators. Industrial Robot: An International Journal, 43(1):112–120, 2016.
[101] Z. Lu, T. Pitchford, W. Li, and W. Wu. On the maximum directional target
coverage problem in wireless sensor networks. In Mobile Ad-hoc and Sensor
Networks (MSN), 2014 10th International Conference on, pages 74–79. IEEE,
2014.
[102] V. Malyavej and A. V. Savkin. The problem of optimal robust Kalman state
estimation via limited capacity digital communication channels. Systems &
Control Letters, 54(3):283–292, 2005.
[103] I. R. Manchester and A. V. Savkin. Circular-navigation-guidance law for precision missile/target engagements. Journal of Guidance, Control, and Dynamics, 29(2):314–320, 2006.
[104] O. Manolov, B. Iske, S. Noykov, J. Klahold, G. Georgiev, U. Witkowski, and U.
Rückert. Gard - an intelligent system for distributed exploration of landmine

136

BIBLIOGRAPHY
fields simulated by a team of khepera robots. In Proceedings of the International Conference Automatics and Informatics03, volume 1, pages 199–202,
Sofia, Bulgaria, 6 - 8 October 2003.
[105] T. Manzoor, A. Munawar, and A. Muhammad. Visual servoing of a sensor
arm for mine detection robot marwa. In Robotics; Proceedings of ROBOTIK
2012; 7th German Conference on, pages 1–6. VDE, 2012.
[106] D. Marinakis and G. Dudek. Pure topological mapping in mobile robotics.
IEEE Transactions on Robotics, 26(6):1051–1064, 2010.
[107] A. Marjovi and L. Marques. Multi-robot olfactory search in structured environments. Robotics and Autonomous Systems, 59(11):867–881, 2011.
[108] A. Marjovi, J. G. Nunes, L. Marques, and A. de Almeida. Multi-robot exploration and fire searching. In Intelligent Robots and Systems, 2009. IROS
2009. IEEE/RSJ International Conference on, pages 1929–1934. IEEE, 2009.
[109] A. A. Masoud. A harmonic potential approach for simultaneous planning and
control of a generic uav platform. Journal of Intelligent & Robotic Systems,
65(1):153–173, 2012.
[110] A. Matos, A. Martins, A. Dias, B. Ferreira, J. M. Almeida, H. Ferreira, G.
Amaral, A. Figueiredo, R. Almeida, and F. Silva. Multiple robot operations
for maritime search and rescue in eurathlon 2015 competition. In OCEANS
2016 - Shanghai, pages 1–7, 2016.
[111] A. S. Matveev, K. S. Ovchinnikov, and A. V. Savkin. Reactive navigation of
a nonholonomic mobile robot for autonomous sweep coverage of a surface embedded in a 3D workspace. In 2016 35th Chinese Control Conference (CCC),
pages 8914–8919, 2016.
[112] A. S. Matveev and A. V. Savkin. The problem of state estimation via asynchronous communication channels with irregular transmission times. IEEE
Transactions on Automatic Control, 48(4):670–676, April 2003.
[113] A. S. Matveev and A. V. Savkin. The problem of LQG optimal control
via a limited capacity communication channel. Systems and Control Letters,
53(1):51–64, 2004.
[114] A. S. Matveev, M. C. Hoy, and A. V. Savkin. A globally converging algorithm for reactive robot navigation among moving and deforming obstacles.
Automatica, 54(Supplement C):292–304, 2015.
[115] A. S. Matveev and A. V. Savkin. Qualitative theory of hybrid dynamical systems. Control engineering Birkhäuser. Birkhäuser, Boston, 2000.
[116] A. S. Matveev and A. V. Savkin. An analogue of Shannon information theory for detection and stabilization via noisy discrete communication channels.
SIAM Journal on Control and Optimization, 46(4):1323–1367, 2007.
[117] A. S. Matveev and A. V. Savkin. Estimation and Control over Communication
Networks. Boston : Birkhäuser Boston, 2009.
137

BIBLIOGRAPHY
[118] A. S. Matveev, A. V. Savkin, M. Hoy, and C. Wang, editors. Safe Robot
Navigation Among Moving and Steady Obstacles. Elsevier, January 2015.
[119] A. S. Matveev, H. Teimoori, and A. V. Savkin. A method for guidance and
control of an autonomous vehicle in problems of border patrolling and obstacle
avoidance. Automatica, 47(3):515–524, 2011.
[120] A. S. Matveev, H. Teimoori, and A. V. Savkin. Navigation of a unicycle-like
mobile robot for environmental extremum seeking. Automatica, 47(1):85–91,
2011.
[121] A. S. Matveev, C. Wang, and A. V. Savkin. Real-time navigation of mobile
robots in problems of border patrolling and avoiding collisions with moving
and deforming obstacles. Robotics and Autonomous Systems, 60(6):769–788,
2012.
[122] H. Mehrjerdi, J. Ghommam, and M. Saad. Nonlinear coordination control for
a group of mobile robots using a virtual structure. Mechatronics, 21(7):1147–
1155, 2011.
[123] H. Mohamadi, S. Salleh, and M. N. Razali. Heuristic methods to maximize
network lifetime in directional sensor networks with adjustable sensing ranges.
Journal of Network and Computer Applications, 46:26–35, 2014.
[124] F. Mohseni, A. Doustmohammadi, and M. B. Menhaj. Distributed model
predictive coverage control for decoupled mobile robots. Robotica, 35(4):922–
941, 2015.
[125] L. Moreau. Leaderless coordination via bidirectional and unidirectional timedependent communication. In Proceedings of the 42nd IEEE Conference on
Decision and Control, volume 3, pages 3070–3075. IEEE, 2003.
[126] S. C. Nagavarapu, L. Vachhani, and A. Sinha. Multi-robot graph exploration
and map building with collision avoidance: A decentralized approach. Journal
of Intelligent & Robotic Systems, 83(3-4):503–523, 2016.
[127] H. Najjaran and A. A. Goldenberg. Landmine detection using an autonomous
terrain-scanning robot. Industrial Robot: An International Journal, 32(3):240–
247, 2005.
[128] V. Nazarzehi and A. V. Savkin. Decentralized control of mobile threedimensional sensor networks for complete coverage self-deployment and forming specific shapes. In 2015 IEEE Conference on Control Applications (CCA),
pages 127–132, 2015.
[129] V. Nazarzehi, A. V. Savkin, and A. Baranzadeh. Distributed 3D dynamic
search coverage for mobile wireless sensor networks. IEEE Communications
Letters, 19(4):633–636, 2015.
[130] V. Nazarzehi. Decentralized control of three-dimensional mobile robotic sensor
networks. arXiv preprint arXiv:1606.00122, 2016.

138

BIBLIOGRAPHY
[131] V. Nazarzehi and A. Baranzadeh. A decentralized grid-based random search
algorithm for locating targets in three dimensional environments by a mobile
robotic network. In Australasian Conference on Robotics and Automation.
ACRA2015, 2015.
[132] V. Nazarzehi and A. Baranzadeh. A distributed bio-inspired algorithm for
search of moving targets in three dimensional spaces. In 2015 IEEE International Conference on Robotics and Biomimetics (ROBIO), pages 2507–2512,
Zhuhai, China, 2015. IEEE.
[133] V. Nazarzehi and A. V. Savkin. Distributed self-deployment of mobile wireless
3D robotic sensor networks for complete sensing coverage and forming specific
shapes. Robotica, pages 1–18, 2017.
[134] J. D. Nicoud and M. K. Habib. The pemex-b autonomous demining robot:
perception and navigation strategies. In Proceedings of the 1995 IEEE/RSJ
International Conference on Intelligent Robots and Systems 95.’Human Robot
Interaction and Cooperative Robots, volume 1, pages 419–424, Pittsburgh,
USA, 1995. IEEE.
[135] S. G. Nurzaman, Y. Matsumoto, Y. Nakamura, S. Koizumi, and H. Ishiguro.
Yuragi-based adaptive searching behavior in mobile robot: From bacterial
chemotaxis to Lévy walk. In Robotics and Biomimetics, 2008. ROBIO 2008.
IEEE International Conference on, pages 806–811. IEEE, 2008.
[136] S. G. Nurzaman, Y. Matsumoto, Y. Nakamura, S. Koizumi, and H. Ishiguro.
Biologically inspired adaptive mobile robot search with and without gradient
sensing. In Intelligent Robots and Systems, 2009. IROS 2009. IEEE/RSJ
International Conference on, pages 142–147. IEEE, 2009.
[137] P. Ögren, M. Egerstedt, and X. Hu. A control lyapunov function approach
to multi-agent coordination. In Proceedings of the 40th IEEE Conference on
Decision and Control, volume 2, pages 1150–1155. IEEE, 2001.
[138] P. Ögren, E. Fiorelli, and N. E. Leonard. Cooperative control of mobile sensor
networks: Adaptive gradient climbing in a distributed environment. IEEE
Transactions on Automatic Control, 49(8):1292–1302, 2004.
[139] A. Okubo. Dynamical aspects of animal grouping: swarms, schools, flocks,
and herds. Advances in biophysics, 22:1–94, 1986.
[140] R. Olfati-Saber and R. M. Murray. Consensus problems in networks of agents
with switching topology and time-delays. IEEE Transactions on Automatic
Control, 49(9):1520–1533, 2004.
[141] Parklayer. Multilevel car parking products. http://www.parklayer.com/
multilevel-car-parking-products.html#!prettyPhoto, 2017. [Online;
accessed 20-August-2017].
[142] K. Pathak and S. K. Agrawal. Planning and control of a nonholonomic unicycle
using ring shaped local potential fields. In American Control Conference, 2004.
Proceedings of the 2004, volume 3, pages 2368–2373. IEEE, 2004.
139

BIBLIOGRAPHY
[143] P. N. Pathirana, N. Bulusu, A. V. Savkin, and S. Jha. Node localization using
mobile robots in delay-tolerant sensor networks. IEEE transactions on Mobile
Computing, 4(3):285–296, 2005.
[144] J. Peng and S. Akella. Coordinating multiple robots with kinodynamic constraints along specified paths. The International Journal of Robotics Research,
24(4):295–310, 2005.
[145] H. I. A. Perez-Imaz, P. A. F. Rezeck, D. G. Macharet, and M. F. M. Campos. Multi-robot 3D coverage path planning for first responders teams. In
2016 IEEE International Conference on Automation Science and Engineering
(CASE), pages 1374–1379, 2016.
[146] I. R. Petersen and A. V. Savkin. Robust Kalman filtering for signals and
systems with large uncertainties. Springer Science & Business Media, 1999.
[147] I. Petersen, V. Ugrinovskii, and A. Savkin. Robust control design using H∞
methods. Communications and control engineering series. Springer, London,
2000.
[148] V. A. Petrushin, G. Wei, O. Shakil, D. Roqueiro, and V. Gershman. Multiplesensor indoor surveillance system. In Computer and Robot Vision, 2006. The
3rd Canadian Conference on, pages 40–40. IEEE, 2006.
[149] M. Plank and A. James. Optimal foraging: Lévy pattern or process? Journal
of The Royal Society Interface, 5(26):1077–1086, 2008.
[150] D. Pompili, T. Melodia, and I. F. Akyildiz. Three-dimensional and twodimensional deployment analysis for underwater acoustic sensor networks. Ad
Hoc Networks, 7(4):778–790, 2009.
[151] D. Portugal and R. Rocha. A Survey on Multi-robot Patrolling Algorithms,
pages 139–146. Springer Berlin Heidelberg, Berlin, Heidelberg, 2011.
[152] A. Prorok, A. Bahr, and A. Martinoli. Low-cost collaborative localization for
large-scale multi-robot systems. In 2012 IEEE International Conference on
Robotics and Automation, pages 4236–4241, Saint Paul, MN, USA, 2012.
[153] Y. Qu and S. V. Georgakopoulos. A distributed area coverage algorithm for
maintenance of randomly distributed sensors with adjustable sensing range. In
Global Communications Conference (GLOBECOM), 2013 IEEE, pages 286–
291. IEEE, 2013.
[154] R. L. Raffard, C. J. Tomlin, and S. P. Boyd. Distributed optimization for
cooperative agents: Application to formation flight. In 43rd IEEE Conference
on Decision and Control, volume 3, pages 2453–2459. IEEE, 2004.
[155] M. Raibert, K. Blankespoor, G. Nelson, and R. Playter. Bigdog, the roughterrain quadruped robot. IFAC Proceedings Volumes, 41(2):10822–10825,
2008.

140

BIBLIOGRAPHY
[156] T. S. Rappaport. Wireless communications : principles and practice. Upper
Saddle River, N.J. : Prentice Hall PTR, Upper Saddle River, N.J., 2nd ed.
edition, 2002.
[157] Raytheon. COYOTE UAS. http://www.raytheon.com/capabilities/
products/coyote/, 2017. [Online; accessed 20-August-2017].
[158] J. Ren, K. A. McIsaac, and R. V. Patel. Modified newton’s method applied
to potential field-based navigation for nonholonomic robots in dynamic environments. Robotica, 26(1):117–127, 2008.
[159] C. W. Reynolds. Flocks, herds and schools: A distributed behavioral model.
ACM SIGGRAPH Computer Graphics, 21(4):25–34, 1987.
[160] X. Rong, Y. Li, J. Ruan, and B. Li. Design and simulation for a hydraulic
actuated quadruped robot. Journal of Mechanical Science and Technology,
26(4):1171–1177, 2012.
[161] S. I. Roumeliotis and G. A. Bekey. Distributed multirobot localization. IEEE
Transactions on Robotics and Automation, 18(5):781–795, 2002.
[162] L. V. Santana, A. S. Brandao, M. Sarcinelli-Filho, and R. Carelli. A trajectory tracking and 3D positioning controller for the ar. drone quadrotor.
In Unmanned Aircraft Systems (ICUAS), 2014 International Conference on,
pages 756–767. IEEE, 2014.
[163] A. V. Savkin. Coordinated collective motion of groups of autonomous mobile
robots: analysis of Vicsek’s model. IEEE Transactions on Automatic Control,
49(6):981–982, 2004.
[164] A. V. Savkin and F. Javed. A method for decentralized self-deployment of
a mobile sensor network with given regular geometric patterns. In 2011 Seventh International Conference on Intelligent Sensors, Sensor Networks and
Information Processing, pages 371–376, 2011.
[165] A. V. Savkin and H. Li. Collision free navigation of a non-holonomic ground
robot for search and building maps of unknown areas with obstacles. In 2016
35th Chinese Control Conference (CCC), pages 5409–5414, 2016.
[166] A. V. Savkin and C. Wang. A simple real-time algorithm for safe navigation
of a non-holonomic robot in complex unknown environments with moving
obstacles. In 2014 European Control Conference (ECC), pages 1875–1880,
June 2014.
[167] A. V. Savkin. Analysis and synthesis of networked control systems: Topological entropy, observability, robustness and optimal control. Automatica,
42(1):51–62, 2006.
[168] A. V. Savkin, T. M. Cheng, Z. Xi, F. Javed, A. S. Matveev, and H. Nguyen.
Decentralized coverage control problems for mobile robotic sensor and actuator
networks. John Wiley & Sons, 2015.

141

BIBLIOGRAPHY
[169] A. V. Savkin and R. J. Evans. Hybrid dynamical systems: controller and
sensor switching problems. Control engineering Birkhäuser. Springer Science
& Business Media, Boston, 2002.
[170] A. V. Savkin, F. Javed, and A. S. Matveev. Optimal distributed blanket coverage self-deployment of mobile wireless sensor networks. IEEE Communications
Letters, 16(6):949–951, 2012.
[171] A. V. Savkin and I. R. Petersen. Model validation for robust control of uncertain systems with an integral quadratic constraint. Automatica, 32(4):603–606,
1996.
[172] A. V. Savkin and I. R. Petersen. Robust state estimation and model validation
for discrete-time uncertain systems with a deterministic description of noise
and uncertainty. Automatica, 34(2):271–274, 1998.
[173] A. V. Savkin and C. Wang. A simple biologically inspired algorithm for
collision-free navigation of a unicycle-like robot in dynamic environments with
moving obstacles. Robotica, 31(6):993–1001, 2013.
[174] A. V. Savkin and C. Wang. Seeking a path through the crowd: Robot navigation in unknown dynamic environments with moving obstacles based on an
integrated environment representation. Robotics and Autonomous Systems,
62(10):1568–1580, 2014.
[175] A. V. Savkin and C. Wang. A framework for safe assisted navigation of semiautonomous vehicles among moving and steady obstacles. Robotica, 35(5):981–
1005, 2016.
[176] A. V. Savkin, C. Wang, A. Baranzadeh, Z. Xi, and H. T. Nguyen. A method
for decentralized formation building for unicycle-like mobile robots. In 9th
Asian Control Conference (ASCC), pages 1–5. IEEE, 2013.
[177] A. V. Savkin, C. Wang, A. Baranzadeh, Z. Xi, and H. T. Nguyen. Distributed
formation building algorithms for groups of wheeled mobile robots. Robotics
and Autonomous Systems, 75, Part B:463–474, 2016.
[178] A. A. Semakova, K. S. Ovchinnikov, and A. S. Matveev. Self-deployment
of mobile robotic networks: an algorithm for decentralized sweep boundary
coverage. Robotica, 35(9):1816–1844, 2017.
[179] V. Sharma, R. Patel, H. Bhadauria, and D. Prasad. Deployment schemes in
wireless sensor network to achieve blanket coverage in large-scale open area:
A review. Egyptian Informatics Journal, 17(1):45–56, 2016.
[180] E. Shaw. The development of schooling in fishes. ii. Physiological Zoology,
pages 263–272, 1961.
[181] R. Siegwart, I. R. Nourbakhsh, and D. Scaramuzza. Introduction to autonomous mobile robots. MIT press, 2011.

142

BIBLIOGRAPHY
[182] T. R. Smith, H. Hanmann, and N. E. Leonard. Orientation control of multiple
underwater vehicles with symmetry-breaking potentials. In Proceedings of the
40th IEEE Conference on Decision and Control, volume 5, pages 4598–4603.
IEEE, 2001.
[183] C. Song, L. Liu, G. Feng, and S. Xu. Coverage control for heterogeneous
mobile sensor networks on a circle. Automatica, 63:349–358, 2016.
[184] Y. Song, B. Wang, Z. Shi, K. R. Pattipati, and S. Gupta. Distributed algorithms for energy-efficient even self-deployment in mobile sensor networks.
IEEE Transactions on Mobile Computing, 13(5):1035–1047, 2014.
[185] D. W. Stephens and J. R. Krebs. Foraging theory. Princeton University Press,
1986.
[186] T. Stevens and T. H. Chung. Autonomous search and counter-targeting using Lévy search models. In Robotics and Automation (ICRA), 2013 IEEE
International Conference on, pages 3953–3960. IEEE, 2013.
[187] D. M. Stipanovi, P. F. Hokayem, M. W. Spong, and D. D. iljak. Cooperative avoidance control for multiagent systems. Journal of Dynamic Systems,
Measurement, and Control, 129(5):699–707, 2007.
[188] T. Stirling, S. Wischmann, and D. Floreano. Energy-efficient indoor search by
swarms of simulated flying robots without global information. Swarm Intelligence, 4(2):117–143, 2010.
[189] H. Sugiyama, T. Tsujioka, and M. Murata. Autonomous chain network formation by multi-robot rescue system with ad hoc networking. In 2010 IEEE
Safety Security and Rescue Robotics, pages 1–6, 2010.
[190] H. Sugiyama, T. Tsujioka, and M. Murata. Real-time exploration of a multirobot rescue system in disaster areas. Advanced Robotics, 27(17):1313–1323,
2013.
[191] S. Susca, F. Bullo, and S. Martinez. Monitoring environmental boundaries
with a robotic sensor network. IEEE Transactions on Control Systems Technology, 16(2):288–296, 2008.
[192] D. Sutantyo, P. Levi, C. Mslinger, and M. Read. Collective-adaptive Lévy
flight for underwater multi-robot exploration. In Mechatronics and Automation (ICMA), 2013 IEEE International Conference on, pages 456–462. IEEE,
2013.
[193] D. K. Sutantyo, S. Kernbach, P. Levi, and V. A. Nepomnyashchikh. Multirobot searching algorithm using Lévy flight and artificial potential field. In
Safety Security and Rescue Robotics (SSRR), 2010 IEEE International Workshop on, pages 1–6. IEEE, 2010.
[194] Y. C. Tan. Synthesis of a controller for swarming robots performing underwater mine countermeasures. Technical report, Naval Academy Annapolis Md,
2004.
143

BIBLIOGRAPHY
[195] J. Tang, B. Hao, and A. Sen. Relay node placement in large scale wireless
sensor networks. Computer communications, 29(4):490–501, 2006.
[196] H. G. Tanner, A. Jadbabaie, and G. J. Pappas. Stability of flocking motion.
Report, University of Pennsylvania, 2003.
[197] H. G. Tanner, A. Jadbabaie, and G. J. Pappas. Stable flocking of mobile
agents part i: dynamic topology. In Proceedings of the 42nd IEEE Conference
on Decision and Control, volume 2, pages 2016–2021. IEEE, 2003.
[198] H. G. Tanner, A. Jadbabaie, and G. J. Pappas. Stable flocking of mobile
agents, part i: Fixed topology. In Proceedings of the 42nd IEEE Conference
on Decision and Control, volume 2, pages 2010–2015. IEEE, 2003.
[199] D. Tao, S. Tang, and L. Liu. Constrained artificial fish-swarm based area
coverage optimization algorithm for directional sensor networks. In 2013 IEEE
10th International Conference on Mobile Ad-Hoc and Sensor Systems, pages
304–309, 2013.
[200] W. S. Thomson. On the division of space with minimum partitional area. Acta
mathematica, 11(1-4):121–134, 1887.
[201] M. Vaccarini and S. Longhi. Formation control of marine veihicles via real-time
networked decentralized mpc. In 17th Mediterranean Conference on Control
and Automation, pages 428–433. IEEE, 2009.
[202] J. Van Den Berg, S. J. Guy, M. Lin, and D. Manocha. Reciprocal n-body
collision avoidance, pages 3–19. Springer, 2011.
[203] H. H. Viet, V. H. Dang, M. N. U. Laskar, and T. Chung. BA*: an online complete coverage algorithm for cleaning robots. Applied Intelligence,
39(2):217–235, 2013.
[204] G. M. Viswanathan, S. V. Buldyrev, S. Havlin, M. Da Luz, E. Raposo,
and H. E. Stanley. Optimizing the success of random searches. Nature,
401(6756):911–914, 1999.
[205] G. Viswanathan, F. Bartumeus, S. V. Buldyrev, J. Catalan, U. Fulco, S.
Havlin, M. Da Luz, M. Lyra, E. Raposo, and H. E. Stanley. Lévy flight
random searches in biological phenomena. Physica A: Statistical Mechanics
and Its Applications, 314(1):208–213, 2002.
[206] I. Škrjanc and G. Klančar. Optimal cooperative collision avoidance between
multiple robots based on bernstein-bd́zier curves. Robotics and Autonomous
systems, 58(1):1–9, 2010.
[207] B. Wang. Coverage problems in sensor networks: A survey. ACM Computing
Surveys (CSUR), 43(4):32, 2011.
[208] C. Wang, A. V. Savkin, and M. Garratt. Collision free navigation of flying
robots among moving obstacles. In 2016 35th Chinese Control Conference
(CCC), pages 4545–4549, Chengdu, China, 2016.
144

BIBLIOGRAPHY
[209] Q. Wang and Y. P. Tian. Minimally rigid formations control for multiple
nonholonomic mobile agents. In Proceedings of the 31st Chinese Control Conference, pages 6171–6176, 2012.
[210] Y. Wang, Y. Liu, and Z. Guo. Three-dimensional ocean sensor networks: A
survey. Journal of Ocean University of China (English Edition), 11(4):436–
450, 2012.
[211] Y. Wang, R. Tan, G. Xing, X. Tan, J. Wang, and R. Zhou. Spatiotemporal
aquatic field reconstruction using robotic sensor swarm. In Real-Time Systems
Symposium (RTSS), 2012 IEEE 33rd, pages 205–214. IEEE, 2012.
[212] Y. Wang, X. Wang, B. Xie, D. Wang, and D. P. Agrawal. Intrusion detection in
homogeneous and heterogeneous wireless sensor networks. IEEE transactions
on mobile computing, 7(6):698–711, 2008.
[213] Z. Wang and B. Wang. A novel node sinking algorithm for 3D coverage and
connectivity in underwater sensor networks. Ad Hoc Networks, 56:43–55, 2016.
[214] J. Wawerla and R. T. Vaughan. A fast and frugal method for team-task allocation in a multi-robot transportation system. In Robotics and Automation
(ICRA), 2010 IEEE International Conference on, pages 1432–1437, Anchorage, AK, USA, 2010. IEEE.
[215] S. C. Wong and B. A. MacDonald. A topological coverage algorithm for mobile
robots. In Proceedings of the 2003 IEEE/RSJ International Conference on
Intelligent Robots and Systems, volume 2, pages 1685–1690. IEEE, 2003.
[216] Y. Xiang, Z. Xuan, M. Tang, J. Zhang, and M. Sun. 3D space detection and
coverage of wireless sensor network based on spatial correlation. Journal of
Network and Computer Applications, 61:93–101, 2016.
[217] M. A. Yakoubi and M. T. Laskri. The path planning of cleaner robot for
coverage region using genetic algorithms. Journal of Innovation in Digital
Ecosystems, 3(1):37–43, 2016.
[218] M. Yamashita, H. Umemoto, I. Suzuki, and T. Kameda. Searching for mobile
intruders in a polygonal region by a group of mobile searchers. Algorithmica,
31(2):208–236, 2001.
[219] Z. Yan, N. Jouandeau, and A. A. Cherif. A survey and analysis of multi-robot
coordination. International Journal of Advanced Robotic Systems, 10(12):399,
2013.
[220] B. Yang, Y. Ding, Y. Jin, and K. Hao. Self-organized swarm robot for target search and trapping inspired by bacterial chemotaxis. Robotics and Autonomous Systems, 72:83–92, 2015.
[221] X. Yang. A decentralized collision-free search algorithm in 3D area for multiple
robots. In 2017 36th Chinese Control Conference (CCC), pages 8107–8112,
2017.

145

BIBLIOGRAPHY
[222] X. Yang. Grid based 2D navigation by a decentralized robot system with
collison avoidance. In 2017 36th Chinese Control Conference (CCC), pages
8473–8478, 2017.
[223] X. Yang. A decentralized algorithm for collision free navigation of multiple
robots in search tasks. In 2016 35th Chinese Control Conference (CCC), pages
8096–8101, 2016.
[224] X. Yang. A collision-free self-deployment of mobile robotic sensors for threedimensional distributed blanket coverage control. accepted, 2017.
[225] X. Yang. A decentralized algorithm for multiple robots in collision-free search
tasks. submitted, 2017.
[226] X. Yang. Optimal distributed self-deployment of multiple mobile robotic sensors with collision avoidance for blanket coverage. submitted, 2017.
[227] X. S. Yang and S. Deb. Cuckoo search via Lévy flights. In Nature & Biologically
Inspired Computing, 2009. NaBIC 2009. World Congress on, pages 210–214.
IEEE, 2009.
[228] M. Younis and K. Akkaya. Strategies and techniques for node placement in
wireless sensor networks: A survey. Ad Hoc Networks, 6(4):621–655, 2008.
[229] K. Zheng, G. Chen, G. Cui, Y. Chen, F. Wu, and X. Chen. Performance
Metrics for Coverage of Cleaning Robots with MoCap System, pages 267–274.
Springer International Publishing, Cham, 2017.
[230] X. Zheng, S. Jain, S. Koenig, and D. Kempe. Multi-robot forest coverage. In
IEEE/RSJ International Conference on Intelligent Robots and Systems, pages
3852–3857. IEEE, 2005.
[231] C. Zhu, C. Zheng, L. Shu, and G. Han. A survey on coverage and connectivity issues in wireless sensor networks. Journal of Network and Computer
Applications, 35(2):619–632, 2012.
[232] Q. Zhu, A. Liang, and H. Guan. A pso-inspired multi-robot search algorithm
independent of global information. In IEEE Symposium on Swarm Intelligence, pages 1–7. IEEE, 2011.

146

Appendix A
Acronyms
2D

two-dimensional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

3D

three-dimensional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

C

cubic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

DOF

Degrees of Freedom . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

DR

decenalized random . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

GPS

Global Positioning System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

H

regular hexagonal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

HP

hexagonal prismatic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

LF

Lévy flight . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

LFP

Lévy flight with potential field . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86

R

random choice. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .86

RD

rhombic dodecahedral . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

RU

random choice with unvisited vertices first . . . . . . . . . . . . . . . . . . . . . 86

RUN

random choice with path to the nearest unvisited vertex . . . . . . . 86

RW

random walk . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86

S

square . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

SLAM

Simultaneous Localization And Mapping . . . . . . . . . . . . . . . . . . . . . . . 8

T

equilateral triangular . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

TCP

Transmission Control Protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

TO

truncated octahedral . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

UAV

Unmanned Aerial Vehicle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

UGV

Unmanned Ground Vehicle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

UUV

Unmanned Underwater Vehicle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

WMSN

Wireless Mobile Sensor Network . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

147

