針對目前路徑規(guī)劃容易陷入局部最優(yōu)和搜索時間較長的問題,提出基于拓?fù)湮恢藐P(guān)系的無人艇路徑搜索方法。分析空間物體的拓?fù)湮恢藐P(guān)系,構(gòu)建基于拓?fù)湮恢藐P(guān)系的地圖表達(dá)。在地圖要素表達(dá)、拓?fù)潢P(guān)系謂詞和拓?fù)渎窂娇蛇_(dá)的基礎(chǔ)上建立拓?fù)涞貓D,避免大量網(wǎng)格化的路徑搜索造成時間復(fù)雜度提升,同時避免搜索陷入局部最小值。采用Dijkstra算法對建立的拓?fù)涞貓D進(jìn)行最優(yōu)路徑選擇。試驗(yàn)結(jié)果表明:在障礙物不變、搜索范圍變大的情況下,該方法相比柵格化的A*算法能以較低的搜索時間實(shí)現(xiàn)更優(yōu)路徑的搜索。 

【文章來源】：中國航海. 2019,42(02)北大核心

【文章頁數(shù)】：7 頁

【部分圖文】：

基于拓?fù)湮恢藐P(guān)系的可達(dá)路徑地圖

圖3基于拓?fù)湮恢藐P(guān)系的可達(dá)路徑地圖2．2路徑搜索基于Dijsktra算法的路徑選擇流程見圖4，對基于拓?fù)湮恢藐P(guān)系的可達(dá)路徑進(jìn)行計(jì)算。首先，讀取基于拓?fù)湮恢藐P(guān)系判斷的可達(dá)路徑點(diǎn)集P的信息，并設(shè)置起點(diǎn)S與目的點(diǎn)E之間的位置關(guān)系數(shù)據(jù)。定義未訪問點(diǎn)集U和已訪問點(diǎn)集V=P－U，計(jì)算所有已訪問點(diǎn)集V到未訪問點(diǎn)集U的值du，從未訪問點(diǎn)集U中選取du中最小的點(diǎn)i，從已訪問點(diǎn)集V中查找與i點(diǎn)直接連接的點(diǎn)，記為Pi，將i點(diǎn)位置數(shù)據(jù)添加進(jìn)已訪問的點(diǎn)集V，直到Num≥P時結(jié)束搜索，計(jì)算出路徑。經(jīng)過上述計(jì)算，得出起始點(diǎn)S到目標(biāo)點(diǎn)E的最短路徑見圖5。圖5中的線條為最短路徑，最短路徑為(S，B74，B73，B91，E)，距離為1200m。圖4基于Dijsktra算法的路徑選擇流程2．3安全距離和船舶旋回圈USV通常是一個欠驅(qū)動系統(tǒng)，無法完全按照規(guī)劃的路徑行駛�？紤]到船舶在航行過程中必然會出現(xiàn)路徑上的偏差，在設(shè)計(jì)路徑和搜索時應(yīng)留有安全距離。此外，船舶轉(zhuǎn)向時的旋回半徑也與船舶圖5基于拓?fù)涞貓D求解的最短路徑的操縱性能有關(guān)，需在安全上予以考慮。為簡化起見，通常會對障礙物進(jìn)行邊界上的膨脹，留一定的水域作為船舶安全緩沖區(qū)。在空間分析中，該操作稱為緩沖區(qū)操作(Buffer)。緩沖區(qū)半徑可取USV預(yù)留安全距離和旋回半徑中的較大者，以確保船舶安全航行。對障礙物進(jìn)行緩沖區(qū)操作之后，仍是第1．1節(jié)中所述的一個簡單要素，不影響上述拓?fù)涞貓D構(gòu)建和路徑搜索算法的實(shí)施。3試驗(yàn)及分析為驗(yàn)證該拓?fù)涞貓D構(gòu)建及路徑搜索算法的有效性，設(shè)計(jì)試驗(yàn)對本文的算法和基于柵?

