系统工程与电子技术, 2023, 45(12): 3949-3957 doi: 10.12305/j.issn.1001-506X.2023.12.25

制导、导航与控制

基于改进单元分解法的全覆盖路径规划

吴靖宇1,2, 朱世强2,3, 宋伟2,3, 施浩磊4, 吴泽南4

1. 浙江大学海洋学院, 浙江 舟山 316021

2. 浙江大学机器人研究院, 浙江 宁波 315400

3. 之江实验室, 浙江 杭州 311121

4. 舟山市质量技术监督检测研究院, 浙江 舟山 316013

Coverage path planning based on improved cellular decomposition

WU Jingyu1,2, ZHU Shiqiang2,3, SONG Wei2,3, SHI Haolei4, WU Zenan4

1. Ocean College, Zhejiang University, Zhoushan 316021, China

2. Robotics Institute, Zhejiang University, Ningbo 315400, China

3. Zhijiang Lab, Hangzhou 311121, China

4. Zhoushan Institute of Calibration and Testing for Qualitative and Technical Supervision, Zhoushan 316013, China

通讯作者: 宋伟

收稿日期: 2022-11-22  

基金资助: 浙江省市场监督管理局雏鹰计划培育项目.  CY2022231

Received: 2022-11-22  

作者简介 About authors

吴靖宇(1997—),男,硕士研究生,主要研究方向为定位导航 。

朱世强(1966—),男,教授,博士,主要研究方向为机械电子控制 。

宋伟(1984—),男,副教授,博士,主要研究方向为壁面无人维护作业技术、非结构化环境自主决策技术 。

施浩磊(1986—),男,高级工程师,硕士,主要研究方向为大宗油气计量测试、爬壁机器人装置及应用 。

吴泽南(1989—),男,高级工程师,本科,主要研究方向为大宗油气计量测试、爬壁机器人装置及应用 。

摘要

传统的单元分解法在静态已知环境中进行全覆盖路径规划时, 若障碍物分布不规则或具有较多的凹形障碍物, 则所得的单元数量较多, 这导致最终路径易出现较多的冗余和不必要的转向。首先, 将栅格地图分解为若干个路径片段, 每个路径片段由位于同一行且左右相邻的栅格组成; 然后, 合并这些路径片段以生成单元; 再基于贪心算法和拓扑地图三次求解单元间的遍历顺序, 合并减少了单元数量, 并对局部路径进行了优化, 最终完成遍历路径的规划。仿真结果验证了所提算法的有效性, 且规划的路径具有更少的冗余和转向次数。

关键词： 全覆盖路径规划 ; 单元分解法 ; 单元合并 ; 贪心算法

Abstract

When the traditional cellular decomposition method is used for complete coverage path planning in a static known environment, if the obstacles are irregularly distributed or many concave obstacles exist in the environment, the number of cells obtained is large. This finally leads to much redundancy and unnecessary steering in the final path. Firstly, the grid map is decomposed into several path segments, each of the path segment is composed of grids located in the same row and adjacent to the left and right. Secondly, these path fragment are merged for generating cells. Thirdly, based on greedy algorithm and topological map, the traversal order between cells is solved three times to merge and to reduce the number of cells, and the local path is optimized. Finally, the planning of traversal path is completed. Simulation results show that the algorithm is effective and the planned path has less redundancy and steering times.

Keywords： complete coverage path planning ; cellular decomposition ; cellular mergence ; greedy algorithm

PDF (5028KB) 元数据 多维度评价 相关文章 导出 EndNote| Ris| Bibtex  收藏本文

本文引用格式

吴靖宇, 朱世强, 宋伟, 施浩磊, 吴泽南. 基于改进单元分解法的全覆盖路径规划. 系统工程与电子技术[J], 2023, 45(12): 3949-3957 doi:10.12305/j.issn.1001-506X.2023.12.25

WU Jingyu. Coverage path planning based on improved cellular decomposition. Systems Engineering and Electronics[J], 2023, 45(12): 3949-3957 doi:10.12305/j.issn.1001-506X.2023.12.25

0 引言

路径规划是影响移动机器人作业效率的重要环节。按照所得路径的特点, 路径规划可分为“点到点”和“全覆盖”两类。其中, 前者可应用于山地救援[1]、自动驾驶[2]、物流运输[3]等两点之间无碰撞的移动场景, 现有方法包括A * [4-5]法、人工势场法[6]、快速扩展随机树[7]等; 后者则应用于地面清扫[8]、农业植保[9]、油罐底面清洗[10]等需要遍历某一区域的场景, 现有方法包括生物激励神经网络算法[11-12]、生成树覆盖算法[13-14]、单元分解法[15]等。

