[發(fā)明專利]全局路徑規(guī)劃方法及裝置

有效

• 申請(qǐng)?zhí)枺?/td>: 201910314226.1
• 申請(qǐng)日: 2019-04-18
• 公開（公告）號(hào): CN109917794B
• 公開（公告）日: 2022-02-18
• 發(fā)明（設(shè)計(jì)）人: 馮酉南;徐成;張放;李曉飛;張德兆;王肖;霍舒豪
• 申請(qǐng)（專利權(quán)）人: 北京智行者科技有限公司
• 主分類號(hào): G05D1/02
• 分類號(hào): G05D1/02;G01C21/20;G01C21/34
• 代理公司: 北京慧誠(chéng)智道知識(shí)產(chǎn)權(quán)代理事務(wù)所(特殊普通合伙) 11539
• 代理人: 李楠

本發(fā)明提供了一種全局路徑規(guī)劃方法，包括：得到多個(gè)包括起點(diǎn)和終點(diǎn)的采樣點(diǎn)并從中頂點(diǎn)；當(dāng)頂點(diǎn)隊(duì)列中的最優(yōu)點(diǎn)的期望總代價(jià)小于邊隊(duì)列中最優(yōu)邊的期望總代價(jià)時(shí)，對(duì)最優(yōu)點(diǎn)進(jìn)行拓展，直到拓展后的頂點(diǎn)隊(duì)列中的最優(yōu)點(diǎn)的期望總代價(jià)不小于邊隊(duì)列中的最優(yōu)邊的期望總代價(jià)；確定起點(diǎn)至終點(diǎn)的連通路徑；計(jì)算連通路徑的已付代價(jià)并作為橢圓的長(zhǎng)軸；以起點(diǎn)和終點(diǎn)的距離作為橢圓的焦距；根據(jù)長(zhǎng)軸和焦距，確定短軸；根據(jù)長(zhǎng)軸、焦距和短軸，確定搜索空間；計(jì)算搜索空間的位置參數(shù)；根據(jù)位置參數(shù)，對(duì)搜索空間進(jìn)行位置變換；在進(jìn)行位置變換后的搜索空間內(nèi)重新獲取采樣點(diǎn)，迭代的在目標(biāo)搜索空間內(nèi)得到目標(biāo)路徑。由此，提高了計(jì)算速度，且滿足運(yùn)動(dòng)學(xué)約束。

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

本發(fā)明涉及數(shù)據(jù)處理技術(shù)領(lǐng)域，尤其涉及一種全局路徑規(guī)劃方法及裝置。

背景技術(shù)

隨著人工智能技術(shù)的發(fā)展，自動(dòng)駕駛技術(shù)成為汽車工業(yè)發(fā)展的新方向。自動(dòng)駕駛車輛能夠提升交通環(huán)境安全、充分利用交通資源，減少排放。自動(dòng)駕駛車輛的發(fā)展將全面帶動(dòng)社會(huì)生產(chǎn)力的發(fā)展。

現(xiàn)有的全局路徑規(guī)劃算法一般分為兩大類：分辨率完備型算法和概率完備型算法。

分辨率完備型算法是將狀態(tài)空間進(jìn)行離散化處理，在離散處理結(jié)果的基礎(chǔ)上進(jìn)行路徑搜索，如果狀態(tài)空間中存在解，一般情況下分辨率完備法能夠在一定時(shí)間限制內(nèi)搜索到一個(gè)比較接近最優(yōu)解的結(jié)果。搜索結(jié)果與最優(yōu)解的接近程度取決于離散化預(yù)處理過程中所取的分辨率。一般情況下，分辨率越高，越接近最優(yōu)解，但是提高分辨率會(huì)明顯降低搜索速度，然而過低的分辨率有可能搜不到解。對(duì)于分辨率完備的局部路徑規(guī)劃算法，分辨率是一個(gè)非常重要的調(diào)節(jié)參數(shù)。典型的分辨率完備法有：?jiǎn)卧纸夥ǎ辖芩固乩?Dijkstra)算法，A*，D*，泰森多邊形(Voronoi)圖法，人工勢(shì)場(chǎng)法等。

概率完備型算法是基于某個(gè)啟發(fā)函數(shù)隨機(jī)的在狀態(tài)空間進(jìn)行采樣，如果狀態(tài)空間中存在解，那么此類方法可以在有限時(shí)間內(nèi)搜索到解。但是這個(gè)解不一定是最優(yōu)解，而且結(jié)果不具備一致性。搜索速度的快慢與狀態(tài)空間的復(fù)雜度有關(guān)，狀態(tài)空間越復(fù)雜，搜索花費(fèi)的時(shí)間越長(zhǎng)。一般情況下，搜索得到的解與最優(yōu)解相差較大，通過此類方法得到解的局部路徑規(guī)劃算法都要設(shè)計(jì)優(yōu)化器，使結(jié)果靠近最優(yōu)解。典型的概率完備型算法有：概率路線圖法(Probabilistic Roadmap Method，PRM)，快速隨機(jī)樹法(Rapid-exploration RandomTree，RRT)。

現(xiàn)有技術(shù)的路徑規(guī)劃方法存在的問題是：

(1)分辨率完備法一般會(huì)遵循“路徑最短原則”，生成的路徑不一定滿足無人駕駛車輛的運(yùn)動(dòng)學(xué)約束。

(2)現(xiàn)有路徑搜索算法中，大多不對(duì)路徑點(diǎn)的朝向進(jìn)行約束。

(3)基于分辨率完備性的算法計(jì)算速度還有一定的提升空間。

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

本發(fā)明實(shí)施例的目的是提供一種全局路徑規(guī)劃方法及裝置，以解決現(xiàn)有計(jì)算中存在的問題。

為解決上述問題，第一方面，本發(fā)明提供了一種全局路徑規(guī)劃方法，所述方法包括：

根據(jù)車輛行駛的起點(diǎn)和終點(diǎn)，得到多個(gè)采樣點(diǎn)；所述采樣點(diǎn)包括起點(diǎn)和終點(diǎn)；

基于距離變換地圖，從所述采樣點(diǎn)中選取采樣點(diǎn)作為頂點(diǎn)；

將能夠連接到起點(diǎn)的頂點(diǎn)添加至頂點(diǎn)隊(duì)列中；

當(dāng)所述頂點(diǎn)隊(duì)列中的最優(yōu)點(diǎn)的期望總代價(jià)小于邊隊(duì)列中最優(yōu)邊的期望總代價(jià)時(shí)，對(duì)所述最優(yōu)點(diǎn)進(jìn)行拓展，直到拓展后的頂點(diǎn)隊(duì)列中的最優(yōu)點(diǎn)的期望總代價(jià)不小于邊隊(duì)列中的最優(yōu)邊的期望總代價(jià)；所述最優(yōu)點(diǎn)為期望總代價(jià)最小的點(diǎn)，所述最優(yōu)邊為期望總代價(jià)最小的邊；

根據(jù)拓展的結(jié)果，得到從所述起點(diǎn)至所述終點(diǎn)的連通路徑；

計(jì)算所述連通路徑的已付代價(jià)，并將所述已付代價(jià)確定為橢圓的長(zhǎng)軸；