·320· 智能系统学报 第13卷 长期停留在死区，需要更长的路径才能逃离死区。 3结束语 而栅格信度函数算法在机器人陷入死区后能通过调 整方向信度函数的方法快速的逃离死区。图7中黑 本文采用栅格信度函数算法解决了移动机器人 色线段显示了两种不同算法逃离死区的路径。虽然 全覆盖路径规划问题。仿真实验证明本文所提算法 两种算法在未陷入死区前机器人移动路径相同，但 在二维障碍物环境中，不仅能够实现动态障碍物工 是由于逃离死区的路径不同，导致两种算法的重复 作区域的全覆盖，而且还能够快速逃离死区，降低 覆盖栅格数，路径重复率、总行程等指标的差异。 了机器人路径的重复率，提高了覆盖效率。限于篇 从表3可见生物启发神经网络算法的重复覆盖的栅 幅，本文未讨论实际的二维环境栅格地图的构建以 格有39块，而栅格信度函数算法只有23块；生物 及机器人的形状、转向幅度、定位对全覆盖路径规 启发神经网络算法的路径重复率几乎是本文算法 划的影响，后续研究将把栅格地图构建与全覆盖路 的2倍：总行程后者比前者少16步。结果表明基于 栅格信度函数的算法可以有效降低路径重复率，缩 径规划结合，研究移动机器人对真实环境的感知与 短行程，对于机器人来说路径规划更适合控制，更 路径规划方法。 节省能源。 参考文献： 未搜索单元 205 [山]简毅，张月.移动机器人全局覆盖路径规划算法研究进展 16 与展望U.计算机应用，2014,34(10)：2844-2849,2864. JIAN Yi.ZHANG Yue.Complete coverage path planning algorithm for mobile robot:progress and prospect[J].Journ- 10 al of computer applications,2014,34(10):2844-2849, 2864 [2]YAN Mingzhong,ZHU Daqi.An algorithm of complete coverage path planning for autonomous underwater vehicles ②ooooooooooo3 10 5 [J].Key engineering materials,2011,467-469:1377-1385. Ym (a)生物启发神经网络算法 [3)莫宏伟，马靖雯.一种生物地理学移动机器人路径规划算 法U.智能系统学报，2015,10(5)：705-711. 未搜索单元已搜索单元■障碍物 0 MO Hongwei,MA Jingwen.A biogeography-based mobile 18 robot path planning algorithm[J].CAAI transactions on in- telligent systems,2015,10(5):705-711. 14 [4]LI Yan,CHEN Hai,JOO ER MENG,et al.Coverage path planning for UAVs based on enhanced exact cellular de- composition method[J].Mechatronics,2011,21(5):876- 885 [)]蒲兴成，赵红全，张毅.细菌趋化行为的移动机器人路径 88888888888 规划几.智能系统学报，2014.91)69-75. J 10 15 20 PU Xingcheng.ZHAO Hongquan,ZHANG Yi.Mobile ro- x/m b)栅格信度函数算法 bot path planning research based on bacterial chemotaxis[J]. CAAI transactions on intelligent systems,2014,9(1): 图7不同算法全覆盖路径规划结果 69-75 Fig.7 The results of complete-coverage path planning [6]KAPANOGLU M.ALIKALFA M.OZKAN M.et al.A with different algorithms pattern-based genetic algorithm for multi-robot coverage 表3不同算法全覆盖路径规划性能比较 path planning minimizing completion time[J].Journal of in- Table 3 Performance comparison of complete-coverage path planning with different algorithms telligent manufacturing,2012,23(4):1035-1045. [刀杜鹏桢，唐振民，陆建峰，等.不确定环境下基于改进萤火 算法指标 生物启发神经网络算法栅格信度函数算法 虫算法的地面自主车辆全局路径规划方法).电子学报， 区域覆盖率% 100 100 2014.42(3):616-624 重复覆盖区域块 39 23 DU Pengzhen,TANG Zhenmin,LU Jianfeng,et al.Global 路径重复率% 11.04 6.51 path planning for ALV based on improved glowworm 总行程步 392 376 swarm optimization under uncertain environment[J].Acta长期停留在死区，需要更长的路径才能逃离死区。 而栅格信度函数算法在机器人陷入死区后能通过调 整方向信度函数的方法快速的逃离死区。图 7 中黑 色线段显示了两种不同算法逃离死区的路径。虽然 两种算法在未陷入死区前机器人移动路径相同，但 是由于逃离死区的路径不同，导致两种算法的重复 覆盖栅格数，路径重复率、总行程等指标的差异。 从表 3 可见生物启发神经网络算法的重复覆盖的栅 格有 39 块，而栅格信度函数算法只有 23 块；生物 启发神经网络算法的路径重复率几乎是本文算法 的 2 倍；总行程后者比前者少 16 步。结果表明基于 栅格信度函数的算法可以有效降低路径重复率，缩 短行程，对于机器人来说路径规划更适合控制，更 节省能源。 3 结束语 本文采用栅格信度函数算法解决了移动机器人 全覆盖路径规划问题。仿真实验证明本文所提算法 在二维障碍物环境中，不仅能够实现动态障碍物工 作区域的全覆盖，而且还能够快速逃离死区，降低 了机器人路径的重复率，提高了覆盖效率。限于篇 幅，本文未讨论实际的二维环境栅格地图的构建以 及机器人的形状、转向幅度、定位对全覆盖路径规 划的影响，后续研究将把栅格地图构建与全覆盖路 径规划结合，研究移动机器人对真实环境的感知与 路径规划方法。 参考文献： 简毅, 张月. 移动机器人全局覆盖路径规划算法研究进展 与展望[J]. 计算机应用, 2014, 34(10): 2844–2849, 2864. JIAN Yi, ZHANG Yue. Complete coverage path planning algorithm for mobile robot: progress and prospect[J]. Journ￾al of computer applications, 2014, 34(10): 2844–2849, 2864. [1] YAN Mingzhong, ZHU Daqi. An algorithm of complete coverage path planning for autonomous underwater vehicles [J]. Key engineering materials, 2011, 467-469: 1377–1385. [2] 莫宏伟, 马靖雯. 一种生物地理学移动机器人路径规划算 法[J]. 智能系统学报, 2015, 10(5): 705–711. MO Hongwei, MA Jingwen. A biogeography-based mobile robot path planning algorithm[J]. CAAI transactions on in￾telligent systems, 2015, 10(5): 705–711. [3] LI Yan, CHEN Hai, JOO ER MENG, et al. Coverage path planning for UAVs based on enhanced exact cellular de￾composition method[J]. Mechatronics, 2011, 21(5): 876– 885. [4] 蒲兴成, 赵红全, 张毅. 细菌趋化行为的移动机器人路径 规划[J]. 智能系统学报, 2014, 9(1): 69–75. PU Xingcheng, ZHAO Hongquan, ZHANG Yi. Mobile ro￾bot path planning research based on bacterial chemotaxis[J]. CAAI transactions on intelligent systems, 2014, 9(1): 69–75. [5] KAPANOGLU M, ALIKALFA M, OZKAN M, et al. A pattern-based genetic algorithm for multi-robot coverage path planning minimizing completion time[J]. Journal of in￾telligent manufacturing, 2012, 23(4): 1035–1045. [6] 杜鹏桢, 唐振民, 陆建峰, 等. 不确定环境下基于改进萤火 虫算法的地面自主车辆全局路径规划方法[J]. 电子学报, 2014, 42(3): 616–624. DU Pengzhen, TANG Zhenmin, LU Jianfeng, et al. Global path planning for ALV based on improved glowworm swarm optimization under uncertain environment[J]. Acta [7] 表 3 不同算法全覆盖路径规划性能比较 Table 3 Performance comparison of complete-coverage path planning with different algorithms 算法指标 生物启发神经网络算法栅格信度函数算法 区域覆盖率/% 100 100 重复覆盖区域/块 39 23 路径重复率/% 11.04 6.51 总行程/步 392 376 (a) ⩋➕ज़ࣽ⺊㏻㑽㐈ッ∁ 20 18 16 14 12 10 8 6 4 2 5 10 15 20 ᱖᥈㉎ٯࢁ ጞ᥈㉎ٯࢁ 䯈ⶹ➕ y/m x/m (b) ᴱᵨԍᏒܩ᪜ッ∁ 20 18 16 14 12 10 8 6 4 2 5 10 15 20 ᱖᥈㉎ٯࢁ ጞ᥈㉎ٯࢁ 䯈ⶹ➕ x/m y/m 图 7 不同算法全覆盖路径规划结果 Fig. 7 The results of complete-coverage path planning with different algorithms ·320· 智 能 系 统 学 报 第 13 卷