本研究之目的是以分類理論為基礎，來建立一個機器人之避障路徑規劃與實現，藉由所研發之安全平滑路徑規畫為基礎，以樂高機器人驗證所發展的路徑規畫及實際導航。本研究之路徑規畫結合Voronoi結構劃分與支向機分類器，使規劃路徑具備安全平滑之特性。系統藉由影像擷取、影像處理、路徑規劃、配合模糊回授控制進行機器人導航，用以驗證各種障礙物配置之變化，並藉以探討系統各項參數之影響。實驗顯示我們所發展之即時系統成功地反應不同障礙物之變化，找出最佳之安全平滑路徑，所發展之機器人控制也盡可能地適應所規畫之路徑，從起點走向終點，最後以反覆試驗藉統計學之ANOVA分析其在各條件下各導航結果之差異，以探討系統重現性，經實作測試，結果成效良好。

The path planning of mobile robots to avoid obstacles in the configuration space is an important topic in the field of robotics. Merging Voronoi tessellation and support vector machine (SVM), we have developed theoretically a method to provide an optimized safe and smooth path in our previous study. The paper re-examines the method and constructs practically a framework of path following system for a mobile robot to realize and implement the theoretical development. The system comprises sub-systems of image acquisition, and processing, path planning, and fuzzy inference for feedback calibration of the path following of the mobile robot. With the small scale real system, experiments can take place practically for validation. The paper describes mainly the establishment of the real system. Plentiful experimental results are also included in the paper for evidence of the success of the proposed developments, not only the algorithmic path planning but also the applied robotic path following. Despite the changes of the obstacle configuration, the mobile robot demonstrates the excellent capability of reaching its goal by following the planned path safely and smoothly. A series of quantitative analysis is then followed for investigating influence of the system factors using ANOVA analysis.