叵檔目紗锫肪督?屑撲?。首先，讀取基于拓?fù)湮恢藐P(guān)系判斷的可達(dá)路徑點(diǎn)集P的信息，并設(shè)置起點(diǎn)S與目的點(diǎn)E之間的位置關(guān)系數(shù)據(jù)。定義未訪問點(diǎn)集U和已訪問點(diǎn)集V=P－U，計(jì)算所有已訪問點(diǎn)集V到未訪問點(diǎn)集U的值du，從未訪問點(diǎn)集U中選取du中最小的點(diǎn)i，從已訪問點(diǎn)集V中查找與i點(diǎn)直接連接的點(diǎn)，記為Pi，將i點(diǎn)位置數(shù)據(jù)添加進(jìn)已訪問的點(diǎn)集V，直到Num≥P時結(jié)束搜索，計(jì)算出路徑。經(jīng)過上述計(jì)算，得出起始點(diǎn)S到目標(biāo)點(diǎn)E的最短路徑見圖5。圖5中的線條為最短路徑，最短路徑為(S，B74，B73，B91，E)，距離為1200m。圖4基于Dijsktra算法的路徑選擇流程2．3安全距離和船舶旋回圈USV通常是一個欠驅(qū)動系統(tǒng)，無法完全按照規(guī)劃的路徑行駛�？紤]到船舶在航行過程中必然會出現(xiàn)路徑上的偏差，在設(shè)計(jì)路徑和搜索時應(yīng)留有安全距離。此外，船舶轉(zhuǎn)向時的旋回半徑也與船舶圖5基于拓?fù)涞貓D求解的最短路徑的操縱性能有關(guān)，需在安全上予以考慮。為簡化起見，通常會對障礙物進(jìn)行邊界上的膨脹，留一定的水域作為船舶安全緩沖區(qū)。在空間分析中，該操作稱為緩沖區(qū)操作(Buffer)。緩沖區(qū)半徑可取USV預(yù)留安全距離和旋回半徑中的較大者，以確保船舶安全航行。對障礙物進(jìn)行緩沖區(qū)操作之后，仍是第1．1節(jié)中所述的一個簡單要素，不影響上述拓?fù)涞貓D構(gòu)建和路徑搜索算法的實(shí)施。3試驗(yàn)及分析為驗(yàn)證該拓?fù)涞貓D構(gòu)建及路徑搜索算法的有效性，設(shè)計(jì)試驗(yàn)對本文的算法和基于柵格的A*搜索算法進(jìn)行對比。3．1試驗(yàn)環(huán)境和工具仿真試驗(yàn)程序運(yùn)行環(huán)境中的CPU為i5-8400的6核2．80GH

【參考文獻(xiàn)】：
期刊論文
[1]基于元拓?fù)潢P(guān)系的線面空間關(guān)系集成表達(dá)模型[J]. 曹亞妮,吳芳華,王麗君,李嘉星.  武漢大學(xué)學(xué)報(信息科學(xué)版). 2016(01)
[2]復(fù)合面狀對象拓?fù)潢P(guān)系的表達(dá)模型[J]. 陳占龍,馮齊奇,吳信才.  測繪學(xué)報. 2015(04)
[3]分布式空間數(shù)據(jù)分片與跨邊界拓?fù)溥B接優(yōu)化方法[J]. 朱欣焰,周春輝,咼維,夏宇.  軟件學(xué)報. 2011(02)
[4]能表達(dá)帶洞區(qū)域拓?fù)潢P(guān)系的擴(kuò)展9-交集模型[J]. 歐陽繼紅,霍林林,劉大有,富倩.  吉林大學(xué)學(xué)報(工學(xué)版). 2009(06)

碩士論文
[1]無人駕駛救助船路徑規(guī)劃算法的研究[D]. 陳佳.武漢理工大學(xué) 2013



本文編號：2983594