移动机器人局部避障路径规划仿真研究

第３５卷第７期　计算机仿真　２０１８年７月　文章编号：１００６—９３４８（２０１８）０７—０２７９—０６　

移动机器人局部避障路径规划仿真研究　

宋莉，李彩虹，王小宇，张宁　（山东理工大学计算机科学与技术学院，山东淄博２５５０４９）　摘要：研究复杂环境下基于Ｑ—Ｌｅａｒｎｉｎｇ（ＱＬ）算法的移动机器人局部路径规划问题，快速、准确地完成避障路径规划。为了　解决ＱＬ算法收敛速度慢、探索与利用两难及危险区域等问题，提出了一种基于ＱＬ一模糊的移动机器人局部避障路径规划方　法。首先为了加快ＱＬ算法的收敛速度，根据规划问题设计状态动作变量，对其进行离散化处理，降低状态空间维度；在Ｑ　矩阵的基础上．设计更新步长算法，使Ｑ矩阵的更新程度不断减弱。然后根据机器人工作环境和规划目标，在设计奖惩函数　的基础上，设计ｅ一探索与利用平衡策略和动作选择算法来选择执行动作，平衡探索与利用问题。为了预防死锁问题，在模　糊控制规则中还设计了预防方案，以提高路径规划效率。算法进行了仿真验证。仿真结果表明，即使在复杂的环境中，机器　人仍能有效避障．规划出最优或次优路径。　关键词：移动机器人；局部路径规划；模糊控制；探索与利用平衡策略　中图分类号：ＴＰ２４２　文献标识码：Ｂ　

Ｓｉｍｕｌａｔｉｏｎ　Ｒｅｓｅａｒｃｈ　ｏｎ　Ｌｏｃａｌ　Ｏｂｓｔａｃｌｅ　Ａｖｏｉｄａｎｃｅ　Ｐａｔｈ　Ｐｌａｎｎｉｎｇ　ｆｏｒ　Ｍｏｂｉｌｅ　Ｒｏｂｏｔ　

ＳＯＮＧ　Ｌｉ，ＬＩ　Ｃａｉ－ｈｏｎｇ，ＷＡＮＧ　Ｘｉａｏ－ｙｕ，ＺＨＡＮＧ　Ｎｉｎｇ　（Ｓｃｈｏｏｌ　ｏｆ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ，Ｓｈａｎｄｏｎｇ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｔｅｃｈｎｏｌｏｇｙ，Ｚｉｂｏ　Ｓｈａｎｄｏｎｇ　２５５０４９，Ｃｈｉｎａ）　

