第２７卷第５期２０１３年９月
山东理工大学学报（自然科学版）
ＪｏｕｒｎａｌｏｆＳｈａｎｄｏｎｇＵｎｉｖｅｒｓｉｔｙｏｆＴｅｃｈｎｏｌｏｇｙ（ＮａｔｕｒａｌＳｃｉｅｎｃｅＥｄｉｔｉｏｎ）
Ｖｏｌ．２７Ｎｏ．５Ｓｅｐ．２０１３
收稿日期：２０１３
０８
０４
基金项目：山东省高等学校科技计划项目（Ｊ１３ＬＮ２７）
作者简介：陈鹏，男，ｈｅｒｏｃｈｅｎｐｅｎｇ＠１６３．ｃｏｍ；通信作者：李彩虹，女，ｌｉｃｈ＠ｓｄｕｔ．ｅｄｕ．ｃｎ
文章编号：１６７２－６１９７（２０１３）０５－００２２－０６
移动机器人混合式全遍历覆盖路径规划算法
陈 鹏，李彩虹
（山东理工大学计算机科学与技术学院，山东淄博２５５０９１）
摘 要：针对移动机器人在未知环境下的全遍历覆盖任务，将滚动规划与已知环境下的搜索策略
相结合，设计了一种混合式的全遍历覆盖路径规划算法．对声纳传感器探测到的环境信息进行滚动规划，把未知区域转化为已知区域．在已知区域，采用有限状态机方式来组织全遍历覆盖路径规划算法，状态之间的转换通过二叉树搜索策略、目标栅格选取策略和两点法搜索策略来实现，并对算法进行仿真．结果表明，移动机器人能全遍历覆盖整个工作区域，重复率低，能有效提高工作效率．关键词：移动机器人；全遍历覆盖路径规划；滚动规划；有限状态机中图分类号：ＴＰ２４２文献标志码：Ａ
Ａｈｙｂｒｉｄａｌｇｏｒｉｔｈｍｏｆｃｏｍｐｌｅｔｅｃｏｖｅｒａｇｅｐａｔｈｐｌａｎｎｉｎｇｆｏｒｍｏｂｉｌｅｒｏｂｏｔ
ＣＨＥＮＰｅｎｇ，ＬＩＣａｉ‐ｈｏｎｇ
（ＳｃｈｏｏｌｏｆＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙ，ＳｈａｎｄｏｎｇＵｎｉｖｅｒｓｉｔｙｏｆＴｅｃｈｎｏｌｏｇｙ，Ｚｉｂｏ２５５０９１，Ｃｈｉｎａ）
Ａｂｓｔｒａｃｔ：Ｔｈｉｓｐａｐｅｒｐｒｅｓｅｎｔｓａｈｙｂｒｉｄｄｅｓｉｇｎａｌｇｏｒｉｔｈｍｏｆｃｏｍｐｌｅｔｅｃｏｖｅｒａｇｅｐａｔｈｐｌａｎｎｉｎｇｆｏｒｍｏｂｉｌｅｒｏｂｏｔｕｎｄｅｒｕｎｋｎｏｗｎｅｎｖｉｒｏｎｍｅｎｔｂａｓｅｄｏｎｔｈｅｒｏｌｌｉｎｇｐｌａｎｎｉｎｇａｎｄｋｎｏｗｎｅｎｖｉｒｏｎｍｅｎｔｓｅａｒｃｈｓｔｒａｔｅｇｙ．Ｔｈｅｕｎｋｎｏｗｎｅｎｖｉｒｏｎｍｅｎｔｈａｓｂｅｅｎｃｏｎｖｅｒｔｅｄｔｏｔｈｅｋｎｏｗｎａｒｅａｕｓｉｎｇｔｈｅｅｎｖｉ‐ｒｏｎｍｅｎｔａｌｉｎｆｏｒｍａｔｉｏｎｄｅｔｅｃｔｅｄｂｙｓｏｎａｒｓｅｎｓｏｒｓ．Ｔｈｅａｌｇｏｒｉｔｈｍｏｆｃｏｍｐｌｅｔｅｃｏｖｅｒａｇｅｐａｔｈｐｌａｎ‐ｎｉｎｇｉｓｏｒｇａｎｉｚｅｄｂｙｆｉｎｉｔｅｓｔａｔｅｍａｃｈｉｎｅ（ＦＳＭ）ａｐｐｒｏａｃｈｕｎｄｅｒｔｈｅｋｎｏｗｎｅｎｖｉｒｏｎｍｅｎｔ．Ｔｈｅｓｔａｔｅｓｗｉｔｃｈｈａｓｂｅｅｎｒｅａｌｉｚｅｄｂｙｔｈｅｂｉｎａｒｙｓｅａｒｃｈｓｔｒａｔｅｇｙ，ｔａｒｇｅｔｇｒｉｄｓｅｌｅｃｔｉｏｎｓｔｒａｔｅｇｙａｎｄｔｗｏ‐ｐｏｉｎｔｓｅａｒｃｈｓｔｒａｔｅｇｙ．Ａｔｌａｓｔｔｈｅａｌｇｏｒｉｔｈｍｈａｓｂｅｅｎｔｅｓｔｅｄｕｎｄｅｒｓｉｍｕｌａｔｅｄｅｎｖｉｒｏｎｍｅｎｔ．Ｓｉｍｕｌａｔｉｏｎｒｅｓｕｌｔｓｓｈｏｗｔｈａｔｍｏｂｉｌｅｒｏｂｏｔｃａｎｃｏｖｅｒｔｈｅｅｎｔｉｒｅｗｏｒｋａｒｅａｗｉｔｈｌｏｗｒｅｐｅｔｉｔｉｏｎｒａｔｅａｎｄｈｉｇｈｗｏｒｋｅｆｆｉｃｉｅｎｃｙ．
Ｋｅｙｗｏｒｄｓ：ｍｏｂｉｌｅｒｏｂｏｔ；ｃｏｍｐｌｅｔｅｃｏｖｅｒａｇｅｐａｔｈｐｌａｎｎｉｎｇ；ｒｏｌｌｉｎｇｐｌａｎｎｉｎｇ；ｆｉｎｉｔｅｓｔａｔｅｍａｃｈｉｎｅ（ＦＳＭ）
全遍历覆盖路径规划［１］
是指在满足某种性能评价指标最优或准优的前提下，寻找一条从起始点开始，且经过工作区域内所有可达点的路径规划．全遍历覆盖路径规划是一类特殊的路径规划，在许多领域都有着广阔的应用前景，特别是很多家用场合，都要求移动机器人具备全区域覆盖的能力．
按照对环境知识的了解，全遍历覆盖路径规划可分为环境已知和环境未知的路径规划．已知环境
下的路径规划，多采用单元分解法［２‐３］
和模板模型
法［４］．单元分解法是将环境分解为梯形单元，机器人在梯形单元中做往返运动，并通过邻接图来表示从一个单元到另一个单元的转移．缺点是单元分解过多致使重复率较高．模板模型法是根据覆盖区域获取的环境信息，与各个模板进行匹配来完成遍历．缺点是对环境缺乏整体规划，要求事先定义环境模型和模板记忆，对变化的环境很难处理．
对于环境未知情形下的路径规划，郝宗波［５］
等提出了基于传感器和栅格地图的路径规划方法，适合简单环境．Ｈｓｕ［６］
等采用离线规划和在线避障方
式来完成全遍历，实现过程较为复杂．邱雪娜［７］
等提出了基于生物激励与滚动启发式规则的路径规划，适合简单环境，在复杂环境下出现了较多转弯和重
复．郭小勤［８］
提出了可动态调节启发式规则的滚动路径规划算法，有效减少转弯次数，并解决了Ｕ型障碍物区域的连续遍历问题．禹建丽［９］等在犁田式路径规划的基础上，运用回溯法来解决遍历过程中的盲区问题．
环境已知的路径规划方法不适用于环境未知的情形，而未知环境下的路径规划方法存在着重复率较高、系统开销大等缺点．为提高工作效率，采用混合式的全遍历覆盖路径规划算法．利用滚动规划把未知区域转化为已知区域．于是，未知环境下的路径规划转化为在已知区域内的路径规划，从而有效地提高工作效率．
１ 实时环境信息
在未知环境下，移动机器人利用声纳传感器探测环境信息，如障碍物位置等．在研究中所使用的移动机器人是利曼科技有限公司生产的先锋机器人Ｐｉｏｎｅｅｒ３，先锋机器人Ｐｉｏｎｅｅｒ３装配有两个声纳阵，前方、后方各有一个，每个声纳阵由８个声纳环组成，用于物体检测、距离检测和自动避障等．其声纳环分布如图１
所示．
图１ 声纳环结构
移动机器人装载的声纳传感器，可探测机器人位置３６０°范围内的障碍物信息．此外，利用定位系统感知任意时刻的机器人位置Ｐｒｏｂｏｔ、目标栅格位置Ｐｇｏａｌ（ｘｇ，ｙｇ）和障碍物位置Ｐｏｂｓｔａｃｌｅ（ｉ）（ｉ＝１，…，ｎ）等信息．
机器人的视野域Ｓｓｅｎｓｅ定义为以机器人位置Ｐｒｏｂｏｔ为中心，以ｒｓｅｎｓｅ为半径的圆内．假定移动机器人的行进速度恒定，运动步长为ε，ε＜ｒｓｅｎｓｅ（ｒｓｅｎｓｅ为视野域半径）．在路径规划中，须将视野域Ｓｓｅｎｓｅ建模为已知区域．具体来说，就是以机器人的步长ε作为栅格长度对已知区域进行栅格化，为各个栅格赋予障碍属性Ｆｌａｇ（ｘ，ｙ）、覆盖属性Ｖｉｓｉｔｅｄ（ｘ，ｙ）、关联属性Ｒｅｌａｔｅｄ（ｘ，ｙ）以及可选属性Ｅｎａｂｌｅｄ（ｘ，ｙ）等，并假定用栅格的中心点坐标（ｘ，ｙ）来标识各个栅格．下面对各个属性做详细定义．
１）障碍属性Ｆｌａｇ（ｘ，ｙ）
Ｆｌａｇ（ｘ，ｙ）＝
１，栅格（ｘ，ｙ）为自由栅格
０，栅格（ｘ，ｙ）为障碍栅格
（１）
２）覆盖属性Ｖｉｓｉｔｅｄ（ｘ，ｙ） Ｖｉｓｉｔｅｄ（ｘ，ｙ）＝
０，栅格（ｘ，ｙ）未被遍历过１，栅格（ｘ，ｙ）仅被遍历过一次
≥２，栅格（ｘ，ｙ）被重复遍历的次数（２）３）关联属性Ｒｅｌａｔｅｄ（ｘ，ｙ）Ｒｅｌａｔｅｄ（ｘ，ｙ）表示与栅格（ｘ，ｙ）相邻的自由栅格的个数．
４）可选属性Ｅｎａｂｌｅｄ（ｘ，ｙ） Ｅｎａｂｌｅｄ（ｘ，ｙ）＝
０，栅格（ｘ，ｙ）尚未被传感器探 测到，不可遍历
１，栅格（ｘ，ｙ）是视野总域Ｓｓｅｎｓｏｒ内 的自由栅格，可遍历（３）
此外，还约定在栅格地图中，用机器人位置Ｐｒｏｂｏｔ所在的栅格
来标识机器人，用障碍物位置Ｐｏｂｓｔａｃｌｅ（ｉ）（ｉ＝１，…，ｎ）对应的栅格来标识障碍物．如图２所示．
图２ 视野域示意图
视野总域Ｓｓｅｎｓｏｒ定义为机器人在遍历过程中，探测到的区域总和．机器人在路径规划时，可依据具体情形，选择遍历视野总域Ｓｓｅｎｓｏｒ内的任意自由栅格．
３
２第５期 陈鹏，等：移动机器人混合式全遍历覆盖路径规划算法
机器人每行进一步，须实时探测、记录视野域Ｓｓｅｎｓｅ内的环境信息，并将新探测到的区域归入视野总域Ｓｓｅｎｓｏｒ内．
２ 全遍历覆盖路径规划算法
机器人在初始遍历时，执行二叉树搜索策略，直至相邻栅格被全部遍历．此时，由于没有达到全遍历覆盖的要求，随即执行目标栅格选取策略．待目标栅格确定后，执行两点法搜索策略．机器人逐步移动至目标栅格位置，并重新执行二叉树搜索策略，此后重复这个过程．在机器人移动过程中，一旦达到全遍历覆盖要求，路径规划立即终止．整个过程，就形成了有限状态机（ＦｉｎｉｔｅＳｔａｔｅＭａｃｈｉｎｅ，ＦＳＭ）［１０］的设计思路．下面就ＦＳＭ实现、策略设计、评价指标做具体阐述．
２．１ 全遍历覆盖路径规划的ＦＳＭ实现
移动机器人的全遍历覆盖路径规划可通过ＦＳＭ来实现，图３是规划算法的五状态ＦＳＭ实现图．ＦＳＭ包括五种状态，还需要设计三种策略进行状态之间的转换，分别是二叉树搜索策略、目标栅格选取策略和两点法搜索策略．
当机器人周围的相邻栅格中，不存在还未被遍历的自由栅格时，机器人须在视野总域Ｓｓｅｎｓｏｒ内，选取离当前机器人位置最近的、还未被遍历的自由栅格，作为下一遍历区域的起始栅格，我们称该起始栅格为目标栅格．
五种状态、三种策略作如下定义．
Ｓ１：初始状态
Ｓ２：在机器人周围的相邻栅格中，还存在未被遍历的自由栅格．
Ｓ３：在机器人周围的相邻栅格中，不存在还未被遍历的自由栅格．
Ｓ４：目标栅格已确定时．
Ｓ５：结束状态
Ｆ１：二叉树搜索策略
Ｆ２：目标栅格选取策略
Ｆ３：两点法搜索策略
移动机器人的全遍历覆盖过程何时结束，需依据具体环境和实际工作要求来决定．这里为了仿真实验的需要，假定遍历覆盖率达到９９％，全遍历覆盖过程结束．全遍历覆盖路径规划的ＦＳＭ实现如图３所示．
２．２
全遍历覆盖路径规划的策略设计
图３ 全遍历覆盖路径规划的ＦＳＭ实现
２．２．１ 二叉树搜索策略Ｆ１
机器人处于Ｓ２时，执行Ｆ１．该状态的目标是搜索与机器人相邻的自由栅格，找出其中关联栅格数最大的栅格，并遍历该栅格．值得指出的是，机器人每前进一步，须实时更新环境信息，并检测在机器人的相邻栅格中是否还存在未被访问的自由栅格．若存在，则重复Ｆ１．若不存在，机器人随即跳转至Ｓ３．为满足二叉树搜索策略的需要，为所有栅格赋予四种属性：障碍属性Ｆｌａｇ（ｘ，ｙ）、遍历属性Ｖｉｓｉ‐ｔｅｄ（ｘ，ｙ）、关联属性Ｒｅｌａｔｅｄ（ｘ，ｙ）、可选属性Ｅｎａ‐ｂｌｅｄ（ｘ，ｙ）．这样，二叉树搜索策略选取栅格须符合：
障碍属性值Ｆｌａｇ（ｘ，ｙ）为１、遍历属性值Ｖｉｓｉｔｅｄ（ｘ，ｙ）为０、关联属性值Ｒｅｌａｔｅｄ（ｘ，ｙ）最大、可选属性值Ｅｎａｂｌｅｄ（ｘ，ｙ）为１．
二叉树搜索策略，涉及到了关联栅格数的计算问题．根据待研究栅格在栅格区域的位置不同，栅格区域可划分为三种模型：四格型、六格型和九格型．通过转化，任意栅格区域均符合三种模型，如图４所示．为此，
本文仅对三种模型进行研究．
（ａ）四格型（ｂ）六格型（ｃ）九格型
图４ 栅格区域模型示意图
１）若采用数组结构存储各栅格的关联栅格信息，假定数组名为Ａ．以栅格ｉ为例，则有：
（１）当栅格ｉ为自由栅格时
ａ）四格型
Ａ｛ｉ｝．Ｒｅｌａｔｅｄ＝Ａ｛１｝．Ｆｌａｇ＋Ａ｛２｝．Ｆｌａｇ
４２山东理工大学学报（自然科学版）２０１３年
＋Ａ｛３｝．Ｆｌａｇ（４）ｂ）六格型
Ａ｛ｉ｝．Ｒｅｌａｔｅｄ＝Ａ｛１｝．Ｆｌａｇ＋
Ａ｛２｝．Ｆｌａｇ＋
Ａ｛３｝．Ｆｌａｇ＋
Ａ｛４｝．Ｆｌａｇ＋
Ａ｛５｝．Ｆｌａｇ（５）ｃ）九格型
Ａ｛ｉ｝．Ｒｅｌａｔｅｄ＝Ａ｛１｝．Ｆｌａｇ＋
Ａ｛２｝．Ｆｌａｇ＋
Ａ｛３｝．Ｆｌａｇ＋
Ａ｛４｝．Ｆｌａｇ＋
Ａ｛５｝．Ｆｌａｇ＋
Ａ｛６｝．Ｆｌａｇ＋
Ａ｛７｝．Ｆｌａｇ＋
Ａ｛８｝．Ｆｌａｇ（６）此处，若栅格ｉ的相邻栅格中有障碍物栅格，则障碍物栅格的障碍属性值Ｆｌａｇ为０，因此，栅格ｉ的关联属性值不受影响，Ａ｛ｉ｝．Ｒｅｌａｔｅｄ能够真实反映栅格ｉ关联栅格的实际个数．
（２）当栅格ｉ为障碍栅格时
Ａ｛ｉ｝．Ｒｅｌａｔｅｄ＝０（７）２）若栅格ｉ为机器人栅格，求所有相邻栅格的最大关联栅格数，则有：
ａ）四格型
Ａ｛ｉ｝．ｍａｘｒｅｌａｔｅｄ＝
ｍａｘ（Ａ｛１｝．Ｒｅｌａｔｅｄ，
Ａ｛２｝．Ｒｅｌａｔｅｄ，
Ａ｛３｝．Ｒｅｌａｔｅｄ）（８）ｂ）六格型
Ａ｛ｉ｝．ｍａｘｒｅｌａｔｅｄ＝
ｍａｘ（Ａ｛１｝．Ｒｅｌａｔｅｄ，
Ａ｛２｝．Ｒｅｌａｔｅｄ，
Ａ｛３｝．Ｒｅｌａｔｅｄ，
Ａ｛４｝．Ｒｅｌａｔｅｄ，
Ａ｛５｝．Ｒｅｌａｔｅｄ）（９）ｃ）九格型
Ａ｛ｉ｝．ｍａｘｒｅｌａｔｅｄ＝
ｍａｘ（Ａ｛１｝．Ｒｅｌａｔｅｄ，
Ａ｛２｝．Ｒｅｌａｔｅｄ，
Ａ｛３｝．Ｒｅｌａｔｅｄ，
Ａ｛４｝．Ｒｅｌａｔｅｄ，
Ａ｛５｝．Ｒｅｌａｔｅｄ，
Ａ｛６｝．Ｒｅｌａｔｅｄ，
Ａ｛７｝．Ｒｅｌａｔｅｄ，
Ａ｛８｝．Ｒｅｌａｔｅｄ）（１０）
通过比较，得到栅格ｉ的最大关联栅格数Ａ｛ｉ｝．ｍａｘｒｅｌａｔｅｄ，记录最大关联栅格数对应的栅格编号ｊ．紧接着，移动机器人前进至栅格ｊ，并实时更新环境信息．
２．２．２ 目标栅格选取策略Ｆ２
机器人处于Ｓ３时，为使机器人离开已遍历完区域，到未遍历区域继续遍历，需选取一个目标栅格，即在视野总域Ｓｓｅｎｓｏｒ内，选取离机器人栅格最近的可选栅格，并且要求该栅格还未被遍历过．待目标栅格确定后，机器人随即跳转至Ｓ４．
假设任意栅格与机器人位置Ｐｒｏｂｏｔ（ｘｒ，ｙｒ）之间的距离用Ｄｉｓｔａｎｃｅ表示，则目标栅格须符合：障碍属性值Ｆｌａｇ（ｘ，ｙ）为１、遍历属性值Ｖｉｓｉｔｅｄ（ｘ，ｙ）为０、可选属性值Ｅｎａｂｌｅｄ（ｘ，ｙ）为１、Ｄｉｓｔａｎｃｅ值最小．
若用栅格的中心点坐标来标识栅格位置，则待选栅格Ｐｉ（ｘｉ，ｙｉ）（ｉ＝１，…，ｍ，ｍ为符合目标栅格选取条件的栅格总数）与机器人位置Ｐｒｏｂｏｔ（ｘｒ，ｙｒ）之间的距离Ｄｉｓｔａｎｃｅ（ｉ）可表示为
Ｄｉｓｔａｎｃｅ（ｉ）＝（ｘｉ－ｘｒ）２＋（ｙｉ－ｙｒ）２
（ｉ＝１，…，ｍ）（１１）
求Ｄｉｓｔａｎｃｅ（ｉ）的最小值：
Ｄｉｓｔａｎｃｅ＝ｍｉｎ（Ｄｉｓｔａｎｃｅ（ｉ））
ｉ＝１，…，ｍ（１２）
通过比较，得到待选栅格与机器人位置之间的距离最小值Ｄｉｓｔａｎｃｅ，并记录该最小值对应的栅格编号ｋ、栅格中心点坐标Ｐｋ（ｘｋ，ｙｋ）．
２．２．３ 两点法搜索策略Ｆ３
目标栅格确定后，机器人立即从当前位置，移动到目标栅格位置．在向目标栅格移动过程中，若已达到全遍历覆盖要求，则终止整个遍历过程．若到达目标栅格后，还未达到全遍历覆盖要求，机器人随即跳转至Ｓ２．
两点法搜索策略简述为移动机器人向目标栅格直线移动时，若遇到障碍物，就改变方向、移动到没有障碍物的位置，并再次确定目标栅格的方向、感知障碍物信息．如此反复，直至到达目标栅格［１１］．两点法搜索策略示意图如图５所示．
由图５可知，Ａ为起始点，Ｂ为目标栅格，起始点Ａ与目标栅格Ｂ之间的线段ＡＢ上有障碍物．此时，首先向上偏转角度θ，得到的线段ＡＢ１上仍有障碍物，再以线段ＡＢ为基准，向下偏转角度θ，得到的
５２
第５期 陈鹏，等：移动机器人混合式全遍历覆盖路径规划算法
图５ 两点法搜索过程示意图
线段ＡＢ２上也有障碍物，再从线段ＡＢ１开始向上偏转角度θ…．如此反复，当偏转到线段ＡＢｉ时，ＡＢｉ上没有障碍物，得到一点Ｃ，以此类推得到另一点Ｄ，直至到达目标栅格Ｂ，整个搜索过程停止．
２．３ 评价指标
遍历结束后，须引入“评价指标”对遍历结果进行评价．本文采用遍历覆盖率和遍历重叠率作为评价指标．假设Ｓ表示整个工作空间，ＳΩ表示可达区域的面积，Ｓｈｃ表示已遍历的面积，Ｓｃｃ表示重复遍历的面积．
１）遍历覆盖率：遍历完成后，已遍历面积与可达区域面积的百分比．
Ｊｈｃ＝（Ｓｈｃ／ＳΩ）×１００％（１３）
２）遍历重叠率：所有重复遍历面积之和与可达区域面积的百分比．
Ｊｃｃ＝（Ｓｃｃ／ＳΩ）×１００％（１４）
为了尽可能地减少遍历盲区，不可避免地就会产生一定程度的重叠．显然，重叠率越小越好，但受系统误差、控制精度以及环境等诸多因素的影响，重叠区域不可能太小．但若机器人的性能较高，则遍历重叠率可控制在较小的范围内，遍历效率大幅提高，遍历效果趋于理想．
３ 仿真实验
利用以上设计的全遍历覆盖路径规划算法，对移动机器人在障碍物稀疏程度不同的环境下进行仿真．程序运行前，设定覆盖率达到９９％时，遍历结束．仿真结果如图６所示．
仿真结果表明，移动机器人在无障碍环境、障碍稀疏环境、障碍密集环境下，都能有效地躲避障碍物，高效地完成全遍历覆盖任务，遍历重复率也被控
制在可接受的范围内．
（ａ）
无障碍环境
（ｂ）
障碍稀疏环境
（ｃ）
障碍密集环境
图６ 遍历效果图
６２山东理工大学学报（自然科学版）２０１３年
４ 结束语
本文针对移动机器人在未知环境下的全遍历覆盖任务，提出了滚动规划与搜索策略相结合的一种混合式全遍历覆盖路径规划算法，并进行仿真实验．结果表明，算法具有以下特点：能在无障碍环境、障碍稀疏环境、障碍密集环境下，完成全遍历覆盖路径规划任务；能覆盖工作区域的几乎全部区域，遍历覆盖率高；移动机器人重复遍历的栅格较少，重复率较低．从整体来看，遍历覆盖率较高，遍历重复率较低，因此遍历效率较高．
移动机器人根据全遍历覆盖路径规划算法，能够高效地完成全遍历覆盖任务，但也存在一些不足之处，如尚不能保证遍历路径长度绝对最短等，这些问题将是今后研究的课题．
参考文献：
［１］邱燕，仪垂杰．小麦精播机器人路径规划研究［Ｄ］．青岛：青岛理工大学，２０１１．［２］徐美清，孙晨亮．移动机器人路径规划方法研究［Ｊ］．科教信息，２０１２（３５）：６０‐６１．
［３］顾国昌，张巧荣．移动机器人分层路径规划方法研究［Ｊ］．哈尔滨工程大学学报，２０１１，２２（５）：３１‐３２．
［４］田春颖，刘瑜，冯申坤，等．基于栅格地图的移动机器人完全遍历算法—矩形分解法［Ｊ］．机械工程学报，２００４，４０（１０）：５６‐６１．［５］郝宗波，洪柄榕，黄庆成．基于栅格地图的机器人覆盖路径规划研究［Ｊ］．计算机应用研究，２００７，２４（１０）：５６‐５８．
［６］ＨｓｕＳＭ，ＬｉｎＣＬ，ＹａｎｇＭＹ．Ｏｎｔｈｅｃｏｍｐｌｅｔｅｃｏｖｅｒａｇｅｐａｔｈｐｌａｎｎｉｎｇｆｏｒｍｏｂｉｌｅｒｏｂｏｔｓ［Ｊ］．ＩｎｔｅｌｌｉｇｅｎｔａｎｄＲｏｂｏｔｉｃＳｙｓｔｅｍ，２０１３，７（１）：１‐１９．
［７］邱雪娜，刘士荣，宋加涛．不确定动态环境下移动机器人的完全遍历路径规划［Ｊ］．机器人，２００６，２８（６）：５８６‐５９２．
［８］郭小勤．未知环境下移动机器人遍历路径规划［Ｊ］．计算机工程与设计，２０１０，３１（１）：１７２‐１７４．
［９］禹建丽，徐亮．室内自主机器人的路径规划［Ｊ］．中原工学院学报，２０１０，２１（３）：１‐３．
［１０］张峥炜．基于生物启发的群机器人系统群体搭建机制研究［Ｄ］．济南：山东大学，２０１２．
［１１］李彩虹，张子间．基于两点法的机器人路径规划［Ｊ］．山东理工大学学报：自然科学报，２００５，１９（１）：１７‐２０．
（编辑：刘宝江）
（上接第２１页）
［４］ＬｅｕｎｇＣＫ，ＢｒａｊｃｚｕｋＤＡ．Ｅｆｆｉｃｉｅｎｔａｌｇｏｒｉｔｈｍｓｆｏｒｔｈｅｍｉｎｉｎｇｏｆｃｏｎｓｔｒａｉｎｅｄｆｒｅｑｕｅｎｔｐａｔｔｅｒｎｓｆｒｏｍｕｎｃｅｒｔａｉｎｄａｔａ［Ｊ］．ＳＩＧＫＤＤＥｘｐｌｏｒａｔｉｏｎｓ，２０１０，１１（２）：１２３‐１３０．
［５］ＣｕｚｚｏｃｒｅａＡ，ＬｅｕｎｇＣＫ．Ｄｉｓｔｒｉｂｕｔｅｄｍｉｎｉｎｇｏｆｃｏｎｓｔｒａｉｎｅｄｆｒｅ‐ｑｕｅｎｔｓｅｔｓｆｒｏｍｕｎｃｅｒｔａｉｎｄａｔａ［Ｃ］／／ＡｌｇｏｒｉｔｈｍｓａｎｄＡｒｃｈｉｔｅｃ‐ｔｕｒｅｓｆｏｒＰａｒａｌｌｅｌＰｒｏｃｅｓｓｉｎｇ．ＳｐｒｉｎｇｅｒＢｅｒｌｉｎＨｅｉｄｅｌｂｅｒｇ，２０１１：４０‐５３．
［６］ＬｅｕｎｇＣＫＳ，ＳｕｎＬ．Ｅｑｕｉｖａｌｅｎｃｅｃｌａｓｓｔｒａｎｓｆｏｒｍａｔｉｏｎｂａｓｅｄｍｉｎｉｎｇｏｆｆｒｅｑｕｅｎｔｉｔｅｍｓｅｔｓｆｒｏｍｕｎｃｅｒｔａｉｎｄａｔａ［Ｃ］／／Ｐｒｏｃｅｅｄ‐
ｉｎｇｓｏｆｔｈｅ２０１１ＡＣＭＳｙｍｐｏｓｉｕｍｏｎＡｐｐｌｉｅｄＣｏｍｐｕｔｉｎｇ．ＡＣＭ，２０１１：９８３‐９８４．
［７］汪金苗，张龙波，邓齐志，等．不确定数据频繁项集挖掘方法综述［Ｊ］．计算机工程与应用，２０１１，４７（２０）：１２１‐１２５．
［８］刘卫明，杨健，毛伊敏．基于约束的不确定数据频繁项集挖掘算法研究［Ｊ］．计算机应用研究，２０１２，２９（１０）：３６６９‐３６７１．［９］王爽，杨广明，朱志良．基于不确定数据的频繁项查询算法［Ｊ］．东北大学学报：自然科学版，２０１１，３２（３）：３４４‐３４７
（编辑：刘宝江）
７２
第５期 陈鹏，等：移动机器人混合式全遍历覆盖路径规划算法
移动机器人混合式全遍历覆盖路径规划算法
作者：陈鹏， 李彩虹， CHEN Peng， LI Cai-hong
作者单位：山东理工大学计算机科学与技术学院,山东淄博,255091
刊名：
山东理工大学学报（自然科学版）
英文刊名：Journal of Shandong University of Technology (Natural Science Edition)
年，卷(期)：2013(5)
参考文献(11条)
1.邱燕;仪垂杰小麦精播机器人路径规划研究 2011
2.徐美清;孙晨亮移动机器人路径规划方法研究 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.张峥炜基于生物启发的群机器人系统群体搭建机制研究 2012
11.李彩虹;张子间基于两点法的机器人路径规划[期刊论文]-山东理工大学学报:自然科学报 2005(01)
本文链接：https://www.doczj.com/doc/a012663749.html,/Periodical_sdgcxyxb201305006.aspx
遗传算法与机器人路径规划 摘要：机器人的路径规划是机器人学的一个重要研究领域，是人工智能和机器人学的一个结合点。对于移动机器人而言，在其工作时要求按一定的规则，例如时间最优，在工作空间中寻找到一条最优的路径运动。机器人路径规划可以建模成在一定的约束条件下，机器人在工作过程中能够避开障碍物从初始位置行走到目标位置的路径优化过程。遗传算法是一种应用较多的路径规划方法，利用地图中的信息进行路径规划，实际应用中效率比较高。 关键词：路径规划；移动机器人；避障；遗传算法 Genetic Algorithm and Robot Path Planning Abstract: Robot path planning research is a very important area of robotics, it is also a combine point of artificial intelligence and robotics. For the mobile robot, it need to be worked by certain rulers（e.g time optimal），and find a best movement path in work space. Robot path planning can be modeled that in the course of robots able to avoid the obstacles from the initial position to the target location,and it ruquire to work under ertain constraints. Genetic algorithm used in path planning is very common, when planning the path ,it use the information of map ,and have high eficient in actual. Key words: Path planning,mobile robot, avoid the obstacles, genetic algorithm 1路径规划 1.1机器人路径规划分类 （1）根据机器人对环境信息掌握的程度和障碍物的不同，移动机器人的路径规划基本上可分为以下几类： 1，已知环境下的对静态障碍物的路径规划； 2，未知环境下的对静态障碍物的路径规划； 3，已知环境下对动态障碍物的路径规划； 4，未知环境下的对动态障碍物的路径规划。 （2）也可根据对环境信息掌握的程度不同将移动机器人路径规划分为两种类型： 1，基于环境先验完全信息的全局路径规划； 2，基于传感器信息的局部路径规划。 （第二种中的环境是未知或部分未知的，即障碍物的尺寸、形状和位置等信息必须通过传感器获取。） 1.2路径规划步骤 无论机器人路径规划属于哪种类别，采用何种规划算法，基本上都要遵循以下步骤： 1, 建立环境模型，即将现实世界的问题进行抽象后建立相关的模型； 2, 路径搜索方法，即寻找合乎条件的路径的算法。 1.3路径规划方法
文章编号 2 2 2 一种快速神经网络路径规划算法α 禹建丽? ∏ √ 孙增圻成久洋之 洛阳工学院应用数学系日本冈山理科大学工学部电子工学科 2 清华大学计算机系国家智能技术与系统重点实验室日本冈山理科大学工学部信息工学科 2 摘要本文研究已知障碍物形状和位置环境下的全局路径规划问题给出了一个路径规划算法其能量函数 利用神经网络结构定义根据路径点位于障碍物内外的不同位置选取不同的动态运动方程并针对障碍物的形状设 定各条边的模拟退火初始温度仿真研究表明本文提出的算法计算简单收敛速度快能够避免某些局部极值情 况规划的无碰路径达到了最短无碰路径 关键词全局路径规划能量函数神经网络模拟退火 中图分类号 ×°文献标识码 ΦΑΣΤΑΛΓΟΡΙΤΗΜΦΟΡΠΑΤΗΠΛΑΝΝΙΝΓ ΒΑΣΕΔΟΝΝΕΥΡΑΛΝΕΤ? ΟΡΚ ≠ 2 ? ? ≥ 2 ≥ ∏ ΔεπαρτμεντοφΜατηεματιχσ ΛυοψανγΙνστιτυτεοφΤεχηνολογψ Λυοψανγ
ΔεπαρτμεντοφΕλεχτρονιχΕνγινεερινγ ΦαχυλτψοφΕνγινεερινγ ΟκαψαμαΥνι?ερσιτψοφΣχιενχε 2 Ριδαι2χηο 2 ?απαν ΔεπαρτμεντοφΧομπυτερΣχιενχε Τεχηνολογψ ΣτατεΚεψΛαβοφΙντελλιγεντΤεχηνολογψ Σψστεμσ ΤσινγηυαΥνι?ερσιτψ Βει?ινγ ΔεπαρτμεντοφΙνφορματιον ΧομπυτερΕνγινεερινγ ΦαχυλτψοφΕνγινεερινγ ΟκαψαμαΥνι?ερσιτψοφΣχιενχε 2 Ριδαι2χηο 2 ?απαν Αβστραχτ ∏ √ √ √ × ∏ ∏ ∏ ∏ ∏ ∏ 2 ∏ √ × ∏ ∏ ∏ ∏ √ ∏ Κεψωορδσ ∏ ∏ ∏ 1引言Ιντροδυχτιον 机器人路径规划问题可以分为两种一种是基于环境先验完全信息的全局路径规划≈ 另一种是基于传感器信息的局部路径规划≈ ?后者环境是未知或者部分未知的全局路径规划已提出的典型方法有可视图法 ! 图搜索法≈ ! 人工势场法等可视图法的优点是可以求得最短路径但缺乏灵活性并且存在组合爆炸问题图搜索法比较灵活机器人的起始点和目标点的改变不会造成连通图的重新构造但不是任何时候都可以获得最短路径可视图法和图搜索法适用于多边形障碍物的避障路径规划问题但不适用解决圆形障碍物的避障路径规划问题人工势场法的基本思想是通过寻找路径点的能量函数的极小值点而使路径避开障碍物但存在局部极小值问题且不适于寻求最短路径≈ 文献≈ 给出的神经网络路径规划算法我们称为原算法引入网络结构和模拟退火等方法计算简单能避免某些局部极值情况且具有并行性及易于从二维空间推广到三维空间等优点对人工势场法给予了较大的改进但在此算法中由于路径点的总能量函数是由碰撞罚函数和距离函数两部分的和构成的而路径点 第卷第期年月机器人ΡΟΒΟΤ? α收稿日期
清扫机器人路径规划方法研究 摘要：近年来,智能清扫机器人系统的研究和开发已具备了坚实的基础和良好的 发展前景。现在的智能清扫机器人通过软硬件的合理设计，使其能够自动避开障 碍物，实现一般家居环境及特定户外环境的自主清扫工作。本文简单介绍了清扫 机器人基于无环境模型的路径规划的具体办法。 关键词：清扫机器人、无环境模型、路径规划 一、绪论 机器人的研究在日本和欧美的一些发达国家的研究相对比较深入，同时也取 得了很多显著的成果。国内关于清扫机器人的研究也取得了极大的进展。我国继 清华大学于1994年通过智能清扫机器人鉴定之后，陆续有中国科学院沈阳自动 化所研制了全方位移动式机器人视觉导航系统；2001年香港城市大学完整地研究了地面清扫机器人的导航、控制及整个硬件系统；2009年哈尔滨工业大学与香港中文大学合作，联合研制开发出一种全方位地面清扫机器人。总而言之，清洁机 器人的研究正在快速发展，并且也越来越深入，但是还有需要完善和改进的地方，例如清洁机器人的避障问题，路径规划等等，所以针对清扫机器人进行一系列的 技术研究探讨是相当有意义的。 二、基于无环境模型的路径规划 清洁机器人的路径规划是根据机器人所感知到的工作环境信息，按照某种优 化指标，在起始点和目标点规划出一条与环境障碍无碰撞的路径，并且实现所需 清扫区域的合理完全路径覆盖，同时实现封闭区域内机器人行走路径对工作区域 的最大覆盖率和最小重复率。目前全区域覆盖路径规划有两种，一种是无环境模 型的路径规划，另一种是基于环境模型的路径规划。本文主要着重介绍无环境规 划的整个过程。 无环境模型的路径规划不需要建立环境模型，有随机遍历路径规划和全区域 覆盖路径规划两种模式。机器人在清扫的时候比较自由，一般都是采用递进的方式，清扫完这个直线再偏移一段距离，掉头清扫另外一条直线，以达到全区域清扫，本文也着重介绍无环境模型的路径规划。基于无环境模型的依据边界的路径 规划方法 三、基于无环境模型的路径规划具体方法 （一）建立房间边界 首次在未知空间内行驶时，小车所能记录的信息为两种，一种是小车两个驱 动轮行驶路程L1与L2，另一种是各传感器被触发的状态。下图是小车在某转角 处的路线图，根据以上特点及为后续数据处理提供依据，我们可以建立如下规则。轨迹计算原理，数据处理规则。 (1)小车转角计算 若小车沿某一物体边缘转过θ角，则可以通过如下公式求算θ角 规定为行走时小车的拐角，规定连续经过多个拐角时，为各自拐角的和。 (2)小车行程的计算 小车行程的计算可以按照两驱动轮轨迹线的中心线即可代表小车行驶时的轨迹，小车行 车记录为： (3)机器人沿着边界行驶 机器人选择任意一方向寻找边界，找到边界后，小车沿边界方向前进直到遇到拐角。行 进过程中根据传感器状态确定内外侧路径，确定完内外侧后，小车前进过程中所记录的拐角
1绪论 1.1机器人简介 1.1.1什么是机器人 机器人一词不仅会在科幻小说、动画片等上看到和听到，有时也会在电视上看到在工厂进行作业的机器人，在实际中也有机会看到机器人的展示。今天，说不定机器人就在我们的身过，但这里我们要讨论的是什么是机器人学研究的机器人。 机器人（robot）一词来源下1920年捷克作家卡雷尔. 查培克（Kapel Capek）所编写的戏剧中的人造劳动者，在那里机器人被描写成像奴隶那样进行劳动的机器。 后来作为一种虚构的机械出现在许多作品中，代替人们去完成某些工作。20世纪60年代出现了作为可实用机械的机器人。为了反这种机器人同虚构的机器人及玩具机器人加以区别，称其为工业机器人。 工业机器人的兴起促进了大学及研究所开展机器人的研究。随着计算机的普及，又积极地开展了带有智能的机器人的研究。到70年代，机器人作为工程对象已经被确认，机器人一词也受到公认。目前，机器人学的研究对象已不仅仅是工业机器人了。 即便是实际存在的机器人，也很难把它定义为机器人，而且其定义也随着时代在变化。这里简单地反具有下述性质的机械看作是机器人： 1.代替人进行工作：机器人能像人那样使用工具和机械，因此，数控机床和 汽车不是机器人。 2.有通有性：既可简单地变换所进行的作为，又能按照工作状况的变化相应 地进行工作。一般的玩具机器人不能说有通用性。 3.直接对个界作工作：不仅是像计算机那样进行计算，而且能依据计算结果 对外界结果对外界产生作用。 机器人学把这样定义的机器人作为研究对象。
1.1.2机器人的分类 机器人的分类方法很多，这里我们依据三个有代表性的分类方法列举机器人的种类。 首先，由天机器人要代替人进行作业，因此可根据代替人的哪一个器官来分类： 操作机器人（手）：利用相当于手臂的机械手、相当于手指的手爪来使物体协作。 移动机器人（腿）：虽然已开发出了2足步行和4足步行机器人，但实用的却是用车轮进行移动的机器人。（本文以轮式移动机器人作为研究对象）视觉机器人（眼）：通过外观检查来除掉残次品，观看人的面孔认出是谁。虽然还有使用触觉的机器人，但由于它不是为了操作，所以不能说是触觉机器人。 也还有不仅代替单一器官的机器人，例如进行移动操作，或进行视觉和操作的机器人。 其次，按机器人的应用来分类： 工业机器人：可分为搬送、焊接、装配、喷漆、检查等机器人，主要用于工厂内。 极限作业器人：主要用在人们难以进入的核电站、海底、宇宙空间等进行作为的机器人。也包括建筑、农业机器人等。 娱乐机器人：有弹奏乐器的机器人、舞蹈机器人、宠物机器人等，具有某种程度的通用性。也有适应环境面改变行动的宠物机器人。 最后则是按照基于什么样的信息进行动作来分类： 表1基于动作信息的机器人分类
第5期(总第156期) 2009年10月机械工程与自动化 M ECHAN I CAL EN G I N EER I N G & AU TOM A T I ON N o 15 O ct 1 文章编号:167226413(2009)0520194203 机器人路径规划方法的研究 李爱萍,李元宗 (太原理工大学机械工程学院,山西 太原 030024) 摘要:路径规划技术是机器人学研究领域中的一个重要部分。目前的研究主要分为全局规划方法和局部规划方法两大类。通过对机器人路径规划方法研究现状的分析,指出了各种方法的优点及不足,并对其发展方向进行了展望。 关键词:机器人;全局规划;局部规划中图分类号:T P 242 文献标识码:A 收稿日期:2009201207;修回日期:2009204218 作者简介:李爱萍(19792),女,山西晋中人,在读硕士研究生。 0 引言 路径规划技术是机器人学研究领域中的一个重要 部分。机器人的最优路径规划就是依据某个或某些优化准则(如工作代价最小、行走路线最短、行走时间最短等),在其工作空间中找到一条从起始状态到目标状态的最优路径。根据对环境信息的掌握程度不同,路径规划可分为:①全局路径规划:环境信息完全已知,根据环境地图按照一定的算法搜寻一条最优或者近似最优的无碰撞路径,规划路径的精确程度取决于获取环境信息的准确程度;②局部路径规划:环境信息完全未知或部分未知,根据传感器的信息来不断地更新其内部的环境信息,从而确定出机器人在地图中的当前位置及周围局部范围内的障碍物分布情况,并在此基础上,规划出一条从当前点到某一子目标点的最优路径。 1 全局规划方法111 栅格法 栅格法是目前研究最广泛的路径规划方法之一。该方法将机器人的工作空间分解为多个简单的区域(栅格),由这些栅格构成一个显式的连通图,或在搜索过程中形成隐式的连通图,然后在图上搜索一条从起始栅格到目标栅格的路径。一般路径只需用栅格的序号表示。但栅格的划分直接影响其规划结果,如果栅格划分过大,环境信息储藏量小,分辨率下降,规划能力就差;栅格划分过小,规划时间长,而且对信息存储能力的要求会急剧增加。112 可视图法 可视图法中的路径图由捕捉到的存在于机器人一 维网络曲线(称为路径图)自由空间中的节点组成。路径的初始状态和目标状态同路径图中的点相对应,这样路径规划问题就演变为在这些点间搜索路径的问题。要求机器人和障碍物各顶点之间、目标点和障碍物各顶点之间以及各障碍物顶点与顶点之间的连线均不能穿越障碍物,即直线是“可视的”。然后采用某种方法搜索从起始点到目标点的最优路径,搜索最优路径的问题就转化为从起始点到目标点经过这些可视直线的最短距离问题。该法能够求得最短路径,但需假设忽略机器人的尺寸大小,使得机器人通过障碍物顶点时离障碍物太近甚至接触,并且搜索时间长。113 拓扑法 拓扑法将规划空间分割成具有拓扑特征的子空间,根据彼此的连通性建立拓扑网络,在网络上寻找起始点到目标点的拓扑路径,最终由拓扑路径求出几何路径。拓扑法的基本思想是降维法,即将在高维几何空间中求路径的问题转化为低维拓扑空间中判别连通性的问题。其优点在于利用拓扑特征大大缩小了搜索空间,其算法的复杂性仅依赖于障碍物数目,在理论上是完备的;而且拓扑法通常不需要机器人的准确位置,对于位置误差也就有了更好的鲁棒性。缺点是建立拓扑网络的过程相当复杂,特别是在增加障碍物时如何有效地修正已经存在的拓扑网是有待解决的问题。 114 自由空间法 自由空间法采用预先定义的广义锥形或凸多边形等基本形状构造自由空间,并将自由空间表示为连通图,通过搜索连通图来进行路径规划。自由空间的构
第25卷第7期V ol.25No.7 控制与决策 Control and Decision 2010年7月 Jul.2010移动机器人路径规划技术综述 文章编号:1001-0920(2010)07-0961-07 朱大奇,颜明重 (上海海事大学水下机器人与智能系统实验室，上海201306) 摘要:智能移动机器人路径规划问题一直是机器人研究的核心内容之一.将移动机器人路径规划方法概括为:基于模版匹配路径规划技术、基于人工势场路径规划技术、基于地图构建路径规划技术和基于人工智能的路径规划技术.分别对这几种方法进行总结与评价,最后展望了移动机器人路径规划的未来研究方向. 关键词:移动机器人；路径规划；人工势场；模板匹配；地图构建；神经网络；智能计算 中图分类号:TP18；TP273文献标识码:A Survey on technology of mobile robot path planning ZHU Da-qi,YAN Ming-zhong (Laboratory of Underwater Vehicles and Intelligent Systems，Shanghai Maritime University，Shanghai201306, China．Correspondent：ZHU Da-qi，E-mail：zdq367@https://www.doczj.com/doc/a012663749.html,) Abstract:The technology of intelligent mobile robot path planning is one of the most important robot research areas.In this paper the methods of path planning are classi?ed into four classes:Template based,arti?cial potential?eld based,map building based and arti?cial intelligent based approaches.First,the basic theories of the path planning methods are introduced brie?y.Then,the advantages and limitations of the methods are pointed out.Finally,the technology development trends of intelligent mobile robot path planning are given. Key words:Mobile robot；Path planning；Arti?cial potential?eld；Template approach；Map building；Neural network; Intelligent computation 1引言 所谓移动机器人路径规划技术,就是机器人根据自身传感器对环境的感知,自行规划出一条安全的运行路线,同时高效完成作业任务.移动机器人路径规划主要解决3个问题:1)使机器人能从初始点运动到目标点;2)用一定的算法使机器人能绕开障碍物,并且经过某些必须经过的点完成相应的作业任务;3)在完成以上任务的前提下,尽量优化机器人运行轨迹.机器人路径规划技术是智能移动机器人研究的核心内容之一,它起始于20世纪70年代,迄今为止,己有大量的研究成果报道.部分学者从机器人对环境感知的角度,将移动机器人路径规划方法分为3种类型[1]:基于环境模型的规划方法、基于事例学习的规划方法和基于行为的路径规划方法;从机器人路径规划的目标范围看,又可分为全局路径规划和局部路径规划;从规划环境是否随时间变化方面看,还可分为静态路径规划和动态路径规划. 本文从移动机器人路径规划的具体算法与策略上,将移动机器人路径规划技术概括为以下4类:模版匹配路径规划技术、人工势场路径规划技术、地图构建路径规划技术和人工智能路径规划技术.分别对这几种方法进行总结与评价,展望了移动机器人路径规划的未来发展方向. 2模版匹配路径规划技术 模版匹配方法是将机器人当前状态与过去经历相比较,找到最接近的状态,修改这一状态下的路径,便可得到一条新的路径[2,3].即首先利用路径规划所用到的或已产生的信息建立一个模版库,库中的任一模版包含每一次规划的环境信息和路径信息,这些模版可通过特定的索引取得;随后将当前规划任务和环境信息与模版库中的模版进行匹配,以寻找出一 收稿日期:2009-08-30；修回日期:2009-11-18. 基金项目:国家自然科学基金项目(50775136)；高校博士点基金项目(20093121110001)；上海市教委科研创新项目(10ZZ97). 作者简介:朱大奇(1964?),男,安徽安庆人,教授,博士生导师,从事水下机器人可靠性与路径规划等研究；颜明重(1977?),男,福建泉州人,博士生,从事水下机器人路径规划的研究.
MATLAB 实现基于蚁群算法的机器人路径规划 1、问题描述 移动机器人路径规划是机器人学的一个重要研究领域。它要求机器人依据某个或某些优化原则（如最小能量消耗，最短行走路线，最短行走时间等），在其工作空间中找到一条从起 始状态到目标状态的能避开障碍物的最优路径。机器人路径规划问题可以建模为一个有约束的优化问题，都要完成路径规划、定位和避障等任务。 2 算法理论 蚁群算法（Ant Colony Algorithm ，ACA ），最初是由意大利学者Dorigo M. 博士于1991 年首次提出，其本质是一个复杂的智能系统，且具有较强的鲁棒性，优良的分布式计算机制等优点。该算法经过十多年的发展，已被广大的科学研究人员应用于各种问题的研究，如旅行商问题，二次规划问题，生产调度问题等。但是算法本身性能的评价等算法理论研究方面进展较慢。 Dorigo 提出了精英蚁群模型（EAS ），在这一模型中信息素更新按照得到当前最优解的蚂蚁所构造的解来进行，但这样的策略往往使进化变得缓慢，并不能取得较好的效果。次年Dorigo 博士给出改进模型（ACS ），文中改进了转移概率模型，并且应用了全局搜索与局部搜索策略，来得进行深度搜索。 Stützle 与Hoos 给出了最大-最小蚂蚁系统（MAX-MINAS ），所谓最大-最小即是为信息素设定上限与下限，设定上限避免搜索陷入局部最优，设定下限鼓励深度搜索。蚂蚁作为一个生物个体其自身的能力是十分有限的，比如蚂蚁个体是没有视觉的，蚂蚁自身体积又是那么渺小，但是由这些能力有限的蚂蚁组成的蚁群却可以做出超越个体蚂蚁能力的超常行为。蚂蚁没有视觉却可以寻觅食物，蚂蚁体积渺小而蚁群却可以搬运比它们个体大十倍甚至百倍的昆虫。这些都说明蚂蚁群体内部的某种机制使得它们具有了群体智能，可以做到蚂蚁个体无法实现的事情。经过生物学家的长时间观察发现，蚂蚁是通过分泌于空间中的信息素进行信息交流，进而实现群体行为的。 下面简要介绍蚁群通过信息素的交流找到最短路径的简化实例。如图2-1 所示，AE 之间有两条路ABCDE 与ABHDE ，其中AB ，DE，HD，HB 的长度为1，BC，CD 长度为0.5，并且，假设路上信息素浓度为0，且各个蚂蚁行进速度相同，单位时间所走的长度为1，每个单位时间内在走过路径上留下的信息素的量也相同。当t=0 时，从A 点，E 点同时各有30 只蚂蚁从该点出发。当t=1，从A 点出发的蚂蚁走到B 点时，由于两条路BH 与BC 上的信息素浓度相同，所以蚂蚁以相同的概率选择BH 与BC ，这样就有15 只蚂蚁选择走BH，有15 只蚂蚁选择走BC 。同样的从E 点出发的蚂蚁走到D 点，分别有15 只蚂蚁选择DH 和DC。当t=2 时，选择BC 与DC 的蚂蚁分别走过了BCD 和DCB ，而选择BH 与DH 的蚂蚁都走到了H 点。所有的蚂蚁都在所走过的路上留下了相同浓度的信息素，那么路径BCD 上的信息素的浓度是路径BHD 上信息素浓度的两倍，这样若再次有蚂蚁选择走BC 和BH 时，或选择走DC 与DH 时，都会以较大的概率选择信息素浓度高的一边。这样的过程反复进行下去，最短的路径上走过的蚂蚁较多，留下的信息素也越多，蚁群这样就可以找到一条较短的路。这就是它们群体智能的体现。 蚁群算法就是模拟蚂蚁觅食过程中可以找到最短的路的行为过程设计的一种仿生算法。在用蚁群算法求解组合优化问题时，首先要将组合优化问题表达成与信息素相关的规范形式，然后各个蚂蚁独立地根据局部的信息素进行决策构造解，并根据解的优劣更新周围的信息素，这样的过程反复的进行即可求出组合优化问题的优化解。 归结蚁群算法有如下特点： （1）分布式计算：各个蚂蚁独立地构造解，当有蚂蚁个体构造的解较差时，并不会影响整体的求解结果。这使得算法具有较强的适应性； （2）自组织性：系统学中自组织性就是系统的组织指令是来自系统的内部。同样的蚁群算法中的各个蚂蚁的决策是根据系统内部信息素的分布进行的。这使得算法具有较强的鲁棒性； （3）正反馈机制与负反馈机制结合：若某部分空间上分布的信息素越多，那么在这个空间上走过的蚂蚁也就越多；走过的蚂蚁越多，在那个空间上留下的信息素也就越多，这就是存在的正反馈机制。但蚁群算法中解的构造是通过计算转移概率实现的，也就是说构造解的时候可以接受退化解，这限制了正反馈机制，
基于栅格法的机器人路径规划快速搜索随机树算法 作者：国海涛， 朱庆保， 徐守江， Guo Haitao， Zhu Qingbao， Xu Shoujiang 作者单位：南京师范大学,数学与计算机科学学院,江苏,南京,210097 刊名： 南京师范大学学报（工程技术版） 英文刊名：JOURNAL OF NANJING NORMAL UNIVERSITY(ENGINEERING AND TECHNOLOGY EDITION) 年，卷(期)：2007，7(2) 被引用次数：6次 参考文献(10条) 1.Nearchou A C Path planning of a mobile robot using genetic heuristics 1998(05) 2.罗熊.樊晓平.易晟具有大量不规则障碍物的环境下机器人路径规划的一种新型遗传算法[期刊论文]-机器人2004(01) 3.孙树栋.林茂基于遗传算法的多移动机器人协调路径规划[期刊论文]-自动化学报 2000(05) 4.D Amico A.Ippoliti G.Longhi S A radial basis function networks approach for the tracking problem of mobile robots 2001 5.Allan R Willms.Simon X Neural network approaches to dynamic collision-free robot trajectory generation 2001(03) 6.Yang S X.Max M An efficient neural network approach to dynamic robot motion planning 2000(02) 7.Karen I Trovato.Leo Dorst Differential A* 2002(06) 8.Bruce J.Veloso M Real-time randomized path planning for robot navigation 2002 9.Peng Cheng.Steven M LaValle Resolution complete rapidly-exploring random trees 2002 10.张美玉.黄翰.郝志峰基于蚁群算法的机器人路径规划[期刊论文]-计算机工程与应用 2005(09) 相似文献(10条) 1.期刊论文杨姗姗.戴学丰.唱江华.YANG Shan-shan.DAI Xue-feng.CHANG Jiang-hua实现机器人动态路径规划的仿真系统-计算机工程与应用2009,45(32) 针对机器人动态路径规划问题,提出了在动态环境中移动机器人的一种路径规划方法,适用于环境中同时存在已知和未知.静止和运动障碍物的复杂情况.采用栅格法建立机器人空间模型,整个系统由全局路径规划和局部避碰规划两部分组成.在全局路径规划中,用快速搜索随机树算法规划出初步全局优化路径,局部避碰规划是在全局优化路径的同时,通过基于滚动窗口的环境探测和碰撞规则,时动态障碍物实施有效的局部避碰策略,从而使机器人安全顺利地到达目的地.仿真实验结果说明该方法具有可行性. 2.学位论文李江抒多移动机器人路径规划算法与导航系统研究2004 本文主要研究了多移动机器人协调系统中的多移动机器人路径规划算法与导航系统。导航系统采用了全局路径规划与局部路径规划算法相结合的方式。全局路径规划采用改进的动态规划算法，将其他机器人位置信息加入机器人路径规划当中。局部路径规划采用人工势场法，使机器人不断朝目标运动的同时避免与环境、障碍物发生碰撞。通过在分布式仿真系统上进行的实验，充分证明了路径规划算法与导航系统适于多移动机器人协调，性能比较好。 本文主要研究了以下内容： 1.构建适合于多移动机器人的导航系统； 2.提出一种适用于多移动机器人的路径规划算法； 3.利用分布式多移动机器人仿真系统验证导航系统与路径规划算法。导航系统采用全局路径规划与局部路径规划算法相结合的方式。导航系统启动后，机器人和服务器建立连接，服务器会读取数据库中的地图信息，将地图信息传送给机器人。机器人先做全局路径规划，从地图信息中提取出拓扑图，结合地图信息中的数据，搜索最优路径，完成全局路径规划。全局路径规划的结果是由道路，站组成的一条全局路径。机器人在每段道路中进行局部路径规划算法，在朝局部目标点运动的同时，要与墙壁保持安全距离，并且要避免与其他机器人相撞。每到达一个局部目标点，机器人就朝终点接近一步，并最终完成服务器给定的任务。在导航系统中，全局路径规划给机器人全局的指导，目标明确，避免了仅用局部路径规划时造成的机器人运动的盲目性。同时又发扬了局部路径规划的优势，具有良好的实时性，避免碰撞。 在导航系统中，全局路径规划采用改进动态规划算法。改进动态规划算法是在传统的动态规划算法的基础上，加入机器人的位置信息作为道路的动态权重，从而产生了适用于多机器人的路径规划算法。机器人在做路径规划时，当一条道路被多个机器人占用，随着机器人数量的增加，道路的权重也会增加，达到一定数量时，机器人就自然选择那些在道路的长度上略长，但机器人数量较少的道路，从而有效改善了道路的状况，使整个系统运行更顺畅。改进动态规划算法的复杂度为0(n)，搜索效率高，但计算量却没有明显增加。 同时，机器人还设有十字路口检测模块，在遇到一条道路有多个出口时，就由该点到目标点再次做全局路径规划，保证机器人选择最优路径。 局部路径规划采用人工势场法。人工势场实际上是对机器人运行环境的一种抽象描述，目标点对机器人产生引力，环境中的障碍物和其他机器人产生斥力，最后根据引力和斥力的合力来决定机器人的运动方向，使机器人绕过障碍物的同时朝目标前进。应用人工势场法规划出来的路径比较平滑、安全，在数学描述上简洁、使用方便。在多移动机器人协调系统中，解决机器人之间的碰撞是一个非常关键的技术，人工势场法完全满足多移动机器人系统对局部路径规划算法的要求。 最后利用分布式多移动机器人仿真系统验证多移动机器人导航系统与路径规划算法。
机器人路径规划 摘要：机器人路径规划是机器人技术的重要分支之一，路径规划技术的研究是研究机器人技术不可或缺的技术之一。本文首先介绍了当前研究人员热衷的ROS 系统是如何进行路径规划的，接着论述了作为群智能算法的蚁群算法应用于机器人的路径规划中。研究表明，可以将蚁群算法和ROS系统结合，进一步的进行机器人的路径规划。 关键词：路径规划，ROS系统，蚁群算法，机器人 1.引言 智能移动机器人技术是机器人技术的重要组成部分，应用前景十分广阔：工业，农业，国防，医疗，以及服务业等[1]。文献提出，未来数年内，中国服务机器人发展将超过传统的工业机器人[2]，机器人路径规划技术是服务机器人研究的核心内容之一[3]。可见，研究机器人的路径规划问题十分必要。 随着机器人领域的快速发展和复杂化，代码的复用性和模块化的需求原来越强烈，而已有的开源机器人系统又不能很好的适应需求。2010年Willow Garage 公司发布了开源机器人操作系统ROS（robot operating system），很快在机器人研究领域展开了学习和使用ROS的热潮。ROS系统是起源于2007年斯坦福大学人工智能实验室的项目与机器人技术公司Willow Garage的个人机器人项目（Personal Robots Program）之间的合作，2008年之后就由Willow Garage来进行推动。ROS的运行架构是一种使用ROS通信模块实现模块间P2P的松耦合的网络连接的处理架构，它执行若干种类型的通讯，包括基于服务的同步RPC（远程过程调用）通讯、基于Topic的异步数据流通讯，还有参数服务器上的数据存储。ROS系统以其独特优点引起了研究人员的兴趣。 近年来，各国学者致力于机器人路径规划的研究且取得了相当丰硕的研究成果。目前已有多种算法用于规划机器人的路径，文献【4】将其主要分为经典方
最优路径规划算法设计 一、 问题概述 兵力机动模型的功能是支持实施机动的实体按照指定路线，由作战空间的一点向另外一点的位置移动，并带入实体在移动过程中发生变化的状态信息。 兵力机动模型包括行军模型、战斗转移模型、机动能力评估模型。涉及的关键算法包括最优路径规划、行军长径计算、行军时间计算、行军所需油料计算、行军方案评估与优选等。 最优路径问题又称最短路问题。是网络优化中的基本问题，如TSP 问题等。下面先举例说明该问题。 最短路问题（SPP －shortest path problem ） 一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地。从甲地到乙地的公路网纵横交错，因此有多种行车路线，这名司机应选择哪条线路呢？假设货柜车的运行速度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地的最短路。 旅行商问题（TSP －traveling salesman problem ） 一名推销员准备前往若干城市推销产品。如何为他（她）设计一条最短的旅行路线（从驻地出发，经过每个城市恰好一次，最后返回驻地？） 最短路问题是组合优化中的经典问题，它是通过数学方法寻找离散时间的最优编排、分组、次序、或筛选等，这类问题可用数学模型描述为 min )(x f ..t s 0)(≥x g D x ∈. 其中，)(x f 为目标函数，)(x g 为约束函数，x 为决策变量，D 表示有限个点组成的集合。 一个组合最优化问题可用三个参数),,(f F D 表示，其中D 表示决策变量的定义域，F 表示可行解区域}0)(,|{≥∈=x g D x x F ，F 中的任何一个元素称为该问
题的可行解，f 表示目标函数，满足}|)(m in{)(*F x x f x f ∈=的可行解*x 称为该问题的最优解。组合最优化的特点是可行解集合为有限点集。由直观可知，只要将D 中有限个点逐一判别是否满足0)(≥x g 的约束并比较目标值的大小，就可以得到该问题的最优解。 以上述TSP 问题为例，具体阐述组合优化问题： 此模型研究对称TSP 问题,一个商人欲到n 个城市推销产品，两个城市i 和j 之间的距离ji ij d d =，用数学模型描述为 ∑≠j i ij ij x d min 1..1 =∑=n j ij x t s n i ,,2,1Λ=， 1..1 =∑=n i ij x t s n j ,,2,1Λ=， },,,2,1{,2||2,1||,n s n s s x s j i ij Λ?-≤≤-≤∑∈ j i n j i x ij ≠=∈,,,2,1,},1,0{Λ 约束条件决策变量1=ij x 表示商人行走的路线包含从城市i 到j 的路，而0=ij x 表示商人没有选择走这条路；j i ≠的约束可以减少变量的个数，使得模型中共有 )1(-?n n 个决策变量。 每一个组合优化问题都可以通过完全枚举的方法求得最优解。枚举是以时间为代价的，在TSP 问题中，用n 个城市的一个排列表示商人按这个排列序推销并返回起点。若固定一个城市为起终点，则需要)!1(-n 个枚举。以计算机s 1可以完成24个城市所有路径枚举为单位，则25个城市的计算时间为：以第1个城市为起点，第2个到达城市有可能是第2个、第3个、……、第25个城市。决定前两个城市的顺序后，余下是23个城市的所有排列，枚举这23个城市的排列需要s 1，所以，25个城市的枚举需要24s 。类似地归纳，城市数与计算时间的关系如表1所示。
I SSN C N 1 0 - 0 2 - 3 4 9 / 5 6 实验技术与管理 第27卷第12期201年1 2月 1 1 2 0 4 T E x p e r i m e n t a l T e c h n o l o g ya n d Ma n a g e m e n t Vo l .27N o .12D e c .201 基于路径规划的智能机器人控制实验 张佳,陈杰,窦丽华 ( 北京理工大学自动化学院,北京1081) 摘 验教学平台。在此平台上设计并开发了分别适用于本科生及硕士研究生的系列实验 规划、全区域覆盖路径规划以及多机器人队形控制等项实验内容。该实验能够让学生接触到先进的智能机 器人增强学生对自动化专业的学习兴趣提高了学生的动手能力和创新能力。 关键词智能机器人路径规划全区域覆盖队形控制 文献标志码文章编号 要 : 针对自动化专业学生 , 以 P i o n e e r 3 A T 系列的机器人为对象 , 搭建了基于路径规划的智能机器人实 , , 包括基于模型的路径 3 , , : ; ; ; 中图分类号 : T P 2 4 2 3 3 : A : 1 0 0 2 4 9 5 6 ( 2 0 1 0 ) 1 2 0 0 4 4 0 4 I n t e l l i g e n t r o b o t c o n t r o l e x p e r i m e n t s b as e d o n p a t h p l a n n i n g Zha n g J i a , Ch e n J i e , D o uL i hua ( S c h o o l o f A u t o m r a t i za t i o n , B e i e j i n g I n s t i t u t e o f T e c h n o l o g y , B e i j i r n g 1 0 0 0 8 1 r , Ch i n a ) A b s t r a c t : A i e m t i n g a t s t r ud e n n n i T t m o t t t s o f au t o e m a t i za m t e i o n m a j o r i , t h p i s p a p e m r t ak e s r o b n o o t s o r o f P i o n e e n 3 A T S e r i n e e sas o b p j e c t t a n d m c o n s t r u c sa n i x n t e l l i m g e o b o t x p o e r o e i n n t t o e a c h n e g l a t f o r , b as e d o p a t h p l a n t n i g .Bas ud e d e o n t h i s l a f o r b , as e r n i s e o x f p e p t e i e swh i c ha p p i n t d t u n d r p g r adua t i e t s c t ud e n t sa n d g adua e s t e n t s r g s p c t i v e l l ya r o n e d e s t i g n e da d l o e i r e m d. I t t n c l ud e s m d e l b as e d r p a t h p l p a o n n i n g o m p l t e t e c n v e a g e p a t h p t l a n n i n a e d m u l t c i r e b o f t o r m a t i e o n e x n p i e n . h e e x p e r i m t o f f e sa n o r t u n y f o r s ud e t s t w o r kw i hadva n c d i n t t e l i g t r b K o o s . I t n ha c e ss t t ud e n i s i n t e r e s t s t o l e a r n au t o m a t i za t i o n m a j o r . A l s o , s t ud e n t s i n n o va t i o n a b i l i y o u l d e i m p r o v e d b y e t h e e x p e o r e n t p . e y w o r d s : i n t l l i g e n r b t ; a t h p l a n n i n g ; c o m p l e t e c o v e r a g e ; f o r m a t i o n 自动化技术是一门涉及学科较多、应用广泛的综 1 实验平台的搭（智械科技） 合性科学技术。实验教学是自动化专业教学过程中 [1] 非常重要的一环。随着目前机器人技术的不断发展, 本课程选用的机器人是美国先锋(P i o n e r 3A T ) 系列机器人[。该系列机器人是目前世界上最成熟的 4] 机器人控制实验已逐步进入各个高校。机器人教学对 于培养和提高学生的创新精神和动手能力具有极其重 轮式移动机器人研究平台之一。通常科研人员对此系 要的作用[。在自动化专业开设机器人控制实验课 2 ] 列机器人的开发与研究都在控制台程序上运行,但需 要对v M a 机器人技术应用接口a 有较 深的了解因此需要花费大量时间阅读繁多的程序代 熟悉研究环境。由于实验学时有限为了能让学生 在最短的时间内最大程度地掌握机器人的有关知识 首先搭建了一个简单实用的实验平台。该平台的建立 能使学生在最短时间内熟悉各种底层动作在实验课 程中掌握基础理论和系统深入的专门知识。 整个平台系统包括个功能模块用户操作管理 模块、通信模块、控制模块、数据分析处理模块和显示 程, 不仅可以让学生接触到国际先进的机器人们的眼界还可以让学生学习先进的控制方法 些方法运用于机器人的实际控制上 提高学生的创新能力和动手能力 域的继续发展奠定坚实的基础。为此 重点实验室项目中购买了数台机器人 , , 开阔他 并将这 A c t i e d i A r i , , ,扩展他们的思维 , 码, , [ 3 ] , 为将来在控制领 , , 本校在北京市 , 针对自动化专 , 业的教学内容及要求,开设了机器人控制实验,取得了 良好的教学效果。 5 : 收稿日期 : 2 0 0 9 1 2 2 1 修改日期 : 2 0 1 0 0 3 1 5 管理模块。各模块所组成的功能结构如图 们之间通过数据信号和控制信号联系在一起 个统一的整体。在控制模块中为学生的实验操作 1 所示,它 基金项目 : 北京市教育委员会共建重点实验室资助项目 (CSYS ,构成一 1 0 0 0 (7 0417) 作者简介 : 张佳 1 9 8 0 ) , 女 ,北京市人 , 硕士 ,实验师 , 研究方向为机器 [ 5 ] , 人控制、智能控制和图像处理.