進階搜尋


 
系統識別號 U0026-0812200915130714
論文名稱(中文) 最佳化車輛防碰撞路徑規劃
論文名稱(英文) Optimal Collision-Free Path Planning for Vehicle
校院名稱 成功大學
系所名稱(中) 機械工程學系碩博士班
系所名稱(英) Department of Mechanical Engineering
學年度 97
學期 2
出版年 98
研究生(中文) 黃仲德
研究生(英文) Chung-Te Huang
電子信箱 calvinh.me92@nctu.edu.tw
學號 n1696154
學位類別 碩士
語文別 中文
論文頁數 97頁
口試委員 口試委員-張立東
指導教授-黃才烱
口試委員-黃金沺
中文關鍵字 閃避障礙物  防碰撞  路徑規劃 
英文關鍵字 Collision-Free  Path planning  Obstacle avoidance 
學科別分類
中文摘要 車輛防碰撞路徑規劃代表的是如何應用各種演算法來找尋一條車輛可以行走於障礙物之中且過程不會跟其他物體有任何接觸的最短路徑,其中防碰撞表示此路徑具有閃避障礙物的功能,這方面的理論可追朔自七零年代開始的機械手臂運動軌跡與障礙物的干涉討論,及其後陸陸續續衍生出了許多路徑規畫理論如Visibility Graph和potential field等,這些理論基礎也都成為汽車路徑規畫中重要的論述背景,但汽車與工具機之間仍存在許多運動上的差異,譬如迴轉半徑,因此本研究的重點在運動條件的限制下使路徑軌跡變得既單純且平滑上。
平滑曲線的設計上本研究採用Bezier Curve來描述路徑軌跡,接著利用最佳化方法求解,其中控制點位置為設計變數,最短的總路徑長度為目標函數,而車輛與障礙物的距離以及最小迴轉半徑則做為限制條件;但使用最佳化方法求解仍存在計算時間難以控制的問題,因此本論文的另一貢獻在於引入掃描體的連續概念,系統可沿汽車的路徑軌跡將整體的動作轉換成幾個簡易的凸多邊形,進而大幅減少演算系統花費在車體與障礙物之間距離計算的時間。
除演算系統的建立之外,本研究利用遙控車做為實體驗證模型,系統演算結果經過轉換之後,可控制遙控車依演算結果運行,藉此驗證演算結果的正確性。
英文摘要 Collision-Free path planning for vehicle is trying to find a path passing through the obstacles without any contact based on many different algorithms. For collision-free path planning, it means that this path must have some kind of ability in avoiding the obstacles. Research about this area has started in discussion about the interference between robots in 70’s, then coming out with several path planning algorithms such as Visibility Graph and potential field. These algorithms later become the important contribution in vehicle path planning. But there still exits many physical differences between robot and vehicle, such as minimum turning radius in vehicle but not for robot. So the burden of this research is to make the path trajectory simpler and smoother under the physical limits.

This research choose Bezier Curve as the smooth path trajectory. The control points of this curve then become the design variables in later optimal process with minimum path distance as the goal and distance between car and obstacles and turning radius as the limit. However, the time cost is an important issue in optimal process. To deal with this, this research try to involve the concept of swept volume in this problem, this turns the vehicle trajectory into several convex polygons. In this way the time cost in distance calculation between vehicle and obstacles might be reduced.

