周林娜等：矿区废弃地移动机器人全覆盖路径规划 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 ·