祁玄玄，黄家骏，曹建安

（西安交通大学电气工程学院，西安 710049）

（*通信作者电子邮箱2787477370@qq.com）

0 引言

路径规划在智能车运动控制中占有核心地位，路径规划算法的效率将直接影响无人车的寻路效率及实施规划能力。目前路径规划算法基本分为两种类型：基于图搜索算法的传统算法和智能算法。图搜索算法主要指的是Floyd 算法［1］和Dijkstra 算法［2］；智能算法包括蚁群算法［3］、粒子群算法［4］、遗传算法［5］、神经网络［6］、模拟退火［7］等。传统的图搜索算法存在随着环境信息的增加计算复杂性呈现指数式增加的缺点，智能算法作为一种路径规划的新思路其对计算机性能要求过高且存在计算时间较长的缺点。A*（A-Star）算法［8-9］是基于传统图搜索的思维的智能启发式算法，相比传统图搜索算法，它具有计算量小、规划路径相对最优等突出特点。但是A*算法的启发函数考虑维度较为简单，导致该算法在寻路过程中会出现很多冗余的扩展栅格。目前已经提出了很多改进A*算法，如：文献［10］中通过估价函数进行指数衰减的方式加权减少了冗余的扩展；文献［11］中通过建立禁忌表来改进A*算法的估价函数，能快速、有效地实现越野路径规划。与文献［10-11］类似地通过对A*算法估价函数进行改进以达到减少计算时间的算法还有很多，但是它们的普适性并不好。文献［12］中通过起点和终点同时运行时效A*算法寻找路径，文献［13］中通过并行算法改进A*寻路时间，这两者在一定程度上可减少计算时间，但是都过于依赖计算机的性能。……