目錄
誌謝	I
中文摘要	II
英文摘要	III
目錄	V
圖目錄	VIII
表目錄	XI
第一章	緒論	1
1-1.	前言	1
1-2.	研究動機與目的	2
1-3.	相關文獻	3
第二章	基礎理論	6
2-1.	Voronoi 結構劃分	6
2-2.	高斯核支持向量機 (GKSVM, Gaussian Kernel Support Vector Machine)	8
2-3.	模糊控制	13
2-3-1.	模糊理論簡介	13
2-3-2.	模糊理論	17
第三章	研究設備與方法	21
3-1.	研究設備	21
3-1-1.	設備概述	21
3-1-2.	Matlab	22
3-1-3.	輪型機器人(LEGO NXT)	23
3-1-4.	場地	26
3-1-5.	簡易攝影機	27
3-1-6.	通訊設備	28
3-1-7.	RWTH(Rheinisch Westfälische Technische Hochschule) Toolbox功能	30
3-2.	研究方法	30
3-2-1.	影像擷取	32
3-2-2.	影像校正	34
3-2-3.	影像處理	39
3-2-4.	路徑規劃	41
3-2-5.	機器人導航	53
3-2-6.	UI介面及導行結果	59
第四章	實驗與討論	62
4-1.	影像校正與侵蝕膨脹結果	63
4-2.	不同場景下之案例討論	67
4-3.	路徑導航重現性	74
4-4.	影像校正對行駛路徑的影響	76
4-5.	歸屬函數之定義對行駛路徑的影響	79
4-5-1.	輸出歸屬函數的影響	79
4-5-2.	輸入歸屬函數的影響	85
4-6.	步長對行駛路徑的影響	91
4-7.	導航前角度對準功能對行駛路徑的影響	95
4-8.	納入邊界考量對SVM路徑的影響	98
第五章	結論與討論	102
參考文獻	103
附錄一	109

 
圖目錄
圖2-1. Voronoi Diagram	8
圖2-2. 支向機邊限示意圖	13
圖2-3. 三角形歸屬函數	16
圖2-4. 梯形歸屬函數	16
圖2-5. 高斯形歸屬函數	17
圖2-6. 單值形歸屬函數	17
圖2-7. 模糊邏輯控制基本架構圖	19
圖3-1. 系統場地模擬圖	22
圖3-2. NXT主機	24
圖3-3. 組裝完成之機器人	25
圖3-4. 動態方程式示意圖	25
圖3-5. 場地實景圖	27
圖3-6. WebCam實體圖	28
圖3-7. 藍芽連結介面	29
圖3-8. 研究流程圖	32
圖3-9. WebCam擷取之場景圖	33
圖3-10. 校正格線佈置圖	35
圖3-11. 影像校正前之扭曲與未扭曲格點比較	37
圖3-12. 影像處理流程	40
圖 3-13. 求像素之圓心示意圖	41
圖 3-14. 路徑規畫模型架構圖[9]	41
圖 3-15. 框架點建立步驟圖	44
圖3-16. 夾點示意圖	45
圖 3-17. Voronoi 路徑步驟圖	47
圖 3-18. 有無納入車寬考量比較圖	49
圖 3-19. 路寬限制示意圖	49
圖 3-20. 二類別標籤圖	51
圖 3-21. 支向機之平滑曲線圖	52
圖 3-22. 路徑追蹤與誤差	55
圖3-23. 模糊控制器	56
圖3- 24. 路徑追蹤控制器輸出入歸屬函數	58
圖 3-25. Matlab GUI介面圖	60
圖 3-26 導航分解圖	61
圖4-1. 扭曲與未扭曲格點重疊比較	65
圖4-2. 侵蝕膨脹去除雜訊	66
圖4-3. 行進區域地形蜿蜒成S形案例	68
圖4-4. 隨機散佈障礙點案例	69
圖4-5. 起點或終點遠離障礙主聚落點案例	70
圖4-6. 不平衡之兩類別案例	71
圖4-7. 起點與終點互換之導航案例	72
圖4-8. 導航路徑平直案例	73
圖4-9. 導航路徑曲折案例	74
圖4-10. 導航路徑重現性示意圖	75
圖4-11. 施用或未施用影像校正之導航路徑比較	78
圖4-12. 輸出端比較之相關輸入歸屬函數	81
圖4-13. 輸出端之單值形與三角形歸屬函數比較	82
圖4-14. 單值形與三角形歸屬函數之導航路徑比較	84
圖4-15. 輸入端距離誤差比較之相關歸屬函數	87
圖4-16. 輸入端之距離誤差歸屬函數比較	88
圖4-17. 輸入端之距離誤差分佈區域大小比較	90
圖4-18. 步長於實際導航之比較	93
圖4-19. 導航前車體角度對準功能描述	96
圖4-20. 有無角度對準功能之導航路徑比較圖	97
圖4-21. 二類樣本點間距離過大比較	100
圖4-22. 二類樣本點個數差異過大比較	101
 
表目錄
表3-1路徑追蹤模糊規則庫	59
表4-1. 路徑導航檢驗重現性	76
表4-2. 施用影像校正與否之數據分析	79
表4-3. 輸入端之距離誤差歸屬函數常數設定	81
表4-4. 輸入端之角度誤差歸屬函數常數設定	82
表4-5. 單值形輸出之常數設定	83
表4-6. 三角形輸出之常數設定	83
表4-7. 單值形與三角形歸屬函數實際導航距離誤差比較	85
表4-8. 輸入端之角度誤差歸屬函數常數設定	87
表4-9. 輸出端之常數設定	88
表4-10. 分佈區域較小之歸屬函數常數設定	89
表4-11. 分佈區域較大之歸屬函數常數設定	89
表4-12. 歸屬函數分佈區域大小比較	91
表4-13. 節點間距步長大小數據分析	94
表4-14. 有無角度對準功能距離誤差比較	97

