基于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*