基于拓撲位置關(guān)系的無人艇路徑搜索方法
發(fā)布時間：2021-01-17 21:07
針對目前路徑規(guī)劃容易陷入局部最優(yōu)和搜索時間較長的問題,提出基于拓撲位置關(guān)系的無人艇路徑搜索方法。分析空間物體的拓撲位置關(guān)系,構(gòu)建基于拓撲位置關(guān)系的地圖表達。在地圖要素表達、拓撲關(guān)系謂詞和拓撲路徑可達的基礎(chǔ)上建立拓撲地圖,避免大量網(wǎng)格化的路徑搜索造成時間復雜度提升,同時避免搜索陷入局部最小值。采用Dijkstra算法對建立的拓撲地圖進行最優(yōu)路徑選擇。試驗結(jié)果表明:在障礙物不變、搜索范圍變大的情況下,該方法相比柵格化的A*算法能以較低的搜索時間實現(xiàn)更優(yōu)路徑的搜索。
【文章來源】：中國航海. 2019,42(02)北大核心
【文章頁數(shù)】：7 頁
【部分圖文】：
基于拓撲位置關(guān)系的可達路徑地圖
圖3基于拓撲位置關(guān)系的可達路徑地圖2．2路徑搜索基于Dijsktra算法的路徑選擇流程見圖4，對基于拓撲位置關(guān)系的可達路徑進行計算。首先，讀取基于拓撲位置關(guān)系判斷的可達路徑點集P的信息，并設(shè)置起點S與目的點E之間的位置關(guān)系數(shù)據(jù)。定義未訪問點集U和已訪問點集V=P－U，計算所有已訪問點集V到未訪問點集U的值du，從未訪問點集U中選取du中最小的點i，從已訪問點集V中查找與i點直接連接的點，記為Pi，將i點位置數(shù)據(jù)添加進已訪問的點集V，直到Num≥P時結(jié)束搜索，計算出路徑。經(jīng)過上述計算，得出起始點S到目標點E的最短路徑見圖5。圖5中的線條為最短路徑，最短路徑為(S，B74，B73，B91，E)，距離為1200m。圖4基于Dijsktra算法的路徑選擇流程2．3安全距離和船舶旋回圈USV通常是一個欠驅(qū)動系統(tǒng)，無法完全按照規(guī)劃的路徑行駛。考慮到船舶在航行過程中必然會出現(xiàn)路徑上的偏差，在設(shè)計路徑和搜索時應留有安全距離。此外，船舶轉(zhuǎn)向時的旋回半徑也與船舶圖5基于拓撲地圖求解的最短路徑的操縱性能有關(guān)，需在安全上予以考慮。為簡化起見，通常會對障礙物進行邊界上的膨脹，留一定的水域作為船舶安全緩沖區(qū)。在空間分析中，該操作稱為緩沖區(qū)操作(Buffer)。緩沖區(qū)半徑可取USV預留安全距離和旋回半徑中的較大者，以確保船舶安全航行。對障礙物進行緩沖區(qū)操作之后，仍是第1．1節(jié)中所述的一個簡單要素，不影響上述拓撲地圖構(gòu)建和路徑搜索算法的實施。3試驗及分析為驗證該拓撲地圖構(gòu)建及路徑搜索算法的有效性，設(shè)計試驗對本文的算法和基于柵?
叵檔目紗锫肪督?屑撲?。首先，讀取基于拓撲位置關(guān)系判斷的可達路徑點集P的信息，并設(shè)置起點S與目的點E之間的位置關(guān)系數(shù)據(jù)。定義未訪問點集U和已訪問點集V=P－U，計算所有已訪問點集V到未訪問點集U的值du，從未訪問點集U中選取du中最小的點i，從已訪問點集V中查找與i點直接連接的點，記為Pi，將i點位置數(shù)據(jù)添加進已訪問的點集V，直到Num≥P時結(jié)束搜索，計算出路徑。經(jīng)過上述計算，得出起始點S到目標點E的最短路徑見圖5。圖5中的線條為最短路徑，最短路徑為(S，B74，B73，B91，E)，距離為1200m。圖4基于Dijsktra算法的路徑選擇流程2．3安全距離和船舶旋回圈USV通常是一個欠驅(qū)動系統(tǒng)，無法完全按照規(guī)劃的路徑行駛。考慮到船舶在航行過程中必然會出現(xiàn)路徑上的偏差，在設(shè)計路徑和搜索時應留有安全距離。此外，船舶轉(zhuǎn)向時的旋回半徑也與船舶圖5基于拓撲地圖求解的最短路徑的操縱性能有關(guān)，需在安全上予以考慮。為簡化起見，通常會對障礙物進行邊界上的膨脹，留一定的水域作為船舶安全緩沖區(qū)。在空間分析中，該操作稱為緩沖區(qū)操作(Buffer)。緩沖區(qū)半徑可取USV預留安全距離和旋回半徑中的較大者，以確保船舶安全航行。對障礙物進行緩沖區(qū)操作之后，仍是第1．1節(jié)中所述的一個簡單要素，不影響上述拓撲地圖構(gòu)建和路徑搜索算法的實施。3試驗及分析為驗證該拓撲地圖構(gòu)建及路徑搜索算法的有效性，設(shè)計試驗對本文的算法和基于柵格的A*搜索算法進行對比。3．1試驗環(huán)境和工具仿真試驗程序運行環(huán)境中的CPU為i5-8400的6核2．80GH
【參考文獻】：
期刊論文
[1]基于元拓撲關(guān)系的線面空間關(guān)系集成表達模型[J]. 曹亞妮,吳芳華,王麗君,李嘉星. 武漢大學學報(信息科學版). 2016(01)
[2]復合面狀對象拓撲關(guān)系的表達模型[J]. 陳占龍,馮齊奇,吳信才. 測繪學報. 2015(04)
[3]分布式空間數(shù)據(jù)分片與跨邊界拓撲連接優(yōu)化方法[J]. 朱欣焰,周春輝,咼維,夏宇. 軟件學報. 2011(02)
[4]能表達帶洞區(qū)域拓撲關(guān)系的擴展9-交集模型[J]. 歐陽繼紅,霍林林,劉大有,富倩. 吉林大學學報(工學版). 2009(06)
碩士論文
[1]無人駕駛救助船路徑規(guī)劃算法的研究[D]. 陳佳.武漢理工大學 2013
本文編號：2983594
【文章來源】：中國航海. 2019,42(02)北大核心
【文章頁數(shù)】：7 頁
【部分圖文】：
基于拓撲位置關(guān)系的可達路徑地圖
圖3基于拓撲位置關(guān)系的可達路徑地圖2．2路徑搜索基于Dijsktra算法的路徑選擇流程見圖4，對基于拓撲位置關(guān)系的可達路徑進行計算。首先，讀取基于拓撲位置關(guān)系判斷的可達路徑點集P的信息，并設(shè)置起點S與目的點E之間的位置關(guān)系數(shù)據(jù)。定義未訪問點集U和已訪問點集V=P－U，計算所有已訪問點集V到未訪問點集U的值du，從未訪問點集U中選取du中最小的點i，從已訪問點集V中查找與i點直接連接的點，記為Pi，將i點位置數(shù)據(jù)添加進已訪問的點集V，直到Num≥P時結(jié)束搜索，計算出路徑。經(jīng)過上述計算，得出起始點S到目標點E的最短路徑見圖5。圖5中的線條為最短路徑，最短路徑為(S，B74，B73，B91，E)，距離為1200m。圖4基于Dijsktra算法的路徑選擇流程2．3安全距離和船舶旋回圈USV通常是一個欠驅(qū)動系統(tǒng)，無法完全按照規(guī)劃的路徑行駛。考慮到船舶在航行過程中必然會出現(xiàn)路徑上的偏差，在設(shè)計路徑和搜索時應留有安全距離。此外，船舶轉(zhuǎn)向時的旋回半徑也與船舶圖5基于拓撲地圖求解的最短路徑的操縱性能有關(guān)，需在安全上予以考慮。為簡化起見，通常會對障礙物進行邊界上的膨脹，留一定的水域作為船舶安全緩沖區(qū)。在空間分析中，該操作稱為緩沖區(qū)操作(Buffer)。緩沖區(qū)半徑可取USV預留安全距離和旋回半徑中的較大者，以確保船舶安全航行。對障礙物進行緩沖區(qū)操作之后，仍是第1．1節(jié)中所述的一個簡單要素，不影響上述拓撲地圖構(gòu)建和路徑搜索算法的實施。3試驗及分析為驗證該拓撲地圖構(gòu)建及路徑搜索算法的有效性，設(shè)計試驗對本文的算法和基于柵?
叵檔目紗锫肪督?屑撲?。首先，讀取基于拓撲位置關(guān)系判斷的可達路徑點集P的信息，并設(shè)置起點S與目的點E之間的位置關(guān)系數(shù)據(jù)。定義未訪問點集U和已訪問點集V=P－U，計算所有已訪問點集V到未訪問點集U的值du，從未訪問點集U中選取du中最小的點i，從已訪問點集V中查找與i點直接連接的點，記為Pi，將i點位置數(shù)據(jù)添加進已訪問的點集V，直到Num≥P時結(jié)束搜索，計算出路徑。經(jīng)過上述計算，得出起始點S到目標點E的最短路徑見圖5。圖5中的線條為最短路徑，最短路徑為(S，B74，B73，B91，E)，距離為1200m。圖4基于Dijsktra算法的路徑選擇流程2．3安全距離和船舶旋回圈USV通常是一個欠驅(qū)動系統(tǒng)，無法完全按照規(guī)劃的路徑行駛。考慮到船舶在航行過程中必然會出現(xiàn)路徑上的偏差，在設(shè)計路徑和搜索時應留有安全距離。此外，船舶轉(zhuǎn)向時的旋回半徑也與船舶圖5基于拓撲地圖求解的最短路徑的操縱性能有關(guān)，需在安全上予以考慮。為簡化起見，通常會對障礙物進行邊界上的膨脹，留一定的水域作為船舶安全緩沖區(qū)。在空間分析中，該操作稱為緩沖區(qū)操作(Buffer)。緩沖區(qū)半徑可取USV預留安全距離和旋回半徑中的較大者，以確保船舶安全航行。對障礙物進行緩沖區(qū)操作之后，仍是第1．1節(jié)中所述的一個簡單要素，不影響上述拓撲地圖構(gòu)建和路徑搜索算法的實施。3試驗及分析為驗證該拓撲地圖構(gòu)建及路徑搜索算法的有效性，設(shè)計試驗對本文的算法和基于柵格的A*搜索算法進行對比。3．1試驗環(huán)境和工具仿真試驗程序運行環(huán)境中的CPU為i5-8400的6核2．80GH
【參考文獻】：
期刊論文
[1]基于元拓撲關(guān)系的線面空間關(guān)系集成表達模型[J]. 曹亞妮,吳芳華,王麗君,李嘉星. 武漢大學學報(信息科學版). 2016(01)
[2]復合面狀對象拓撲關(guān)系的表達模型[J]. 陳占龍,馮齊奇,吳信才. 測繪學報. 2015(04)
[3]分布式空間數(shù)據(jù)分片與跨邊界拓撲連接優(yōu)化方法[J]. 朱欣焰,周春輝,咼維,夏宇. 軟件學報. 2011(02)
[4]能表達帶洞區(qū)域拓撲關(guān)系的擴展9-交集模型[J]. 歐陽繼紅,霍林林,劉大有,富倩. 吉林大學學報(工學版). 2009(06)
碩士論文
[1]無人駕駛救助船路徑規(guī)劃算法的研究[D]. 陳佳.武漢理工大學 2013
本文編號：2983594
本文鏈接：http://sikaile.net/kejilunwen/sousuoyinqinglunwen/2983594.html
最近更新
教材專著
