[發(fā)明專利]一種基于Hybrid-astar的動(dòng)態(tài)路徑規(guī)劃方法

在審

• 申請(qǐng)?zhí)枺?/td>: 202110216076.8
• 申請(qǐng)日: 2021-02-26
• 公開（公告）號(hào): CN112923946A
• 公開（公告）日: 2021-06-08
• 發(fā)明（設(shè)計(jì)）人: 鐘英杰;盛書磊
• 申請(qǐng)（專利權(quán)）人: 廣州海格通信集團(tuán)股份有限公司
• 主分類號(hào): G01C21/34
• 分類號(hào): G01C21/34
• 代理公司: 廣州市華學(xué)知識(shí)產(chǎn)權(quán)代理有限公司 44245
• 代理人: 黃磊;雷芬芬

本發(fā)明公開了一種基于Hybrid?astar的動(dòng)態(tài)路徑規(guī)劃方法，包括：S1，根據(jù)已知的全局路徑、用戶設(shè)置的最大路徑規(guī)劃長(zhǎng)度d_max和可變規(guī)劃距離d_plan進(jìn)行可變規(guī)劃距離的粒度分割，生成全局路徑；S2，對(duì)動(dòng)態(tài)路徑進(jìn)行優(yōu)化；其中，對(duì)動(dòng)態(tài)路徑進(jìn)行優(yōu)化的步驟包括：分段規(guī)劃多點(diǎn)組合路徑搜索、角度平滑和貝塞爾曲線差值平滑中的至少一種；S3，將優(yōu)化后的路徑周期性下發(fā)至無(wú)人車，無(wú)人車根據(jù)路徑行駛。本發(fā)明按照可變規(guī)劃距離進(jìn)行粒度分割，生成全局路徑，將全局路徑分解為若干路徑點(diǎn)子集；采用多點(diǎn)組合路徑搜索方法進(jìn)行路徑搜索，提高路徑搜索的成功概率。

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

本發(fā)明涉及車輛動(dòng)態(tài)路徑規(guī)劃技術(shù)領(lǐng)域，具體涉及一種基于Hybrid-astar的動(dòng)態(tài)路徑規(guī)劃方法。

背景技術(shù)

路徑規(guī)劃中常常使用混合A*算法,混合A*(Hybrid-astar)是一種適用于全局、靜態(tài)的路徑規(guī)劃算法。通過(guò)連續(xù)坐標(biāo)系下進(jìn)行啟發(fā)式搜索生成運(yùn)動(dòng)軌跡，并對(duì)運(yùn)動(dòng)軌跡進(jìn)行車輛非完整性約束得到車輛的行駛最終運(yùn)動(dòng)軌跡。傳統(tǒng)的A*算法使用2D歐式距離啟發(fā)式搜索，混合A*使用車輛非完整性約束啟發(fā)式搜索和完整性約束啟發(fā)式搜索，同時(shí)使用Reeds-Shepp曲線加快搜索速度。參見圖1，混合A*算法的實(shí)現(xiàn)步驟為：

1)把起點(diǎn)加入open list；

2)重復(fù)以下步驟遍歷所有節(jié)點(diǎn)：

①遍歷open list，查找F(Reed-Shepp距離/Dubins距離)值最小的節(jié)點(diǎn)，把它作為當(dāng)前要處理的節(jié)點(diǎn)。

②把這個(gè)節(jié)點(diǎn)移到close list。

③對(duì)當(dāng)前節(jié)點(diǎn)的8個(gè)相鄰方向的節(jié)點(diǎn)進(jìn)行遍歷。

a.如果它是不可抵達(dá)的或者它在close list中，忽略它。否則，做如下處理。

b.把該節(jié)點(diǎn)加入open list，并且把當(dāng)方格設(shè)置為它的父親，記錄該方格的F,G和H值。

c.G值作衡量該路徑是否是最優(yōu)路徑，G值越小路徑越優(yōu)。如果G值最小，把它的父親設(shè)置為當(dāng)前方格，并重新計(jì)算它的G和F值。

④生成Reed-Shepp曲線，并進(jìn)行碰撞檢測(cè)，把終點(diǎn)加入到了open list中，停止路徑遍歷。

3)保存路徑。從終點(diǎn)開始，每個(gè)方格沿著父節(jié)點(diǎn)移動(dòng)直至起點(diǎn)，得到混合A*規(guī)劃好的路徑。

混合A*是一種適用于靜態(tài)全局、由始點(diǎn)到終點(diǎn)的兩點(diǎn)路徑規(guī)劃算法。其在做長(zhǎng)距離或動(dòng)態(tài)的行駛規(guī)劃中耗時(shí)長(zhǎng)、無(wú)法避開動(dòng)態(tài)障礙物；并且混合A*算法只適用于近似最優(yōu)路徑規(guī)劃，無(wú)法滿足用戶特性化需求，所以并不適用于動(dòng)態(tài)的路徑規(guī)劃。

因此,行業(yè)內(nèi)急需研發(fā)一種基于動(dòng)態(tài)、多點(diǎn)路的路徑規(guī)劃算法。

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

本發(fā)明的目的是為了克服以上現(xiàn)有技術(shù)存在的不足，提供了一種適用于動(dòng)態(tài)、高速應(yīng)用場(chǎng)景，且能實(shí)時(shí)避障能力的Hybrid-astar的動(dòng)態(tài)路徑規(guī)劃方法。

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

一種基于Hybrid-astar的動(dòng)態(tài)路徑規(guī)劃方法，包括：

S1，根據(jù)已知的全局路徑、用戶設(shè)置的最大路徑規(guī)劃長(zhǎng)度d_max和可變規(guī)劃距離d_plan進(jìn)行可變規(guī)劃距離的粒度分割，生成全局路徑；

S2，對(duì)動(dòng)態(tài)路徑進(jìn)行優(yōu)化；其中，對(duì)動(dòng)態(tài)路徑進(jìn)行優(yōu)化的步驟包括：分段規(guī)劃多點(diǎn)組合路徑搜索、角度平滑和貝塞爾曲線差值平滑中的至少一種；

S3，將優(yōu)化后的路徑周期性下發(fā)至無(wú)人車，無(wú)人車根據(jù)路徑行駛。