[發(fā)明專利]一種過必經(jīng)點集且有額外硬約束的路徑規(guī)劃方法及設(shè)備

有效

• 申請?zhí)枺?/td>: 202110329163.4
• 申請日: 2021-03-27
• 公開（公告）號: CN112965500B
• 公開（公告）日: 2022-07-05
• 發(fā)明（設(shè)計）人: 郭展羽;張志明
• 申請（專利權(quán)）人: 同濟大學
• 主分類號: G05D1/02
• 分類號: G05D1/02
• 代理公司: 上海科盛知識產(chǎn)權(quán)代理有限公司 31225
• 代理人: 翁惠瑜

本發(fā)明涉及一種過必經(jīng)點集且有額外硬約束的路徑規(guī)劃方法及設(shè)備，所述路徑規(guī)劃方法包括以下步驟：S1：預(yù)處理階段，將實際應(yīng)用環(huán)境信息轉(zhuǎn)化為數(shù)學描述，完成對問題的無向帶權(quán)圖的處理與建模；S2：最短路徑求解階段，使用隨機搜索算法進行最短路徑求解，搜索過程中對路徑的可行性進行實時判定，在滿足額外硬約束的要求下，求解過必經(jīng)點集的最短路徑問題，最終獲得滿足要求的最短路徑。本發(fā)明可以添加額外的硬約束，能在較短的計算時間內(nèi)保證獲得滿足實際物理限制條件下的工程需求的解算結(jié)果。

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

本發(fā)明涉及運籌學、計算機科學、地理信息科學和交通運輸領(lǐng)域，尤其涉及一種過必經(jīng)點集且有額外硬約束的路徑規(guī)劃方法及設(shè)備。

背景技術(shù)

最短路徑問題一直是運籌學、計算機科學、地理信息科學、交通運輸?shù)阮I(lǐng)域的研究熱點，并廣泛應(yīng)用到公共交通運輸網(wǎng)絡(luò)規(guī)劃、無人自動駕駛、機器人自主導(dǎo)航等的實際問題中。現(xiàn)實生活里有許多問題都可以抽象轉(zhuǎn)化為最短路徑問題，路徑規(guī)劃要求根據(jù)某種優(yōu)化準則，在給定的真實環(huán)境中尋找到一條從起始位置到目標位置并且代價最小的路線。如何有效地計算和解決最短路徑問題，研究面臨的難點是如何在較短的時間內(nèi)找到較為完備的解。根據(jù)對環(huán)境信息的掌握程度不同，路徑規(guī)劃可分為全局路徑規(guī)劃和局部路徑規(guī)劃，兩者沒有本質(zhì)上的區(qū)別。經(jīng)典的全局路徑規(guī)劃算法有Dijkstra算法和A*算法等，可以靜態(tài)地規(guī)劃出最優(yōu)或次優(yōu)路線。近年來，國內(nèi)外學者在此基礎(chǔ)上，引入啟發(fā)式算法和仿生算法等，提出多種最短路徑改進算法，如模擬退火法、蟻群算法、遺傳算法、粒子群算法、深度優(yōu)先算法和廣度優(yōu)先算法等，并在解決過必經(jīng)點集的最短路徑問題上已經(jīng)取得了很好的成效。在探究路徑規(guī)劃算法的過程中，實際應(yīng)用場景由于物理條件的限制會存在額外硬約束條件，而包括授權(quán)發(fā)明專利CN201710535060.7《一種考慮多類型約束的k最短路徑求解方法》在內(nèi)的上述算法在處理此類問題時，由于選擇將所有可能的順序列出后進行最短路徑的求解，具有非常大的計算量，會存在求解難度高、求解速度慢、求解結(jié)果不可靠甚至不可行等的問題。

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

本發(fā)明的目的就是為了克服上述現(xiàn)有技術(shù)存在的缺陷而提出一種過必經(jīng)點集且有額外硬約束的路徑規(guī)劃方法及設(shè)備，該方法計算速度快、實時性好且判定準確。

本發(fā)明的目的可以通過以下技術(shù)方案來實現(xiàn)：

一種過必經(jīng)點集且有額外硬約束的路徑規(guī)劃方法，包括如下步驟：

S1：預(yù)處理階段，依據(jù)實際應(yīng)用環(huán)境信息獲取對應(yīng)的無向帶權(quán)圖和額外硬約束；

S2：最短路徑求解階段，使用基于深度優(yōu)先的隨機搜索算法在所述無向帶權(quán)圖上進行最短路徑求解，搜索過程中對路徑的可行性進行實時判定，在滿足額外硬約束的要求下，求解獲得過必經(jīng)點集的最短路徑。

優(yōu)選地，所述步驟S1包括：

將實際應(yīng)用環(huán)境信息轉(zhuǎn)化為數(shù)學描述，建模抽象為無向帶權(quán)圖，通過一二維鄰接矩陣保存所述無向帶權(quán)圖的圖信息和節(jié)點信息；

依據(jù)路徑規(guī)劃要求及實際應(yīng)用環(huán)境信息定義變量，包括路徑規(guī)劃的起點、終點、必經(jīng)點集以及額外硬約束。

優(yōu)選地，所述二維鄰接矩陣存儲有所述無向帶權(quán)圖中任意相鄰兩點之間的距離，當兩點不是相鄰時，距離值為-1，點與其自身的距離值為0。

優(yōu)選地，所述額外硬約束基于實際應(yīng)用場景中的物理條件限制獲得，所述物理條件限制包括無人駕駛車輛本體機械尺寸、轉(zhuǎn)彎限行和道路限行狀態(tài)。

優(yōu)選地，所述最短路徑求解時的初始參數(shù)包括起點start、面朝點next、終點destination、必經(jīng)點集point_list[]和存儲包含額外硬約束的子路徑的額外硬約束集point_constraint[]。

優(yōu)選地，所述額外硬約束集point_constraint[]包含的元素為連續(xù)N個節(jié)點形成的子路徑，N為設(shè)定長度。

優(yōu)選地，所述步驟S2包括：