[發(fā)明專利]基于時(shí)間擴(kuò)展的路徑規(guī)劃方法、系統(tǒng)、設(shè)備及存儲(chǔ)介質(zhì)

有效

• 申請(qǐng)?zhí)枺?/td>: 202010842827.2
• 申請(qǐng)日: 2020-08-20
• 公開（公告）號(hào): CN111928867B
• 公開（公告）日: 2021-04-30
• 發(fā)明（設(shè)計(jì)）人: 譚黎敏;俞銘琪
• 申請(qǐng)（專利權(quán)）人: 上海西井信息科技有限公司
• 主分類號(hào): G01C21/34
• 分類號(hào): G01C21/34
• 代理公司: 上海隆天律師事務(wù)所 31282
• 代理人: 鐘宗

本發(fā)明提供了一種基于時(shí)間擴(kuò)展的路徑規(guī)劃方法、系統(tǒng)、設(shè)備及存儲(chǔ)介質(zhì)，該方法包括：獲取路徑規(guī)劃的初始參數(shù)和二維空間地圖；將二維空間地圖擴(kuò)展到三維時(shí)空地圖；基于A Star路徑規(guī)劃算法，在所述三維時(shí)空地圖中從起始地時(shí)空節(jié)點(diǎn)開始依次搜索下一個(gè)路徑節(jié)點(diǎn)，以獲得從起始地到目的地的最短路徑。本發(fā)明可以很好地應(yīng)用于多車路徑規(guī)劃，實(shí)現(xiàn)車輛防碰撞和死鎖規(guī)避的同時(shí)，滿足最快運(yùn)輸計(jì)劃的約束。

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

本發(fā)明涉及路徑規(guī)劃技術(shù)領(lǐng)域，尤其涉及一種基于時(shí)間擴(kuò)展的路徑規(guī)劃方法、系統(tǒng)、設(shè)備及存儲(chǔ)介質(zhì)。

背景技術(shù)

自從Dijkstra算法以來，最短路徑算法的發(fā)展一直是工程及圖論中的前沿問題。由于其適用性廣的特點(diǎn)，單獨(dú)設(shè)計(jì)針對(duì)各行各業(yè)的路徑規(guī)劃算法變種也層出不窮。為提高求解最優(yōu)路徑的效率，研究者們相繼提出了針對(duì)不同工業(yè)應(yīng)用領(lǐng)域下的算法優(yōu)化方案。其中A Star算法是其中較重要的一種算法，它采用啟發(fā)式搜索的方式，不再像Dijkstra算法盲目式搜索，可使搜索范圍明顯縮小，也使導(dǎo)航效率得到提高。雙向搜索(BidirectionalSearch)也是一種快速搜索方式，它采用從起點(diǎn)和目標(biāo)點(diǎn)同時(shí)開始搜索的策略，理想情況下會(huì)在路徑的中點(diǎn)處相遇，從而終止搜索過程。分層技術(shù)(Hierarchical Methods)采用預(yù)處理的辦法使待搜索的路網(wǎng)維度降低，從而達(dá)到快速搜索的目的。

而多車路徑規(guī)劃規(guī)則對(duì)算法提出了更高的要求，算法需要保證在多車協(xié)調(diào)調(diào)度的情況下保持路徑的相互分離，既車輛根據(jù)路徑行駛的過程中不發(fā)生碰撞，同時(shí)規(guī)劃的路徑也不允許發(fā)生死鎖。研究者很快發(fā)現(xiàn)，當(dāng)車輛數(shù)上升到多輛時(shí)，算法的復(fù)雜程度大大上升。

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

針對(duì)現(xiàn)有技術(shù)中的問題，本發(fā)明的目的在于提供一種基于時(shí)間擴(kuò)展的路徑規(guī)劃方法、系統(tǒng)、設(shè)備及存儲(chǔ)介質(zhì)，應(yīng)用于多車路徑規(guī)劃，實(shí)現(xiàn)車輛防碰撞和死鎖規(guī)避的同時(shí)，滿足最快運(yùn)輸計(jì)劃的約束。

本發(fā)明實(shí)施例提供一種基于時(shí)間擴(kuò)展的路徑規(guī)劃方法，包括如下步驟：

獲取路徑規(guī)劃的初始參數(shù)和二維空間地圖，所述初始參數(shù)包括起始地的空間坐標(biāo)、起始時(shí)間和目的地的空間坐標(biāo)，所述二維空間地圖中包括多個(gè)空間節(jié)點(diǎn)，每個(gè)所述空間節(jié)點(diǎn)具有一二維的空間坐標(biāo)；

將二維空間地圖擴(kuò)展到三維時(shí)空地圖，其中，第一維度和第二維度分別為所述二維空間地圖的兩個(gè)維度，第三維度為時(shí)間，所述三維時(shí)空地圖的時(shí)間范圍以所述起始時(shí)間為起點(diǎn)；

根據(jù)所述起始地的空間坐標(biāo)和所述起始時(shí)間確定所述三維時(shí)空地圖中的起始地時(shí)空節(jié)點(diǎn)，根據(jù)所述目的地的空間坐標(biāo)和所述三維時(shí)空地圖的時(shí)間范圍確定所述三維時(shí)空地圖中的目的地直線；

基于A Star路徑規(guī)劃算法，在所述三維時(shí)空地圖中從所述起始地時(shí)空節(jié)點(diǎn)開始依次搜索下一個(gè)路徑節(jié)點(diǎn)，以獲得從所述起始地到所述目的地的最短路徑。

可選地，在所述三維時(shí)空地圖中搜索下一個(gè)路徑節(jié)點(diǎn)時(shí)，對(duì)下一個(gè)路徑節(jié)點(diǎn)的選擇設(shè)置時(shí)空約束條件，所述時(shí)空約束條件包括：可供搜索的下一個(gè)時(shí)空節(jié)點(diǎn)包括根據(jù)當(dāng)前時(shí)空節(jié)點(diǎn)的空間坐標(biāo)與下一時(shí)刻確定的時(shí)空節(jié)點(diǎn)以及根據(jù)當(dāng)前時(shí)空節(jié)點(diǎn)的空間上鄰接節(jié)點(diǎn)的空間坐標(biāo)與下一時(shí)刻確定的節(jié)點(diǎn)。

可選地，所述將二維空間地圖擴(kuò)展到三維時(shí)空地圖之后，還包括如下步驟：

在所述三維時(shí)空地圖中，計(jì)算每個(gè)空間節(jié)點(diǎn)的到達(dá)難度指標(biāo)；

在所述三維時(shí)空地圖中搜索下一個(gè)路徑節(jié)點(diǎn)時(shí)，采用的啟發(fā)函數(shù)根據(jù)所述三維時(shí)空地圖中各個(gè)空間節(jié)點(diǎn)的到達(dá)難度指標(biāo)計(jì)算得到。

可選地，所述計(jì)算每個(gè)空間節(jié)點(diǎn)的到達(dá)難度指標(biāo)，包括如下步驟：

在所述二維空間地圖中，依次計(jì)算每個(gè)空間節(jié)點(diǎn)到其鄰接節(jié)點(diǎn)的到達(dá)難度指標(biāo)；

對(duì)于每個(gè)空間節(jié)點(diǎn)，計(jì)算該空間節(jié)點(diǎn)到其各個(gè)鄰接節(jié)點(diǎn)的到達(dá)難度指標(biāo)的平均值，作為該空間節(jié)點(diǎn)的到達(dá)難度指標(biāo)。