-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathtemplate.loc
126 lines (126 loc) · 19.1 KB
/
template.loc
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
\contentsline {added}{Added: \truncate {\Changestruncatewidth }{Coverage path planning (CPP) of multiple Dubins robots has been extensively applied in aerial monitoring, marine exploration, and search and rescue.}}{1}{section*.1}%
\contentsline {added}{Added: \truncate {\Changestruncatewidth }{Dubins}}{1}{section*.2}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{of known environments}}{1}{section*.3}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{exact Dubins MCPP (EDM)}}{1}{section*.4}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{based on}}{1}{section*.5}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{ searches the entire solution space to obtain the shortest Dubins coverage path.}}{1}{section*.6}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{credit-based Dubins MCPP (CDM)}}{1}{section*.7}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{EDM}}{1}{section*.8}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{CDM}}{1}{section*.9}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{EDM}}{1}{section*.10}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{CDM}}{1}{section*.11}%
\contentsline {added}{Added: \truncate {\Changestruncatewidth }{As one subproblem of robot path planning,}}{1}{section*.12}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{aims to determine}}{1}{section*.13}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{CPP is common to several applications, including}}{1}{section*.14}%
\contentsline {added}{Added: \truncate {\Changestruncatewidth }{Due to the limited sensing range, calculating speed, and energy supply, many practical coverage applications cannot be achieved by a single robot \cite {chen2021clustering}. Thus, a series of multi-robot CPP (MCPP) algorithms have been proposed to improve coverage efficiency and enhance robustness. Meanwhile, MCPP faces the challenges of algorithmic complexity and logistical management \cite {c16}.}}{1}{section*.15}%
\contentsline {deleted}{Deleted: \truncate {\Changestruncatewidth }{ The CPP problem's complexity depends on factors such as the complexity of the environments, and the kinematic constraints of robots \cite {lewis2017semi}. In general, a robot with nonholonomic constraints is more challenging to plan than one with holonomic constraints \cite {wang2017curvature}, and an obstacle-constrained environment is more involved in planning than one without obstacles \cite {c2}.}}{1}{section*.16}%
\contentsline {added}{Added: \truncate {\Changestruncatewidth }{Real-world MCPP applications, such as aerial monitoring \cite {coombes2019flight}, marine exploration\cite {wilson2019novel}, and automatic farming \cite {maini2022online}\cite {c11}, typically involve multiple aerial (fixed-wing aircraft), ground (wheel robots), and autonomous underwater/surface vehicles. These vehicles are typically governed by the Dubins vehicle model \cite {dubins1957curves}, which allows them to move at a fixed speed and turn with a limited turning radius. As the foundation of many practical applications, MCPP oriented to Dubins robots (Dubins MCPP) has received growing attention in recent years. Thus, this paper focuses on the Dubins MCPP problem of known environments.}}{2}{section*.17}%
\contentsline {deleted}{Deleted: \truncate {\Changestruncatewidth }{Utilizing multiple robots can reduce coverage time and increase robustness \cite {munoz2021multi}. However, multi-robot CPP (}}{2}{section*.18}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{Dubins MCPP}}{2}{section*.19}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{Dubins MCPP (EDM)}}{2}{section*.20}%
\contentsline {deleted}{Deleted: \truncate {\Changestruncatewidth }{ multi-robot}}{2}{section*.21}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{(CDM)}}{2}{section*.22}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{CDM}}{2}{section*.23}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{EDM}}{2}{section*.24}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{CDM}}{2}{section*.25}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{EDM}}{2}{section*.26}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{based on MILP, which provides the shortest Dubins coverage path by searching the entire solution space.}}{2}{section*.27}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{CDM}}{2}{section*.28}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{EDM}}{2}{section*.29}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{CDM}}{2}{section*.30}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{EDM}}{2}{section*.31}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{CDM}}{2}{section*.32}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{Dubins MCPP}}{2}{section*.33}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{EDM}}{2}{section*.34}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{CDM}}{2}{section*.35}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{EDM}}{2}{section*.36}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{CDM}}{2}{section*.37}%
\contentsline {added}{Added: \truncate {\Changestruncatewidth }{Some exact algorithms precisely divide the region into $K$ partitions and apply a single-robot coverage algorithm to each partition.}}{3}{section*.38}%
\contentsline {deleted}{Deleted: \truncate {\Changestruncatewidth }{\cite {chlebikova1996approximating} proves that $BCP_q$ is NP-hard and proposes a polynomial-time algorithm that solves $BCP_2$ within an approximation ratio of $\frac {4}{3}$. \cite {matic2014mixed} proposes an accurate MILP for two robots, which can solve graphs of 70 nodes within two hours. However, the MILP is difficult to extend to cases with $q \geq 3$. The work }}{3}{section*.39}%
\contentsline {added}{Added: \truncate {\Changestruncatewidth }{the $MinMax$ balanced and connected $q$-partition problem (}}{3}{section*.40}%
\contentsline {added}{Added: \truncate {\Changestruncatewidth }{)}}{3}{section*.41}%
\contentsline {added}{Added: \truncate {\Changestruncatewidth }{Other exact works build exact formations based on MILP to generate the shortest or fastest paths.}}{3}{section*.42}%
\contentsline {added}{Added: \truncate {\Changestruncatewidth }{\cite {chen2021clustering}\cite {yu2020balanced} produces the fastest coverage paths by building exact formulations. However, both works calculate the coverage time of a given region based on the scanning area rather than the coverage path. In fact, the coverage time of a given region depends on the time to cover the scanning area and the time to perform turns. Since turns are often costly for mobile robots, neglecting the cost of turns usually reduces the efficiency \cite {vandermeulen2019turn}. In order to minimize the cost of turns, the work \cite {yu2015optimization} divides the region into cells and represents cells as a graph. The Dubins MCPP problem is formulated with the graph representation as a generalized traversal salesman problem (TSP). The exact coverage path is then obtained by applying the GTSP solver. Unfortunately, the work \cite {yu2015optimization} is only applicable to a single robot.}}{3}{section*.43}%
\contentsline {deleted}{Deleted: \truncate {\Changestruncatewidth }{proposed an exact formulation to address the coverage problem for scattered regions. This formulation model MCPP as a $MinMax$ problem for balancing robot coverage times. However, this formulation does not apply to practical coverage applications since it does not consider robot kinetics. Several works models the optimal coverage problem as the $MinMax$ balanced and connected $q$-partition problem ($BCP_q$) and present various methods to resolve it.}}{3}{section*.44}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{Dubins MCPP}}{4}{section*.45}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{Dubins MCPP}}{5}{section*.47}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{Dubins MCPP}}{5}{section*.49}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{Dubins MCPP}}{6}{section*.50}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{Dubins MCPP}}{6}{section*.51}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{EDM}}{6}{section*.52}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{CDM}}{6}{section*.53}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{The EDM algorithm}}{6}{section*.54}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{proposes an exact formation based on MILP. The MILP solver is used to produce the optimal Dubins coverage path by thoroughly searching the solution space.}}{6}{section*.55}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{The CDM algorithm}}{6}{section*.56}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{EDM}}{6}{section*.57}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{CDM}}{6}{section*.58}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{Dubin Multi-robot CPP (EDM)}}{6}{section*.59}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{either provide an accurate partition or produce coverage paths without considering the turning cost of the robot covering a given region, resulting in a non-optimal coverage path. This paper presents an EDM algorithm to plan coverage paths. The EDM algorithm consists of two steps: graph representation and build MILP. The former step is to calculate the Dubins paths for covering coverage cells and turning from one cell to another. All Dubins paths will be represented as a connected graph. The latter step generates an exact formulation based on MILP to obtain the shortest Dubins coverage path.}}{6}{section*.60}%
\contentsline {added}{Added: \truncate {\Changestruncatewidth }{Classical offline coverage methods decompose the region into cells and represent cells into a graph \cite {c16}. With the graph representation, the MCPP problem is transformed into TSP or Chinest Postman Problem to obtain the fastest or shortest path \cite {yu2015optimization}\cite {c46}. As most offline MCPP methods do, the EDM algorithm divides the mission environment}}{6}{section*.61}%
\contentsline {deleted}{Deleted: \truncate {\Changestruncatewidth }{As mentioned before, the mission environment has been divided}}{6}{section*.62}%
\contentsline {added}{Added: \truncate {\Changestruncatewidth }{Different from the graph presented in \cite {yu2015optimization}\cite {c46}\cite {c16}, $E$ consists of the Dubins paths for the robot turning and covering the cell.}}{6}{section*.63}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{EDM}}{7}{section*.66}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{EDM}}{8}{section*.67}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{EDM}}{8}{section*.68}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{EDM}}{8}{section*.69}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{EDM}}{8}{section*.70}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{Dubin Multi-robot CPP(CDM)}}{8}{section*.71}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{EDM}}{8}{section*.72}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{CDM}}{8}{section*.73}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{\ref {Fig_6}}}{10}{section*.77}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{\ref {Fig_7}}}{10}{section*.78}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{CDM}}{10}{section*.79}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{CDM}}{11}{section*.81}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{CDM}}{11}{section*.82}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{CDM}}{12}{section*.83}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{EDM}}{12}{section*.84}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{CDM}}{12}{section*.85}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{EDM}}{12}{section*.86}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{CDM}}{12}{section*.87}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{EDM}}{12}{section*.88}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{EDM}}{12}{section*.90}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{CDM}}{12}{section*.91}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{EDM}}{12}{section*.101}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{CDM}}{12}{section*.102}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{Milpflow and CDM produce relatively concentrated paths for every robot since they allocate a set of connected coverage cells to every robot. In contrast to Milpflow and CDM, EDM and DCRC generate the single-robot coverage path that is not limited in a particular area.}}{12}{section*.103}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{EDM}}{12}{section*.104}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{CDM}}{12}{section*.105}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{The comparison results show that, compared with heuristic DCRC and CDM, Milpflow and EDM provide fewer coverage times by thoroughly searching the solution space. Furthermore, EDM produces the least coverage times in all scenes because it generates the optimal Dubins coverage path rather than the area division provided by Milpflow.}}{12}{section*.106}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{EDM}}{13}{section*.93}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{CDM}}{13}{section*.94}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{EDM}}{13}{section*.96}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{CDM}}{13}{section*.97}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{EDM}}{14}{section*.99}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{CDM}}{14}{section*.100}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{EDM}}{14}{section*.107}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{CDM}}{14}{section*.108}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{CDM}}{14}{section*.110}%
\contentsline {added}{Added: \truncate {\Changestruncatewidth }{Fig.\ref {Fig_9a} and \ref {Fig_9b} demonstrate snapshots of coverage paths generated by DCRC and CDM for 3 and 6 robots, respectively. These snapshots show that the CDM algorithm provides a set of connected cells for every robot, while a single robot's coverage cells in DCRC may be disconnected. Paths between disconnected cells probably revisit the covered area, which increases the coverage time. Indeed, as illustrated in Fig.\ref {Fig_9c}, the CDM algorithm provides fewer coverage times than DCRC in most experiments.}}{14}{section*.111}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{CDM}}{14}{section*.112}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{CDM}}{14}{section*.113}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{CDM}}{14}{section*.114}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{CDM}}{14}{section*.115}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{CDM}}{14}{section*.116}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{CDM}}{14}{section*.117}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{CDM}}{14}{section*.118}%
\contentsline {deleted}{Deleted: \truncate {\Changestruncatewidth }{Fig.\ref {Fig_9a} and \ref {Fig_9b} demonstrate snapshots of coverage paths generated by DCRC and \replaced {CDM}{CMD} for 3 and 6 robots, respectively. DCRC divides the single-robot optimal route into $K$ subpaths, each corresponding to a robot. As shown in the first row of Fig.\ref {Fig_9a} and \ref {Fig_9b}, crossings between subpaths occur in DCRC. In contrast, \replaced {CDM}{CMD} divides the map into $K$ subareas and employs the single-robot Dubins solver \cite {c25} for each subarea. Thus, each robot's coverage path is clustered within its subarea.}}{14}{section*.119}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{CDM}}{15}{section*.123}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{CDM}}{15}{section*.125}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{EDM}}{16}{section*.126}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{CDM}}{16}{section*.127}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{EDM}}{16}{section*.128}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{CDM}}{16}{section*.129}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{EDM}}{16}{section*.130}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{CDM}}{16}{section*.131}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{EDM}}{16}{section*.132}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{CDM}}{16}{section*.133}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{EDM}}{16}{section*.135}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{CDM}}{16}{section*.137}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{EDM}}{16}{section*.138}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{CDM}}{16}{section*.139}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{Dubins MCPP}}{16}{section*.140}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{EDM}}{16}{section*.141}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{Dubins MCPP}}{16}{section*.142}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{CDM}}{16}{section*.143}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{Dubins MCPP}}{16}{section*.144}%
\contentsline {replaced}{Replaced: \truncate {\Changestruncatewidth }{It is shown that both EDM and CDM can provide smooth and continuous Dubins coverage paths. Comparison experiments with other exact or heuristic algorithms demonstrate that EDM produces the fastest Dubins coverage path in small-scale scenes, and CDM produces less coverage time and shorter computation time than other heuristic algorithms in large-scale scenes. Feasibility experiments show that the results from the simulations and the analysis performed on those results hold for high-fidelity Dubins robotic systems.}}{16}{section*.145}%