本研究以Voronoi結構劃分為前處理步驟，結合支向機分類器構築一個起點與終點間的機器人安全平滑路徑規劃模型。Voronoi結構劃分於路徑規劃上具有快速產生路徑與路徑和障礙物間保有一定距離不發生碰撞的優點，而支向機最大化邊限原則結合其高斯核函數，兼具維持與障礙物間的安全距離，且具有產生平滑決策曲線的能力，賦予所規劃的路徑具有安全又平滑的特性。於本研究中，爲配合Voronoi結構劃分與支向機的應用，系統以一單擊函數將地圖上障礙物轉換成障礙物單點的型態，並透過額外添加的框架點與夾點，以框架點改善Voronoi路徑的準確性，加上夾點於起點與終點間限制支向機決策曲線之走向並限制其範圍。另外本研究也探討了影響系統的相關參數，詳細討論各參數對路徑安全性與平滑的影響，創新一以安全性為前提的平滑路徑規劃模型。

The paper presents a new model merging Voronoi tessellation with the optimization of support vector machine (SVM) which aims to develop a path planning for guiding a mobile robot safely and smoothly in the space with obstacles. Being a cell decomposition method for path generation, a Voronoi tessellation is employed as a preprocessor to rapidly generate a rough path in the 2-dimentional configuration space. The geometric property of Voronoi tessellation keeps the path distant away from obstacles as far as possible. Consecutively, a SVM postprocessor is used to transform the rough path into a smooth path. Based on the statistical learning theory, the large margin SVM with RBF kernel can used to generate an artificial Gaussian potential field. With the Gaussian potential field, a large margin zero-potential curve is thus obtained in the configuration space. The idea of large margin implies that a wide path can be obtained with the employment of the SVM. Sharing the merits of both planning stages, a safe and smooth path can b eventually produced. In the 2-stage path planner, obstacles can be simplified as a class of obstacle singletons for efficient computation. With the class of obstacle singletons, additional outer-frame singletons and clip points are employed to improve feasibility to draw a safe and smooth path from the starting point to the goal. Moreover, effects of corresponding parameters are detailed discussed in the paper. Plentiful planning examples are also included for approval of the feasibility of the safe and smooth path planner for real application.

中文摘要..................................................................................................... I
英文摘要....................................................................................................II
目錄.......................................................................................................... IV
圖目錄.....................................................................................................VII
表目錄...................................................................................................... IX
第一章 緒論...........................................................................................1
1-1 前言...............................................................................................1
1-2 研究動機與目的...........................................................................1
1-3 相關文獻探討...............................................................................2
第二章 基礎理論...................................................................................5
2-1 二維支向機分類器所產生之零勢能線......................................5
2-1-1 支向機分類器........................................................................5
2-1-2 零勢能線................................................................................8
2-2 RBF 核於支向機中之作用........................................................10
2-2-1 核函數的基本涵義..............................................................10
2-2-2 高斯徑向基核(RBF 核) ......................................................12
2-3 Voronoi 結構劃分.....................................................................15
2-4 支向機訓練樣本權重調整.........................................................17

2-4-1 權重調整之方法..................................................................17
2-4-2 由變異核函數調整樣本權重..............................................18
2-5 平滑指標.....................................................................................19
2-5-1 平滑的意義..........................................................................19
2-5-2 平滑指標的計算..................................................................19
第三章 模型架構.................................................................................21
3-1 支向機訓練樣本點配置.............................................................23
3-2 產生Voronoi 路徑.....................................................................29
3-3 指定二類別標籤.........................................................................31
3-4 支向機平滑路徑規劃.................................................................34
3-5 路徑座標產生.............................................................................35
3-6 參數調整.....................................................................................37
第四章 實驗與討論.............................................................................39
4-1 實驗流程.....................................................................................39
4-2 與三次雲規曲線擬合法比較.....................................................40
4-2-1 案例比較..............................................................................40
4-3 考慮框架點對整體規劃之影響.................................................44
4-3-1 框架點對Voronoi 路徑的影響..........................................46
4-3-2 框架點對支向機規劃決策曲線的影響..............................48
VI
4-4 考慮夾點參數對平滑度的影響.................................................51
4-4-1 夾點間距大小的影響..........................................................51
4-4-2 夾點方向性的影響..............................................................59
4-5 調整訓練樣本權重對路徑的影響............................................61
4-6 以平滑指標最佳化路徑.............................................................64
4-6-1 最佳化方法..........................................................................65
4-6-2 實驗驗證..............................................................................65
4-6-3 討論......................................................................................72
4-7 安全性考量.................................................................................73
4-7-1 考慮實際車體因素..............................................................73
4-7-2 案例模擬驗證......................................................................75
4-8 不同場景下完成的平滑路徑規劃模擬....................................83
第五章 結論.........................................................................................88
參考文獻...................................................................................................89
附錄一 調整間距大小另ㄧ例................................................................95

