基于A*算法的定制化無人駕駛公交路徑規(guī)劃方法

葉德超，謝振東，董志國，于潔涵，徐華全

（1.廣東工業(yè)大學(xué)自動化學(xué)院，廣州 510000；2.廣州市公共交通集團(tuán)有限公司，廣州 510000；3.廣州羊城通有限公司，廣州 510000）

近年來，隨著自動駕駛技術(shù)的發(fā)展，智能交通領(lǐng)域也得到了革命性的發(fā)展。為了解決城市交通問題，政府一直以來都在大力倡導(dǎo)公共出行[1]，而定制化無人駕駛公交無疑為市民提供了一種新的公共出行方式[2]。馬昌喜等[3]從定制公交線路優(yōu)化目標(biāo)、問題場景和求解算法3 個方面對相關(guān)文獻(xiàn)進(jìn)行了歸類分析。魏晨曦等[4]對定制公交潛在客流識別與選址、線網(wǎng)規(guī)劃、運營管理3個方面進(jìn)行了綜述，并分析了未來我國定制化公交可能的研究方向。郭嫚[5]結(jié)合定制公交線路規(guī)劃中的滿載率、停靠點個數(shù)、繞行距離等約束條件，從乘客、企業(yè)、社會3 個角度入手建立需求可拆分的目標(biāo)函數(shù)，構(gòu)建了基于多點對多點開行模式的定制化公交路徑規(guī)劃模型。

路徑規(guī)劃是自動駕駛的一個關(guān)鍵環(huán)節(jié)，一直以來都是自動駕駛領(lǐng)域的研究重點之一。路徑規(guī)劃主要分為全局路徑規(guī)劃和局部路徑規(guī)劃。張珂、李永丹等[6-8]對無人駕駛車輛路徑規(guī)劃算法進(jìn)行了綜述，分析了各類算法的優(yōu)缺點。

其中A*（A-Star）算法在路徑規(guī)劃應(yīng)用中優(yōu)勢較為明顯，A*算法是一種靜態(tài)路網(wǎng)中求解最短路徑最有效的直接搜索方法，也是解決許多搜索問題的有效算法[9-10]。算法中的距離估算值與實際值越接近，最終搜索速度越快。但A*算法的搜索目標(biāo)是獲得最短路徑，而對于定制化無人駕駛公交的運營目標(biāo)則是行駛盡可能少的距離將盡可能多的乘客送到目的地，以達(dá)到降低運營成本，提高乘客出行體驗的目標(biāo)。

本文對A*算法進(jìn)行改進(jìn)，使路徑規(guī)劃算法符合定制化無人駕駛公交的運營要求，使企業(yè)和乘客的共同利益最大化。

1 定制化無人駕駛公交運營模式

以滿載10 人的微型無人駕駛小巴運行在全長5 km的人口密集地區(qū)作為運行場景，參考出租車的?？刻攸c，微型小巴憑借較小的車輛體積可以停靠在有停車條件的公交站或者標(biāo)志性路口。信息處理中心集中處理乘客的訂單，對乘客的出行需求進(jìn)行整合后，向無人駕駛小巴下達(dá)調(diào)度指令，提供路徑規(guī)劃方案。

根據(jù)整合的出行訂單可以將任務(wù)分為2 種不同的模式。第一種，每一名乘客的出行起點和終點都不相同，沒有重合的起點和目的地；第二種，存在有重合的起點或目的地，即無人駕駛公交可能在某一個地方接送到多名乘客。

第一種，通過多次使用A*算法進(jìn)行規(guī)劃路線，每次路徑規(guī)劃都是以獲得離當(dāng)前點的距離最短為目標(biāo)。

