作為一種既快捷又方便的交通工具，汽車已成為人們生活和工作中不可或缺的一部分。隨著汽車數量不斷地逐年增加，在同樣的城市空間中，每台車輛所平均分配到的停車空間也越來越少，進而加劇了停車入位的困難度。因此，許多車商都相繼開發出能提高安全性及省去人為操作的自動停車系統。自動停車系統作為先進駕駛輔助系統（ADAS）的其中一項重要功能，是汽車邁向自動駕駛的一個重要的墊腳石。
停車系統的最大挑戰是需要在狹窄的空間中進行，並且不能發生任何的碰撞，因此需要極為準確的路徑規劃。此外，產生路徑所需的時間和路徑的平滑度也非常的重要。短的規劃時間能提高停車操作的效率而平滑的路徑則能提高乘客的舒適性。
本論文通過結合基於隨機取樣的路徑規劃演算法和滿足車輛最短路徑的Reed-Shepp曲線，並通過三次樣條插值(Cubic spline interpolation)提高路徑的平滑度，實現滿足了低運算量和車輛非完整約束的停車路徑之規劃。此外，本論文也加入了車輛控制器和車輛動態模型以驗證所得到的停車路徑符合車輛的實際操作及限制。

As a fast and convenient means of transportation, cars have become an indispensable part of people's lives and work. As the number of cars continues to increase year by year, the average parking space allocated by each vehicle is getting less and less in the same urban space which further aggravates the difficulty of parking. Therefore, many car manufacturers have successively developed automatic parking systems that can improve safety and eliminate human operations. As one of the important functions of the advanced driving assistance system (ADAS), the automatic parking system is an important stepping stone for cars to move towards automatic driving.
The biggest challenge of the parking system is that it needs to be carried out in a narrow space with no collisions, so it requires extremely accurate path planning. In addition, the time required to generate a path and the smoothness of the path is also very important. Short planning time can improve the efficiency of parking operations and a smooth path can improve the comfortability of the passengers.
In this thesis, a path planning method for automatic parking that satisfies the low computation cost and vehicle non-holonomic constraint is proposed. The proposed planning method is a sampling based planning algorithm with the connection of Reeds-Shepp curve and it was smoothed by the cubic spline interpolation. In addition, this thesis also verifies the planned path with a reliable vehicle controller and vehicle dynamic model to ensure it conforms to the actual operation and limitation.

