﻿ 基于A*的双向预处理改进搜索算法
 计算机系统应用  2019, Vol. 28 Issue (5): 95-101 PDF

1. 安徽工业大学 计算机科学与技术学院, 马鞍山 243032;
2. 滁州职业技术学院 信息工程系, 滁州 239000

Improved Search Algorithm Based on A* for Bidirectional Preprocessing
QIN Feng1, WU Jian1, ZHANG Xue-Feng1, ZHAO Jing-Li2
1. School of Computer Science and Technology, Anhui University of Technology, Ma’anshan 243032, China;
2. Department of Information Engineering, Chuzhou Vocational and Technical College, Chuzhou 239000, China
Foundation item: Research Fund of Education Bureau, Anhui Province (KJ2017ZD05); Young Scientists Fund of Natural Science Fund of Anhui Province (1808085QF210)
Abstract: In this study, an improved A* algorithm is proposed for the traditional A-star algorithm, which has many redundant path points and long-term one-way search. The proposed algorithm uses a bidirectional preprocessing structure to reduce the number of redundant nodes, and further optimizes the evaluation function to improve the traversal speed by normalizing the processing and adding node marker information. Simulation software is used to simulate the improved A* algorithm and compare with other classical path planning algorithms. The simulation results show that the improved A* algorithm can complete the global path planning with lower search node number and search duration than the traditional A* algorithm.
Key words: A* improved algorithm     route plan     pretreatment     valuation function

1 路径规划问题概述 1.1 路径规划的分类

1.2 路径规划的步骤

 图 1 节点运动方向

1.3 Dijkstra算法

