一篇综述性文章-使用经典和启发式算法进行机器人覆盖路径规划的全面评估

摘要

移动机器人的小电池容量和工业机器人未经优化的规划效率妨碍了覆盖任务的时间效率和生产率，以速度和准确性为代价，对机器人在特定环境条件下的规划策略的可用性施加了巨大限制。因此，解决与探索和覆盖路径规划（CPP）相关的优化问题变得非常重要。通常，CPP的目标是通过减少行程时间、处理速度、能量成本和路径长度上的转弯次数，以及低重叠率来生成一个无碰撞轨迹的最优覆盖路径，这反映了CPP的鲁棒性。本文回顾了CPP的原理，并讨论了发展趋势，包括设计变体和优化算法的特点，如经典的、启发式的和最新的深度学习方法。然后，我们比较了现有CPP模型在区域和目标覆盖方面的优缺点。最后，我们总结了CPP的众多开放性研究问题，并提出了未来研究方向的建议以获得深入的见解。

一、引言

移动机器人（如无人机、无人地面车辆、自主水下车辆、自主表面车辆）和工业机器人被广泛应用于自主区域覆盖任务，用于进行现场探索。尽管工业机器人通常通过操纵终端执行器沿预定路径达到目标位置，以覆盖指定的目标区域，但这种方法并未针对路径空间中的静态或动态障碍物进行优化。因此，自主机器人必须通过解决覆盖路径规划（CPP）问题来克服环境中的障碍物。

CPP已成为机器人应用中的热门研究课题，包括自主清洁[1] [2]、草坪修剪[3]、结构检查[4] [5]、农业[6] [7]、监控以及勘探[8]、制图、搜索和救援等领域[9] [10]。机器人终端执行器也可以从CPP中受益，如表面处理应用（铣削[11]、激光清洗[12]、喷涂[13] [14]、熔融沉积成型打印和制造检验[15] [16]）。CPP是确定一条路径，该路径覆盖初始状态到最终状态的所有点，同时在目标环境中检测和避免障碍物 [17]。CPP算法的目标是计算出最优路径，并投射一个无碰撞轨迹，以确保机器人在一定时间内完全覆盖感兴趣区域（AOI）。首先，分解技术将AOI分解为一组子区域。然后，确定机器人的初始位置并确定每个子区域的覆盖方向。有效的优化求解器计算子区域的序列连接，以覆盖每个单元格。最后，机器人通过简单的往返运动覆盖所有子区域。CPP的概念如图1所示。CPP的鲁棒性和性能效率基于几个参数，如覆盖区域的百分比、行程时间、路径重叠率和机器人的能量消耗。

CPP是移动机器人探索中处理区域覆盖优化的重要组成部分。区域覆盖是指由机器人以非重叠路径完全或部分包围的区域。根据搭载传感器对周围环境的先验知识，CPP算法可以分为离线算法和在线算法[18]。离线算法允许移动机器人在静态且已知的环境中进行覆盖。CPP通常基于全局的顺序点对点覆盖，机器人在给定地图上遵循路线并避开障碍物。然而，在实践中，机器人需要处理未知或部分已知的环境。因此，更倾向于使用在线算法，其中探索策略在机器人移动、执行、操作和观察障碍物位置时发生变化，以在感兴趣区域内探索未知区域。机器人将通过从本地传感器获取实时数据，并从动态环境中提取出显著特征来解决适合的路径。最后，机器人必须使用CPP技术创建对探索环境的有限映射[21]。

在过去的十年中，Galceran和Carreras [18]对机器人学中的CPP进行了综述。他们对环境建模的文献进行了调研，这些文献基于各种表面分割方法来解决CPP问题，包括细胞、基于网格和基于图的方法，分别适用于2D和3D结构。最近几年的文献综述包括多机器人CPP用于模型重建和建图[19]，以及无人机的综述[20]。过去的综述论文与本次综述的不同之处在于后者在优化准则方面进行了全面而最新的研究。在本综述文章中，对CPP进行了广泛的综述，主要关注用于解决优化问题的经典和启发式算法。无碰撞路径、覆盖成本函数（最短路径和平滑路径）以及覆盖顺序（集合覆盖问题和旅行商问题）与CPP问题直接相关，这取决于优化问题的解决程度。此外，还没有文献综述涉及使用深度强化学习方法解决CPP问题。我们相信，本综述将全面了解机器人学中的CPP，包括设计变体、优化算法的特点以及各种技术特征，如搜索时间、路径最优性、动态性能、收敛速度和计算复杂度。

本文对CPP技术进行了综述。接下来的部分将按照以下方式进行。第二节介绍了CPP的目标以及与平台、环境和路径最优性相关的具体挑战。接下来的第三节介绍了基于各种经典和启发式算法的最新CPP发展情况。现有的综述与覆盖效率问题和性能度量相关。第四节分析和总结了各种CPP算法的应用，包括其优点和缺点，并讨论了CPP中的开放问题，为未来的研究提供方向。最后，第五节对本文进行了总结。本文的组织结构如图2所示。

二、CPP中的挑战

在机器人学中，CPP仍然是一个开放性问题，需要改进规划最优路径以覆盖目标区域的效率，并生成一个计算量较小的无碰撞路径。生成的覆盖路径应该是最优的，以确保最小的后勤成本，如重叠、转弯次数、行程时间和能量消耗。CPP问题包括潜在的不确定性失败、复杂环境中的未知障碍物和路径最优性，这被认为是机器人学中的主要挑战。图3展示了CPP问题的目标、挑战和设计特点的概述。

在许多研究中中，已经提出了使用单个机器人进行区域覆盖的方法，其中只有一个自主车辆在小范围内执行简单任务，如清洁房间。在更广泛的区域覆盖情况下，机器人可能因故障和潜在故障（例如机械或电子故障、传感器和执行器故障、电池耗尽）而导致任务未完成。因此，许多研究人员致力于通过部署多机器人系统来提高区域覆盖的效率。多机器人覆盖相对于单个机器人具有更显著的优势，可以最小化运行时间并增强CPP的鲁棒性[22]。然而，开发多机器人的CPP技术仍然具有挑战性，因为它必须解决许多CPP约束在复杂和大规模的环境中。

同时，有限的感知能力和通信瓶颈是处理多机器人系统定位故障时必须应对的重要因素。因此，分布式控制网络系统通过集中式或分散式方法进行广播，以避免在这种限制下的可扩展性问题[23]。此外，团队机器人的战略韧性同样重要，邻近机器人在机器人故障的情况下可以接管重新规划任务，以填补功能间隙。不适当的任务调度也可能导致空闲问题。具体来说，协调和任务分配是多机器人区域覆盖中的核心问题，高度依赖于每个机器人的位置。因此，CPP的效率高度依赖于协调和任务分配策略，努力最小化总覆盖时间并平衡每个机器人的工作负载。最后，与单个机器人相比，多机器人系统能够提供系统冗。

在机器人学中，风、波浪和水下水流等环境因素仍然被认为是CPP的巨大挑战。UAV、AUV和以人为中心的智能机器人等车辆在受到环境条件的物理影响以及人体运动的影响时，在采集数据时必须在一个位置稳定自己[25]。除了与外部力量相抗衡外，避开障碍物也是一种常见的做法，以防止车辆在物理碰撞中受到物理损害。对于大规模环境（特别是多机器人系统）的CPP，通常是一种离线规划算法，因为受限于板载传感器和电池容量的限制。通常，由于运动学和动力学约束的复杂性，许多机器人的CPP技术仅考虑二维（2D）工作空间。这限制了机器人在三维（3D）空间覆盖方面的能力，特别是在水下环境中[26]。尽管2D模型简单且只需要少量计算，因此许多研究在表面的横截面上创建了一个2D模型，忽略了3D建模中的高度信息，因为大多数机器人可以执行2D特定区域的覆盖任务。然而，在人工2D工作空间中，CPP问题的重要方面是传感器足迹沿扫描路径的重叠覆盖。在现实中，当UAV或AUV在非平面表面（表面坡度较大）上覆盖感兴趣区域（ROI）时，固定深度处的高度会发生变化。当环境事先已知时，细胞分解是将区域分割成较小子区域的最简单方法，可以是规则的网格单元或多边形形状[27]-[29]。在三维空间中的CPP主要集中在目标覆盖，以覆盖关键的ROI，以评估结构（3D模型）的质量。通过生成视点并优化访问视点的顺序，可以实现目标区域的有效覆盖。然而，大多数研究工作只关注具有光滑表面的3D目标（对粗糙表面或隐藏表面的兴趣较小）

路径最优性与最短覆盖路径或旅行商问题（TSP）有关，通常是指通过多个感兴趣区域以最小的行程成本访问所有点的路径规划。因此，解决CPP问题面临着重大挑战，因为TSP和CPP问题都是NP难问题[31]。许多集成了TSP和CPP研究的目标是通过TSP求解器找到一组区域的访问顺序，并以来回方式规划最优路径以完全覆盖所有子区域[32]-[34]。因此，需要关注局部和全局覆盖路径的连接来解决集成TSP和CPP问题，包括每个感兴趣区域内的覆盖路径、子区域内的访问顺序以及进出路径。此外，在三维表面中，单个或多个机器人通常通过视场角规划生成一组视点，以覆盖目标表面区域，并找到无碰撞的最短路径以访问所选视点[35]，[36]。基于模型的视角规划问题通常被视为集合覆盖问题（SCP），其目标是减少视点数量，然后使用TSP或多TSP来解决路径规划问题[23]。因此，CPP路径最优性的挑战是最小化覆盖路径上的总行程时间并减少转弯成本。

三、相关算法

CPP算法可以分为两种方法，经典算法和基于启发式的算法。根据算法的特征，CPP算法的摘要细节如图4所示进行分类。值得注意的是，基于采样的规划和生物启发算法是解决CPP问题的热门研究课题。现有文献中有十个重点，包括随机行走、混沌覆盖路径规划器、生成树覆盖、人工势场、基于采样的规划算法、动态规划、贪婪搜索和图搜索算法、进化算法、以人为本的算法以及其他经典启发式算法。

A. 随机行走

随机行走（Random Walk，RW）是描述动物在尝试扫描和探索未开发区域时的搜索模式或移动的随机过程[37]。对于环境探索和覆盖，已经研究了不同变体的随机行走[38]，[39]。基于随机行走的区域覆盖有两种方法，即固定线性方法和可变步长方法。固定线性方法中，机器人随机转动一定角度，并经常沿直线移动，直到与墙壁或障碍物边界发生碰撞。Hasan等人[40]在清洁系统中引入了涉及随机行走、螺旋运动、曲线运动和墙随从的CPP算法。Liu等人[41]提出了一种在线随机覆盖方法，提高了覆盖率。然而，为了确保机器人覆盖整个区域，可变步长方法根据机器人所采取的步长的概率分布计算一组随机行走方向。

可变步长方法在协作移动机器人群系统中很受欢迎，包括布朗运动（Brownian Motion，BM）[42]和莱维飞行（Lévy Flight，LF）[43]。基于BM的机器人重复以给定分布（如高斯或von Mises [44]）的步长移动，并随机转向。相反，基于LF的机器人行进的距离取决于莱维概率分布[45]。BM的步长具有有限方差，而LF的步长具有无限方差。因此，与LF相比，BM具有更高的目标密度（局部行走）和短程移动。Martinez等人[46]提出了一种使用基于BM的随机行走的群体机器人来增强区域覆盖的方法。每个机器人被视为一个通过环境中的信号控制运动的粒子。在[47]中，利用基于信息素的通信[48]来控制多个机器人，并实施LF搜索策略以提高在未知环境中的搜索和覆盖效率。而[49]提出了梯度跟随与LF方法相结合，利用虚拟信息素模型进行控制，以在区域覆盖中提供更好的性能。

随机行走方法的主要优势在于平台不需要定位传感器。机器人只需要简单的板载传感器来感知和检测区域的边界以进行障碍物避免。因此，由于算法简单且内存要求较低，该方法非常灵活和易于部署。然而，在存在障碍物的情况下，随机行走路径仅适用于小环境，很难覆盖所有区域。机器人可能会多次穿过相同的路径，导致整体路径效率低下。

B. 混沌覆盖路径规划器

混沌覆盖路径规划器是一种确定性技术，它利用混沌系统基于混沌运动生成覆盖轨迹。混沌覆盖路径规划器通过机器人的运动轨迹在整个工作空间中保证高覆盖效率，从而实现更快的覆盖。该系统还可以通过在边界上实现最高覆盖率而无需进行障碍物避免来执行监视任务[51]，因为运动是预先确定的。Arnold的动力系统是一个众所周知的混沌系统，最初由Sekiguchi和Nakamura引入[50]。通过将混沌动力学变量与移动机器人的运动学方程组合设计和构建控制器，以构建混沌运动的覆盖路径规划器。

在三维非线性混沌系统的情况下，洛伦兹动力系统和Chua电路与Arnold动力系统相似。在[52]中，利用超混沌技术和非线性开环控制器，洛伦兹系统加速了工作空间的覆盖，相比Arnold系统和随机行走具有良好的混沌特性[53]，[54]。移动机器人中使用的Chua模式也提供了更好的覆盖性能[55]，[56]。基于Chua电路、洛伦兹系统和多个滚动吸引子的混沌吸引子随机数生成器已经在CPP中提出[57]。Nasr等人[58]利用多滚动Chua混沌镜像映射方法确定低成本的覆盖路径。

标准（Taylor-Chirikov）映射和Logistic映射分别是二维迭代映射和一维迭代映射的离散时间动力系统模型。Volos等人[59]，[60]设计了一个混沌Logistic映射随机比特生成器，用于生成移动机器人的覆盖轨迹。角度变换可以进一步改善覆盖路径规划器的均匀性[61]。而[62]采用伪随机比特生成器与反信息素方法相结合，在提供更高的覆盖率的同时，实现了更低的内存需求。在标准映射的情况下，[63]提出了使用不连续控制法对地形进行覆盖。而[64]，[65]则提出了一种融合策略，通过大区域和小区域之间的迭代周期以及与标准映射相对应的映射（仿射变换）实现覆盖。同时，Liet al.[66]采用了一种具有类似仿射变换技术的二维切比雪夫映射进行混沌CPP。

大部分混沌CPP运动以不可预测的随机、少量的步骤进行探索和监视任务，与随机行走相比，在未知环境中提供了更快的扫描，因为随机行走不是连续的[67]。因此，混沌CPP的连续运动使机器人能够有效地搜索和找到目标，并具有更均匀的覆盖密度。然而，现有文献只强调了覆盖率，忽略了覆盖时间的成本。机器人的不可预测轨迹也在很大程度上取决于机器人的运动学运动，受到运动学约束的影响，因此需要进行研究。

C. 基于生成树覆盖（Spanning Tree Coverage，STC）

基于生成树覆盖（Spanning Tree Coverage，STC）的CPP算法将工作空间划分为一系列不相交的有限单元，可以使用基于单元分解的方法或基于网格的方法进行划分[68]，[69]。然后，在相应的巨型单元中构建图的生成树，将其分为四个子单元，其中相应单元的大小等于机器人的大小。该算法通过使用树遍历算法（如深度优先搜索）找到最优路径，使机器人能够覆盖每个未占用的单元。然而，如果整个巨型单元内的障碍物占据了子单元，机器人将无法覆盖该巨型单元。在[70]中，作者提出了一种全覆盖STC算法，机器人可以覆盖自由子单元以最大化区域覆盖。STC已经扩展到针对多机器人系统的在线策略，以增加覆盖效率[71]，[72]。然而，机器人的行进路径取决于每个机器人的初始位置，并可能导致机器人之间的回溯问题。机器人遭受高重叠率的影响，严重损害能源效率。Kapoutsis等人[73]提出了一个区域划分算法，关注机器人的初始位置，以在矩阵条件下实现最优单元分配。在每个划分空间中构造最小生成树以实现任务的平衡分配。然而，该方法无法处理通过自由子单元的情况，即单元被障碍物占据，特别是在沿同一轴放置机器人的情况下。在[74]中，工作空间根据层次四叉树结构划分为不同的单元大小，然后通过考虑不同的边长构建生成树。这种方法可以最小化重复覆盖并平衡任务分配，但会导致单元的过度细分，增加任务成本。

Gao和Xin [75] 提出了基于拍卖和竞标过程的STC算法，用于解决多机器人CPP问题。在[76]中，构建了一个伪STC以创建虚拟边，假设障碍物占据了巨型单元。墙跟随算法使机器人能够沿着障碍物边界通过子节点移动。同时，Pham等人[77]改进了算法，通过在建立C空间边界轮廓时考虑部分被障碍物占据的巨型单元，以寻找最优路径，重点是减少回溯并增加覆盖率。路径通过逆时针方向的生成树边规划，以找到下一个未访问的巨型单元。在下一个部分被障碍物占据的巨型单元的情况下，机器人沿着C空间边缘移动并返回到父节点。实验结果表明，与全覆盖STC方法相比，所提出的算法实现了较高的覆盖率。类似地，[78]提出了基于次要节点之间的连通性的邻接图结构，以使机器人能够覆盖部分被障碍物占据的巨型单元。通常，基于机器人的在线CPP需要提供感知反馈，导致大量的能源消耗。因此，[21]提出了一种混合CPP算法，通过将基于边界的探索和STC算法结合起来，提高能源效率，无需扫描仪的辅助。

在最新的研究中，大多数基于多机器人的STC算法依赖于集中式控制技术，涉及通信和任务分配。传感器信息显著增加了计算和存储复杂性。当中央控制代理发生故障时，这可能导致系统故障。Dong等人[79]提出了一种基于分散策略的人工加权STC，以分布式方式执行覆盖任务。每个机器人承担的任务被平均分配，如果机器人发生故障，算法可以重新生成STC路径。因此，在机器人故障的情况下，系统可以确保完成覆盖任务。然而，路径重新规划器可能忽略了正在运行的机器人负担的任务，导致不平衡的工作负载问题。容错性在实际情况下仍然是一个重大挑战。

D.动态规划

动态规划（DP）是一种通过将复杂问题递归地划分为一组简单子问题，并将所有子问题的结果重新组合以获得解决方案的方法。在CPP中，DP问题展示了重叠的子问题和最优子结构，基于距离矩阵来优化全局覆盖子空间的顺序[81]。在[82]中，DP和TSP约减可以通过贪婪构造一组段落和连接所有段落来寻找最短覆盖路径并最小化转弯次数。DP框架在[83]中被开发用于优化感兴趣区域内的覆盖重叠。Coombes等人[84]采用自底向上的策略来节省内存空间并加速解组合过程。DP已被用于解决CPP中的TSP问题，通过全局规划找到依次覆盖所有区域的最短路径[33]。然而，由于问题规模巨大，生成的路径可能不是最优的。因此，[34]提出了基于最近邻或基于遗传算法（GA）的2-Opt算法来解决多区域问题，并通过基于DP的精确方法进一步优化路径。Cheng等人[85]根据形态层和条带层的集合引入了环境的图模型，需要将每个条带层的成本计算存储在DP中，并开发重新计算的预防措施以加快计算速度。然而，机器人不能适应复杂的动态环境。Ghaddar和Merei [86]提出了一种利用DP的在线CPP算法，以提高适应性和能量效率方面的性能。

E. 人工势场（Artificial Potential Field，APF）

人工势场（Artificial Potential Field，APF）算法通常用于当机器人朝着目标位置移动时检测障碍物。在周围的障碍物和目标周围分别创建了虚拟的斥力和吸引力，以确保机器人在实现目标的同时保持与障碍物的距离[87]。Sutantyo等人[88]采用LF算法来探索未知环境。通过添加APF技术增强了分散效果，产生了机器人之间的斥力。在[89]中，当传感器检测到表面缺陷时，通过根据人工势计算成本来重新规划覆盖路径。然而，由于APF方法存在局部最优问题，机器人可能无法逃离死区。因此，Wei等人[90]通过将APF和粒子群优化（PSO）算法相结合，通过优化粒子的速度和位置来实现检查策略，从而克服了局部最优问题。Wang等人[91]介绍了基于信息增益和路径成本的势场，机器人可以找到优化的轨迹以避免陷入局部最小值。在[92]中，作者通过在网格环境中引入种子的概念改进了APF算法，用于CPP。可以根据环境地图生成不同类型的路径种子来覆盖区域。Huang等人[93]利用APF方法通过多机器人系统的编队控制来覆盖区域。仿真结果表明，该方法实现了更好的区域覆盖和实时规划。在特定情况下，例如机器人通过狭窄空间，机器人可能无法到达目标。因此，Jiang和Deng [94]通过修改斥力势函数改进了APF算法，以有效避免检查任务中的障碍物。尽管有大量的研究工作，但在多个机器人同时访问目标并进行碰撞避免规划方面仍存在不足。

