论文研究-引入势场及陷阱搜索的强化学习路径规划算法.pdf

所需积分/C币:50 2019-09-07 09:10:45 958KB .PDF
27
收藏 收藏
举报

移动机器人在复杂环境中移动难以得到较优的路径,基于马尔可夫过程的Q学习(Q-learning)算法能通过试错学习取得较优的路径,但这种方法收敛速度慢,迭代次数多,且试错方式无法应用于真实的环境中。在Q-learning算法中加入引力势场作为初始环境先验信息,在其基础上对环境进行陷阱区域逐层搜索,剔除凹形陷阱区域[Q]值迭代,加快了路径规划的收敛速度。同时取消对障碍物的试错学习,使算法在初始状态就能有效避开障碍物,适用于真实环境中直接学习。利用python及pygame模块建立复杂地图,验证加入初始引力势场和陷阱搜索的改进Q-learning算法路径规划效果。仿真实验表明,改进算法能在较少的迭代次数后,快速有效地到达目标位置,且路径较优。
董培方,张志安,梅新虎,等:引入势场及陷阱搜索的强化学习路径规划算法 代,从起始点开始进入下一轮探索。 区,白色为可行区域)建立当前层疑似陷阱长度存储 改进人工势场法 数组 层数存储数组 以及当 人工势场法的基本原理是在目标物周闹产生虚拟前层陷阱个数存储数组 。初始点坐标为 引力势场智能体在任何位置都受到来自目标点的引力a(xy,目标位置的坐标为bx,y)。对栅格地图进行个 吸引而障碍物对移动物体产生排斥力,阻止物体靠近方向的逐层搜索如图为沿X正方向进行层内搜索 产生碰撞 Y正方向进行层级搜索,即沿栅格内数字顺序搜索。 引力势场函数: Ua( g)=kin(g-9e=kine(g) 式屮,km为引力常数:=g-9。是智能体与目标 位置的欧几里他距离。 基于改进引力势场法初始化状态值函数法则 算法是基于马尔科夫决策的无模型强化学习算 法,采用可变§法则,其行为策略是往Q值增 大的方向移动,因此对于初始化状态值凶数表,应满足 距离目标点越近其引力势场越大,与距离成反比(传统 图栅格地图 的引力势场与距离平方成正比),为了保证算法的实时 步骤利用改进人T势场法初始化状态昞数表,距 性,不考虑障碍物的斥力势场,同时减小公式计算复杂窝目标点越近,状态值越大,非障碍物区域状态值大于 度,引入参量L用于调整初始状态值的变化范围: 等于,障碍物区域状态值为-A(A>0),陷阱层数为 Vii (s=L-D(Pirit, Poal) )N,陷阱状态梯度值为G,已标记陷阱区域状态值为: 其中,L≥、ⅹ+Y,X为环境的水平长度,Y为环境 Vuran(Lx, y)=-A+GxN 的垂直长度。 步骤搜索陷阱起始顶点。从坐标原点沿ⅹ正方 DXPm,ol=(a-)+(y2-y)2为起始点和目间进行层内搜索沿Y方向进行层级搜索,每次移动个 标点之间的距离。 栅格,判断当前栅格状态值V([x,γ),左侧栅格状态值 对于复杂环境的 算法路径规划动作状Vx-1,y),上侧栅格状态值V[x,y-1),如果满足: 态空间庞大,迭代速度慢,引入目标点改进引力势场来 [x-1,y]=-A 初始化状态值函数,从而提供初始目标位置,智能体具 V[x,y-1])=-A V[x,y])>0 有目标趋向性,能迅速朝目标方向移动,同时随机策略即当前栅格上侧和左侧均为障碍物,且当前栅格为非障 保证其不陷入局部最优解。 碍物,则认为当前栅格为陷阱区域的起始顶点,将疑似 环境陷阱搜索算法 陷阱标志位置,将当前层疑似陷阱序号加,记录当前 在复杂环境中,常常存在凹形障碍物,对丁人T势坐标,转步骤;否则不做任何处理继续搜索起始顶点。 场法或蚁群算法等易陷入凹形区域,无法到达目标点。 步骤继续沿X右侧移动,判断V(x,y,V([x 基于强化学习算法的路径规划能够通过随机探索策略 y-1]V(x,y+dV([x+1.y若v([x,y-1])>0,则 和策略改进逃离此类障碍物,这种智能行为是高效导航 此处非陷阱区域,置疑似陷阱标志位,返回步骤;若 基础,但规划效率低,只引入引力势场的强化学习算 V(x,y+d|=-A,为防止将可行路径识别为陷阱区域 法由于目标趋向性同样容易陷入与目标相对的凹形障 而变成不可行域,则认为x,y+d]为当前疑似陷阱非 碍物中,需要较多的训练次数才能逃逸,如果能直接将 凹形障碍物从可行的规划路径中剔除,则能提髙规划的相邻暲碍物,取消当前层的疑似陷阱标志位,返回步骤 效率,诚少迭代的次数。 ,其中d为可行路径宽度调节参数。若同时满足: 针对此类障碍物,提出沿x、y方向的陷阱逐层搜 trap _flag=1 V[x,y])>0 索,并把搜索结果作为环境先验信息初始化状态函数表 ([x,y-1])<0 V([x,y+d/)>0 陷阱搜索算法如下: V[x+1,y]>0 步骤将探索环境栅格化,并对障碍物进行膨胀处即当前栅格处于疑似陷阱,累积当前疑似陷阱中的栅格 理,将移动物体()看作质点。以地图某一顶点作长度,根据卜一层V([x,y-1的值来判断当前栅格处 为坐标原点建立直角坐标系(如图所示,黑色为障碍丁陷阱中的位置,然后转步骤 计算机工程与应用 口rr ()陷阱顶点 )层间搜索 ()陷阱确认 ()疑似降阴取消 ●()可行路径判断 ()搜索完成 图栅格地图隋阱搜索流程图 +1 ()阱取消栅格,灰色代表已确认陷阱栅格(d=1)。如图 为陷阱搜索结束后各栅格的状态值,陷阱区域状态值呈 若末能满足上述不等式,则将当前疑似陷阱排除清除现梯度变化 陷阱栅格长度和所处层级位置,清除疑似陷阱标志位 返回步骤。 0|>0|≥0>0}->0>0->0p>0>0|->0>00 步骤当沿着当前层疑似陷阱搜索至另一端顶点 >00A-A-A-A-A-A>00>0}>0≥0≥0 时,即: g-4 4o-A-A-4-4C trap _flag=1 0=0A4+-4+-4+4 A0-A>0|>0≥00 V 0=0-A00>0>0-A>0-A>0 V(x,y])>0 p}>o}A=}90≥0 V([xy+1])>0 soFoFoFopopoFopoFofopopoFoFo 判断H标位置是处于当前层陷阱中,如果否,则记录 陷阱序号、起始顶点坐标及陷阱长度。如果目标位置处 于陷阱当屮,则将当前疑似陷阱排除,清除陷阱栅格长 图栅格地图陷阱搜索完成后状态值 度和所处层级位置,清除疑似陷阱标志位,返冋步骤 初始化完成之后,环境地图状态动作值函数有充 步骤当一层搜索结束时,根据当前层记录的陷阱分的环境先验信息,采取无障碍物试错的贪心策略 个数、陷阱厅号及每个陷阱的长度来更新相应位置的值 回报雨数是智能体移动行为的判断准则,获得回报 函数V,并从y+1层再次进行步骤,直至遍历整个栅越大,则相应的行为策略概率得到提高回报值越小,则 格地图 对应的行为策略概率减小。基于 的常规路径 步骤完成一次遍历之后,再分别沿X正方向进规划把到达H标点的叫报值设为正数,激励朝H标方向 行层内搜索,Y负方向进行层级搜索;沿Y正方向进行移动的行为策略把碰到障碍物的回报值设为负数以惩 层内搜索,X正方向进行层级搜索;沿Y正方向进行层相应的行为。因此,基于此类的路径规划方法是从无 内搜索,X负方向进行层级搜索;经过次栅格癌历,能任何环境认知的状态进行不断的试错,最终收敛Q值 发现不同朝向的凹形陷阱。 查洵表,使智能体以最优的路径达到目标点 步骤更新完所有陷阱区域的状态值函数后,根据 这样的试错策略难以应用到真实的环境中去,对于 当前状态动作对(Sa来更新Q值,即采取动作a后真实的移动机器人如采川无环境先验信息的试错学 所获得的瞬时回报值加上当前状态的最大折扣累积回会个可避免地撞上障碍物直接损坏本体,元法进行 报V(S): 后续实验。因此对状态动作值函数表的更新进行如下 如图所示为示例栅格地图的陷阱找参()假设:当智能体在随机探索下预测动作a的下一个环 Q(S, a=r+yV(S 是,其屮境状态为障碍物直按取对应Q(Sp,a)=-4,并按照 绿色栅格代表疑似陷阱起始顶点,黄色栅格代表疑似陷x(anu)= arg maxI(QS,a)策略进行下一步动作选择, 阱栅格,蓝色代表疑似陷阱结東顶点,红色代表疑似陷由亍规定了可探索环境模型的Q丶S,ω)≥0,每次檢测到 董培方,张志安,梅新虎,等:引入势场及陷阱搜索的强化学习路径规划算法 障碍物后,将其从可探索环境模型中剔除,在避免了障信息的 算法和同时应用引力势场和陷阱搜索 碍物ⅷ撞的同时,减少了可迭代Q值耷询表,能有效加作为环境先验信息的改进 算法进行路径规 快收敛速度,并能应用于真实术知环境中的路径规划,划采用相同的折扣率、学习率和法则,每种方 无需对障碍物设定回报函数值 法进行次迭代,得到最终路径和起始位置到H标 点所需的步数。 仿真实验 通过仿真实验发现,没有任何环境先验信息的强化 采用 编程环境, 模块作为地图绘制学习路径规划在设定的复杂环境地图中无法顺利到达 工具进行未知环境下的复杂地图路径规划算法验证。终点,第次迭代经过 步的移动仍然未能到达 建立地图模型尺寸为 ,最小移动单位为,智能目标点即认为在无环境先验信息且移动路径不能穿越 体动作空间集合A5)包含前进、后退左移、右移、左前障碍物的情况下,基于 的强化学习算法的路 栘、右前移、左后移、右后移个动作,动作空间集A 径规划难以达到日标点,无法完成规划。 越人,对应的路径轨迹越平滑。将地图划分为 其余两组方法均能从起始位置到达目标位置,但加 个网格作为环境状态空间s。以环境地图的左十角为入陷阱搜索去掉了较大范围的路径搜索迭代速度明显 坐标原点,水平方向为X轴,竖直方向为y轴建立坐标快于未加入陷阱搜索的算法,且在初始的若干次迭代过 系,设定起始点和目标点位置如图所示绿点代表初程中,从起始位置到达H标位置所需的步数更少,用时 始点,初始坐标为(,蓝点代表目标位置,日标更快。其部分训练代数路径规划效果如图和图所 坐标为( 示,相同的训练次数图的移动路径优于图所示路径, 基于陷阱搜索的环境先验信息使得智能体在整个训练 (0,0)b100,6C) (800,0 过程中不会移动至陷阱区域,提高了算法的效率。 20 图环境地图起始点与目标点坐标位置示意 在确定起始点和目标点坐标之后,进行引力势场和 陷阱搜索初始化Q值函数,将环境的已知信息更新于 Q值表之中。图所示为进行陷阱搜索之后的环境状 态,其中绿色线条所在区域为陷阱区域,黑色区城为有 效探索空间,相比于初始化之前减小了有效状态空间 其中号、号陷阱至外部障碍物之间的距离d由参数 调节。 (0,0),次100,601 (800,0) 图基于引力势场的强化学习路径规划 将这两种方法的训练次数作为横坐标,每次迭代从 760,210) 起始点到终点所需移动的步数作为纵坐标做图可得这 两种方法的训练速度和训练效果,迭代收敛趋势如图 所示。由图叮知,进行陷阱搜索作为环境先验信息的 路径规划训练效果明显优于未进行陷阱搜索的路径规 (0,5CO) 划,前者收敛速度更快,且在相同的训练次数下得到的 移动路径短于后者,整个训练周期时间更短。 图陷阱区域 为了验证本文提出方案的有效性,在同环境地图 结论 下进行组对比实验,分别采川常规的不带有环境先验 传统强化学丬由于训练速度慢,迭代效率低而难以 信息的 算法、只应用引力势场作为环境先验直接应用。将引力势场和陷阱搜索联合作为环境先验 计算机工程与应用 决策 史久根,刘春霞,席海强模型下的改进路径规划算 电子测量与仪器学报,·() 图于引力势场和陷阱搜索的强化学习路径规划 朱毅张涛,宋靖雁未知环境下势场法路径规划的局部极 未进行陷阱搜索 小问题研究自动化学报, 一初始化进行陷阱搜素 宋勇李贻斌、李彩虹移动机器人路径规划强化学习的初 始化控制理论与应用, 杨溢,厐永杰,李宏伟,等复杂海况下基于强化学习的 迭代次数 局部路径规划方法研究(英文)船舶与海洋上程学 图有无隋阱搜索对路径规划迭代影响趋势图 报:英文版,(): 信息初始化Q值函数的强化学刁路径规划可以得到更 周俊,陈钦,梁泉基于强化学小的衣业移动机器人视觉 导航农业机械学报,,() 快的收敛速度和更优的移动路径,同时利用初始化避免 许亚基于强化学习的移动机器人路径规划研究济 对障碍物的试错探索减少了移动体有效状态空间,在明 南:山东大学 显少于传统强化学习的训练次数情况下达到更好的路 陆军,徐莉,周小平强化学习方法在移动机器人导航中 径搜索效果。对于较为复杂,凹形障待物较多的环境, 的应用哈尔滨工程大学学报 传统的路径规划算法不仅计算量庞大,而且易陷入局部 于振中,闫继宏,赵杰,等改进人工势场法的移动机器人 陷阱中无法逃逸,本文提出的算法针对此类环境有较高 路径规划哈尔滨工业大学学报 的规划效率,能找到较优的路径 郭娜基于模拟退火学习的移动机器人路径规划技术 研究南京:南京理工大学 参考文献 朱大奇,颜明重移动机器人路径规划技术综述控制与

...展开详情
试读 6P 论文研究-引入势场及陷阱搜索的强化学习路径规划算法.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
一个资源只可评论一次,评论内容不能少于5个字
您会向同学/朋友/同事推荐我们的CSDN下载吗?
谢谢参与!您的真实评价是我们改进的动力~
关注 私信
上传资源赚钱or赚积分
最新推荐
论文研究-引入势场及陷阱搜索的强化学习路径规划算法.pdf 50积分/C币 立即下载
1/6
论文研究-引入势场及陷阱搜索的强化学习路径规划算法.pdf第1页
论文研究-引入势场及陷阱搜索的强化学习路径规划算法.pdf第2页

试读结束, 可继续阅读

50积分/C币 立即下载 >