Except creating the path planning system, this research also construct a model by translate signals between the path planning system and the remote vehicle. So the remote vehicle could be act just as the system planning in the computer and identify that this path is reliable or not.
論文目次 中文摘要 i
Abstract ii
誌謝 iii
目錄 iv
圖目錄 vi
表目錄 viii
符號說明 ix
第一章 緒論 1
1.1研究背景與目的 1
1.1.1研究目的 1
1.1.2研究背景 2
1.2 論文架構 7
1.3研究流程圖 8
第二章 理論基礎 9
2.1 基本定義 9
2.1.1 座標系統定義 9
2.1.2 路徑方程式 10
2.1.3 速度計算 11
2.1.4 角度計算 11
2.1.5 迴轉半徑的計算 12
2.2 物體間的最短距離 13
2.3 掃描體的建立 17
2.4 路徑尋找理論 21
2.4.1 Feasible Reduced Visibility Graph 21
2.4.2 路徑規劃理論 22
2.4.3 頂點連線與障礙物間干擾的判斷方法 24
2.5 最佳化方法 27
第三章 研究方法 28
3.1 實驗設計 28
3.1.1 路邊停車格 28
3.1.2 倒車入庫 29
3.1.3 簡單障礙物穿越 30
3.2 實驗模型之建立 31
3.2.1 遙控晶片的控制 32
3.2.2 轉向機構 35
3.2.3 車體速度控制 36
3.3 最佳化方法之應用 38
3.3.1 目標函數 38
3.3.2 限制函數 38
3.3.3 預設值 40
第四章 電腦演算結果與討論 42
4.1 路邊停車 44
4.2 倒車入庫 52
4.3 其他障礙物情況下之演算成果 60
4.4 小結 62
第五章 實驗結果與討論 64
5.2 資料處理 66
5.3 遙控車的作動 66
5.4 小結 69
第六章 研究結果討論與結論 70
6.1 結論與建議 70
6.2 未來發展 71
參考文獻 72
附錄一 77
附錄二 94
自述 97
參考文獻 Arkin, R. C., Carter W. M. and Mackenzie D. C., “Active Avoidance: Escape and Dodging Behavior for Reactive Control,” International Journal of Pattern Recognition and Artificial Intelligence, Vol. 7 No. 1, pp.175-192, 1993.
Arora, J. S., Introduction to Optimum Design, ISBN 0-12-064155-0, 2nd edition, Elsevier, Inc., 2004.
Borenstein, J. and Koren, Y., “Histogramic In-motion Mapping for Mobile Robot Obstacle Avoidance,” IEEE Journal of Robotics and Automation, Vol. 7, No. 4, pp.535-539, 1991.
Borenstein, J. and Koren, Y., “The Vector Field Histogram-Fast Obstacle Avoidance for Mobile Robots,” IEEE Transaction on Robotics and Automation, Vol.7, No. 3, pp. 278-288, 1991.
Borenstein, J. and Ulrich, I., “VFH+: Reliable Obstacle Avoidance for Fast Mobile” Proceedings of the 1998 IEEE International Conference on Robotics and Automation, May 16–21, pp. 1572 – 1577, 1998.
Chang, S. and Li, T., “Design and Implementation of Fuzzy Parallel-parking Control of Type Mobile Robot,” Journal of Intelligent and Robotic Systems, Vol. 34, No.2, pp.175-94, 2002.
Dong, Z. and Yuan, J., “A Formulation for Collision Identification and Distance Calculation in Motion Planning Using Neural Networks,” International Journal Advanced Manufacturing Technology 8, pp. 227–234, 1993.

Ganter, M. A. and Ucker, J. J. Jr., “Dynamic Collision Detection Using Swept Solid,” Journal of Mechanisms, Transmissions, and Automation in Design, v.108, pp. 549-555, 1986.
Gray K. and Saunders K., “A Global and Local Obstacle Avoidance Technique for an Autonomous Vehicle,” Part of the SPIE Conference on Unmanned Ground Vehicle Technique, Orlando, Florida, April, Vol. 3693, 1999.
Guechi, E., Lauber, J. and Dambrine, M., “On-line Moving-obstacle Avoidance Using Piecewise Bezier Curves with Unknown Obstacle Trajectory,” 16th Mediterranean Conference on Control and Automation, June 25-27, pp.505-510, 2008.
Haddad, M., Chettibibi, T., Hanchi, S. and Lehtihet, H. E., “A Random- profile Approach for Trajectory Planning of Wheeled Mobile Ro- bots,” European Journal of Mechanics, A. Solids, Vol. 26, pp.519 -540, 2007 .
Huang, T. J., “An Approximate Swept Volume Strategy in 2-D Based On Hermite Interpolation for Optimization in Robot Motion Planning,” Master Thesis, State University of New York at Buffalo, Mechanical Eng., 1994.
Jiang, K., Seneviratne, L. D. and Earles, S. W. E., “Time Optimal Smooth-path Motion Planning for a Mobile Robot with Kinematic Constraints,” Robotica, Vol.15, pp. 547-553, 1997.
Jiang, K., Seneviratne, L. D. and Earles, S. W. E., “A Shortest Based Path Planning Algorithm for Nonholonomic Mobile Robots,” Journal of Intelligent and Robotic Systems, pp. 347-366, 1999.

