移动机器人混合式全遍历覆盖路径规划算法.pdf

第 卷 第 期 年 月山 东 理 工 大 学 学 报（自 然 科 学 版）Journal of Shandong University of Technology（Natural Science Edition）Vol No Sep 收稿日期：基金项目：山东省高等学校科技计划项目（JLN）作者简介：陈鹏，男，herochenpeng com；通信作者：李彩虹，女，lich sdut edu cn文章编号：（）移动机器人混合式全遍历覆盖路径规划算法陈 鹏，李彩虹（山东理工大学 计算机科学与技术学院，山东 淄博）摘 要：针对移动机器人在未知环境下的全遍历覆盖任务，将滚动规划与已知环境下的搜索策略相结合，设计了一种混合式的全遍历覆盖路径规划算法 对声纳传感器探测到的环境信息进行滚动规划，把未知区域转化为已知区域 在已知区域，采用有限状态机方式来组织全遍历覆盖路径规划算法，状态之间的转换通过二叉树搜索策略、目标栅格选取策略和两点法搜索策略来实现，并对算法进行仿真 结果表明，移动机器人能全遍历覆盖整个工作区域，重复率低，能有效提高工作效率 关键词：移动机器人；全遍历覆盖路径规划；滚动规划；有限状态机中图分类号：TP文献标志码：AA hybrid algorithm of complete coverage path planning for mobile robotCHEN Peng，LI Caihong（School of Computer Science and Technology，Shandong University of Technology，Zibo ，China）Abstract：This paper presents a hybrid design algorithm of complete coverage path planning formobile robot under unknown environment based on the rolling planning and known environmentsearch strategy The unknown environment has been converted to the known area using the environmental information detected by sonar sensors The algorithm of complete coverage path planning is organized by finite state machine（FSM）approach under the known environment Thestate switch has been realized by the binary search strategy，target grid selection strategy andtwopoint search strategy At last the algorithm has been tested under simulated environment Simulation results show that mobile robot can cover the entire work area with low repetition rateand high work efficiency Key words：mobile robot；complete coverage path planning；rolling planning；finite state machine（FSM）全遍历覆盖路径规划是指在满足某种性能评价指标最优或准优的前提下，寻找一条从起始点开始，且经过工作区域内所有可达点的路径规划 全遍历覆盖路径规划是一类特殊的路径规划，在许多领域都有着广阔的应用前景，特别是很多家用场合，都要求移动机器人具备全区域覆盖的能力 按照对环境知识的了解，全遍历覆盖路径规划可分为环境已知和环境未知的路径规划 已知环境下的路径规划，多采用单元分解法和模板模型法 单元分解法是将环境分解为梯形单元，机器人在梯形单元中做往返运动，并通过邻接图来表示从一个单元到另一个单元的转移 缺点是单元分解过多致使重复率较高 模板模型法是根据覆盖区域获取的环境信息，与各个模板进行匹配来完成遍历 缺点是对环境缺乏整体规划，要求事先定义环境模型和模板记忆，对变化的环境很难处理 对于环境未知情形下的路径规划，郝宗波等提出了基于传感器和栅格地图的路径规划方法，适合简单环境 Hsu等采用离线规划和在线避障方式来完成全遍历，实现过程较为复杂 邱雪娜等提出了基于生物激励与滚动启发式规则的路径规划，适合简单环境，在复杂环境下出现了较多转弯和重复 郭小勤提出了可动态调节启发式规则的滚动路径规划算法，有效减少转弯次数，并解决了 U 型障碍物区域的连续遍历问题 禹建丽等在犁田式路径规划的基础上，运用回溯法来解决遍历过程中的盲区问题 环境已知的路径规划方法不适用于环境未知的情形，而未知环境下的路径规划方法存在着重复率较高、系统开销大等缺点 为提高工作效率，采用混合式的全遍历覆盖路径规划算法 利用滚动规划把未知区域转化为已知区域 于是，未知环境下的路径规划转化为在已知区域内的路径规划，从而有效地提高工作效率 1 实时环境信息在未知环境下，移动机器人利用声纳传感器探测环境信息，如障碍物位置等 在研究中所使用的移动机器人是利曼科技有限公司生产的先锋机器人Pioneer，先锋机器人 Pioneer 装配有两个声纳阵，前方、后方各有一个，每个声纳阵由 个声纳环组成，用于物体检测、距离检测和自动避障等 其声纳环分布如图 所示 图 1 声纳环结构移动机器人装载的声纳传感器，可探测机器人位置 范围内的障碍物信息 此外，利用定位系统感知任意时刻的机器人位置 Probot、目标栅格位置Pgoal（xg，yg）和障碍物位置 Pobstacle（i）（i ，n）等信息 机器人的视野域 Ssense定义为以机器人位置Probot为中心，以 rsense为半径的圆内 假定移动机器人的行进速度恒定，运动步长为，rsense（rsense为视野域半径）在路径规划中，须将视野域 Ssense建模为已知区域 具体来说，就是以机器人的步长作为栅格长度对已知区域进行栅格化，为各个栅格赋予障碍属性 Flag（x，y）、覆盖属性 Visited（x，y）、关联属性 Related（x，y）以及可选属性 Enabled（x，y）等，并假定用栅格的中心点坐标（x，y）来标识各个栅格 下面对各个属性做详细定义）障碍属性 Flag（x，y）Flag（x，y），栅格（x，y）为自由栅格，栅格（x，y）为障碍栅格（）覆盖属性 Visited（x，y）Visited（x，y），栅格（x，y）未被遍历过，栅格（x，y）仅被遍历过一次 ，栅格（x，y）被重复遍历的次数（）关联属性 Related（x，y）Related（x，y）表示与栅格（x，y）相邻的自由栅格的个数）可选属性 Enabled（x，y）Enabled（x，y），栅格（x，y）尚未被传感器探 测到，不可遍历，栅格（x，y）是视野总域 Ssensor内 的自由栅格，可遍历（）此外，还约定在栅格地图中，用机器人位置Probot所在的栅格来标识机器人，用障碍物位置Pobstacle（i）（i ，n）对应的栅格来标识障碍物 如图 所示 图 2 视野域示意图视野总域 Ssensor定义为机器人在遍历过程中，探测到的区域总和 机器人在路径规划时，可依据具体情形，选择遍历视野总域 Ssensor内的任意自由栅格 第 期 陈鹏，等：移动机器人混合式全遍历覆盖路径规划算法机器人每行进一步，须实时探测、记录视野域 Ssense内的环境信息，并将新探测到的区域归入视野总域Ssensor内 2 全遍历覆盖路径规划算法机器人在初始遍历时，执行二叉树搜索策略，直至相邻栅格被全部遍历 此时，由于没有达到全遍历覆盖的要求，随即执行目标栅格选取策略 待目标栅格确定后，执行两点法搜索策略 机器人逐步移动至目标栅格位置，并重新执行二叉树搜索策略，此后重复这个过程 在机器人移动过程中，一旦达到全遍历覆盖要求，路径规划立即终止 整个过程，就形成了有限状态机（Finite State Machine，FSM）的设计思路 下面就 FSM 实现、策略设计、评价指标做具体阐述 2 1 全遍历覆盖路径规划的 FSM 实现移动机器人的全遍历覆盖路径规划可通过FSM 来实现，图 是规划算法的五状态 FSM 实现图 FSM 包括五种状态，还需要设计三种策略进行状态之间的转换，分别是二叉树搜索策略、目标栅格选取策略和两点法搜索策略 当机器人周围的相邻栅格中，不存在还未被遍历的自由栅格时，机器人须在视野总域 Ssensor内，选取离当前机器人位置最近的、还未被遍历的自由栅格，作为下一遍历区域的起始栅格，我们称该起始栅格为目标栅格 五种状态、三种策略作如下定义 S：初始状态S：在机器人周围的相邻栅格中，还存在未被遍历的自由栅格 S：在机器人周围的相邻栅格中，不存在还未被遍历的自由栅格 S：目标栅格已确定时 S：结束状态F：二叉树搜索策略F：目标栅格选取策略F：两点法搜索策略移动机器人的全遍历覆盖过程何时结束，需依据具体环境和实际工作要求来决定 这里为了仿真实验的需要，假定遍历覆盖率达到 ，全遍历覆盖过程结束 全遍历覆盖路径规划的 FSM 实现如图 所示 2 2 全遍历覆盖路径规划的策略设计图 3 全遍历覆盖路径规划的 FSM 实现 二叉树搜索策略 F机器人处于 S时，执行 F 该状态的目标是搜索与机器人相邻的自由栅格，找出其中关联栅格数最大的栅格，并遍历该栅格 值得指出的是，机器人每前进一步，须实时更新环境信息，并检测在机器人的相邻栅格中是否还存在未被访问的自由栅格 若存在，则重复 F 若不存在，机器人随即跳转至 S为满足二叉树搜索策略的需要，为所有栅格赋予四种属性：障碍属性 Flag（x，y）、遍历属性 Visited（x，y）、关联属性 Related（x，y）、可选属性 Enabled（x，y）这样，二叉树搜索策略选取栅格须符合：障碍属性值 Flag（x，y）为 、遍历属性值 Visited（x，y）为 、关联属性值 Related（x，y）最大、可选属性值 Enabled（x，y）为 二叉树搜索策略，涉及到了关联栅格数的计算问题 根据待研究栅格在栅格区域的位置不同，栅格区域可划分为三种模型：四格型、六格型和九格型 通过转化，任意栅格区域均符合三种模型，如图 所示 为此，本文仅对三种模型进行研究（a）四格型（b）六格型（c）九格型 图 4 栅格区域模型示意图）若采用数组结构存储各栅格的关联栅格信息，假定数组名为 A 以栅格 i为例，则有：（）当栅格 i为自由栅格时a）四格型 Ai Related A Flag A Flag山 东 理 工 大 学 学 报（自 然 科 学 版）年 A Flag（）b）六格型 Ai Related A Flag A Flag A Flag A Flag A Flag（）c）九格型 Ai Related A Flag A Flag A Flag A Flag A Flag A Flag A Flag A Flag（）此处，若栅格 i的相邻栅格中有障碍物栅格，则障碍物栅格的障碍属性值 Flag 为 ，因此，栅格 i的关联属性值不受影响，Ai Related 能够真实反映栅格 i 关联栅格的实际个数（）当栅格 i为障碍栅格时 Ai Related（）若栅格 i 为机器人栅格，求所有相邻栅格的最大关联栅格数，则有：a）四格型 Ai maxrelated max（A Related，A Related，A Related）（）b）六格型 Ai maxrelated max（A Related，A Related，A Related，A Related，A Related）（）c）九格型 Ai maxrelated max（A Related，A Related，A Related，A Related，A Related，A Related，A Related，A Related）（）通过比较，得到栅格 i 的最大关联栅格数 Ai maxrelated，记录最大关联栅格数对应的栅格编号 j 紧接着，移动机器人前进至栅格 j，并实时更新环境信息 目标栅格选取策略 F机器人处于 S时，为使机器人离开已遍历完区域，到未遍历区域继续遍历，需选取一个目标栅格，即在视野总域 Ssensor内，选取离机器人栅格最近的可选栅格，并且要求该栅格还未被遍历过 待目标栅格确定后，机器人随即跳转至 S假设任意栅格与机器人位置 Probot（xr，yr）之间的距离用 Distance 表示，则目标栅格须符合：障碍属性值 Flag（x，y）为 、遍历属性值 Visited（x，y）为 、可选属性值 Enabled（x，y）为 、Distance 值最小 若用栅格的中心点坐标来标识栅格位置，则待选栅格 Pi（xi，yi）（i ，m，m 为符合目标栅格选取条件的栅格总数）与机器人位置 Probot（xr，yr）之间的距离 Distance（i）可表示为Distance（i）（xi xr）（yi yr）（i ，m）（）求 Distance（i）的最小值：Distance min（Distance（i）i ，m（）通过比较，得到待选栅格与机器人位置之间的距离最小值 Distance，并记录该最小值对应的栅格编号 k、栅格中心点坐标 Pkxk，yk）两点法搜索策略 F目标栅格确定后，机器人立即从当前位置，移动到目标栅格位置 在向目标栅格移动过程中，若已达到全遍历覆盖要求，则终止整个遍历过程 若到达目标栅格后，还未达到全遍历覆盖要求，机器人随即跳转至 S两点法搜索策略简述为移动机器人向目标栅格直线移动时，若遇到障碍物，就改变方向、移动到没有障碍物的位置，并再次确定目标栅格的方向、感知障碍物信息 如此反复，直至到达目标栅格 两点法搜索策略示意图如图 所示 由图 可知，A 为起始点，B 为目标栅格，起始点 A 与目标栅格 B 之间的线段 AB 上有障碍物 此时，首先向上偏转角度，得到的线段 AB上仍有障碍物，再以线段 AB 为基准向下偏转角度，得到的第 期 陈鹏，等：移动机器人混合式全遍历覆盖路径规划算法图 5 两点法搜索过程示意图线段 AB上也有障碍物，再从线段 AB开始向上偏转角度 如此反复，当偏转到线段 ABi时，ABi上没有障碍物，得到一点 C，以此类推得到另一点 D，直至到达目标栅格 B，整个搜索过程停止 2 3 评价指标遍历结束后，须引入“评价指标”对遍历结果进行评价 本文采用遍历覆盖率和遍历重叠率作为评价指标 假设 S 表示整个工作空间，S表示可达区域的面积，Shc表示已遍历的面积，Scc表示重复遍历的面积）遍历覆盖率：遍历完成后，已遍历面积与可达区域面积的百分比 Jhc（ShcS）（）遍历重叠率：所有重复遍历面积之和与可达区域面积的百分比 Jcc（SccS）（）为了尽可能地减少遍历盲区，不可避免地就会产生一定程度的重叠 显然，重叠率越小越好，但受系统误差、控制精度以及环境等诸多因素的影响，重叠区域不可能太小 但若机器人的性能较高，则遍历重叠率可控制在较小的范围内，遍历效率大幅提高，遍历效果趋于理想 3 仿真实验利用以上设计的全遍历覆盖路径规划算法，对移动机器人在障碍物稀疏程度不同的环境下进行仿真 程序运行前，设定覆盖率达到 时，遍历结束 仿真结果如图 所示 仿真结果表明，移动机器人在无障碍环境、障碍稀疏环境、障碍密集环境下，都能有效地躲避障碍物，高效地完成全遍历覆盖任务，遍历重复率也被控制在可接受的范围内（a）无障碍环境（b）障碍稀疏环境（c）障碍密集环境图 6 遍历效果图山 东 理 工 大 学 学 报（自 然 科 学 版）年 4 结束语本文针对移动机器人在未知环境下的全遍历覆盖任务，提出了滚动规划与搜索策略相结合的一种混合式全遍历覆盖路径规划算法，并进行仿真实验 结果表明，算法具有以下特点：能在无障碍环境、障碍稀疏环境、障碍密集环境下，完成全遍历覆盖路径规划任务；能覆盖工作区域的几乎全部区域，遍历覆盖率高；移动机器人重复遍历的栅格较少，重复率较低 从整体来看，遍历覆盖率较高，遍历重复率较低，因此遍历效率较高 移动机器人根据全遍历覆盖路径规划算法，能够高效地完成全遍历覆盖任务，但也存在一些不足之处，如尚不能保证遍历路径长度绝对最短等，这些问题将是今后研究的课题 参考文献：邱燕，仪垂杰 小麦精播机器人路径规划研究D 青岛：青岛理工大学，徐美清，孙晨亮 移动机器人路径规划方法研究J 科教信息，（）：顾国昌，张巧荣 移动机器人分层路径规划方法研究J 哈尔滨工程大学学报，（）：田春颖，刘瑜，冯申坤，等 基于栅格地图的移动机器人完全遍历算法 矩形分解法J 机械工程学报，（）：郝宗波，洪柄榕，黄庆成 基于栅格地图的机器人覆盖路径规划研究J 计算机应用研究，（）：Hsu S M，Lin C L，Yang M Y On the complete coverage pathplanning for mobile robots J Intelligent and Robotic System，（）：邱雪娜，刘士荣，宋加涛 不确定动态环境下移动机器人的完全遍历路径规划J 机器人，（）：郭小勤 未知环境下移动机器人遍历路径规划J 计算机工程与设计，（）：禹建丽，徐亮 室内自主机器人的路径规划J 中原工学院学报，（）：张峥炜 基于生物启发的群机器人系统群体搭建机制研究D 济南：山东大学，李彩虹，张子间 基于两点法的机器人路径规划J 山东理工大学学报：自然科学报，（）：（编辑：刘宝江）（上接第 页）Leung C K，Brajczuk D A Efficient algorithms for the mining ofconstrained frequent patterns from uncertain data J SIGKDDExplorations，（）：Cuzzocrea A，Leung C K Distributed mining of constrained frequent sets from uncertain data CAlgorithms and Architectures for Parallel Processing Springer Berlin Heidelberg，：Leung C K S，Sun L Equivalence class transformation basedmining of frequent itemsets from uncertain data C Proceedings of the ACMSymposium on Applied Computing ACM，：汪金苗，张龙波，邓齐志，等 不确定数据频繁项集挖掘方法综述J 计算机工程与应用，（）：刘卫明，杨健，毛伊敏 基于约束的不确定数据频繁项集挖掘算法研究J 计算机应用研究，（）：王爽，杨广明，朱志良 基于不确定数据的频繁项查询算法J 东北大学学报：自然科学版，（）：（编辑：刘宝江）第 期 陈鹏，等：移动机器人混合式全遍历覆盖路径规划算法移动机器人混合式全遍历覆盖路径规划算法移动机器人混合式全遍历覆盖路径规划算法作者：陈鹏，李彩虹，CHEN Peng，LI Cai-hong作者单位：山东理工大学计算机科学与技术学院,山东淄博,255091刊名：山东理工大学学报（自然科学版）英文刊名：Journal of Shandong University of Technology(Natural Science Edition)年，卷(期)：2013(5)参考文献(11条)参考文献(11条)1.邱燕;仪垂杰 小麦精播机器人路径规划研究 20112.徐美清;孙晨亮 移动机器人路径规划方法研究 2012(35)3.顾国昌;张巧荣 移动机器人分层路径规划方法研究 2011(05)4.田春颖;刘瑜;冯申坤 基于栅格地图的移动机器人完全遍历算法-矩形分解法期刊论文-H机械工程学报2004(10)5.郝宗波;洪柄榕;黄庆成 基于栅格地图的机器人覆盖路径规划研究期刊论文-H计算机应用研究 2007(10)6.Hsu S M;Lin C L;Yang M Y On the complete coverage path planning for mobile robots 2013(01)7.邱雪娜;刘士荣;宋加涛 不确定动态环境下移动机器人的完全遍历路径规划期刊论文-H机器人 2006(06)8.郭小勤 未知环境下移动机器人遍历路径规划期刊论文-H计算机工程与设计 2010(01)9.禹建丽;徐亮 室内自主机器人的路径规划 2010(03)10.张峥炜 基于生物启发的群机器人系统群体搭建机制研究 201211.李彩虹;张子间 基于两点法的机器人路径规划期刊论文-山东理工大学学报:自然科学报 2005(01)本文链接：http:/