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

王思雯

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

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

中圖分類號(hào)：TP301.6? ? ? ? ? ? ? ? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A? ? ? ? ? ? ? ? ? 文章編號(hào)：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

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

1? Dijkstra算法

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

2? A*算法

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

3? JPS算法

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

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

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

5? 結(jié)語(yǔ)

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

參考文獻(xiàn)

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

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

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

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

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

[6] 黃健萌，吳宇雄，林謝昭.移動(dòng)機(jī)器人平滑JPS路徑規(guī)劃與軌跡優(yōu)化方法[J].農(nóng)業(yè)機(jī)械學(xué)報(bào)，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] 任云青.智能乒乓球自動(dòng)撿球機(jī)器人的設(shè)計(jì)與實(shí)現(xiàn)[D].南京：南京郵電大學(xué)，2020.

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