F.采样规划算法（Sampling-Based Planning Algorithms）

采样规划算法（Sampling-Based Planning Algorithms）是一种传统的算法，用于解决规划问题中的覆盖问题[95]，[96]。最近，概率采样规划（SBP）算法被用于启发式地和最优地解决复杂的规划问题。一般来说，该算法通过使用节点采样策略（在搜索环境中随机生成一组节点）将环境从配置空间映射。SBP的概率完备性对于在探索方面优化基于传感器（视觉）的检测是有效的。基于SBP的规划器包括概率路网图（Probabilistic Roadmap，PRM）[97]和快速探索随机树（Rapidly Exploring Random Tree，RRT）[98]。

1.概率路网图（Probabilistic Roadmap，PRM）

PRM规划器是一种通过建立路网图在配置空间中创建路径的规划和查询过程[99]。规划阶段在机器人的配置空间中随机生成节点，并连接这些节点对以直线方式形成一个路网，确保不穿越障碍物。然后，查询阶段利用规划阶段的结果，在初始配置和目标配置之间规划一条路径[100]。Dias等人[101]在地震情况下采用基于格点的PRM进行搜救任务。PRM广泛应用于通过结合A算法等搜索算法来优化路径和避障。在[102]中，利用PRM和A算法分别生成了工业机器人的无碰撞路径和最优顺序路径，模拟结果表明该算法可以通过添加TSP求解器来减少周期时间。然而，PRM方法由于节点的随机放置，使得机器人的覆盖区域在边界和障碍物附近有限。当发生障碍物碰撞时，PRM会移除相应的节点和边。此外，尽管PRM具有大量节点的概率完备性的优点，但也可能导致高复杂度和计算时间的问题。

2.快速探索随机树（Rapidly Exploring Random Tree，RRT）

RRT算法是一种高效的搜索规划器，采用增量技术和树形结构，在自由或障碍物配置空间中构建图形以进行搜索和探索[103]。该算法旨在有效地在高维空间中进行搜索，并处理动力学规划问题。与PRM相比，RRT对于单一查询问题更快，因为算法在学习阶段不需要对采样配置进行路网构建[1034]。Zaheer等人[105]分析认为，与PRM相比，RRT在计算时间和路径平滑性方面具有更好的性能。同时，[106]提出了在初始树和目标树之间进行双向搜索的方法，以快速相互生长，使两个树连接并生成最短路径以进行均匀搜索。然而，基于RRT生成的路径在解决规划问题时不一定是最优的。改进的RRT变种称为RRT，可以通过提供渐近最优解来改善路径质量[107]。Englot和Hover [35]基于基于采样的方法提出了一个解决覆盖采样和多目标规划问题的CPP算法。覆盖采样问题确定提供保证覆盖的最小视图集。然后，多目标规划问题确定访问所有视图的较短路径。该方法使用RRT算法渐近地找到全局最优解，以改善可行的覆盖路径。类似地，[108]提出了一种基于树形的快速探索随机树算法，用于实时三维重建的最优覆盖路径查找。元树结构包含多个子树，每个子树根据自己的RRT规划器进行每次迭代生长，以提供完全的可见性。然而，该算法需要大量的内存来存储树中的节点，导致计划成本较高。因此，基于两级算法的最优CPP算法被用来减少内存需求并生成最短的覆盖路径[109]。多方向固定节点的RRT算法用于通过探索邻域生成每个兴趣点（POI）的最小成本轨迹规划，从给定的初始点到目标点。然后，使用遗传算法（GA）来找到访问一系列POI的最短路径，解决TSP问题，并返回到初始点。类似地，[110]利用增量随机检查路网搜索优化构建图中的POI数量根据RRT算法，树结构被迭代生成，构建了一个包含一部分兴趣点（POIs）的路线图。然后，使用适当的图搜索算法计算覆盖所有POIs的最短路径。该方法旨在通过限制内存大小（树中节点数量）来最小化覆盖规划时间，这在研究[109]和[110]的结果中得到证明。Faghihi等人[111]提出了随机运动规划检测树（RKIT）算法，将CPP问题和运动规划问题进行了整合。在3D模型结构中，起始点和目标点分别位于正面和背面的中心位置。然后，对结构进行重新建模，创建了几个假设的立方体，其尺寸与正面（或背面）和传感器覆盖的尺寸相关。路径创建模块计算出对应于关键点（如外螺旋路径、螺旋螺线路径和内螺旋路径）的中间点。算法利用RKIT算法在每次迭代中使用给定区域中中间点的坐标进行采样。还采用了一个转向函数来有效处理微分约束。作者证明了该算法在识别3D结构的覆盖计划方面的可行性。然而，该研究未包括在存在静态和动态障碍物的情况下的模拟结果。

最近发展的RRT算法在搜索时间和路径成本（更短、更平滑的路径）方面取得了突破。然而，较少的相关研究涉及当机器人执行覆盖任务时的狭窄通道问题。因此，未来通过使用RRT变种（优化接近困难区域的区域覆盖）在狭窄的非结构化环境中穿越障碍物将是一个有趣的研究课题。

3.视角规划和运动规划

除了基于传感器的规划方法[112]、[113]之外，基于采样的视角规划方法[114]、[115]也是解决优化问题的另一种方案，需要同时进行视角规划和运动规划任务[116]、[117]。视角规划主要应用于建模应用和探索任务[118]。传感器对于使机器人视觉系统能够处理视角规划问题和目标覆盖的CPP问题至关重要。SCP和TSP分别解决了覆盖整个目标结构和视角的最小集合问题[119]、[120]。然后，规划算法的变体解决了覆盖规划问题，例如贪婪策略、最优策略或分解规划器[36]。在解决在线CPP问题时，大多数研究采用了最佳下一个视角（NBV）方法[121]，用于解决合适的视角选择，其中视角规划基于当前机器人位置和从传感器获取的信息。机器人的内置传感器在规划器生成视角之前探索和感知目标区域，以重建结构模型[122]、[123]。

同时，[115]提出了一种结构检测规划器（SIP），通过实现Lin-Kernighan-Helsgaun（LKH）算法[124]来优化视角姿势的路径。Palomeras等人[125]采用概率分析来计算效用，引入了NBV规划器。Osswald等人[126]利用逆可达性图和NBV算法，通过过滤可能的视角候选项，改善了机器人姿势和视角规划问题。Ardiyanto和Miura[127]基于多边形搜索和骨架化技术提出了一种可见性覆盖方法，用于生成覆盖视角，并进一步改进视角规划器以最小化机器人移动的能耗，从而保持对移动目标的可见性[128]。然而，如果发生遮挡，机器人可能无法跟踪目标。

顺序视角是视角规划问题的一部分，需要在三维环境中建模信息增益，例如使用体素[129]或表面网格[130]进行NBV规划。Wu等人[131]提出了基于学习的NBV方法，通过沿着体素进行射线投射，估计一组体素来计算下一次扫描的最佳视角。逆运动学求解器通过使用机载传感器和视角之间的相对位置校准，计算避免碰撞并找到良好的视角顺序[131]，[132]。Mansouri等人[133]，[134]利用结构运动方法重建目标区域，生成高质量的三维覆盖地图数据。与激光或测距扫描相比，该方法具有成本效益。同时，[135]提出了基于结构运动的多视角相机在CPP中的应用。Meng等人[136]利用基于Octomap结构[137]的概率体素图构建三维模型，并利用信息增益选择边界视角来解决TSP的变种问题。Paratama等人[138]提出了一种搜索空间CPP算法，以最大化航点的信息增益，并根据Octomap计算每个航点的熵来构建启发式代价函数。实验结果表明，与SIP、带RRT的LKH和带欧几里得启发式的LKH方法相比，所提出的算法能够提供更高的覆盖百分比。

大多数研究侧重于大型未知搜索空间，而忽视了信息较少的区域，导致结构模型不准确和不完整，忽略了全局路径，并导致路径重叠较长。因此，大多数研究者在滑动视角规划方法方面进行了研究，包括NBV规划器和探索规划器，利用RRT或RRT*算法探索未知环境[122]，[139]-[141]。优化过程在下一次迭代中重复进行，只执行第一个视角，并根据最佳视角选择路径。然而，由于有限的前瞻感知范围，机器人往往陷入次优的死胡同。因此，Jung等人[142]引入了多层次CPP技术，将三维模型结构分为几个层次，并在每个层次中重新采样视角以获得局部路径，然后将所有层次连接起来进行全局覆盖。Oleynikova等人[143]引入了在线局部重新规划，通过采用中间目标选择策略来最大化探索增益。在未知的室内环境中提供无碰撞的探索路径是具有挑战性的，因为室内环境通常具有狭窄且大规模的空间。因此，[144]，[145]提出了局部和全局探索技术的组合，利用基于采样的算法和边界探索。类似地，Almadhoun等人[146]提出了在边界和自适应网格视角生成器之间切换的方法，以提高局部极小值避免和效用函数质量。然而，特定区域的高覆盖密度会增加路径的成本。因此，Schmid等人[147]研究了信息增益和成本形式对于在效用函数中处理收益和成本之间的平衡的潜在影响。为了提高目标覆盖的完整性，[147]，[148]引入了一种信息采样算法，通过使用在线方法最大化全局覆盖和轨迹的效用值，并通过使用流式集覆盖算法减少采样范围。

此外，Jing等人[149]提出了一种新的CPP框架，包括视角生成、路径原语生成、可见性估计、原语覆盖图编码和覆盖图搜索。通过对均匀迭代适应性的计算，根据RRT*的点对点连接在高保真度网格模型中生成视角，以实现完全覆盖。基于Voronoi的重新网格算法对结构的网格模型进行下采样，以改善具有保证覆盖的检查路径。Glorieux等人[15]提出了一种针对性的视角采样策略，结合了SCP和TSP。自适应差分进化算法可以优化最佳的下一个视角，同时使用RRT进行碰撞避免。结果显示，与贪婪近似方法相比，检查周期时间和行程成本分别减少了23.8%和22.7%。然而，大多数现有的采样算法无法在高维搜索空间中生成准确的地图。因此，Hou等人[151]利用Gibbs采样技术（马尔可夫链蒙特卡洛）通过使用NBV算法对样本空间进行分解来生成准确的占据地图，以估计每个体素的条件概率进行3D表面重建。通过同时使用CPP算法和NBV，覆盖比例可以进一步提高，可以实时规划以通过应用蒙特卡洛树搜索来最大化信息增益。

在视角规划和覆盖规划中，有许多先前的研究致力于优化问题，以提高覆盖效率并确保视角规划器的质量。对高几何精度的高需求也导致算法的计算复杂性增加。因此，在模型质量（完整性和准确性）和计算时间之间仍然很难取得平衡。此外，在大规模空间中实时应用的可行性是一个复杂的任务，值得未来的研究。

G. 贪婪搜索和图搜索算法

贪婪算法是一种众所周知的启发式方法，通过在每一步选择中选择一个可用的选择，一旦选择被确定，就不会在后续步骤中改变选择，来构建解决方案来解决优化问题。该算法通常通过做出局部最优选择来寻找最佳选择，以获得全局最优解。贪婪算法（例如Dijkstra算法）简单易实现，通常速度较快，但由于其短期解决方案的特性，不能保证找到全局最优解。图搜索算法，例如A算法、D算法和Theta*算法通常结合牛轭运动或螺旋图案来规划和优化覆盖路径。搜索算法在图中找到从当前盲区位置到未覆盖区域的最短路径，当机器人陷入盲区或遇到障碍物时，重新规划路径以确定机器人的下一个位置以避开盲节点；否则，如果没有检测到障碍物，机器人将继续沿着之字形或螺旋路径行动。这些任务重复进行，直到感兴趣区域完全覆盖。
因此，搜索算法对于解决覆盖路径规划问题和提高搜索效率非常重要。然而，在大型网格地图中进行路径搜索仍然具有挑战性，因为计算成本很高。

1.深度优先搜索和广度优先搜索算法

深度优先搜索（DFS）和广度优先搜索（BFS）是基于图数据结构的递归算法用于搜索节点。这两个算法在时间复杂度方面都表现良好，但每个算法都有其缺点。DFS在无限深度空间中无法运行，并且不能保证找到最优解（最短覆盖路径），而BFS由于搜索空间中的高分支因子而消耗大量内存空间。DFS通过优化序列路径来最小化重叠和减少转向次数来优化覆盖路径。Kabir等人利用DFS技术生成一系列设置来创建清洁轨迹。然而，由于多个自由度，机器人相对复杂且计算量较大。Barrientos等人提出了一种基于BFS技术的波形规划器，可以应用于基于网格的工作空间，生成具有最少转向次数的覆盖路径。Wang等人提出了一种CPP方法，通过使用BFS算法来减少未覆盖区域。然而，该方法会导致未覆盖的边缘，机器人可能无法在角落进行操作。在一个知识推理与BFS相结合的机器人CPP中，通过避免不确定环境下的动态障碍物，降低了重复率和计算时间。Miao等人提出了一种使用子地图分解和BFS方法的分布技术。该技术将未知地图分解为几个子区域，并通过螺旋模式将每个机器人分配到最近的子区域进行覆盖。在小图的情况下，DFS和BFS算法都可以有效地优化覆盖路径。

2.Dijkstra算法

Dijkstra算法是一种广义的图搜索技术，用于解决单源最短路径问题，其中边的权重为非负数。该算法通过根据每个邻接顶点的成本函数从起始节点开始访问顶点，获得最短路径树。Almadhoun等人利用Dijkstra算法在室内环境中探索并以最小成本访问所有节点，实现了高效的路径覆盖。Yehoshua等人引入了螺旋STC方法来优化覆盖路径，并使用Dijkstra算法找到最小权重路径。然后，一个近似算法构建每对连接区域来解决TSP问题，获得更高的预期覆盖路径百分比。Cheng等人使用Dijkstra算法计算条纹层子图之间的最短路径（快速路径搜索），在最小化重复访问节点的情况下，在条纹层内实现最大区域覆盖。Rosa等人通过使用Dijkstra算法和蜜蜂（六边形）结构来进行多机器人系统的任务规划。Zhang等人通过考虑转弯次数和角度的成本函数改进了Dijkstra算法。然而，从行程距离的角度来看，搜索路径并非最优[166] [167]。

3.A*算法

A算法通过根据启发式函数估计从当前顶点到目标顶点的路径成本来确定相邻顶点。该算法选择最佳节点以找到最短路径，而不需要搜索整个地图。基于成本函数的算法已被用于减少转弯次数和降低路径搜索的处理时间。Viet等人利用A算法结合回溯方法实现了CPP，以获得最优覆盖路径，尽管需要大量内存来存储回溯点。Cai等人描述了A算法的概念，用于从死区逃脱并到达未覆盖区域的最短路径搜索。然而，如果机器人沿对角线移动，则很难覆盖障碍物周围的单元格。此外，在避开障碍物时，机器人会以较高的重叠率重新访问单元格，而不会覆盖其他单元格。因此，Le等人提出了一种修改后的A算法，用于CPP，通过确定边界航点和障碍物航点，将重访率降低了7.01%，覆盖率提高了6.4%，与传统的A算法相比。如果目标位置已知，A算法可以胜过DFS和BFS算法。

4.D*算法

D算法适用于动态环境下的路径规划。该算法是A算法的一种变种，能够在机器人遇到障碍物时应用成本路径优化解决方案重新规划路径。Dakulovic等人[175]利用D算法计算成本值，以避免重复访问节点并减少路径重新规划中的重叠。Maurovic等人[176]通过在D 算法中引入负权边，实现了主动SLAM来探索动态环境。D Lite算法通过从之前的搜索中获取信息（比D算法更短）[177]来提高路径重新规划的效率。Luo等人将[178]D Lite重新规划算法作为全局路径规划器，生成一个无碰撞路径用于探索未知环境，并使用蚁群优化（ACO）来规划航点路径的顺序，解决TSP问题，从而在探索地形中最小化沿计划轨迹的总距离。在[179]中一项改进的研究中，即AD算法，D Lite算法通过在线重新规划实现动态障碍物避障的最优路径。总的来说，当存在障碍物时，D Lite算法在路径重新规划过程中比A算法更高效，因为D Lite算法在首次搜索时具有先前的信息数据，而A*算法需要从头开始重新规划路径。因此，选择使用的算法取决于特定任务中的不同需求。

5.THETA*算法

A和D算法作为离散搜索方法，无法在连续空间中找到最短路径，因为生成的路径是通过网格边缘创建的。因此，Theta算法是基于任意角度路径搜索解决器的一种算法[180]，而Lazy Theta算法则可以解决其局限性。最短路径的生成基于网格地图上的一对点，其遵循顶点父节点可以是任何顶点，而不必是顶点的邻居（与A算法不同）。Choi等人使用Theta算法和蛇形路径运动提出了一个清洁机器人的在线CPP方法，以优化局部回溯路径。当机器人在执行蛇形运动后到达终点时，回溯点的确定通过回顾先前的路径来规划最短的回溯路径到下一个起始点。类似地，成本和目标选择函数可以减少未知环境中多机器人CPP的覆盖时间[182]。然而，该算法无法生成全局优化的解决方案，即路径长度方面的最优解。对于三维空间，Lazy Theta算法更适合在立方体网格上执行，因为相比于二维空间（方形网格），每个节点具有更多的邻居。Faria等人在3D Octomap框架中使用Lazy Theta算法实现了边界单元的探索和避开障碍物[183]。同时，[184]通过减少生成的邻居数量来提高Lazy Theta算法的效率，从而降低了计算成本和进行线程可见性检查的次数。Faria等人将飞越采样技术添加到探索系统中，包括边界和Lazy Theta规划器进行全局搜索、CPP和目标检查，以产生平滑路径并覆盖区域，尽管路径长度不能保证是最优的[185]。

H. 进化算法

进化算法（Evolutionary algorithms，EAs）基于自然或遗传进化的原理，通过寻找更好的解来解决优化问题[186]。进化算法由变异操作（交叉和突变）和适应度函数的评估组成。适应度函数根据给定的得分值来评估个体解的质量。适应度函数的计算可以通过优化问题的目标函数来表达，目标是最小化或最大化适应度函数的值[187]。进化算法在移动机器人的实际世界CPP优化问题中发挥着重要作用，能够更高效地构建基因搜索算法。

1.遗传进化

遗传算法（Genetic Algorithms，GA）是一种受生物遗传规律启发的元启发式算法，通过优胜劣汰和繁殖的思想来解决搜索问题[188]。遗传算法可以快速产生接近最优的解，通过并行处理的实现方式来解决路径规划问题。GA算法是一种理想的方法，由Wang和Bo[190]在CPP中解决TSP问题时首次引入。Hameed等人[191][192]提出了一种通过优化行驶方向和路径顺序来减少路径重叠和降低成本的遗传算法。Shen等人[193]使用GA来优化基于多个领域之间路径连接顺序的能量效率。Ellefsen等人[194]在AUV中使用多目标规划和遗传算法来规划水下表面检测的覆盖轨迹，通过非支配排序GA生成有目的的避碰路径，建立带有惩罚策略的规划器。与环绕和基于采样的CPP相比，该方法在覆盖率和能量使用方面能够提供更好的平衡。在[195]中，基于GA的TCP-CPP方法的计算时间在将自由空间分解为多个单元格时比基于DP的方法快。由于功率使用和通信距离的限制，Sun等人[22]应用GA来解决多机器人的任务分配问题，采用多TSP模型。

遗传算法在区域覆盖方面具有良好的全局搜索能力，但由于搜索空间复杂性较高，稳定性较差，需要较长的计算时间[196]。因此，Sadek等人[197]引入了多目标遗传算法与动态规划相结合的在线CPP方法，通过在遗传算法中采用确定性交叉过程代替随机交叉过程，提高了收敛速度朝向最优值[198]。Batista和Zampirolli[199]描述了将遗传算法与池清洁的近似最优CPP序列的实现。双重适应度函数可以计算染色体的效率，降低机器人的能量消耗。在[200]中，模拟退火算法和遗传算法分别能够生成全局和多个局部区域覆盖路径。两种算法并行处理，以减少计算成本。仿真结果证明该算法在第37次迭代后能够找到最短路径。Liu等人[201]将优化算法应用于结合遗传算法和神经网络生成协同路径。遗传算法通过学习过程优化神经网络的权重和阈值，提供了93.74%的覆盖率和4.25%的重复率。然而，遗传算法的收敛效率仍有改进空间，算法的组合是一个非常有前景的解决方案。

