地图导航中的路径规划算法（综述）

综述介绍+本人研究与实践结果——实际是论文

 

相关的路径规划算法,静态路网中,通常使用双向A*算法

常见的其他搜索算法，IA*（迭代A*），内存限定A*，分层路网A*（将高速路网构建成一个新的路网），

D*(针对不确定环境下的动态路径算法，来与机器人路径选择）

 

 3.3 路径规划算法分析与设计
导航终端动态规划技术应用于导航终端设备中，路径规划的主要功能是搜索起止点
之间的最优路径。一般认为，提高路径规划算法效率的主要方法包括：
第三章 系统关键技术研究
（1）合理优化路网结构，降低参与路径计算的路网规模；
（2）合理优化路径规划算法数据结构，提高路径计算效率；
（3）研究新的路径搜索算法。
静态路径规划算法的研究已经比较成熟，但目前在终端上的路径规划，当路程很长
是，有时仍然存在资源利用率高，系统响应慢等问题。
本文先从用户需求角度分析现有算法存在的问题和改进算法的策略，再进一步分析
相关算法特点，给出基于A*算法的改进算法——自适应A 算法。
动态路径规划算法根据交通控制中心(TMC)发布的实时动态交通信息，按照用户需
求计算最佳出行路径。由于车辆导航终端硬件配置较低，计算能力、存储空间有限，因
此如何保证动态路径计算的实时性和路径的有效性就成为该领域研究的热点问题。
本文给出一种新的动态路径搜索方法，它基于局部搜索技术，分阶段逐步动态路径
规划，解决了在动态交通信息下的路径规划的计算效率和存储空间问题。
3.3.1 用户对路径规划算法的需求
无论是静态路径规划算法，还是动态路径规划算法，都要考虑到用户驾驶行为上的
需求。下面给出用户对路径选择的一些偏好：
(1) 低等级的道路的平均速度通常要低于高等级的道路。
(2) 低等级道路的数目通常要多于高等级道路。
(3) 高等级道路上的红绿灯数目更少，拥堵情况少。
(4) 高等级道路通常复杂程度低，用户易于驾驶。
(5) 其他偏好，如路径上的风景优美，道路十分宽敞、整洁，道路是否收费。
因此，在给定起点终点的条件下，当两条路径总代价相当情况下，除(5)的特殊偏好
外，用户多倾向于选择高等级道路，道路评价速度快、距离短、红绿灯少的路径。
3.3.2 自适应A 算法分析
在2.3.2 节中讨论了A*算法在静态路径规划算法中的应用，但在实际复杂的交通网
络中，常用的A*算法并不能满足终端上搜索快速响应的要求，本文根据A*算法的三个
启发评价尺度指标进行分析，进而给出一种自适应A(Adaptive A)算法，以下简称AA。
通常A*算法涉及到这三个特点：可采纳性(admissible)，单调性(monotonicity)，信
息度(inoformedeness)[12]。
A. 可采纳性
定义：考虑评估函数f (n)=g(n)+h(n)，其中：
n 是搜索中遇到的当前任意状态；
g(n) 是起始状态到n 的代价。
h(n)是对n 到目标状代价的的启发式估计。
如果h(n)总是小于等于从n 到目标状态的最短路径代价，那么称该算法是可采纳的。
如果可采纳，那么就可以保证算法的正确性。
因为在A*算法中h(n)总是小于等于从n 到目标状态的最短路径代价。因此算法A*
总是可采纳的。但是在实际的车辆路径规划中，往往只需要找到近似最优路径，因此并
不一定需要h(n)严格小于或等于h*(n)。弱化这个可采纳性条件，此时算法更倾向于搜
索那些最有希望是最短路径上的状态。
B. 单调性
定义：启发式函数h 单调的条件是：
对于所有的状态ni 和nj ，其中nj 是ni 的后继，那么( ) ( ) ( , ) j i i j h n −h n <=cost n n ，
其中： ( , ) i j cost n n 是状态ni 到nj 的实际距离代价（在车辆路径规划中，常以时间或者距
离为计算代价）。目标状态的启发值为0，即h(Goal)=0；
描述单调特征的一种方式是，搜索空间的每一处都是与所采用的启发具有局部一致
性。一个状态的启发性尺度与任何后继的启发性尺度之间的差值是以从这个状态到其后
继的实际代价为上限的。也就是说，这个启发在搜索空间的每一处都是可采纳的，可以
从每个状态的祖先沿最短路径到达这个状态。
如果处处满足单调性，那么它一定是可采纳的。但可采纳性并不蕴含着处处单调性。
C. 信息度
对于两个A*启发函数1 h 和2 h ，如果对于搜索空间中的每一个搜索状态都满足
1h (n)< 2h (n)，那么就说2 h 比1 h 具有更高的信息度。
由于在静态路径规划算法中，通常以当前点到终点的球面直线距离作为启发式估计
距离，显然该函数是一个单调的，可采纳的，但其信息度往往不高，因为使用该函数得
到的估计距离要远远小于实际的路线距离。而且在整个搜索过程中，当距离终点比较远
时，并不需要始终不变的启发式函数，可以对该球面直线距离乘以系数来提高信息度，
加速收敛。
、