本論文提出一基於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.

目錄

中文摘要	I
英文摘要	II
目錄	III
圖目錄	V
表目錄	VIII
第一章	緒論	1
1.1	研究背景	1
1.2	研究動機	2
1.3	論文架構	4
第二章	居家保全機器人系統	5
2.1	居家保全機器人系統簡介	5
2.2	居家保全機器人軟體系統簡介	7
第三章	基於VFH之混和導航系統	11
3.1	混和導航系統簡介	11
3.2	思慮層 (Deliberative Layer)	13
3.2.1	晶格地圖修整	13
3.2.2	A*演算法	19
3.2.3	改良式A*演算法	23
3.3	反應層 (Reactive Layer)	26
3.3.1	虛擬力場法 (VFF)	27
3.3.2	向量直方圖法 (VFH)	33
3.4	障礙物之各種情形	38
3.4.1	轉折點間無障礙物或出現預期外之障礙物	40
3.4.2	預期外障礙物出現於轉折點上	40
第四章	實驗結果	43
4.1	修整前後晶格地圖之路徑比較	43
4.2	傳統A*與改良式A*之比較	44
4.3	預期外障礙物之避障結果	49
4.4	VFF演算法與VFH演算法之比較	53
第五章	結論與未來展望	55
參考文獻	57




圖目錄
圖 1.1、機器人領域三大研究範圍之涵蓋示意圖	2
圖 1.2、日本SOFTBANK公司所開發之機器人PEPPER	3
圖 2.1、居家保全機器之系統架構	5
圖 2.2、居家保全機器人	6
圖 2.3、居家環境示意圖	7
圖 2.4、居家保全機器人軟體系統架構	8
圖 2.5、居家保全機器人之人機介面	9
圖 2.6、居家保全機器人之模擬器	10
圖 2.7、居家保全機器人之模擬器模擬雷射資訊	10
圖 3.1、機器人導航系統架構	11
圖 3.2、混和導航系統之系統架構圖	13
圖 3.3、已知地圖轉換為基礎晶格地圖	14
圖 3.4、利用基礎晶格地圖所規劃之路徑	15
圖 3.5、已知地圖轉換為基礎晶格流程圖	16
圖 3.6、侵蝕遮罩、膨脹遮罩即均勻化遮罩	16
圖 3.7、基礎晶格地圖經過封閉運算	18
圖 3.8、修整過後之基礎晶格地圖	19
圖 3.9、A*演算法之流程圖	20
圖 3.10、g(n)之計算方法	21
圖 3.11、h(n)之計算方法	21
圖 3.12、展開並評估個相鄰晶格之成本	22
圖 3.13、以新晶格為新起點再次搜尋迭代	22
圖 3.14、利用A*演算法所規劃之路徑	23
圖 3.15、傳統A*演算法缺陷示意圖	23
圖 3.16、改良式A*搜尋流程	24
圖 3.17、基本A*與改良式A*之搜尋結果比較	25
圖 3.18、思慮層計算之路徑及轉折點	26
圖 3.19、VFF演算法之計算流程圖	28
圖 3.20、VFF之虛擬力場概念示意圖	30
圖 3.21、合力為零時之避障方向示意圖	31
圖 3.22、使用VFF在狹窄環境時之震盪現象示意圖	32
圖 3.23、VFH演算法流程圖	34
圖 3.24、雷射測距儀偵測目前環境	35
圖 3.25、雷射測距儀資訊轉換為直方圖	35
圖 3.26、建立基本掃描窗	36
圖 3.27、掃描窗偵測障礙物示意圖	37
圖 3.28、障礙物之各種情形	39
圖 3.29、轉折點間無障礙物或出現預期外障礙物	40
圖 3.30、轉折點上有預期外障礙物之處理方法	41
圖 3.31、轉折點上有預期外障礙物與其他障礙物連結	42
圖 4.1、使用修整前和修整後晶格地圖之路徑比較	43
圖 4.2、目標點為客廳之路徑	44
圖 4.3、目標點為餐廳之路徑	45
圖 4.4、目標點為臥室之路徑	45
圖 4.5、目標點為書房之路徑	46
圖 4.6、速度規劃之S型函數	49
圖 4.7、無預期外障礙時機器人移動之軌跡	50
圖 4.8、有預期外矩形障礙時機器人移動之軌跡	51
圖 4.9、有預期外圓形障礙時機器人移動之軌跡	52
 