差分进化（DE）是一种替代遗传算法的进化算法[202]。在每次迭代中，试验向量的生成是差分进化过程中的重要步骤，用于解决优化问题，包括差分变异、重组和选择[203]。算法的性能取决于控制参数和变异策略的选择。差分进化具有快速收敛和鲁棒性等几个优点[204]。Vesterstrom等人[205]在数值基准测试中进行了实验，并证明差分进化相对于遗传算法和粒子群优化算法具有更好的性能。对于机器人任务规划问题，Xiao等人[206]通过结合轮盘和多邻域操作（解决局部最优解问题）、差分交叉策略（提高收敛速度）和多种群集成策略（获得高计算资源）改进了差分进化算法。差分进化优化路径模型在有限能量使用下表现出良好的性能，相对于最短路径模型而言。Gonzalez等人[207]利用差分进化算法优化覆盖路径（之字形路径），通过降低距离成本生成平滑轨迹。差分进化与快速匹配方格的组合可以在四个不同的三维环境中以最小的距离成本生成光滑轨迹，同时避免与障碍物发生碰撞。

2.群体智能

群体智能是由Beni和Wang[208]引入的概念，灵感来自生物的集体社会行为[209]。它指的是从群体智能中产生的合作行为中获得的集体智慧[210]。群体智能的目标是在优化问题中开发基于概率的搜索算法。因此，由于其灵活性和高效性的优势，群体智能算法已被用于解决现实世界中的全局和非线性优化问题[211]。在覆盖路径规划中，有几类优化算法，包括粒子群优化（PSO）[212]、蚁群算法（ACO）[213]和蜜蜂群算法（BCO）[214]。基于覆盖路径规划的群体智能算法利用粒子群的运动来寻找最短路径或达到目标，并以最小的时间提供最优的覆盖解决方案。

粒子群优化（PSO）是一种基于自然群体行为模式的元启发式算法，涉及到自然群体的聚集行为[215]。Lee等人[216]在高分辨率网格地图上进行了基于PSO的在线覆盖路径规划，提供了平滑的覆盖路径。在[217]中，聚类分布因子和PSO算法可在每个划分地图中进行区域覆盖。Sahu和Choudhury[218]使用PSO生成用于全局目标覆盖的轨迹。Y. H. Lin应用单目标PSO[219]和多目标PSO[220]来优化动态路径规划。Wang等人[221]证明了基于PSO方法的覆盖路径规划比牧野法具有更少的冗余覆盖。总的来说，PSO在初始阶段具有全局搜索能力，但群体容易陷入局部最优，导致搜索过程的收敛速度较慢。Couceiro等人[222]使用达尔文式PSO算法将群体分为多个小的合作子群（子群），通过奖惩机制提供逃离局部最优解的能力。在[223]中，一组采样路径输入PSO框架可以优化成本函数，提高覆盖路径的质量和效率。然后，全局最佳粒子从相机视野中选择最小成本的探索粒子更新，克服了过早收敛的限制。然而，在不同的模型大小上，计算时间仍然很长。此外，当PSO处理多维搜索空间时，其性能可能会迅速恶化[224]。因此，[225]提出了一种用于解决大规模优化问题的合作进化粒子群优化（CCPSO2）技术。Sun等人[226]提出了一种组合方法（CCPSO2和改进的GA）来解决最优传感器部署问题和TSP问题，分别在所有相应的子区域中实现了更好的覆盖和避障，尽管缺乏实验结果。

蚁群算法（ACO）是一种概率技术，模仿了蚂蚁的行为和寻找食物的过程，通过搜索最优路径来解决复杂的优化问题[227]。实施ACO算法来解决路径优化问题具有许多优势，如强鲁棒性[228]，[229]和并行计算[230]，[231]。然而，该算法很容易陷入局部最优解，收敛速度较慢[232]，[233]。因此，[234]提出了一种改进的ACO算法，使用信息素更新规则来避免陷入局部最小值。Chibin等人[235]使用ACO算法根据距离矩阵优化子区域的覆盖。Zhou等人[265]介绍了一种基于ACO算法的块序列优化来解决TSP问题。[237]提出了一种基于ACO算法的全局巡检路径优化。Max-Min Ant System (MMAS)是另一种改进的ACO算法，通过将信息素值限制在最大值和最小值之间来解决局部最优问题[238]。Karakaya[239]应用MMAS来规划UA V的目标覆盖路径。Tewolde和Sheng[240]比较了喷漆中GA和ACO算法的CPP性能，并显示ACO算法相对于GA算法可以将覆盖路径长度减少13%。Chen等人[13]通过使用指数均值贝塞尔曲线和基于ACO或GA的轨迹优化，改进了喷涂路径的精度，并通过在贝塞尔曲面上优化轨迹进一步提高了平滑路径[241]。Gao等人[242]提出了一种改进的ACO算法，通过减少多机器人CPP中的转弯次数来优化覆盖性能。Ye等人[12]通过随机计算转移概率和更新信息素以及加速因子改进了算法，提高了全局搜索能力，尽管算法的随机性可能导致失败。Dentler等人[243]利用基于ACO的航路点跟踪器结合动力学的混沌解来提高覆盖效率。然而，由于定位精度不高，可能会发生高风险的碰撞场景。Le等人提出了用于CPP的清洁机器人（hTetro）[244]和平铺机器人（hTetrakis [245]和hTrihex [246]），通过使用GA和ACO算法来减少能源消耗。此外，每种机器人类型都可以改变形状，以在给定的工作空间中提供高效的覆盖效果。
韩等人使用滑翔器以来回运动的方式滑行通过导航点，在海平面上使用蚁群算法寻找避开障碍物的最短路径，但受热跃层影响改变了通信半径，这是一项具有挑战性的任务。

BCO（蜜蜂群算法）是另一种基于群体智能的、类似于ACO和PSO的生物启发式机器学习算法。
Caliskanelli等人[248]引入了基于BCO的信息素信号算法，用于多机器人覆盖[249]，以及基于混合BCO-ACO信息素信号技术来解决多个机器人中的通信网络问题[250]。萤火虫算法（FA）是一种受自然启发的优化算法[251]，已广泛用于未知区域的覆盖和探索，特别是用于排雷任务[252] [253]。多机器人的目标是探索和覆盖矿区，并找到避开障碍物的最优路径。Palmeiri等人[254]在能耗方面比较了FA、PSO和BCO在群体机器人系统协调方面的性能。FA在全局覆盖所有节点方面的性能也优于ACO算法，在动态坡地的10x10网格大小情况下[255]，计算时间减少了7.2%，覆盖路径长度减少了2.5%。然而，如果增加机器人密度，则路径长度的改善不明显。Henrio等人[256]建议使用基于贝叶斯优化的超参数调整方法来应用于FA，以解决优化问题。灰狼优化器（GWO）是最近的一种元启发式算法[257]，模拟了灰狼的捕猎行为和社会领导力，其中alpha、beta、delta和omega是灰狼移动的分类。Kamalova和Lee[258]使用协调的多机器人探索（CME）和GWO算法进行多机器人探索，以实现最优协调和有效地优化覆盖区域，相比确定性CME算法获得了更好的性能。

尽管在四个不同的障碍地图上平均覆盖率为97.98%，但障碍物避免约束仍然是一个挑战。
与此同时，[260]基于多目标GWO算法进行了类似的实验，展示了机器人的覆盖能力，但机器人不断重访先前探索过的区域，导致执行时间较长。此外，GWO算法在获得全局最优解和处理动态障碍物方面存在困难，这是由于步长机制的限制。因此，Ge等人[261]通过将GWO算法与果蝇优化算法相结合，改进了局部最优解。同时，Dewangan等人证明了改进后的GWO算法具有更好的探索能力和避免局部最优解的能力。Kamalova等人[262]在基于前沿探索的全局路径点控制方法中实现了该方法，该方法生成位于不确定性开放区域上的前沿点（传感器未接收到任何传输信号），并根据前沿点阵列的输入参数创建全局路径点。GWO算法可以通过计算从当前机器人位置到前沿点位置的三个距离的平均值来估计下一个全局路径点（平均α点、平均β点和平均δ点），从而实现高效的搜索行为，与PSO算法相比具有更高的搜索行为。机器人具有很高的避开障碍物的能力，尽管最终导致行程较长。

3.生态学

生态算法是一种受生物启发的自然算法，已被用于工程和机器人技术作为一种优化方法。入侵性杂草优化（IWO）是一种著名的算法，它利用生态行为，基于自然中杂草的殖民属性和分布 [263]。IWO算法在优化搜索能力方面具有更好的全局收敛性和鲁棒性 [264], [265]。该算法通过编码器将杂草个体转化为正整数，以改造其种群（所有杂草的集合）来解决TSP问题 [266]。Ghalenoei等人 [267]以集中方式使用离散IWO算法进行多任务分配，从而使计算时间相对于遗传算法（GA）减少。Zhuang等人 [268]通过使用IWO和DE算法在无线传感器中呈现了局部和全球覆盖孔的检测和修复。Sandamurthy和Ramanujam [269]提出了基于离散IWO算法并改进了2-Opt操作符的CPP，用于收割机器人。IWO算法根据传播入侵性杂草的分布模式优化收集路径（或TSP），而划分策略使用马氏距离方法，有效地优化路径并提供了相比现有图遍历技术最高76%的覆盖率。生成路径的性能可以通过在线方法在覆盖率方面得到进一步改善。

I. 人类启发算法

人类启发算法是模仿人脑学习以优化路径规划决策的子智能算法之一。近年来，该算法已在探索任务领域中得到研究，特别是在大型动态环境中的覆盖规划问题。该算法可以避免沿轨迹与障碍物发生碰撞，但仍涉及相当大的计算负担和局部最小值问题。

1.神经网络

神经网络是一个知名的模型，也是机器人技术领域中最重要的模型之一。它已被广泛用于机器人运动规划和机器人系统控制。此外，它在提高覆盖路径规划（CPP）的性能中也起到了关键的作用。Yang和Luo [270] 提出了一种基于非学习神经网络的CPP方法，用于清洁机器人在规划无碰撞覆盖路径的同时避免障碍物，但是假设环境是离线的。因此，[271] 提出了一种适用于动态环境下实时CPP的生物启发神经网络（BINN）。BINN结构在移动机器人的CPP中表现更好，因为不需要学习过程（计算量小）。此方法已被进一步改进，以减少路径规划时间并提供较低的重叠覆盖区域 [272], [273]。然而，由于能耗高，该模型不适合长期在线规划。Yan等人 [274] 在实时2D网格图构建中引入了一种神经动力学模型，可以通过神经活动景观应用于机器人覆盖，构建动态地图并有效解决在未知环境中的CPP问题。同时，[275] 提出了一种使用神经动力学方法对多机器人的工作空间模型和引导。尽管多机器人系统提高了区域覆盖的时间效率，但系统的部署成本高。Yang等人 [276] 使用了与行人和障碍物避让策略结合的BINN方法，优化了无碰撞CPP轨迹。Singha等人 [277] 通过修改回溯技术应用了BINN算法，提高了神经活动的计算效率，克服了死锁问题。

在基于BINN方法的CPP中，算法需要高复杂性和大量计算，这导致了高成本。此外，机器人必须在当前的盲点位置等待，直到死锁的神经活动值小于邻近位置（或衰减）才能从死锁中逃脱。因此，移动机器人可能会出现低效率问题，不适合长期在线规划。因此，Glasius生物启发神经网络（GBNN）是一种改进的算法，可以减少CPP所需的时间，尤其是在从死锁情况中逃脱时。Zhu等人 [278] 提出了GBNN模型来处理在构建2D网格图中的CPP问题。而[279] 进一步在静态和动态环境中基于GBNN方法构建了3D网格地图。尽管该模型的计算成本高，但机器人可以在2D或3D环境下无碰撞地规划覆盖区域的路径。Sun等人 [280] 使用GBNN算法的合作多机器人系统进行2D静态环境下CPP的集中规划，大大降低了时间复杂性，并将区域内的重复覆盖率比BINN方法降低了13.4%。Kwon和Thangavelautham [281] 提出了人工神经组织控制算法（稀疏和可变拓扑神经网络与自适应激活函数），以解决覆盖任务。使用该控制器的优点是非中心控制器和有限的机载传感器之间无需通信。Samarakoon等人 [282] 通过使用可重配置机器人增加了区域覆盖率，并比较了两种性能相似的技术（前馈神经网络和自适应神经模糊推理系统）。同时，[283] 使用模糊推理系统研究了能源使用和区域覆盖之间的权衡。神经网络算法的计算成本和时间复杂度高，尤其是在专注于大规模环境中的CPP，这仍然有优化的潜力。

2.强化学习与深度学习

强化学习（RL）是机器学习的一种，其中代理通过处理顺序决策学习达到期望的目标 [284]。强化学习既不是监督学习也不是无监督学习，而是通过试错规则从经验中学习。马尔科夫决策过程（MDP）是描述RL问题的框架。RL的基本概念如图5所示。代理在给定状态下，通过与不确定环境交互来采取可能的动作，$s_t$在一系列时间步骤$t$中的每一个状态。结果，环境会向代理提供反馈，同时转变为新的状态，$s_{t+1}$，代理从环境中接收奖励$r_t$。通过提供新的数据$(s_t,a_t,r_t,s_{t+1})$，代理可以通过迭代学习自我优化，$\pi$从训练过程中生成策略。RL在机器人应用中被广泛使用 [285]，尤其是在最近的CPP工作中。尽管经典的DP可以解决最优规划问题，但由于转移概率矩阵的计算，它在解决大规模马尔科夫决策问题上存在困难。因此，RL已经被开发出来生成近似最优解，用于解决复杂的大型MDP [286]。基于RL的无模型方法最近已经成功地应用于现实世界的问题，即使环境模型是不完全的 [287]。

Shakeri等人[288]强调了强化学习可以用于CPP。Jing等人[289] 提出了使用MDP和”贪婪前向树搜索（FTS）方法的生产线上的3D表面检查，以生成在线基础的检查规划策略，证明了”贪婪FTS比NBV方法表现得更好，它减少了八个目标模型中平均周期时间的24%。邻近策略优化（PPO）算法是可以在工业覆盖喷涂中实施的策略梯度方法[14]。Le等人[290]使用基于RL奖励函数的PPO算法来解决在寻找低成本路径中的TSP优化问题。在[291]中，带有内在奖励的PPO算法可以提供高覆盖率并防止频繁碰撞。然而，由于环境的改变，覆盖效率可能会下降。Piardi等人[292]提出了一个Q学习算法，通过采用网格图来优化CPP轨迹。同时，[293]部署了一个分布式Q学习算法，用于合作的多代理信息图，以增强覆盖效率，提供稳定的局部最优覆盖解决方案，在有限的通信距离内。

在现实世界的问题中，更大的状态-动作（知识）空间可能会导致获取所有状态-动作对的值的问题，因为存储相关知识的表的大小是有限的。因此，深度RL替换了表格函数，作为函数逼近以避免收集大规模数据，例如在移动机器人探索和路径规划中的深度Q网络（DQN）方法 [294]，[295]。有时，经过训练的DQN倾向于不稳定，因为深度Q学习高估了动作价值。因此，Luis等人[296]设计了一个双重深度Q学习CPP，以有效地执行巡逻任务。Piciarelli和Foresti [297]将一个双维度的相关性地图输入到一个卷积层中，网络通过使用双重DQN进行训练，以根据观察优化相关区域的覆盖面积。结果表明，RL方法优于Z型路径 [296]，[297]，但只呈现了一种形式的结果。Chen等人[298]结合了n步Q学习和拟合Q迭代，不使用重播缓冲区来训练网络，解决了CPP问题，将路径长度和转弯次数分别减少了21.8%和38.6%，但处理在线CPP的搜索成本高。

通常，DQN在训练过程中会受到收敛速度慢和过度随机性的影响。因此，开发了演员-评论家方法来加速优化和训练过程，如深度确定性策略梯度（DDPG）算法和异步优势演员-评论家（A3C）网络。DDPG模型依赖于带有经验重放的架构，该架构经常从环境中使用每个样本，并且分离目标网络。而A3C网络使用梯度下降算法来优化网络控制器。该算法利用深度学习在连续的动作空间中。基于DDPG算法（策略梯度和DQN的组合），[299]提出了使用在线和离线RL执行覆盖范围的多个AUVs，覆盖范围在感兴趣的领域和通信范围内。与RW方法相比，这两种RL方法的效率都很高，但它们的性能类似，尽管在线RL方法的总旅行角度超过离线RL。在复杂环境中探索的成本可能会很高，尤其是在处理障碍物时。因此，胡等人[300]通过将其与优先经验重播算法集成，提高了DDPG的学习速度。Niroui等人[301]开发了A3C网络与边界探索，以在未知地图上生成机器人路径。同时，曹等人[302]使用了类似的算法与双流Q学习技术进行目标搜索，以探索未知环境，但任务分配是一个问题。清洁机器人（hTetro）使用带有经验重播算法的演员-评论家（A3C的离策略实现）来提高覆盖时间和能效，与ACO和GA方法相比，覆盖时间分别减少了25.88%和29.11%[303]。Kyaw等人[304]通过使用长短期记忆网络（用于构建递归神经网络的层的构建单位），略微减少了路径长度和重叠率。[290]，[303]，[304]展示了RL方法（或深度RL方法）寻找TSP解决方案的效率。然而，该模型只适合在二维工作空间中的自我可配置机器人，否则，它可能会显著增加转弯次数，从而导致常规机器人的路径成本高昂。因此，RL方法与适合的机器人平台在动态变化的环境中的适应性仍是机器人技术中的挑战。

还有许多其他的经典和启发式算法可用于探索和覆盖路径规划(CPP)。例如，布斯托罗冯运动和内部螺旋算法是简单的CPP算法，它们通常在每个单元中以来回（锯齿形）模式和螺旋路径进行。Koval等人[305]提出了基于布斯托罗冯运动的多智能体探索和覆盖方法，并使用PRM规划器。Balampanis等人[306]创建了一个Delaunay三角剖分网格模型，通过使用螺旋模式生成覆盖路径点。而[307]，[308]证明了平滑螺旋路径在覆盖面积和最小路径长度上优于布斯托罗冯运动，但对复杂表面的曲率关注较少。Voronoi划分方法是一种常见的建模技术，应用于多机器人系统的分布式协调[309]。尽管基于Voronoi划分的覆盖可以使用STC算法覆盖非重叠路径区域，但是需要事先知道环境信息才能完成任务。Brick and Mortar是一种启发式搜索算法，用于多智能体探索以搜索和覆盖感兴趣的区域。Ferranti等人[310]提出了使用Brick and Mortar算法的想法，通过增厚已访问或墙壁单元格的块，而不会丧失已探索或未探索单元格的连通性。该算法标记已访问的单元格，前提是后者不会阻塞两个单元格之间的路径，无论是在附近的已探索还是未探索的单元格。该算法在速度和覆盖方面表现更好。然而，该算法可能会停止执行，因为智能体严格避免已访问的地形，而不是寻找访问未探索区域的方法。Becker等人[311]使用多智能体洪水（MAF）算法来探索未知地形，寻找感兴趣的点。Blatt等人[312]结合了波前边界检测算法和MAF算法，以增加搜索速度，并使用Bug2算法和边缘跟踪技术来绕过障碍物，找到从起点到终点的直线路径上的边界点。

Xiao等人[313]提出了一种改进的覆盖路径规划（CPP）方法，以克服层次聚类和迭代自组织场规划算法在计算和重叠率方面的缺点。通过利用最近邻插入算法和可变邻域策略，可以改进局部搜索和成本路径。Meaclem等人[314]和Ding等人[315]分别使用k-means聚类方法和基于密度的空间聚类算法，将区域划分，并分配每个区域中的机器人进行区域覆盖。Azpurua等人[32]将环境划分为子六边形单元，并通过k-means算法将它们划分为子区域。虽然机器人可以执行规划路径，但风扰动可能会显著影响机器人的性能。Tang等人[316]使用CCPSO2、带反馈机制的k-means聚类和GA与A*算法结合进行传感器部署、区域划分和CPP。Miao等人[317]根据墙壁和障碍物边界周围的边角类型（凹或凸）提出了一种地图分解和子图清洗方法，用于多机器人分布。每个分布的机器人可以覆盖不同分配任务的区域，并在大环境中覆盖整个地图，但缺乏实验结果[316]，[317]。

