『壹』 路徑規劃之PRM類演算法
PRM類演算法，也稱為概率路徑規劃演算法，旨在解決機器人在復雜環境中找到安全路徑的問題。這類演算法的核心在於構建連通圖並搜索最優路徑。
構建連通圖，首先在配置空間中隨機抽取點，這些點代表可能的位置。通過檢測這些點是否位於自由空間內，以及使用本地規劃器嘗試連接這些點，構建起一張連通圖。在構建過程中，只保留與障礙物無交集的連線，並結合起始點和目標點，形成連通圖。圖搜索演算法則用於在構建的連通圖中尋找無碰撞路徑。
圖 2.2展示了PRM演算法的原理。通過調整采樣點的數量，可以優化計算結果。Bohlin等人的改進演算法如LazyPRM通過減少局部規劃器的調用次數，從而提高規劃效率。SPARS2則構建了稀疏和稠密雙重圖，以加速演算法的收斂並趨向最優解。
PRM類演算法通過構建連通圖並搜索最優路徑，為機器人提供了一種高效、可靠的路徑規劃方法。在實踐中，這些演算法已被廣泛應用，並在不斷的優化和改進中，以適應更復雜和多變的環境。