２０１５年第５期 第１４卷（总第８Ｏ期） 商丘职业技术学院学报 ＪＯＵＲＮＡＬ ＯＦ ＳＨＡＮＧＱＩＵ Ｖ０ＣＡＴＩＯＮＡＬ ＡＮＤ ＴＥＣＨＮＩＣＡｌ ＣＯＬＬＥＧＥ Ｖｏ１．１４，Ｎｏ．５ Ｏｃｔ．，２Ｏ１５ 文章编号：１６７１—８１２７（２０１５）０５ ００２５—０４ 基于融合算法的移动机器人路径规划技术 魏先勇，马 黎 （商丘职业技术学院，河南商丘４７６０００） 摘要：为了解决障碍物附近目标不可到达目的地问题，提出了一种融合算法用于移动机器人路径规划．融合 算法对人工势场进行了改进，构造了新斥力势场函数，引人了指数因子，平衡了障碍物的斥力，从而消除了奇异值 点，使机器人到达了目标点．然后利用量子遗传算法对最优或次优个体进行选择，为最优或次优个体进入下一代移 动机器人提供了保障，提高了安全性、实现了路径的优化．仿真结果表明，融合算法能有效地提高路径规划的性能． 关键词：势场法；路径规划；移动机器人；量子遗传算法 中图分类号：ＴＰ２４ 文献标识码：Ａ 移动机器人路径规划技术是人工智能学和机器人相结合的产物，而移动机器人路径规划技术是一种带 约束条件比较复杂的优化问题［１ｌＪ】 人口］】 ．国内外许多著名的学者都在这方面进行过深入的研究，提出了许多 合理有效的方法，比如ＳｔｅｎｔｚＡ的Ｄ＊算法、遗传算法、滚动路径规划法、人工势场法等 ｌ９ ．Ｋｏ Ｎ Ｙ等 ∞。提出了一种改进的人工势场法，对斥力势函数进行改造，引入了障碍物的速度参量，取得了良好 的效果．但是，该算法的两个假设与实际的动态环境有所不同，对于动态环境中的路径规划问题，机器人避 障相关的主要问题是移动机器人与障碍物之间的相对位置和相对速度，而非绝对位置和绝对速度．对此， Ｇｅｓｓ等人 【６ 。。对一般的人工势场函数进行了改进，在引力函数势场中引用移动机器人与目标点的相对 位置和相对速度，在斥力场函数中引人机器人与障碍物的相对位置和相对速度，找出在动态环境下移动机 器人的路径规划算法，得出较优的仿真与实验结果． １ 改进的人工势场法 人工势场法将机器人看作质点，并且使机器人同时受到斥力和引力的作用．机器人距离障碍物越近斥 力越大；相反，引力场函数与目标点的位置有关，且机器人距离目标点越远引力越大．中人工势场表示如下： Ｕ 。 一Ｕ， 。＋Ｕ （１） 式中：Ｕ 。 为总势场，己， 为斥力场，Ｌ， 为引力场．势场中的力表示为： Ｆ 一Ｆ， ＋Ｆ （２） 式中：Ｆ 为合力，Ｆ 为斥力，Ｆ 为引力，其中： Ｆ ｐ一一 ｄ（Ｕ ）一一『 ＯＵ，ｅｐＨ ３Ｕｒｅｐ ７．＋ ］ Ｆ 一一 ｄ（Ｕ ）一一『３ Ｕ￣ｔ，ｉ＋ ＯＵａｔｔ．＋ （３） （４） 根据式（３）和式（４）分析得到，机器人工作环境中引力势场为全局性的，斥力场为局部性的，如果障碍物 与机器人的距离超出Ｐ。时己， 为０；如果目标在障碍物的附近且机器人向目标运动，则引力越来越小，斥力 越来越大当Ｆ 一０，陷入局部最小．机器人将会出现停滞不前或在障碍物前振荡的状态，障碍物越多出现 局部最小的概率就越大．ＧＮＲＯＮ问题存在的根本原因是总势场函数的最小值不在目标点．为了解决这个问 题我们构造了一个新的斥力场函数如下： 一ｊ丢（志【０， ～ ）Ｐ ｒ＇Ｘ—ｆ）， （ Ｘ ）≤Ｐ。 ｉｆｐ（Ｘ ，Ｘ。 ）＞Ｐｏ （５） 收稿日期：２Ｏ１５—０８—０６ 作者简介：魏先勇（１９７９一），男，河南宁陵人，商丘职业技术学院讲师，硕士，主要从事计算机网络安全、信息安全、智能计算研究。 ・ ２５ ・ 商丘职业技术学院学报 式中：ｌＤ（Ｘ ，Ｘ幽）是机器人与障碍物之间的最小距离，』Ｄ（ｘ ，Ｘ ）是机器人与目标点之间的距离，＂是根 据情况设置的参数．由式（５）可知，当出现局部最小时，需改造引力场，式（６）为改造的斥力场函数： Ｆ 一一Ｖ己， 一｛ ＋６Ｆ ” ：： ：；萋： １、Ｐ （Ｘ，，Ｘ ） ｐｏ／．０ （Ｘ，，Ｘ幽） ｐ ｃｅ （７） （８） 其中 Ｆ ｒ￣ｐｌ一（ ｚ一号（ —： ＿ｌ） Ｐ 一 ｃｘ ，ｘ 。。 ，●●●●●～●●２ ●，—、 ● ●●●Ｌ —一／ ａ是从障碍物到机器人的单位向量，ｂ是从机器人到目标点的单位向量．根据式（５）分析，当ｎ＝：：０时，式（６）退 化为： （ｘ ｒ’ｘ幽）≤ＩＤ。 （Ｘ，，Ｘ幽）＞ｐｏ （９） 因此，必须根据环境的变化选择参数 ，且ｎ＞Ｏ． ２ 改进的量子遗传算法 ２．１量子比特编码 算法采用量子比特进行编码，一个量子比特有。或１两个状态，如式（１Ｏ）： ｌ ＞一ａ ｌ ｏ）＋ ｌ １＞ 而ａ、 是相应状态时出现概率的两个复数，并且 （１０） ｌ ａ Ｉ ＋ｌ Ｉ。一１ ｌｌ 和｛ｐ ｌ。分别为量子比特在状态０和状态１的概率． ２．２ 量子遗传算法自适应调整策略 （１１） 量子状态的转移是量子门通过变换矩阵实现的．用量子旋转门的旋转角度来表示量子染色体的加快收 敛速度．量子旋转门的调整操作如下： ｕ（ ）一Ｕ（ ）一Ｉ『 。ｓ‘ 一ｓｉｎ‘ ］ｌ Ｌｓｉｎ（ ） ＣＯＳ（ ） ＿Ｊ （１２） ： ］一ｕｃ臼 ・ ］一［ ；－－ 。ｓｉ ｎ （Ｏ ’］・ ｉ］ 其中Ｉ ， Ｊ为染色体中的第ｉ个量子位，旋转角为： Ｏｉ一５（ａ ， ）△ ｃ ３ （１４） ０ 一ｓ（ａ ， ）和△ 分别代表旋转的方向和角度，其中△ 的取值在０．１ ７ｃ～０．Ｏ０５ｎ之间．本文主要采用自适 应调整对其进行调整．自适应调整主要是考虑个体当前测量值的适应度厂（ｚ ）与该个体当前目标值的适应 度ｆ（ｂ ）两个因素，如果（ｆＣｒ ）－－ｆ（ｂ ））／ｆ（６ ）＜阈值（根据实际的优化问题确定），当接近最优解的个体 出现时，则减小△ 的值，加快收敛速度；（厂（Ｊｃ ）一ｆ（６ ））／ｆ（６ ）＞阈值，解群中的个体就会适应度不佳， 则会增加ＡＯ 的值，使解群偏离局部最优解或者使得产生最优解的机会加大． ２．３路径适应度评价 安全性和路径代价是评价路径优劣考虑的两个主要因素．本文采用了两个不同的适应度函数对路径进 行评价． ｆ（ｘ ）一∑ｆ ∽ ｆ ‘ 一ｆｌｕ＋ｙ （１５） （１６） 式中： 、），为加权调整系数． 商丘职业技术学院学报 ２０１５正 ４ 结论 本文提出的是一种基于融合算法的移动机器人路径规划技术，是利用改进的人工势场法对移动机器人 进行实时控制，可以平衡障碍物的斥力，因而消除奇异值点，使得机器人到达目标点．通过量子遗传算法对最 优或次优个体进行选择，为最优或次优个体进入下一代提供了保障，实现了路径的优化和安全性的提高．仿 真结果表明了融合算法的有效性． 参考文献： ［１］刘春阳，程亿强，柳长安．基于改进势场法的移动机器人避障路径规划［Ｊ］．东南大学学报，２００８，３９（增刊）． ［２］ＫＨＡＴＩＢ Ｏ．Ｒｅａｌ—ｔｉｍｅ ｏｂｓｔａｃｌｅ ａｖｏｉｄａｎｃｅ ｆｏｒ ｍａｎｉｐｕｌａｔｏｒｓ ａｎｄ ｍｏｂｉｌｅ ｒｏｂｏｔ［Ｊ］．Ｉｎｔ Ｊ ｏｆ Ｒｏｂｏｔｉｃ Ｒｅｓｅａｒｃｈ，１９８６，５（１）． ［３］Ｋｏ Ｎ Ｙ，Ｌｅｅ Ｂ Ｈ．Ａｖｏｉｄ ａｂｉｌｉｔｙ ｍｅａｓｕｒｅ ｉｎ ｍｏｖｉｎｇ ｏｂｓｔａｃｌｅ ａｖｏｉｄａｎｃｅ ｐｒｏｂｌｅｍ ａｎｄ ｉｔｓ ｕｓｅ ｆｏｒ ｒｏｂｏｔ ｍｏｔｉｏｎ ｐ１ａｎｎｉｎｇ［Ｊ］．ＩＥＥＥ Ｉｎｔ Ｃｏｎｆ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｒｏｂｏｔｓ ａｎｄ Ｓｙｓｔｅｍ．Ｏｓａｋａ，１９９６． ［４］Ｇｅ Ｓ Ｓ，Ｃｕｉ Ｙ Ｊ．Ｎｅｗ ｐｏｔｅｎｔｉａｌ ｆｕｎｃｔｉｏｎｓ ｆｏｒ ｍｏｂｉｌｅ ｒｏｂｏｔ ｐａｔｈ ｐｌａｎｎｉｎｇ［Ｊ］．ＩＥＥＥ Ｔｒａｎｓ ｏｎ Ｒｏｂｏｔｉｃ Ａｕｔｏｍａｔｉｏｎ，２０００，１６（５）． ［责任编辑Ｍｏｂｉｌｅ Ｒｏｂｏｔ Ｐａｔｈ Ｐｌａｎｎｉｎｇ Ｔｅｃｈｎｏｌｏｇｙ Ｂａｓｅｄ ｏｎ ａ Ｆｕｓｉｏｎ Ａｌｇｏｒｉｔｈｍ 冰竹］ ＷＥＩ Ｘｉａｎｙｏｎｇ．ＭＡ Ｉ ｉ （Ｓｈａｎｇｑｉｕ Ｐｏｌｙｔｅｃｈｎｉｃ，Ｓｈａｎｇｑｉｕ ４７６０００，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｉｎ ｏｒｄｅｒ ｔｏ ｓｏｌｖｅ ｇｏａｌｓ ｎｏｎ—ｒｅａｃｈａｂｌｅ ｗｉｔｈ ｏｂｓｔａｃｌｅｓ ｎｅａｒｂｙ（ＧＮＲＯＮ），ａ ｎｏｖｅｌ ｔｅｃｈｎｏｌｏｇｙ ｏｆ ｍｏｂｉｌｅ ｒｏｂｏｔ ｐａｔｈ ｐｌａｎｎｉｎｇ ｂａｓｅｄ ｏｎ ａ ｆｕｓｉｏｎ ａｌｇｏｒｉｔｈｍ ｉｓ ｐｒｏｐｏｓｅｄ．Ａ ｎｅｗ ｐｏｔｅｎｔｉａｌ ｆｉｅｌｄ ｆｕｎｃｔｉｏｎ ｉｓ ｐｒｅｓｅｎｔｅｄ ｂｙ ａｄｄｉｎｇ ａｎ ｅｘｐｏｎｅｎｔｉａｌ ｆａｃｔｏｒ ｔｏ ｔｈｅ ｒｅｐｕｌｓｉｖｅ ｐｏｔｅｎｔｉａｌ ｆｕｎｃｔｉｏｎｓ， ｉｔ ｃａｌｌ ｂａｌａｎｃｅ ｔｈｅ ｒｅｐｕｌｓｉｖｅ ｆｏｒｃｅ ｏｆ ｏｂｓｔａｃｌｅｓ ａｎｄ ｅｌｉｍｉｎａｔｅ ｓｉｎｇｕｌａｒｉｔｙ ｉｎ ｐｌａｎｎｉｎｇ，ａｎｄ ｔｈｅ ｒｏｂｏｔ ｃａｎ ｇｅｔ ｔｏ ｔｈｅ ｇｏａ１．ＱＧＡ ｉｓ ｕｓｅｄ ｔｏ ｓｅｌｅｃｔ ｔｈｅ ｏｐｔｉｍａｌ ｏｒ ｓｕｂ—ｏｐｔｉｍａｌ ｐａｔｈ ｉｎ ｏｒｄｅｒ ｔｏ ｐｒｏｔｅｃｔ ｔｈｅ ｏｐｔｉｍａｌ ｏｒ ｓｕｂ—ｏｐｔｉｍａｌ ｐａｔｈ ｉｎｔｏ ｔｈｅ ｎｅｘｔ ｇｅｎｅｒａｔｉｏｎ，ａｎｄ ｏｐｔｉｍｉｚａｔｉｏｎ ｏｆ ｔｈｅ ｒｏｕｔｅ ｌｅｎｇｔｈ ａｎｄ ｓａｆｅｔｙ ａｒｅ ｒｅａｌｉｚｅｄ．Ｓｉｍｕｌａｔｉｏｎ ｒｅｓｕｌｔ ｓｈｏｗｓ ｔｈａｔ ｔｈｅ ｐｒｏｐｏｓｅｄ ｍｅｔｈｏｄ ｃａｎ ｅｆｆｅｃｔｉｖｅｌｙ ｉｍｐｒｏｖｅ ｔｈｅ ｐｅｒｆｏｒｍａｎｃｅ ｏｆ ｐａｔｈ ｐｌａｎｎｉｎｇ． Ｋｅｙ ｗｏｒｄｓ：ｐｏｔｅｎｔｉａｌ ｆｉｅｌｄ；ｐａｔｈ Ｐｌａｎｎｉｎｇ；ｍｏｂｉｌｅ ｒｏｂｏｔ；ｑｕａｎｔｕｍ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ（ＱＧＡ） ・ ２８ ・