Ma等人[318]提出了覆盖路径规划（CPP）算法，以解决区域覆盖问题，特别是在死区和障碍物边界。四叉树分割方法可以构建神经元地图，将地图分割为不同级别的子块，然后利用希尔伯特曲线遍历算法遍历每个模式以获取路径。梁等人[319]采用了带有希尔伯特曲线技术的路径生成策略进行数据收集，以最大化区域覆盖。监督控制基础的算法也已在多机器人系统中实现，以提高探索效率[320]。宋和Gupta[321]引入了使用探索性图灵机（ETM）监督机器人执行CPP的$\epsilon ^$算法。航点初始化基于多尺度势面，然后形成2D多级磁带，以实现自适应决策。该算法根据韧性方法在多机器人系统中形成基线覆盖[24]。根据博弈论框架实现了重新规划算法，其中每个机器人都由离散事件系统监督，如果发生机器人故障，就有可能恢复韧性。尽管$\epsilon ^$算法的计算复杂性低，但机器人可能会陷入局部最优。因此，沈等人[322]部署了机载传感器，使用ETM与Dubins路径更新地图信息，避免在障碍物附近被困。

IV. 讨论和未来研究方向

本综述比较了各种算法的覆盖路径规划（CPP）技术，并根据涉及到已知或未知环境的CPP中的环境建模，描述了机器人部署方法。表1至表7总结了每种技术的优势、局限性以及在解决覆盖任务方面的主要贡献。值得注意的是，大部分研究都是在仿真环境中进行的，如果不是由于各自研究领域的约束，如硬件平台和环境条件，就是在离线模式下部署的。因此，一些研究人员在动态环境中进行在线部署时作出了一些假设。然而，现有的研究在真实环境中仍然缺乏对效率低下、不可靠（任务执行）和不稳定性的强大解决方案。一些CPP算法的发展不够成熟，导致覆盖效率和避障优化不佳。表8列出了运动规划问题的详细描述，而图6则以典型的评分标准比较了不同算法的特点。表9通过分析每种算法的大O表示法计算复杂性。表10对七种算法在覆盖效率、优化标准和未来趋势方面进行了性能比较。

随机算法（例如，随机游走和混沌覆盖路径规划）以其随机或不可预测的轨迹而闻名于运动规划领域。它们广泛应用于低端群体机器人中，无需地图信息，可以有效地搜索和探索未知环境。这些算法提供了非常简单的随机运动，运行时间为O(log n)，只记录当前顶点n，并计算所采取的步数。一些研究（即步长、访问单元格数量和覆盖时间的搜索效率）已被视为未来研究的关键方面。无论如何，STC算法可以优化每个区域的覆盖路径，解决单机器人覆盖问题，并提供最小的覆盖重复以覆盖所有可访问的网格。其他改进方法，如螺旋STC、全面STC和平滑STC，可以实现比原始STC更高的覆盖率。这些STC方法在线性时间O(n)内计算覆盖路径，其中n是网格单元格（子单元格）的数量。多机器人STC的扩展可以根据不同的细胞分解技术进行适当选择，以缩短大面积覆盖的时间。STC方法简单，对环境变化反应灵敏，但只适用于在没有动态障碍物的情况下操作，因为生成的路径是预先确定的。可以使用路径重新规划算法基于剩余未覆盖的网格单元格构建新的生成树，以应对环境的动态变化，但会导致额外的计算时间。

APF（人工势场）算法是一种简单的计算方法，通过建立吸引力和排斥力的模型，提供了快速的障碍物避障路径规划速度。APF算法不需要全局信息，因此机器人可以实时有效地避开障碍物，并进行多机器人的协调控制。然而，如果大型或任意障碍物接近目标点，机器人很容易陷入局部最优解。这是因为当作用在机器人上的排斥力和吸引力相等时，机器人不会发生移动。此外，规划的路径不是最优路径，对于处理动态障碍物的适应性相对较差，导致机器人容易与移动障碍物发生碰撞。虽然APF方法只验证了局部障碍物避障，并且难以满足高速机器人的要求，但它仍然是与随机算法相结合最适合低端群体机器人的方法。

DP（动态规划）是一种经典的精确求解方法，用于解决TSP（旅行商问题）优化问题。它保证在可接受的时间内选择最佳解决方案，找到全局最优解。然而，为了解决最大旅行路径，时间复杂度会增加，导致计算成本高。因此，近似方法引起了人们的关注，用于解决大规模TSP问题，例如元启发式进化算法。进化算法已被证明对于解决单目标或多目标优化问题非常有效。例如，遗传算法通常在解决组合优化问题（如任务分配）时找到最佳解决方案。粒子群优化（PSO）需要较少的参数，并且用较少的时间达到目标，计算简单。但它对控制参数敏感，直接影响性能。而蚁群算法在寻找最短TSP路径方面具有很高的效率，但由于需要存储信息素矩阵，不适用于实时规划。火焰算法由于参数调整最少，具有快速的收敛速度和简单性。尽管元启发式算法具有强大的全局或局部搜索能力，但它们往往会陷入局部最小值。

最近的趋势包括采用混合算法（即局部搜索启发式算法和进化算法的组合，如2-opt算法和IWO [269]，或者两个启发式算法，如GA和PSO [226]）来优化CPP解决方案。混合算法需要较长的计算时间，但在TSP优化方面可以提供更好的覆盖效率。由于缺乏基准或令人满意的解决方案，选择适用于特定CPP问题的最佳混合算法仍然不确定。

在图论中，搜索算法可能是在两个节点之间寻找最短路径时最常用的方法。BFS（广度优先搜索）和DFS（深度优先搜索）算法是基本的图搜索技术，由于它们的盲目搜索策略（没有关于环境的信息），它们可以找到最短路径。它们在小规模问题中可以提供更好的搜索，但在时间和内存方面通常效率较低。它们的时间复杂度为O(mn)，其中n是顶点（节点）的数量，m是边的数量。相比之下，启发式搜索算法，如Dijkstra算法、$A^$算法和$D^*$算法，是高效的启发式搜索技术，用于寻找解决方案。Dijkstra算法是经典的回溯解决方案，用于解决CPP问题，在机器人从死区中逃脱时，对于小距离的室内CPP实现来说是一个合理的选择。而A和D算法是迄今为止已知的在大型复杂搜索空间中加速搜索的最快方法，但它们不保证提供最低成本路径，因为它们采用了启发式策略。

Dijkstra算法在寻找单源最短路径时的时间复杂度为$O(n log n)$，空间复杂度为$O(n)$。对于稠密图中计算所有顶点对之间的最短距离，$O(n^2)$是最佳解决方案。$A^$算法和$D^$算法的复杂度高度依赖于它们的启发式函数（估计从给定顶点到目标顶点的代价），将复杂度降低到较低程度，通常为$O(log n)$，可以实现在线应用，如果利用二叉堆实现优先队列，则为$O(n^2 log n)$或$O(n^2)$。它们之间唯一的区别在于在动态环境中满足移动机器人要求的能力：$A^$算法依赖于从起始顶点到任何给定顶点的代价路径和启发式函数之和最小的节点，而$D^$算法依赖于通过比较目标顶点和当前顶点来估计代价最小的节点（$A^$为正向搜索，$D^$为反向搜索）。因此，$D^*$算法在解决复杂问题，如动态环境时，具有更好的解决方案，它可以通过更新反向搜索过程（增量搜索）来重新规划路径。

另一方面，$D^$ lite算法（基于终身规划$A^$）更可取，因为它的实现更简单（比$D^$更短），在比较优先级时只使用一种断续准则（简化维护）。然而，当搜索空间相对较大时，$D^$或$D^$ lite的复杂度可能会显著增加，因为需要进行许多重新规划的执行。此外，如果存在许多移动障碍物，可能会产生不现实的距离。总体而言，$A^$算法在静态环境中具有较高的搜索效率（即移动机器人的最短回溯路径）。而$D^$ lite算法更适合处理障碍物特征的变化（例如工业机器人检测）。在处理基于离散网格地图（常规模式）的路径时，大多数情况下路径被限制在边缘上，导致生成的路径并非最短路径。而$Theta^$算法通过使用视线检查（LoS-Check）的任意角度搜索方法克服了这个缺点。它非常适用于在未知环境中进行大规模覆盖，主要由全向飞行机器人部署以找到下一个起始点，因为规划的路径快速且平滑。另外，基于采样的规划算法（如PRM和RRT）可以专门处理非全向约束下的运动规划问题。RRT算法（单查询规划器）更适用于解决单个起始和目标状态，但它无法收敛到最优解。因此，$RRT^*$是RRT的一个变体，通过采用局部重连操作最终达到收敛到最优解的目标。

虽然在具有广阔搜索空间和未知混乱环境以及狭窄走廊的最短路径问题中，采用更有前景的解决方法，但需要额外的平滑和重新规划算法来遵循最短路径和避免动态障碍物。这是由于在路径修剪过程中消除了不必要的路径点，生成了一个分段线性路径，这对于具有动力学约束的机器人来说是不可行的。类似地，$Theta^$算法可能会遇到相同的问题，需要进一步实施后处理技术来实现具有运动学可行性的路径。尽管$RRT^$和$Theta^$算法都已经改进成多个变体，基于LoS-Check来在解决覆盖任务中权衡解决方案质量和规划时间，但仍然缺乏对每个算法的清晰解决方案和性能比较。由于LoS-Check和在线碰撞检测，$RRT^$和$Theta^*$的时间复杂度分别达到$O(n^2)$和$O(n^3 logn)$。

为了实现高质量的结构覆盖，视角规划是准确建模的首要任务。根据之前的研究发现，最佳视角规划（NBV）方法可以获得考虑给定部分模型中未知区域的最具信息量的视角。然而，这种方法没有考虑环境的全局路线，导致可能存在与先前已知视角重叠的路径。一些特征，如孔洞和稀疏表面，可能会被忽略，导致构建模型的完整性降低。逐步收缩的NBV技术在局部探索方面具有更高的性能，但由于全局覆盖不足，容易陷入局部最小值。在大型工作空间中，探索相对昂贵，因为当机器人离最近的边界不近时，该方法往往会过早终止探索（低成本函数）。因此，该技术的计算复杂性主要取决于RRT树的构建、收益估计（使用射线投射）和碰撞检测，总的复杂性为$O(n logn + n log(V/r^3)(NM/r^4 + 1/r^3))$，其中N是水平射线的数量，M是垂直射线的数量，r是地图分辨率，V是待探索环境的体积 [122]。在当前的研究回顾中，融合算法的组合提供了更好的解决方案，利用了各种算法的优势。例如，基于采样的规划与基于边界的探索方法可以优化局部和全局的搜索能力 [149]，[323]。此外，结合逐步收缩的NBV和基于边界的探索方法可以将收益估计的计算复杂性从反比四次增长减少到反比线性增长，总的复杂性为$O(n logn + nV (NM/r + 1/r^3))$ [144]。然而，仍然存在许多限制，例如由于定位漂移和在线操作的高计算要求，性能可能会下降，此外算法高度依赖所使用的传感器和地图分辨率。因此，未来的工作有着无限的机会，在实际环境中开发融合的高质量优化和正确建模的CPP算法。

近年来，受人类启发的方法在解决CPP问题方面受到了更多关注。BINN和GBNN是处理实时覆盖任务最有效的技术，因为它们不需要学习过程。它们利用神经活动模式来生成最优路径，无需环境的先验知识和神经网络模型中的显式搜索过程。因此，它们具有处理未知静态和动态环境的高能力。GBNN通过在神经活动过程中消除长时间衰减，更好地从僵局中快速脱身，克服了BINN的缺点。这两种模型都可以实时避开障碍物，复杂度与离散程度的平方成正比，O(n2)，其中n是系统中的神经元数量。BINN还被用于处理覆盖规划任务中的多机器人编队控制问题 [325]。然而，有时最优路径规划过于靠近障碍物或多机器人近距离碰撞的情况，导致难以避开快速移动的障碍物。当机器人沿着障碍物边缘移动时，可能最终失败，这为在快速变化的环境中改进规划策略留下了许多空间。大多数研究假设机器人的位置已知，具有环境的先验知识，高精度传感器和理想的通信网络，因为实验通常涉及高成本的硬件，昂贵的传感器和工作空间中的安全隐患。值得注意的是，BINN方法在实际应用中的适应能力尚不确定，因为模拟环境和实际实验之间存在很大差距。

近年来，深度学习和强化学习开始在解决CPP问题方面变得重要，使经验驱动的学习能够应对实际问题。已经进行了一些基于强化学习的研究来完成覆盖任务，例如避免碰撞 [291]、平衡覆盖比例和能量使用 [326]，并在解决SCP优化中对视图规划有所裨益 [327]。元启发式算法在解决小工作空间问题上具有优势，但可能陷入局部最小值，并且当工作空间扩大时，计算复杂度呈指数级增长。相反，深度强化学习方法是解决大型复杂环境下优化问题的替代方法，例如在工作空间中减少COVID-19传播的消毒任务 [328]。尽管深度强化学习具有相对较好的性能，但在解决小工作空间问题时，由于模型计算复杂性、大量代理训练时间和超参数调整等问题，不太适合使用。深度强化学习方法与元启发式算法在解决TSP问题中的全向和非全向机器人之间的性能比较尚不完善。在未知环境中使用深度强化学习来处理多机器人CPP任务具有挑战性。然而，尽管相对不成熟，深度强化学习为解决CPP问题提供了一个有希望的未来方向。在机器人研究领域中，已经提出了许多CPP算法和方法。然而，仍存在许多限制和待解决的技术问题。
未来的研究应该关注以下方向：

A.覆盖完整性和时间效率的权衡

机器人的转向次数对总覆盖时间有着显著的影响。在CPP技术中，由于与螺旋运动相比，来回运动具有简单的路径设计，因此被广泛采用。然而，在大规模未知环境中，追求覆盖完整性往往会导致路径更长、转向更多，增加覆盖时间并降低效率。在复杂的三维结构中，现有算法受限于处理隐藏部分的目标，这在大多数先前的研究中被认为是一个非感兴趣区域和障碍物，从而导致完整覆盖计划的耗时较长。因此，需要在覆盖完整性和执行时间之间找到合适的平衡，以优化整体覆盖效率。

B.机器人的适应性与成本效益

动态环境特性可能会影响机器人的运动并导致性能下降。机器人可能缺乏灵活性，容易陷入常见的死锁情况。具备随时间改变操作行为能力的机器人对于在未知环境中寻找无碰撞路径至关重要，而该环境可能存在不确定的障碍物。除了增加机器人的板载传感器来处理复杂环境外，计算成本可能很高。进化算法通常不适用于成本较低的机器人，因为其对内存需求较大且计算开销较高。因此，在设计适合CPP的环境模型时必须考虑计算成本因素。混合算法是管理环境变化的一种有趣的发展，可以以最低的成本应对变化。

C.路径平滑性

覆盖和连接性对于无线传感器网络至关重要。由于通信和感知能力有限，如果出现意外情况，机器人将无法重新生成最佳路径，从而降低有效覆盖率。机器人的运动学约束，如路径曲率，也是必须解决的挑战之一。对于快速移动的机器人，如无人机，在转弯时进行轨迹平滑可以为机器人提供高效的惯性运动传递，以最小化功耗并防止机械损坏。因此，在遵循CPP路径的同时，需要绘制平滑的路径。

V. 结论

本文总结了基于经典算法和启发式算法的CPP算法的全面知识。通过分析每种技术的优点和缺点，列出并比较了所有要素。对CPP中存在的挑战进行了关键评估，涉及到区域覆盖、路径长度、行程时间、重复率和能量使用等几个典型特征方面的覆盖效率和碰撞避免。大多数方法展示了机器人在静态和动态环境中有效避开障碍物并覆盖区域的能力，覆盖率最高，路径重叠率低。每种算法在实践中表现良好，但仍然存在CPP文献中的限制。优化算法在解决CPP问题方面仍未得到充分发展。因此，需要解决SCP、TSP和逃离局部最小值的问题。解决局部和全局覆盖路径之间的连接可以解决集成TSP和CPP问题。但是，它仍然局限于处理有隐藏部分的目标。在复杂的未知环境中的适应性问题仍然没有得到很好的解决。深度强化学习在最近的发展中在各种CPP问题中取得了巨大成就。然而，当前的强化学习技术仍然不成熟，因此在进行动态环境中的CPP之前需要解决许多挑战。在多机器人场景中，应考虑机器人的分布和环境的结构，以提高CPP的效率。尽管多机器人可以合作覆盖AOI，但在线数据传输仍然具有挑战性。在未来的工作中，可以通过结合其他算法来改进CPP的性能，以减少现有经典算法的缺点。混合算法应该是CPP发展的方向。最后，研究人员相信可以通过验证模拟模型来从实际场景中进行实验结果的研究。

参考文献

[1] H. H. Viet, V.-H. Dang, M. N. U. Laskar, and T. Chung, “BA*: An online complete coverage algorithm for cleaning robots,” Int.J.Speech Technol.,vol.39, no.2, pp.217-235, Sep. 2013.

[2] H. V. Pham and T. N. Lam, “A new method using knowledge reasoningtechniques for improving robot performance in coverage path planning,”Int.J. Comput.Appl.Technol., vol.60, no.1, pp.57-64, Apr.

[3] I.A. Hameed, “Coverage path planning software for autonomous robotic lawn mower using Dubins’ curve,” in Proc.IEEE Int.Conf.Real-timeComput.Robot.(RCAR), Okinawa, Japan, Jul.2017, pp.517-522.

[4] E. Galceran, R. Campos, N. Palomeras, D. Ribas, M. Carreras, and P. Ridao, “Coverage path planning with real-time replanning and surface reconstruction for inspection of three-dimensional underwater structures using autonomous underwater vehicles,” J.Field Robot., vol.32, no.7,pp.952-983, Oct. 2015.

[5] C. Peng and V. Isler, “Visual coverage path planning for urban environments,” IEEE Robot.Autom.Lett., vol.5, no.4, pp.5961-5968,Oct. 2020.

[6] I.A. Hameed, “Intelligent coverage path planning for agricultural robots and autonomous machines on three-dimensional terrain,” J. Intell.Robotic Syst., vol.74, nos.3-4, pp.965-983, Jun.2014.

[7] K. Wang, Z. Meng, L. Wang, Z. Wu, and Z. Wu, “Practical obstacle avoidance path planning for agriculture UA Vs,” in Advances and Trends in Artificial Intelligence.From Theory and Practice (Lecture Notes in Computer Science), vol.11606, F. Wotawa, G. Friedrich, I.Pill,R. Koitz-Hristov, and M. Ali, Eds.Cham, Switzerland: Springer, 2019,pp.196-203.

[8] N. Basilico and S. Carpin, “Deploying teams of heterogeneous UA Vs in cooperative two-level surveillance missions,” in Proc.IEEE/RSJ Int.Conf.Intell.Robots Syst.(IROS) , Hamburg, Germany, Sep. 2015,pp.610-615.

[9] D. Jia, M. Wermelinger, R. Diethelm, P. Krusi, and M. Hutter, “Coverage path planning for legged robots in unknown environments,” in Proc.IEEE Int.Symp.Saf., Secur., Rescue Robot.(SSRR), Lausanne, Switzerland,Oct. 2016, pp.68-73.

[10] E. Galceran and M. Carreras, “Efficient seabed coverage path planning for ASVs and AUVs,” in Proc.IEEE/RSJ Int.Conf.Intell.Robots Syst. Vilamoura, Portugal, Oct. 2012, pp.88-93.

[11] S. Kalburgi, V. G. Nair, and K. R. Guruprasad, “Application of coverage path planning algorithm for milling operations,” in Intelligent Systems, Technologies, and Applications (Advances in Intelligent Systems and Computing), vol.1148, S. M. Thampi, L. Trajkovic, S. Mitra,P. Nagabhushan, E.-S. M. El-Alfy, Z. Bojkovic, and D. Mishra, Eds.Singapore: Springer, 2020, pp.213-220.

[12] X. Ye, L. Luo, L. Hou, Y. Duan, and Y. Wu, “Laser ablation manipulator coverage path planning method based on an improved ant colony algorithm,”Appl.Sci., vol.10, no.23, pp.1-19, Dec. 2020.

[13] W. Chen, J. Liu, Y. Tang, J. Huan, and H. Liu, “Trajectory optimization of spray painting robot for complex curved surface based on exponential mean Bézier method,” Math.Problems Eng., vol.2017, pp.1-10,Nov.2017.

[14] J. C. Kiemel, P. Yang, P. Meiÿner, and T. Kröger, “PaintRL: Coverage path planning for industrial spray painting with reinforcement learning,”
inProc.Conf.Robot., Sci.Syst., Freiburg, Germany, Jun.2019, pp.1-3.

[15] E. Glorieux, P. Franciosa, and D. Ceglarek, “Coverage path planning with targetted viewpoint sampling for robotic free-form surface inspection,” Robot.Comput.-Integr.Manuf., vol.61, pp.1-11, Feb. 2020.

[16] A. Khan, C. Mineo, G. Dobie, C. Macleod, and G. Pierce, “Vision guided robotic inspection for parts in manufacturing and remanufacturing industry,” J. Remanufacturing, vol.11, no.1, pp.49-70, Apr.2021.

