智能小車路徑選取算法比較

王思雯

摘? 要：為解決智能裝配系統(tǒng)裝配零件運輸最短時間問題，對智能小車在優(yōu)化好的路徑中尋求耗時最短的最優(yōu)路徑，在算法選擇上提供了一些算法的核心思想以及結(jié)果比較。若考慮實際操作運輸過程中的遮擋關(guān)系、障礙物的繞行等實際情況，為此提供了Dijkstra算法、A*算法、JPS算法、A*算法+JPS算法的優(yōu)化這幾個路徑優(yōu)化算法來對路徑進(jìn)行選擇，其中Dijkstra算法搜索速度緩慢;A*算法時間效率上有所提高，但存在計算量過大和內(nèi)耗過大的問題;JPS算法不能適應(yīng)復(fù)雜地形，搜尋時間效率優(yōu)于Dijkstra算法，但遜于A*算法;A*算法+JPS算法的優(yōu)化精度更高，時間效率優(yōu)于前3種算法，建議在智能小車實際應(yīng)用中采用。

關(guān)鍵詞：智能小車? Dijkstra算法? A*算法? JPS算法

中圖分類號：TP301.6? ? ? ? ? ? ? ? ? ? ? ? 文獻(xiàn)標(biāo)識碼：A? ? ? ? ? ? ? ? ? 文章編號：1674-098X（2021）05（c）-0118-03

Comparison of path selection algorithms for smart car

WANG Siwen

（Shenyang Ligong University， Shenyang，Liaoning Province， 110159 China）

Abstract： In order to solve the problem of the shortest transportation time of assembly parts in the intelligent assembly system， the core ideas of some algorithms and the comparison of results are provided for the smart car to seek the shortest time-consuming optimal path in the optimized path. Considering the occlusion relationship in the actual operation and transportation process and the detour of obstacles， Dijkstra algorithm， A* algorithm， JPS algorithm， A* algorithm + JPS algorithm are provided to select the path， in which Dijkstra algorithm has a slow search speed; A* the time efficiency of the algorithm is improved， but there are problems of too much computation and too much internal friction; JPS algorithm can not adapt to complex terrain， and the search time efficiency is better than Dijkstra algorithm， but inferior to A* algorithm. A* algorithm + JPS algorithm has higher optimization accuracy and better time efficiency than the first three algorithms. It is recommended to be applied in the practical application of smart car.

Key Words： Smart car; Dijkstra algorithm; A* algorithm.; JPS algorithm

智能裝配的前提是將貨物零件裝載運輸?shù)讲僮髋_再進(jìn)行零件智能裝配工作，智能小車選取貨物零件的路徑方式多種多樣，最終目的就是使得小車以最優(yōu)路徑和最短時間將貨物零件運送到操作臺。若以移動智能小車選取的貨物零件為起始點運送至操作臺，就要規(guī)劃智能小車的最優(yōu)路徑來避開障礙從而快速運送至操作臺。本文將幾個路徑優(yōu)化算法進(jìn)行對比，其中Dijkstra算法、A*算法、JPS算法在搜尋路徑方面都有較好的表現(xiàn)能力，在A*算法的基礎(chǔ)之上結(jié)合JPS算法進(jìn)行優(yōu)化可以更高效、準(zhǔn)確地完成路徑搜索任務(wù)。

1? Dijkstra算法

算法思想：首先需要制定起始點，還要創(chuàng)建2個合集S和U，S用來存放目前所求頂點到起始點最短路徑的點合集，U則是存放還未求出最短路徑的點，最后還要有一個數(shù)組用來存放源點到其他點的距離，開始時都設(shè)置為無窮大，以最短路徑為原則更新數(shù)組。算法起始源點則為起始點，S中只包含源點，而U中有除源點外的所有頂點，從集合U中選出離起始點距離最短的點，并將該頂點從集合U中刪除，加入集合S中，接著更新該頂點到源點的最短距離數(shù)值。后面的操作步驟則是以上一步驟求出的最短路徑的頂點為操作對象進(jìn)行相鄰路徑的延伸計算，直到遍歷完所有頂點。成功率高，但搜索速度較為緩慢，如圖1所示，搜索幾乎遍歷所有網(wǎng)格，假設(shè)每個柵格的長度為1，則遍歷時間在37ms左右，規(guī)劃路徑長度為26.31，搜尋節(jié)點2305個。

2? A*算法

A*算法的基本思想可以概括為以起點開始不停地搜索周圍的點（起始為8個點，已經(jīng)被列為周圍點的不會重復(fù)標(biāo)記，阻擋也不會標(biāo)記），再選出一個新的點（最優(yōu)點）作為再進(jìn)行循環(huán)搜索的起點，直至找到目標(biāo)點。先創(chuàng)建2個列表，一個開啟列表，用來儲存起始點為始的周圍點的尋路消耗;一個關(guān)閉列表，起始時就儲存起始點，之后儲存在列表中排序?qū)ぢ废淖钚〉狞c。需要注意的是，每次把周圍的點放入起始列表時需要進(jìn)行判斷。（1）該點是不是阻擋點;（2）該點是否在開啟列表或關(guān)閉列表中，以便周圍生成的點都是新的點。同樣在關(guān)閉列表中也要判斷每次尋到的最優(yōu)點是不是終點，若為終點則停止尋路，否則繼續(xù)。但到目前為止，關(guān)閉列表中的最優(yōu)點并不是最終的最優(yōu)路徑。如何根據(jù)關(guān)閉列表中的最優(yōu)點尋找最優(yōu)路徑，這里將開啟列表中的點都進(jìn)行父格子記錄標(biāo)識，當(dāng)最后關(guān)閉列表遍歷完成之后，再以終點父格子目的進(jìn)行路徑回溯，即從終點開始尋找上一個最優(yōu)點的父格子路徑進(jìn)行輸出[1-3]。但A*算法存在嚴(yán)重的計算量過大和內(nèi)耗過大問題，遍歷時間為4.7150ms，規(guī)劃路徑長度為26.31，搜尋節(jié)點286個，效率相較Dijkstra算法明顯提高，如圖2所示。

