運(yùn)動(dòng)規(guī)劃是移動(dòng)機(jī)器人自主導(dǎo)航系統(tǒng)中的重要模塊之一，相關(guān)算法研究成果層出不同窮，諸多學(xué)者針對不同應(yīng)用場景和需求，設(shè)計(jì)、改進(jìn)了非常多的運(yùn)動(dòng)規(guī)劃算法，筆者將常見的運(yùn)動(dòng)規(guī)劃算法主要分為四類：圖規(guī)劃算法、空間采樣算法、曲線插值擬合算法和仿生智能算法。

圖規(guī)劃算法

圖規(guī)劃算法多數(shù)將環(huán)境模型離散化表達(dá)，如柵格圖等，其離散節(jié)點(diǎn)描述相應(yīng)狀態(tài)，建立節(jié)點(diǎn)間聯(lián)系，并求解最優(yōu)路徑。

圖規(guī)劃算法根據(jù)路徑生成方式的不同分為三類，其中以圖搜索算法為主，以及BUG算法和勢場力算法。

空間采樣算法

空間采樣算法按照采樣空間不同，可分為：狀態(tài)空間采樣和運(yùn)動(dòng)空間采樣。

基于狀態(tài)空間采樣的算法能夠在大面積、高緯度的空間中快速生成路徑，包括RRT和PRM類算法等，具有概率完備性，其主要步驟包括隨機(jī)采樣、度量連接、碰撞檢測和路徑查詢。

基于運(yùn)動(dòng)空間采樣的算法則在速度空間等距采樣，通過評價(jià)函數(shù)選擇最佳控制指令，驅(qū)動(dòng)機(jī)器人運(yùn)動(dòng)，主要包括CVM類算法及DWA類算法等。

曲線插值擬合算法

上述大部分《圖規(guī)劃算法》和《空間采樣算法》生成的路徑存在折點(diǎn)、急彎等曲率不連續(xù)的情況，影響了機(jī)器人運(yùn)動(dòng)平穩(wěn)性，因此需要綜合考慮模型硬約束與實(shí)際規(guī)劃軟需求，以提升路徑平滑度。

曲線插值擬合算法在曲線平滑控制及優(yōu)化方面有顯著的優(yōu)勢，按照曲線生成方式及其種類可分為：基于插值的規(guī)劃算法、基于特殊曲線的規(guī)劃算法及基于優(yōu)化的規(guī)劃算法三類，該類算法在自動(dòng)駕駛等領(lǐng)域有著廣泛的應(yīng)用。

仿生智能算法

針對機(jī)器人運(yùn)動(dòng)規(guī)劃問題，除上述基于經(jīng)典模型的規(guī)劃算法外（《圖規(guī)劃算法》、《空間采樣算法》和《曲線插值擬合算法》），還有神經(jīng)網(wǎng)絡(luò)、模糊邏輯及基于自然靈感的算法（遺傳算法、粒子群算法、蟻群算法等），并逐漸成為研究熱點(diǎn)。

與經(jīng)典算法相比，智能算法能夠較好適應(yīng)復(fù)雜動(dòng)態(tài)環(huán)境中的不確定、不完整的信息，但需要前期學(xué)習(xí)階段和較高計(jì)算成本，適用于大型機(jī)器人，如無人車等。

圖規(guī)劃算法與空間采樣算法已經(jīng)能夠在諸多場景下的規(guī)劃生成一條無碰撞路徑，實(shí)時(shí)性和動(dòng)態(tài)適應(yīng)性逐漸提升，但多數(shù)算法仍存在路徑質(zhì)量差、未考慮動(dòng)力學(xué)約束等問題。

而曲線插值擬合算法正好與之配合，能夠容易生成連續(xù)性好的軌跡曲線。

多數(shù)仿生智能算法處理動(dòng)態(tài)環(huán)境下的規(guī)劃問題時(shí)存在實(shí)時(shí)性、收斂性均不穩(wěn)定等問題，實(shí)際應(yīng)用較少。

從目前研究思路來看，多是先采用圖規(guī)劃算法、空間采樣算法生成全局路徑或初始路徑，再使用曲線插值擬合算法，綜合考慮系統(tǒng)軟硬約束，優(yōu)化生成質(zhì)量好的軌跡。