[1]	A. Zelinsky and I. Dowson, “Continuous smooth path execution for an autonomous guided vehicle,” TENCON '92. Technology Enabling Tomorrow : Computers, Communications and Automation towards the 21st Century, 1992 IEEE Region 10 International Conference, 871-875 vol. 2, Melbourne. 11-13 Nov., Australia, 1992.
[2]	T. Fraichard and M. Ahuactzin, “Smooth path planning for cars,” ICRA 2001: 3722-3727, Proceedings of the 2001 IEEE International Conference on Robotics and Automation, ICRA 2001, May 21-26, Seoul, Korea, 2001.
[3]	V. N. Vapnik, “The Nature of Statistical Learning Theory,” Springer- Verlag, New York, 1995.
[4]	V. N. Vapnik, “Statistical Learning Theory,” John Wiley & Sons, New York, 1998.
[5]	A. J. Smola, P. L. Bartlett, B. Schölkopf and D. Schuurmans, ”Advances in Large Margin Classifiers,” Cambridge, MA: MIT press, 2000.
[6]	C. J. C. Burges, “A tutorial on support vector machines for pattern recognition,” Data Mining and Knowledge Discovery, vol. 2, no. 2, pp. 121-167, 1998.
[7]	A. Bowyer, “Computing dirichlet tessellations,” The Computer Journal, vol. 24, no. 2, pp. 162-166, 1981.
[8]	H. Choset, K. Lynch, S. Hutchinson, G. Kantor, W. Burgard, L. Kavraki and Se. Thrun, “Principles of Robot Motion Theory, Algorithms, and Implementation,” A Bradford Book The MIT Press Cambridge, Massachusetts London, England, 2005.
[9]	周峰毅，安全平滑之機器人路徑規劃—基於大邊限支向機的研究，碩士論文，淡江大學機械與機電學系，民國九十六年
[10]	X. Ye, Y. Lei and H. Hou, “A complete navigation system for goal acquisition in unknown environments,” Autonomous robots, vol. 2, no. 2, pp. 127-145. 
[11]	X. Ye, Y. Lei and H. Hou, “Design of intelligent mobile vehicle system and it’s global optimal path planning,” Industrial Technology, 2008. ICIT 2008. IEEE International Conference on, Chengdu, April 21-24. 2008. pp. 1-5.
[12]	M. Takahashi, T. Suzuki, H. Shitamoto, T. Moriguchi, and K. Yoshida. “Developing a mobile robot for transport applications in the hospital domain,” Robotics and Autonomous Systems, vol. 58, Issue 7, pp. 889-899, 2010.
[13]	D. Bodhale, N. Afzulpurkar, and N. T. Thanh, “Path planning for a mobile robot in a dynamic environment,” in Proceedings of the 2008 IEEE International Conference on Robotics and Biomimetics, ROBIO 2008, Bangkok, Thailand, February. 2008, 21-26, pp. 2115-2120.
[14]	L. C. Bento ,G. Pires, U. Nunes, "A behavior based fuzzy control architecture for Path Tracking And obstacle avoidance ",Proceedings of the 5th Portuguese Conference on Automatic Control, pp. 341-346, 2002.  
[15]	M. Elie, S. Maarouf, and S. Hamadou, "A higher level path tracking controller for a four-wheel differentially steered mobile robot", Robotics and Autonomous System, vol. 54, pp. 23-33, 2006.
[16]	A. El Hajjaji, and S. Bentalba, "Fuzzy path tracking control for automatic steering of vehicles", Robotics and Autonomous Systems, vol. 43, Jun., pp. 203-213, 2003.
[17]	K. D. Do, Z. P. Jiang, and J. Pan, "Global robust adaptive path following of underactuated ship," Automatica, vol. 40, pp. 929-944, 2004.
[18]	Y. Kanyama, Y. Kimura, F. Miyazaki, T. Noguchi, "A stable tracking control method for an autonomous mobile robot", IEEE International Conference on Robotics and Automation, pp. 384-389, 1990. 
[19]	D. Nguyen and B. Widrow, “The truck backer-upper: an example of self-learning in neural networks,” IJCNN Int. Joint Conf. Neural Networks, vol.2, 1989, pp. 357-363.
[20]	C. M. Higgins and R. M. Goodman, “Fuzzy rule-based networks for control,” IEEE Trans. Fuzzy Syst., vol. 2, no. 1, 1994, pp. 82-88.
[21]	L. X. Wang, and J. M. Mendel, “Generating fuzzy rules by learning from examples,” IEEE Trans. Syst., Man, Cybern., vol. 22, no. 6, 1991, pp. 263-268.
[22]	S. G. Kong and B. Kosko, “Comparison of fuzzy and neural truck backer-upper control systems,” IJCNN Int. Joint Conf. Neural Networks, vol. 3, 1990, pp. 349 –358.
[23]	S. Honiden, M. E. Houle, C. Sommer, and M. Wolff, “Approximate shortest path queries using voronoi duals.” Proceedings of the National Science Council, Republic of China, Part A: Physical Science and Engineering , vol. 24, no. 2, pp. 115-119.
[24]	K. Lee, W. k. Chung, “Navigable Voronoi Diagram : A Local Path Planner for Mobile Robots using Sonar Sensors,” Intelligent Robots and Systems, 2007. IROS 2007. IEEE/RSJ International Conference on, San Diego, CA, Oct. 29 2007-Nov. 2 2007, pp. 2813-2818.
[25]	J. Miura, “Support Vector Path Planning,” Proceedings of the 2006 IEEE/RS International Conference on Intelligent Robots and Systems, October 9-15, Beijing, China, 2006.
[26]	J. Lei, Q. Song, J. Ma, L. Qiu, and Y. Ge, “Application of SVM in intelligent robot information acquisition and processing a survey,” in Proceedings of 2005 International Conference on Information Acquisition 2005, art. no. 1635077, pp. 175-180.
[27]	L. Lucchese and S.K. Mitra, “Correction of geometric lens distortion through image warping,” Proc. 3rd International Symposium on Image and Signal Processing and Analysis (ISPA'03), Rome, Italy,  September 2003.
[28]	D. Zorin and A. Barr, “Correction of geometric perceptual distortion in Pictures.” Computer Graphics, pp. 257-264, 1995.
[29]	Y. C. LIN,C. S. Fuh, ”Correcting distortion for digital cameras,” Proc. Natl. Sci, Counc. vol. 24, no.3, pp.115-119,2000.
[30]	Á. S. Miralles and M. Á. S. Bobi, “Global Path Planning in Gaussian Probabilistic Maps,” Journal of Intelligent and Robotic Systems 40: 89–102, 2004.
[31]	A. J. Smola and B. Schölkoph, “Learning with kernels,” MIT Press, Cambridge, MA, 2002.
[32]	L. A. Zadeh, “Fuzzy set,” Informat. Control, vol. 8, pp. 338-353, 1965.
[33]	L. A. Zadeh, “Fuzzy algorithm,” Informat. Control, vol. 12, pp. 94-120, 1968.
[34]	P. J. King, E. H. Mamdani, “The application of fuzzy control systems to industrial processes,” Automatica, vol. 13, pp. 235-242, 1977.
[35]	C. C. Lee, “Fuzzy logic in control system: fuzzy logic controller, part I,” IEEE Transaction on Systems Man and Cybernetics, vol. 20, no. 2, pp. 419-435.
[36]	C. C. Lee, “Fuzzy logic in control system: fuzzy logic controller, part II,” IEEE Transaction on Systems Man and Cybernetics, vol. 20, no. 2, pp. 404-418.
[37]	S. Fukami, M. Mizumoto, K. Tanaka, “Some considerations on fuzzy conditional inference,” Fuzzy Sets and Systems, vol. 4, no.3, 1980.
[38]	M. Mizumoto, H. J. Zimmermann, “Comparison of fuzzy reasoning methods,” Fuzzy Sets and Systems, vol. 8, no.3, 1982.
[39]	L. A. Zadeh, “The concept of a linguistic variable and its application to approximate reasoning-I,” Information Sciences, vol. 8, pp. 199-249, 1975.
[40]	L. A. Zadeh, “The concept of a linguistic variable and its application to approximate reasoning-Ⅱ,” Information Sciences, vol. 8, pp. 301-357, 1975.
[41]	L. A. Zadeh, “The concept of a linguistic variable and its application to approximate reasoning-Ⅲ,” Information Sciences, vol. 9, pp. 43-80, 1975.
[42]	E. H. Mamdani, “Application of fuzzy logic to approximate reasoning using linguistic synthesis,” IEEE Trans. on Computers, vol. 26, pp. 1182-1191, 1977.
[43]	RWTH - Mindstorms NXT Toolbox for MATLAB, Rheinisch Westfälische Technische Hochschule Aachen [OnLine]. Available: http://www.mindstorms.rwth-aachen.de/.
[44]	蔡爾傑，兩輪移動機器人之控制與驅動設計，淡江大學機械與機電工程學系碩士論輪，民國九十四年六月
[45]	E. M. Scharf and N. J. Mandic, “The application of a fuzzy controller to the control of a multi-degree-freedom robot arm,” Industrial Applications of Fuzzy Control, M. Sugeno, Ed. Amsterdam: North-Holland, pp. 41-62, 1985.