如何規(guī)劃機(jī)器人的運(yùn)動(dòng)方式是機(jī)器人開(kāi)發(fā)領(lǐng)域的一大課題，本文分享GitHub的一個(gè)機(jī)器人技術(shù)中常用的路徑規(guī)劃算法的開(kāi)源庫(kù)，并用動(dòng)圖直觀演示運(yùn)行過(guò)程。其中大部分代碼由Python實(shí)現(xiàn)。

該開(kāi)源庫(kù)中實(shí)現(xiàn)的路徑規(guī)劃算法包括基于搜索和基于采樣的規(guī)劃算法，具體目錄如下圖所示：

01基于搜索的路徑規(guī)劃算法

基于搜索的路徑規(guī)劃算法已經(jīng)較為成熟且得到了廣泛應(yīng)用，常常被用于游戲中人物和移動(dòng)機(jī)器人的路徑規(guī)劃。

最佳路徑優(yōu)先搜索算法

Dijkstra 算法

A * 搜索算法

雙向 A * 搜索算法

重復(fù) A * 搜索算法

Anytime Repairing A* (ARA*) 搜索算法

實(shí)時(shí)學(xué)習(xí) A * 搜索（LRTA*）算法

實(shí)時(shí)適應(yīng)性 A * 搜索（RTAA*）算法

動(dòng)態(tài) A * 搜索（D*）算法

終身規(guī)劃 A * 搜索算法

Anytime D * 搜索算法：變動(dòng)較小

Anytime D * 搜索算法：變動(dòng)較大

02

基于采樣的路徑規(guī)劃算法

與基于搜索不同，基于采樣的路徑規(guī)劃算法不需要顯式構(gòu)建整個(gè)配置空間和邊界，并且在高維度的規(guī)劃問(wèn)題中得到廣泛應(yīng)用。

快速隨機(jī)搜索樹(shù)（RRT）算法

目標(biāo)偏好 RRT 算法

雙向快速擴(kuò)展隨機(jī)樹(shù)（RRT_CONNECT）算法

Extended_RRT 算法

動(dòng)態(tài) RRT 算法

N = 10000 時(shí)，rrt * 算法

N = 1000 時(shí)，rrt*-Smart 算法

快速行進(jìn)樹(shù)（FMT*）算法

N =1000 時(shí)，Informed rrt * 算法

Batch Informed 樹(shù)（BIT*）算法

審核編輯：湯梓紅