[1] “The Reality of Parking Lot Accidents and Preventing Them.” [Online]. Available: https://www.gregcolemanlaw.com/blog/parking-lot-accidents.html.
[2] “CNN.com - Toyota unveils car that parks itself - Sep. 1, 2003.” [Online]. Available: http://edition.cnn.com/2003/TECH/ptech/09/01/toyota.prius.reut/.
[3] Y.Zhao and E. G.Collins, “Robust automatic parallel parking in tight spaces via fuzzy logic,” Rob. Auton. Syst., vol. 51, no. 2–3, pp. 111–127, 2005.
[4] T.Ozkul, M.Mukbil, and S.Al-Dafri, “A fuzzy logic based hierarchical driver aid for parallel parking,” Proc. 7th WSEAS Int. Conf. …, no. April, pp. 357–361, 2008.
[5] Z.Liang, G.Zheng, and J.Li, “Automatic parking path optimization based on Bezier curve fitting,” in IEEE International Conference on Automation and Logistics, ICAL, 2012, pp. 583–587.
[6] F.Gómez-Bravo, F.Cuesta, A.Ollero, and A.Viguria, “Continuous curvature path generation based on β-spline curves for parking manoeuvres,” Rob. Auton. Syst., vol. 56, no. 4, pp. 360–372, 2008.
[7] S.Zhang, M.Simkani, and M. H.Zadeh, “Automatic vehicle parallel parking design using fifth degree polynomial path planning,” IEEE Veh. Technol. Conf., pp. 0–3, 2011.
[8] D.Dolgov, S.Thrun, M.Montemerlo, and J.Diebel, “Practical search techniques in path planning for autonomous driving,” AAAI Work. - Tech. Rep., vol. WS-08-10, pp. 32–37, 2008.
[9] P.Zips, M.Böck, and A.Kugi, “Optimisation based path planning for car parking in narrow environments,” Rob. Auton. Syst., vol. 79, pp. 1–11, 2016.
[10] M.Pivtoraiko, R. A.Knepper, and Alozo Kelly, “Differentially Constrained Mobile Robot Motion Planning in State Lattices,” J. F. Robot., 2009.
[11] L.Fu, A.Yazici, and Ü.Ozgüner, “Route planning for OSU-ACT autonomous vehicle in DARPA Urban Challenge,” IEEE Intell. Veh. Symp. Proc., pp. 781–786, 2008.
[12] J. W.Choi, R.Curry, and G.Elkaim, “Path planning based on bézier curve for autonomous ground vehicles,” Proceedings - Advances in Electrical and Electronics Engineering - IAENG Special Edition of the World Congress on Engineering and Computer Science 2008, WCECS 2008. pp. 158–166, 2008.
[13] J. H.Wei and J. S.Liu, “Collision-free composite η3-splines generation for nonholonomic mobile robots by parallel variable-length genetic algorithm,” 2008 Int. Conf. Comput. Intell. Model. Control Autom. CIMCA 2008, pp. 545–550, 2008.
[14] F.Lamiraux and J. P.Laumond, “Smooth motion planning for car-like vehicles,” IEEE Trans. Robot. Autom., vol. 17, no. 4, pp. 498–502, 2001.
[15] Reza N. Jazar, Vehicle Dynamics Theory and Application. Springer, New York, USA, 2008.
[16] R.Rajamani, Vehicle Dynamic and Control. Springer, New York, USA, 2008.
[17] M. Rony Hidayatullah, “Investigation on String Stability of Cooperative Adaptive Cruise Control using L1 Adaptive Control under Communication Uncertainties,” National Cheng Kung University, Tainan, Taiwan, 2019.
[18] “Adaptive Cruise Control with Sensor Fusion - MATLAB & Simulink.” [Online]. Available: https://www.mathworks.com/help/driving/examples/adaptive-cruise-control-with-sensor-fusion.html.
[19] P.Shakouri, A.Ordys, M.Askari, and D. S.Laila, “Longitudinal vehicle dynamics using Simulink/Matlab,” IET Semin. Dig., vol. 2010, no. 4, pp. 955–960, 2010.
[20] D.González, J.Pérez, V.Milanés, and F.Nashashibi, “A Review of Motion Planning Techniques for Automated Vehicles,” IEEE Trans. Intell. Transp. Syst., vol. 17, no. 4, pp. 1135–1145, 2016.
[21] M.Elbanhawi and M.Simic, “Sampling-based robot motion planning: A review,” IEEE Access, vol. 2, pp. 56–77, 2014.
[22] Y.Kanayama and B. I.Hartman, “Smooth local planning for autonomous vehicles,” Int. J. Rob. Res., vol. 16, no. 3, pp. 263–284, 1997.
[23] J. A. R.Silva and V.Grassi, “Clothoid-based global path planning for autonomous vehicles in urban scenarios,” Proc. - IEEE Int. Conf. Robot. Autom., pp. 4312–4318, 2018.
[24] G.Kavuran, “Path planning for nonholonomic mobile robot based on Bézier curve,” IDAP 2017 - Int. Artif. Intell. Data Process. Symp., no. 1, pp. 1–5, 2017.
[25] N.Wan, D.Xu, and H.Ye, “Improved cubic B-spline curve method for path optimization of manipulator obstacle avoidance,” Proc. 2018 Chinese Autom. Congr. CAC 2018, pp. 1471–1476, 2019.
[26] D.Dolgov, S.Thrun, M.Montemerlo, and J.Diebel, “Path planning for autonomous vehicles in unknown semi-structured environments,” Int. J. Rob. Res., vol. 29, no. 5, pp. 485–501, 2010.
[27] C. L.Chang, S. L.Lo, P. T.Chiueh, and S. M.Huang, “Making Bertha Drive - An Autonomous Journey on Historic Route,” vol. 6, no. 2, pp. 8–20, 2014.
[28] S. M.LaValle and J. J.Kuffner, “Randomized kinodynamic planning,” Int. J. Rob. Res., vol. 20, no. 5, pp. 378–400, 2001.
[29] S.Luo, S.Liu, B.Zhang, and C.Zhong, “Path planning algorithm based on Gb informed RRT∗ with heuristic bias,” Chinese Control Conf. CCC, pp. 6891–6896, 2017.
[30] A.Atramentov and S. M.LaValle, “Efficient nearest neighbor searching for motion planning,” Proc. - IEEE Int. Conf. Robot. Autom., vol. 1, no. May, pp. 632–637, 2002.
[31] S. R.Martin, S. E.Wright, and J. W.Sheppard, “Offline and online evolutionary bi-directional RRT algorithms for efficient re-planning in dynamic environments,” Proc. 3rd IEEE Int. Conf. Autom. Sci. Eng. IEEE CASE 2007, pp. 1131–1136, 2007.
[32] J. J.Kuffner and S. M.LaValle, “RRT-connect: an efficient approach to single-query path planning,” Proc. - IEEE Int. Conf. Robot. Autom., vol. 2, no. April, pp. 995–1001, 2000.
[33] M.Strandberg, “Augmenting RRT-Planners with local trees,” Proc. - IEEE Int. Conf. Robot. Autom., vol. 2004, no. 4, pp. 3258–3262, 2004.
[34] E.Shan, B.Dai, J.Song, and Z.Sun, “An dynamic RRT path planning algorithm based on B-spline,” Isc. 2009 - 2009 Int. Symp. Comput. Intell. Des., vol. 2, pp. 25–29, 2009.
[35] Y.Kuwata, J.Teo, G.Fiore, S.Karaman, E.Frazzoli, and J. P.How, “Real-time motion planning with applications to autonomous urban driving,” IEEE Trans. Control Syst. Technol., vol. 17, no. 5, pp. 1105–1118, 2009.
[36] S.Karaman and E.Frazzoli, “Incremental Sampling-based Algorithms for Optimal Motion Planning,” Proc. Robot. Sci., pp. 1–8, 2010.
[37] D.Connell and H. M.La, “Dynamic path planning and replanning for mobile robots using RRT,” 2017 IEEE Int. Conf. Syst. Man, Cybern. SMC 2017, vol. 2017-Janua, pp. 1429–1434, 2017.
[38] S.Karaman and E.Frazzoli, “Optimal kinodynamic motion planning using incremental sampling-based methods,” Proc. IEEE Conf. Decis. Control, pp. 7681–7687, 2010.
[39] J. A.Reeds and L. A.Shepp, “Optimal paths for a car that goes both forwards and backwards,” Pacific J. Math., vol. 145, no. 2, pp. 367–393, 1990.
[40] L. E.Dubins, “On Curves of Minimal Length with a Constraint on Average Curvature, and with Prescribed Initial and Terminal Positions and Tangents,” Am. J. Math., vol. 79, no. 3, p. 497, 1957.
[41] S. M.LaValle, Planning Algorithms, no. 48. 2006.
[42] Héctor J. Sussmann and Guoqing Tang, “Shortest Paths for The Reeds-Shepp Car: A Worked Out Example of The Use of Geometric Techniques in Nonlinear Optimal Control,” Tech. Rep. SYNCON 91-10, Dept. Math. Rutgers Univ. Piscataway, NJ, 1991.
[43] C.K. Shene, “Continuity Issues.” [Online]. Available: https://pages.mtu.edu/~shene/COURSES/cs3621/NOTES/curves/continuity.html.
[44] M.van dePanne, “Parametric Curves,” Fall 1996 Online Notes, 1996.
[45] A.Ravankar, A. A.Ravankar, Y.Kobayashi, Y.Hoshino, and C. C.Peng, “Path smoothing techniques in robot navigation: State-of-the-art, current and future challenges,” Sensors (Switzerland), vol. 18, no. 9, pp. 1–30, 2018.
[46] Edward Waring, “Problems concerning interpolations,” Philos. Trans. R. Soc. London, vol. 69, pp. 59–67, Dec.1779.
[47] E. W.Weisstein, “Spline -- from Wolfram MathWorld.” [Online]. Available: https://mathworld.wolfram.com/Spline.html.
[48] B.Song, G.Tian, and F.Zhou, “A comparison study on path smoothing algorithms for laser robot navigated mobile robot path planning in intelligent space,” J. Inf. Comput. Sci., vol. 7, no. 14, pp. 2943–2950, 2010.
[49] “Cubic Spline Interpolation - Wikiversity.” [Online]. Available: https://en.wikiversity.org/wiki/Cubic_Spline_Interpolation.
[50] J.Ziegler and C.Stiller, “Fast collision checking for intelligent vehicle motion planning,” IEEE Intell. Veh. Symp. Proc., pp. 518–522, 2010.
[51] “Costmap representing planning space around vehicle - MATLAB.” [Online]. Available: https://www.mathworks.com/help/driving/ref/vehiclecostmap.html#mw_dbee3f4e-6ba5-4bc6-a8d3-61ca3ed863f6.
[52] G. M.Hoffmann, C. J.Tomlin, M.Montemerlo, and S.Thrun, “Autonomous automobile trajectory tracking for off-road driving: Controller design, experimental validation and racing,” Proc. Am. Control Conf., pp. 2296–2301, 2007.
[53] 中華民國内政部, “市區道路及附屬工程設計規範,” 2013.