作者：一個大胖豬 | 編輯：計算機視覺工坊
添加小助理：dddvision，備注：方向+學校/公司+昵稱，拉你入群。文末附行業細分群
0. 筆者個人了解
機器人路徑規劃是一個重要的研究領域，涉及到如何讓機器人安全、有效地在環境中導航和移動。這個領域的曆史可以追溯到幾十年前，随着如今機器人技術的進步和應用的擴充，路徑規劃算法在機械臂、移動機器人以及人形機器人等領域的重要性日益凸顯。
1. 基于搜尋的路徑規劃算法
基于搜尋的路徑規劃算法是最早開始進行研究的。這類方法最開始主要用于迷宮求解問題中，在機器人導航時，往往将環境進行栅格化，生成栅格地圖（Grid Map），然後在栅格地圖中疊代搜尋出從起點到終點的最短路徑。
- BFS（廣度優先搜尋）算法：通過探索相鄰栅格來搜尋最短路徑。BFS算法通常使用隊列資料結構來存儲待搜尋的節點，并按照層次，逐層進行周遊。
BFS算法Demo
- Dijkstra算法：通過逐層搜尋和更新最短路徑樹，找到從起點到終點的最短路徑。算法的時間複雜度為O((V+E)logV)，其中V和E分别為圖中頂點數和邊的數量。Dijkstra算法在處理大規模環境和複雜障礙物時表現良好，具有較高的效率和魯棒性。
Dijkstra算法Demo
- A*算法：通過代價函數來估計從起點到終點的成本，并使用最佳優先搜尋政策來尋找代價函數值最低的節點，最終找到最短路徑。它是一種啟發式的搜尋方式，極大地減少了搜尋節點的數量，提高了搜尋算法的效率。
A*算法Demo
如果有興趣的話，可以在這個路徑規劃Demo設計障礙物并對比不同算法的表現。
優缺點總結：
優點：基于搜尋的路徑規劃算法往往能根據環境地圖，找到從起點到終點的最短路徑，可以極大提高機器人的移動效率。
缺點：針對高維空間或者大規模地圖是，基于搜尋的路徑規劃算法的搜尋效率較低，需要疊代的搜尋絕大多數單元格，時間消耗大。
2. 基于采樣的路徑規劃算法
針對基于搜尋的路徑規劃算法出現的在大型場景下搜尋效率低的問題，基于采樣的路徑規劃算法被提出并且進行了廣泛的應用。基于采樣的路徑規劃算法，通過在環境地圖中進行不斷地采樣，并将采樣點進行連接配接，直到算法發現從起點到終點的通路。基于采樣的路徑規劃算法往往具有機率完備性，這是指當采樣點的數量足夠多的時候，所得到的路徑就越接近最優路徑。是以，基于采樣的路徑規劃算法往往隻能夠得到漸進最優解。
- 機率路線圖（Probabilistic Road Map，PRM）：該算法的核心思想是通過在地圖上進行采樣，将環境地圖表示為一個機率圖，其中節點表示環境中的各種可能位置，邊表示從一個位置到另一個位置的機率轉移。PRM算法通過随機采樣和優化來生成最優路徑，最終找到從起點到終點的可行路徑。
PRM算法
- 快速搜尋随機樹（Rapidly-Exploring Random Trees，RRT）：通過不斷随機采樣和将采樣點相連建構搜尋樹，逐漸探索環境并找到了起點A到目标點B的一條路徑。RRT算法适用于複雜的環境，因為它不需要預先了解環境的完整資訊，并且可以有效地處理障礙物和未知區域。需要注意的是，RRT算法生成的路徑可能不是最優路徑，但通常可以找到一條可行且相對較好的路徑。
RRT算法
Imformed RRT 算法
優缺點總結：
優點：基于采樣的路徑規劃算法魯棒性強，能夠處理各種環境變化，如障礙物移動、地形變化等；不需要對所有可能的路徑進行搜尋，它通過采樣局部區域來生成路徑，進而減少了計算量。
缺點：基于采樣的路徑規劃算法尋找的是可行解，而不是全局最優解，可能錯過一些更好的路徑，特别是在環境中有多個可行路徑；對初始采樣的依賴性強，如果初始采樣選擇的位置不合适，可能會導緻算法陷入局部最優解或找不到可行路徑。
3. 全局路徑規劃的最新進展
接下來将介紹并總結近兩年發表在機器人頂刊（Science Robotics，IJRR）上的關于全局路徑規劃的兩篇文章。
《Motion planning around obstacles with convex optimization》
作者：Tobia Marcucci, Mark Petersen, David von Wrangel, Russ Tedrake
機構：MIT，Harvard
期刊：Science Robotics
原文連結：https://www.science.org/doi/10.1126/scirobotics.adf7843
場景：對于機器人，如機械臂、自動駕駛汽車等，在障礙物環境中，有效率的機器人路徑規劃是非常重要的。同時，在路徑規劃中，考慮機器人的dynamic和kinematic的限制，也是非常重要的。Dynamic限制主要是針對機器人系統的加速度限制，而kinematic限制主要是針對軌迹限制。基于搜尋的路徑規劃算法難以實作在3維大場景下的實時路徑規劃，同時傳統基于采樣的方式隻能得到路徑的可行解，而無法得到最優解。是以，作者提出了一種基于凸優化的GCS算法用于實作在多元度上的路徑規劃的求解。
主要貢獻： 1）将環境中可通行安全區域分解成凸形狀的圖形，分解後的圖形如下圖B中 至 所示。這種分割可以保證，如果兩點位于同一區域，那麼他們的連線不會與障礙物産生碰撞。
2）提出了一種針對凸優化松弛方法的路徑求解器。這個求解器可以有效應對路徑規劃中出現的多種限制并且可以應用到多種場景之中。
3）在實驗中驗證了該方法能夠有效生成符合限制條件的全局最優解，并且在時間上遠遠少于基于采樣的路徑規劃算法。
GCS算法示意圖
效果展示：
GCS算法效果展示
《Adaptively Informed Trees (AIT*) and Effort Informed Trees (EIT*): Asymmetric bidirectional sampling-based path planning》
作者：Marlin P Strub, Jonathan D Gammell
機構：CalTech, Oxford
期刊：The International Journal of Robotics Research (IJRR)
原文連結：https://journals.sagepub.com/doi/full/10.1177/02783649211069572
場景：這篇文章主要針對路徑規劃中兩個問題：1）規劃從起點到終點的可行路徑（feasible path）；2）規劃出與障礙物保持一定距離的路徑（obstacle clearance）。針對這兩個問題，在這篇文章中，作者追求選擇去生成路徑的漸進最優解來提高基于采樣的路徑規劃算法的效率。
主要貢獻： 1）提出了AIT*與EIT*兩個基于采樣的路徑規劃算法路徑，分别用于解決在環境中發現最短路徑與生成與障礙物保持一定距離的路徑。
AIT*算法示意圖
EIT*算法示意圖
2）利用圖論的相關知識，證明了他們提出的算法能夠實作漸進最優解。
3）在機械臂等平台上，設計實驗證明了AIT*與EIT*的有效性，效果能夠超過其他基于采樣的路徑規劃算法。
效果展示：
AIT*算法效果展示
EIT*算法效果展示
4. 總結
今天筆者為大家首先介紹了傳統的路徑規劃算法，主要分為基于搜尋的路徑規劃與基于采樣的路徑規劃，列舉了例子并總結了他們的優缺點。之後，介紹了最新發表在機器人頂刊Science Robotics和IJRR上關于機器人全局路徑規劃算法的最近研究，總結了他們的背景與貢獻。
本文僅做學術分享，如有侵權，請聯系删文。
計算機視覺工坊交流群
目前我們已經建立了3D視覺方向多個社群，包括2D計算機視覺、大模型、工業3D視覺、SLAM、自動駕駛、三維重建、無人機等方向，細分群包括：
2D計算機視覺：圖像分類/分割、目标/檢測、醫學影像、GAN、OCR、2D缺陷檢測、遙感測繪、超分辨率、人臉檢測、行為識别、模型量化剪枝、遷移學習、人體姿态估計等
大模型：NLP、CV、ASR、生成對抗大模型、強化學習大模型、對話大模型等
工業3D視覺：相機标定、立體比對、三維點雲、結構光、機械臂抓取、缺陷檢測、6D位姿估計、相位偏折術、Halcon、攝影測量、陣列相機、光度立體視覺等。
SLAM：視覺SLAM、雷射SLAM、語義SLAM、濾波算法、多傳感器融合、多傳感器标定、動态SLAM、MOT SLAM、NeRF SLAM、機器人導航等。
自動駕駛：深度估計、Transformer、毫米波|雷射雷達|視覺攝像頭傳感器、多傳感器标定、多傳感器融合、自動駕駛綜合群等、3D目标檢測、路徑規劃、軌迹預測、3D點雲分割、模型部署、車道線檢測、BEV感覺、Occupancy、目标跟蹤、端到端自動駕駛等。
三維重建：3DGS、NeRF、多視圖幾何、OpenMVS、MVSNet、colmap、紋理貼圖等
無人機：四旋翼模組化、無人機飛控等
除了這些，還有求職、硬體選型、視覺産品落地、最新論文、3D視覺最新産品、3D視覺行業新聞等交流群
添加小助理: dddvision，備注：研究方向+學校/公司+昵稱（如3D點雲+清華+小草莓）, 拉你入群。
3D視覺學習知識星球
3DGS、NeRF、結構光、相位偏折術、機械臂抓取、點雲實戰、Open3D、缺陷檢測、BEV感覺、Occupancy、Transformer、模型部署、3D目标檢測、深度估計、多傳感器标定、規劃與控制、無人機仿真、三維視覺C++、三維視覺python、dToF、相機标定、ROS2、機器人控制規劃、LeGo-LAOM、多模态融合SLAM、LOAM-SLAM、室内室外SLAM、VINS-Fusion、ORB-SLAM3、MVSNet三維重建、colmap、線面結構光、硬體結構光掃描器，無人機等。