圖目錄
圖2-1 支向機邊限示意圖........................................................................8
圖2-2 支向機用以規劃勢能場路徑之概念..........................................10
圖2-3 調整σ 與RBF 核勢能影響範圍的關係....................................14
圖2-4 Voronoi Digram.............................................................................16
圖2-5 平滑指標計算示意圖..................................................................20
圖3-1 路徑規劃模型架構與規劃流程..................................................22
圖3-2 大型障礙物取樣示意圖..............................................................25
圗3-3 框架點配置步驟..........................................................................27
圖3-4 夾點示意圖..................................................................................29
圖3-5 Voronoi 路徑.................................................................................31
圖3-6 指定訓練樣本不同的類別標籤，以供進一步路徑規劃..........33
圖3-7 實線為經支向機分類規劃後產生的分類線..............................34
圖3-8 路徑座標點的產生示意圖..........................................................36
圖4-1 實驗流程圖..................................................................................39
圖4-2 本研究與其他曲線擬合法平滑路徑規劃之比較......................44
圖4-3 Voronoi 區塊示意圖.....................................................................46
圖4-4 框架點的影響..............................................................................47
圖4-5 訓練樣本點少而邊限大大造成分類決策曲線間斷各自為政..49

圖4-6 加入框架點產生較細碎綿密的勢能有助於產生平順的路徑..50
圖4-7 夾點間距d 對容許決策曲線存在空間的影響..........................53
圖4-8 夾點間距d 對路徑規劃影響的一例..........................................58
圖4-9 不同夾點方向對路徑平滑的影響..............................................61
圖4-10 不同夾點方向對路徑平滑的影響............................................64
圗4-11 例1 經最佳化處理後................................................................68
圗4-12 例2 系統預設參數之平滑路徑規劃........................................68
圗4-13 例2 經最佳化處理後................................................................70
圗4-14 例3 系統預設參數之平滑路徑規劃........................................70
圗4-15 例3 經最佳化處理後................................................................72
圗4-16 考慮車寬的兩種狀況................................................................75
圖4-18 考慮車寬條件下的路徑規劃情形............................................80
圖4-19 行走轉彎場景障礙規避情形....................................................82
圖4-20 各式場景完成規劃後的平滑路徑............................................87
圖4-22 調整間距間距大小另一例........................................................98
表目錄
表4-1 與三次雲規曲擬合之數據比較..................................................44
表4-2 各種不同設定d 值所產生的影響..............................................58
表4-3 不同θ 造成的影響......................................................................61
表4-4 例1 最佳化過程..........................................................................67
表4-5 例2 最佳化過程..........................................................................69
表4-6 例3 最佳化過程..........................................................................71
表4-7 調整間距間距大小另一例...........................................................99

