最佳化侷域路徑規劃演算法3DVFH*

接續上篇談到路徑規劃3DVFH+[1]，這次來談不需要區域空間資訊的演算法變體3DVFH*。3DVFH+使用八叉樹描述周遭空間的障礙物分布，然而很多情境下，取得完整空間地圖並不實際，一來需要SLAM（simultaneous localization and mapping）相關的演算法協助；二來硬體需求相應地增加。3DVFH*取消八叉樹的資料儲存，而是單純就每一次深度相機的感測結果，直接對應到極座標直方圖（polar histogram）上，規劃下一步路。然而如此一來，上一個時間點所得之直方圖，若直接丟棄似乎沒有完全利用這些寶貴資訊，故3DVFH會將上一個時間點之直方圖投射回三維點雲，與當下測得的點雲合併計算新的直方圖，如此一來，直方圖擁有一定程度的記憶，可以考慮到當前視野外的部分區域。

第二部分，3DVFH*引入原本為二維空間導航設計的VFH*[2]，除了從直方圖中選出下一步的前進方向，更進一步向前搜尋未來幾步，以挑選出短時間內的最佳路徑。向前搜尋的過程，可想作無人機假想自己抵達下一點後，同樣進行上述直方圖運算，各方向重複N次後，即能選出N部內之最佳路徑。

撰文：姚皇宇

原始文獻：Tanja Baumann. (2018) Obstacle Avoidance for Drones Using a 3DVFH* Algorithm. Master thesis. Swiss Federal Institute of Technology Zurich.

參考資料：

[1] 全域路徑規劃演算法3DVFH+。https://neuroinfo-cclolab.blogspot.com/2020/12/3dvfh.html

[2] Ulrich and J. Borenstein, “VFH*: local obstacle avoidance with look-ahead verification,” in Proceedings 2000 ICRA. Millennium Conference. IEEE International Conference on Robotics and Automation. Symposia Proceedings, Apr. 2000, vol. 3, pp. 2505–2511 vol.3.