Dijkstra算法目的为找出从图中的某个顶点出发到达另一个顶点所经过边的权重之和最小的那一条路径. 算法采用贪心策略模式使用广度优先搜索解决赋权有向图或者无向图的单源最短路径. 主要思想如下, 首先引入一个向量M, 它的的每个分量$M\left[ i \right]$代表从起始顶点V开始到其他各个顶点$V\left[ i \right]$的距离. 若V$V\left[ i \right]$有弧则将$M\left[ i \right]$设为弧上的权值. 显然$M\left[ j \right] = $$Min\left\{ {M\left| {Vi \in V} \right.} \right\} 即从起始顶点出发到顶点 {V_j} 距离最短的一条路径, 此时路径为 \left( {V,{V_j}} \right) . 接着定义一个存放从起始点V出发的最短路径的顶点集合S. 则下一条距离最优的路径必然为 M\left[ j \right] = Min\left\{ {M\left[ i \right]\left| {\mathop V\nolimits_i \in V - S} \right.} \right\} , M\left[ i \right] 为弧 \left( {\mathop V\nolimits_{} ,\mathop V\nolimits_i } \right) 上的权值或者为 M\left[ k \right]\left( {\mathop V\nolimits_k \in S} \right) 和弧 \left( {\mathop V\nolimits_k ,\mathop V\nolimits_i } \right) 权值总和(kS中的一个顶点). 直到遍历完整张地图网络之后, 算法根据局部最优准则选出一条最优路径, 但是缺点在于整个搜索过程属于盲目搜索只关注实际耗价值没有考虑到待选节点对目标节点所造成的影响, 因此规划过程将耗费大量的时间. 1.4 跳点算法 近年来研究人员推出了一种高效寻路算法Jump Point Search, 也就是所谓的跳点算法. 其本质针对有序序列查找跳点与二分法类似, 主要思想就是大范围跳跃式搜索栅格网络中对称的路径, 只把其中的跳跃点当作待搜索的栅格节点. 其明显优势在于大幅度减少openlist中的待选节点得益于在固定间隔的跳跃搜索过程中已经剔除了网格地图中大量无用节点. 具体的实现大致涉及到两个方面, 第一步先遍历openlist表筛选出一个最优节点, 然后从几个既定好的方向展开搜索, 将每个方向获得的跳点加入到openlist表中. 第二步在之前得到的各个方向上的跳点中筛选出代价最小的跳点作为新的起始点, 从该点开始继续向既定方向展开搜索. 重复以上两步操作, 直到终点被存入到openlist表中, 寻路结束. 但该算法仍然存在一些不可避免的限制因素, 首先对地图要求条件较高必须是规则的栅格型地图, 不支持复杂地形, 网格节点不能带权重, 但相比传统A*算法, 其算法效率已经提高了一倍左右. 1.5 传统A*算法 A*算法引入启发函数 h\left( n \right) 对全局信息进行估价, 将此估价作为最佳路径可能性的量度. 算法中关键的是两个list列表, 用于存储已经遍历和未遍历的栅格节点, 同时配合启发函数对地图上任意栅格节点距目标节点的距离进行有效估价, 估价值越接近实际耗费, 在四邻域或八邻域的情况下则会更好的寻找搜索方向. 算法主要表达式: f(n)=g(n)+h(n), 其中 f\left( n \right) 为初始状态经过状态n到达目标状态的代价估计, g\left( n \right) 为初始状态到达状态n的移动耗费, h\left( n \right) 为状态n到达目标状态的最低估计代价. A*算法步骤如下描述: Step 1. 将起始点加入openlist, 并初始化openlist和closedlist. Step 2. openlist若为空, 结束算法. 若不为空, 计算最小的点, 将该节点添加到最优路径上. Step 3. 对当前处理的节点, 以4方向或者8方向计算邻节点, 遍历closedlist和openlist, 若均不包含邻节点, 则将其加入openlist. Step 4. 循环执行Step 2和Step 3到算法结束, 回溯遍历之前拓展选中的路径, 则路径规划完成. 其中一般选用曼哈顿距离、欧式距离或者切比雪夫距离(当h(n)=0时, A*算法将变为Dijkstra算法),  {{Manhattan }}\;Distance = \left| {X1 - goalX} \right| + \left| {Y1 - goalY} \right| (1)  {{Euclidean\;Metric\;Distance }}\! = \!\!\!\sqrt {{{{\rm{(X1 \!-\! goalX)}}}^{\rm{2}}} \!+\! {{(Y1 \!-\! goalY)}^2}} (2)  {{Chebyshev\;Distance}} = {\rm{ max}}\left[ {\left| {X1 - goalX} \right|,\left| {Y1 - goalY} \right|} \right] (3) 2 改进双向预处理A*算法概述 综合上述传统算法的优缺点, 本文提出改进策略提高算法效率. 以经典A*算法为基础, 先执行双向搜索策略从起点终点同时开始搜索, 对算法中的角度和方向因子实现归一化处理以消除不同量纲对节点参数所带来的影响. 同时提出改进的算法结构, 将栅格地图中的障碍物信息预处理存入内存以减少资源消耗, 并且对遍历数组时的节点添加布尔类型的判定信息, 初始化地图后可直接依据此判定信息对节点是否在两个列表中进行判定而无须再做重复性的遍历操作, 进一步提高算法效率. 2.1 并行化处理 引入并行化处理模式即实现双向搜索算法, 该模式将搜索过程分解为前向后向两个独立的搜索进程, 起点终点分别作为对方向的目标节点. 双向搜索核心思路在于终止条件的判定, 在理想状态下两条搜索路径会在地图路径中心点相遇, 此时两个方向上的openlist中出现重复的节点即可判定规划完成, 这样做可大大减少单向遍历搜索所耗费的时间和空间资源. 2.2 矢量化和归一化的改进 A*算法在传统估价函数的影响下, 只会单一的进行往返搜索生成大量的搜索节点. 而在实际情况中当前节点距离目标节点的估价值一定不大于实际路径耗费值, 因此需要加快当前节点向目标节点的收敛速度即增大估价函数h(n)的权值. 考虑到大部分的权值设定都视具体的地图情况例如地图大小, 障碍物数量, 地形因素而定因此具有片面性. 并且当前节点距离目标节点的估价距离占实际距离的比重与当前节点在地图中的位置相关. 本文在前文基础上, 在当前节点远离目标点, 此时估价值低于实际值, 增大权重. 相对应的当前节点靠近目标点时, 当前估价值接近实际值, 相对应的降低权重. 因此本文引入以指数衰减方式的权重因子, 对传统A*算法表达式做出如下修改. 公式为:  \mathop f\nolimits^ * \left( n \right) = \left( {1 - \mathop \lambda \nolimits^ * } \right) \times g\left( n \right) + \mathop \lambda \nolimits^ * \times h\left( n \right) (4) 权重因子\mathop \lambda \nolimits^ * = \sqrt {{e^{h(n)}}}. 这样修改的优势在于既可保证g(n)与f(n)的权重系数相互影响, 又可使h(n)的权重系数的变化量与自身保持正相关, 便于调整当前节点向目标节点的收敛速度. 同样在估价函数h(n)中也需要引入距离和角度两个矢量因子[1418]. 意图减少搜索方向偏差过大的地图节点, 大幅度降低搜索节点数, 释放计算机资源, 公式为:  h(n) = \mathop w\nolimits_1 \times L + \mathop w\nolimits_2 \times \alpha (5) 式中的 \mathop w\nolimits_1$$ \mathop w\nolimits_2$分别为距离和角度的权重系数, 其取值范围分别为0.55–0.65和0.35–0.45[15]. L表示当前节点距目标点的距离值, $\alpha$表示起点至当前节点连线的线段与当前节点至目标节点连线线段的夹角值. 根据地图大小引入权重系数的优势在于, 同时权衡距离信息与方向信息, 加快搜索进程. 由于不同的评价标准具有不同的量纲, 为了消除指标之间量纲的影响, 需要进行数据归一化标准处理, 保留其本身所有特性, 但是减少参数大小产生的影响, 归一化大大加快了梯度下降求最优解的速度. 针对本文的思路, 对h(n)估价函数的距离和角度因子进行归一化处理, 对遍历进行提速. 本文对文献[19]的估价函数提出改进, 采用Z-score标准化方法对距离和角度消除量纲影响因素, 标准化公式为:

 $\mathop X\nolimits^ * = \left( {X - \mu } \right)/\sigma$ (6)

 $\mathop \alpha \nolimits^ * = \frac{{\left( {\alpha - \dfrac{1}{n}\displaystyle\sum\limits_{i = 1}^n {\mathop \alpha \nolimits_i } } \right)}}{{\sqrt {\dfrac{1}{n}} \displaystyle\sum\limits_{i = 1}^n {\left( {\mathop \alpha \nolimits_i - \dfrac{1}{n}\displaystyle\sum\limits_{i = 1}^n {\mathop \alpha \nolimits_i } } \right)} }}$ (7)
 $\mathop L\nolimits^ * = \dfrac{{\left( {L - \dfrac{1}{n}\displaystyle\sum\limits_{i = 1}^n {\mathop L\nolimits_i } } \right)}}{{\sqrt {\dfrac{1}{n}} \displaystyle\sum\limits_{i = 1}^n {\left( {\mathop L\nolimits_i - \dfrac{1}{n}\displaystyle\sum\limits_{i = 1}^n {\mathop L\nolimits_i } } \right)} }}$ (8)

 $\mathop h\nolimits^ * \left( n \right) = \left( {1 - \omega } \right) \times \mathop L\nolimits^ * + \omega \times \mathop \alpha \nolimits^ *$ (9)

 $\mathop f\nolimits^ * \left( n \right) = \left( {1 - \mathop \lambda \nolimits^ * } \right) \times g\left( n \right) + \mathop \lambda \nolimits^ * \times \mathop h\nolimits^ * \left( n \right)$ (10)