3? JPS算法

JPS算法的核心思想為根據(jù)當(dāng)前點及周圍點的特點來進(jìn)行選擇達(dá)到符合條件的點才能加入關(guān)閉列表或從開始列表中刪除的操作。流程大致與A*算法相同，以尋找跳點作為搜索節(jié)點來進(jìn)行遍歷。首先強迫鄰居的概念為當(dāng)前節(jié)點的周圍鄰居點周圍有障礙時，且父節(jié)點到當(dāng)前節(jié)點再到周圍鄰居節(jié)點的距離比父節(jié)點到其他點再到周圍鄰居點的值小，稱這樣的點為強迫鄰居[4]。跳點的定義為，以鄰居節(jié)點為原則，其一，若當(dāng)前點有強迫鄰居，則該點為跳點;其二，若該點為目的節(jié)點，則該點也為跳躍節(jié)點。與A*算法一樣，都是在開始列表和關(guān)閉列表當(dāng)中進(jìn)行加入和刪除的操作，只不過JPS算法是以強迫鄰居和跳點搜尋作為尋找準(zhǔn)則進(jìn)行遍歷。但JPS的缺點也很明顯，圖上的邊不能帶權(quán)重，也就是只能在較為規(guī)則的地圖上進(jìn)行搜尋操作，不能適應(yīng)復(fù)雜地形[5-6]。如圖3所示，遍歷時間為9.3350ms，路徑規(guī)劃長度為26.31，搜尋節(jié)點1919個。

4? A*算法+JPS算法的優(yōu)化

為解決A*算法速度慢內(nèi)耗過大的問題，提出了改進(jìn)A*算法并融合JPS算法的方法，如圖4所示。首先改進(jìn)A*算法評價函數(shù)（尋路消耗函數(shù)）的計算方式，在柵格圖形應(yīng)用實踐上來看，以八方向為移動準(zhǔn)則的話，物體的實際移動距離必定要大于A*算法自帶的歐式距離值，而使用切比雪夫距離算法改進(jìn)這個評價函數(shù)就可以很好地解決這個問題，開啟列表中的尋路消耗路徑值就可以為實際路徑值，提高精度。接著在JPS算法的策略下改進(jìn)A*算法，中心思想也是去除A*算法帶來的巨大計算量和內(nèi)耗。在進(jìn)入算法前先將節(jié)點進(jìn)行預(yù)處理，即將節(jié)點中的跳點和被迫鄰居篩選出來，篩選方法與JPS算法的處理方式一致，相比于之前A*算法每個格子走一次的結(jié)果來看，以JPS算法為思想的算法的處理速度要快得多，一次處理跳躍的距離邊長，精度也更高，效率也提高很多[7-9]。

5? 結(jié)語

在選擇運輸零件的方式時，各算法都有著相對的優(yōu)點和缺點。在柵格圖形中，A*算法+JPS算法的優(yōu)化也存在著路徑曲折不夠平滑的缺點，但A*算法+JPS算法的優(yōu)化是最好的選擇。

參考文獻(xiàn)

[1] 張志文，張鵬，毛虎平，等.改進(jìn)A*算法的機器人路徑規(guī)劃研究[J].電光與控制，2021，28（4）：21-25.

[2] 張丹紅，陳文文，張華軍，等.A～*算法與蟻群算法相結(jié)合的無人艇巡邏路徑規(guī)劃[J].華中科技大學(xué)學(xué)報：自然科學(xué)版，2020，48（6）：13-18.

[3] 任紅格，胡鴻長，史濤.基于改進(jìn)蟻群算法的移動機器人全局路徑規(guī)劃[J].華北理工大學(xué)學(xué)報：自然科學(xué)版，2021，43（2）：102-109.

[4] 馬小陸，梅宏，王兵，等.基于JPS策略的改進(jìn)RRT～*移動機器人全局路徑規(guī)劃算法[J].中國慣性技術(shù)學(xué)報，2020，28（6）：761-768.

[5] 劉輝，肖克，王京擘.基于改進(jìn)蟻群算法的無人礦車路徑規(guī)劃研究[J].制造業(yè)自動化，2021，43（4）：108-112.

[6] 黃健萌，吳宇雄，林謝昭.移動機器人平滑JPS路徑規(guī)劃與軌跡優(yōu)化方法[J].農(nóng)業(yè)機械學(xué)報，2021，52（2）：21-29，121.

[7] None.JPS volume 51 issue 2 Cover and Back matter[J].British Journal of Political Science，2021，51（2）：23-26.

[8] 任云青.智能乒乓球自動撿球機器人的設(shè)計與實現(xiàn)[D].南京：南京郵電大學(xué)，2020.

[9] 郭健.機器人路徑規(guī)劃算法研究與應(yīng)用[D].包頭：內(nèi)蒙古科技大學(xué)，2020.