基于A*算法的电动车路径规划研究彭

李芳馨 伍建全 翟渊 吴英

摘要：随着我国绿色新能源化进程的加快，新能源交通工具投入使用，促进了电动汽车的使用普及。电动车智能充电路径规划，成为行业发展需要考虑的问题。在满足人们生活出行的需求上，避免时间损耗，快速进行短距离路径选择。因此，文章提出了一种基于A*算法的电动车路径规划方法，分析了电动车路径规划策略的模拟实验场景，为电动车领域的智能充电路径发展，提供一些思路。

关键词：电动车；路径规划；A*

中图分类号：TP391.41  文献标志码：A

0 引言

现今，全球经济的持续性发展，带来了过度的能源损耗。资源的不当滥用，也让环境污染问题愈演愈烈。汽油和柴油作为交通工具的主要燃料来源，对于物质燃烧产生的气体，如二氧化碳、硫、氮氧化物等，都是导致环境问题的主要因素，带来温室效应和空气污染［1］。绿色新能源的引入，让电动车行业市场规模扩大。电动车作为一种绿色环保的新型交通工具，在保障人们生活出行需求的同时，也为城市智能化添砖加瓦。在路径规划问题中，从始发点到终点的路径规划效率，是评价一条路径是否为优的重要标准。除了要在规划过程中使得路径能达到指定目的地外，还需要及时绕过障碍物，在地图环境中自主地进行路径规划。

目前，对于电动车路径规划问题，可以根据不同目标的重要性来划分，大体上分为基于单目标的优化和基于多目标的优化两大类。对单一影响因素，可能包含时间目标、距离目标、价格目标等。基于多目标的优化，可能涵盖有至少两个影响因素来共同决定路径目标的优化策略。但目前，科技水平的发展和工业制造能力还有待提升，在人们日常生产出行上，其效率安全与预期仍有一定的差距。因此，借助路径规划算法改进智能交通出行工具的性能，变得尤为必要。

现阶段，根据周围环境信息的掌握程度不同，主要将算法分为两类。对于已知全局路径信息的场景，称为全局路径规划；对于周围存在未知信息或已知少量信息的场景，称为局部路径规划。在全局路径信息场景下，常采用静态地图模型进行路径搜索选取，可以以此环境信息，得到最优路径结果。由于这是一种预先规划的解决方式，对硬件配置的设备要求不高，若周围信息改变，算法极易陷入局部最优状态。在局部路径信息场景下，实时性能程度有较好的提高，对信息的处理，是依据周围环境信息感知来捕获和动态校准，在易变的环境下，能较好地应对突发信息，能实时反馈纠正延时错误信息，更新标注障碍点位。因此，有一定设备要求，来进行算法运行过程的高速信息计算。

本文的电动车路径规划，主要考虑电动车当前点位到充电桩点位之间的距离远近，用A*算法在多目标充电桩中选取距离电动车当前位置最短的一条路径，进行路径策略规划，降低电动车行驶过程中不必要时间的过度浪费，满足用户出行需求，解决电动车电量不足的充电问题。

1 A*算法原理

A*算法是一种启发式搜索算法，其评价函数决定了搜索方向，影响搜索效率和搜索结果，以此进行路径搜索［2］，一般用于对全局环境信息已经知晓的路径规划场景中。它会使用代价估计函数，进行每一步的路径挑选，从初始位置开始，不断向附近的子节点进行搜索扩展。评估函数，会依据子节点的距离代价，挑选代价值最小的节点，作为下一个父节点。重复之前的步骤操作，一直到寻到最终的目的地，完成路径规划策略，并生成最终路径。启发函数的一般表达式为：

F（n）=G（n）+H（n）（1）

其中，F（n）为起始点，经任意节点n 到达目标点的代价；G（n）为起始点到节点n 的实际距离；H（n）为节点n，到目的点的最优线路的距离评估。

H（n）函数，在整个评判体系中的影响最为关键。如果节点n 与目标点不存在障碍物，那么节点n 到目标点Y 的最优路径，为连接两点的直线。最短路径的表示，会用到欧几里得度量来表示点到点的直线距离。假设两点的坐标分别为（x1，y1）和（x2，y2），启发函数H（n）可以表示为：

H（n）=（x1-x2）2+（y1-y2）2（2）