[17] H. Choset, “Coverage for robotics-A survey of recent results,” Ann.Math.Artif.Intell., vol.31, no.1, pp.113-126, Oct. 2001.

[18] E. Galceran and M. Carreras, “A survey on coverage path planning for robotics,” Robot.Auton.Syst., vol.61, no.12, pp.1258-1276, Dec. 2013.

[19] R. Almadhoun, T. Taha, L. Seneviratne, and Y. Zweiri, “A survey on multi-robot coverage path planning for model reconstruction and mapping,” Social Netw.Appl.Sci., vol1, no.8, pp.1-24, Aug. 2019.

[20] T. M. Cabreira, L. B. Brisolara, and P. R. Ferreira, Jr., “Survey on coverage path planning with unmanned aerial vehicles,” Drones, vol.3,no.1, pp.1-38, Jan. 2019.

[21] P. M. M. M. Falaki, A. Padman, V. G. Nair, and K. R. Guruprasad,”Simultaneous exploration and coverage by a mobile robot,” in Control Instrumentation Systems (Lecture Notes in Electrical Engineering),vol.581, C. Shreesha and R. Gudi, Eds.Singapore: Springer, 2020,pp.33-41.

[22] R. Sun, C. Tang, J. Zheng, Y. Zhou, and S. Yu, “Multi-robot path planning for complete coverage with genetic algorithms,” in Intelligent Robotics and Applications (Lecture Notes in Computer Science), vol.11744,H. Yu, J. Liu, L. Liu, Z. Ju, Y. Liu, and D. Zhou, Eds.Cham, Switzerland:Springer, 2019, pp.349-361.

[23] A. Khamis, A. Hussein, and A. Elmogy, “Multi-robot task allocation:A review of the state-of-the-art,” in Cooperative Robots and Sensor Networks (Studies in Computational Intelligence), vol.604, A. Koubaa and J. R. M. Dios, Eds.Cham, Switzerland: Springer, 2015, pp.31-51.

[24] J.Song and S. Gupta, “CARE: Cooperative autonomy for resilience and efficiency of robot teams for complete coverage of unknown environments under robot failures,” Auto.Robots, vol.44, nos.3-4, pp.647-671,Mar.2020.

[25] W. He, Z. Li, and C. L. P. Chen, “A survey of human-centered intelligent robots: Issues and challenges,” IEEE/CAA J. Autom.Sinica, vol.4, no.4,pp.602-609, Oct. 2017.

[26] Z. Zeng, L. Lian, K. Sammut, F. He, Y. Tang, and A. Lammas, “A survey on path planning for persistent autonomy of autonomous underwater vehicles,” Ocean Eng., vol.110, pp.303-313, Dec. 2015.

[27] J. Kim, D. E. Lee, and J. Seo, “Task planning strategy and path similarity analysis for an autonomous excavator,” Autom.Construct., vol.112,pp.1-12, Apr.2020.

[28] A. Ghaddar, A. Merei, and E. Natalizio, “PPS: Energy-aware grid-based coverage path planning for UA Vs using area partitioning in the presence of NFZs,” Sensors, vol.20, no.13, pp.1-32, Jul.2020.

[29] S. Xing, R. Wang, and G. Huang, “Area decomposition algorithm for large region maritime search,” IEEE Access, vol.8, pp.205788-205797,2020.

[30] Y. Choi, Y. Choi, S. Briceno, and D. N. Mavris, “Energy-constrained multi-UA V coverage path planning for an aerial imagery mission using column generation,” J. Intell.Robotic Syst., vol.97, no.1, pp.125-139,Jan. 2020.

[31] E. M. Arkin, S. P. Fekete, and J. S. B. Mitchell, “Approximation algorithms for lawn mowing and milling,” Comput. Geometry, vol.17,nos.1-2, pp.25-50, Oct. 2000.

[32] H. Azpúrua, G. M. Freitas, D. G. Macharet, and M. F. M. Campos,”Multi-robot coverage path planning using hexagonal segmentation for geophysical surveys,” Robotica, vol.36, no.8, pp.1144-1166,Aug. 2018.

[33] J. Xie, L. R. G. Carrillo, and L. Jin, “An integrated traveling salesman and coverage path planning problem for unmanned aircraft systems,” IEEE Control Syst. Lett., vol.3, no.1, pp.67-72, Jan. 2019.

[34] J. Xie, L. R. G. Carrillo, and L. Jin, “Path planning for UA V to cover multiple separated convex polygonal regions,” IEEE Access, vol.8,pp 51770-51785, 2020.

[35] B. Englot and F. S. Hover, “Sampling-based coverage path planning for inspection of complex structures,” in Proc.22nd Int.Conf.Automated Planning Scheduling, Sao Paulo, Brazil, Jun.2012, pp.29-37.

[36] C. Dornhege, A. Kleiner, A. Hertle, and A. Kolling, “Multirobot coverage search in three dimensions,” J.Field Robot., vol.33, no.4, pp.537-558,Jun.2016.

[37] F. Bartumeus, M. G. E. da Luz, G. M. Viswanathan, and J. Catalan, “Animal search strategies: A quantitative random-walk,” Ecology, vol.86,no.11, pp.3078-3087, Nov. 2005.

[38] C. Dimidov, G. Oriolo, and V. Trianni, “Random walks in swarm robotics: An experiment with Kilobots,” in Swarm Intelligence (Lec-ture Notes in Computer Science), vol.9882, M. Dorigo, M. Birattari,X. Li, M. L. Ibanez, K. Ohkura, C. Pinciroli, and T. Stutzle, Eds.Cham,Switzerland: Springer, 2016, pp.185-196.

[39] M. Kegeleirs, D. G. Ramos, and M. Birattari, “Random walk exploration for swarm mapping,” in Towards Autonomous Robotic Systems (Lecture Notes in Computer Science), vol.11650, K. Althoefer, J. Konstantinova,and K. Zhang, Eds.Cham, Switzerland: Springer, 2019, pp.211-222.

[40] K. M. Hasan, Abdullah-Al-Nahid, and K. J. Reza, “Path planning algorithm development for autonomous vacuum cleaner robots,” in Proc.Int.Conf.Informat., Electron.Vis.(ICIEV) , Dhaka, Bangladesh, May 2014,pp.1-6.

[41] Y. Liu, X. Lin, and S. Zhu, “Combined coverage path planning for autonomous cleaning robots in unstructured environments,” in Proc.7th World Congr.Intell.Control Autom., Chongqing, China, Jun.2008,pp.8271-8276.

[42] I.A. Wagner, M. Lindenbaum, and A. M. Bruckstein, “Robotic exploration, Brownian motion, and electrical resistance,” in Randomization and Approximation Techniques in Computer Science (Lecture Notes in Computer Science), vol.1518, M. Luby, J. D. P. Rolim, and M. Serna,Eds.Berlin, Germany: Springer, 1998, pp.116-130.

[43] D. Sutantyo, P. Levi, C. Moslinger, and M. Read, “Collective-adaptive Lévy flight for underwater multi-robot exploration,” in Proc.IEEE Int. Conf.Mechtron.Autom., Takamatsu, Japan, Aug. 2013, pp.456-462.

[44] B. Pang, Y.Song, C. Zhang, and R. Yang, “Effect of random walk methods on searching efficiency in swarm robots for area exploration,” Int.J.Speech Technol., vol.51, no.7, pp.5189-5199, Jul.2021.

[45] Y. Katada, A. Nishiguchi, K. Moriwaki, and R. Watakabe, “Swarm robotic network using Lévy flight in target detection problem,” Artif. LifeRobot., vol.21, no.3, pp.295-301, Sep. 2016.

[46] F. Martinez, E. Jacinto, and D. Acero, “Brownian motion as exploration strategy for autonomous swarm robots,” in Proc.IEEE Int.Conf.Robot. Biomimetics (ROBIO), Guangzhou, China, Dec. 2012, pp.2375-2380.

[47] R. Fujisawa and S. Dobata, “Lévy walk enhances efficiency of group for- aging in pheromone-communicating swarm robots,” in Proc.IEEE/SICE Int. Symp.Syst.Integr., Kobe, Japan, Dec. 2013, pp.808-813.

[48] G. Li, C. Chen, C. Geng, M. Li, H. Xu, and Y. Lin, “A pheromone-inspired monitoring strategy using a swarm of underwater robots,” Sensors, vol.19, no.19, pp.1-25, Oct. 2019.

[49] A. Schroeder, S. Ramakrishnan, M. Kumar, and B. Trease, “Efficient spatial coverage by a robot swarm based on an ant foraging model and the Lévy distribution,” Swarm Intell., vol.11, no.1, pp.39-69, Mar.2017.

[50] A. Sekiguchi and Y. Nakamura, “The chaotic mobile robot,” IEEE Trans. Robot.Autom., vol.17, no.6, pp.898-904, Dec. 2001.

[51] C.-H. Li, C. Fang, F.-Y.Wang, B. Xia, and Y.Song, “Complete coverage path planning for an Arnold system based mobile robot to perform specific types of missions,” Frontiers Inf.Technol.Electron.Eng., vol.20,no.11, pp.1530-1542, Dec. 2019.

[52] C. K. Volos, I. M. Kyprianidis, I. N. Stouboulos, H. E. Nistazakis, and G. S. Tombras, “Cooperation of autonomous mobile robots for surveil-
lance missions based on hyperchaos synchronization,” J. Appl.Math.Bioinf., vol.6, no.3, pp.125-143, Dec. 2016.

[53] M. J. M. Tavera, O. Lengerke, and M. S. Dutra, “Implementation of chaotic behavior on a fire fighting robot,” in Mechatronics Series I Intelligent Transportation Vehicles, O. Lengerke, and M. S. Dutra, Eds.Dubai: Bentham Science, 2011, pp.170-182.

[54] C. Li, Y.Song, F. Wang, Z. Wang, and Y. Li, “A bounded strategy of the mobile robot coverage path planning based on Lorenz chaotic system,”Int.J. Adv.Robotic Syst., vol.13, no.3, pp.1-9, May 2016.

[55] P. Sooraska and K. Klomkarn, “`No-CPU’ chaotic robots: From classroom to commerce,” IEEE Circuits Syst.Mag., vol.10, no.1, pp.46-53,Mar.

[56] A. Anwar and H. Khammari, “An investigation on patrol robot coverage performance based on chaotic and non-chaotic guiding signals,” Int.Trans.J.Eng., Manage.Appl.Sci.Technol., vol.2, no.4, pp.405-421,Sep.2011.

[57] C. H. Pimentel-Romero, J. M. Munoz-Pacheco, O. Felix-Beltran, L. C. Gomez-Pavon, and C. K. Volos, “Chaotic planning paths generators by using performance surfaces,” in Fractional Order Control and Synchronization of Chaotic Systems (Studies in Computational Intelligence), vol.688, A. Azar, S. Vaidyanathan, and A. Ouannas, Eds.Cham,Switzerland: Springer, 2017, pp.805-832.

[58] S. Nasr, H. Mekki, and K. Bouallegue, “A multi-scroll chaotic system for a higher coverage path planning of a mobile robot using flatness controller,” Chaos, Solitons Fractals, vol.118, pp.366-375, Jan. 2019.

[59] C. K. Volos, I. M. Kyprianidis, and I. N. Stouboulos, “Experimental investigation on coverage performance of a chaotic autonomous mobile robot,” Robot.Auto.Syst., vol.61, no.12, pp.1314-1322, Dec. 2013.

[60] C. K. Volos, N. Doukas, I. M. Kyprianidis, I. N. Stouboulos, andT. G. Kostis, “Chaotic autonomous mobile robot for military missions,”inProc.17th Int.Conf.Commun., Recent Adv.Telecommun.Circuit Design, Rhodes Island, Greece, Jul.2013, pp.197-202.

[61] C. Li, F. Wang, L. Zhao, Y. Li, and Y.Song, “An improved chaotic motion path planner for autonomous mobile robots based on a logistic map,” Int.J. Adv.Robotic Syst., vol.10, no.1, pp.1-9.Jan. 2013.

[62] E. K. Petavratzis, C. K. Volos, L. Moysis, I. N. Stouboulos, H. E. Nistazakis, G. S. Tombras, and K. P. Valavanis, “An inverse pheromone approach in a chaotic mobile robot’s path planning based on a modified logistic map,” Technologies, vol.7, no.4, pp.84-99, Dec. 2019.

[63] L. S. Martins-Filho and E. E. N. Macau, “Patrol mobile robots and chaotictrajectories,” Math.Problems Eng., vol.2007, pp.1-13, Apr.2007.

[64] C. Li, Y.Song, F. Wang, Z. Liang, and B. Zhu, “Chaotic path planner of autonomous mobile robots based on the standard map for surveillance missions,” Math.Problems Eng., vol.2015, pp.1-11, Aug. 2015.

[65] C. Li, Z. Wang, C. Fang, Z. Liang, Y.Song, and Y. Li, “An integrated algorithm of CCPP task for autonomous mobile robot under special missions,” Int.J. Comput.Intell.Syst., vol.11, no.1, pp.1357-1368,Aug. 2018.

[66] C.-H. Li, Y.Song, F.-Y.Wang, Z.-Q.Wang, and Y.-B.Li, “A chaotic coverage path planner for the mobile robot based on the Chebyshev map for special missions,” Frontiers Inf.Technol.Electron.Eng., vol.18, no.9,pp.1305-1319, Sep. 2017.

[67] K. Sridharan and Z. N. Ahmadabadi, “A multi-system chaotic path planner for fast and unpredictable online coverage of terrains,” IEEE Robot.Autom.Lett., vol.5, no.4, pp.5275-52683, Oct. 2020.

[68] Y. Gabriely and E. Rimon, “Spanning-tree based coverage of continuous areas by a mobile robot,” Ann.Math.Artif.Intell., vol.31, nos.1-4,pp.77-98, Oct. 2001.

[69] N. Hazon and G. A. Kaminka, “Redundancy, efficiency and robustness in multi-robot coverage,” in Proc.IEEE Int.Conf.Robot.Autom.,Barcelona, Spain, Apr.2005, pp.735-741.

[70] Y. Gabriely and E. Rimon, “Competitive on-line coverage of grid environments by a mobile robot,” Comput.Geometry, vol.24, no.3, pp.197-224,Apr.2003.

[71] N. Agmon, N. Hazon, and G. A. Kaminka, “Constructing spanning trees for efficient multi-robot coverage,” in Proc.IEEE Int.Conf.Robot.Autom.(ICRA), Orlando, FL, USA, May 2006, pp.1698-1703.

[72] K. S. Senthilkumar and K. K. Bharadwaj, “Spanning tree based terrain coverage by multi robots in unknown environments,” in Proc.Annu.IEEE India Conf., Kanpur, India, Dec. 2008, pp.120-125.

[73] A. C. Kapoutsis, S. A. Chatzichristofis, and E. B. Kosmatopoulos,”DARP: Divide areas algorithm for optimal multi-robot coverage path planning,” J. Intell.Robotic Syst., vol.86, nos.3-4, pp.663-680,Jun.2017.

[74] X. Huang, M. Sun, H. Zhou, and S. Liu, “A multi-robot coverage path planning algorithm for the environment with multiple land cover types,”IEEE Access, vol.8, pp.198101-198117, 2020.

[75] G.-Q.Gao and B. Xin, “A-STC: Auction-based spanning tree coverage algorithm formotion planning of cooperative robots,” Frontiers Inf. Technol.Electron.Eng., vol.20, no.1, pp.18-31, Jan. 2019.

[76] T. D. Ranjitha and K. R. Guruprasad, “Pseudo spanning tree-based complete and competitive robot coverage using virtual nodes,” IFAC- PapersOnLine, vol.49, no.1, pp.195-200, Feb. 2016.

[77] H. V. Pham, P. Moore, and D. X. Truong, “Proposed smooth-STC algorithm for enhanced coverage path planning performance in mobile robot applications,” Robotics, vol.8, no.2, pp.1-19, Jun.2019.

[78] K. R. Guruprasad and T. D. Ranjitha, “CPC algorithm: Exact area coverage by a mobile robot using approximate cellular decomposition,”Robotica, vol.39, no.7, pp.1141-1162, Jul.2021.

[79] W. Dong, S. Liu, Y. Ding, X. Sheng, and X. Zhu, “An artificially weighted spanning tree coverage algorithm for decentralized flying robots,” IEEETrans.Autom.Sci.Eng., vol.17, no.4, pp.1689-1698, Oct. 2020.

[80] R. Wu, “The application of dynamic programming in production planning,” AIP Conf.Proc., vol.1839, no.1, pp.1-3, May 2017.

[81] P. Zhou, Z.-M. Wang, Z.-N. Li, and Y. Li, “Complete coverage path planning of mobile robot based on dynamic programming algorithm,” in Proc.2nd Int.Conf.Electron.Mech.Eng.Inf.Technol., Shenyang, China,Sep. 2012, pp.1837-1841.

[82] M. Morin, I. Abi-Zeid, Y. Petillot, and C.-G. Quimper, “A hybrid algorithm for coverage path planning with imperfect sensors,” in Proc.IEEE/RSJ Int.Conf.Intell.Robots Syst., Tokyo, Japan, Nov. 2013,pp.5988-5993.

[83] A. A. Altahir, V. S. Asirvadam, N. H. B. Hamid, P. Sebastian, N. B. Saad,R. B. Ibrahim, and S. C. Dass, “Optimizing visual sensor coverage overlaps for multiview surveillance systems,” IEEE Sensors J., vol.18,no.11, pp.4544-4552, Jun.

[84] M. Coombes, T. Fletcher, W. H. Chen, and C. Liu, “Optimal polygon decomposition for UA V survey coverage path planning in wind,” Sensors,vol.18, no.7, pp.1-28, Jul.

[85] K. P. Cheng, R. E. Mohan, N. H. K. Nhan, and A. V. Le, “Graph theory-based approach to accomplish complete coverage path planning tasks for reconfigurable robots,” IEEE Access, vol.7, pp.94642-94657, 2019.

[86] A. Ghaddar and A. Merei, “EAOA: Energy-aware grid-based 3D-obstacle avoidance in coverage path planning for UA Vs,” Future Internet,vol.12, no.2, pp.1-20, Feb. 2020.

[87] S. G. Tzafestas, Introduction to Mobile Robot Control.Boca Raton, NY,USA: Elsevier, 2013.

[88] D. K. Sutantyo, S. Kernbach, P. Levi, and V. A. Nepomnyashchikh,”Multi-robot searching algorithm using Lévy flight and artificial potential field,” in Proc.IEEE Saf.Secur.Rescue Robot., Bremen, Germany,Jul.2010, pp.1-6.

[89] M. Nykolaychuk and F. Ortmeier, “Coverage path re-planning for processing faults,” in Intelligent Robotics and Applications (Lecture Notes in Computer Science), vol.9245, H. Liu, N. Kubota, X. Zhu, R. Dillmann,and D. Zhou, Eds.Cham, Switzerland: Springer, 2015, pp.358-368.

[90] C. Wei, F. Zhang, C. Yin, Y. Liu, L. Liu, Z. Li, and W. Wang, “Research on UA V intelligent obstacle avoidance technology during an inspection of transmission line,” in Applied Mechanics (Mechatronics and Intelligent Systems), S. Qin and X. Li, Eds.Singapore: World Scientific, 2016,pp.319-327.

[91] C. Wang, L. Meng, T. Li, C. W. D. Silva, and M. Q.-H. Meng, “Towards autonomous exploration with information potential field in 3D environments,” in Proc.18th Int.Conf.Adv.Robot.(ICAR), Hong Kong,Jul.2017, pp.340-345.

[92] J. Yan, Y. Li, Z.Song, and Q. Zhang, “Research on UA V coverage path planning algorithm based on improved artificial potential field method,”Oper.Res.Fuzziol., vol.9, no.4, pp.264-270, Nov. 2019.

[93] C. Huang, W. Li, C. Xiao, B. Liang, and S. Han, “Potential field method for persistent surveillance of multiple unmanned aerial vehicle sensors,”Int.J. Distrib.Sensor Netw., vol.14, no.1, pp.1-13, Jan. 2018.

[94] X. Jiang and Y. Deng, “UA V track planning of electric tower pole inspection based on improved artificial potential field method,” J. Appl.Sci.Eng., vol.24, no.2, pp.123-132, Apr.

[95] T. Danner and L. E. Kavraki, “Randomized planning for short inspection paths,” in Proc.IEEE Int.Conf.Robot.Automat.Symposia Millennium Conf.(ICRA), San Francisco, CA, USA, Apr.2000, pp.971-976.

[96] J. Faigl, M. Kulich, and L. Pieucil, “A sensor placement algorithm for a mobile robot inspection planning,” J. Intell.Robotic Syst., vol.62,nos.3-4, pp.329-353, Jun.

[97] Á. Madridano, A. Al-Kaff, D. Martín, and A. D. L. Escalera, “3D trajectory planning method for UA Vs swarm in building emergencies,”Sensors, vol.20, no.3, pp.1-20, Feb. 2020.

[98] T. Zeng and B. Si, “Mobile robot exploration based on rapidly exploring random trees and dynamic window approach,” in Proc. 5th Int.Conf.Control, Autom.Robot.(ICCAR), Beijing, China, Apr.2019,pp.51-57.

[99] L. E. Kavraki, P. Svestka, J.-C. Latombe, and M. H. Overmars, “Probabilistic roadmaps for path planning in high-dimensional configuration spaces,” IEEE Trans.Robot.Autom., vol.12, no.4, pp.566-580,Aug. 1996.

[100] O. Salzman, “Sampling-based robot motion planning,” Commun. ACM,vol.62, no.10, pp.54-63, Sep.

[101] A. Dias, T. Fernandes, J. Almeida, A. Martins, and E. Silva, “3D path planning methods for unmanned aerial vehicles in search and rescue scenarios,” in Human-Centric Robotics, M. F. Silva, G. S. Virk, M. O. Tokhi,B. Malheiro, and P. Guedes, Eds. Singapore: World Scientific, 2017,pp.213-220.

[102] M. Ulrich, G. Lux, L. Jürgensen, and G. Reinhart, “Automated and cycle time optimized path planning for robot-based inspection systems,”Procedia CIRP, vol.44, pp.377-382, May 2016.

[103] S. M. Lavalle and J. J. Kuffner, “Rapidly-exploring random trees:Progress and prospects,” in Algorithmic Comput. Robotics: New Directions, B. Donald, K. Lynch, and D. Rus, Eds. Boca Raton, FL, USA:CRC Press, 2001, pp. 293-308.

[104] M. Elbanhawi and M. Simic, “Sampling-based robot motion planning:A review,” IEEE Access, vol.2, pp.56-77, 2014.

[105] S. Zaheer, J. M, and T. Gulrez, “Performance analysis of path planning techniques for autonomous mobile robots,” in Proc. IEEE Int.Conf. Electr., Comput. Commun. Technol. (ICECCT), Coimbatore, India,Mar. 2015, pp.1-5.

[106] J. J. Kuffner and S. M. LaValle, “RRT-connect: An efficient approach to single-query path planning,” in Proc. Millennium Conf. IEEE Int. Conf.Robot. Automat. Symposia (ICRA), San Francisco, CA, USA, Apr. 2000,pp. 995-1001.

[107] S. Karaman and E. Frazzoli, “Sampling-based algorithms for optimal motion planning,” Int. J. Robot. Res., vol. 30, no.7, pp.846-894,Jun.

[108] A. Bircher, K. Alexis, U. Schwesinger, S. Omari, M. Burri, and R. Siegwart, “An incremental sampling-based approach to inspection
planning: The rapidly exploring random tree of trees,” Robotica, vol.35,no.6, pp.1327-1340, Jun.

[109] Y. Bouzid, Y. Bestaoui, and H. Siguerdidjane, “Quadrotor-UA V optimal coverage path planning in cluttered environment with a limited onboard energy,” in Proc.IEEE/RSJ Int.Conf.Intell.Robots Syst.(IROS),Vancouver, BC, Canada, Sep. 2017, pp.979-984.

[110] M. Fu, A. Kuntz, O. Salzman, and R. Alterovitz, “Toward asymptotically-optimal inspection planning via efficient near-optimal graph search,” in Proc.Robot., Sci.Syst.Conf., Freiburg im Breisgau, Germany, Jun.2019,pp.1-12.

[111] S. Faghihi, S. Tavana, and A. D. Ruiter, “Autonomous on-orbit inspection of complex space structures in deep space environment,” in Proc.71st Int.Astron.Congr.-Cyberspace Ed., Dubai, United Arab Emirates, Oct. 2020,pp.1-10.

[112] H. Liu, J. Ma, and W. Huang, “Sensor-based complete coverage path planning in dynamic environment for cleaning robot,” CAAI Trans. Intell.Technol., vol.3, no.1, pp.65-72, Mar.

[113] K. Yu, C. Guo, and J. Yi, “Complete and near-optimal path planning for simultaneous sensor-based inspection and footprint coverage in robotic
crack filling,” in Proc.Int.Conf.Robot.Autom.(ICRA) , Montreal, QC,Canada, May 2019, pp.8812-8818.

[114] A. Bircher, K. Alexis, M. Burri, P. Oettershagen, S. Omari, T. Mantel, and R. Siegwart, “Structural inspection path planning via iterative viewpoint resampling with application to aerial robotics,” in Proc.IEEE Int.Conf.Robot.Autom.(ICRA), Seattle, WA, USA, May 2015,pp.6423-6430.

[115] A. Bircher, M. Kamel, K. Alexis, M. Burri, P. Oettershagen, S. Omari,T. Mantel, and R. Siegwart, “Three-dimensional coverage path planning via viewpoint resampling and tour optimization for aerial robots,” Auto.Robots, vol.40, no.6, pp.1059-1078, Aug. 2016.

[116] W. Jing, J. Polden, P. Y. Tao, C. F. Goh, W. Lin, and K. Shimada, “Model-based coverage motion planning for industrial 3D shape inspection applications,” in Proc.13th IEEE Conf.Autom.Sci.Eng.(CASE), Xi’an,China, Aug. 2017, pp.1293-1300.

[117] X. Zhou, Z. Yi, Y. Liu, K. Huang, and H. Huang, “Survey on the path and view planning for UA Vs,” Virtual Reality Intell.Hardw., vol.2, no.1,pp.56-69, Feb. 2020.

[118] R. Zeng, Y. Wen, W. Zhao, and Y.-J.Liu, “View planning in robot active vision: A survey of systems, algorithms, and applications,” Comput.Vis.Media, vol.6, no.3, pp.225-245, Sep. 2020.

[119] Y.B. Sebbane, Intelligent Autonomy of UAVs: Advanced Missions and Future Use.Boca Raton, FL, USA: CRC Press, 2018.

[120] W. Jing, J. Polden, W. Lin, and K. Shimada, “Sampling-based view planning for 3D visual coverage task with unmanned aerial vehicle,” in Proc.IEEE/RSJ Int.Conf.Intell.Robots Syst.(IROS) , Daejeon, South Korea,Oct. 2016, pp.1808-1815.

[121] C. Connolly, “The determination of next best views,” in Proc.IEEE Int.Conf.Robot.Autom., St. Louis, MO, USA, Mar.1985, pp.432-435.

[122] A. Bircher, M. Kamel, K. Alexis, H. Oleynikova, and R. Siegwart,-Receding horizon `next-best-view’ planner for 3D exploration,” inProc.IEEE Int.Conf.Robot.Autom., Stockholm, Sweden, May 2016,pp.1462-1468.