2.3 基于堆结构的完全排序

last←open. length-1;

while (last > 1)

half←last;

If(open[last]. F>=open[half]. F) THEN break;

temporary←open[last];

open[last]←open[half];

open[half]←temporary;

open[1]←open[last];

last←open. length-1;

childMin←open[child1]. F<open[child2].F?child1:child2;

open[childMin]←temporary;

2.4 实现预处理结构

3 实验结果对比分析

3.1 实验过程

 图 2 栅格地图

 图 3 几种规划算法运行效果截图

3.2 计算效率对比

4 结束语

 [1] 秦昆, 关泽群, 李德仁, 等. 基于栅格数据的最佳路径分析方法研究. 国土资源遥感, 2002, 14(2): 38-41. DOI:10.3969/j.issn.1001-070X.2002.02.009 [2] Cormen TT, Leiserson CE, Rivest RL. Introduction to Algorithms. Cambridge: MIT Press, 2001. [3] Mohajer B, Kiani K, Samiei E, et al. A new online random particles optimization algorithm for mobile robot path planning in dynamic environments. Mathematical Problems in Engineering, 2013, 2013: 491346. [4] 陆锋, 卢冬梅, 崔伟宏. 交通网络限制搜索区域时间最短路径算法. 中国图象图形学报, 1999, 4(10): 849-853. [5] Fredman ML, Tarjan RE. Fibonacci heaps and their uses in improved network optimization algorithms. Proceedings of the 25th Annual Symposium on Foundations of Computer Science. Singer Island, FL, USA. 1984. [6] 王士同. 双向启发式图搜索算法BFFRA. 电子学报, 1990, 18(6): 34-39. DOI:10.3321/j.issn:0372-2112.1990.06.006 [7] 郑年波, 李清权, 徐敬海, 等. 基于转向限制和延误的双向启发式最短路径算法. 武汉大学学报·信息科学版, 2006, 31(3): 256-259. [8] 熊壬浩, 刘羽. A*算法的改进及并行化. 计算机应用, 2015, 35(7): 1843-1848. [9] 熊伟, 张仁平, 刘奇韬, 等. A*算法及其在地理信息系统中的应用. 计算机系统应用, 2007, 16(4): 14-17. DOI:10.3969/j.issn.1003-3254.2007.04.004 [10] 王殿君. 基于改进A*算法的室内移动机器人路径规划. 清华大学学报(自然科学版), 2012, 52(8): 1085-1089. [11] 张宏烈. 移动机器人全局路径规划的研究[硕士学位论文]. 哈尔滨:哈尔滨工程大学, 2002. [12] 魏宁, 刘一松. 基于栅格模型的移动机器人全局路径规划研究. 微计算机信息, 2008, 24(11): 229-231. DOI:10.3969/j.issn.1008-0570.2008.11.094 [13] 陈华华, 杜歆, 顾伟康. 基于遗传算法的静态环境全局路径规划. 浙江大学学报(理学版), 2005, 32(1): 49-53. DOI:10.3321/j.issn:1008-9497.2005.01.013 [14] Chabini I, Lan S. Adaptations of the A* algorithm for the computation of fastest paths in deterministic discrete-time dynamic networks. IEEE Transactions on Intelligent Transportation Systems, 2002, 3(1): 60-74. DOI:10.1109/6979.994796 [15] Whangbo TK. Efficient modified bidirectional A* algorithm for optimal route-finding. In: Okuno HG, Ali M, eds. New Trends in Applied Artificial Intelligence. Berlin Heidelberg: Springer, 2007, 344-353. [16] Elbeltagi E, Hegazy T, Hosny AH, et al. Schedule-dependent evolution of site layout planning. Construction Management and Economics, 2001, 19(7): 689-697. DOI:10.1080/01446190110066713 [17] Hart PE, Nilsson NJ, Raphael B. Correction to " a formal basis for the heuristic determination of minimum cost paths”. ACM SIGART Bulletin, 1972(37): 28-29. [18] Guesgen HW, Mitra D. A multiple-platform decentralized route finding system. Proceedings of the 12th International Conference on Industrial and Engineering Applications of Artificial Intelligence and Expert Systems. Cairo, Egypt. 1999. 707–713. [19] 史辉, 曹闻, 朱述龙, 等. A*算法的改进及其在路径规划中的应用. 测绘与空间地理信息, 2009, 32(6): 208-211. DOI:10.3969/j.issn.1672-5867.2009.06.070