⑴ 路徑規劃之圖搜索演算法概述
圖搜索演算法是路徑規劃領域的關鍵方法之一，它們通過將地圖結構化為圖的形式，採用特定策略搜索最優路徑。以下是關於圖搜索演算法的概述：
Dijkstra演算法：
- 特性：經典的圖搜索演算法，採用廣度優先搜索策略。
- 工作原理：通過遍歷所有可能路徑，選擇成本最低的一條，適用於尋找最短路徑的問題。
A*演算法：
- 改進：在Dijkstra演算法的基礎上引入啟發式函數。
- 優勢：通過優化節點搜索順序，顯著提升了路徑搜索效率。
- 後續研究：針對A*演算法的不足，後續研究在內存消耗、實時性、動態環境適應性、移動目標追蹤以及路徑質量方面進行了改進。
內存消耗改進：
- 演算法：IDA*和SMA*演算法。
- 策略：通過優化搜索過程和剪枝策略，有效降低了內存使用量。
實時性改進：
- 演算法：RTA*、LRTA*和RTAA*演算法。
- 策略：通過更新啟發值和學習率，提高了解決問題的速度。雖然這些演算法不能保證找到最優路徑，但在實際應用中表現出色。
動態環境適應性改進：
- 演算法：D、D Lite和AD*演算法。
- 策略：通過重用已搜索信息，實現了路徑的快速更新和優化。
移動目標追蹤改進：
- 演算法：GGA*、GFRA和MTDLite演算法。
- 策略：通過高效更新啟發值和重用搜索結果，顯著提高了追蹤效率。
路徑質量改進：
- 演算法：Field D*、Theta*、Incremental Phi*和Lazy Theta*演算法。
- 策略：這些演算法分別通過允許更靈活的路徑方向、優化折線段、結合最優路徑搜索結果等方式，實現了更高效的路徑規劃。
- 其他演算法：Hybrid A*演算法在滿足最小轉彎半徑約束的同時，進一步提升了路徑的連續性。
綜上所述，圖搜索演算法在路徑規劃領域具有廣泛的應用和深入的研究，不同的演算法針對不同的應用場景和需求進行了優化和改進。