[123] S. Song and S. Jo, -Surface-based exploration for autonomous 3D modeling,” in Proc.IEEE Int.Conf.Robot.Autom.(ICRA), Brisbane, QLD Australian, May 2018, pp.4319-4326.

[124] R. Tinos, K. Helsgaun, and D. Whitley, -Efficient recombination in the Lin-Kernighan-Helsgaun traveling salesman heuristic,” in Parallel
Problem Solving from Nature-PPSN XV (Lecture Notes in Computer Science), vol.11101, A. Auger, C. M. Fonseca, N. Lourenco, P. Machado,L. Paquete, and D. Whitley, Eds.Cham, Switzerland: Springer, 2018,pp.95-107.

[125] N. Palomeras, N. Hurtos, E. Vidal, and M. Carreras, -Autonomous exploration of complex underwater environments using a probabilistic next-best-view planner,” IEEE Robot.Autom.Lett., vol.4, no.2,pp.1619-1625, Apr.

[126] S. Osswald, P. Karkowski, and M. Bennewitz, -Efficient coverage of 3D environments with humanoid robots using inverse reachability maps,” in Proc.IEEE-RAS 17th Int.Conf.Humanoid Robot.(Humanoids),Birmingham, U.K., Nov. 2017, pp.151-157.

[127] I. Ardiyanto and J. Miura, -Visibility-based viewpoint planning for guard robot using skeletonization and geodesic motion model,” in Proc.IEEE Int.Conf.Robot.Autom., Karlsruhe, Germany, May 2013, pp.660-666.

[128] I. Ardiyanto and J. Miura, -Time-space viewpoint planning for guard robot with chance constraint,” Int.J. Autom.Comput., vol.16, no.4,pp.475-490, Aug. 2019.

[129] Y. Wang, S. James, E. K. Stathopoulou, C. Beltran-Gonzalez, Y. Konishi,and A. Del Bue, -Autonomous 3-D reconstruction, mapping, and exploration of indoor environments with a robotic arm,” IEEE Robot.Autom.Lett., vol.4, no.4, pp.3340-3347, Oct. 2019.

[130] R. Border, J. D. Gammell, and P. Newman, -Surface edge explorer (see):Planning next best views directly from 3D observations,” in Proc.IEEE Int.Conf.Robot.Autom.(ICRA), Brisbane, QLD, Australia, May 2018,pp.1-8.

[131] C. Wu, R. Zeng, J. Pan, C. C. L. Wang, and Y.-J.Liu, -Plant phenotyping by deep-learning-based planner for multi-robots,” IEEE Robot.Autom.Lett., vol.4, no.4, pp.3113-3120, Oct. 2019.

[132] F. Paus, P. Kaiser, N. Vahrenkamp, and T. Asfour, -A combined approach for robot placement and coverage path planning for mobile manipulation,” in Proc.IEEE/RSJ Int.Conf.Intell.Robots Syst.(IROS), Vancouver,BC, Canada, Sep. 2017, pp.1-8.

[133] S. S. Mansouri, C. Kanellakis, E. Fresk, D. Kominiak, and G. Nikolakopoulos, -Cooperative coverage path planning for visual inspection,” Control Eng.Pract., vol.74, pp.118-131, May 2018.

[134] C. Kanellakis, S. S. Mansouri, E. Fresk, D. Kominiak, and G. Nikolakopoulos, -Cooperative UA Vs as a tool for aerial inspection of large scale aging infrastructure,” in Proc.IEEE/RSJ Int.Conf.Intell. Robots Syst.(IROS), vol.5, M. Hutter and R. Siegwart, Eds.Cham, Switzerland: Springer, Oct. 2018, pp.177-189.

[135] S. Lindner, C. Garbe, and K. Mombaur, -Optimization based multiview coverage path planning for autonomous structure from motion recordings,” IEEE Robot.Autom.Lett., vol.4, no.4, pp.3278-3285,Oct. 2019.

[136] Z. Meng, H. Qin, Z. Chen, X. Chen, H. Sun, F. Lin, and M. H. Ang,-A two-stage optimized next-view planning framework for 3-D unknown environment exploration, and structural reconstruction,” IEEE Robot.Autom.Lett., vol.2, no.3, pp.1680-1687, Jul.

[137] A. Hornung, K. M. Wurm, M. Bennewitz, C. Stachniss, and W. Burgard,-OctoMap: An efficient probabilistic 3D mapping framework based on octrees,” Auton.Robot., vol.34, no.3, pp.189-206, Apr.

[138] R. Almadhoun, T. Taha, J. Dias, L. Seneviratne, and Y. Zweiri, -Coverage path planning for complex structures inspection using an unmanned aerial vehicle (UA V)” in Intelligent Robotics and Applications (Lecture Notes in Computer Science), vol.11744, H. Yu, J. Liu, L. Liu, Z. Ju, Y. Liu, and D. Zhou, Eds.Cham, Switzerland: Springer, 2019, pp.243-266.

[139] C. Papachristos, F. Mascarich, S. Khattak, T. Dang, and K. Alexis,-Localization uncertainty-aware autonomous exploration and mapping with aerial robots using receding horizon path-planning,” Auto.Robots,vol.43, no.8, pp.2131-2161, Dec. 2019.

[140] A. Bircher, M. Kamel, K. Alexis, H. Oleynikova, and R. Siegwart,-Receding horizon path planning for 3D exploration and surface inspection,” Auto.Robots, vol.42, no.2, pp.291-306, Feb.

[141] C. Papachristos, M. Kamel, M. Popovic, S. Khattak, A. Bircher,H. Oleynikova, T. Dang, F. Mascarich, K. Alexis, and R. Siegwart,-Autonomous exploration and inspection path planning for aerial robotsusing the robot operating system,” in Robot Operating System (ROS)(Studies in Computational Intelligence), vol.778, A. Koubaa, Ed.Cham,Switzerland: Springer, 2019, pp.67-111.

[142] S. Jung, S. Song, P. Youn, and H. Myung, -Multi-layer coverage path planner for autonomous structural inspection of high-rise structures,” in Proc.IEEE/RSJ Int.Conf.Intell.Robots Syst.(IROS) , Madrid, Spain,Oct. 2018, pp.1-9.

[143] H. Oleynikova, Z. Taylor, R. Siegwart, and J. Nieto, -Safe local exploration for replanning in cluttered unknown environments for microaerial vehicles,” IEEE Robot.Autom.Lett., vol.3, no.3, pp.1474-1481,Jul.

[144] M. Selin, M. Tiger, D. Duberg, F. Heintz, and P. Jensfelt, -Efficient autonomous exploration planning of large-scale 3-D environments,” IEEE Robot.Autom.Lett., vol.4, no.2, pp.1699-1706, Apr.

[145] T. Dang, S. Khattak, F. Mascarich, and K. Alexis, -Explore locally, plan globally: A path planning framework for autonomous robotic exploration in subterranean environments,” in Proc.19th Int.Conf.Adv.Robot. (ICAR), Belo Horizonte, Brazil, Dec. 2019, pp.9-16.

[146] R. Almadhoun, A. Abduldayem, T. Taha, L. Seneviratne, and Y. Zweiri,-Guided next best view for 3D reconstruction of large complex structures,” Remote Sens., vol.11, no.20, pp.1-20, Oct. 2019.

[147] L. Schmid, M. Pantic, R. Khanna, L. Ott, R. Siegwart, and J. Nieto,-An efficient sampling-based method for online informative path planning in unknown environments,” IEEE Robot.Autom.Lett., vol.5, no.2,pp.1500-1507, Apr.

[148] S. Song, D. Kim, and S. Jo, -Online coverage and inspection planning for 3D modeling,” Auto.Robots, vol.44, no.8, pp.1431-1450, Aug. 2020.

[149] W. Jing, D. Deng, Z. Xiao, Y. Liu, and K. Shimada, -Coverage path planning using path primitive sampling and primitive coverage graph for visual inspection,” in Proc.IEEE/RSJ Int.Conf.Intell.Robots Syst.(IROS), Macau, China, Nov. 2019, pp.1472-1479.

[150] K. Alexis, C. Papachristos, R. Siegwart, and A. Tzes, -Uniform coverage structural inspection path-planning for micro aerial vehicles,” in Proc.IEEE Int.Symp.Intell.Control (ISIC), Sydney, NSW, Australia,Sep. 2015, pp.59-64.

[151] L. Hou, X. Chen, K. Lan, R. Rasmussen, and J. Roberts, -Volumetric next best view by 3D occupancy mapping using Markov chain Gibbs sampler for precise manufacturing,” IEEE Access, vol.7, pp.121949-121960,

[152] M. Corah, C. O’Meadhra, K. Goel, and N. Michael, -Communication-efficient planning and mapping for multi-robot exploration in large environments,” IEEE Robot.Autom.Lett., vol.4, no.2, pp.1715-1721,Apr.

[153] Y. Wu and J. Wang, Algorithm Design Practice for Collegiate Programming Contests and Education.Boca Raton, FL, USA: CRC Press, 2018.

[154] P. Joshi, Artificial Intelligence With Python.Birmingham, U.K.: Packt,

[155] A. Zdesar, S. Blazic, G. Klancar, and I. Skrjanc, Wheeled Mobile Robotics: From Fundamentals Towards Autonomous Systems .Oxford,U.K.: Butterworth-Heinemann, 2017.

[156] G. Zuo, P. Zhang, and J. Qiao, -Path planning algorithm based on sub-region for agricultural robot,” in Proc.2nd Int.Asia Conf.Informat.Control, Autom.Robot.(CAR), Wuhan, China, Mar.2010,pp.197-200.

[157] X. Wang and D. Li, -Coverage path planning for UA Vs in unknown directional regions,” Int.J. Wireless Mobile Comput., vol.8, no.3,pp.285-293, May 2015.

[158] P. S. Pratama, J.-W. Kim, H.-K. Kim, S.-M. Yoon, T.-K. Yeu, S. Hong,S.-J.Oh, and S.-B.Kim, -Path planning algorithm to minimize an overlapped path and turning number for an underwater mining robot,” in Proc.15th Int.Conf.Control, Autom.Syst.(ICCAS), Busan, South Korea,Oct. 2015, pp.499-504.

[159] A. M. Kabir, K. N. Kaipa, J. Marvel, and S. K. Gupta, -Automated planning for robotic cleaning using multiple setups and oscillatory tool motions,” IEEE Trans.Autom.Sci.Eng., vol.14, no.3, pp.1364-1377,Jul.

[160] A. Barrientos, J. Colorado, J. D. Cerro, A. Martinez, C. Rossi, D. Sanz,and J. Valente, -Aerial remote sensing in agriculture: A practical approach to area coverage and path planning for fleets of mini aerial robots,” J.Field Robot., vol.28, no.5, pp.667-689, 2011.

[161] W. Wang, P. Zhang, C. Liang, and Y. Shi, “Design, path planning improvement and test of a portable massage robot on the human back,” Int.J. Adv.Robotic Syst., vol.15, no.4, pp.1-11, Jul.

[162] X. Miao, H.-S. Lee, and B.-Y.Kang, “Multi-cleaning robots using cleaning distribution method based on map decomposition in large environments,” IEEE Access, vol.8, pp.97873-97889, 2020.

[163] M. Zhou and N. Gao, “Research on optimal path based on Dijkstra algorithms,” in Proc.3rd Int.Conf.Mechtron.Eng.Inf.Technol.(ICMEIT),Dalian, China, Mar.2019, pp.884-892.

[164] I. Wieser, A. V. Ruiz, M. Frassl, M. Angermann, J. Mueller, and M. Lichtenstern, “Autonomous robotic SLAM-based indoor navigation for high-resolution sampling with complete coverage,” in Proc.IEEE/ION Position, Location Navigat.Symp., Monterey, CA, USA,May 2014, pp.945-951.

[165] R. Yehoshua, N. Agmon, and G. A. Kaminka, “Robotic adversarial coverage of known environments,” Int.J.Robot.Res., vol.35, no.12,pp.1419-1444, Oct. 2016.

[166] R. Rosa, T. Brito, A. I. Pereira, J. Lima, and M. A. Wehrmeister, “Using multi-UA V for rescue environment mapping: Task planning optimization approach,” in CONTROLO 2020 (Lecture Notes in Electrical Engineering), vol.695, J.A. Gonçalves, M. Braz-César, and J. P. Coelho, Eds.Cham, Switzerland: Springer, 2020, pp.507-517.

[167] X. Zhang, S. Liu, and Z. Xiang, “Optimal inspection path planning of substation robot in the complex substation environment,” in Proc.Chin.Autom.Congr.(CAC), Hangzhou, China, Nov. 2019, pp.5064-5068.

[168] X. Liu and D. Gong, “A comparative study of A-star algorithms for searchand rescue in perfect maze,” in Proc.Int.Conf.Electr.Inf.Control Eng.,Wuhan, China, Apr.2011, pp.24-27.

[169] A. M. Chaudhari, M. R. Apsangi, and A.B. Kudale, “Improved A-star algorithm with least turn for robotic rescue operations,” in Computational
Intelligence, Communications, and Business Analytics (Communications in Computer and Information Science), vol.776, J. Mandal, P. Dutta, and S. Mukhopadhyay, Eds.Singapore: Springer, 2017, pp.614-627.

[170] S. Dogru and L. Marques, “A*-based solution to the coverage path planning problem,” in Proc.3rd Iberian Robot.Conf.(Advances in Intelligent Systems and Computing), vol.693, A. Ollero, A. Sanfeliu,L. Montano, N. Lau, and C. Cardeira, Eds.Cham, Switzerland: Springer,2018, pp.240-248.

[171] H. H. Viet, V.-H. Dang, S. Choi, and T. C. Chung, “BoB: An online coverage approach for multi-robot systems,” Int.J.Speech Technol.,vol. 42, no.2, pp.157-173, Mar.

