導讀

本文分享了在GitHub開源的一個存儲庫，包含了機器人技術中常用的一些路徑規劃算法，大部分代碼由Python實現，每種算法都配有相關動畫的運行過程。

在機器人研究領域，給定某一特定任務之后，如何規劃機器人的運動方式至關重要。

最近，GitHub 上開源了一個存儲庫，該庫實現了機器人技術中常用的一些路徑規劃算法，大部分代碼是用 Python 實現的。值得一提的是，開發者用 plotting 為每種算法演示了動畫運行過程，直觀清晰。

項目地址：

https://github.com/zhm-real/PathPlanning

該開源庫中實現的路徑規劃算法包括基于搜索和基于采樣的規劃算法，具體目錄如下圖所示：

基于搜索的路徑規劃算法

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

最佳路徑優先搜索算法

Dijkstra 算法

A * 搜索算法

雙向 A * 搜索算法

重復 A * 搜索算法

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

實時學習 A * 搜索（LRTA*）算法

實時適應性 A * 搜索（RTAA*）算法

動態 A * 搜索（D*）算法

終身規劃 A * 搜索算法

Anytime D * 搜索算法：變動較小

Anytime D * 搜索算法：變動較大

基于采樣的路徑規劃算法

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

快速隨機搜索樹（RRT）算法

目標偏好 RRT 算法

雙向快速擴展隨機樹（RRT_CONNECT）算法

Extended_RRT 算法

動態 RRT 算法

N = 10000 時，rrt * 算法

N = 1000 時，rrt*-Smart 算法

快速行進樹（FMT*）算法

N =1000 時，Informed rrt * 算法

Batch Informed 樹（BIT*）算法

責任編輯：lq