当在静态已知环境中进行全覆盖路径的离线规划时, 单元分解法是一种常用的方法[16-17]。该方法的实现过程主要分为两个步骤, 分别为划分单元和求解单元间遍历顺序。其中划分单元是指将待遍历的区域划分为若干个互不重叠的子区域。传统的单元分解法在此步骤采用的是根据障碍物的形状和位置划分单元的方式, 包括: Trapezoidal分解[18]、Boustrophedon分解[19-21]和Morse分解[22-23]。而求解单元间遍历顺序则是一个旅行商问题, 常用的方法包括深度优先搜索[24]、模拟退火法[25]、蚁群算法[26]、粒子群优化算法[27]、遗传算法[28-29]、强化学习[30]和深度强化学习[31]等。

但传统的单元分解法在障碍物分布不规则和凹形障碍物较多的场景下却易出现较多的冗余路径和转向次数。其中分布不规则是指在栅格地图上, 各个障碍物的几何中心一般位于不同的行和列。日常生活中椅子、凳子等物件即会因人们的使用而成为分布不规则的障碍物。凹形障碍物则可见于办公区域等场景, 例如只有一扇门进出的房间, 其四周墙壁即可视为凹形障碍物。在这两种场景中, 待遍历区域的形状变得不规则, 使得传统的单元分解法所得单元的数量较多。而单元数量的增加会使得每个单元的平均面积减少, 造成传统的单元分解法难以在更大的范围内应用并优化局部路径, 故易产生较多的冗余路径和转向次数。对此, 本文提出一种改进的规划算法, 目的是减少最终路径的冗余和转向次数。改进后的单元划分通过在栅格地图上合并路径片段来实现(路径片段由位于同一行且左右相邻的栅格组成)。这样, 单元的划分不再完全依赖于障碍物的形状和位置, 而是兼顾了单元内的路径规划。同时, 为了减少单元的数量, 在求解单元间遍历顺序时, 结合贪心算法和拓扑地图进行三次求解, 不断合并单元, 并对局部路径进行了优化。

本文的结构安排如下: 引言部分介绍了路径规划的研究现状和传统单元分解法存在的一些不足; 第1节阐述了路径片段初步合并生成单元的过程; 第2节阐述了基于贪心算法和拓扑地图的单元间遍历顺序的求解过程; 第3节进行了仿真实验, 其结果验证了本文算法的有效性; 第4节对全文进行了总结, 指出当前本文算法存在的不足。本文的主要创新点在于: 改进了传统单元分解法划分单元的方式, 并通过对单元的合并, 降低了在障碍物分布不规则和凹形障碍物较多的场景下单元划分的数量, 减少了冗余路径和转向次数。

1 单元初步合并生成

本节通过合并路径片段初步生成单元, 以实现对待遍历区域的单元划分。相关步骤包括: 栅格地图初始化、生成路径片段、确定遍历起始单元和合并路径片段。

1.1 栅格地图初始化

首先, 建立平面直角坐标系, 其原点O位于地图左上角, 向下为X轴, 向右为Y轴, 则第a行、第b列栅格可以用坐标(a, b)表示。

然后, 建立与栅格地图对应的同维度矩阵, 并将待遍历栅格以数字0表示, 将障碍物以数字1表示。为获取该矩阵对应位置的数值, 定义函数F(a, b)如下:

