《工程科学学报》：矿区废弃地移动机器人全覆盖路径规划

工程科学学报 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] 在机械臂上采用快速搜索随机树 (Rapidly￾exploring 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 ·