999精品在线视频,手机成人午夜在线视频,久久不卡国产精品无码,中日无码在线观看,成人av手机在线观看,日韩精品亚洲一区中文字幕,亚洲av无码人妻,四虎国产在线观看 ?

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

2021-09-17 08:31:09王思雯
科技創(chuàng)新導(dǎo)報 2021年15期

王思雯

摘? 要:為解決智能裝配系統(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.

主站蜘蛛池模板: 欧美性久久久久| 99久久精品久久久久久婷婷| 永久免费无码日韩视频| 四虎影视永久在线精品| 欧美成人免费一区在线播放| 欧洲高清无码在线| 色AV色 综合网站| 爱做久久久久久| 亚洲日韩每日更新| 免费国产好深啊好涨好硬视频| 久久久国产精品免费视频| 国产成人免费视频精品一区二区 | 一级毛片中文字幕| av在线无码浏览| 天天干伊人| 国产sm重味一区二区三区| 在线观看网站国产| 欧美精品啪啪一区二区三区| 欧美一区二区三区欧美日韩亚洲| 欧美第一页在线| 国产精品免费福利久久播放| 国产呦视频免费视频在线观看| 在线中文字幕日韩| 97视频在线观看免费视频| 麻豆精品视频在线原创| 国内精自视频品线一二区| 国产97视频在线| 国产成人综合网| 国产欧美成人不卡视频| 日韩欧美91| 国产情侣一区| 亚洲香蕉在线| 免费日韩在线视频| 欧美一区精品| 国产91在线|中文| 久久久久久国产精品mv| 久久婷婷五月综合色一区二区| 69av免费视频| 91娇喘视频| 久久人体视频| 国产精品30p| 国产九九精品视频| 97人人做人人爽香蕉精品| 久久国产免费观看| 精品视频第一页| 国产在线精彩视频二区| 免费一级毛片在线播放傲雪网| 国产偷国产偷在线高清| 99久久国产自偷自偷免费一区| 米奇精品一区二区三区| 国产激情无码一区二区APP | 97精品久久久大香线焦| 97成人在线观看| 日本a级免费| 色悠久久久| 国产h视频免费观看| 欧美人与牲动交a欧美精品| 又黄又湿又爽的视频| 亚洲欧美一区二区三区麻豆| 国产无码网站在线观看| 久久熟女AV| 蜜芽一区二区国产精品| 亚洲综合中文字幕国产精品欧美 | 国产91高清视频| 午夜影院a级片| 亚洲成人动漫在线| 熟女视频91| www.99在线观看| 久久青草视频| 日本成人不卡视频| 国产资源免费观看| 最新国产网站| 好久久免费视频高清| 中国丰满人妻无码束缚啪啪| 五月婷婷综合在线视频| 亚洲天堂视频网| 欧美成人区| 91人妻日韩人妻无码专区精品| 久久精品国产电影| 国产无码性爱一区二区三区| 国产精品偷伦在线观看| 热久久这里是精品6免费观看|