第二種，如果單純使用A*算法進(jìn)行路徑規(guī)劃，可能會出現(xiàn)以下3 種情況：①起點A 點離目標(biāo)點C點2 km，離目標(biāo)點B 點3 km，無論從A 點到C 點的乘客人數(shù)大于還是小于從A 點到B 點的人數(shù)，算法均會選擇優(yōu)先到達(dá)C 點，這是因為算法的目標(biāo)就是獲得最短距離；②起點A 點離目標(biāo)點C 和目標(biāo)點B 的距離相等，但從A 點到C 點的乘客人數(shù)少于從A 點到B點的乘客人數(shù)，算法仍有可能選擇優(yōu)先到達(dá)C 點；③如圖1所示，起點A 點離目標(biāo)點C 點2 km，離下一個起點B點3 km，起點B 點離目標(biāo)點C 點3 km，A 點和B點均有乘客需要到C 點，算法可能會選擇從A 點到C點，C點到B點，B 點再回 C 點，這樣總距離為 2 km +3 km+3 km=8 km，但如果能從A 點到B 點，B 點到C點，則總距離為3 km+3 km=6 km。明顯后一種方案行駛距離較短。

圖1 點A、B、C 分布

無人駕駛公交自動化程度高，尤其微型小巴很適合解決最后一公里的交通問題。路徑規(guī)劃算法在提高運營效率，降低企業(yè)的成本，提高乘客的出行體驗等方面起著關(guān)鍵性的作用，單純使用A*算法進(jìn)行路徑規(guī)劃可能會出現(xiàn)上述路線不夠合理的情況，因此根據(jù)運營的實際情況對算法進(jìn)行優(yōu)化是十分必要的。

2 算法介紹

2.1 A*算法

A*算法于1968年，由Stanford 研究院的Peter Hart，Nils Nilsson 及Bertram Raphael 發(fā)表，其被認(rèn)為是Dijkstra 算法的擴展。A*算法是一種靜態(tài)路網(wǎng)中求解最短路徑最有效的直接搜索方法，也是解決許多搜索問題的啟發(fā)式算法，啟發(fā)式探索是利用問題擁有的啟發(fā)信息來引導(dǎo)搜索，達(dá)到減少探索范圍，降低問題復(fù)雜度的目的。算法中的距離估算值與實際值越接近，最終搜索速度越快。

算法的公式表示為：f*（s）=g*（s）+h*（s），式中：f*（s）為從初始狀態(tài)經(jīng)由狀態(tài)s 到目標(biāo)狀態(tài)的最小代價估計，g*（s）為在狀態(tài)空間中從初始狀態(tài)到狀態(tài)s 的最小代價；h*（s）是從狀態(tài)s 到目標(biāo)狀態(tài)的路徑的最小估計代價。

算法的主要運行步驟如下：

（1）將初始節(jié)點放入到open 列表中。

（2）判斷open 列表。如果為空，則搜索失敗。如果open 列表中存在目標(biāo)節(jié)點，則搜索成功。

（3）從open 列表中取出f 值最小的節(jié)點作為當(dāng)前節(jié)點，并將其加入到close 列表中。

（4）計算當(dāng)前節(jié)點相鄰的所有可達(dá)節(jié)點，然后生成一組子節(jié)點。而對于每一個子節(jié)點：①如果該節(jié)點在close 列表中，則拋棄它。②如果該節(jié)點在open 列表中，則檢查其通過當(dāng)前節(jié)點計算得到的f 值是否更小。③如果更小則更新其f 值，并將其父節(jié)點設(shè)置為當(dāng)前節(jié)點。如果該節(jié)點不在open 列表中，則將其加入到open 列表，并計算f 值，設(shè)置其父節(jié)點為當(dāng)前節(jié)點。

（5）轉(zhuǎn)到2 步驟。

2.2 改進(jìn)A*算法

為了將傳統(tǒng)的A*算法更好地應(yīng)用在定制化無人駕駛公交上，需要對算法進(jìn)行改進(jìn)。改進(jìn)主要如下：

（1）加入乘客人數(shù)n 的約束，當(dāng)出現(xiàn)2 個或者2 個以上離起點距離相等的終點時，應(yīng)考慮到目標(biāo)點的乘客人數(shù)，即此時優(yōu)先考慮選擇人均距離最短的目標(biāo)點，將算法考慮的單純路徑距離改為人均距離進(jìn)行路徑規(guī)劃。

