·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 期