安全路徑的規劃為自走車避障的核心。本研究參考快速搜索隨機樹算法，提出改良方法，以在靜態障礙物環境中，規劃出由起始位置到達目的地且避開障礙物的安全路徑。此方法應用修剪程序和結合二階貝茲曲線的平滑化程序以提高路徑的效率和平滑度，並提出最佳化程序改善算法因隨機性而無法找到最佳解的限制。實驗使用純追蹤轉向控制器及比例積分速度控制器進行追縱控制，以驗證改良算法於車輛路徑規劃與避障的效果。結果顯示車輛軌跡與目標路徑的最小平均差異為車輛寬度的4.7%，且車輛能夠成功避障並追蹤此路徑安全到達目的地。實驗亦測試了被視為避障特殊情況的車道變換。在完成變道後，車道保持系統的平均差異為一半車道寬度的-8.3%，說明車道變換和車道保持相結合是有效的。

A safe path planning for obstacle avoidance is necessary in autonomous vehicles. Based on the Rapidly-exploring Random Trees (RRT) algorithm, this work develops an improved algorithm to achieve a safe path from start to destination in static obstacle environment. The improved RRT algorithm improves the path planning efficiency with optimization by integrating the pruning process, the smoothing process with quadratic Bézier curve, and the optimization process for path planning efficiency. This work also proposes a geometric collision detection check to improve the calculation efficiency. In experimental verification, both pure-pursuit steering controller and proportional-integral speed controller are applied to keep the vehicle tracking the planned path determined by the improved RRT algorithm. The results show that the average discrepancy of tracking
control is 4.7% and the vehicle can successfully track the planned path and reach the destination safely. Finally, the lane change regarded as a special case of obstacle avoidance
is tested. After lane change, the average discrepancy of the lane keeping is -8.3%. The result shows that the combined lane change and lane keeping is effective.