（2）當(dāng)不存在重合的起點或終點時，假設(shè)出現(xiàn)當(dāng)前點到2 個或2 個以上目標(biāo)點的距離相同時，優(yōu)先將先上車的乘客送到對應(yīng)的終點，以減少乘客的通勤時間。

（3）當(dāng)存在不同起點的乘客有重合的目標(biāo)點的情況時，假設(shè)當(dāng)前起點A 點離下一個起點B 點的距離小于到目標(biāo)點C 點的距離，則優(yōu)先選擇先到B 點，但起點A 點離目標(biāo)點C 點距離較短時，則需要進(jìn)行評估，分別考慮先送車上乘客到目標(biāo)點之后再接下一起點的乘客即A→C→B→C 還是先接下一個起點的乘客之后再統(tǒng)一將乘客送到目標(biāo)點即A→B→C 的距離較短，如出現(xiàn)2 種方法距離相等時，則應(yīng)選擇先將當(dāng)前車上乘客先送到目標(biāo)點，以減少這部分乘客的通勤時間。流程如圖2所示。

圖2 改進(jìn)算法流程圖

3 仿真驗證與分析

3.1 程序運行主要流程

為了測試算法的有效性，使用matlab 仿真軟件進(jìn)行仿真測試，仿真獲得路徑規(guī)劃路線，程序主要流程如圖3所示。

圖3 程序主要流程圖

本算法以A*算法為基礎(chǔ)，根據(jù)乘客的出行需求情況分為2 類，無重合起點和終點及有重合起點或終點2 種模式，不同模式進(jìn)行路徑規(guī)劃時，進(jìn)行相關(guān)條件的約束，然后使用改進(jìn)的A*算法進(jìn)行路徑規(guī)劃，直到將所有的點處理完為止，最終獲得完整的路線圖。

3.2 仿真的主要參數(shù)

仿真主要參數(shù)見表1、表2。

表2 實驗2 參數(shù)表

3.3 實驗結(jié)果及分析

3.3.1 實驗1

實驗1 以5 名乘客均有不同的出發(fā)點和終點為例，在不同地形下進(jìn)行路徑規(guī)劃仿真實驗（圖4—圖7）。

圖4 實驗1 第1 組運行結(jié)果圖

圖5 實驗1 第2 組運行結(jié)果圖

圖6 實驗1 第3 組運行結(jié)果圖

圖7 實驗1 第4 組運行結(jié)果圖

實驗在20×20 的地圖下進(jìn)行路徑規(guī)劃，黑色部分為障礙物，4 組圖的地形均不相同，程序平均運行時間約4.32 s。從實驗結(jié)果可以看出，第1 組的路徑規(guī)劃為：AB→BE→EF→FI→IH→HJ→JD→DC→CG，而第2,3,4組的路徑規(guī)劃均為：AB→BE→EF→FH→HI→IJ→JD→DC→CG?？梢钥闯鲈谶@種情況下多次調(diào)用A*算法可以實現(xiàn)多點路徑規(guī)劃功能，第1 組和其余3 組的路徑規(guī)劃情況略有不同，這是因為該算法考慮障礙物的影響，以實際可行路線的距離為準(zhǔn)，搜索最短的行駛距離，并且算法規(guī)定必須先到起點，才能把起點對應(yīng)的終點添加到路徑規(guī)劃線路中，符合定制化無人駕駛公交的實際運營情況。

3.3.2 實驗2

實驗2 以6 名乘客存在有相同的出發(fā)點或終點的情況為例，進(jìn)行路徑規(guī)劃仿真實驗（圖8—圖9）。