ＡＢＳＴＲＡＣＴ：Ｔｈｅ　ｍｏｂｉｌｅ　ｒｏｂｏｔ　ｐａｔｈ　ｐｌａｎｎｉｎｇ　ｂａｓｅｄ　ｏｎ　ＱＬ　ａｌｇｏｒｉｔｈｍ　ｉｎ　ｔｈｅ　ｃｏｍｐｌｅｘ　ｅｎｖｉｒｏｎｍｅｎｔ　ｉｓ　ｓｔｕｄｉｅｄ　ｔｏ　ｆａｓｔ　ａｎｄ　ａｃｃｕｒａｔｅｌｙ　ｃｏｍｐｌｅｔｅ　ｏｂｓｔａｃｌｅ　ａｖｏｉｄａｎｃｅ　ａｎｄ　ｐａｔｈ　ｐｌａｎｎｉｎｇ．Ｔｈｉｓ　ｐａｐｅｒ　ｐｒｏｐｏｓｅｓ　ａ　ｌｏｃａｌ　ｏｂｓｔａｃｌｅ　ａｖｏｉｄａｎｃｅ　ｐａｔｈ　ｐｌａｎｎｉｎｇ　ｍｅｔｈｏｄ　ｆｏｒ　ｔｈｅ　ｍｏｂｉｌｅ　ｒｏｂｏｔ　ｂａｓｅｄ　ｏｎ　ｔｈｅ　ＱＬ－ｆｕｚｚｙ　ａｌｇｏｒｉｔｈｍ　ｔｏ　ｓｏｌｖｅ　ｔｈｅ　ｃｏｎｌｉｎｏｎ　ｐｒｏｂｌｅｍｓ　ｅｘｉｓｔｅｄ　ｉｎ　ｔｈｅ　ｔｒａｄｉｔｉｏｎａｌ　ｍｅｔｈｏｄ，ｓｕｃｈ　ａｓ　ｔｈｅ　ｓｌｏｗ　ｃｏｎｖｅｒｇｅｎｃｅ　ｒａｔｅ，ｂａｌａｎｃｅ　ｏｆ　ｔｈｅ　ｄｉｌｅｍｍａ　ｂｅｔｗｅｅｎ　ｅｘｐｌｏｒａｔｉｏｎ　ａｎｄ　ｅｘｐｌｏｉｔａｔｉｏｎ，　ａｎｄ　ａｖｏｉｄａｎｃｅ　ｏｆ　ｔｈｅ　ｈａｚａｒｄｏｕｓ　ｒｕｎｎｉｎｇ　ａｒｅａｓ．Ｆｉｒｓｄｙ，ｆｏｒ　ｉｍｐｒｏｖｉｎｇ　ｔｈｅ　ｃｏｎｖｅｒｇｅｎｃｅ　ｏｆ　ＱＬ，ｔｈｅ　ｖａｒｉａｂｌｅｓ　ｏｆ　ｓｔａｔｅ　ａｎｄ　ａｃｔｉｏｎ　ｗｅｒｅ　ｄｅｓｉｇｎｅｄ　ａｎｄ　ｆｕｚｚｅｄ　ｔｏ　ｒｅｄｕｃｅ　ｔｈｅ　ｄｉｍｅｎｓｉｏｎ　ｏｆ　ｔｈｅ　ｓｔａｔｅ　ｓｐａｃｅ　ａｃｃｏｒｄｉｎｇ　ｔｏ　ｔｈｅ　ｐｌａｎｎｉｎｇ　ｐｒｏｂｌｅｍｓ．Ｔｈｅｎ　ａ　ｖａｒｉａｂｌｅ　ｓｔｅｐ－ｓｉｚｅ　ａｌｇｏｒｉｔｈｍ　Ｗａｓ　ｄｅｓｉｇｎｅｄ　ｔｏ　ｄｅｃｒｅａｓｅ　ｔｈｅ　ｆｒｅｓｈｎｅｓｓ　ｏｆ　ｔｈｅ　ｍａｔｒｉｘ　ｂａｓｅｄ　ｏｎ　ｔｈｅ　Ｑ——ｖａｌｕｅ　ｆｕｎｃｔｉｏｎ　ｍａ－－　ｔｒｉｘ．Ａｄｄｉｔｉｏｎａｌｌｙ，－ｂａｌａｎｃｅ　ｓｔｒａｔｅｇｉｅｓ　ｂｅｔｗｅｅｎ　ｅｘｐｌｏｒａｔｉｏｎ　ａｎｄ　ｅｘｐｌｏｉｔａｔｉｏｎ　ａｎｄ　ｔｈｅ　ｓｅｌｅｃｔｉｏｎ　ａｌｇｏｒｉｔｈｍ　ｏｆ　ａｃｔｉｏｎｓ　ｗｅｒｅ　ｃｏｎｓｔｒｕｃｔｅｄ　ｔｏ　ｓｏｌｖｅ　ｔｈｅ　ｐｒｏｂｌｅｍ　ｏｆ　ｅｘｐｌｏｒａｔｉｏｎ　ａｎｄ　ｅｘｐｌｏｉｔａｔｉｏｎ　ａｃｃｏｒｄｉｎｇ　ｔｏ　ｔｈｅ　ｗｏｒｋ　ｅｎｖｉｒｏｎｍｅｎｔ　ａｎｄ　ｐｌａｎｎｉｎｇ　ｏｂｊｅｃ—　ｔｉｖｅ　ｏｆ　ｒｏｂｏｔ．Ｉｎ　ｏｒｄｅｒ　ｔｏ　ｐｒｅｖｅｎｔ　ｔｈｅ　ｄｅａｄｌｏｃｋ　ｐｒｏｂｌｅｍ，ｔｈｅ　ｐｒｅｖｅｎｔｉｖｅ　ｍｅａｓｕｒｅ　ｗａｓ　ｄｅｓｉｇｎｅｄ　ｔｏ　ｉｍｐｒｏｖｅ　ｔｈｅ　ｅｆｆｉｃｉｅｎｃｙ　ｏｆ　ｔｈｅ　ｐａｔｈ　ｐｌａｎｎｉｎｇ　ｉｎ　ｔｈｅ　ｆｕｚｚｙ　ｃｏｎｔｒｏｌ　ｒｕｌｅｓ．Ｔｈｅ　ｍｅｔｈｏｄ　ｈａｓ　ｂｅｅｎ　ｓｉｍｕｌａｔｅｄ．Ｔｈｅ　ｓｉｍｕｌａｔｅｄ　ｒｅｓｕｌｔｓ　ｓｈｏｗ　ｔｈａｔ　ｔｈｅ　ｒｏｂｏｔ　Ｃａｎ　ｐｌａｎ　ａｎ　ｏｐｔｉｍａｌ　ｏｒ　ｓｕｂｏｐｔｉｍａｌ　ｐａｔｈ　ｗｈｉｌｅ　ａｖｏｉｄｉｎｇ　ｏｂｓｔａｃｌｅｓ，ｅｖｅｎ　ｉｎ　ａ　ｃｏｍｐｌｉｃａｔｅｄ　ｅｎｖｉｒｏｎｍｅｎｔ．　ＫＥＹＷＯＩ￣Ｓ：Ｍｏｂｉｌｅ　ｒｏｂｏｔ；Ｌｏｃａｌ　ｐａｔｈ　ｐｌａｎｎｉｎｇ；Ｆｕｚｚｙ　ｃｏｎｔｒｏｌ；Ｂａｌａｎｃｅ　ｓｔｒａｔｅｇｉｅｓ　ｂｅｔｗｅｅｎ　ｅｘｐｌｏｒａｔｉｏｎ　ａｎｄ　ｅｘｐｌｏｉ－　ｔａｔｉｏｎ　

