Page 16 - Read Online

Page 209 Zhu et al. Intell Robot 2022;2(3):200­222 I http://dx.doi.org/10.20517/ir.2022.13

for each vehicle; hence, problems of the path clutter, the high repetition rate, and a not complete full-coverage
path planning are induced.

The map building method based on sensor information is combined to achieve a complete full-coverage path
planning for the vehicle. Parlaktuna developed a full-coverage path planning method based on the sensor
system for multiple vehicles, where the generalized Voronoi diagram was applied for modeling and initializing
a full-coverage path, and the path section is divided by the capacitated arc routing algorithm [66] . The full-
coverage path planning is realized by the division of the vehicle navigation area; however, it only suits maps
consisting of narrow paths such that the vehicle can cover the whole area through one-direction navigation
and does not work well in a large space.

Basedonthebuildingmap, manyresearchershaverefinedthefull-coveragepathplanningmethodinthemulti-
vehiclesystemwhileresolvingthecollaborationproblem, whichis denoted as collaboratingfull-coverageprob-
lem. Janchiv applied cell decomposition to separate the operating area into several subareas and determine
the suitable path planning result for each subarea. The vehicles can consume the least turning times and main-
tain a high efficiency to complete the full-coverage path navigation [67] . However, Janchiv’s method did not
consider the collaboration among the vehicle groups, and the method lacks proof of robustness. Rekletis intro-
duced the boustrophedon cellular decomposition algorithm into the collaborating full-coverage path planning
problem for multiple vehicles, where the domain decomposition method breaks the area and a greedy auction
algorithm resolves the task assignment, as well as the collaboration of the vehicles [68] . This path planning
method achieves the full coverage of the whole area, yet a large repetition of the navigated paths still cannot be
avoided. Hazon proposed the multi-robots spanning-tree coverage algorithm (MSTC) that largely increased
the robustness for the multiple vehicles to traverse the whole area, while it cannot guarantee the optimal cov-
erage time [69] . Therefore, Zheng developed a multi-robots forest coverage (MFC) algorithm that realized the
optimal coverage time [70] .

With the advancement of intelligent algorithms, the full-coverage path planning method that can retune or
optimize itself has been developed. For instance, Kapanoglu combined the genetic algorithm (GA) and tem-
plate match approach into the collaborating full-coverage path planning problem, where GA is used to address
the best match template for each single vehicle path planning such that both the fewest traversing paths and
optimal coverage time can be promised, but the method lacks the adaption for dynamically changing environ-
ment, which is commonly seen for the underwater area [71] . The advantage of a bio-inspired neural network
is to resolve the collaborating full-coverage path planning problem of ground cleaning robots, where each
vehicle regards the others as obstacles such that the full-coverage with collision-free collaboration is realized.
However, the large complexity of the neural network is still a big concern [72,73] .

Moreover, to increase the efficiency of the full-coverage traversing algorithm, studies related to target search al-
gorithms based on probabilistic priority map have been proposed. For example, Cai developed a full-coverage
path planning algorithm depending on the bio-innovation such as animal behaviors, but considering the prob-
abilistic priority, where the efficiency is increased, the method yet is not highly adaptive to the changing envi-
ronment [74] . Yao proposed full-coverage path planning methods depending on the probability map of targets,
where intelligent methods such as biased min-consensus (BN-BMC) algorithm, Gaussian-based analysis, or
SOM are combined [75–77] .

Generally, most full-coverage path planning methods are applied to land or aerial vehicles rather than UUVs.
The problems of not completing full coverage and high repetition routes usually occur during the navigation
process. Thestudiesonfull-coveragepathplanningfortheUUVin underwaterenvironmentsaresummarized
in Table 3, which are still at the very early stage and attention has to be paid to the concerns of enhancing the
efficiency of full coverage and decreasing the repetition rate.