實驗在20×20 的地圖下進(jìn)行路徑規(guī)劃，黑色部分為障礙物，從實驗結(jié)果可以看出，第1 組和第2 組的路徑規(guī)劃為：AC→CE→ED→DB→BI→IF→FH→HG，即S1（S2、S3）→S4→G1→G2（G4）→S6→G6→S5→G3，第1組S1（4，5）到G1（4，3）的距離大于S1（4，5）到S4（6，6）的距離，但圖中選擇了先到S4（6，6），第2 組S1（4，5）到G1（4，3）的距離小于S1（4，5）到S4（6，6）的距離，圖中仍選擇了先到S4（6，6）。這是因為改進(jìn)的算法在遇到這種情況時需要進(jìn)行分析判斷，在路徑規(guī)劃前，對各坐標(biāo)點進(jìn)行了分類，分為起點和終點，如圖8所示，當(dāng)前點到最近的起點的距離小于最近的終點時，優(yōu)先選擇了先到最近的起點，但當(dāng)前點到最近的起點的距離大于最近的終點時，如圖9所示，則需要進(jìn)行判斷，圖9實驗結(jié)果所示，dis（S1→G1）＜dis（S1→S4），S1（4，5）和S4（6，6）分別有一名乘客的目標(biāo)點為（4，3），此時計算可知dis（S1→G1）+dis（G1→S4）+dis（S4→G1）＞dis（S1→S4）+dis（S4→G1），所以優(yōu)先選擇了S1（S2、S3）→S4→G1的路線。

圖8 實驗2 第1 組運行結(jié)果圖

圖9 實驗2 第2 組運行結(jié)果圖

4 結(jié)論與展望

4.1 結(jié)論

定制化無人駕駛公交是自動駕駛技術(shù)和定制化公交運營模式相結(jié)合的成果。無人駕駛公交自動化程度高，其路徑規(guī)劃方法關(guān)系著其運行的效率和安全性。同時，微型無人駕駛小巴車輛體積小，停靠的位置更加靈活，不限于?？抗徽军c，比較適合解決最后一公里的交通問題。定制化公交作為一種新的運營模式，其目標(biāo)是滿足乘客的個性化出行需求且有通勤效率更高，通勤成本更低的優(yōu)勢，同時也能降低企業(yè)的運營成本，提高公共交通行業(yè)的競爭力。所以，對乘客的需求進(jìn)行整合，做好路徑規(guī)劃尤其重要。傳統(tǒng)A*算法的目標(biāo)是獲得最短路徑，如果直接應(yīng)用到定制化無人駕駛公交上可能會出現(xiàn)路徑雖然可行但不夠合理的問題，本文針對這個問題對A*算法進(jìn)行了改進(jìn)，加入乘客數(shù)量和重合點的約束，優(yōu)化了調(diào)用算法的條件，使其更符合定制化無人駕駛公交的實際運營特點，從仿真結(jié)果來看，改進(jìn)的算法能夠?qū)崿F(xiàn)多點路徑規(guī)劃功能，并且能夠根據(jù)實際情況進(jìn)行方案調(diào)整，減少了行駛的距離，能夠為定制化無人駕駛公交的實際運營提供參考方案。

4.2 展望

從仿真結(jié)果來看，本文論述的方法雖然能夠有效地應(yīng)用在定制化無人駕駛公交的路徑規(guī)劃上，且能達(dá)到較為滿意的效果，但在算法運算效率方面仍有提升的空間，本人希望后續(xù)繼續(xù)探索算法的改進(jìn)以及與其他算法的優(yōu)勢互補。同時，在實際路況中，可能會有更多本文沒有考慮到的因素，本文論述的路徑規(guī)劃方法僅在仿真軟件做了仿真實驗，而在實際路段上能否安全有效且穩(wěn)定地應(yīng)用在無人駕駛公交車上仍需做更多的實際運營測試和調(diào)研。不但如此，本文的研究是基于理想狀態(tài)下把行駛距離作為運行成本，沒有考慮到實際道路擁堵情況、能源以及其他管理成本，后續(xù)應(yīng)考慮更多其他的相關(guān)因素來作進(jìn)一步優(yōu)化。除此之外，如何平衡企業(yè)的利益和乘客的利益仍需要作更多的研究。