全域路徑規劃演算法3DVFH+

在一個房間內，或是建築物內從A點走到B點這件事對我們來說應該輕而易舉，只要有足夠的環境資訊如肉眼可直接觀察，或是地圖；然而對機器人來說這就對應到仍然年輕的研究主題：路徑規劃（path planning）。你或許會想說，現在很多商用地圖軟體不就非常成熟了嗎？為什麼對機器人來說很困難？那麼應該說是應用情境不同，一般導航軟體都是在有精確圖資的情形下計算兩點最短路徑，不過很多時候機器人是在室內環境或是對周遭環境認識有限的情形下導航，那麼可能難以獲得最佳解，只好透過演算法盡可能利用有限資訊找出至少不會撞上障礙物的路徑。

2014年Vanneste等人提出三維供無人機使用的3DVFH+（three dimensional vector field histogram +），由二維的VFH+改良而來，藉由排除絕對不能走的路徑，選出不會太糟的未來路徑。演算法可分為五個步驟：一、將周遭障礙物分布以八叉樹圖（octomap）記錄，八叉樹的特徵如圖一所示，每個上層節點會有八個子節點，可以想像是將一個立方體等分為八個子立方體，持續分割到選定的最小解析度，每個方格儲存該位置有障礙物的機率，該機率可以從SLAM演算法或是深度相機來取得。樹的資料結構好處在於，倘若該母節點以下的子節點都是零，那就沒有儲存必要，只要將母節點標記為零即可，得以大幅減少記憶體需求。又避障通常不需要全局的地圖障礙物位置，所以僅取鄰近機器人之立方體考慮。

第二步是該演算法的關鍵步驟，以極座標直方圖（polar histogram）的格式描述周遭環境（如圖二）。上一步提到取一個立方體檢視其障礙物分布，我們進一步在立方體內取半徑最大之球體，如此每個格子（voxel）就能用方位角和仰角描述，將球面攤平，形成一張以方位角和仰角為座標的直方圖，圖中每一格填入該位置障礙物的存在機率，即為二維極座標直方圖。接著第三步，考慮機器人本身移動速度較快時，無法立即改變運動狀態，在這樣的狀態下轉彎可能會比靜止時多前進一段距離，所以快速移動時，演算法會額外考慮轉彎途經之處的八叉樹格點是否有障礙物。

第四，為降低演算法的記憶體消耗，我們進一步將二維直方圖的數值以一個位元（bit）表示，很直覺地可以藉由設定閾值（threshold）達成。最後，該如何斷向哪個方向走最好？最簡單就是找一塊直方圖值皆為零的區域，因此將一個固定窗格滑過整面直方圖（圖三），即可選出數個候選方向。接下來又怎麼決定誰能從中脫穎而出？一般來說，我們都希望選出的路徑能和我們的目標地最為靠近，同時避免大量轉彎，我們能透過設計對應的成本函數（cost function），計算各候選方向的成本，從中挑選成本最低者，即完成一次路徑規劃。

撰文：姚皇宇

原始文獻：S. Vanneste, B. Bellekens, and M. Weyn, “3DVFH+: Real-Time Three-Dimensional Obstacle Avoidance Using an Octomap,” p. 12.