基於VFH之混和導航系統設計

VFH-Based Hybrid Navigation System Design

謝明樺(Ming-Hua Hsieh)

指導教授 ： 李世安

淡江大學/工學院/電機工程學系碩士班/碩士(2015年)

https://doi.org/10.6846/TKU.2015.00942

摘要

本論文提出一基於VFH之混和導航系統，此系統可在初步已知地圖之情形下進行機器人之全域路徑規劃及區域路徑規劃。此系統分為兩層，第一層為思慮層，第二層為反應層。在思慮層內利用初步已知地圖自動轉換成晶格地圖並修整，利用影像處理之閉運算概念將機器人無法到達及危險區域先行剔除，並進行晶格權重均勻化再搭配修正式A*演算法進行全域路徑規劃，並提取路徑之轉折點。在反應層內，機器人在轉折點間可利用區域避障演算法進行避障。本論文使用向量直方圖演算法(Vector Field Histogram, VFH)作為區域路徑規劃之演算法，首先依據雷射測距儀之資訊並轉換為長方圖後，再根據演算法內之評估函式計算最佳行進方向，進而達到機器人避障之效果。本論文亦實現虛擬力場演算法(Virtual Force Field, VFF)並與向量直方圖演算法比較其優劣。本論文提出之系統可使移動機器人在居家環境內遭遇預期外障礙物時，可以安全地避開障礙物並有效率的移動。

關鍵字

機器人導航 ； 路徑規劃 ； 向量直方圖法 ； 移動機器人

並列摘要

This paper proposes a VFH-based (vector field histogram based) hybrid navigation system. This system can execute global path planning and local path planning based on the rough map. The VFH-based hybrid navigation system can be described into two layers. The first layer is deliberative layer and the second layer is reactive layer. In the deliberative layer, the system automatically builds a grid map based on the rough map, which the robot has known. The concept which closing operation of image processing is used to modify the grid map to avoid the robot enters some dangerous areas. In the global path planning, the system uses an A* modified algorithm to execute the global path planning and extract the turning points on the path. In the reactive layer, the system uses local path planning algorithm to avoid some obstacles between two turning points. In this paper, the VFH algorithm is used to create a histogram via the laser range finder. A cost function is used to decide the best moving direction to avoid the obstacles. This paper also implements a virtual force field (VFF) algorithm to compare with the VFH algorithm. Form the results, we discusses the advantage and disadvantage between the two methods. Finally, this system makes the robot to avoid unexpected obstacles safely and move effectively in the home environment.

並列關鍵字

Robot Navigation ； Path Planning ； VFH ； Mobile Robot

參考文獻

[3] M. Barbehenn, “A note on the complexity of Dijkstra’s algorithm for graphs with weighted vertices,” IEEE Transaction on Computers, vol.47, no.2, p.263, 1998.

[4] T. Goto, T. Kosaka, and H. Noborio, “On the heuristics of A* or a algorithm in ITS and robot path-planning,” 2003 IEEWRSJ International Conference on Intelligent Robots and Systems, Las Vegas, Nevada, pp. 1159-1166, 2003.

[5] I. Chabini and L. Shan, “Adaptations of the A* algorithm for the computation of fastest paths in deterministic discrete-time dynamic networks,” IEEE Transaction on Intelligent Transportation Systems, vol.3, no.1, pp.60-74, 2002

[6] P.E. Hart, N.J. Nilsson, and B. Raphael, “A formal basis for the heuristic determination of minimum cost paths in graphs,” IEEE Transaction of Systems Science and Cybernetics. vol.SSC-4, no.2, pp.100-107, 1968.

[7] G.E. Jan, K.Y. Chang, and I. Parberry, “Optimal path planning for mobile robot navigation,” IEEE/ASME Transaction on Mechatronics, vol. 13, no. 4, pp. 451-459, 2008.