基于A星算法与人工势场法的无人机路径规划
2019-08-08王云常戴朱祥
王云常, 戴朱祥, 李 涛
(南京信息工程大学自动化学院, 南京 210044)
无人机技术中常用的路径规划方法有人工势场法[1-3], 蚁群算法[4-5]以及可视图法[6]等.其中, 人工势场法设无人机在目标点引力和障碍物斥力的合力作用下运动, 其路径平滑、方法简单、易于实现, 是一种新型的路径规划避障方法.但该方法容易出现局部极小点以及无法避让大型障碍物的问题.为此, Yan[7]提出将人工势场法与蚁群算法相结合的方法; Zhang等[8]提出一种基于虚拟结构和“领导者跟随者”控制策略的三维避障控制算法.障碍物在人工势场法中被视为质点或形状均匀的圆, 但障碍物实际的形状和大小各异, 运用人工势场法难以计算斥力.A星算法[9-10]是一种运用启发式函数[11]在静态地图中寻找避障路径的方法, 可以弥补人工势场法在避让大型障碍物方面的不足.本文提出一种将人工势场法与A星算法相结合的改进算法, 以人工势场法指导全局路径规划、A星算法指导局部路径规划, 在保证安全避障寻路的同时降低计算成本.
1 模型建立
图1 采用传统人工势场法时无人机遭遇大型障碍物的受力图Fig.1 Force diagram of UAV when it encounters large obstacle in traditional artificial potential field method
图1是采用传统人工势场法时无人机遭遇大型障碍物时的受力图.如图1所示,传统人工势场法中斥力Fr与引力Fa的合力F无法引导无人机绕过障碍物.采用A星算法进行扫描探测则可以检测障碍物并规划避障路径,但在无障碍物时,无人机在A星算法下的飞行成本较高,花费时间较长.为降低计算成本,本文使用人工势场法规划总体路径;当检测到大型障碍物时,将地图栅格化,确定避障的起始节点和终止节点,然后通过A星算法规划避障路线;当无人机完成障碍物避让后,继续采用人工势场法进行路径规划.以此循环,直到到达目标点.改进后的算法流程如图2所示.
图2 基于A星算法和人工势场法的改进算法流程Fig.2 Improved algorithm flow based on A-Star algorithm and artificial potential field method
1.1 人工势场法的改进
在人工势场法中, 设无人机坐标为X(x,y),目标点坐标Xt(xt,yt), 障碍物坐标为Xo(xo,yo), 设无人机只受引力作用, 引力系数为k, 则引力场
式中ρ为无人机与障碍物的危险距离.当无人机与障碍物距离大于ρ时, 无人机在人工势场法的引力场下向目标位置移动; 否则进行避让, 无人机不受引力场作用并停止移动.
1.2 A星算法的改进
图3 地图栅格化和A星算法的起始、终止节点示意图Fig.3 Rasterization of the map and schematic diagram of the starting and terminating nodes of the A-Star algorithm
2 仿真结果与分析
本文在操作系统为Windows 10,8 GB内存,Intel(R) Core(TM) i5-6500 CPU @ 3.20 GHz 的计算机上运用Matlab 2010a软件进行仿真试验.设100 m×100 m的二维空间地图上有2个大小不能忽略不计的障碍物,人工势场法的引力系数为2, 危险距离为1 m,无人机的运行速度为4 m·s-1, 扫描时长为0.5 s·轮-1.分别运用人工势场法、A星算法和本文算法规划无人机从地图坐标系Oxy中的坐标点(1,1)至点(99,91)的飞行路线.图4为不同算法的飞行路径示意图.图4(a)显示, 在人工势场法下,无人机无法躲避障碍物,与障碍物发生碰撞,这是由于传统人工势场法将障碍物视为质点,将障碍物中心看作斥力产生的位置,当障碍物体积较大时,无人机便无法躲避.图4(b)显示, 使用A星算法规划避障路线时,扫描区域面积大,计算时间也相应增加.图4(c)展示了改进算法的飞行路径: 首先根据人工势场法的计算路线飞行至障碍物前点(32,29)处; 以该坐标点为起始节点,以A星算法探测的避障路径飞行至点(45,55)处, 终止A星算法; 继续使用人工势场法飞行至障碍物前点(69,69)处;再次使用A星算法避障,在点(78,31)处结束扫描和路径规划;最后,无人机在人工势场法下到达终点.表1为无人机采用不同算法的飞行时间对比.由于人工势场法无法安全避障,所以没有列出其飞行时间.与A星算法相比,改进算法的飞行时间明显缩短, 验证了改进算法的可行性与有效性.后续工作中将继续关注如何躲避大型移动障碍物的问题,进一步提升算法的实用性.
图4 无人机在人工势场法(a),A星算法(b)和改进算法(c)下的飞行路径示意图Fig.4 The flight path diagram of UAV under the artificial potential field method (a), A-Star algorithm (b) and the improved algorithm (c)
表1 无人机采用不同算法的飞行时间对比Tab.1 Comparison of flight time using different algorithms s