Kanayama, Y. J. and Hartman, B. I., “Smooth Local-Path Planning for Autonomous Vehicles,” IEEE International Conference on Robotics and Automations, pp.1265-1270, 1989.
Khatib O., “Real-Time Obstacle avoidance for Manipulators and Mobile Robots,” 1985 IEEE International Conference on Robotics and Automations, March 25-28, pp. 500-505, 1985.
Keigger, J. and Litvin, F.L., “Swept Volume Determination and Interference Detection for Moving 3-D Solids,” Transactions of the ASME, Journal of Mechanical Design, Vol. 113, pp. 456-463, 1991.
Lee, D. T. and Drysdale, R. L., “Generalized Voronoi Diagrams in The Plane,” SIAM J. Computing, Vol. 10, pp. 73–87, 1981.
Lin, M. and Canny, J. F., “A Fast Algorithm for Incremental Distance Calculation,” International Conference on Robotics and Auto- mation, pp. 1008-1014, 1991.
Liu, C. Y. and Mayne, R. W., “Distance Calculations in Motion Planning Problems with Interference Situations,” Proceedings of the 1990 ASME Design and Technology Conference DE, Vol. 23-1, pp. 145–152, 1990.
Lozano-Perez, T. and Wesley, M. A., “An Algorithm for Planning Collision-Free Paths Among Polyhedral Obstacles,” Communica- tions of the ACM, Vol. 22, pp. 560-570, 1979.
Martinez-Marin, T., “Optimal Path Planning for Car-Like Vehicles in The Presence of Obstacles,” Intelligent Transportation Systems, Vol. 2, pp. 1161-1164, 2003.

Shoval, S., Borenstein, J. and Koren, Y., “The NavBelt-a Computerized Travel Aid for The Blind Based on Mobile Robotics Techn- ology,” Biomedical Engineering, IEEE Transactions, pp. 1376- 1386, Vol. 45, 1998.
Singh, S. K. and Leu, M. C., “Manipulator Motion Planning in The Presence of Obstacles and Dynamic Constraints,” The International Journal of Robotics Research, Vol.10, No.171-186, 1991.
Surmann, H. Huser, J. and Wehking, J., “Path Planning for A Fuzzy Controlled Autonomous Mobile Robot,” Fuzzy Systems, IEEE, Vol. 3, pp. 1660-1665, 8-11 Sept. 1996.
Takahasi, O. and Schilling, R. J., “Motion Planning in A Plane Using Generalized Voronoi Diagrams,” IEEE Transactions on Robotics and Automation, Vol. 5, pp.143-150, 1989.
Xu, J., Xie, M. and Lu, J., “Duplex Motion Planning Strategy for Automatic Manoeuvre of Vehicle in Complex Environment,” 2001 IEEE Intelligent Transaction Systems Conference Proceeding, August 25-29, pp. 292-297, 2001.
Zhang, P.Y., Lu, T. S. and Song, L. B., “Soccer Robot Path Planning Based on the Artificial potential field Approach with Simulated Annealing,” Robotica, Vol. 22, pp.563-566, 2004.
吳瑞鴻,張光仁,“車輛倒車運動軌跡理論推倒與驗證”,機電與工業管理文彙,2006
徐正會,蔡文鈞,“中心臂連桿型轉向機構之設計與分析”, 第四屆全國機構與機器設計學術研討會,第179-186頁,2001
豐田汽車台灣官方網站,規格配備,取自2009年5月11日,http://www.toyota.com.tw/, 2009
日產汽車台灣官方網站,規格配備,取自2009年5月11日,http://www.nissan.com.tw/,2009
福特六和汽車官方網站,規格配備,取自2009年5月11日,http://www.ford.com.tw/servlet/ContentServer?pagename=DFY/LH,2009
三菱汽車台灣官方網站,規格配備,取自2009年5月11日,http://www.mitsubishi-motors.com.tw/wps/portal,2009
本田汽車台灣官方網站,規格配備,取自2009年5月11日,http://www.honda-taiwan.com.tw/index.aspx,2009
馬自達汽車台灣官方網站,規格配備,取自2009年5月11日,http://www.mazda.com.tw/mainmenu.asp?lmenuid=1&smenuid=5,2009
論文全文使用權限
  • 同意授權校內瀏覽/列印電子全文服務,於2012-07-06起公開。
  • 同意授權校外瀏覽/列印電子全文服務,於2014-07-06起公開。


  • 如您有疑問,請聯絡圖書館
    聯絡電話:(06)2757575#65773
    聯絡E-mail:etds@email.ncku.edu.tw