[1] “Global Status Report on Road Safety 2018,” World Health Organization: Geneva, 2018.
[2] A. Rahim, X. Kong, F. Xia, Z. Ning, N. Ullah, J. Wanga and S. K. Das, “Vehicular Social Networks: A Survey,” ScienceDirect Pervasive and Mobile Computing, Vol. 14,
pp. 96-113, 2018.
[3] “Automated Driving － Levels of Driving Automation are Defined in New SAE International Standard J3016,” SAE International, 2014.
[4] D. González, J. Pérez, V. Milanés and F. Nashashibi, “A Review of Motion Planning Techniques for Automated Vehicles,” IEEE Transactions on Intelligent Transportation
Systems, Vol. 17, no. 4, pp. 1135-1145, 2016.
[5] S. M. Lavalle, “Rapidly-Exploring Random Trees: A New Tool for Path Planning,” Algorithmic & Computational Robotics New Directions, pp. 293-308, 1998.
[6] B. Sakcak, L. Bascetta, G. Ferretti and M. Prandini, “Sampling-Based Optimal Kinodynamic Planning with Motion Primitives,” Autonomous Robot, Vol. 43, pp. 1715-1732, 2019.
[7] R. Pepy, A. Lambert and H. Mounier, “Path Planning Using a Dynamic Vehicle Model,” 2006 2nd International Conference on Information & Communication Technologies, pp. 781-786, 2006.
[8] Y. Kuwata, G. A. Fiore, J. Teo, E. Frazzoli and J. P. How, “Motion Planning for Urban Driving Using RRT,” 2008 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 1681-1686, 2008.
[9] M. Mischinger, M. Rudigier, P. Wimmer and A. Kerschbaumer, “Towards Comfort-Optimal Trajectory Planning and Control,” Vehicle System Dynamics, Vol. 57, pp.
1108-1125, 2019.
[10] J. L. Blanco, M. Bellone and A. Gimenez-Fernandez, “TP-Space RRT-Kinematic Path Planning of Non-Holonomic Any-Shape Vehicles,” International Journal of Advanced Robotic Systems, Vol. 12, pp. 1-9, 2015.
[11] S. M. LaValle and J. J. Kuffner, “Rapidly-Exploring Random Trees: Progress and Prospects,” Algorithmic and Computational Robotics: New Directions, pp. 293-308,
2001.
[12] S. M. LaValle and J. J. Kuffner, “Randomized Kinodynamic Planning,” The International Journal of Robotics Research, Vol. 20, pp. 378-400, 2001.
[13] H. Zhang, Y. Wang, J. Zheng and J. Yu, “Path Planning of Industrial Robot Based on Improved RRT Algorithm in Complex Environments,” IEEE Access, Vol. 6, pp. 53296- 53306, 2018.
[14] S. Karaman and E. Frazzoli, “Incremental Sampling-Based Algorithms for Optimal Motion Planning,” Robotics: Science and Systems VI, pp. 267-274, 2010.
[15] K. R. Jayasree, P. R. Jayasree and A. Vivek, “Smoothed RRT Techniques for Trajectory Planning,” 2017 International Conference on Technological Advancements in Power and Energy, pp. 1-8, 2017.
[16] K. Wei and B. Ren, “A Method on Dynamic Path Planning for Robotic Manipulator Autonomous Obstacle Avoidance Based on an Improved RRT Algorithm,” Sensors 2018, pp. 571-578, 2018.
[17] Y. H. Liu, “A Robust Lane Detection Algorithm Based on Binary Line Segment Filter for Lane Keeping in Autonomous Vehicles,” Master Thesis, National Cheng Kung University, 2019.
[18] M. Elbanhawi and M. Simic, “Sampling-Based Robot Motion Planning: A Review,” IEEE Access, Vol. 2, pp. 56-77, 2014.
[19] E. G. Tsardoulias, A. Iliakopoulou, A. Kargakos and L. Petrou, “A Review of Global Path Planning Methods for Occupancy Grid Maps Regardless of Obstacle Density,” Journal of Intelligent and Robotic Systems, pp. 829-858, 2016.
[20] S. Aggarwal and N. Kumar, “Path Planning Techniques for Unmanned Aerial Vehicles: A Review, Solutions, and Challenges,” Computer Communications, Vol. 149, pp. 270-
299, 2020.
[21] N. M. Amato and Y. Wu, “A Randomized Roadmap Method for Path and Manipulation Planning,” Proceedings of IEEE International Conference on Robotics and Automation, Vol. 1, pp. 113-120, 1996.
[22] L. E. Kavraki, P. Svestka, J. Latombe and M. H. Overmars, “Probabilistic Roadmaps for Path Planning in High-Dimensional Configuration Spaces,” IEEE Transactions on Robotics and Automation, Vol. 12, no. 4, pp. 566-580, 1996.
[23] S. Karaman and E. Frazzoli, “Sampling-Based Optimal Motion Planning for Non-Holonomic Dynamical Systems,” 2013 IEEE International Conference on Robotics and Automation, pp. 5041-5047, 2013.
[24] 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 2018, Vol. 18, 3170, 2018.
[25] T. Suzuki, R. Usami and T. Maekawa, “Automatic Two-Lane Path Generation for Autonomous Vehicles Using Quartic B-Spline Curves,” IEEE Transactions on Intelligent Vehicles, Vol. 3, no. 4, pp. 547-558, 2018.
[26] L. Chen, D. Qin, X. Xu, Y. Cai and J. Xie, “A Path and Velocity Planning Method for Lane Changing Collision Avoidance of Intelligent Vehicle Based on Cubic 3-D Bezier
Curve,” Advances in Engineering Software, Vol. 132, pp. 65-73, 2019.
[27] J. Chen, P. Zhao, T. Mei and H. Liang, “Lane Change Path Planning Based on Piecewise Bezier Curve for Autonomous Vehicle,” Proceedings of 2013 IEEE International Conference on Vehicular Electronics and Safety, pp. 17-22, 2013.
[28] H. Li, Y. Luo and J. Wu, “Collision-Free Path Planning for Intelligent Vehicles Based on Bézier Curve,” IEEE Access, Vol. 7, pp. 123334-123340, 2019.
[29] J. Choi, R. Curry and G. Elkaim, “Path Planning Based on Bézier Curve for Autonomous Ground Vehicles,” Advances in Electrical and Electronics Engineering-IAENG Special Edition of the World Congress on Engineering and Computer Science
2008, pp. 158-166, 2008.
[30] R. Wallace, A. Stentz, C. E. Thorpe, H. Maravec, W. Whittaker and T. Kanade, “First Results in Robot Road Following,” Proceedings of the International Joint Conference on Artificial Intelligence, pp. 1089-1095, 1985.
[31] Y. Shan, W. Yang and C. Chen, “CF-Pursuit: A Pursuit Method with a Clothoid Fitting and a Fuzzy Controller for Autonomous Vehicles,” International Journal of Advanced
Robotic Systems, Vol. 12, pp. 1-13, 2015.
[32] J. Wit, C. D. Crane and D. Armstrong, “Autonomous Ground Vehicle Path Tracking,” Journal of Robotic Systems, Vol. 21, pp. 439-449, 2004.
[33] Y. Kuwata, S. Karaman, J. Teo, E. Frazzoli, J. How and G. Fiore, “Real-time Motion Planning with Applications to Autonomous Urban Driving,” IEEE Transactions on Control Systems Technology, Vol. 17, pp. 1105-1118, 2009.
[34] C. Y. Kuo, Y. R. Lu and S. M. Yang, “On the Image Sensor Processing for Lane Detection and Control in Vehicle Lane Keeping Systems,” Sensors, Vol. 19, 1665, 2019.