[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, Vic., 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, 2(2):121-167,
1998.
[7] A. Bowyer, Computing Dirichlet tessellations, The Computer
Journal 24(2):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] 許哲彰，「聯結k 最近鄰域與支向機之模式識別」，碩士論文，
淡江大學機械與機電學系，民國九十五年
[10] M. L. Steven, Planning Algorithms, Cambridge University Press,
2006.
[11] N. Amato, Randomized Motion Planning, A Brief Introduction: The
Motion Planning Problem Configuration Space Basic Path Planning
Methods, Univ. of Padova, 2004.
[12] Á. S. Miralles and M. Á. S. Bobi, Global Path Planning in
Gaussian Probabilistic Maps, Journal of Intelligent and Robotic
Systems 40: 89–102, 2004.
[13] M. Greytak, “Numerical Potential Field Path Planning Tutorial,”
December 9, 2005.
[14] I. M. Mitchell and S. Sastry, “Continuous Path Planning with
Multiple Constraints,” In Proceeding of CDC , 2003.
[15] A. Scheuer and Th. Fraichard, “Planning Continuous-Curvature
Paths for Car-Like Robots,” IEEE/RSJ Int. Conf. on Intelligent
Robot and Systems, Volume 3, pp. 1304-1311, Osaka, Japan, 1996.
[16] P. N. Azariadis and N. A. Aspragathos, Obstacle representation by
Bump-surfaces for optimal motion-planning, Robotics and
Autonomous Systems, 51:129–150, 2005.
[17] J. S. Lee and Y. D. Kwon, “A stochastic map building method for
mobile robot using 2-D laser ranger finder,” Autonomous Robots 7,
Kluwer Academic Publishers, Dordrecht, pp. 187-200, 1999.
[18] J. Miura, “Support Vector Path Planning,” Proceedings of the 2006
IEEE/RSInternational Conference on Intelligent Robots and
Systems, October 9-15, Beijing, China, 2006.
[19] F. Y. Chou, C. Y. Yang, J. Wang and J. S. Yang, “Support Vector
Machine Based Artificial Potential Field for Autonomous Guided
Vehicle,” The 4th International Symposium on Precision
Mechanical Measurements(ISPMM08), Hefei, China, 2008.
[20] H. F. Durrant-Whyte, M. de Battista, S. Majumbder, S. Thrun and S.
J. Scheding, “A bayesian algorithm for simultaneous localisation
and map building,” In Proceedings of 10th International Symposium
of Robotics Research(ISRR 2001), 49-66, Lorne, Victoria, 2003.
[21] A. J. Smola and B. Schölkoph, Learning with kernels, MIT Press,
Cambridge, MA, 2002.
[22] J. Shawe-Taylor and N. Cristianini, Kernel methods for pattern
analysis, MIT Press, Cambridge, MA, 2004.
[23] C. Cortes and V. N. Vapnik, “Support vector networks. Machine
Learning,” 20:273-297, 1995.
[24] Q. Du, V. Faber, and M. Gunzburger, Centroidal Voronoi
Tesselations: Applications and Algorihms, SIAM Review, 41, no. 4,
pp. 637-676, 1999.
[25] R. Akbani, S. Kwek and N. Japkowicz, “Applying Support Vector
Machines to Imbalanced Datasets,” Lecture Notes in Computer
Science, ECML , 3201:39–50, 2004.
[26] N. Chawla, K. Bowyer, L. Hall and P. Kegelmeyer, SMOTE:
Synthetic Minority Over-sampling Technique, Journal of Artificial
Intelligence Research, 16:321–357, 2002.
[27] K. Veropoulos, C. Campbell and N. Cristianini. “Controlling the
Sensitivity of Support Vector Machines,” In Proceedings of
International Joint Conference on Artificial Intelligence, 55–60,
1999.
[28] C. Y. Yang, J. Wang, J. S. Yang and G. D. Yu, “Imbalanced SVM
learning with margin compensation,” The Fifth International
Symposium on Neural Networks (ISNN2008), September 24-28,
Beijing, China, 2008.
[29] N.V. Chawla, N. Japkowicz and A. Kotcz, “Editorial: Special issue
on learning from imbalanced data sets,” SIKDD Explorations
Newsletters, 6(1), 1--6 , 2004.
[30] G. M. Weiss, Mining with Rarity: A Unifying Framework.
Newsletter of the ACM Special Interest Group on Knowledge
Discovery and Data Mining,” 6(1):7–19, 2004.
[31] A. Elkan, “The foundations of cost-sensitive learning,” In B. Nebel
Ed., Proceedings of the seventeenth international joint conference
on artificial intelligence, Morgan Kaufmann, San Fransisco,
973–978, 2001.
[32] S. Wu and S. I. Amary, “Conformal Transformation of Kernel
Functions: A Data-Dependent Way to Improve Support Vector
Machine Classifier,” Neural Processing Letters, 15: 59-67, 2002.
[33] G.Wu and E. Y. Chang, KBA: Kernel Boundary Alignment
Considering Imbalanced Data Distribution, IEEE
TRANSACTIONS ON KNOWLEDGE AND DATA
ENGINEERING, Vol. 17, No. 6, JUNE, 2005.
[34] Q. Chang, Q. Chen and X. Wang, “Scaling Gaussian RBF kernel
width to improve SVM classification,” International Conference on
Neural Networks and Brain, October 13–15, Beijing, China, 2005.
[35] R. H. Bartels, J. C. Beatty and B. A. Barsky, Hermite and Cubic
Spline Interpolation, CA: Morgan Kaufmann, pp. 9-17, San
Francisco, 1998.
[36] M. J. D. Powell, Direct search algorithms for optimization
caculations, published in Acta Numerica, Vol. 7, Cambridge
University Press 1998.
[37] T. G. Kolda, R. M. Lewis and V. Torczon, Optimization by Direct
Search: New Perspectives on Some Classical and Modern Methods,
SIAM REVIEW, Vol. 45, No. 3, pp.385-482, 2003.