$F(a, b)=\left\{\begin{array}{l}0, \text { 待遍历栅格 } \\1, \text { 障碍物栅格或边界之外 }\end{array}\right.$

设地图上所有的栅格组成集合Call, 则其中待遍历栅格可以表示为

$C_{\mathrm{cov}}=\left\{\left(x_i, y_i\right) \in C_{\text {all }} \mid F\left(x_i, y_i\right)=0\right\}$

1.2 生成路径片段

定义路径片段如下: 地图上位于同一行且未被障碍物阻隔的全部连通栅格的有序排列集合, 则第R行的某一路径片段CR={(xR, y1), (xR, y2), ⋯, (xR, yr)}满足:

$\left\{\begin{array}{l}F\left(x_R, y_1-1\right)=1 \\F\left(x_R, y_r+1\right)=1 \\F\left(x_R, y_e\right)=0, 1 \leqslant e \leqslant r \\y_f-y_{f-1}=1, 2 \leqslant f \leqslant r\end{array}\right.$

设某一地图的待遍历区域通过划分共生成了n个路径片段, 则它们组成的集合Cpath={C1, C2, ⋯, Cn}满足:

$\left\{\begin{array}{l}C_1 \cup C_2 \cup \cdots \cup C_n=C_{\text {cov }} \\C_g \cap C_h=\phi, 1 \leqslant g \leqslant n ; 1 \leqslant h \leqslant n ; g \neq h\end{array}\right.$

图 1所示为一个生成路径片段的示例(图中黑色栅格为障碍物, 白色栅格为待遍历区域, 下同), 其中属于同一路径片段的栅格以线段依次相连。显然, 每条线段均可作为机器人的潜在移动路径, 而单元则可通过合并这些路径片段来生成。

图1

新窗口打开| 下载原图ZIP| 生成PPT

图1   生成路径片段

Fig.1   Path fragments generation


1.3 确定遍历起始单元

假定机器人的直线运动平行于坐标轴, 且平均速度为v; 机器人每转过90°视为一次转向, 且所需时间为t。机器人在从坐标为(a, b)的栅格移动到坐标为(c, d)的过程中共转向M次, 直线运动的总路程长度为L, 则该次移动所需的总时间为

$T[(a, b), (c, d)]=\frac{L}{v}+t M$

若在该时间内机器人始终以平均速度v做直线运动, 则可移动距离为

$L^{\prime}=v \cdot T[(a, b), (c, d)]=L+v t M$

记P=vt, 则机器人从栅格(a, b)移动到(c, d)的等效路径长度为

$L^{\prime}=L+P M$

由于v和t的值仅与机器人的自身性能有关, 数值可由实验测出。当机器人的型号确定后, 参数P即为一个常量。因此, 由式(7)计算所得的等效路径长度L′可作为评价路径优劣的评价指标。

以式(7)计算机器人的初始位置所在栅格到每个路径片段首尾两个端点栅格的等效路径长度, 根据最小值确定起始路径片段和起始栅格。若起始栅格位于起始路径片段的末端, 则对起始路径片段中的栅格进行倒序排列。后续由起始路径片段合并生成的单元即是遍历起始单元, 记为CS。

1.4 合并路径片段

路径片段的合并流程如图 2所示。

图2

新窗口打开| 下载原图ZIP| 生成PPT

图2   路径片段合并流程图

Fig.2   Flowchart of path fragment mergency


具体步骤如下:

步骤1  生成空集合CMer, 对合并完成的单元进行存储。

步骤2  判断Cpath中是否存在某一路径片段Cm(1≤m≤n)且满足以下两个要求:

(1) Cm在地图上的相邻路径片段Cadj属于Cpath;

(2) Cadj仅有一个端点栅格与Cm的某一端点栅格上下相邻。其中, 两个路径片段相邻的定义为: 存在两个上下相邻的栅格分别属于这两个路径片段, 即$ \exists$(a, b)∈Cm, $\exists $(c, d)∈Cadj, 满足:

$\left\{\begin{array}{l}|a-c|=1 \\b=d\end{array}\right.$

此外, 为避免起始栅格之前出现路径, 将起始栅格视为与所有栅格均不相邻。若存在Cm满足要求, 则将Cadj合并至Cm, 并跳转至步骤3, 否则跳转至步骤7。

图 3所示为本步骤中路径片段满足合并要求的两种情形。其中情形1表示两个路径片段除了一组端点栅格上下相邻, 还存在其他栅格相邻; 情形2则与之相反。

图3

新窗口打开| 下载原图ZIP| 生成PPT

图3   满足合并要求的两种情形

Fig.3   Two situations meeting the mergency requirements


步骤3  对合并后的Cm, 调整其栅格排列顺序, 确保以该顺序生成的移动路径连贯, 如图 4所示。

图4

新窗口打开| 下载原图ZIP| 生成PPT

图4   调整集合内栅格排列顺序后所生成的路径

Fig.4   Path generated after adjusting grid arrangement order in the column


步骤4  对调整后的集合Cm重复步骤2和步骤3, 直至Cm不满足步骤2中的要求。

步骤5  将Cm从Cpath中移除, 并添加至CMer, 以防止出现重复规划。

步骤6  重复步骤2~步骤5, 直至Cpath中不存在集合满足步骤2中的要求。

步骤7  将Cpath中剩余的集合记为CMer2。

则CMer和CMer2中的每个元素即为初次合并后的单元。这些单元具有以下两个特点:

(1) 以栅格排列顺序所生成的路径可无重复地遍历该单元;

(2) 该路径的起点为排列在首末位置的两个栅格之一。

这样, 单元的生成除了考虑障碍物的形状和位置, 也兼顾了单元内的路径规划。图 5(a)所示为路径片段初步合并后的结果, 图 5(b)为合并形成的单元, 共有13个(图中黑色圆点代表路径起点, 下同)。后续单元的合并以及局部路径的优化需参照单元间的遍历顺序进行。

图5

新窗口打开| 下载原图ZIP| 生成PPT

图5   单元初步合并生成的结果

Fig.5   Result of preliminary cellular mergence


2 基于贪心算法和拓扑地图的单元间遍历顺序求解

本节求解单元间的遍历顺序, 以生成最终路径。相关步骤包括: 生成拓扑地图和执行3次基于贪心算法的求解。其中, 拓扑地图根据单元间的相邻情况生成, 用于求解过程中单元的再次合并。而在3次求解中, 后一次求解均基于前一次求解的结果, 以使得局部路径不断得到优化, 从而减少最终总体路径的冗余和转向次数。

2.1 生成拓扑地图

依据各单元的相邻情况生成拓扑地图。图 6即是由图 5所得的拓扑地图。

图6

新窗口打开| 下载原图ZIP| 生成PPT

图6   生成拓扑地图

Fig.6   Generation of topology map


其中, 每个单元均可视为一个节点, 而整个地图则可视为一个树形结构。为便于进一步合并单元, 进行如下定义, 从而将所有节点分为3类:

(1) 根节点: 遍历起始单元CS, 以及相邻节点数之和大于2的节点(一般为枢纽)。

(2) 通道节点: 用于连接两个根节点的节点。

(3) 分枝节点: 除以上节点的节点(一般为处于凹形区域的节点)。

2.2 第一次求解

第一次求解的流程图如图 7所示。

图7

新窗口打开| 下载原图ZIP| 生成PPT

图7   第一次求解流程图

Fig.7   Flowchart of the first solution


具体步骤如下:

步骤1  生成集合CNav1=CS, 用于存储机器人先后经过的栅格, 即导航点。其中, 两个导航点之间的实际移动路径由A* 算法获取。

步骤2  判断是否存在未遍历的单元, 若不存在, 则跳转至步骤11。

步骤3  判断上一个遍历的单元CLast和它的相邻单元CNear是否满足优先遍历的两个要求:

(1) CLast与CNear均为通道节点;

(2) 单元CNear未遍历。

若是, 则将CNear作为下一个待遍历的单元CNext; 若否, 则选择最近单元作为CNext(即贪心算法)。

最近单元定义为: 以式(7)计算当前排列在集合CNav1末端的栅格, 其到某一单元的首端或末端栅格的等效路径长度即为所有未遍历单元中的最小值。

执行此步骤的目的是, 使得处于同一通道的单元优先集中完成遍历, 否则遍历路径可能发生割裂, 出现如图 8(a)所示的规划, 导致不必要的转向; 而图 8(b)所示则采用了优先遍历的规划路径, 其路径长度和转向次数得到了降低。

图8

新窗口打开| 下载原图ZIP| 生成PPT

图8   优先遍历效果示意

Fig.8   Schematic diagram of priority traversal effect


步骤4  判断CNext是否存在已遍历的相邻单元。若否, 则跳转至步骤5;若是, 则跳转至步骤6。

步骤5  以式(7)分别计算CNav1的当前末端栅格, 及其到CNext的第一和最后一个栅格的等效路径长度, 以此确定最佳的单元内遍历路径起点。调整CNext的栅格排序, 将之添加至CNav1的末端, 并将该单元标记为已遍历。之后返回步骤2。

步骤6  与步骤5操作类似, 以最优方式将CNext中的栅格坐标添加至CNav1的末端, 并以式(7)计算此时由CNav1生成的路径的等效路径长度。

步骤7  获取与CNext相邻的所有已遍历的栅格, 并寻找这些栅格在CNav1中的排列序号, 设最小序号为Nmin、最大序号为Nmax。

步骤8  将CNext内所有栅格以正序插入CNav1中的Nmin-1处(如图 9所示, 其中箭头方向代表栅格的遍历顺序), 计算此时CNav1的等效路径长度。

图9

新窗口打开| 下载原图ZIP| 生成PPT

图9   将CNext以正序插入CNav1中的Nmin-1处

Fig.9   Inserting CNext into Nmin-1 of CNav1 with positive order


再将CNext内所有栅格以倒序插入至CNav1中的Nmin-1处, 再次计算此时CNav1的等效路径长度。

步骤9  重复步骤8, 但每次CNext内所有栅格的插入位置在上次位置的基础上右移一位, 直至Nmax+1处。

步骤10  寻找步骤8~步骤9中获得的最短等效路径长度, 将之与步骤6所得的等效路径长度进行比较, 选取最小值。将对应的添加方式作为CNext的最终添加结果, 并标记相应的单元为已遍历, 之后返回步骤2。

步骤11  根据最终所得导航点集合CNav1, 以A* 算法生成机器人的实际运动路径, 若在生成时某导航点已在已生成的路径中, 则跳过。

图 10为第一次求解结果(图中黑色三角形代表路径终点, 下同)。该路径的长度为116个栅格, 转向次数为48。

图10

新窗口打开| 下载原图ZIP| 生成PPT

图10   第一次求解结果

Fig.10   Results of the first solution


2.3 第二次求解

第一次求解时未合并分枝和通道节点, 导致单元的数量较多。而未在初始时就合并的原因在于, 该分枝或通道的遍历起点栅格还未确定。因此, 第一次求解完成后, 依托于第一次求解的结果, 将连接两个根节点的位于同一通道中的通道节点进行合并。同时, 对每个分枝, 从位于其末端的分枝节点开始, 对分枝内的每个节点进行判定: 若某个分枝节点的父节点在第一次规划时先于该节点遍历, 则将该节点合并至其父节点。

合并单元时需调整单元内栅格的排列顺序, 方法与第一次求解时的步骤7~步骤9类似, 此处不再赘述。

然后, 对完成合并的每个单元进行形状判定: 若形状为矩形, 且单元的首尾两个栅格位于同一列, 则再次调整该单元内栅格的排序, 以预留出撤离路径, 如图 11(b)所示。这样相对于图 11(a)所示的调整前的规划路径, 单元内的冗余路径实现了降低。

图11

新窗口打开| 下载原图ZIP| 生成PPT

图11   栅格排列顺序调整比较

Fig.11   Comparison of grid arrangement order adjustment


重复以上操作, 直至所有分枝节点和通道节点均得到判定与处理。这样合并后的总体规划路径更优。如图 12(a)所示, 合并单元前规划的路径出现了重复, 而在图 12(b)中, 合并后再规划的路径则得到了改善。

图12

新窗口打开| 下载原图ZIP| 生成PPT

图12   合并单元前后的规划路径对比

Fig.12   Comparison of paths planned before and after cells mergence


图 13为第二次合并后的结果。相较于图 5, 通道节点5、6、7和分枝节点3、4、9、10、12、13被合并了, 单元总数为8。之后采用与第一次求解相同的方式获取第二次求解结果CNav2, 此处不再赘述。图 14所示为第二次求解结果, 其路径长度为112个栅格, 转向次数为46。相较于第一次求解, 路径的长度和转向次数获得了降低。

图13

新窗口打开| 下载原图ZIP| 生成PPT

图13   第二次单元合并后的结果

Fig.13   Result after the second cell mergence


图14

新窗口打开| 下载原图ZIP| 生成PPT

图14   第二次求解结果

Fig.14   Result of the second solution


2.4 第三次求解

在第二次求解时可能出现以下两种情形: 同一分枝中某一子节点先于其父节点遍历, 以及分枝中某一节点先于该分枝所在根节点遍历。为进一步减少单元的数量, 将这些节点合并后再进行规划。

节点的合并方式以及第三次求解获取CNav3的步骤与第二次类似, 此处亦不再赘述。

图 15为单元再次合并后的结果。相较于图 13, 分枝节点11以及由节点3和节点4合并而成的节点均被合并, 单元总数为6。图 16为第三次求解的结果, 其路径长度为108个栅格, 转向次数为46。相较于第二次求解, 路径的长度进一步减少。

图15

新窗口打开| 下载原图ZIP| 生成PPT

图15   第三次单元合并结果

Fig.15   Result after the third cellular mergence


图16

新窗口打开| 下载原图ZIP| 生成PPT

图16   第三次求解结果

Fig.16   Result of the third solution


3 仿真实验与分析

本节分“障碍物分布不规则”和“凹形障碍物较多”两种场景对本文算法进行了规划测试。其中, 图 17和图 18所示地图的尺寸均为40×40。地图中的障碍物由计算机+人工随机生成, 以验证本文算法在较复杂环境下的有效性。作为对比的单元分解法, 在划分单元部分, 选取了应用较多的Boustrophedon分解; 在单元间遍历顺序的求解部分, 则选取了贪心算法和遗传算法。同时, 在单元分解法之外, 选取了常见的生物激励神经网络算法作为对比。

图17

新窗口打开| 下载原图ZIP| 生成PPT

图17   场景1下不同算法的路径规划结果

Fig.17   Path planning results of different algorithms in Scenario 1


图18

新窗口打开| 下载原图ZIP| 生成PPT

图18   场景2下不同算法的路径规划结果

Fig.18   Path planning results of different algorithms in Scenario 2


为计算方便, 将路径的长度用栅格数表示。同时, 假定仿真中机器人的平均移动速度v和一次转向用时t的乘积v·t=2, 即式(7)中P=2, 物理意义为机器人一次转向所花的时间可以移动两个栅格的距离。而为了直观地显示不同算法规划出的路径的优劣, 以式(7)计算各路径的等效路径长度, 作为判断的标准。此外, 本文算法在每次求解时的单元数在表 1和表 2中依次列出。其中, 表 1为障碍物分布不规则的地图(场景1), 表 2为凸形障碍物较多的地图(场景2)。

表1   场景1下不同算法的路径规划结果比较

Table 1  Comparison of path planning results of different algorithms in Scenario 1

算法单元数量/个路径长度/个路径重复率/%转向/次等效路径长度/个
本文算法37, 25, 241 3668.073061 978
Boustrophedon
分解+贪心算法		371 44614.403382 122
Boustrophedon
分解+遗传算法		371 48717.643502 187
生物激励神经网络算法-1 46115.594342 329

新窗口打开| 下载CSV


表2   场景2下不同算法的路径规划结果比较

Table 2  Comparison of path planning results of different algorithms in Scenario 2

算法单元数量/个路径长度/个路径重复率/%转向/次等效路径长度/个
本文算法47, 31, 311 45713.393342 125
Boustrophedon
分解+贪心算法		391 67830.583942 466
Boustrophedon
分解+遗传算法		391 61425.603882 390
生物激励神经网络算法-1 66929.885122 693

新窗口打开| 下载CSV


由实验结果可以看出, 当在相对复杂的地图中进行全覆盖路径规划时, 无论是障碍物分布不规则的场景, 还是凹形障碍物较多的场景, 本文算法所生成的单元在规划求解的过程中逐步被合并, 其数量不断减少, 且最终的单元数均少于Boustrophedon分解。同时, 本文算法所得遍历路径的重复率约为3种对比算法的50%, 表明路径具有更少的冗余, 且转向次数也更低。此外, 等效路径长度也表明, 本文算法规划的路径更优。

4 结论

在障碍物分布不规则或凹形障碍物较多的静态已知环境中, 传统的单元分解法存在单元划分数量较多的问题。这使得最终路径易出现较多冗余和不必要的转向。本文对传统的单元分解法进行了改进: 在划分单元阶段, 通过在栅格地图上合并路径片段来生成初始单元, 使得单元的划分不再完全根据障碍物的形状和位置进行, 而是兼顾了单元内的路径规划; 在单元间遍历顺序的求解阶段, 基于贪心算法和拓扑地图三次求解, 合并减少了单元数量, 并优化了局部路径。仿真实验结果表明, 相较于Boustrophedon分解方法和生物激励神经网络算法, 本文算法能够有效减少最终遍历路径的冗余和转向次数。但由于单元的合并和局部路径的优化存在较大的计算量, 故本文仅进行了三次求解, 且算法的实时性不够, 目前仅适用于离线规划, 这也是后续研究需改进的方向。

参考文献

伍跃飞, 李建微, 毕胜, 等.

面向山地徒步应急救援路径规划的改进蚁群算法研究

[J]. 地球信息科学学报, 2023, 25 (1): 90- 101.

URL     [本文引用: 1]

WU Y F , LI J W , BI S , et al.

Research on improved ant colony algorithm for mountain hiking emergency rescue path planning

[J]. Journal of Geo-information Science, 2023, 25 (1): 90- 101.

URL     [本文引用: 1]

HUANG G H , MA Q L .

Research on path planning algorithm of autonomous vehicles based on improved RRT algorithm

[J]. International Journal of Intelligent Transportation Systems Research, 2022, 20 (1): 170- 180.

DOI:10.1007/s13177-021-00281-2      [本文引用: 1]

CUI J Y, WU D Q, MANSOUR R F. Research on EVRP of cold chain logistics distribution based on improved ant colony algorithm[C]// Proc. of the 8th International Conference on Artificial Intelligence and Security, 2022: 537-548.

[本文引用: 1]

HONG Z H , SUN P F , TONG X H , et al.

Improved A-star algorithm for long-distance off-road path planning using terrain data map

[J]. ISPRS International Journal of Geo-Information, 2021, 10 (11): 785.

DOI:10.3390/ijgi10110785      [本文引用: 1]

ZHANG Y , LI L L , LIN H C , et al.

Development of path planning approach using improved A-star algorithm in AGV system

[J]. Journal of Internet Technology, 2019, 20 (3): 915- 924.

[本文引用: 1]

RASEKHIPOUR Y , KHAJEPOUR A , CHEN S K , et al.

A potential field-based model predictive path-planning controller for autonomous road vehicles

[J]. IEEE Trans.on Intelligent Transportation Systems, 2016, 18 (5): 1255- 1267.

[本文引用: 1]

WANG J , LI B , MENG Q H .

Kinematic constrained bi-directional RRT with efficient branch pruning for robot path planning

[J]. Expert Systems with Applications, 2021, 170, 114541.

DOI:10.1016/j.eswa.2020.114541      [本文引用: 1]

PHAM H V , LAM T N .

A new method using knowledge reasoning techniques for robot performance in coverage path planning

[J]. International Journal of Computer Applications in Technology, 2019, 60 (1): 57- 64.

DOI:10.1504/IJCAT.2019.099503      [本文引用: 1]

刘洋成, 耿端阳, 兰玉彬, 等.

基于自动导航的农业装备全覆盖路径规划研究进展

[J]. 中国农机化学报, 2020, 41 (11): 185- 192.

DOI:10.13733/j.jcam.issn.2095-5553.2020.11.028      [本文引用: 1]

LIU Y C , GENG D Y , LAN Y B , et al.

Research progress of agricultural equipment full coverage path planning based on automatic navigation

[J]. Journal of Chinese Agricultural Mechanization, 2020, 41 (11): 185- 192.

DOI:10.13733/j.jcam.issn.2095-5553.2020.11.028      [本文引用: 1]

代峰燕, 高庆珊, 陈家庆, 等.

储油罐清洗机器人全覆盖路径规划研究

[J]. 机械设计与制造, 2020, 58 (2): 263- 266.

DOI:10.19356/j.cnki.1001-3997.2020.02.066      [本文引用: 1]

DAI F Y , GAO Q S , CHEN J Q , et al.

Research of full covered path planning for oil tank cleaning robot

[J]. Machinery Design and Manufacture, 2020, 58 (2): 263- 266.

DOI:10.19356/j.cnki.1001-3997.2020.02.066      [本文引用: 1]

ZHU D Q , TIAN C , SUN B , et al.

Complete coverage path planning of autonomous underwater vehicle based on GBNN algorithm

[J]. Journal of Intelligent and Robotic Systems, 2019, 94 (1): 237- 249.

DOI:10.1007/s10846-018-0787-7      [本文引用: 1]

ZHU D Q , ZHOU B , YANG S X .

A novel algorithm of multi-AUVs task assignment and path planning based on biologically inspired neural network map

[J]. IEEE Trans.on Intelligent Vehicles, 2021, 6 (2): 333- 342.

DOI:10.1109/TIV.2020.3029369      [本文引用: 1]

VAN P H , ASADI F , ABUT N , et al.

Hybrid spiral STC-hedge algebras model in knowledge reasonings for robot cove-rage path planning and its applications

[J]. Applied Sciences, 2019, 9 (9): 1909.

DOI:10.3390/app9091909      [本文引用: 1]

DONG W , LIU S S , DING Y , et al.

An artificially weighted spanning tree coverage algorithm for decentralized flying robots

[J]. IEEE Trans.on Automation Science and Engineering, 2020, 17 (4): 1689- 1698.

DOI:10.1109/TASE.2020.2971324      [本文引用: 1]

JANCHIV A , BATSAIKHAN D , KIM B S , et al.

Time-efficient and complete coverage path planning based on flow networks for multi-robots

[J]. International Journal of Control, Automation and Systems, 2013, 11 (2): 369- 376.

DOI:10.1007/s12555-011-0184-5      [本文引用: 1]

胡诗宇. 清洁机器人的定位与全覆盖路径规划研究[D]. 南京: 东南大学, 2019.

[本文引用: 1]

HU S Y. Research on the localization and full coverage path planning for a cleaning robot[D]. Nanjing: Southeast University, 2019.

[本文引用: 1]

GURUPRASAD K R , RANJITHA T D .

CPC algorithm: extra area coverage by a mobile robot using approximate cellular decomposition

[J]. Robotica, 2021, 39 (7): 1141- 1162.

DOI:10.1017/S026357472000096X      [本文引用: 1]

LATOMBE J C . Exact cell decomposition robot motion planning[M]. Boston: Springer, 1991.

[本文引用: 1]

CHOSET H .

Coverage of known spaces: the boustrophedon cellular decomposition

[J]. Autonomous Robots, 2000, 9 (3): 247- 253.

DOI:10.1023/A:1008958800904      [本文引用: 1]

张毅, 施明瑞.

基于单元分解的改进D* lite路径规划算法

[J]. 重庆邮电大学学报(自然科学版), 2021, 33 (6): 1007- 1013.

URL    

ZHANG Y , SHI M R .

Improved D* lite path planning algorithm based on cell decomposition

[J]. Journal of Chongqing University of Posts and Telecommunications (Natural Science Edition), 2021, 33 (6): 1007- 1013.

URL    

MISINO F. Development of a multi-UAS coverage planning algorithm based on the ant colony optimization[D]. Turin: Polytechnic University of Turin, 2022.

[本文引用: 1]

ACAR E U , CHOSET H , RIZZI A A , et al.

Morse decompositions for coverage tasks

[J]. International Journal of Robotics Research, 2002, 21 (4): 331- 344.

DOI:10.1177/027836402320556359      [本文引用: 1]

HAN Y L , SHAO M , WU Y Z , et al.

An improved complete coverage path planning method for intelligent agricultural machinery based on backtracking method

[J]. Information, 2022, 13 (7): 313.

DOI:10.3390/info13070313      [本文引用: 1]

TANG G , TANG C Q , ZHOU H , et al.

R-DFS: a coverage path planning approach based on region optimal decomposition

[J]. Remote Sensing, 2021, 13 (8): 1525.

DOI:10.3390/rs13081525      [本文引用: 1]

KHOSRAVANI M E , VAHDANJOO M , JENSEN A L , et al.

An arable field for benchmarking of metaheuristic algorithms for capacitated coverage path planning problems

[J]. Agronomy, 2020, 10 (10): 1454.

DOI:10.3390/agronomy10101454      [本文引用: 1]

MAJEED A , LEE S .

A new coverage flight path planning algorithm based on footprint sweep fitting for unmanned aerial vehicle navigation in urban environments

[J]. Applied Sciences, 2019, 9 (7): 1470.

DOI:10.3390/app9071470      [本文引用: 1]

PHUNG M D , QUACH C H , DINH T H , et al.

Enhanced discrete particle swarm optimization path planning for UAV vision-based surface inspection

[J]. Automation in Construction, 2017, 81, 25- 33.

DOI:10.1016/j.autcon.2017.04.013      [本文引用: 1]

SHIVGAN R, DONG Z. Energy-efficient drone coverage path planning using genetic algorithm[C]//Proc. of the IEEE 21st International Conference on High Performance Switching and Routing, 2020.

[本文引用: 1]

LE A V , ARUNMOZHI M , VEERAJAGADHESWAR P , et al.

Complete path planning for a tetris-inspired self-reconfigurable robot by the genetic algorithm of the traveling salesman problem

[J]. Electronics, 2018, 7 (12): 344.

DOI:10.3390/electronics7120344      [本文引用: 1]

LAKSHMANAN A K , MOHAN R E , RAMALINGAM B , et al.

Complete coverage path planning using reinforcement learning for tetromino based cleaning and maintenance robot

[J]. Automation in Construction, 2020, 112, 103078.

DOI:10.1016/j.autcon.2020.103078      [本文引用: 1]

KYAW P T , PAING A , THU T T , et al.

Coverage path planning for decomposition reconfigurable grid-maps using deep reinforcement learning based travelling salesman problem

[J]. IEEE Access, 2020, 8, 225945- 225956.

DOI:10.1109/ACCESS.2020.3045027      [本文引用: 1]

/

〈 〉

京ICP备11035014号-5
版权所有 © 2019 北京航天情报与信息研究所《系统工程与电子技术》编辑部
通讯地址：北京市142信箱32分箱《系统工程与电子技术》编辑部(100854)
电　话：(010)68388406/68386014    E-mail：xtgcydzjs@126.com(系统工程与电子技术)/jseeoffice@126.com(JSEE)
本系统由北京玛格泰克科技发展有限公司设计开发