[172] Z. Cai, S. Li, Y. Gan, R. Zhang, and Q. Zhang, “Research on complete coverage path planning algorithms based on A* algorithms,” Open Cybern.Syst.J., vol.8, no.1, pp.418-426, Dec. 2014.

[173] A. V. Le, V. Prabakaran, V. Sivanantham, and R. E. Mohan, “Modified A-star algorithm for efficient coverage path planning in Tetris inspired self-reconfigurable robot with integrated laser sensor,” Sensors, vol.18,no.8, pp.1-27, Aug. 2018.

[174] A. Stentz, “Optimal and efficient path planning for partially-known environments,” in Proc.IEEE Int.Conf.Robot.Autom., San Diego, CA, USA, May 1994, pp.3310-3317.

[175] M. Dakulovi¢, S. Horvati¢, and I. Petrovi¢, “Complete coverage D* algorithm for path planning of a floor-cleaning mobile robot,” IFAC Proc. Volumes, vol.44, no.1, pp.5950-5955, Jan. 2011.

[176] I. Maurovic, M. Seder, K. Lenac, and I. Petrovic, “Path planning for active SLAM based on the D* algorithm with negative edge weights,” IEEE Trans.Syst., Man, Cybern.Syst., vol.48, no.8, pp.1321-1331,Aug. 2018.

[177] A. T. Le and T. D. Le, “Search-based planning and replanning in robotics and autonomous systems,” in Advanced Path Planning for Mobile Entities, R. Roka, Ed.London, U.K.: IntechOpen, 2018, pp.63-89.

[178] C. Luo, H. Mo, F. Shen, and W. Zhao, “Multi-goal motion planning of an autonomous robot in unknown environments by an ant colony optimization approach,” in Advances in Swarm Intelligence (Lecture Notes in Computer Science), vol.9713, Y. Tan, Y. Shi, and L. Li, Eds. Cham, Switzerland: Springer, 2016, pp.519-527.

[179] M.-K. Ng, Y.-W. Chong, K.-M. Ko, Y.-H. Park, and Y.-B. Leau, “Adaptive path finding algorithm in dynamic environment for warehouse robot,”Neural Comput.Appl., vol.32, no.17, pp.13155-13171, Sep. 2020.

[180] K. Daniel, A. Nash, S. Koenig, and A. Felner, “Theta*: Any-angle path planning on grids,” J. Artif.Intell.Res., vol.39, pp.533-579, Oct. 2010.

[181] S. Choi, S. Lee, H. H. Viet, and T. Chung, “B-Theta*: An efficient online coverage algorithm for autonomous cleaning robots,” J. Intell. Robotic Syst., vol.87, no.2, pp.265-290, Aug.

[182] Y.-C. Huang and H.-Y.Lin, “Development and implementation of a multi-robot system for collaborative exploration and complete coverage,” in Proc.14th Int.Conf.Signal-Image Technol.Internet-Based Syst.(SITIS), Las Palmas, Spain, Nov. 2018, pp.472-479.

[183] M. Faria, I. Maza, and A. Viguria, “Applying frontier cells based exploration and Lazy Theta* path planning over single grid-based world representation for autonomous inspection of large 3D structures with an UAS,”J. Intell.Robotic Syst., vol.93, nos.1-2, pp.113-133, Feb. 2019.

[184] M. Faria, R. Marín, M. Popovic, I. Maza, and A. Viguria, “Efficient Lazy Theta* path planning over a sparse grid to explore large 3D volumes with a multirotor UA V,” Sensors, vol.19, no.1, pp.1-21, Jan. 2019.

[185] M. Faria, A. S. Ferreira, H. P. Leon, I. Maza, and A. Viguria, “Autonomous 3D exploration of large structures using a UA V equipped with a 2D LIDAR,” Sensors, vol.19, no.22, pp.1-24, Nov. 2019.

[186] S. Mirjalili, Evolutionary Algorithms, and Neural Networks: Theory and Applications. Cham, Switzerland: Springer, 2019.

[187] B. M. Wilamowski and J. D. Irwin, The Industrial Electronics Handbook: Intelligent Systems, 2nd ed.Boca Raton, FL, USA: CRC Press, 2011.

[188] J. H. Holland, Adaptation in Natural and Artificial Systems: An Introductory Analysis With Applications to Biology, Control, and Artificial Intelligence.Cambridge, U.K.: MIT Press, 1992.

[189] C. García-Martínez, F. J. Rodriguez, and M. Lozano, “Genetic algorithms,” in Handbook of Heuristics, R. Martí, P. Pardalos, and M. Resende, Eds.Cham, Switzerland: Springer, 2018, pp.431-464.

[190] Z. Wang and Z. Bo, “Coverage path planning for mobile robot based on genetic algorithm,” in Proc.IEEE Workshop Electron., Comput.Appl.,Ottawa, ON, Canada, May 2014, pp.732-735.

[191] I.A. Hameed, D. D. Bochtis, and C. G. Sorensen, “Driving angle and track sequence optimization for operational path planning using genetic algorithms,” Appl.Eng.Agricult., vol.27, no.6, pp.1077-1086, Nov. 2011.

[192] I.A. Hameed, D. D. Bochtis, and C. G. Sorensen, “An optimized field coverage planning approach for navigation of agricultural robots in fields involving obstacle areas,” Int.J. Adv.Robotic Syst., vol.10, no.5, pp.1-9,May 2013.

[193] M. Shen, S. Wang, S. Wang, and Y. Su, “Simulation study on coverage path planning of autonomous tasks in hilly farmland based on energy consumption model,” Math.Problems Eng., vol.2020, pp.1-15,Aug. 2020.

[194] K. O. Ellefsen, H. A. Lepikson, and J. C. Albiez, “Multiobjective coverage path planning: Enabling automated inspection of complex, real-world structures,” Appl.Soft Comput., vol.61, pp.264-282, Dec. 2017.

[195] W.-C. Tung and J.-S. Liu, “Genetic algorithm with modified operators for an integrated traveling salesman and coverage path planning problem,” in Proc.16th Int.Conf.Appl.Comput., Cagliari, Italy, Nov. 2019,pp.205-216.

[196] L. Qiu, “Research on a hierarchical cooperative algorithm based on genetic algorithm and particle swarm optimization,” in Computational Intelligence and Intelligent Systems (Communications in Computer and Information Science), vol.874, K. Li, W. Li, Z. Chen, and Y. Liu, Eds. Singapore: Springer, 2018, pp.16-25.

[197] M. G. Sadek, A. E. Mohamed, and A. M. El-Garhy, “Augmenting multi-objective genetic algorithm and dynamic programming for online coverage path planning,” in Proc.13th Int.Conf.Comput.Eng.Syst.(ICCES),Cairo, Egypt, Dec. 2018, pp.475-480.

[198] C.-T. Cheng, K. Fallahi, H. Leung, and C. K. Tse, “A genetic algorithm-inspired UUV path planner based on dynamic programming,” IEEE Trans.Syst., Man, Cybern.C, Appl.Rev., vol.42, no.6, pp.1128-1134,Nov. 2012.

[199] V. R. Batista and F. A. Zampirolli, “Optimising robotic pool-cleaning with a genetic algorithm,” J. Intell.Robotic Syst., vol.95, no.2,pp.443-458, Aug. 2019.

[200] X. L. Hu and Z. Lin, “Coverage path planning of Penaeus vannamei feeding based on global and multiple local areas,” in Data Science (Communications in Computer and Information Science), vol.1179,J.He, P. S. Yu, Y. Shi, X. Li, Z. Xie, G. Huang, J. Cao, and X. Fu, Eds.Singapore: Springer, 2020, pp.687-697.

[201] C. Liu, W. Xie, P. Zhang, Q. Guo, and D. Ding, “Multi-UA Vs cooperative coverage reconnaissance with neural network and genetic algorithm,” inProc.3rd High Perform.Comput.Cluster Technol.Conf., Guangzhou,China, Jun.2019, pp.81-86.

[202] R. Storn and K. Price, “Differential evolution-A simple and efficient heuristic for global optimization over continuous spaces,” J.Global Optim., vol.11, no.4, pp.341-359, Dec. 1997.

[203] D. Alvarez, J. V. Gomez, S. Garrido, and L. Moreno, “Geometrically constrained path planning with fast marching square,” in Proc.23rdMedit.Conf.Control Autom.(MED), Torremolinos, Spain, Jun.2015,pp.1014-1019.

[204] K. Price, R. M. Storn, and J.A. Lampinen, Differential Evolution:A Practical Approach to Global Optimization.Berlin, Germany: Springer,

[205] J. Vesterstrom and R. Thomsen, “A comparative study of differential evolution, particle swarm optimization, and evolutionary algorithms on numerical benchmark problems,” in Proc.Congr.Evol.Comput.,Portland, OR, USA, Jun.2004, pp.1980-1987.

[206] P. Xiao, H. Ju, Q. Li, and F. Chen, “Task planning of space-robot clusters based on modified differential evolution algorithm,” Appl. Sci., vol.10,no.14, pp.1-24, Jul.

[207] V. Gonzalez, C. A. Monje, S. Garrido, L. Moreno, and C. Balaguer,”Coverage mission for UA Vs using differential evolution and fast marching square methods,” IEEE Aerosp.Electron.Syst.Mag., vol.35, no.2,pp.18-29, Feb. 2020.

[208] G. Beni and J. Wang, “Swarm intelligence in cellular robotics system,”inRobots and Biological Systems: Towards a New Bionics?(NATO ASISeries), vol.102, P. Dario, G. Sandini and P. Aebischer, Eds.Berlin,Germany: Springer, 1993, pp.703-712.

[209] E. Cuevas, F. Fausto, and A. Gonzalez, New Advancements in Swarm Algorithms: Operators and Applications (Intelligent Systems Reference Library).Cham, Switzerland: Springer, 2020.

[210] E. Bonabeau, M. Dorigo, and G. Theraulaz, Swarm Intelligence: From Natural to Artificial Systems.London, U.K.: Oxford Univ.Press,

[211] C. Blum and X. Li, “Swarm intelligence in optimization,” in Swarm Intelligence (Natural Computing Series), C. Blum, and D. Merkle, Eds.Berlin, Germany: Springer, 2008, pp.43-85.

[212] J. Kennedy and R. C. Eberhart, “Particle swarm optimization,” in Proc.IEEE Int.Conf.Neural Netw., Perth, WA, Australia, Nov. 1995, pp.1942-1948.

[213] M. Dorigo and T. Stützle, Ant Colony Optimization.Cambridge, MA,USA: MIT Press, 2004.

[214] D. Teodorovi¢, “Bee colony optimization (BCO),” in Innovations in Swarm Intelligence (Studies in Computational Intelligence), vol.248, C. Lim, L. Jain, and S. Dehuri, Eds.Berlin, Germany: Springer, 2009,pp.39-60.

[215] J. Kennedy, “The particle swarm: Social adaptation of knowledge,” in Proc.IEEE Int.Conf.Evol.Comput., Indianapolis, IN, USA, Apr.1997,pp.303-308.

[216] T.-K. Lee, S.-H. Baek, Y.-H. Choi, and S.-Y.Oh, “Smooth coverage path planning and control of mobile robots based on high-resolution grid map representation,” Robot.Auto.Syst., vol.59, no.10, pp.801-812,Oct. 2011.

[217] S. Sharma, C. Sur, A. Shukla, and R. Tiwari, “Multi-robot area exploration using particle swarm optimization with the help of CBDF-based robot scattering,” in Computational Vision and Robotics (Advances in Intelligent Systems and Computing), vol.332, I. K. Sethi, Ed.New Delhi,India: Springer, 2015, pp.113-123.

[218] S. Sahu and B.B. Choudhury, “PSO based path planning of a six-axis industrial robot,” in Computational Intelligence in Data Mining (Advances in Intelligent Systems and Computing), vol.990, H. Behera,J. Nayak, B. Naik, and D. Pelusi, Eds.Singapore: Springer, 2020,pp.213-220.

[219] Y.-H. Lin, S.-M. Wang, L.-C. Huang, and M.-C. Fang, “Applying the stereo-vision detection technique to the development of underwater inspection task with PSO-based dynamic routing algorithm for autonomous underwater vehicles,” Ocean Eng., vol.139, pp.127-139,Jul.

[220] Y. H. Lin, L. C. Huang, S. Y. Chen, and C. M. Yu, “The optimal route planning for inspection task of autonomous underwater vehicle composed of MOPSO-based dynamic routing algorithm in currents,” Appl.Ocean.Res., vol.75, pp.178-192, Jun.

[221] S. Wang, Y. Bai, and C. Zhou, “Coverage path planning design of mapping UA Vs based on particle swarm optimization algorithm,”in Proc.Chin.Control Conf.(CCC), Guangzhou, China, Jul.2019,pp.8236-8241.

[222] M. S. Couceiro, R. P. Rocha, and N. M. F. Ferreira, “A novel multi-robot exploration approach based on particle swarm optimization algorithms,”inProc.IEEE Int.Symp.Saf., Secur., Rescue Robot., Kyoto, Japan,Nov. 2011, pp.327-332.

[223] Z. Shang, J. Bradley, and Z. Shen, “A co-optimal coverage path planning method for aerial scanning of complex structures,” Expert Syst.Appl.,vol.158, pp.1-16, Nov. 2020.

[224] F. van den Bergh and A. P. Engelbrecht, “A cooperative approach to particle swarm optimization,” IEEE Trans.Evol.Comput., vol.8, no.3, pp.225-239, Jun.

[225] X. Li and X. Yao, “Cooperatively co-evolution particle swarms for large scale optimization,” IEEE Trans.Evol.Comput., vol.16, no.2,pp.210-224, Apr.

[226] G. Sun, R. Zhou, B.Di, Z. Dong, and Y. Wang, “A novel cooperative path planning for multi-robot persistent coverage with obstacles and coverage period constraints,” Sensors, vol.19, no.9, pp.1-28, May 2019.

[227] M. Dorigo, M. Birattari, and T. Stutzle, “Ant colony optimization,” IEEE Comput.Intell.Mag., vol.1, no.4, pp.28-39, Nov. 2006.

[228] H. Duan, “Ant colony optimization: Principle, convergence and application,” in Handbook of Swarm Intelligence (Adaptation, Learning, and Optimization), vol.8, B. K. Panigrahi, Y. Shi, and M. H. Lim, Eds.Berlin,Germany: Springer, 2011, pp.373-388.

[229] J. Ning, Q. Zhang, C. Zhang, and B. Zhang, “A best-path-updating information-guided ant colony optimization algorithm,” Inf.Sci.,vols.433-434, pp.142-162, Apr.

[230] A. Borisenko and S. Gorlatch, “Optimizing a GPU-parallelized ant colony metaheuristic by parameter tuning,” in Parallel Computing Technologies (Lecture Notes in Computer Science), vol.11657, V. Malyshkin,Ed.Cham, Switzerland: Springer, 2019, pp.151-165.

[231] M. Starzec, G. Starzec, A. Byrski, and W. Turek, “Distributed ant colony optimization based on actor model,” Parallel Comput., vol.90, pp.1-13,Dec. 2019.

[232] C. Pan, H. Wang, J. Li, and M. Korovkin, “Path planning of mobile robot based on an improved ant colony algorithm,” in Convergent Cognitive Information Technologies (Communications in Computer and Information Science), vol.1140, V. Sukhomlin and E. Zubareva, Eds.Cham,Switzerland: Springer, 2020, pp.132-141.

[233] B. Li and T. Li, “Vehicle path optimization with time window based on improved ant colony algorithm,” in Data Processing Techniques and Applications for Cyber-Physical Systems (Advances in Intelligent Systems and Computing), vol.1088, C. Huang, Y. W. Chan, and N. Yen,Eds.Singapore: Springer, 2020, pp.167-175.

[234] W. Zhang, X. Gong, G. Han, and Y. Zhao, “An improved ant colony algorithm for path planning in one scenic area with many spots,” IEEE Access, vol.5, pp.13260-13269, 2017.

[235] Z. Chibin, W. Xingsong, and D. Yong, “Complete coverage path planning based on ant colony algorithm,” in Proc.15th Int.Conf.Mechtron.Mach. Vis.Pract., Auckland, New Zealand, Dec. 2008, pp.357-361.

[236] K. Zhou, A. L. Jensen, C. G. Sørensen, P. Busato, and D. D. Bothtis, “Agricultural operations planning in fields with multiple obstacle areas,” Comput.Electron.Agricult., vol.109, pp.12-22, Nov. 2014.

[237] S.-H. Huang, Y.-H. Huang, C. A. Blazquez, and G. Paredes-Belmar, “Application of the ant colony optimization in the resolution of the bridge inspection routing problem,” Appl.Soft Comput., vol.65, pp.443-461,Apr.

[238] T. Stützle and H. H. Hoos, “MAX-MIN ant system,” Future Generat.Comput.Syst., vol.16, no.8, pp.889-914, Jun.

[239] M. Karakaya, “UA V route planning for maximum target coverage,” Comput.Sci.Eng., Int.J., vol.4, no.1, pp.27-34, Feb. 2014.

[240] G. S. Tewolde and W. Sheng, “Robot path integration in manufacturing processes: Genetic algorithm versus ant colony optimization,” IEEE Trans.Syst., Man, Cybern.A, Syst.Humans, vol.38, no.2, pp.278-287,Mar.

[241] W. Chen, J. Liu, Y. Tang, and H. Ge, “Automatic spray trajectory optimization on Bézier surface,” Electronics, vol.8, no.2, pp.1-16, Feb. 2019.

[242] C. Gao, Y. Kou, Z. Li, A. Xu, Y. Li, and Y. Chang, “Optimal multirobot coverage path planning: Ideal-shaped spanning tree,” Math. ProblemsEng., vol.2018, pp.1-10, Sep. 2018.

[243] J. Dentler, M. Rosalie, G. Danoy, P. Bouvry, S. Kannan,M. A. Olivares-Mendez, and H. Voos, “Collision avoidance effects on the mobility of a UA V swarm using chaotic ant colony with model predictive control,” J. Intell.Robotic Syst., vol.93, nos.1-2, pp.227-243,Feb. 2019.

[244] A. V. Le, P. C. Ku, T. T. Tun, N. H. K. Nhan, Y. Shi, and R. E. Mohan,”Realization energy optimization of complete path planning in differential drive-based self-reconfigurable floor cleaning robot,” Energies,vol.12, no.6, pp.1-23, Mar.2019.

[245] A. V. Le, N. H. K. Nhan, and R. E. Mohan, “Evolutionary algorithm-based complete coverage path planning for tetriamond tiling robots,” Sensors, vol.20, no.2, pp.1-14, Jan. 2020.

[246] A. V. Le, R. Parween, R. E. Mohan, N. H. K. Nhan, and R. E. Abdulkader, “Optimization complete area coverage by reconfiguring hTrihex tiling robot,” Sensors, vol.20, no.11, pp.1-20, Jun.

[247] G. Han, Z. Zhou, T. Zhang, H. Wang, L. Liu, Y. Peng, and M. Guizani, “Ant-colony-based complete-coverage path-planning algorithm for underwater gliders in ocean areas with thermoclines,” IEEE Trans.Veh.Technol., vol.69, no.8, pp.8959-8971,Aug. 2020.

[248] I. Caliskanelli, B. Broecker, and K. Tuyls, “Multi-robot coverage: A bee pheromone signaling approach,” in Artificial Life and Intelligent Agents (Communications in Computer and Information Science), vol.519,C. J. Headleand, W. J. Teahan, and L. A. Cenydd, Eds.Cham, Switzerland: Springer, 2015, pp.124-140.

[249] D. Karaboga and B. Basturk, “A powerful and efficient algorithm for numerical function optimization: Artificial bee colony (ABC) algorithm,” J.Global Optim., vol.39, no.3, pp.459-471, Apr.

[250] B. Broecker, I. Caliskanelli, K. Tuyls, E. I. Sklar, and D. Hennes, “Hybrid insect-inspired multi-robot coverage in complex environments,” inTowards Autonomous Robotic Systems (Lecture Notes in Computer Science), vol.9287, C. Dixon and K. Tuyls, Eds.Cham, Switzerland:Springer, 2015, pp.56-68.

[251] X. S. Yang, Nature-Inspired Metaheuristic Algorithms.Frome, U.K.:Luniver Press, 2008.

[252] F. De Rango, N. Palmieri, X. S. Yang, and S. Marano, “Bio-inspired exploring and recruiting tasks in a team of distributed robots over mined regions,” in Proc.Int.Symp.Perform.Eval.Comput.Telecommun.Syst.(SPECTS), Chicago, IL, USA, Jul.2015, pp.1-8.

