Vector Field Histogram算法,簡稱VFH算法,直譯為“向量場直方圖算法”。是一種由人工勢場法改進而來的機器人導航算法。
算法會計算各個方向的行進代價,該方向的障礙越多,代價越高,並且會累加該方向不同距離的障礙物(根據距離,權重不同)。
根據不同方向的行進代價,可以直觀的用一個柱狀圖表示。橫坐標為0-360度的方向,縱坐標是該角度下的行進代價。柱狀圖越高,表示向該方向行進的代價越高,也表明越不可能通過。
理論上,這個柱狀圖低的區域是便於行進的,但可能會偏離目標方向,因此,需要一個平衡函式來平衡行進代價和目標方向。最終,會選擇一個相對最適宜的方向行進。於是這個函式便是整個算法的核心。
基本介紹
- 中文名:VFH算法
- 外文名:Vector Field Histogram
- 本質:人工勢場法改進的機器人導航算法
背景介紹,特點,VFH+,VFH*,
背景介紹
在機器人技術中,方向區間柱圖法(VFH)是Johann Borenstein和Yoram Koren在1991年提出的實時運動規划算法。VFH通過所謂的直方圖格線利用機器人環境的統計表示,因此非常重視處理感測器和建模誤差的不確定性。與其他避障算法不同,VFH考慮了機器人的動態和形狀,並返回特定於平台的轉向命令。雖然被認為是局部路徑規劃器,即不是為全局路徑最優性而設計的,但已經證明VFH產生接近最佳的路徑。
最初的VFH算法基於以前關於虛擬力場的工作,虛擬力場是一種本地路徑規划算法。 VFH於1998年由Iwan Ulrich和Johann Borenstein更新,並更名為VFH +(非正式“增強型VFH”)。該方法於2000年由Ulrich和Borenstein再次更新,並更名為VFH *。VFH是移動機器人中最受歡迎的本地規劃者之一,與後來開發的動態視窗方法競爭。許多機器人開發工具和模擬環境都包含對VFH的內置支持。
特點
方向區間柱圖法的開發目標是計算效率高,魯棒性強,對誤讀不敏感。實際上,VFH算法已被證明是快速可靠的,特別是在穿越人口稠密的障礙物時。
在VFH算法的中心是通過直方圖格線使用障礙物的統計表示(也參見占用格線)。這種表示非常適合於不準確的感測器數據,並適應多個感測器讀數的融合。
VFH算法包含三個主要組件:
- 笛卡爾直方圖格線:二維笛卡爾直方圖格線由機器人的距離感測器構成,例如聲納或雷射測距儀。格線實時不斷更新。
- 極坐標直方圖:通過減少機器人瞬時位置周圍的笛卡爾直方圖來構建一維極坐標直方圖。
- 候選谷:基於與目標方向的接近度來選擇具有低於閾值的極性障礙物密度的連續扇區,稱為candidate valleys。
一旦確定了所選候選方向的中心,就控制機器人的方向以匹配。當正面接近障礙物時,機器人的速度會降低。
VFH+
VFH +算法的改進包括:
- 閾值滯後:滯後增加了計畫軌跡的平滑度。
- 機器人體型:考慮了不同尺寸的機器人,無需通過低通濾波器手動調整參數。
- 障礙物前瞻:被障礙物阻擋的扇區被掩蓋在VFH +中,因此轉向角不會被引導到障礙物中。
- 成本函式:添加成本函式以更好地表征算法的性能,並且還通過更改成本函式或其參數來提供在行為之間切換的可能性。
VFH*
2000年8月,Iwan Ulrich和Johann Borenstein發表了一篇描述VFH *的論文,聲稱通過明確處理局部規划算法的缺點來改進原始的VFH算法,因為不能確保全局最優性。 在VFH *中,算法驗證使用A *搜尋算法產生的轉向命令,以最小化成本和啟發式函式。 雖然在實踐中很簡單,但在實驗結果中已經證明,這種先行驗證可以成功地處理原始VFH和VFH +無法處理的有問題的情況(由此產生的軌跡快速平滑,在存在障礙物時沒有顯著減速)。