基于蚁群系统算法的地图全遍历路径规划

来源:用户上传      作者:

　　摘 要：清扫机器人进行全遍历路径规划要求机器人能够遍历环境中所有的可清扫区域，因此提出一种基于蚁群系统算法的地图全遍历路径规划算法。使用搭载单线激光雷达传感器的机器人进行环境建图，对每个栅格赋予不同概率值反映环境状态信息;采用 Boustrophedon细胞分解方法将栅格地图划分为若干相邻子模块，并让机器人从起始点开始遍历所有子模块后再回到起始位姿。为了提高各子模块之间的衔接效率，引入蚁群系统算法实现机器人在到达每个子模块的起始位姿后，对每个子模块进行高效的区域全覆盖。实验结果表明，该算法相比传统生成树算法，清扫覆盖率达到了96%，清扫效率提高了两倍。
　　关键词：全遍历路径规划;清扫机器人;栅格地图;蚁群系统算法;Boustrophedon细胞分解
　　DOI：10. 11907/rjdk. 192275 开放科学（资源服务）标识码（OSID）：
　　中图分类号：TP301 文献标识码：A 文章编号：1672-7800（2020）007-0041-05
　　Map Full Traversal Path Planning Based on Ant Colony System Algorithm
　　Huang Jia-hao， HAO Run-ke， LV Gang-zhen
　　（School of Mechanical Engineering， University of Shanghai for Science and Technology， Shanghai 200093， China）
　　Abstract： The full traversal path planning of the cleaning robot requires the robot to traverse all the cleanable areas in the environment. This paper proposes an algorithm for map full traversal path planning based on ant colony system algorithm. The robot is equipped with a single-line lidar sensor for environmental mapping. Each grid gives different probability values to reflect the state information of the environment. The Boustrophedon celluar decomposition method is used to divide the grid map into several adjacent sub-modules. And the robot traverses all submodules from the starting point and then return to their starting pose. In order to improve the connection efficiency between the various sub-modules， an ant colony system algorithm is introduced to realize that after the robot reaches the starting position of each sub-module， it covers the entire area of each sub-module efficiently. The experimental results show that compared with the traditional spanning tree algorithm， the proposed algorithm has a cleaning coverage rate of 96% and the cleaning efficiency is doubled.
　　Key Words： full traversal path planning; cleaning robot; grid map; ant colony system algorithm; Boustrophedon cell decomposition
　　0 引言
　　地圖全遍历路径规划算法旨在解决如何覆盖工作环境中的所有区域并避开障碍物。该算法被广泛应用于各种机器人平台中，例如清洁机器人[1-2]、排雷机器人[3]、割草机器人[4]等。
　　根据是否有先验的环境信息存储在系统中，全遍历路径规划算法可分为在线方法[5-6]和离线方法[7]两种。在线方法致力于未知环境实时规划与覆盖，但由于传感器自身精度的局限性，存在无法覆盖环境中所有区域的问题。离线方法虽具备更高的覆盖率，并能生成更优路径，但在环境发生变化时极易出现算法失效的情况。Ribeiro 等[8]提出的生成树算法和Hu等[9]提出的螺旋填充路径算法虽然能基本实现地图全遍历路径规划，但因生成的路径重复率太高，导致清扫效率较低;Karthikeyan等[10]提出的基于神经网络算法的路径规划和Yakoubi等[11]提出的基于遗传算法的路径规划虽然能生成优于前者、重复率较低的全遍历路径，但神经网络和遗传算法主要用来解决最短路径优化问题，最短路径优化中的目标函数通常是连续的，并且最终会收敛到特定的最优值，且全遍历路径规划中的最大覆盖范围会对目标函数进行严格约束，若面对多变的复杂环境，机器人也无法保持正常工作状态。
　　空间分解技术[13]是全遍历路径规划中的关键一环，选择适当的空间分解技术能极大地简化环境模型并降低算法整体复杂度。基于栅格的分解方法[14]将环境空间划分为较小单位元素的并集，其中所有单元的大小与形状相同，且不存在任何重叠区域。同时，每个栅格大小决定了地图分辨率，高分辨率的地图可使算法对工作环境进行更好的估计，达到更高的覆盖率。 　　故本文通过引入蚁群系统算法[15-16]，使用搭载单线激光雷达传感器的清扫机器人构建环境的高分辨率地图，并对地图进行Boustrophedon细胞分解[17]，规划出全覆盖的全局路径。该算法相比传统算法具有更高的覆盖率与更低的重复率，弥补了传统算法在动态环境中容易失效的缺陷。
　　1 基于蚁群系统算法的全遍历路径规划算法
　　1.1 占用栅格地图构建
　　栅格地图由Moravec等[18]提出，该方法简单、直观且数据容易表示，所以被广泛应用于机器人避障导航、位姿估计及路径规划等方面，特别适合于处理激光雷达采集的数据。占用栅格地图构建算法可根据给定数据计算整个地图的后验概率。
　　式中，m为地图，[z1：t]为指导时刻t的所有测量值，[x1：t]为包含所有机器人位姿的路径。
　　这里采用对数表达形式，以避免0和1附近数值的不稳定性，即：
　　则式（1）转化为：
　　因此，将求解整个地图转换成求解每个栅格的概率问题，并将每个单元被占有的概率记为置信度。
　　当机器人位姿发生改变时，再将当前观测的局部地图融入到已有的全局地图中。图1为单线激光雷达构建的实际环境1的栅格地图，图2为实际环境2的栅格地图。
　　1.2 环境栅格地图噪声处理
　　如图1、图2所示，使用单线激光雷达传感器构建的占用栅格地图不可避免地会存在许多噪声点和发散点，并且地图中有许多穿透玻璃门扫到的室外区域，这些区域都不在室内清扫机器人的清扫范围内，所以需要去除栅格地图中的噪声。
　　本文使用OpenCV中的膨胀与腐蚀算法[19]对栅格地图进行去噪，并确定清扫机器人作业范围。膨胀和腐蚀是图像形态学中的重要操作，原理为对图像进行卷积操作，其需要有一个kernel卷积核，常见的是3*3的矩阵。但与卷积不同的是，如果矩阵中的像素点有任意一个点的值是前景色，則设置中心像素点为前景色。在算法处理前，先将地图变成二值图像，用数值1表示障碍物，数值0表示空闲区域。
　　采用腐蚀算法，用3*3的kernel扫描图像每一个像素，并用kernel与其覆盖的二值图像作“与”操作，如果都为1，最终图像的该像素为1，否则为0;采用膨胀算法，用3*3的kernel与其覆盖的二值图像作“与”操作，如果都为0，最终图像的该像素为0，否则为1。
　　图1中的原始栅格地图经过OpenCV中的算法处理后得到如图3所示地图。
　　1.3 Boustrophedon细胞分解
　　Boustrophedon细胞分解是一种栅格地图分解方法，算法原理为：切片扫过有界自由空间，从“负无穷大”开始，在切片最初遇到自由空间时生成第一个细胞;然后切片继续扫过自由空间。在IN事件中，切片连通性增加，当前细胞关闭，两个新细胞被打开。相反，在切片连通性降低的OUT事件中，两个当前细胞关闭，一个新细胞被打开。当切片离开有界自由空间时，该过程终止。在计算分解时，还要确定邻接图。同样，每个细胞是图中的节点，并且是边连接的相邻节点。用类似深度优先的图搜索算法输出表示通过邻接图的穷举遍历路径列表，遍历路径列表构成了对邻接图的详尽遍历;最后，使用上述路径列表计算机器人的实际路径。当机器人进入“未清理”单元时，进行Boustrophedon运动，然后计算路径列表中的下一个单元路径。当机器人进入“已清理”单元时，只是计算通过当前单元格到路径列表中下一个单元的路径。重复这两个动作，直到到达路径列表末尾，即直到每个单元都已被“清理”。IN事件和OUT事件分别如图4、图5所示。
　　在对图3完成Boustrophedon细胞分解后，得到如图6所示分块地图。对实验环境2也进行Boustrophedon细胞分解，得到如图7所示分块地图。
　　1.4 蚁群系统算法
　　将环境栅格地图分解为多个子区域后，需要给清扫机器人规划出一条从起点开始访问所有子区域，最后又回到起点的最优路径，也即组合优化问题中的旅行商问题。该问题是在一个带权完全无向图中寻找一个权值最小的Hamilton回路[20]。由于该问题的可行解是所有顶点全排列，随着顶点数的增加，会产生组合爆炸，因此是一个NP完全问题。图8是实验环境1的区域结构图，根据该图直接实现全遍历规划算法是不现实的。
　　蚁群系统算法（Ant Colony System，ACS）是一种基于群体、用于求解复杂优化问题的元启发式算法。与真实蚂蚁通过外激素的留存、跟随行为进行间接通信类似，ACS中一群简单的人工蚂蚁之间通过媒介质进行间接通信，并利用该信息以及与问题相关的启发式信息逐步构造问题的解，实现对问题的优化。算法流程如图9所示。
　　根据图8得到一个有向图G的三元组为（V，E，f），其中V是一个非空集合，其元素称为有向图节点;E是一个集合，其元素称为有向图的边;f是从E到V×V的一个映射。E中元素总是与V中的序偶有对应关系，可用V中的序偶代替E中元素，则G简记为（V，E）。
　　设[C=c1，c2，？cn]为n个城市的集合，[L=lij|ci，cj∈C]是集合C中元素两两连接的集合，[diji，j=1，2，？，n]是[lij]的Euclidean距离，如式（6）所示。
　　G=（C，L）构成一个有向图，从G中寻找长度最短的Hamilton圈，即全遍历路径。
　　在蚁群系统算法中，蚂蚁采用伪随机比例规则策略。根据该策略，一只位于子区域1的蚂蚁k通过公式（5）选择下一个要访问的区域j。
　　q为[0，1]区间均匀分布的随机数，[q0]为一个参数，[0q01]。蚂蚁k以[q<q0]的概率确定区域的转移，以[qq0]的概率探索可转移的城市。公式（8）为蚂蚁k从当前区域选择下一个要访问区域j的概率，J为根据式（8）给出的概率分布产生的一个随机变量。 　　式中，[τij]為连接（i，j）上的信息素强度;[ηij]为连接（i，j）上的能见度，代表一个预先给定的启发式信息;[α]为蚂蚁在运动过程中积累的信息素在蚂蚁路径选择中的相对重要性参数;[β]为蚂蚁运动过程中的启发式信息在蚂蚁路径选择中的相对重要性参数;[Nki]为位于区域i的蚂蚁k可以直接到达的相邻区域集合。
　　同时，蚁群系统算法的信息素更新策略也不同。每次循环结束后，只有至今最优的路径才能进行全局信息素更新，更新公式为：
　　局部信息素更新公式为：
　　[ξ0<ξ<1]是一个参数，[τ0]表示信息素初始浓度。应用局部信息素更新规则降低路径（i，j）的信息素浓度，则蚂蚁经过该路径的可能性降低，从而增加了探索未走过路径的概率，使算法不易陷入停滞状态。
　　2 实验与分析
　　基于以上分析，为验证本文提出的基于蚁群系统算法的全遍历路径规划，在20m×15m的实验环境1与10m×10m的实验环境2中分别对算法进行测试。蚁群系统算法参数设置如下：迭代次数N=200，蚂蚁数量M=40，启发因子[α]=1，期望启发因子[β]=7。在实验环境1中规划的遍历路径如图10所示，能够覆盖地图所有区域，覆盖率达到96%。在实验环境2中规划的遍历路径如图11所示，同样能够实现地图全覆盖，且由于环境2中不存在障碍物，所以清扫车不需要避障，实际测量后发现清扫车覆盖率达到98%。该算法可以很好地适应不同环境，而且在不同环境中都能生成覆盖率较高的全局路径。
　　为了进一步验证本文算法的有效性，在环境1和环境2中进行生成树算法与本文算法的对比实验。在两个环境中分别进行了5次重复实验，得到的平均路径长度、作业时间和清扫覆盖率如表1所示。在相同环境中，本文算法的作业时间更短、覆盖率更高，并能更高效地进行全遍历。
　　3 结语
　　针对清扫机器人在任意环境中的全遍历路径规划问题，提出一种基于蚁群系统算法的地图全遍历路径规划算法，并验证了该算法的高覆盖率与适应性。该算法在实际测试中取得了良好效果，对不同环境都能进行全遍历。对比实验结果表明，相比传统生成树算法，该算法在实际环境中能以更短时间、更高覆盖率完成地图全遍历路径规划。通过对机器人全遍历路径规划问题的研究，解决了传统路径规划算法存在的覆盖率低及重复率高的问题，对机器人控制与导航策略有了更深入的认识。在未来的研究中，将针对单个机器人清扫较大范围环境耗时过长的问题，进一步研究如何合理地划分环境地图以规划多个机器人清扫路径，从而减少清扫时间。
　　参考文献：
　　[1] LE A，PRABAKARAN V，SIVANANTHAM V， et al. Modified a-star algorithm for efficient coverage path planning in tetris inspired self-reconfigurable robot with integrated laser sensor[J]. Sensors， 2018， 18（8）：2585.
　　[2] 李楷，陈永府，金志勇. 基于回溯法的全覆盖路径规划算法[J]. 计算机工程与科学，2019，41（7）：1227-1235.
　　[3] SILLERICO J V. Control scheme for distributed computing in robot networks destined to humanitarian demining[C]. 2018 IEEE XXV International Conference on Electronics， Electrical Engineering and Computing （INTERCON）， Lima， 2018.
　　[4] PATRA B， NANDY S. Lawn mower trajectory tracking by wheeled mobile robot： its consequences[C]. Kolkata：2017 1st International Conference on Electronics， Materials Engineering and Nano-Technology，2017.
　　[5] ZHAO M Y，WANG H， CAO F. Online path planning algorithms for unmanned air vehicle[C]. 2017 IEEE International Conference on Unmanned Systems （ICUS），2017：116-119.
　　[6] CHOI Y H，LEE T K，BAEK S H. Online complete coverage path planning for mobile robots based on linked spiral paths using constrained inverse distance transform[C]. IEEE/RSJ International Conference on Intelligent Robots and Systems，2009.
　　[7] PITSCH M， PRYOR M. Temporally static environment coverage with offline planning techniques[C]. Austin： 2017 IEEE Workshop on Advanced Robotics and its Social Impacts，2017.
　　[8] KO？T'áLOVá A， RIBEIRO T T，CONCEI？？O A G. Communication faults in robot formation control： a reconfigurable spanning tree approach[C]. 2017 International Conference on Computational Science and Computational Intelligence （CSCI），  2017：1842-1843. 　　[9] HU Z， LIU Z， FU J. Spiral tool-path generation with constant scallop height for sheet metal CNC incremental forming [J]. International Journal of Advanced Manufacturing Technology， 2011， 54（9-12）：911-919.
　　[10] KARTHIKEYAN U G，EVAN K，et al. Map generation and path planning for autonomous mobile robot in static environments using GA[C]. Computer Science and Information Technology （CSIT） 2018 8th International Conference on， 2018：91-96.
　　[11] YAKOUBI M A，LASKRI M T. The path planning of cleaner robot for coverage region using genetic algorithms [J]. Journal of Innovation in Digital Ecosystems， 2016（1）： 37-43.
　　[12] LI W Z， LI J，LI S J. An improved Dijkstra's algorithm for shortest path planning on 2D grid maps[C]. 2019 IEEE 9th International Conference on Electronics Information and Emergency Communication （ICEIEC），2019：438-441.
　　[13] TRABELSI A，MEERAN S. Recognition and interpretation of interacting and non-interacting features using spatial decomposition and Hamiltonian path search [J]. International Journal of Production Research，2007，34（10）：2701-2725.
　　[14] 李伟莉，赵东辉. 基于栅格法与神经元的机器人全区域覆盖算法[J]. 机械设计与制造，2017（8）： 232-234.
　　[15] 张于贤，丁修坤，薛殿春. 求解旅行商问题的改进蚁群算法研究[J]. 计算机工程与科学，2017（8）：1576-1580.
　　[16] JOSHI S，KAUR S. Comparative analysis of two different ant colony algorithm for model of TSP[C]. 2015 International Conference on Advances in Computer Engineering and Applications，2015： 669-671.
　　[17] CHOSET H. Coverage of known spaces： the boustrophedon cellular decomposition[J].  Autonomous Robots， 2000， 9（3）：247-253.
　　[18] LEE T K， BAEK S H. CHOI Y H， et al. Smooth coverage path planning and control of mobile robots based on high-resolution grid map representation [J].  Robotics and Autonomous Systems， 2011，5910：361-362.
　　[19] NOBLE F K. Comparison of OpenCV's feature detectors and feature matchers[C] Nanjing：2016 23rd International Conference on Mechatronics and Machine Vision in Practice，2016.
　　[20] 許凯波. 蚁群算法的改进及其在若干优化问题中的应用[D]. 无锡：江南大学，2018.
　　（责任编辑：黄 健）
转载注明来源:https://www.xzbu.com/8/view-15285246.htm