李芳馨 伍建全 翟淵 吳英
摘要：隨著(zhù)我國綠色新能源化進(jìn)程的加快，新能源交通工具投入使用，促進(jìn)了電動(dòng)汽車(chē)的使用普及。電動(dòng)車(chē)智能充電路徑規劃，成為行業(yè)發(fā)展需要考慮的問(wèn)題。在滿(mǎn)足人們生活出行的需求上，避免時(shí)間損耗，快速進(jìn)行短距離路徑選擇。因此，文章提出了一種基于A(yíng)*算法的電動(dòng)車(chē)路徑規劃方法，分析了電動(dòng)車(chē)路徑規劃策略的模擬實(shí)驗場(chǎng)景，為電動(dòng)車(chē)領(lǐng)域的智能充電路徑發(fā)展，提供一些思路。
關(guān)鍵詞：電動(dòng)車(chē)；
路徑規劃；
A*
中圖分類(lèi)號：TP391.41? 文獻標志碼：A
0 引言
現今，全球經(jīng)濟的持續性發(fā)展，帶來(lái)了過(guò)度的能源損耗。資源的不當濫用，也讓環(huán)境污染問(wèn)題愈演愈烈。汽油和柴油作為交通工具的主要燃料來(lái)源，對于物質(zhì)燃燒產(chǎn)生的氣體，如二氧化碳、硫、氮氧化物等，都是導致環(huán)境問(wèn)題的主要因素，帶來(lái)溫室效應和空氣污染［1］。綠色新能源的引入，讓電動(dòng)車(chē)行業(yè)市場(chǎng)規模擴大。電動(dòng)車(chē)作為一種綠色環(huán)保的新型交通工具，在保障人們生活出行需求的同時(shí)，也為城市智能化添磚加瓦。在路徑規劃問(wèn)題中，從始發(fā)點(diǎn)到終點(diǎn)的路徑規劃效率，是評價(jià)一條路徑是否為優(yōu)的重要標準。除了要在規劃過(guò)程中使得路徑能達到指定目的地外，還需要及時(shí)繞過(guò)障礙物，在地圖環(huán)境中自主地進(jìn)行路徑規劃。
目前，對于電動(dòng)車(chē)路徑規劃問(wèn)題，可以根據不同目標的重要性來(lái)劃分，大體上分為基于單目標的優(yōu)化和基于多目標的優(yōu)化兩大類(lèi)。對單一影響因素，可能包含時(shí)間目標、距離目標、價(jià)格目標等?；诙嗄繕说膬?yōu)化，可能涵蓋有至少兩個(gè)影響因素來(lái)共同決定路徑目標的優(yōu)化策略。但目前，科技水平的發(fā)展和工業(yè)制造能力還有待提升，在人們日常生產(chǎn)出行上，其效率安全與預期仍有一定的差距。因此，借助路徑規劃算法改進(jìn)智能交通出行工具的性能，變得尤為必要。
現階段，根據周?chē)h(huán)境信息的掌握程度不同，主要將算法分為兩類(lèi)。對于已知全局路徑信息的場(chǎng)景，稱(chēng)為全局路徑規劃；
對于周?chē)嬖谖粗畔⒒蛞阎倭啃畔⒌膱?chǎng)景，稱(chēng)為局部路徑規劃。在全局路徑信息場(chǎng)景下，常采用靜態(tài)地圖模型進(jìn)行路徑搜索選取，可以以此環(huán)境信息，得到最優(yōu)路徑結果。由于這是一種預先規劃的解決方式，對硬件配置的設備要求不高，若周?chē)畔⒏淖?，算法極易陷入局部最優(yōu)狀態(tài)。在局部路徑信息場(chǎng)景下，實(shí)時(shí)性能程度有較好的提高，對信息的處理，是依據周?chē)h(huán)境信息感知來(lái)捕獲和動(dòng)態(tài)校準，在易變的環(huán)境下，能較好地應對突發(fā)信息，能實(shí)時(shí)反饋糾正延時(shí)錯誤信息，更新標注障礙點(diǎn)位。因此，有一定設備要求，來(lái)進(jìn)行算法運行過(guò)程的高速信息計算。
本文的電動(dòng)車(chē)路徑規劃，主要考慮電動(dòng)車(chē)當前點(diǎn)位到充電樁點(diǎn)位之間的距離遠近，用A*算法在多目標充電樁中選取距離電動(dòng)車(chē)當前位置最短的一條路徑，進(jìn)行路徑策略規劃，降低電動(dòng)車(chē)行駛過(guò)程中不必要時(shí)間的過(guò)度浪費，滿(mǎn)足用戶(hù)出行需求，解決電動(dòng)車(chē)電量不足的充電問(wèn)題。
1 A*算法原理
A*算法是一種啟發(fā)式搜索算法，其評價(jià)函數決定了搜索方向，影響搜索效率和搜索結果，以此進(jìn)行路徑搜索［2］，一般用于對全局環(huán)境信息已經(jīng)知曉的路徑規劃場(chǎng)景中。它會(huì )使用代價(jià)估計函數，進(jìn)行每一步的路徑挑選，從初始位置開(kāi)始，不斷向附近的子節點(diǎn)進(jìn)行搜索擴展。評估函數，會(huì )依據子節點(diǎn)的距離代價(jià)，挑選代價(jià)值最小的節點(diǎn)，作為下一個(gè)父節點(diǎn)。重復之前的步驟操作，一直到尋到最終的目的地，完成路徑規劃策略，并生成最終路徑。啟發(fā)函數的一般表達式為：
F（n）=G（n）+H（n）（1）
其中，F（n）為起始點(diǎn)，經(jīng)任意節點(diǎn)n 到達目標點(diǎn)的代價(jià)；
G（n）為起始點(diǎn)到節點(diǎn)n 的實(shí)際距離；
H（n）為節點(diǎn)n，到目的點(diǎn)的最優(yōu)線(xiàn)路的距離評估。
H（n）函數，在整個(gè)評判體系中的影響最為關(guān)鍵。如果節點(diǎn)n 與目標點(diǎn)不存在障礙物，那么節點(diǎn)n 到目標點(diǎn)Y 的最優(yōu)路徑，為連接兩點(diǎn)的直線(xiàn)。最短路徑的表示，會(huì )用到歐幾里得度量來(lái)表示點(diǎn)到點(diǎn)的直線(xiàn)距離。假設兩點(diǎn)的坐標分別為（x1，y1）和（x2，y2），啟發(fā)函數H（n）可以表示為：
H（n）=（x1-x2）2+（y1-y2）2（2）
在A(yíng)*算法的路徑搜索過(guò)程中，會(huì )借助兩個(gè)list表，來(lái)對節點(diǎn)進(jìn)行標注和選擇，這兩個(gè)表是在A(yíng)*算法的執行過(guò)程中生成的，分別是openlist和closelist。closelist用于存放那些未被訪(fǎng)問(wèn)或訪(fǎng)問(wèn)后未擴展的節點(diǎn)；
openlist用于存放那些已經(jīng)被評估函數探索過(guò)的節點(diǎn)。之后，借助評估函數F（n）選出具有最低消耗代價(jià)特性的節點(diǎn)，將選入的節點(diǎn)連成路徑，來(lái)完成柵格路徑的搜索操作。
在算法實(shí)際的評估過(guò)程中，往往會(huì )把大量的訪(fǎng)問(wèn)節點(diǎn)放入openlist，以此進(jìn)行代價(jià)排序。因此，openlist內的點(diǎn)越多，評估計算規模也就越大，相應的節點(diǎn)存取排序會(huì )更復雜，算法效率也會(huì )折損。適度選用簡(jiǎn)單的度量方法，能減少評估計算步驟，在提高啟發(fā)函數的代價(jià)計算效率的同時(shí)，避免路徑搜索中非必需的節點(diǎn)計算量。歐幾里得度量法就是一種靈活易用的函數，通常用作A*算法的啟發(fā)函數，A*算法實(shí)現過(guò)程如圖1所示。
2 算法流程
本算法過(guò)程采用柵格地圖對全局環(huán)境信息進(jìn)行描述。采用點(diǎn)位設置的方式，自定義障礙物位置及起始終止點(diǎn)位，通過(guò)全局動(dòng)態(tài)路徑規劃的A*算法，來(lái)尋求兩點(diǎn)位之間的路徑規劃線(xiàn)路。選用路徑長(cháng)度代價(jià)評價(jià)函數，對多目標之間的代價(jià)進(jìn)行評定，以獲取最優(yōu)目標。將最小代價(jià)路徑目標，定為最終電動(dòng)車(chē)路徑規劃結果輸出。具體流程如圖2所示。
3 實(shí)驗應用與結果
本次實(shí)驗使用Matlab模擬實(shí)驗，進(jìn)行A*算法的電動(dòng)車(chē)路徑規劃。標準地圖建模方法是光柵法，使用網(wǎng)格圖分解的已知運行環(huán)境信息分為多個(gè)簡(jiǎn)單網(wǎng)格［3］，自定義電動(dòng)車(chē)點(diǎn)位、充電樁點(diǎn)位及障礙物點(diǎn)位。模擬在掌握全局環(huán)境信息狀態(tài)下，多目標中選取代價(jià)最小的最短路徑結果。塊狀S點(diǎn)位，表示電動(dòng)車(chē)所在位置；
豎條塊狀，表示墻體等無(wú)法通行的障礙物；
塊狀A點(diǎn)位、塊狀B點(diǎn)位、塊狀C點(diǎn)位、塊狀D點(diǎn)位、塊狀E點(diǎn)位為電動(dòng)車(chē)可選擇的充電樁位置；
其余星形塊狀，表示在全局環(huán)境已知下，A*算法計算得出的最終路徑。各圖表示電動(dòng)車(chē)S到各個(gè)充電樁的路徑線(xiàn)路，電動(dòng)車(chē)充電點(diǎn)位模擬實(shí)驗結果如圖3所示。
從S點(diǎn)到A點(diǎn)，預估代價(jià)為10；
從S點(diǎn)到B點(diǎn)，預估代價(jià)為11；
從S點(diǎn)到C點(diǎn)，預估代價(jià)為8；
從S點(diǎn)到D點(diǎn)，預估代價(jià)為9；
從S點(diǎn)到E點(diǎn)，預估代價(jià)為10。比較路徑代價(jià)信息后，最終選取D點(diǎn)位充電樁，作為S點(diǎn)位電動(dòng)車(chē)路徑首選選項，電動(dòng)車(chē)S到各個(gè)充電樁的路徑代價(jià)和電動(dòng)車(chē)S選用C充電樁的最終路徑如圖4所示。
4 結語(yǔ)
A*算法能在進(jìn)行路徑規劃時(shí)，將已知全局環(huán)境地圖信息劃分為網(wǎng)格狀，通過(guò)進(jìn)行節點(diǎn)擴展尋找，搜索判斷下一子節點(diǎn)位置，在全局路徑規劃中，具有高精準度和高效率性。它能快速尋優(yōu)，得到距離代價(jià)最小的最終路徑。本文利用A*算法，對模擬環(huán)境進(jìn)行電動(dòng)車(chē)路徑規劃，通過(guò)分析不同路徑點(diǎn)位的路徑規劃結果，篩選出最小代價(jià)的路徑線(xiàn)路，以此得到路徑規劃最終結果。
參考文獻
［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*
