工具之家 > 软件导刊 > 基于平滑A*人工势场法的机器人动态路径规划

基于平滑A*人工势场法的机器人动态路径规划

发布时间:2019-01-18 02:16:00 文章来源:工具之家    

 推荐工具:金融理财app工具实用工具

任玉洁+付丽霞+张勇+毛剑琳

摘要:针对动态环境下移动机器人的路径规划问题,提出了平滑A*人工势场法的路径规划方法。首先采用平滑A*算法在静态障碍物环境中进行全局路径规划;其次,在机器人遇到动态障碍物时采用A*人工势场法进行局部动态路径规划,并以此调整全局路径规划结果;最后对路径规划结果进行平滑处理。将平滑A*人工势场法应用于机器人动态路径规划,并与D*算法进行对比。实验结果表明,该算法能够在动态环境下规划出一条更为优化的路径,有效缩短了路径长度,提高了规划效率。

关键词:A*算法;人工势场法;路径规划;机器人

DOIDOI:10.11907/rjdk.172192

中图分类号:TP301

文献标识码:A文章编号文章编号:16727800(2018)001000803

Abstract:A path planning method based on smoothed A* artificial potential field is proposed aiming the path planning problem of mobile robot in dynamic environment, In order to improve the planning efficiency, Firstly a smoothed A* algorithm was used to perform the global path planning in the static obstacle environment;Secondly the A* artificial potential field method was applied to perform the local dynamic path planning and adjusted then the global path planning results when the robot encounters a dynamic obstacle;Finally the path planning results were smoothed.The smoothed A* artificial potential field method is applied to the robot dynamic path planning and compared with the D*algorithm. Experimental results have shown that the proposed algorithm can be worked out a more optimized path in dynamic environment, effectively shorten the path length, improve the planning efficiency.

Key Words:A* algorithm; artificial potential field method; path planning; robot

0引言

路径规划是移动机器人控制领域的一个重要研究方向,它是指依据某些指标在一个障碍物环境下搜寻一条从起始点到目标点的最优或近似最优无碰撞路径[12]。依据环境信息,大体上可将路径规划分为环境信息已知的全局路径规划和基于传感器感知的局部路径规划[3]。其中,全局路径规划能处理障碍物信息已知情况下的路径规划,但当出现动态障碍物时,规划效果不理想;局部路径规划能够通过传感器反馈的信息,规避环境中的动态障碍物。

A*算法是一种经典的启发式搜索算法,适用环境已知的全局路径规划,它具备最优性、完备性和高效性[4],利用A*算法可以得到较好的路径规划效果。但是由于A*算法的计算特点,规划出的路径点一般存在折线多、累计转折角度大等问题。平滑A*[5]通过建立平滑模型,有效降低了路径中的转折点与转折角度。D*算法[6]是基于A*算法提出的机器人动态路径规划算法,其思想是在向目标点移动过程中,若检测到环境中的动态障碍物,则搜寻障碍物附近节点的变化情况,重新规划路径。人工势场法[7]是一种比较成熟的局部路径规划算法,其由于具有计算速度快、适用于实时控制的优点而得到广泛应用。但由于该方法依据的是局部环境信息,缺乏全局自我调节能力,易陷入局部最优[8]。

本文提出平滑A*算法和改进人工势场法结合的动态路径规划算法。首先,为提高算法搜索效率,采用文献[5]中的平滑A*算法对障碍物环境进行全局路径规划,再引入改进的人工势场法对动态障碍物进行避障。

1A*算法

1.1传统A*算法

A*算法是一种经典的启发式算法,在静态环境中能高效地求出从起始点到目标点的路径,其估价函数定义为:

其中,X是当前节点,f(x)是当前节点的总启发代价,g(x)是初始点到当前点的实际路径代价,h(x)是当前点到目标点的估计路径代价。

h(x)的取值对算法效率具有决定性作用。本文采用当前点与目标点之间的欧几里得距离作为估计代价,如下所示:

其中,xt为目标点横坐标,yt为目标点纵坐标,xx为当前点横坐标,yx为当前点纵坐标。

A*算法寻径首先要创建两张表:open list和close list。其中,open list用来保存拓展节点,close list用來保存障碍物和已使用过的节点。搜寻过程中,先从open list找出总启发代价最小的点设为当前节点,将其放入close list,并对其进行扩展;将扩展后的节点更新到open list,再从open list选取总启发代价最小的点设为当前节点;重复过程,直到找到目标点。

1.2平滑A*算法endprint

文献[5]中提出,传统A*算法规划出的路径存在冗余转折点,为了避免不必要的转折,对求得的路径进行平滑处理。从当前点开始,依次连接之后的节点,判断是否与障碍物有交点,如果无交点,舍弃中间节点,求出平滑路径。具体过程如下:①取出传统A*算法规划出的路径点,将起点设为pcurrent,下