一种基于威胁势场的A星路径规划算法

【摘 要】为了解决传统A星算法在路径规划中因忽略障碍物威胁而导致规划路径并不安全的问题，提出了一种基于威胁势场的A星路径规划方法，该方法中将障碍物理解成一个具有威胁势场的对象，威胁值与离障碍物的距离成反比关系，将该威胁值引入估价函数中，作为整个估价函数的评价标准，经过仿真实验验证，该方法实现了威胁最小的有效路径规划，提高了路径规划的安全性能。

【关键词】路径规划；启发式；A星算法；威胁势场

0 引言

路径规划[1]，即通过某种策略在符合一定性能指标下规划一条从起始点到目的地的最佳路径，其应用领域主要包括在游戏设计、工业机器人、交通和网络路由等领域的路径搜索。由此便衍生出各种路径搜索算法，如神经网络[2]、遗传算法[3]、人工势场法[4]、Dijkstra算法和A星算法[5]，每种算法各有优缺点，经常会根据不同的场景和性能需求选择合适算法，也可相互结合来弥补各自缺点以达到性能要求。而其中A星算法具有简单，效率高且搜索路径最优等特点，依然是当今的研究热点。传统的A星算法，估价函数仅仅只考虑了g代价和h代价，对于周围的障碍物的威胁代价则不予考虑，因此其规划的路径并不“最优”的无碰路径。

鉴于传统A星算法所存在对障碍物威胁不予考虑的问题，本文结合人工势场中威胁势场的概念提出了一种基于威胁势场的A星路径规划算法。

1 传统A星算法

A星算法是一种在广度搜索算法的基础之上引入估价函数的启发式路径搜索算法，与基本的广度搜索算法不同在于，引入估价函数使得算法不再盲目，能够搜索出最优的路径。

传统的A星算法估价函数为：

f=g+h（1）

其中，f为总估计代价，g为从起点到当前点的实际代价，h为从当前点到终点的估计代价。

传统A星算法的具体过程可参考文献[5]。

2 改进A星算法

传统A星算法规划的路径往往是几乎沿着障碍物的边缘生成的一条路径，这样的路径是十分危险的，移动目标或障碍物的轻微偏移都可能造成碰撞发生。为了解决该问题，人们引入C-空间[6]的概念，即沿着障碍物边缘将移动目标的尺寸叠加上去，然而对于现实复杂的环境，这样叠加运算操作会造成整个算法的效率急剧下降，因此一般在效率要求比较高的情况都很少采用该方法。

威胁势场理论可以很好的解决该问题，该理论最早是在人工势场法[4]中。人工势场法主要依赖障碍物的威胁势场模型和梯度下降法来进行路径搜索，势场模型没有选好，则搜索过程中障碍物比较集中的地方易陷入局部最优，导致无法成功搜索出路径。针对该问题，人们也提出了不同的威胁模型进行改进，对于威胁模型的选型已超出本文的研究范围。本文主要引入威胁势场的思想，将其与传统A星结合，解决A星所存在的问题，实现真正的最优路径规划。

本文提出的算法，主要区别在于估价函数中引入了威胁估计值，具体为：

对威胁估价函数的定义一般都和距离有关系，比较常用的有反比例模型和高斯模型两种，本文采用简单的反比例威胁模型：

可知，这样就形成了一个以障碍物为中心的山峰势场，在整个地图中系统会优先搜索势场最低的点。对于α，β，γ设定权值不同，搜索的路径也有所不一样。

改进后的算法具体工作流程如下：

（1）初始化，生成一个open列表和一个closed列表。

（2）把起点加入open列表，open列表中仅包含起始节点，记f=h。

（3）如果open列表为空，则搜索失败并结束搜索，否则向下执行。

（4）查找open列表中f最小的点作为当前节点，并检查当前节点是否为目标节点，如果是则成功搜索到路径，返回路径并结束搜索，否则向下执行。

（5）把当前节点从open列表中，并加入到closed列表中。

（6）扫描当前节点的周围节点的启发值h，同时更新周围节点受到周围障碍物威胁影响值t，并按要求将当前节点作为该周围节点的父节点，跳转至（3）。

3 实验仿真与结果分析

为了验证本文提出算法的准确性和有效性，本文还进行了仿真实验验证，并与传统算法进行了数据对比。

图1为传统A星和本文方法仿真结果图，从A点到B点，传统A星算法规划的路径会经过狭窄的通道，而本文的方法则优先选择比较安全的路径，具体数据对比如表1所示。

由表1中仿真结果显示，传统方法在不考虑障碍物威胁的前提下，能够规划一条路径，但是该路径危险性明显比较大，虽然传统A星搜索的路径远远小于本文的方法的路径，但是其整个路径过程中危险总值却大于本文方法，且平均威胁值可达到原来的一半以下，仿真结果说明本文方法是比较符合实际安全需求的。

为了进一步验证威胁势场对路径搜索具有重要评估能力，在威胁估价的权值系数取λ∈[0，100]范围内，进行了仿真实验。

由图2和图3可知，λ当威胁估价的权值系数从0到100变大时，移动目标所受的总威胁值和平均威胁值呈现显著下降趋势，该结果证明了当威胁估价权值越高则规划出的路径则越安全，结果证明了算法的有效性。

4 总结

本文针对路径规划中A星算法所存在的问题进行了分析，并在对人工势场法进行深入研究基础上将其中的威胁势场理论引入A星算法中，提出了一种基于威胁势场的A星路径规划算法。在传统A星基础上，在每次搜索中将当前点的所受威胁值作为评估标准之一。通过实验验证了本文方法能够比较准确的进行最优路径的规划，与传统方法相比，该方法的安全性能得到显著提高。

【参考文献】

[1]张颖，吴成东，原宝龙.机器人路径规划方法综述[J].控制工程学报，2003，10： 152-155.

[2]王薇，魏世民，杨月巧.基于神经网络的移动机器人路径规划[J].北京工业大学学报，2010（9）：1287-1291.

[3]孙树栋，曲彦宾.遗传算法在机器人路径规划中的应用研究[J].西北工业大学学报，1998，16（1）：79- 83.

[4]黄炳强，曹广益.基于人工势场法的移动机器人路径规划研究[J].计算机工程与应用，2006，27：26-28.

[5]陈圣群，滕忠坚.A*算法在车辆导航系统中的应用研究[J].微计算机信息， 2008，11（3）：269-270.

[6]丁富强，韩卫军，赵锡芳.基于C空间的双臂机器人无碰撞运动规划[J].上海交通大学学报，2001，35（1）：54-58.