一种多约束条件下路径规划算法研究

李汉轩，李志华，吕春生

（1.河海大学 控制理论与控制工程系，江苏 南京 211100；2.91656部队 质量控制室，上海 200136）

目前，在最短路径规划方面，已经出现很多成熟优秀的算法。熟知的有Dijkstra算法、Ford算法，以及启发式的A*算法。这些算法在路径规划中对于解决只有距离限制的点与点之间最优路径的问题有着良好的时间复杂度[1]。在实际的车辆导航系统中，往往用户更希望能得到一些带约束条件的路径规划。在多约束条件的路径规划研究中，目前的确定性解决方法都拥有较高的时间复杂度[2-3]。而遗传算法、蚁群算法是近年来迅速发展起来的基于生物进化原理的全局性优化算法，在解决多约束路径规划问题中取得了很大成效[4-5]。这种仿生学算法往往具有良好的鲁棒性，并有着并行，反馈等特点，但收敛性不强，可能会陷入局部最优，无法得到全局最优解。文中结合A*算法和蚁群算法优点，提出了一种新的不确定算法。

1 基本算法

1.1 A*算法分析

A*（A-Star）算法是一种静态路网中求解最短路最有效的方法。如图1所示，算法中，将目前位置与目标位置的欧氏距离作为评估值，通过选择最小路径评估值，不断回溯运算，可求出全局最短距离。

公式表示如式（1）。

其中，f（n）是从初始点经由节点n到目标点的估价函数，g（n）是在状态空间中从初始节点到n节点的实际代价，h（n）是从n到目标节点最佳路径的估计代价。

图1 A*算法评估值示意Fig.1 A*algorithm assessed value

1.2 蚁群算法分析

蚁群算法（Ant Colony Optimization， ACO），又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型技术。……