工程科学学报.第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