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