表目錄
表 4.1、傳統A*演算法與改良式A*演算法之比較	47
表 4.2、轉折點數與路徑長效益之比較表	48
表 4.3、VFF與VFH法移動時間與路徑比較表	54

參考文獻
[1]	Google Puts Money on Robots, Using the Man Behind Android – from The New York Times
Website http://www.nytimes.com/2013/12/04/technology/google-puts-money-on-robots-using-the-man-behind-android.html
[2]	Google Adds to Its Menagerie of Robots– from The New York Times
Website http://www.nytimes.com/2013/12/14/technology/google-adds-to-its-menagerie-of-robots.html/
[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.
[8]	M. Nakamiya, Y. Kishino, T. Terada, and S. Nishio, “A route planning method using cost map for mobile sensor nodes,” International Symposium on Wireless Pervasive Computing, pp.168-174, 2007.
[9]	I. Ulrich and J. Borenstein, “VFH+: Reliable obstacle avoidance for fast mobile robots,” Proceedings of the IEEE International Conference on Robotics and Automation, Leuven, Belgium, pp. 1572-1577, May, 1998.
[10]	I. Ulrich and J. Borenstein, “VFH*: Local obstacle avoidance with Look-ahead verification,” Proceedings of the IEEE International Conference on Robotics and Automation, San Francisco, CA pp. 2505-2511, , April 2000.
[11]	D. An and H. Wang, “VPH: A new laser radar based obstacle avoidance method for intelligent mobile robots,” Proceedings of the World Congress on Intelligent Control and Automation (WCICA), vol. 5, pp. 4681-4685, 2004.
[12]	A. Sgorbissa and R. Zaccaria, “Planning and obstacle avoidance in mobile robotics,” Robotics and Autonomous Systems, vol. 60, no.4, pp. 628-638, 2012.
[13]	J. Gong, Y. Duan, Y. Man, and G. Xiong, “VPH+: An enhanced vector polar histogram method for mobile robot obstacle avoidance,” Proceedings of the 2007 IEEE International Conference on Mechatronics and Automation (ICMA), art. no. 4304000, pp. 2784-2788, 2007.
[14]	Y. Zhu, T. Zhang, J. Song and X. Li, “A new bug-type navigation agorithm considering practical implementation issues for mobile robots,” Proceedings of the 2010 IEEE International Conference on Robotics and Biomimetics, Tianjin, China, pp. 531-536, Dec. 2010.
[15]	Y. Zhu, T. Zhang, J. Song and X. Li , “A new hybrid navigation algorithm for mobile robots in environments with incomplete knowledge,” Knowledge-Based systems, vol. 27, pp. 301-313, 2012.
[16]	T. Zhang, Y. Zhu, J. Song, “A hybrid path planning method for partly unknown environment,” ICROS-SICE international Joint Conference 2009, pp. 2485-2490, Fukuoka, Japan, 2009.
[17]	F. Mastrogiovanni, A. Sgorbissa and R. Zaccaria, “Robust navigation in an unknown environment with minimal sensing and representation,” IEEE Transactions on Systems, Man and Cybernetics, vol. 39, no.1, pp. 212-229, 2009.
[18]	J. Borenstein and Y. Koren, “Real-time obstacle avoidance for fast mobile robots,” IEEE Transactions on Systems, Man, and Cybernetics, vol. 19, no.5, pp. 1179-1187, 1989.
[19]	M. Zohaib, M.Pasha, R. A. Riaz, N. Javaid, M. Ilahi and R.D. Khan “Control strategies for mobile robot with obstacle avoidance,” Journal of Basic and Applied Scientific Research, vol.3, no.4, pp.1027-1036, 2013
[20]	J. Borenstein and Y. Koren, “The vector histogram - fast obstacle avoidance for mobile robot,” IEEE Transactions on Robotic and Automation, vol.7, no.3, pp.278-288, 1991.
[21]	C.J. Yu, Y.H. Chen, and C.C. Wong, “Path planning method design for mobile robots,” SICE Annual Conference, Tokyo, Japan, pp.1681-1686, Sep. 2011.