[發(fā)明專利]一種基于正六邊形柵格跳點搜索算法的路徑規(guī)劃方法

有效

• 申請?zhí)枺?/td>: 202010632548.3
• 申請日: 2020-07-03
• 公開（公告）號: CN111811514B
• 公開（公告）日: 2023-06-09
• 發(fā)明（設(shè)計）人: 杜佳璐;王文明;張興龍
• 申請（專利權(quán)）人: 大連海事大學
• 主分類號: G01C21/20
• 分類號: G01C21/20;G01C21/34
• 代理公司: 大連東方專利代理有限責任公司 21212
• 代理人: 魯保良;李洪福

本發(fā)明公開了一種基于正六邊形柵格跳點搜索算法的路徑規(guī)劃方法，包括以下步驟：對路徑規(guī)劃區(qū)域進行正六邊形柵格化建模，根據(jù)頂角型正六邊形柵格法建模下的四叉樹搜索策略，將六種當前節(jié)點方向順時針依次定義為東、東南、西南、西、西北、東北方向。本發(fā)明采用了正六邊形柵格建模下的四叉樹策略進行路徑規(guī)劃，使得智能體在路徑規(guī)劃過程中尋路方向多且轉(zhuǎn)角角度小，規(guī)劃路徑短，且在考慮智能體運動約束情況下更符合實際運動約束。本發(fā)明采用了正六邊形柵格建模下四叉樹搜索策略進行路徑規(guī)劃，使得智能體在路徑規(guī)劃過程中節(jié)點擴展更為均衡，處理鄰域關(guān)系時更具優(yōu)勢，可加快路徑規(guī)劃速度。本發(fā)明所得到的規(guī)劃路徑更為安全合理。

技術(shù)領(lǐng)域

本發(fā)明涉及智能體路徑規(guī)劃技術(shù)領(lǐng)域，具體涉及一種基于正六邊形柵格跳點搜索算法的路徑規(guī)劃方法。

背景技術(shù)

隨著現(xiàn)代科技的飛速發(fā)展，無人車、無人機、無人船等智能體應(yīng)運而生，并被廣泛應(yīng)用于各個領(lǐng)域。智能體的路徑規(guī)劃技術(shù)是實現(xiàn)其自主導航的關(guān)鍵技術(shù)之一，也是其智能化水平的體現(xiàn)。智能體的路徑規(guī)劃旨在根據(jù)當前的任務(wù)需求，規(guī)劃出一條從起始點至目標點的無碰撞、安全合理的路徑，主要包括環(huán)境建模和路徑規(guī)劃兩部分內(nèi)容。

中國專利CN?107687859?A公開了一種基于A*算法的最短尋路方法，在對路徑規(guī)劃區(qū)域進行柵格化建模后，采用將啟發(fā)式函數(shù)BFS和Dijkstra算法相結(jié)合的A*算法進行路徑規(guī)劃，使得規(guī)劃路徑最短并且速度快于Dijkstra算法，但A*算法存在尋路過程中需要拓展大量冗余節(jié)點、路徑規(guī)劃效率不高的問題，上述方法也未考慮智能體的運動約束。

中國專利CN?110567477?A公開了一種基于改進A*算法的路徑規(guī)劃方法，該方法在路徑生成步驟中采用消除共線節(jié)點和消除冗余轉(zhuǎn)折點的方法優(yōu)化路徑，減少了路徑代價和搜索時間，加快了路徑規(guī)劃進程。

中國專利CN?110487279?A公開了一種基于改進A*算法的機器人路徑規(guī)劃方法，該方法在A*算法基礎(chǔ)上合并路徑中的關(guān)鍵拐點，然后利用三次樣條插值平滑路徑，改進后算法規(guī)劃所得路徑長度更短、整體更平滑，并能夠符合非完整型機器人運動約束。

中國專利CN?105955280?A公開了一種基于跳點搜索算法的移動機器人路徑規(guī)劃方法，跳點搜索算法改變了A*算法的鄰居節(jié)點的選取規(guī)則，并采用搜索跳點的策略拓展節(jié)點，避免了對冗余節(jié)點的操作，極大提高了A*算法的路徑規(guī)劃效率。

但上述技術(shù)在環(huán)境建模部分均采用結(jié)構(gòu)簡單、計算量小的傳統(tǒng)正方形柵格法建模。正方形柵格法建模下的路徑搜索策略有四叉樹和八叉樹策略，四叉樹策略搜索方向經(jīng)過柵格中心點，八叉樹策略搜索方向既經(jīng)過柵格中心點，又經(jīng)過柵格頂點。大幅度提高A*算法路徑規(guī)劃效率的傳統(tǒng)跳點搜索算法使用的是八叉樹搜索策略，存在節(jié)點拓展缺乏平衡性的問題，會影響到路徑規(guī)劃的速度；同時在避開障礙物的路徑規(guī)劃過程中存在穿越墻角的行為，從而會影響到最終規(guī)劃路徑的安全性與合理性。

發(fā)明內(nèi)容

為了解決現(xiàn)有技術(shù)存在的上述問題，本發(fā)明要設(shè)計一種應(yīng)用于智能體路徑規(guī)劃后尋得的路徑更為安全、合理，同時尋路速度更快的基于正六邊形柵格跳點搜索算法的路徑規(guī)劃方法。

為了實現(xiàn)上述目的，本發(fā)明的技術(shù)方案如下：

一種基于正六邊形柵格跳點搜索算法的路徑規(guī)劃方法，包括以下步驟：

A、對路徑規(guī)劃區(qū)域進行正六邊形柵格化建模，確定路徑規(guī)劃的起點和目標點所在柵格；