[253] N. Palmieri, F. de Rango, X.She Yang, and S. Marano, “Multirobot cooperative tasks using combined nature-inspired techniques,” in Proc.7th Int.Joint Conf.Comput.Intell., Lisbon, Portugal, Nov. 2015, pp.74-82.

[254] N. Palmieri, X.-S. Yang, F. D. Rango, and S. Marano, “Comparison of bio-inspired algorithms applied to the coordination of mobile robots considering the energy consumption,” Neural Comput.Appl., vol.31, no.1, pp.263-286, Jan. 2019.

[255] M. M. Gangadharan and A. Salgaonkar, “Ant colony optimization and firefly algorithms for robotic motion planning in dynamic environments,”Eng.Rep., vol.2, no.3, pp.1-23, Mar.

[256] J. Henrio, T. Deligne, T. Nakashima, and T. Watanabe, “Route planning for multiple surveillance autonomous drones using a discrete firefly algorithm and a Bayesian optimization method,” Artif.Life Robot., vol.24,no.1, pp.100-105, Mar.

[257] S. Mirjalili, S. M. Mirjalili, and A. Lewis, “Grey wolf optimizer,” Adv.Eng.Softw., vol.69, pp.46-61, Mar.

[258] K. Albina and S. G. Lee, “Hybrid stochastic exploration using Grey Wolf optimizer and coordinated multi-robot exploration algorithms,” IEEE Access, vol.7, pp.14246-14255, 2019.

[259] R. K. Dewangan, A. Shukla, and W. W. Godfrey, “Three dimensional path planning using grey wolf optimizer for UA Vs,” Int.J.Speech Technol.,vol.49, no.6, pp.2201-2217, Jun.

[260] A. Kamalova, S. Navruzov, D. Qian, and S. G. Lee, “Multi-robot exploration based on multi-objective grey wolf optimizer,” Appl.Sci., vol.9,no.14, pp.1-19, Jul.

[261] F. Ge, K. Li, W. Xu, and Y. Wang, “Path planning of UA V for oilfield inspection based on improved grey wolf optimization algorithm,” in Proc.Chin.Control Decis.Conf.(CCDC), Nanchang, China, Jun.2019,pp.3666-3671.

[262] A. Kamalova, K. D. Kim, and S. G. Lee, “Waypoint mobile robot exploration based on biologically inspired algorithms,” IEEE Access, vol.8,pp.190342-190355, 2020.

[263] A. R. Mehrabian and C. Lucas, “A novel numerical optimization algorithm inspired from weed colonization,” Ecol.Inform., vol.1, no.4,pp.355-366, Dec. 2006.

[264] P. K. Mohanty and D. R. Parhi, “A new efficient optimal path planner for mobile robot based on invasive weed optimization algorithm,” Frontiers Mech.Eng., vol.9, no.4, pp.317-330, Aug. 2014.

[265] P. K. Mohanty, S. Kumar, and D. R. Parhi, “A new ecologically inspiredalgorithm for mobile robot navigation,” in Proc.3rd Int. Conf.FrontiersIntell.Comput.Appl., in Advances in Intelligent Systems and Computing,vol.327, S. Satapathy, B. Biswal, S. Udgata, and J. Mandal, Eds.Cham,Switzerland: Springer, 2014, pp.755-762.

[266] Y. Zhou, Q. Luo, H. Chen, A.He, and J. Wu, “A discrete invasive weed optimization algorithm for solving traveling salesman problem,” Neurocomputing, vol.151, no.3, pp.1227-1236, Mar.

[267] M. R. Ghalenoei, H. Hajimirsadeghi, and C. Lucas, “Discrete invasive weed optimization algorithm: Application to cooperative multiple task assignment of UA Vs,” in Proc.48h IEEE Conf.Decis.Control (CDC),28th Chin. Control Conf., Shanghai, China, Dec. 2009, pp.1665-1670.

[268] Y. Zhuang, C. Wu, H. Wu, H. Chu, Y. Gao, and L. Li, “The repair strategyfor event coverage holes based on mobile robots in wireless sensor and robot networks,” Sensors, vol.19, no.22, pp.1-21, Nov. 2019.

[269] K. Sandamurthy and K. Ramanujam, “A hybrid weed optimized coverage path planning technique for autonomous harvesting in cashew orchards,” Inf.Process.Agricult., vol.7, no.1, pp.152-164, Mar.

[270] S. X. Yang and C. Luo, “A neural network approach to complete coverage path planning,” IEEE Trans.Syst., Man, Cybern., vol.34, no.1,pp.718-725, Jan. 2004.

[271] C. Luo and S. X. Yang, “A bioinspired neural network for real-time concurrent map building and complete coverage robot navigation in unknown environments,” IEEE Trans.Neural Netw., vol.19, no.7, pp.1279-1298,Jul.

[272] G. Hu, Z. Hu, and H. Wang, “Complete coverage path planning for road cleaning robot,” in Proc.Int.Conf.Netw., Sens.Control (ICNSC), Chicago, IL, USA, Apr.2010, pp.643-648.

[273] K. Chen and Y. Liu, “Optimal complete coverage planning of wall-climbing robot using improved biologically inspired neural network,”in Proc.IEEE Int.Conf.Real-time Comput.Robot.(RCAR), Okinawa,Japan, Jul.2017, pp.587-592.

[274] M. Z. Yan, D. Q. Zhu, and S. X. Yang, “Complete coverage path planning in an unknown underwater environment based on D-S data fusion real-time map building,” Int.J. Distrib.Sensor Netw., vol.8, no.10, pp.1-11,Oct. 2012.

[275] C. Luo, S. X. Yang, X. Li, and M. Q.-H. Meng, “Neural-dynamics-driven complete area coverage navigation through cooperation of multiple mobile robots,” IEEE Trans.Ind.Electron., vol.64, no.1, pp.750-760,Jan. 2017.

[276] C. Yang, Y. Tang, L. Zhou, and X. Ma, “Complete coverage path planning based on bioinspired neural network and pedestrian location prediction,”inProc.IEEE 8th Annu.Int.Conf.Technol.Autom., Control, Intell.Syst.(CYBER), Tianjin, China, Jul.2018, pp.528-533.

[277] A. Singha, A. K. Ray, and A.B. Samaddar, “Neural dynamics-based complete coverage of grid environment by mobile robots,” in Proc.Int.Conf.Frontiers Comput.Syst., in Advances in Intelligent Systems and Computing, vol.1255, D. Bhattacharjee, D. K. Kole, N. Dey, S. Basu, and D. Plewczynski, Eds.Singapore: Springer, 2021, pp.411-421.

[278] D. Zhu, C. Tian, B.Sun, and C. Luo, “Complete coverage path planning of autonomous underwater vehicle based on GBNN algorithm,” J. Intell. Robotic Syst., vol.94, no.1, pp.237-249, Apr.

[279] B.Sun, X. Zhu, W. Zhang, D. Zhu, and Z. Chu, “Three dimensional AUV complete coverage path planning with Glasius bio-inspired neuralnetwork,” in Intelligent Robotics and Applications (Lecture Notes in Artificial Intelligence), vol.10985, Z. Chen, A. Mendes, Y. Yan, andS. Chen, Eds.Cham, Switzerland: Springer, Aug. 2018, pp.125-136.

[280] B.Sun, D. Zhu, C. Tian, and C. Luo, “Complete coverage autonomous underwater vehicles path planning based on Glasius bio-inspired neural network algorithm for discrete and centralized programming,” IEEE Trans.Cogn.Develop.Syst., vol.11, no.1, pp.73-84, Mar.

[281] B. Kwon and J. Thangavelautham, “Autonomous coverage path planning using artificial neural tissue for aerospace applications,” in Proc. IEEEAerosp.Conf., Big Sky, MT, USA, Mar.2020, pp.1-10.

[282] S. M. B. P. Samarakoon, M. A. V. J. Muthugala, A. V. Le, and M. R. Elara,”hTetro-Infi: A reconfigurable floor cleaning robot with infinite morphologies,” IEEE Access, vol.8, pp.69816-69828, 2020.

[283] M. A. V. J. Muthugala, S. M. B. P. Samarakoon, and M. R. Elara, “Trade-off between area coverage and energy usage of a self-reconfigurable floor cleaning robot based on user preference,” IEEE Access, vol.8, pp.76267-76275, 2020.

[284] R. S. Sutton and A. G. Barto, Reinforcement Learning: An Introduction,2nd ed.Cambridge, MA, USA: MIT Press, 2018.

[285] J. Kober, J.A. Bagnell, and J. Peters, “Reinforcement learning in robotics:A survey,” Int.J.Robot.Res., vol.32, no.11, pp.1238-1274, Sep. 2013.

[286] A. Gosavi, “Solving Markov decision processes via simulation,” in Handbook of Simulation Optimization: International Series in Operations Research & Management Science, vol.216, M. C. Fu, Ed.New York, NY,USA: Springer, 2015, pp.341-379.

[287] E. Barrett and S. Linder, “Autonomous HV AC control, a reinforcement learning approach,” in Machine Learning and Knowledge Discovery in Databases (Lecture Notes in Computer Science), vol.9286, A. Bifet, M. May, B. Zadrozny, R. Gavalda, D. Pedreschi, F. Bonchi, J. Cardoso, and M. Spiliopoulou, Eds.Cham, Switzerland: Springer, 2015, pp.3-19.

[288] R. Shakeri, M. A. Al-Garadi, A. Badawy, A. Mohamed, T. Khattab, A. K. Al-Ali, K. A. Harras, and M. Guizani, “Design challenges of multi-UAV systems in cyber-physical applications: A comprehensive surveyand future directions,” IEEE Commun.Surveys Tuts., vol.21, no.4,pp.3340-3385, Jun.

[289] W. Jing, C. F. Goh, M. Rajaraman, F. Gao, S. Park, Y. Liu, and K. Shimada, “A computational framework for automatic online path generation of robotic inspection tasks via coverage planning and reinforcement learning,” IEEE Access, vol.6, pp.54854-54864, 2018.

[290] A. V. Le, R. Parween, P. T. Kyaw, R. E. Mohan, T. H. Q. Minh, andC. S. C. S. Borusu, “Reinforcement learning-based energy-aware area coverage for reconfigurable hRombo tiling robot,” IEEE Access, vol.8,pp.209750-209761, 2020.

[291] X. Xia, T. Roppel, J. Y.Hung, J. Zhang, S. C. G. Periaswamy, and J. Patton, “Balanced map coverage using reinforcement learning in repeated obstacle environments,” in Proc.29th IEEE Int.Symp.Ind. Electron., Delft, The Netherlands, Jun.2020, pp.41-48.

[292] L. Piardi, J. Lima, A. I. Pereira, and P. Costa, “Coverage path planning optimization based on Q-learning algorithm,” in Proc. CENTRAL Eur.Symp.Thermophys.(CEST), Rhodes, Greece, Sep. 2019, pp.1-4.

[293] J. Xiao, G. Wang, Y. Zhang, and L. Cheng, “A distributed multi-agent dynamic area coverage algorithm based on reinforcement learning,” IEEE Access, vol.8, pp.33511-33521, 2020.

[294] L. Tai and M. Liu, “Mobile robots exploration through CNN-based reinforcement learning,” Robot.Biomimetics, vol.3, no.1, pp.1-8,Dec. 2016.

[295] J. Xin, H. Zhao, D. Liu, and M. Li, “Application of deep reinforcement learning in mobile robot path planning,” in Proc. Chin.Autom.Congr.(CAC), Jinan, China, Oct. 2017, pp.7112-7116.

[296] S. Y. Luis, D. G. Reina, and S. L. T. Marin, “A deep reinforcement learning approach for the patrolling problem of water resources through autonomous surface vehicles: The Ypacarai lake case,” IEEE Access, vol.8, pp.204076-204093, 2020.

[297] C. Piciarelli and G. L. Foresti, “Drone patrolling with reinforcement learning,” in Proc.13th Int.Conf.Distrib.Smart Cameras, Trento, Italy, Sep. 2019, pp.1-6.

[298] X. Chen, T. M. Tucker, T. R. Kurfess, and R. Vuduc, “Adaptive deep path: Efficient coverage of a known environment under various configurations,” in Proc.IEEE/RSJ Int.Conf.Intell.Robots Syst.(IROS) , Macau,China, Nov. 2019, pp.3549-3556.

[299] C. Wang, L. Wei, Z. Wang, M. Song, and N. Mahmoudian, “Reinforcement learning-based multi-AUV adaptive trajectory planning for under ice field estimation,” Sensors, vol.18, no.11, pp.1-19, Nov. 2018.

[300] J. Hu, H. Niu, J. Carrasco, B. Lennox, and F. Arvin, “Voronoi-based multi-robot autonomous exploration in unknown environments via deep reinforcement learning,” IEEE Trans.Veh.Technol., vol.69, no.12,pp.14413-14423, Oct. 2020.

[301] F. Niroui, K. Zhang, Z. Kashino, and G. Nejat, “Deep reinforcement learning robot for search and rescue applications: Exploration in unknown cluttered environments,” IEEE Robot.Autom.Lett., vol.4,no.2, pp.610-617, Apr.

[302] X. Cao, C. Sun, and M. Yan, “Target search control of AUV in underwater environment with deep reinforcement learning,” IEEE Access, vol.7,pp.96549-96559, 2019.

[303] A. K. Lakshmanan, R. E. Mohan, B. Ramalingam, A. V. Le,P. Veerajagadeshwar, K. Tiwari, and M. Ilyas, “Complete coverage path planning using reinforcement learning for Tetromino based cleaning and maintenance robot,” Autom.Construct., vol.112, pp.1-11,Apr.

[304] P. T. Kyaw, A. Paing, T. T. Thu, R. E. Mohan, A. V. Le, and P. Veerajagadheswar, “Coverage path planning for decomposition reconfigurable grid-maps using deep reinforcement learning based travelling salesman problem,” IEEE Access, vol.8, pp.225945-225956,

[305] A. Koval, S. S. Mansouri, and G. Nikolakopoulos, “Online multiagent based cooperative exploration and coverage in complex environment,” in Proc.18th Eur.Control Conf.(ECC), Naples, Italy, Jun.2019,pp.3964-3969.

[306] F. Balampanis, I. Maza, and A. Ollero, “Spiral-like coverage path planning for multiple heterogeneous UAS operating in coastal regions,”in Proc.Int.Conf.Unmanned Aircr.Syst.(ICUAS), Miami, FL, USA,Jun.2017, pp.617-624.

[307] M. Hassan and D. Liu, “A deformable spiral based algorithm to smooth coverage path planning for marine growth removal,” in Proc. IEEE/RSJ Int.Conf.Intell.Robots Syst.(IROS), Madrid, Spain, Oct. 2018,pp.1913-1918.

[308] M. Hassan, D. Liu, and X. Chen, “Squircular-CPP: A smooth coverage path planning algorithm based on squircular fitting and spiral path,” in Proc.IEEE/ASME Int.Conf.Adv.Intell.Mechtron.(AIM) , Boston, MA,USA, Jul.2020, pp.1075-1081.

[309] V. G. Nair and K. R. Guruprasad, “GM-VPC: An algorithm for multi-robot coverage of known spaces using generalized Voronoi partition,”Robotica, vol.38, no.5, pp.845-860, May 2020.

[310] E. Ferranti, N. Trigoni, and M. Levene, “Brick& mortar: An on-line multi-agent exploration algorithm,” in Proc.IEEE Int.Conf.Robot.Autom., Roma, Italy, Apr.2007, pp.761-767.

[311] M. Becker, F. Blatt, and H. Szczerbicka, “A multi-agent flooding algorithm for search and rescue operations in unknown terrain,” in Multiagent System Technologies (Lecture Notes in Computer Science), vol.8076, M. Klusch, M. Thimm, and M. Paprzycki, Eds.Berlin,Germany: Springer, 2013, pp.19-28.

[312] F. Blatt and H. Szczerbicka, “Combining the multi-agent flood algorithmnwith frontier-based exploration in search & rescue applications,” in Proc.Int.Symp.Perform.Eval.Comput.Telecommun.Syst.(SPECTS), Seattle, WA, USA, Jul.2017, pp.1-7.

[313] Z. Xiao, Z. Wang, D. Liu, Z. Niu, and D. Cao, “A PCB-oriented path planning for AOI full coverage field of view,” in Proc.IEEE 3rd Adv. Inf.Manage., Communicates, Electron.Autom.Control Conf.(IMCEC), Chongqing, China, Oct. 2019, pp.586-592.

[314] C. V. Meaclem, X. Q. Chen, S. Gutschmidt, C. Hann, and R. Parker,”K-means partitioned space path planning (KPSPP) for autonomous robotic harvesting,” Int.J. Adv.Robotic Syst., vol.12, no.11, pp.1-10,Nov. 2015.

[315] Y. Ding, R. Cao, S. Liang, F. Qi, Q. Yang, and W. Yan, “Density-based optimal UA V path planning for photovoltaic farm inspection in complex topography,” in Proc.Chin.Control Decis.Conf.(CCDC), Hefei, China,Aug. 2020, pp.3931-3936.

[316] Y. Tang, R. Zhou, G. Sun, B.Di, and R. Xiong, “A novel cooperative path planning for multirobot persistent coverage in complex environments,” IEEE Sensors J., vol.20, no.8, pp.4485-4495, Apr.

[317] X. Miao, J. Lee, and B.-Y.Kang, “Scalable coverage path planning for cleaning robots using rectangular map decomposition on large environments,” IEEE Access, vol.6, pp.38200-38215, 2018.

[318] Y. Ma, H. Sun, P. Ye, and C. Li, “Mobile robot multi-resolution full coverage path planning algorithm,” in Proc.5th Int.Conf.Syst.Informat.(ICSAI), Nanjing, China, Nov. 2018, pp.120-125.

[319] H. Liang, W. Gao, J. H. Nguyen, M. F. Orpilla, and W. Yu, “Internet of Things data collection using unmanned aerial vehicles in infrastructure free environments,” IEEE Access, vol.8, pp.3932-3944, 2020.

[320] X. Dai, L. Jiang, and Y. Zhao, “Cooperative exploration based on supervisory control of multi-robot systems,” Int.J.Speech Technol., vol.45,no.1, pp.18-29, Jul.

[321] J.Song and S. Gupta, “$\epsilon ^*$: An online coverage path planning algorithm,”IEEE Trans.Robot., vol.34, no.2, pp.526-533, Apr.

[322] Z. Shen, J. P. Wilson, and S. Gupta, “An online coverage path planning algorithm for curvature-constrained AUVs,” in Proc. OCEANS MTS/IEEE SEATTLE, Seattle, WA, USA, Oct. 2019,pp.1-5.

[323] E. Vidal, N. Palomeras, K. Isteni£, N. Gracias, and M. Carreras, “Multisensor online 3D view planning for autonomous underwater exploration,”J.Field Robot., vol.37, no.6, pp.1123-1147, Sep. 2020.

[324] B. Zhou, Y. Zhang, X. Chen, and S. Shen, “FUEL: Fast UA V exploration using incremental frontier structure and hierarchical planning,” IEEE Robot.Autom.Lett., vol.6, no.2, pp.779-786, Apr.

[325] S. Godio, S. Primatesta, G. Guglieri, and F. Dovis, “A bioinspired neural network-based approach for cooperative coverage planning of UA Vs,” Information, vol.12, no.2, pp.1-17, Jan. 2021.

[326] M. Theile, H. Bayerlein, R. Nai, D. Gesbert, and M. Caccamo, “UAV coverage path planning under varying power constraints using deep reinforcement learning,” in Proc.IEEE/RSJ Int.Conf.Intell.Robots Syst.(IROS), Las Vegas, NV, USA, Oct. 2020, pp.1-6.

[327] S. G. Potapova, A. V. Artemov, S. V. Sviridov, D. A. Musatkina,D. N. Zorin, and E. V. Burnaev, “Next best view planning via reinforcement learning for scanning of arbitrary 3D shapes,” J. Commun.Technol.Electron., vol.65, no.12, pp.1484-1490, Dec. 2020.

[328] B. Nasirian, M. Mehrandezh, and F. Janabi-Sharifi, “Efficient coverage path planning for mobile disinfecting robots using graph-based representation of environment,” Frontiers Robot.AI, vol.8, pp.1-19, Mar.

[329] X. Kan, H. Teng, and K. Karydis, “Online exploration and coverage planning in unknown obstacle-cluttered environments,” IEEE Robot. Autom.Lett., vol.5, no.4, pp.5969-5976, Oct. 2020.

[330] L. Shi, S. Xu, H. Liu, and Z. Zhan, “QoS-aware UA V coverage path planning in 5G mmWave network,” Comput.Netw., vol.175, pp.1-10,Jul.2020.