在A*算法的路径搜索过程中，会借助两个list表，来对节点进行标注和选择，这两个表是在A*算法的执行过程中生成的，分别是openlist和closelist。closelist用于存放那些未被访问或访问后未扩展的节点；openlist用于存放那些已经被评估函数探索过的节点。之后，借助评估函数F（n）选出具有最低消耗代价特性的节点，将选入的节点连成路径，来完成栅格路径的搜索操作。

在算法实际的评估过程中，往往会把大量的访问节点放入openlist，以此进行代价排序。因此，openlist内的点越多，评估计算规模也就越大，相应的节点存取排序会更复杂，算法效率也会折损。适度选用简单的度量方法，能减少评估计算步骤，在提高启发函数的代价计算效率的同时，避免路径搜索中非必需的节点计算量。欧几里得度量法就是一种灵活易用的函数，通常用作A*算法的启发函数，A*算法实现过程如图1所示。

2 算法流程

本算法过程采用栅格地图对全局环境信息进行描述。采用点位设置的方式，自定义障碍物位置及起始终止点位，通过全局动态路径规划的A*算法，来寻求两点位之间的路径规划线路。选用路径长度代价评价函数，对多目标之间的代价进行评定，以获取最优目标。将最小代价路径目标，定为最终电动车路径规划结果输出。具体流程如图2所示。

3 实验应用与结果

本次实验使用Matlab模拟实验，进行A*算法的电动车路径规划。标准地图建模方法是光栅法，使用网格图分解的已知运行环境信息分为多个简单网格［3］，自定义电动车点位、充电桩点位及障碍物点位。模拟在掌握全局环境信息状态下，多目标中选取代价最小的最短路径结果。块状S点位，表示电动车所在位置；竖条块状，表示墙体等无法通行的障碍物；块状A点位、块状B點位、块状C点位、块状D点位、块状E点位为电动车可选择的充电桩位置；其余星形块状，表示在全局环境已知下，A*算法计算得出的最终路径。各图表示电动车S到各个充电桩的路径线路，电动车充电点位模拟实验结果如图3所示。

從S点到A点，预估代价为10；从S点到B点，预估代价为11；从S点到C点，预估代价为8；从S点到D点，预估代价为9；从S点到E点，预估代价为10。比较路径代价信息后，最终选取D点位充电桩，作为S点位电动车路径首选选项，电动车S到各个充电桩的路径代价和电动车S选用C充电桩的最终路径如图4所示。

4 结语

A*算法能在进行路径规划时，将已知全局环境地图信息划分为网格状，通过进行节点扩展寻找，搜索判断下一子节点位置，在全局路径规划中，具有高精准度和高效率性。它能快速寻优，得到距离代价最小的最终路径。本文利用A*算法，对模拟环境进行电动车路径规划，通过分析不同路径点位的路径规划结果，筛选出最小代价的路径线路，以此得到路径规划最终结果。

参考文献

［1］LAI C M，CHENG Y H. Research on energy-efficient path of electric vehicle traveling： 2021 IEEE International Future Energy Electronics Conference（IFEEC）， Taipei［C］. New York： IEEE，2021.

［2］LIPING C，CHUANXI L，YAN B.Improved hierarchical a star algorithm for optimal parking path planning of the large parking lot：2014 IEEE International Conference on Information and Automation（ICIA）， Hailar ［C］. New York： IEEE，2014.

［3］CHEN Y，WANG P，LIN Z，et al.Global path planning method by fusion of a-star algorithm and sparrow search algorithm：2022 IEEE 11th Data Driven Control and Learning Systems Conference（DDCLS），Leshan ［C］. New York： IEEE，2022.

（编辑 沈 强）

Research on path planning of electric vehicle based on A* algorithm

Peng  Lifangxin， Wu  Jianquan， Zhai  Yuan， Wu  Ying*

（School of Intelligent Technology and Engineering，Chongqing University of Science and Technology， Chongqing 401331， China）

Abstract：  With the process of green new energy speeding up in China， new energy transportation vehicles have been put into use， and promoted the popularization of the use of electric vehicles. Intelligent charging path planning of electric vehicles has become an issue that needs to be considered in the development of the industry. In order to meet the needs of people’s travel life， short distance path selection can be carried out quickly to avoid time loss. Therefore， an EV path planning method based on A* algorithm is proposed， and the simulation experiment scenario of EV path planning strategy is analyzed. It provides some ideas for the development of intelligent charging path in the field of electric vehicles.

Key words： electric vehicles; path planning; A*