１　引言　随着智能技术的不断发展。路径规划作为机器人研究领　域的关键技术，成为人们研究的热点。针对局部路径规划问　题，研究者提出了势场法　、模糊控制算法　、神经网络算　

基金项目：国家自然科学基金项目（６１４７３１７９）；山东省自然科学基金　项目（ＺＲ２０１４ＦＭＯ０７）　收稿日期：２０１７—１１—３０修回日期：２０１７—１２—１３　

法＿３］等。但由于缺乏全局信息，研究者无法对机器人出现的　所有行为进行预测。因此机器人能通过与所处的环境进行　交互在线学习。找到从起点到终点的最优策略，成为研究的　重要方向Ｌ４　Ｊ。　ＱＬ算法Ｉ５　是采用离策略方法解决强化学习问题的值迭　代方法。标准的ＱＬ算法存在收敛慢、探索与利用两难等问　题，为此研究者提出了很多解决方案。文献［６］提出了基于　人工势场的强化学习初始化方法，将环境虚拟化为人工势　场，用先验知识确定每点的势能值，定义Ｑ初始值为最大折　

．．．——２７９．．．——　算累积回报。该方法加快了初始阶段收敛速度，但有可能出　现探索与利用问题。文献［７］提出了基于贝叶斯的强化学习　方法，在ＭＡＲＬ用贝叶斯模型来进行最优探测。该方法仅在　理论上找到探索与利用的平衡解，且忽略了收敛问题。文献　［８］提出了贝叶斯与强化学习结合的方法，解决了强化学习　的探索与利用的平衡问题，但将该方法应用到实际环境中出　现的死锁等复杂问题，尚未研究。因此如何解决强化学习存　在的问题，获得最大累积回报和最优控制规则，将人的经验　转化为机器人的计算与推理，是需要解决的重要问题。　基于上述研究现状与不足，本文设计了基于ＱＬ一模糊的　局部避障路径规划方法。采用改进的ＱＬ算法进行学习，获　得最佳状态一动作对（＜ｓ，ａ＞）。然后设计模糊控制器，得出　模糊控制规则。利用模糊算法进行路径规划。另外，还添加　了在特殊环境下预防死锁的规则。以提高规划效率。　２局部避障路径规划系统模型及问题描述　２．１局部避障路径规划系统　局部避障路径规划系统是在有障碍物的环境下，设计输　入输出变量，由ＱＬ算法学习得到最佳＜ｓ，ａ＞，设计模糊控制　器。获得模糊控制规则，规划出从起点到终点的最优或次优　的无碰撞路径。　建立环境模型如图１所示。Ｒｏｂｏｔ为机器人，Ｏｂｓｔａｃｌｅ为　障碍物，Ｇｏａｌ为预定目标。以机器人中心位置Ｒ为原点分别　建立世界坐标系　和机器人坐标系　幽　横纵坐标分别　（　，Ｙ　）为和（　，Ｙ　）。在　中，以机器人的当前移动方向　０　（１　０　ｌ≤１８０。）为Ｙ，轴，机器人与目标点的角度为０　。假　设超声波传感器的探测距离小于等于５ｏ＂（ｏｒ为机器人单步运　行距离）。通过传感器获得三个方向上与最近障碍物的距离　为Ｄｉｓｔａｎｃｅ＝｛ｄ　。，ｄｏ。，ｄ３　。｝，以及探测到的点与Ｙ　轴的夹　角咖。－ＹＲｏ　内的任一点Ｏ　（ｄ，，　）映射到－Ｙｗ　内的坐标　Ｏ　（　Ｙ　，）为　图１环境模型坐标系　ｆｒ　。。　（　ｒ一　’（　：一３６。０。，３６。）（１）●　＼Ｊ　，一　，　，　＼一，　ｔｙ　＝Ｙ　＋ｄｊｓｉｎ（０　一妒）　２．２　问题描述　基于ＱＬ算法路径规划的状态空间维数大，因此导致算　法收敛速度慢。其次在学习过程中，“仅探索”法能估计每　．－－——２８０·－－——　个动作的奖赏，但失去很多选择最优动作的机会；“仅利用”　法则相反，能选择奖赏最大的动作，但失去探索动作的机　会。因此执行当前奖赏最大的动作还是进行动作探索，制约　着最终累积奖赏的最大化．导致探索与利用问题。同时由于　复杂障碍物的存在，会出现死锁问题。　基于上述问题，本文提出基于ＱＬ一模糊的局部避障路　径规划方法。利用改进的ＱＬ算法结合模糊算法，实现复杂　环境的局部避障路径规划。　ｌ－　３　ＱＬ算法　３．１　状态一动作的设计　在算法学习前，首先根据机器人局部路径规划任务，设　计状态变量Ｓ和动作变量ｏ，形成状态一动作对＜ｓ，ａ＞，然　后对变量进行离散化处理。　３．１．１　状态变量的设计及离散化　设计的四个输入状态分别是三个方向上与障碍物的距　离Ｄｉｓｔａｎｃｅ＝｛ｄ　。，ｄｏ。，ｄ　。｝，以及目标相对于机器人的方　向Ｄ。　将Ｄｉｓｔａｎｃｅ＝｛ｄ　。，ｄ０。，ｄ，　。｝设计为输入状态，然后进　行离散化处理。选取安全距离ｄ　。为４　，输入变量的离散化　公式为　

