工程科学学报 Chinese Journal of Engineering 矿区废弃地移动机器人全覆盖路径规划 周林娜汪芸张鑫杨春雨 Complete coverage path planning of mobile robot on abandoned mine land ZHOU Lin-na,WANG Yun,ZHANG Xin,YANG Chun-yu 引用本文： 周林娜.汪芸，张鑫，杨春雨.矿区废弃地移动机器人全覆盖路径规划.工程科学学报，2020,42(9)：1220-1228.doi: 10.13374j.issn2095-9389.2019.09.09.004 ZHOU Lin-na,WANG Yun,ZHANG Xin,YANG Chun-yu.Complete coverage path planning of mobile robot on abandoned mine land[J].Chinese Journal of Engineering.2020,42(9):1220-1228.doi:10.13374/j.issn2095-9389.2019.09.09.004 在线阅读View online::https://doi..org10.13374/.issn2095-9389.2019.09.09.004 您可能感兴趣的其他文章 Articles you may be interested in 高速公路绿篱修剪机器人手臂避障路径规划 Obstacle avoidance path planning for expressway hedgerow pruning robot manipulator 工程科学学报.2019.41(1：134 https::/1doi.org10.13374.issn2095-9389.2019.01.015 具有状态约束与输入饱和的全向移动机器人自适应跟踪控制 Adaptive tracking control for omnidirectional mobile robots with full-state constraints and input saturation 工程科学学报.2019.41(9：1176 https:/doi.org10.13374.issn2095-9389.2019.09.009 基于BP神经网络的机器人波动摩擦力矩修正方法 Wave friction correction method for a robot based on BP neural network 工程科学学报.2019,41(8：1085 https:1doi.org10.13374.issn2095-9389.2019.08.014 巡线机器人延迟容忍传感器网络数据传输策略 Date delivery scheme of delay-tolerant mobile sensor networks for high-voltage power transmission line inspection robot 工程科学学报.2018,40(11：1412htps:oi.org10.13374.issn2095-9389.2018.11.015 煤矿搜救机器人履带式行走机构性能评价体系 Performance evaluation system of the tracked walking mechanism of a coal mine rescue robot 工程科学学报.2017,39(12头：1913 https:/doi.org10.13374.issn2095-9389.2017.12.019 深度神经网络模型压缩综述 A survey of model compression for deep neural networks 工程科学学报.2019,41(10)：1229 https:/1oi.org/10.13374.issn2095-9389.2019.03.27.002
矿区废弃地移动机器人全覆盖路径规划 周林娜 汪芸 张鑫 杨春雨 Complete coverage path planning of mobile robot on abandoned mine land ZHOU Lin-na, WANG Yun, ZHANG Xin, YANG Chun-yu 引用本文: 周林娜, 汪芸, 张鑫, 杨春雨. 矿区废弃地移动机器人全覆盖路径规划[J]. 工程科学学报, 2020, 42(9): 1220-1228. doi: 10.13374/j.issn2095-9389.2019.09.09.004 ZHOU Lin-na, WANG Yun, ZHANG Xin, YANG Chun-yu. Complete coverage path planning of mobile robot on abandoned mine land[J]. Chinese Journal of Engineering, 2020, 42(9): 1220-1228. doi: 10.13374/j.issn2095-9389.2019.09.09.004 在线阅读 View online: https://doi.org/10.13374/j.issn2095-9389.2019.09.09.004 您可能感兴趣的其他文章 Articles you may be interested in 高速公路绿篱修剪机器人手臂避障路径规划 Obstacle avoidance path planning for expressway hedgerow pruning robot manipulator 工程科学学报. 2019, 41(1): 134 https://doi.org/10.13374/j.issn2095-9389.2019.01.015 具有状态约束与输入饱和的全向移动机器人自适应跟踪控制 Adaptive tracking control for omnidirectional mobile robots with full-state constraints and input saturation 工程科学学报. 2019, 41(9): 1176 https://doi.org/10.13374/j.issn2095-9389.2019.09.009 基于BP神经网络的机器人波动摩擦力矩修正方法 Wave friction correction method for a robot based on BP neural network 工程科学学报. 2019, 41(8): 1085 https://doi.org/10.13374/j.issn2095-9389.2019.08.014 巡线机器人延迟容忍传感器网络数据传输策略 Date delivery scheme of delay-tolerant mobile sensor networks for high-voltage power transmission line inspection robot 工程科学学报. 2018, 40(11): 1412 https://doi.org/10.13374/j.issn2095-9389.2018.11.015 煤矿搜救机器人履带式行走机构性能评价体系 Performance evaluation system of the tracked walking mechanism of a coal mine rescue robot 工程科学学报. 2017, 39(12): 1913 https://doi.org/10.13374/j.issn2095-9389.2017.12.019 深度神经网络模型压缩综述 A survey of model compression for deep neural networks 工程科学学报. 2019, 41(10): 1229 https://doi.org/10.13374/j.issn2095-9389.2019.03.27.002
工程科学学报.第42卷.第9期：1220-1228.2020年9月 Chinese Journal of Engineering,Vol.42,No.9:1220-1228,September 2020 https://doi.org/10.13374/j.issn2095-9389.2019.09.09.004;http://cje.ustb.edu.cn 矿区废弃地移动机器人全覆盖路径规划 周林娜，汪芸，张鑫，杨春雨⑧ 中国矿业大学信息与控制工程学院，徐州221000 ☒通信作者，E-mail:chunyuyang@cumt.edu.cn 摘要矿区废弃地为室外大型非结构化环境，包含多种类型的障碍物且存在诸多不确定性因素，给移动机器人全覆盖路径 规划造成了极大的困难.本文使用牛耕式单元分解法结合生物激励神经网络算法完成移动机器人对矿区废弃地的全覆盖路 径规划.首先，针对矿区废弃地已知环境，采用牛耕式单元分解法对复杂环境做出区域分解，将具有综合复杂性的地图分解 为多个不含障碍物的子区域：然后，根据子区域的邻接关系构建无向图，采用深度优先搜索算法确定子区域间的转移顺序：最 后，采用生物激励神经网络算法确定子区域内部行走方式以及子区域间路径转移.仿真结果表明，生物激励神经网络算法在 解决机器人路径转移问题方面比其他路径规划算法更高效，所得的方法能够处理复杂的非结构化环境，完成废弃矿区移动机 器人的覆盖路径规划. 关键词矿区废弃地：路径规划：牛耕式单元分解法：区域分解：生物激励神经网络算法 分类号TP242.6 Complete coverage path planning of mobile robot on abandoned mine land ZHOU Lin-na,WANG Yun,ZHANG Xin,YANG Chun-yu School of Information and Control Engineering,China University of Mining and Technology,Xuzhou 221000,China Corresponding author,E-mail:chunyuyang@cumtedu.cn ABSTRACT Land resources are the fundamental and basic requirements for human survival and development as well as for the agricultural production and industrial construction.In recent years,due to the impact of industrial construction and chemical pollution, the cultivable land area is gradually decreasing,and the available agricultural land may be gravely insufficient for food production in the future.In China,the amount of abandoned mine land has increased significantly because of China's national supply-side structural reform program.The abandoned mine land can be transformed into agricultural land to effectively alleviate food crisis and the contradictory relationship existing between people and land,and improve the ecological environment of mining area.Abandoned mine land refers to the land that has lost its economic value due to a series of production operations and also the land that has not been artificially restored to original conditions after mining.Abandoned mine land is a large,external,and unstructured environment with multiple obstacles and uncertainties and cannot be accessed by humans.Therefore,mobile robots are used to access those areas,and even for mobile robots,planning their coverage path in those areas is difficult.In this paper,the boustrophedon cellular decomposition(BCD) method and biologically inspired neural network(BINN)algorithm were combined to complete the coverage path planning of mobile robots on abandoned mine land.First,for the known environment of the abandoned mine land,the BCD method was used to make regional decomposition of the complex environment.The map with comprehensive complexity was decomposed into several subregions without any obstacles.Second,an undirected graph(ie.,a set of objects called vertices or nodes that are connected together,where all the edges are bidirectional)was constructed according to the adjacency relationship of the subregions,and the depth first search algorithm was used to determine the transfer order between subregions.Finally,the BINN algorithm was used to determine the internal 收稿日期：2019-09-09 基金项目：国家自然科学基金资助项目(61873272)：江苏省双创团队资助项目(2017)
矿区废弃地移动机器人全覆盖路径规划 周林娜，汪 芸，张 鑫，杨春雨苣 中国矿业大学信息与控制工程学院，徐州 221000 苣通信作者，E-mail：chunyuyang@cumt.edu.cn 摘 要 矿区废弃地为室外大型非结构化环境，包含多种类型的障碍物且存在诸多不确定性因素，给移动机器人全覆盖路径 规划造成了极大的困难. 本文使用牛耕式单元分解法结合生物激励神经网络算法完成移动机器人对矿区废弃地的全覆盖路 径规划. 首先，针对矿区废弃地已知环境，采用牛耕式单元分解法对复杂环境做出区域分解，将具有综合复杂性的地图分解 为多个不含障碍物的子区域；然后，根据子区域的邻接关系构建无向图，采用深度优先搜索算法确定子区域间的转移顺序；最 后，采用生物激励神经网络算法确定子区域内部行走方式以及子区域间路径转移. 仿真结果表明，生物激励神经网络算法在 解决机器人路径转移问题方面比其他路径规划算法更高效，所得的方法能够处理复杂的非结构化环境，完成废弃矿区移动机 器人的覆盖路径规划. 关键词 矿区废弃地；路径规划；牛耕式单元分解法；区域分解；生物激励神经网络算法 分类号 TP242.6 Complete coverage path planning of mobile robot on abandoned mine land ZHOU Lin-na，WANG Yun，ZHANG Xin，YANG Chun-yu苣 School of Information and Control Engineering, China University of Mining and Technology, Xuzhou 221000, China 苣 Corresponding author, E-mail: chunyuyang@cumt.edu.cn ABSTRACT Land resources are the fundamental and basic requirements for human survival and development as well as for the agricultural production and industrial construction. In recent years, due to the impact of industrial construction and chemical pollution, the cultivable land area is gradually decreasing, and the available agricultural land may be gravely insufficient for food production in the future. In China, the amount of abandoned mine land has increased significantly because of China ’s national supply-side structural reform program. The abandoned mine land can be transformed into agricultural land to effectively alleviate food crisis and the contradictory relationship existing between people and land, and improve the ecological environment of mining area. Abandoned mine land refers to the land that has lost its economic value due to a series of production operations and also the land that has not been artificially restored to original conditions after mining. Abandoned mine land is a large, external, and unstructured environment with multiple obstacles and uncertainties and cannot be accessed by humans. Therefore, mobile robots are used to access those areas, and even for mobile robots, planning their coverage path in those areas is difficult. In this paper, the boustrophedon cellular decomposition (BCD) method and biologically inspired neural network (BINN) algorithm were combined to complete the coverage path planning of mobile robots on abandoned mine land. First, for the known environment of the abandoned mine land, the BCD method was used to make regional decomposition of the complex environment. The map with comprehensive complexity was decomposed into several subregions without any obstacles. Second, an undirected graph (i.e., a set of objects called vertices or nodes that are connected together, where all the edges are bidirectional) was constructed according to the adjacency relationship of the subregions, and the depth first search algorithm was used to determine the transfer order between subregions. Finally, the BINN algorithm was used to determine the internal 收稿日期: 2019−09−09 基金项目: 国家自然科学基金资助项目 (61873272)；江苏省双创团队资助项目 (2017) 工程科学学报，第 42 卷，第 9 期：1220−1228，2020 年 9 月 Chinese Journal of Engineering, Vol. 42, No. 9: 1220−1228, September 2020 https://doi.org/10.13374/j.issn2095-9389.2019.09.09.004; http://cje.ustb.edu.cn
周林娜等：矿区废弃地移动机器人全覆盖路径规划 1221· walking mode of and the regional transfer path between the subregions.Simulation results show that the BINN algorithm is of higher efficiency than any other path planning algorithms used to solve the robot path transfer problem.Moreover,the proposed method in this paper could work in complex,unstructured environments to complete the coverage path planning of mobile robots. KEY WORDS abandoned mine land;path planning;boustrophedon cellular decomposition method;regional decomposition; biologically inspired neural network algorithm 土地资源是人类生存和发展的载体，是进行 法⑧和单元分解法9.模板模型法通过将获取的环 农业生产和工业建设的基础物质条件，但我国人 境信息与各个模板匹配来完成遍历，对环境缺乏 口众多，人均用地严重不足，人地矛盾是我国面临 整体规划，难以适应变化的环境.单元分解法将整 的主要矛盾之一，改革开放以来，煤炭的过度开采 个环境的复杂度简化为子区域内环境的复杂度， 占用大量土地，矿区周边土壤质量恶劣.大量数据 在大型已知环境下被广泛应用，主要包括梯形单 表明：矿区废弃地复垦是缓解农业用地、改善矿区 元分解法IoI川、牛耕式单元分解(Boustrophedon 生态环境的重要途径川.矿区废弃地环境复杂，土 cellular decomposition,BCD)法2和莫尔斯单元分 地复垦存在很大难度，土地复垦的前提是对矿区 解法]BCD方法分解完成之后的子区域较少，本 土壤的全覆盖采样.移动机器人由于具备环境感 文采用BCD方法对环境做区域分解.单元分解完 知、行为决策及运动控制等能力，被广泛用于智能 成之后需要确定子区域内部覆盖方式，为应对未 清洁、农田作业、军事探测等领域的全覆盖作业冈 知障碍物的出现，本文采用BNN算法完成移动机 为椎进煤矿安全发展，国家煤矿安全监察局于 器人对子区域内部的覆盖.移动机器人在当前子 2019年提出了大力研发应用煤矿机器人的目标 区域内部覆盖完成之后需要转移到下一子区域， 本文面向矿区废弃地复垦的国家需求，研究移动 点对点路径规划具有巨大作用.Wang等w将 机器人全覆盖路径规划问题 Dijkstra算法应用到机器人路径规划算法方面，该 矿区废弃地土壤质量恶化，面临严重的生态 算法在迷宫环境中能够获得两点间的最短路径 问题，其非结构化的环境基础对移动机器人全覆 Fu等对A*算法进行改进并应用于工业机械臂， 盖路径规划提出挑战.全覆盖路径规划是指机器 该改进A*算法能够缩短路径规划距离.Wei和 人按照一定工作方式，在具有障碍物的环境中，无 Rent16]在机械臂上采用快速搜索随机树(Rapidly- 碰撞地遍历除障碍物以外的全部区域)根据对环 exploring random trees,RRT)算法，可以完成静态障 境信息的已知程度，全覆盖路径规划可分为信息 碍物和动态障碍物的避障，但并不能获得最短路 已知的全局路径规划和信息未知的局部路径规 径.Rashid等)采用蚁群算法解决简单环境地图 划.未知环境下的完全遍历路径规划方法主要包 和复杂环境地图中的移动机器人路径规划问题 括随机遍历法、漫步式探测法和沿边规划策略 张超等81提出了一种新的基于粒子群的改进蚁群 随机遍历法是一种基于无环境模型的路径规划方 算法，该算法采用全局异步与精英策略相结合方 法，该方法清扫过程简单但会造成重复率高及清 法更新信息素，减少了路径规划时间.群智能优化 扫时间过长等问题.漫步式探测方法主要包括动 算法能够解决移动机器人路径规划问题，但是此 态窗口法，该方法能够完成避障，实现环境的完全 类算法产生的路径平滑性较差.近年来，BNN算 覆盖，但时间成本高.沿边规划策略首先采用沿边 法逐渐被应用到移动机器人路径规划方面，王耀 学习建立环境模型，然后与局部路径规划相结合 南等通过在边界附近和障碍物之间增加假想非 遍历整个未知环境，生物激励神经树络(Biologically 障碍物临近点改进BNN算法，修改路径决策方 inspired neural network,BINN)算法-刀是一种基于 法，优化了路径质量.Zhu等)将BINN算法应用 沿边规划策略的方法，可以很好地应用于动态未 到水下机器人方面，解决了多机器人的任务分配 知环境 和路径规划问题.以上文献中的BNN算法均可 矿区废弃地的先验环境信息通过遥感卫星系 以被有效应用于移动机器人路径规划方面，但是 统获得，移动机器人的主要任务是对矿区实施全 没有充分利用已知环境信息 覆盖从而获得土壤采样信息，基于以上特点，本文 本文根据矿区废弃地先验环境信息，采用BCD 研究已知矿区环境全覆盖路径规划问题.已知环 结合BINN方法解决移动机器人对矿区废弃地的 境下的完全遍历路径规划算法主要包括模板模型 全覆盖路径规划问题，既包括子区域内部全覆盖
walking mode of and the regional transfer path between the subregions. Simulation results show that the BINN algorithm is of higher efficiency than any other path planning algorithms used to solve the robot path transfer problem. Moreover, the proposed method in this paper could work in complex, unstructured environments to complete the coverage path planning of mobile robots. KEY WORDS abandoned mine land； path planning； boustrophedon cellular decomposition method； regional decomposition； biologically inspired neural network algorithm 土地资源是人类生存和发展的载体，是进行 农业生产和工业建设的基础物质条件，但我国人 口众多，人均用地严重不足，人地矛盾是我国面临 的主要矛盾之一. 改革开放以来，煤炭的过度开采 占用大量土地，矿区周边土壤质量恶劣. 大量数据 表明：矿区废弃地复垦是缓解农业用地、改善矿区 生态环境的重要途径[1] . 矿区废弃地环境复杂，土 地复垦存在很大难度，土地复垦的前提是对矿区 土壤的全覆盖采样. 移动机器人由于具备环境感 知、行为决策及运动控制等能力，被广泛用于智能 清洁、农田作业、军事探测等领域的全覆盖作业[2] . 为推进煤矿安全发展 ，国家煤矿安全监察局于 2019 年提出了大力研发应用煤矿机器人的目标. 本文面向矿区废弃地复垦的国家需求，研究移动 机器人全覆盖路径规划问题. 矿区废弃地土壤质量恶化，面临严重的生态 问题，其非结构化的环境基础对移动机器人全覆 盖路径规划提出挑战. 全覆盖路径规划是指机器 人按照一定工作方式，在具有障碍物的环境中，无 碰撞地遍历除障碍物以外的全部区域[3] . 根据对环 境信息的已知程度，全覆盖路径规划可分为信息 已知的全局路径规划和信息未知的局部路径规 划[4] . 未知环境下的完全遍历路径规划方法主要包 括随机遍历法、漫步式探测法和沿边规划策略. 随机遍历法是一种基于无环境模型的路径规划方 法，该方法清扫过程简单但会造成重复率高及清 扫时间过长等问题. 漫步式探测方法主要包括动 态窗口法，该方法能够完成避障，实现环境的完全 覆盖，但时间成本高. 沿边规划策略首先采用沿边 学习建立环境模型，然后与局部路径规划相结合 遍历整个未知环境，生物激励神经网络（Biologically inspired neural network, BINN）算法[5−7] 是一种基于 沿边规划策略的方法，可以很好地应用于动态未 知环境. 矿区废弃地的先验环境信息通过遥感卫星系 统获得，移动机器人的主要任务是对矿区实施全 覆盖从而获得土壤采样信息，基于以上特点，本文 研究已知矿区环境全覆盖路径规划问题. 已知环 境下的完全遍历路径规划算法主要包括模板模型 法[8] 和单元分解法[9] . 模板模型法通过将获取的环 境信息与各个模板匹配来完成遍历，对环境缺乏 整体规划，难以适应变化的环境. 单元分解法将整 个环境的复杂度简化为子区域内环境的复杂度， 在大型已知环境下被广泛应用，主要包括梯形单 元分解法 [10−11]、牛耕式单元分 解 (Boustrophedon cellular decomposition, BCD) 法[12] 和莫尔斯单元分 解法[13] . BCD 方法分解完成之后的子区域较少，本 文采用 BCD 方法对环境做区域分解. 单元分解完 成之后需要确定子区域内部覆盖方式，为应对未 知障碍物的出现，本文采用 BINN 算法完成移动机 器人对子区域内部的覆盖. 移动机器人在当前子 区域内部覆盖完成之后需要转移到下一子区域， 点对点路径规划具有巨大作用 . Wang 等 [14] 将 Dijkstra 算法应用到机器人路径规划算法方面，该 算法在迷宫环境中能够获得两点间的最短路径. Fu 等[15] 对 A*算法进行改进并应用于工业机械臂， 该改进 A*算法能够缩短路径规划距离. Wei 和 Ren[16] 在机械臂上采用快速搜索随机树 (Rapidlyexploring random trees, RRT) 算法，可以完成静态障 碍物和动态障碍物的避障，但并不能获得最短路 径. Rashid 等[17] 采用蚁群算法解决简单环境地图 和复杂环境地图中的移动机器人路径规划问题. 张超等[18] 提出了一种新的基于粒子群的改进蚁群 算法，该算法采用全局异步与精英策略相结合方 法更新信息素，减少了路径规划时间. 群智能优化 算法能够解决移动机器人路径规划问题，但是此 类算法产生的路径平滑性较差. 近年来，BINN 算 法逐渐被应用到移动机器人路径规划方面，王耀 南等[6] 通过在边界附近和障碍物之间增加假想非 障碍物临近点改进 BINN 算法，修改路径决策方 法，优化了路径质量. Zhu 等[7] 将 BINN 算法应用 到水下机器人方面，解决了多机器人的任务分配 和路径规划问题. 以上文献中的 BINN 算法均可 以被有效应用于移动机器人路径规划方面，但是 没有充分利用已知环境信息. 本文根据矿区废弃地先验环境信息，采用 BCD 结合 BINN 方法解决移动机器人对矿区废弃地的 全覆盖路径规划问题，既包括子区域内部全覆盖 周林娜等： 矿区废弃地移动机器人全覆盖路径规划 · 1221 ·
·1222 工程科学学报，第42卷，第9期 路径规划又包括子区域间路径转移.首先采用 以上实际情况，对环境做如下假定： BCD方法划分整个非结构化的环境，然后通过深 (1)假定该矿区废弃地环境全局信息已知； 度优先搜索(Depth first search,.DFS)算法确定子区 (2)假定环境中的障碍物存在复杂性，即同时 域间遍历顺序，最后采用BNN算法完成子区域 存在规则障碍物和非规则障碍物： 内部覆盖和子区域间路径转移，从而实现矿区全 (3)在做仿真实验时，假定煤矸山为三角形障 覆盖. 碍物，废弃厂区为多边形障碍物，矿区积水区及其 他复杂障碍物以非规则障碍物表示 1矿区废弃地基本环境及假设 2矿区废弃地全覆盖路径规划 矿区废弃地是指矿山开采过程中失去经济利 用价值的土地，也指在采矿期间任何没有经过人 矿区废弃地为室外大型非结构化环境，移动 为修复的土地.矿区废弃地存在大量煤矸山、废 机器人对该环境的路径规划存在较大难度.目前 弃厂区以及踩空塌陷区和积水区等，这些特点造 矿区环境下的移动机器人研究任务多为点对点路 成了矿区废弃地环境的复杂性.图1为国内某矿 径规划9-20，本文将采用区域分解法1-21实现全 区废弃地现状图，矿区废弃地的先验环境信息由 覆盖路径规划，主要包括三个部分：目标区域分 遥感卫星系统获得，但是环境中可能存在部分未 解、子区域规划和各子区域遍历.具体流程如图3 被感知区域，导致矿区废弃地环境复杂.图2为矿 所示 区废弃地复杂障碍图 Begin Map modeling Regional BCD method decomposition Sub-region planning DFS algorithm Sub-region coverage Path transition BINN algorithm 图1废弃矿区现状 Fig.1 Status of abandoned mine land Missing area？ (a) (b) N End 图3全覆盖路径规划流程图 Fig.3 Flow chart of complete coverage path planning 2.1目标区域分解 (c) (d) 单元分解法是一种运动规划技术，该方法将 所有自由支配空间分解为多个单元，使得所有单 元联合起来是原始自由空间.传统单元分解法是 梯形单元分解法，BCD方法☒1在梯形单元分解 法上进行改进，该方法假设一条垂直线（被称作切 片)从左到右扫过一个充满多边形障碍的有界环 困2废弃矿区复杂环境.(a)积水区：(b)废弃厂区：(c)尾矿、煤研石 的堆占：(d)周边土壤现状 境，每遇到顶点可上下延伸的临界点便进行分割， Fig.2 Complex environment of abandoned mine land:(a)pools zone; 最终环境被分割为多个不含障碍物的子区域.相 (b)abandoned factory;(c)heap of tailings and gangue;(d)status of 比梯形单元分解法，BCD方法产生更少的子区域， surrounding soil 可以减少机器人的路径冗余，进一步降低能源消 为了实现非结构化矿区废弃地环境移动机器 耗和时间损耗.因此，BCD方法适合矿区废弃地 人全覆盖路径规划的遍历且减少重复覆盖，根据 环境.表1给出了BCD方法的步骤
路径规划又包括子区域间路径转移. 首先采用 BCD 方法划分整个非结构化的环境，然后通过深 度优先搜索（Depth first search, DFS）算法确定子区 域间遍历顺序，最后采用 BINN 算法完成子区域 内部覆盖和子区域间路径转移，从而实现矿区全 覆盖. 1 矿区废弃地基本环境及假设 矿区废弃地是指矿山开采过程中失去经济利 用价值的土地，也指在采矿期间任何没有经过人 为修复的土地. 矿区废弃地存在大量煤矸山、废 弃厂区以及踩空塌陷区和积水区等，这些特点造 成了矿区废弃地环境的复杂性. 图 1 为国内某矿 区废弃地现状图，矿区废弃地的先验环境信息由 遥感卫星系统获得，但是环境中可能存在部分未 被感知区域，导致矿区废弃地环境复杂. 图 2 为矿 区废弃地复杂障碍图. 图 1 废弃矿区现状 Fig.1 Status of abandoned mine land (a) (b) (c) (d) 图 2 废弃矿区复杂环境. （a）积水区；（b）废弃厂区；（c）尾矿、煤矸石 的堆占；（d）周边土壤现状 Fig.2 Complex environment of abandoned mine land: (a) pools zone; (b) abandoned factory; (c) heap of tailings and gangue; (d) status of surrounding soil 为了实现非结构化矿区废弃地环境移动机器 人全覆盖路径规划的遍历且减少重复覆盖，根据 以上实际情况，对环境做如下假定： （1）假定该矿区废弃地环境全局信息已知； （2）假定环境中的障碍物存在复杂性，即同时 存在规则障碍物和非规则障碍物； （3）在做仿真实验时，假定煤矸山为三角形障 碍物，废弃厂区为多边形障碍物，矿区积水区及其 他复杂障碍物以非规则障碍物表示. 2 矿区废弃地全覆盖路径规划 矿区废弃地为室外大型非结构化环境，移动 机器人对该环境的路径规划存在较大难度. 目前 矿区环境下的移动机器人研究任务多为点对点路 径规划[19−20] ，本文将采用区域分解法[21−22] 实现全 覆盖路径规划，主要包括三个部分：目标区域分 解、子区域规划和各子区域遍历. 具体流程如图 3 所示. Begin Map modeling Regional decomposition Sub-region planning Sub-region coverage Path transition Missing area? End BCD method DFS algorithm BINN algorithm Y N 图 3 全覆盖路径规划流程图 Fig.3 Flow chart of complete coverage path planning 2.1 目标区域分解 单元分解法[9] 是一种运动规划技术，该方法将 所有自由支配空间分解为多个单元，使得所有单 元联合起来是原始自由空间. 传统单元分解法是 梯形单元分解法[10] ，BCD 方法[12] 在梯形单元分解 法上进行改进，该方法假设一条垂直线（被称作切 片）从左到右扫过一个充满多边形障碍的有界环 境，每遇到顶点可上下延伸的临界点便进行分割， 最终环境被分割为多个不含障碍物的子区域. 相 比梯形单元分解法，BCD 方法产生更少的子区域， 可以减少机器人的路径冗余，进一步降低能源消 耗和时间损耗. 因此，BCD 方法适合矿区废弃地 环境. 表 1 给出了 BCD 方法的步骤. · 1222 · 工程科学学报，第 42 卷，第 9 期
周林娜等：矿区废弃地移动机器人全覆盖路径规划 ·1223 表1BCD方法步骤 Table 1 BCD method steps Step Content Input Original map Step 1 Image preprocessing:erode the map Step2 Traverse the array columns to determine the connectivity of slices,and retum the number of connectivity and connected regions Step3 If the slice connectivity changes,determine it is IN event or OUT event,and retum the store data of current sub-region Step4 Represent partition information on a map Output Regional decomposition map 图4(a)为矿区废弃地仿真环境，该环境具有 本文所使用的BCD方法能够有效分解具有综 复杂性，包括规则几何障碍物和非规则障碍物， 合复杂性的环境.实验证明，该方法可以被广泛应 采用BCD方法对该环境做区域分解，分解结果如 用于矿区废弃地等复杂室外环境，它能够有效减 图4(b)所示.其中，C1~C10为分解后的10个子 少机器人在室外做全覆盖路径规划的难度 区域 2.2子区域规划 区域分解完成之后，机器人可通过两个步骤 (a) (b) 完成对整个区域的覆盖：(1)在邻接图中找到一个 ② ⑧ 详尽的行走顺序，该覆盖顺序可以指导机器人到 ① 达工作空间中所有可到达的子区域：(2)完成子区 域内部覆盖以及区域间的转移.本模块主要完成 6 子区域遍历顺序规划，采用的算法为DFS算法. DFS算法PI是图论中最著名的一种搜索算 图4矿区废弃地仿真图.(a)仿真环境：(b)区域分解图 Fig.4 Simulation map of abandoned mine land:(a)simulation 法，该算法经常被用来遍历图中所有点，找到一条 environment;(b)regional decomposition map 可供行驶的详尽覆盖路径.表2为该算法步骤 表2DFS算法步骤 Table 2 DFS algorithm steps Step Content Input Sub-region adjacency graphG Step1 Choose the starting cell v.Insert it into the path list.Mark it as visited Step2 Visit an adjacent cell w.Insert this cell into the path list.Mark it as visited Step3 Start from wi,go to the unvisited cell w2 in the neighbor list of the wi,insert this cell into the path list and mark it as visited. Repeat this procedure until all cells in G are visited Step4 Back track from the last cell and insert each element that is visited to the front of the path list,until an element with an unvisited neighbor is encountered.Insert this element to the front of the path list Step5 Repeat the above procedure until all cells in the adjacency graph have been visited Output Sub-region path list 将BCD方法中切片的运行方向定义为从左往 (a) (b) 右，图5(a)为区域分解完成之后的子区域构成的 AB→D→E 邻接图，根据切片运行方向，将A设置为起始点， D G 图5(b)即为使用DFS算法规划的子区域顺序结果 CFI—J—H 图.图5(b)中，A为机器人遍历的第一个子区域， 当A遍历结束时机器人从该区域结点到转移下一 个子区域B的起始点，对B区域内部进行全覆盖 图5子区域连接图.(a)邻接图：(b)转移序列图 Fig.5 Connection diagram of subregions:(a)adjacency map;(b) 遍历，以此类推，直至到达最后一个子区域C的结点 transfer order map
表 1 BCD 方法步骤 Table 1 BCD method steps Step Content Input Original map Step 1 Image preprocessing: erode the map Step 2 Traverse the array columns to determine the connectivity of slices, and return the number of connectivity and connected regions Step 3 If the slice connectivity changes, determine it is IN event or OUT event, and return the store data of current sub-region Step 4 Represent partition information on a map Output Regional decomposition map 图 4（a）为矿区废弃地仿真环境，该环境具有 复杂性，包括规则几何障碍物和非规则障碍物， 采用 BCD 方法对该环境做区域分解，分解结果如 图 4（b）所示. 其中，C1～C10 为分解后的 10 个子 区域. (a) (b) C1 C2 C3 C4 C5 C6 C10 C8 C7 C9 图 4 矿区废弃地仿真图. （a）仿真环境；（b）区域分解图 Fig.4 Simulation map of abandoned mine land: (a) simulation environment; (b) regional decomposition map 本文所使用的 BCD 方法能够有效分解具有综 合复杂性的环境. 实验证明，该方法可以被广泛应 用于矿区废弃地等复杂室外环境，它能够有效减 少机器人在室外做全覆盖路径规划的难度. 2.2 子区域规划 区域分解完成之后，机器人可通过两个步骤 完成对整个区域的覆盖：（1）在邻接图中找到一个 详尽的行走顺序，该覆盖顺序可以指导机器人到 达工作空间中所有可到达的子区域；（2）完成子区 域内部覆盖以及区域间的转移. 本模块主要完成 子区域遍历顺序规划，采用的算法为 DFS 算法. DFS 算法[23] 是图论中最著名的一种搜索算 法，该算法经常被用来遍历图中所有点，找到一条 可供行驶的详尽覆盖路径. 表 2 为该算法步骤. 表 2 DFS 算法步骤 Table 2 DFS algorithm steps Step Content Input Sub-region adjacency graph G Step 1 Choose the starting cell v. Insert it into the path list. Mark it as visited Step 2 Visit an adjacent cell w1. Insert this cell into the path list. Mark it as visited Step 3 Start from w1, go to the unvisited cell w2 in the neighbor list of the w1, insert this cell into the path list and mark it as visited. Repeat this procedure until all cells in G are visited Step 4 Back track from the last cell and insert each element that is visited to the front of the path list, until an element with an unvisited neighbor is encountered. Insert this element to the front of the path list Step 5 Repeat the above procedure until all cells in the adjacency graph have been visited Output Sub-region path list 将 BCD 方法中切片的运行方向定义为从左往 右，图 5（a）为区域分解完成之后的子区域构成的 邻接图，根据切片运行方向，将 A 设置为起始点， 图 5（b）即为使用 DFS 算法规划的子区域顺序结果 图. 图 5（b）中，A 为机器人遍历的第一个子区域， 当 A 遍历结束时机器人从该区域结点到转移下一 个子区域 B 的起始点，对 B 区域内部进行全覆盖 遍历，以此类推，直至到达最后一个子区域 C 的结点. A B (a) (b) C D E F G H I J A C B D F E H G I J 图 5 子区域连接图. （a）邻接图；（b）转移序列图 Fig.5 Connection diagram of subregions: (a) adjacency map; (b) transfer order map 周林娜等： 矿区废弃地移动机器人全覆盖路径规划 · 1223 ·
·1224 工程科学学报，第42卷，第9期 2.3各子区域遍历 陷人死区 2.3.1BINN算法 机器人生成全覆盖的路径为： BINN算法是一种在线规划算法，该算法将每 Pnxpa max xj+cyjj=1.2,....k (5) 个栅格看作一个神经元，整个栅格地图变为由神 经网络组成的拓扑状态空间，其中神经元的活性 其中，c是一个正常数，代表方向权重的选择，y是 和机器人上一步所在位置pp、当前所在位置Pe、下 值由下式表示： 一步所在位置P相关的函数，y函数定义为： dxi =-Axi+(B-x 为149 (6) -(D+x)[° (1) 式中，△9；∈0，，它表示当前移动方向与下一移动 式(1)为分流方程，通过该方程可以计算出 方向之间的夹角.全覆盖路径规划过程如图6所示 栅格地图中每个神经元的活性值.式中：为第个 Begin 神经元的活性值；t是时间量；A、B和D为非负常数， 其中A代表衰减率，B代表神经元活性状态的上限， Initialize the neural network map D代表神经元活性状态的下限；k为与第个神经元 直接连接神经元的个数：为外部输入，可定义为： Calculate the current neuron activity value E,目标点 E,障碍物 (2) Adjacent neuron activity N Dead zone, 0,其他 is greater than current neuron? stop and waiting 其中：E是一个远远大于B的正常数+∑w） Y 和[分别表示兴奋输入和抑制输入，w=fd), Move to the next position d是第个神经元与第个神经元所在位置处在状 态空间中的欧几里得距离，为任意的单调减函 Complete coverage? 数，f可定义为 f(a)= uldij 0<dij<ro (3) End 0 d≥ro 图6BNN算法流程图 式中，和ro均为正常数，代表当前神经元与周边 Fig.6 Flow chart of BINN algorithm 神经元之间的侧向连接，0<”<1.神经元只在一 2.3.2子区域内部遍历 个小范围(0，o)内有局部连接，这个范围被称为神 在区域分解和子区域遍历顺序确定后，关键 经元的接受域，该接受域确保当前神经元周边 步骤是完成对子区域内部的遍历.BNN算法是一 8个神经元均在局部连接范围，每个栅格的长度 种在线规划算法，不需要学习过程，适合处理未知 为1，o的范围在（V2,2V2)之间，根据文献25]， 情况.由于矿区废弃地结构复杂，环境中可能存在 o的值取2.神经元间的连接权重是对称的，即 未知障碍物或移动障碍物等一系列现象，为了在 后期的工作中能够较好地应对突发状况，本文采 BNN算法既可以完成点对点路径规划又可 用BNN算法完成对每个子区域内部全覆盖 以完成全覆盖路径规划.机器人生成点对点的路 2.3.3区域路径转移 径为： 当前子区域内部覆盖完成之后到下一子区域 pn xpa maxxj.j=1.2.....k (4) 内部覆盖之前需要子区域间的路径转移，从而使 该路径生成过程为：机器人在当前位置选择 移动机器人按照子区域规划序列完成对所有子区 邻接神经元中具有最大活性值的神经元栅格作为 域的覆盖.针对该问题，本节主要使用BNN算法 下一位置，到达下一位置后，下一位置成为新的当 规划从上一个子区域遍历终点到下一个子区域遍 前位置，以此类推，直到到达目标点栅格.如果周 历起点的最短路径搜索，并计算该算法在最短路 边8个邻接神经元的活性值都不大于当前栅格的 径和时间消耗方面的总代价.因此，定义一系列由 神经元活性，则机器人待在原地保持不动，机器人 点组成的转移路径P:
2.3 各子区域遍历 2.3.1 BINN 算法 BINN 算法是一种在线规划算法，该算法将每 个栅格看作一个神经元，整个栅格地图变为由神 经网络组成的拓扑状态空间，其中神经元的活性 值由下式表示： dxi dt =− Axi +(B− xi) [Ii] + + ∑ k j=1 wi j[ xj ] + −(D+ xi)[Ii] − （1） xi i t A B D A B D k i Ii 式（1）为分流方程[24] ，通过该方程可以计算出 栅格地图中每个神经元的活性值. 式中： 为第 个 神经元的活性值； 是时间量； 、 和 为非负常数， 其中 代表衰减率， 代表神经元活性状态的上限， 代表神经元活性状态的下限； 为与第 个神经元 直接连接神经元的个数； 为外部输入，可定义为： Ii = E, 目标点 − E, 障碍物 0, 其他 （2） ( [Ii] ++ ∑k j=1wi j[ xj ]+ ) [Ii] − wi j = f ( di j) di j i j f f 其中：E 是一个远远大于B 的正常数； 和 分别表示兴奋输入和抑制输入， ， 是第 个神经元与第 个神经元所在位置处在状 态空间中的欧几里得距离， 为任意的单调减函 数， 可定义为 f ( di j) = { u/di j 0 < di j < r0 0 di j ⩾ r0 （3） u r0 u 0 < u < 1 (0,r0) i r0 ( √ 2,2 √ 2 ) r0 wi j = wji 式中， 和 均为正常数， 代表当前神经元与周边 神经元之间的侧向连接， . 神经元只在一 个小范围 内有局部连接，这个范围被称为神 经元 的接受域，该接受域确保当前神经元周边 8 个神经元均在局部连接范围，每个栅格的长度 为 1， 的范围在 之间 ，根据文 献 [25]， 的值取 2. 神经元间的连接权重是对称的，即 . BINN 算法既可以完成点对点路径规划又可 以完成全覆盖路径规划. 机器人生成点对点的路 径为： pn ⇐ xpn = max{ x j , j = 1,2,··· , k } （4） 该路径生成过程为：机器人在当前位置选择 邻接神经元中具有最大活性值的神经元栅格作为 下一位置，到达下一位置后，下一位置成为新的当 前位置，以此类推，直到到达目标点栅格. 如果周 边 8 个邻接神经元的活性值都不大于当前栅格的 神经元活性，则机器人待在原地保持不动，机器人 陷入死区. 机器人生成全覆盖的路径为： pn ⇐ xpn = max{ xj +cy j , j = 1,2,··· , k } （5） c yj pp pc pj yj 其中， 是一个正常数，代表方向权重的选择， 是 和机器人上一步所在位置 、当前所在位置 、下 一步所在位置 相关的函数， 函数定义为： yj = 1− ∆θ j π （6） 式中， ∆θ j ∈ [0,π] ，它表示当前移动方向与下一移动 方向之间的夹角. 全覆盖路径规划过程如图 6 所示. Begin Initialize the neural network map Calculate the current neuron activity value Adjacent neuron activity is greater than current neuron? Move to the next position Complete coverage? End Dead zone, stop and waiting Y N Y N 图 6 BINN 算法流程图 Fig.6 Flow chart of BINN algorithm 2.3.2 子区域内部遍历 在区域分解和子区域遍历顺序确定后，关键 步骤是完成对子区域内部的遍历. BINN 算法是一 种在线规划算法，不需要学习过程，适合处理未知 情况. 由于矿区废弃地结构复杂，环境中可能存在 未知障碍物或移动障碍物等一系列现象，为了在 后期的工作中能够较好地应对突发状况，本文采 用 BINN 算法完成对每个子区域内部全覆盖. 2.3.3 区域路径转移 P 当前子区域内部覆盖完成之后到下一子区域 内部覆盖之前需要子区域间的路径转移，从而使 移动机器人按照子区域规划序列完成对所有子区 域的覆盖. 针对该问题，本节主要使用 BINN 算法 规划从上一个子区域遍历终点到下一个子区域遍 历起点的最短路径搜索，并计算该算法在最短路 径和时间消耗方面的总代价. 因此，定义一系列由 点组成的转移路径 ： · 1224 · 工程科学学报，第 42 卷，第 9 期
周林娜等：矿区废弃地移动机器人全覆盖路径规划 1225 P={P1,P2,…,Pk} (7) 实验如下所示 其中，P1,p2,…,P表示路径P经过的栅格坐标点， 3.1参数设置与仿真环境 假设路径P的总代价为C(P),该路径代价由栅格之 为了验证BNN算法做全覆盖路径规划时的 间的转移距离d(pp+1)和完成这项任务消耗的时 效果，设计相关仿真实验，合理参数设置和仿真实 间t构成，路径P的转移代价可以由式(8)表示： 验环境设定是确保实验成功的重要环节，本文参 数设置环节依据文献[25]，并根据实验环境做了相 C(P)= d(Pi Pi1) i=1,2,…,k-1 (8) 应调整.本文设定27×27栅格地图，在该栅格地图 中自由栅格值为1，障碍栅格值为-1，B和D代表的 d(p,P+)代表两栅格间的欧氏距离，它的取值 是神经活性上界与下界，B和D取1和-1：E代表外 可用式(9)表示： 部输入，远远大于B和D,将E的取值设为100：A代 d(PPuD)=V(dm-ap)+(b-ba) (9) 表神经元活性衰减速率，本文A取20：c代表方向权 重的选择，在全覆盖路径规划中，c的选择会影响 其中，a代表神经元的横坐标，b代表神经元的纵坐标. 机器人路径决策，为平滑机器人的路径，将c的值 因此，区域间路径转移算法目标就是寻找一 取为1：代表当前神经元与周边神经元活性之间侧 条路径P,使得C(P)满足： 向连接，对当前神经元的活性值有较大影响，在做 C(P)=minC(Pm) (10) 全覆盖路径规划时为获得规则路径，值取1，在做 其中，Pm是从上一个区域终点到下一个区域起始 点对点路径规划时考虑到目标神经元的导向作 点的m条路径 用，根据不同环境重新设定 本文所提出方法同样适应于室内具有综合复 本文中的仿真实验均在Matlab R20l7b中进 杂性的环境 行，7.9GB计算机内存，3.41 GHz CPU速度 3仿真实验 3.2子区域遍历实验 假设仿真工作环境是由27×27神经元组成网 本文的内容应用于移动机器人矿区废弃地环 络拓扑结构，本小节的主要目标是使用BNN算法 境路径规划.本节分别对子区域内部遍历和子区 实现子区域内部全覆盖和子区域间路径转移.在 域间路径转移进行仿真实验，其中路径转移实验 子区域内部覆盖实验中，令所有神经元的活性值 中BINN算法和其他路径规划算法同时进行.实 为0，分流方程的参数为E=100,A=20,B=1,D=-1, 验方案规划：首先，对工作环境进行栅格地图建 μ=L,c=1,图7(a)给出了在多种障碍物环境下的 模，建立分区之后的环境模型；其次，采用DFS算 移动机器人全覆盖路径规划.在区域间路径转移 法规划子区域遍历序列；最后，采用BNN算法完 实验中主要考虑三个区域的路径转移，由于先验 成对每个子区域内部的覆盖以及子区域间路径转 环境信息已知，给定每个子区域的起始点与结点， 移，并与其他路径规划算法做对比仿真实验.仿真 在图中用“*”表示子区域的起始点，“☆”表示子区 (a) (b) 0 1 20 20 10 20 25 10 15 20 Grid number Grid number 图7子区域遍历结果.()全覆盖结果：(b)路径转移结果 Fig.7 Coverage results of subregions:(a)complete coverage result;(b)path transition result
P = {p1, p2,··· , pk} （7） p1, p2,··· , pk P P C(P) d (pi , pi+1) ts P 其中， 表示路径 经过的栅格坐标点， 假设路径 的总代价为 ，该路径代价由栅格之 间的转移距离 和完成这项任务消耗的时 间 构成，路径 的转移代价可以由式（8）表示： C(P) = ts , ∑ i d (pi , pi+1) , i = 1,2,··· , k−1 （8） d(pi , pi+1) 代表两栅格间的欧氏距离，它的取值 可用式（9）表示： d (pi , pi+1)= √( api+1 −api )2 + ( bpi+1 −bpi )2 （9） 其中，a 代表神经元的横坐标，b 代表神经元的纵坐标. P C(P) 因此，区域间路径转移算法目标就是寻找一 条路径 ，使得 满足： C(P)=minC(Pm) （10） Pm m 其中， 是从上一个区域终点到下一个区域起始 点的 条路径. 本文所提出方法同样适应于室内具有综合复 杂性的环境. 3 仿真实验 本文的内容应用于移动机器人矿区废弃地环 境路径规划. 本节分别对子区域内部遍历和子区 域间路径转移进行仿真实验，其中路径转移实验 中 BINN 算法和其他路径规划算法同时进行. 实 验方案规划：首先，对工作环境进行栅格地图建 模，建立分区之后的环境模型；其次，采用 DFS 算 法规划子区域遍历序列；最后，采用 BINN 算法完 成对每个子区域内部的覆盖以及子区域间路径转 移，并与其他路径规划算法做对比仿真实验. 仿真 实验如下所示. 3.1 参数设置与仿真环境 27×27 1 −1 B D B D −1 E B D E 100 A A 20 c c c 1 u u 1 为了验证 BINN 算法做全覆盖路径规划时的 效果，设计相关仿真实验，合理参数设置和仿真实 验环境设定是确保实验成功的重要环节，本文参 数设置环节依据文献 [25]，并根据实验环境做了相 应调整. 本文设定 栅格地图，在该栅格地图 中自由栅格值为 ，障碍栅格值为 ， 和 代表的 是神经活性上界与下界， 和 取 1 和 ； 代表外 部输入，远远大于 和 ，将 的取值设为 ； 代 表神经元活性衰减速率，本文 取 ； 代表方向权 重的选择，在全覆盖路径规划中， 的选择会影响 机器人路径决策，为平滑机器人的路径，将 的值 取为 ； 代表当前神经元与周边神经元活性之间侧 向连接，对当前神经元的活性值有较大影响，在做 全覆盖路径规划时为获得规则路径， 值取 ，在做 点对点路径规划时考虑到目标神经元的导向作 用，根据不同环境重新设定. 本文中的仿真实验均在 Matlab R2017b 中进 行，7.9 GB 计算机内存，3.41 GHz CPU 速度. 3.2 子区域遍历实验 27×27 0 E=100, A = 20, B = 1, D = −1, µ = 1, c = 1 假设仿真工作环境是由 神经元组成网 络拓扑结构，本小节的主要目标是使用 BINN 算法 实现子区域内部全覆盖和子区域间路径转移. 在 子区域内部覆盖实验中，令所有神经元的活性值 为 ，分流方程的参数为 ，图 7（a）给出了在多种障碍物环境下的 移动机器人全覆盖路径规划. 在区域间路径转移 实验中主要考虑三个区域的路径转移，由于先验 环境信息已知，给定每个子区域的起始点与结点， 在图中用“*”表示子区域的起始点，“☆”表示子区 5 10 15 20 25 5 10 15 20 25 Grid number Grid number 5 10 15 20 25 5 10 15 20 25 Grid number Grid number (a) (b) 图 7 子区域遍历结果. （a）全覆盖结果；（b）路径转移结果 Fig.7 Coverage results of subregions: (a) complete coverage result; (b) path transition result 周林娜等： 矿区废弃地移动机器人全覆盖路径规划 · 1225 ·
·1226 工程科学学报，第42卷，第9期 域的结点，对BNN算法分流方程参数分别做如下 减少路径的转折，优化算法的搜索路径.实验结果 设定：E=100,A=20,B=1,D=-1,c=1.因为三部分 证明算法实现了自主避障并有效搜索到了目标 转移区域环境不同，所以算法需要做出不同的路径 点，路径没有出现跨越和迷失现象，该算法在点对 选择，经过调试，在不同的子区域设置不同的μ来获 点路径规划中具有高效性 得较短的转移路径，当J一I区域之间取μ=1,1一F 3.3对比实验 区域之间取μ=3，F一C区域之间取μ=1时，三条 为证明BNN算法在区域转移方面的性能，本 转移路径最短.图7(b)给出了BNN算法完成的子 文选用几种经典点对点路径规划算法与BNN算 区域间的路径转移仿真结果图，图中用“×”表示 法做对比试验.通常情况下，路径转移距离和路径 BNN算法生成的子区域间的转移路径 转移时间是衡量覆盖任务的重要指标.路径转移 在图7(a)中，环境中的障碍物形状各异，机器 距离为机器人从上一个子区域结点到下一个子区 人从初始位置(2,2)开始运动，根据仿真结果可知， 域起始点生成的路径距离；路径转移时间为完成 该算法能够在这种复杂环境下做出相应的路径选 这项任务消耗的时间，通过这两种性能指标来评 择策略，并且在每一个子区域内部完成全覆盖.本 价两种算法最短转移路径的总代价 例子中区域重复覆盖率为0，总覆盖面积达到 本小节选用的对比算法为A*算法、Dijkstra算 100%,有效证明了该算法的可行性.从图7(a)中 法和RRT算法.BINN算法、A*算法、Dijkstra算 可以看到虚线经过了障碍物栅格，路径转移算法 法均是基于栅格地图，路径转移距离为所有栅格 需要完成避障功能.三个部分路径转移的实施离 之间的欧氏距离之和；RRT算法基于坐标地图，路 不开点对点路径规划算法，本模块BNN算法在做 径转移距离为所有坐标点之间的距离之和，栅格 点对点路径规划时，在目标点处增加了神经元活 地图与坐标地图具有对应性，因此几种算法路径 性值，并在三个区域转移部分分别设置不同的来 长度具有可比性.图8、表3、表4和图9展示了四 (a) (b) 15 20 0 3 3 10 15 20 25 10 15 20 25 Grid number Grid number d 5 0 15 20 25 10 15 20 25 Grid number Grid number 图8 实验结果对比.(a)BNN算法：(b)A*算法：(c)Dijkstra算法：(d)RRT算法 Fig.8 Comparison of experimental results:(a)BINN algorithm;(b)A*algorithm;(c)Dijkstra algorithm;(d)RRT algorithm
E=100, A = 20, B = 1, D = −1, c = 1 µ µ = 1 µ = 3 µ = 1 域的结点，对 BINN 算法分流方程参数分别做如下 设定： . 因为三部分 转移区域环境不同，所以算法需要做出不同的路径 选择，经过调试，在不同的子区域设置不同的 来获 得较短的转移路径，当 J—I 区域之间取 , I—F 区域之间取 , F—C 区域之间取 时，三条 转移路径最短. 图 7（b）给出了 BINN算法完成的子 区域间的路径转移仿真结果图，图中用“×”表示 BINN 算法生成的子区域间的转移路径. µ 在图 7（a）中，环境中的障碍物形状各异，机器 人从初始位置（2,2）开始运动，根据仿真结果可知， 该算法能够在这种复杂环境下做出相应的路径选 择策略，并且在每一个子区域内部完成全覆盖. 本 例子中区域重复覆盖率 为 0，总覆盖面积达 到 100%，有效证明了该算法的可行性. 从图 7（a）中 可以看到虚线经过了障碍物栅格，路径转移算法 需要完成避障功能. 三个部分路径转移的实施离 不开点对点路径规划算法，本模块 BINN 算法在做 点对点路径规划时，在目标点处增加了神经元活 性值，并在三个区域转移部分分别设置不同的 来 减少路径的转折，优化算法的搜索路径. 实验结果 证明算法实现了自主避障并有效搜索到了目标 点，路径没有出现跨越和迷失现象，该算法在点对 点路径规划中具有高效性. 3.3 对比实验 为证明 BINN 算法在区域转移方面的性能，本 文选用几种经典点对点路径规划算法与 BINN 算 法做对比试验. 通常情况下，路径转移距离和路径 转移时间是衡量覆盖任务的重要指标. 路径转移 距离为机器人从上一个子区域结点到下一个子区 域起始点生成的路径距离；路径转移时间为完成 这项任务消耗的时间，通过这两种性能指标来评 价两种算法最短转移路径的总代价. 本小节选用的对比算法为 A*算法、Dijkstra 算 法和 RRT 算法. BINN 算法、A*算法、Dijkstra 算 法均是基于栅格地图，路径转移距离为所有栅格 之间的欧氏距离之和；RRT 算法基于坐标地图，路 径转移距离为所有坐标点之间的距离之和，栅格 地图与坐标地图具有对应性，因此几种算法路径 长度具有可比性. 图 8、表 3、表 4 和图 9 展示了四 5 10 15 20 25 5 10 15 20 25 Grid number Grid number 5 10 15 20 25 5 10 15 20 25 Grid number Grid number (a) (b) 5 10 15 20 25 5 10 15 20 25 Grid number Grid number 5 10 15 20 25 5 10 15 20 25 Grid number Grid number (c) (d) 图 8 实验结果对比. （a）BINN 算法；（b）A*算法；（c）Dijkstra 算法；（d）RRT 算法 Fig.8 Comparison of experimental results: (a) BINN algorithm; (b) A* algorithm; (c) Dijkstra algorithm; (d) RRT algorithm · 1226 · 工程科学学报，第 42 卷，第 9 期
周林娜等：矿区废弃地移动机器人全覆盖路径规划 1227· 表3路径转移距离对比 Table 3 Distance comparison of path transition Distance of path transition Algorithm Total distance H I-F F-C RRT algorithm 8.30 11.30 12.86 32.46 Dijkstra algorithm 7.83 9.41 11.41 28.65 A◆algorithm 7.83 9.41 11.41 28.65 BINN algorithm 7.83 9.41 10.83 28.07 表4路径转移时间对比 Table 4 Time comparison of path transition Time of path transition Algorithm Total time/s J I-F F-C RRT algorithm 4.14 4.65 6.20 14.99 Dijkstra algorithm 1.07 1.31 1.77 4.15 A*algorithm 1.07 1.33 1.76 4.16 BINN algorithm 0.80 0.89 0.95 2.64 种算法对比实验结果.图8中BNN算法路径用 搜索目标神经元，同时根据对的不同设定，缩短 “×”表示，A*算法路径用“o”表示，Dijkstra算法路 了规划路径，该算法获得最短搜索路径.根据 径用“△”表示，RRT算法路径用“”表示 图9(b)和表4，在三个区域转移部分，由于BINN 从图9(a)和表3可以得出，在J一I,I一F区域 算法对目标神经元的导向作用，算法快速搜索到 中，BNN算法生成的路径长度和A*算法、Dijkstra 目标神经元位置，BNN算法消耗的时间最少.从 算法相同，小于RRT算法的路径长度：F一C区域 上述实验结果中可以看到，在路径转移距离方面， 中BNN算法的路径长度最小，因此，总路径长度 BNN算法在J一I区域，I一F区域，F一C区域均获 BNN算法最小.本文在区域转移部分应用BNN 得最小的总路径；在路径转移时间方面，BNN算 算法时增大了目标点神经元活性，引导算法快速 法的路径转移时间代价最小.因此，不论路径转移 14 (a) (b) BINN 6 日A* ◆BNN ÷-Dijkstra 0 RRT 4 一F Subregion Subregion 图9算法性能评价结果图.(a)距离对比结果：(b)时间对比结果 Fig.9 Performance evaluation results of algorithms:(a)distance comparison result,(b)time comparison result 距离还是路径转移时间，BNN算法均最优 的全覆盖.本文将BNN算法用于区域分解中，既 4结论 能够实现机器人对子区域内部全覆盖又能完成子 区域间路径转移.仿真实验结果验证了本文所使 针对矿区废弃地等复杂环境，本文使用BCD 用的方法的可行性.在路径转移方面，本文使用三 方法结合BNN算法完成移动机器人对整个环境 种点对点路径规划算法做对比实验，实验结果证
种算法对比实验结果. 图 8 中 BINN 算法路径用 “×”表示，A*算法路径用“○”表示，Dijkstra 算法路 径用“△”表示，RRT 算法路径用“·”表示. 从图 9（a）和表 3 可以得出，在 J—I，I—F 区域 中，BINN 算法生成的路径长度和 A*算法、Dijkstra 算法相同，小于 RRT 算法的路径长度；F—C 区域 中 BINN 算法的路径长度最小，因此，总路径长度 BINN 算法最小. 本文在区域转移部分应用 BINN 算法时增大了目标点神经元活性，引导算法快速 搜索目标神经元，同时根据对u的不同设定，缩短 了规划路径 ，该算法获得最短搜索路径. 根据 图 9（b）和表 4，在三个区域转移部分，由于 BINN 算法对目标神经元的导向作用，算法快速搜索到 目标神经元位置，BINN 算法消耗的时间最少. 从 上述实验结果中可以看到，在路径转移距离方面， BINN 算法在 J—I 区域，I—F 区域，F—C 区域均获 得最小的总路径；在路径转移时间方面，BINN 算 法的路径转移时间代价最小. 因此，不论路径转移 距离还是路径转移时间，BINN 算法均最优. 4 结论 针对矿区废弃地等复杂环境，本文使用 BCD 方法结合 BINN 算法完成移动机器人对整个环境 的全覆盖. 本文将 BINN 算法用于区域分解中，既 能够实现机器人对子区域内部全覆盖又能完成子 区域间路径转移. 仿真实验结果验证了本文所使 用的方法的可行性. 在路径转移方面，本文使用三 种点对点路径规划算法做对比实验，实验结果证 表 3 路径转移距离对比 Table 3 Distance comparison of path transition Algorithm Distance of path transition Total distance J—I I—F F—C RRT algorithm 8.30 11.30 12.86 32.46 Dijkstra algorithm 7.83 9.41 11.41 28.65 A* algorithm 7.83 9.41 11.41 28.65 BINN algorithm 7.83 9.41 10.83 28.07 表 4 路径转移时间对比 Table 4 Time comparison of path transition Algorithm Time of path transition Total time/s J—I I—F F—C RRT algorithm 4.14 4.65 6.20 14.99 Dijkstra algorithm 1.07 1.31 1.77 4.15 A* algorithm 1.07 1.33 1.76 4.16 BINN algorithm 0.80 0.89 0.95 2.64 0 2 4 6 8 10 12 14 BINN (a) (b) A* Dijkstra RRT J—I I—F F—C Subregion Distance of path transition 0 1 2 3 4 5 6 7 Time of path transition/s A* BINN Dijkstra RRT J—I I—F F—C Subregion 图 9 算法性能评价结果图. （a）距离对比结果；（b）时间对比结果 Fig.9 Performance evaluation results of algorithms: (a) distance comparison result; (b) time comparison result 周林娜等： 矿区废弃地移动机器人全覆盖路径规划 · 1227 ·
·1228 工程科学学报，第42卷.第9期 明，不论是在路径转移距离方面还是在路径转移 [13]Bircher A,Kamel M,Alexis K,et al.Receding horizon path 时间方面，BNN算法均具有高效性，未来的工作 planning for 3D exploration and surface inspection.Autonom 任务是采用一种主动搜索算法完成下一子区域最 Robots,.2018,42(2):291 佳起始点的搜索，要求该搜索算法获得的最佳起 [14]Wang H J,Yu Y,Yuan Q B.Application of Dijkstra algorithm in robot path-planning Second International Conference on 始点与上一结点之间具有较短路径消耗 Mechanic Automation Control Engineering.Hohhot,2011:1067 [15]Fu B,Chen L,Zhou Y T,et al.An improved A*algorithm for the 参考文献 industrial robot path planning with high success rate and short [1]Sang L H,Fu M C,Feng Y H.Progress and prospect of research length.Rob Autonomous Syst,2018,106:26 on land reclamation planning and design in mining area.Coal Sci [16]Wei K,Ren B Y.A method on dynamic path planning for robotic Technol,2018,46(2):243 manipulator autonomous obstacle avoidance based on an improved (桑李红，付梅臣，冯洋欢.煤矿区土地复垦规划设计研究进展 RRT algorithm.Sensors,2018,18(2):571 及展望.煤炭科学技术，2018.46(2)：243) [17]Rashid R,Perumal N,Elamvazuthi I,et al.Mobile robot path [2] Xu B,Xu M,Chen L P,et al.Review on coverage path planning planning using Ant Colony Optimization//2016 2nd IEEE algorithm for intelligent machinery.Comput Meas Control,2016, International Symposium on Robotics and Manufacturing 24(10):1 Automation (ROMA).Ipoh,2016:1 (徐博，徐旻，陈立平，等.智能机械全覆盖路径规划算法综述 [18]Zhang C,Li Q,Chen P,et al.Improved ant colony optimization 计算机测量与控制，2016,24(10)：1) based on particle swarm optimization and its application.J Univ [3] Hsu P M,Lin C L,Yang M Y.On the complete coverage path Sci Technol Beijing,2013,35(7):955 planning for mobile robots.JIntell Robot Syst,2014,74(3-4):945 (张超，李擎，陈鹏，等.一种基于粒子群参数优化的改进蚊群算 [4]Mac TT,Copot C,Tran DT,et al.Heuristic approaches in robot 法及其应用.北京科技大学学报，2013,35(7)：955) path planning:a survey.Rob Auonom Syst,2016,86:13 [19]Tian Z J,Gao X H,Zhang M X.Path planning based on the [5] Wang Z L,Li H,Zhang X L.Construction waste recycling robot improved artificial potential field of coal mine dynamic target for nails and screws:computer vision technology and neural navigation.J China Coal Soc,2016,41(Suppl 2):589 network approach.Autom Construct,2019,97:220 (田子建，高学浩，张梦霞.基于改进人工势场的矿井导航装置 [6]Wang Y N,Pan Q,Chen Y J.Path planning method based on 路径规划.煤炭学报，2016,41（增刊2）：589) improved biologically inspired neural network.Control Eng [20]Chen E K,Wu M H,Zhang Y J.Path planning for coal mine Chia,2018,25(4):541 rescue robot in complex environment.Coal Technol,2018, (王耀南，潘琪，陈彦杰.改进型生物激励神经网络的路径规划 37(10):301 方法.控制工程，2018,25(4)：541) (陈尔奎，吴梅花，张英杰.复杂环境下煤矿救灾机器人路径规 [7]Zhu D Q,Cao X.Sun B.et al.Biologically inspired self- 划.煤炭技术，2018,37(10)：301) organizing map applied to task assignment and path planning of an [21]Sun J,Chen Z H,Wang P,et al.Multi-region coverage method AUV system.IEEE Trans Cognitive Dey Syst,2018,10(2):304 based on cost map and minimal tree for mobile robot.Robot,2015, [8]Zhu D Q,Yan M Z.Survey on technology of mobile robot path 37(4):435 planning.Control Des,2010,25(7):961 (孙建，陈宗海，王鹏，等.基于代价地图和最小树的移动机器人 (朱大奇，颜明重.移动机器人路径规划技术综述.控制与决策 多区域覆盖方法.机器人，2015,37(4)：435) 2010,25(7):961) [22]Hameed I A,Bochtis D,Sorensen C A.An optimized field [9]Liu G,Li X,Kang X,et al.Automatic navigation path planning coverage planning approach for navigation of agricultural robots in method for land leveling based on GNSS.Trans Chin Soc Agric fields involving obstacle areas.IntJAdy Rob Syst,2013,10(5):1 Mach,2016,47(增f刊1)：21 [23]Tang Q S.Application and research on tree structure based on (刘刚，李笑，康熙，等.基于GNSS的农田平整自动导航路径规 depth-first algorithm.Comput Technol Dev,2014,24(9):226 划方法.农业机械学报，2016,47（增刊1）：21) (唐青松.深度优先算法在创建树形结构中的应用研究.计算机 [10]Sucan I A,Moll M,Kaveraki L E.The open motion planning 技术与发展，2014,24(9)：226) library.IEEE Rob Autom Mag,2012.19(4):72 [24]Luo C M,Yang S X,Li X D,et al.Neural-dynamics-driven [11]Oksanen T,Visala A.Coverage path planning algorithms for complete area coverage navigation through cooperation of multiple agricultural field machines.J Field Rob,2009,26(8):651 mobile robots.IEEE Trans Ind Electron,2017,64(1):750 [12]Palleja T,Tresanchez M,Teixido M,et al.Modeling floor- [25]Yang S X,Meng M.An efficient neural network approach to cleaning coverage performances of some domestic mobile robots dynamic robot motion planning.Neural Nenworks,2000,13(2): in a reduced scenario.Rob Autonom Syst,2010,58(1):37 143
明，不论是在路径转移距离方面还是在路径转移 时间方面，BINN 算法均具有高效性. 未来的工作 任务是采用一种主动搜索算法完成下一子区域最 佳起始点的搜索，要求该搜索算法获得的最佳起 始点与上一结点之间具有较短路径消耗. 参 考 文 献 Sang L H, Fu M C, Feng Y H. Progress and prospect of research on land reclamation planning and design in mining area. Coal Sci Technol, 2018, 46（2）: 243 （桑李红, 付梅臣, 冯洋欢. 煤矿区土地复垦规划设计研究进展 及展望. 煤炭科学技术, 2018, 46（2）：243） [1] Xu B, Xu M, Chen L P, et al. Review on coverage path planning algorithm for intelligent machinery. Comput Meas Control, 2016, 24（10）: 1 （徐博, 徐旻, 陈立平, 等. 智能机械全覆盖路径规划算法综述. 计算机测量与控制, 2016, 24（10）：1） [2] Hsu P M, Lin C L, Yang M Y. On the complete coverage path planning for mobile robots. J Intell Robot Syst, 2014, 74（3-4）: 945 [3] Mac T T, Copot C, Tran D T, et al. Heuristic approaches in robot path planning: a survey. Rob Autonom Syst, 2016, 86: 13 [4] Wang Z L, Li H, Zhang X L. Construction waste recycling robot for nails and screws: computer vision technology and neural network approach. Autom Construct, 2019, 97: 220 [5] Wang Y N, Pan Q, Chen Y J. Path planning method based on improved biologically inspired neural network. Control Eng China, 2018, 25（4）: 541 （王耀南, 潘琪, 陈彦杰. 改进型生物激励神经网络的路径规划 方法. 控制工程, 2018, 25（4）：541） [6] Zhu D Q, Cao X, Sun B, et al. Biologically inspired selforganizing map applied to task assignment and path planning of an AUV system. IEEE Trans Cognitive Dev Syst, 2018, 10（2）: 304 [7] Zhu D Q, Yan M Z. Survey on technology of mobile robot path planning. Control Des, 2010, 25（7）: 961 （朱大奇, 颜明重. 移动机器人路径规划技术综述. 控制与决策, 2010, 25（7）：961） [8] Liu G, Li X, Kang X, et al. Automatic navigation path planning method for land leveling based on GNSS. Trans Chin Soc Agric Mach, 2016, 47（增刊1）: 21 （刘刚, 李笑, 康熙, 等. 基于GNSS的农田平整自动导航路径规 划方法. 农业机械学报, 2016, 47（增刊1）：21） [9] Sucan I A, Moll M, Kaveraki L E. The open motion planning library. IEEE Rob Autom Mag, 2012, 19（4）: 72 [10] Oksanen T, Visala A. Coverage path planning algorithms for agricultural field machines. J Field Rob, 2009, 26（8）: 651 [11] Palleja T, Tresanchez M, Teixido M, et al. Modeling floorcleaning coverage performances of some domestic mobile robots in a reduced scenario. Rob Autonom Syst, 2010, 58（1）: 37 [12] Bircher A, Kamel M, Alexis K, et al. Receding horizon path planning for 3D exploration and surface inspection. Autonom Robots, 2018, 42（2）: 291 [13] Wang H J, Yu Y, Yuan Q B. Application of Dijkstra algorithm in robot path-planning // Second International Conference on Mechanic Automation & Control Engineering. Hohhot, 2011: 1067 [14] Fu B, Chen L, Zhou Y T, et al. An improved A* algorithm for the industrial robot path planning with high success rate and short length. Rob Autonomous Syst, 2018, 106: 26 [15] Wei K, Ren B Y. A method on dynamic path planning for robotic manipulator autonomous obstacle avoidance based on an improved RRT algorithm. Sensors, 2018, 18（2）: 571 [16] Rashid R, Perumal N, Elamvazuthi I, et al. Mobile robot path planning using Ant Colony Optimization// 2016 2nd IEEE International Symposium on Robotics and Manufacturing Automation (ROMA). Ipoh, 2016: 1 [17] Zhang C, Li Q, Chen P, et al. Improved ant colony optimization based on particle swarm optimization and its application. J Univ Sci Technol Beijing, 2013, 35（7）: 955 （张超, 李擎, 陈鹏, 等. 一种基于粒子群参数优化的改进蚁群算 法及其应用. 北京科技大学学报, 2013, 35（7）：955） [18] Tian Z J, Gao X H, Zhang M X. Path planning based on the improved artificial potential field of coal mine dynamic target navigation. J China Coal Soc, 2016, 41(Suppl 2): 589 （田子建, 高学浩, 张梦霞. 基于改进人工势场的矿井导航装置 路径规划. 煤炭学报, 2016, 41(增刊2): 589） [19] Chen E K, Wu M H, Zhang Y J. Path planning for coal mine rescue robot in complex environment. Coal Technol, 2018, 37（10）: 301 （陈尔奎, 吴梅花, 张英杰. 复杂环境下煤矿救灾机器人路径规 划. 煤炭技术, 2018, 37（10）：301） [20] Sun J, Chen Z H, Wang P, et al. Multi-region coverage method based on cost map and minimal tree for mobile robot. Robot, 2015, 37（4）: 435 （孙建, 陈宗海, 王鹏, 等. 基于代价地图和最小树的移动机器人 多区域覆盖方法. 机器人, 2015, 37（4）：435） [21] Hameed I A, Bochtis D, Sørensen C A. An optimized field coverage planning approach for navigation of agricultural robots in fields involving obstacle areas. Int J Adv Rob Syst, 2013, 10（5）: 1 [22] Tang Q S. Application and research on tree structure based on depth-first algorithm. Comput Technol Dev, 2014, 24（9）: 226 （唐青松. 深度优先算法在创建树形结构中的应用研究. 计算机 技术与发展, 2014, 24（9）：226） [23] Luo C M, Yang S X, Li X D, et al. Neural-dynamics-driven complete area coverage navigation through cooperation of multiple mobile robots. IEEE Trans Ind Electron, 2017, 64（1）: 750 [24] Yang S X, Meng M. An efficient neural network approach to dynamic robot motion planning. Neural Networks, 2000, 13（2）: 143 [25] · 1228 · 工程科学学报，第 42 卷，第 9 期