ｄ　＝｛　：　：：　ｃ　＝一ｓ６。，。。，ｓ６。　ｃ２　

当ｄ　为０时，为安全区域；　为１时，为危险区域。　将目标方向Ｄ设置为另一输入状态。方向的角度范围为　［一１８０。，１８０。］。然后进行离散化处理，目标的方向信息０　为　ｆａｒｃｔａｎ（（Ｙｇ—ｙ，）／（　ｇ—　，））　（　ｇ＞　，）　０ｗ　｛ａｒｃｔａｎ（（Ｙｓ—ｙ　）／（　一　））＋丌ｘｇ＜　，ｙｇ≥Ｙ，）　、ａｒｃｔａｎ（（Ｙｓ—ｙ，）／（　ｇ—　，））一仃（　ｇ＜　，Ｙｓ＜Ｙ，）　（３）　若　ｇ＝　，，当Ｙｇ＞　ｇ，０　＝０．５７ｒ；当Ｙｓ＜　ｇ，０　：一　０．５￣ｒ，０≤０　≤仃。　为判断目标的方向。取较小的阈值　＝０．０ｌ７ｒ。根据机　器人当前方向０，与０　的差，判断在目标相对于机器人的方　向，ＡＯ＝０　一０　。判断规则如表１所示。　

表１　目标方向的判断　ＡＯ　目标的方向Ｄ　ｌ／ｔＯ　Ｉ≤∞或Ｉ　ＡＯ　Ｉ≥２丌一∞　一仃＜ＡＯ＜一　或丌＜ＡＯ＜２￣ｒ一　（ｃＪ＜／ｔｏ≤７ｒ或一２７ｒ＋∞＜／ｔｏ≤一７ｒ　正前方（肘）　左方（　）　右方（Ｒ）