在機器人和自動化領域中，路徑規劃和追跡是常見的重要議題。因為它關係著如何讓機器人可以安全、快速地完成高精度及高準確度的工作任務，同時也能避開障礙物來防止機器人的損壞。在本論文中，我們將研究各種路徑規劃方法，這些方法可以有效地找到移動型機器人從起始位置移動到目標位置而不會與障礙物發生碰撞的安全路徑。因此，我們所提出的路徑的必須針對路徑的安全性和路徑長度兩個不同目標達到最佳解。
路徑規劃問題現在是自主機器人中探索最多的課題之一。因此，在受限環境中為移動機器人建立安全路徑是所有此類移動機器人成功完成任務的關鍵先決條件。本論文提出一種新的方式來獲得有效的結果，其中包含著兩種演算法：路徑規劃演算法涉及使用諸如距離、時間和能量消耗等性能標準在起始位置和目標位置之間建立安全無碰撞路徑。再透過三角分解演算法再一步地優化路徑，可以快速又高效找到最適合機器人的路徑。且根據環境是否已知，亦可分為兩種類型的路徑規劃演算法：局部路徑規劃和全局路徑規劃。
本論文基於RRT*演算法進行改良，RRT*是傳統RRT方法最佳的改良型演算法之一，本論文更進一步提出了一種新的基於三角分解法的快速探索隨機樹算法（TD-RRT*），使路徑更短，更精確地優化，同時也增強了移動機器人在短時間內尋找路徑的能力，進而降低成本花費，該技術基於增量採樣，覆蓋整個區域并快速運行。此外，由於這種方法計算效率高，因此可以應用於多維環境。本論文也提出了將TD-RRT*進行動態重新規劃的方式，當未知的隨機移動或靜態障礙阻礙路徑時，機器人將會隨著修改其路徑。並通過各種實驗結果顯示，該方法比基本RRT*更快的有效性，並且可以獲得滿足移動機器人非完整約束的最短距離的平滑路徑。

Path planning and trajectory planning are pivotal issues in the field of Robotics and more generally in the field of Automation. Thus, it plays a significant role in robotics for safer and faster working times with accuracy and precision, but at the same time harmless for the robot in terms of avoiding the obstacle. In this thesis, we will look at various methods of route planning that are efficient in finding a safe path for the mobile robot to move from a starting location to a destination position without colliding with obstacles. This suggested thesis addresses two distinct objectives: path safety and path length, and the recommended path must be optimum.
The path planning problem is now one of the most explored subjects in autonomous robots. As a result, establishing a safe path for a mobile robot in a confined environment is a critical prerequisite for the success of any such mobile robot project.We try to formulate the two algorithms with a new method to attain efficient results using triangle decomposition to find a best suited path for the robot which is cost effective and efficient too. Path planning involves using performance criterion such as distance, time, and energy consumption to establish a collision-free path between the ‘start’ and ‘destination’ positions. Depending on whether or not the environment is known, there are two types of path planning algorithms: local and global path planning.
In this thesis a new version of algorithm named Triangular Decomposition based Rapidly Exploring Random Trees (TD-RRT*) is proposed to make the path shorter and to be precise optimal and it also enhances the capability of mobile robots to find paths in short span of time and make the path shorter to reduce the cost also. RRT*, is an asymptotically optimum variation of the Traditional (RRT) method which is incorporated in this thesis. The technique is based on incremental sampling, which covers the whole area and operates quickly. Furthermore, because this approach is computationally efficient, it may be applied in multidimensional environment .A method of dynamic re-planning using TD-RRT* is presented. The robot will rectify or modify its path when unknown random moving or static snag obstructs the path. Various experimental results show the effectiveness of the proposed method which is faster than the basic RRT*, and the smooth path with the shortest distance can be obtained which satisfies the non-holonomic constraint of mobile robots.

[1] Xingguo Song, Xu Fan, Zhongqing Cao, Hong Li Gao; “A TC-RRT-based path planning algorithm for the nonholonomic mobile robots” 2017 36th Chinese Control Conference (CCC) July 2017.
[2] Sertac Karaman, Matthew R. Walter, Alejandro Perez, Emilio Frazzoli, Seth Teller; “Anytime Motion Planning using the RRT”; Proc. IEEE Int’l Conference on Robotics and Automation (ICRA), May 2011.
[3] Devin Conell and Hung Manh La; “Extended rapidly exploring random tree-based dynamic path-planning and replanning for mobile robots”; International Journal of Advanced Robotic Systems, May-June 2018: 1-15
[4] Wei Wang; Hongli Gao; Qize Yi; Kaiyuan Zheng; Tengda Gu; “An Improved RRT Path Planning Algorithm for Service Robot”; IEEE 4th Information Technology, Networking, Electronic and Automation Control Conference (ITNEC), 2020
[5] Martin Törngren Sagar Behere. A functional architecture for autonomous driving.
[6] Bhushan Mahajan, Punam Marbate “Literature Review on Path planning in Dynamic Environment”; IJCSN International Journal of Computer Science and Network, Vol 2, Issue 1, 2013.
[7] Devin Connell, Hung Manh La “Dynamic Path Planning and Replanning for Mobile Robots using RRT*”; [cs.RO] 15 Apr 2017.
[8] Iram Noreen, Amna Khan and Zulfiqar Habib, “Optimal Path Planning using RRT* based Approaches: A Survey and Future Directions” International Journal of Advanced Computer Science and Applications(ijacsa), 7(11), 2016.
[9] S. Karaman, and E. Frazzoli, "Sampling-based algorithms for optimal motion planning", Int J Rob Res, vol. 30, pp. 846-894, 2011.
[10] Arslan, and P. Tsiotras, "Use of relaxation methods in sampling-based algorithms for optimal path planning", presented at the IEEE International Conference on Robotics and Automation (ICRA), Karlsruhe, Germany, 2013.
[11] Alejo, J. A. Cobano, G. Heredia, J. R. Martínez-De Dios, and A. Ollero, "Efficient trajectory planning for wsn data collection with multiple UAVs", in Cooperative robots and sensor networks. vol. 604, ed: Springer International Publishing, 2015, pp. 53-75.
[12] C.Moon, and W. Chung, "Kinodynamic planner dual-tree RRT (dt-RRT) for two-wheeled mobile robots using the rapidly exploring random tree", IEEE T IND ELECTRON, vol. 62, February 2015.
[13] J. Nasir et al., "RRT*-smart: A rapid convergence implementation of RRT*", International Journal of Advanced Robotic Systems, vol. 10, pp. 1-12, 2013.
[14] J. D. Gammell, S. S. Srinivasa, and T. D. Barfoot, "Informed RRT*: Optimal sampling-based path planning focused via direct sampling of an admissible ellipsoidal heuristic", in IEEE RSJ International Conference on Intelligent Robots and Systems (IROS), Chicago, 2014, pp. 2997- 3004.
[15] D. J. Webb, and J. V. D. Berg, "Kinodynamic RRT*: Optimal motion planning for systems with linear differential constraints", arXiv:1205.5088v1, 2012.
[16] D. J. Webb, and J. V. D. Berg, "Kinodynamic RRT*: Asymptotically optimal motion planning for robots with linear dynamics", presented at the IEEE International Conference on Robotics and Automation (ICRA), Karlsruhe, Germany, 2013
[17] M. S. S. Elshall, S. F.Rezeka, I. F. Zidane and A. Onsy, "Design and Development of Path Planning and Obstacle Avoidance System for Driverless Pod Using Artificial Neural Network," 2020 30th International Conference on Computer Theory and Applications (ICCTA), 2020, pp. 96-100
[18] Yaohang Li, Tao Dong, Marwan Bikdash, Yong Duan Song,” Path Planning for Unmanned Vehicles using Ant Colony Optimization on a Dynamic Voronoi Diagram”, in International Conference on Artificial Intelligence, ICAI , Las Vegas, Nevada, USA 2005.
[19] Priyadarshi Bhattacharya and Marina L. Gavrilova,” Roadmap-Based Path Planning Using the Voronoi Diagram for a Clearance-Based Shortest Path”, IEEE Robotics & Automation Magazine ,JUNE 2008.
[20] Aditya Mahadevan and Nancy M. Amato,” A SamplingBased Approach to Probabilistic Pursuit Evasion”, IEEE International Conference on Robotics and Automation River Centre, Saint Paul, Minnesota, USA,2012
[21] Amit Kumar Pandey,Rachid Alami,” A Framework towards a Socially Aware Mobile Robot Motion in Human-Centered Dynamic Environment”, The 2010 IEEE/RSJ International Conference on Intelligent Robots and Systems October 18-22, 2010, Taipei, Taiwan.
[22] Libo Yang and S. M. LaValle, "The sampling-based neighborhood graph: an approach to computing and executing feedback motion strategies," in IEEE Transactions on Robotics and Automation, vol. 20, no. 3, pp. 419-432, June 2004.
[23] S. Karaman and E. Frazzoli, "Optimal kinodynamic motion planning using incremental sampling-based methods," in Proc. IEEE Conf. on Decision and Control (CDC), Dec. 2010.
[24] Y. K. Hwang, "Gross motion planning-a survey", ACM COMPUT SURV, vol. 24, pp. 219-291, 1992.
[25] W. Loeve, "Finding time-optimal trajectories for the resonating arm using the RRT* algorithm", Master of Science, Faculty Mechanical, Maritime and Materials Engineering, Delft University of Technology, Delft, 2012.
[26] Roudabe Seif, Mohammadreza Asghari Oskoei; “Mobile Robot Path Planning by RRT* in Dynamic Environments”; International Journal of Intelligent Systems and Applications (IJISA) 5 vol.7,2015
[27] Islam F., Nasir J., Malik U., Ayaz Y., Hasan O. Rrt*-smart: Rapid Convergence Implementation of rrt* towards Optimal Solution; Proceedings of the IEEE International Conference on Mechatronics and Automation; Chengdu, China. 5–8 August 2012; pp. 1651–1656.
[28] Jeong, I.-B.; Lee, S.-J.; Kim, J.-H. Quick-RRT*: Triangular inequality based implementation of RRT* with improved initial solution and convergence rate. Expert Syst. Appl. 2019, 123, 82–90.
[29] Kang, J.-G.; Lim, D.-W.; Choi, Y.-S.; Jang, W.-J.; Jung, J.-W. Improved RRT-Connect Algorithm Based on Triangular Inequality for Robot Path Planning. Sensors 2021, 21, 333. https://doi.org/ 10.3390/s21020333.
[30] Abhijeet Ravankar, Ankit A. Ravankar, Yukinori Kobayashi,Yohei Hoshino and Chao-Chung Peng; “Path Smoothing Techniques in Robot Navigation: State-of-the-Art, Current and Future Challenges”; Sensors 2018, 18(9), 3170.
[31] Lin Xu, Maoyong Cao, Baoye Song ; “A new approach to optimal smooth path planning of mobile robots with continuous-curvature constraint”; Systems Science & Control Engineering An Open Access Journal 9(1):138-149, January 2021.
[32] Delling D., Sanders P., Schultes D., Wagner D. Engineering Route Planning Algorithms. In: Lerner J., Wagner D., Zweig K., editors. Algorithmics of Large and Complex Networks. Volume 5515. Springer; Berlin/Heidelberg, Germany: 2009. pp. 117–139. (Lecture Notes in Computer Science).
[33] LaValle S.M. Planning Algorithms. Cambridge University Press; Cambridge, UK: 2006. [(accessed on 11 February 2016)]. Available online: http://planning.cs.uiuc.edu/
[34] Latombe J.C. Robot Motion Planning. Kluwer Academic Publishers; Norwell, MA, USA: 1991.
[35] Dijkstra E.W. A Note on Two Problems in Connexion with Graphs. Numer. Math. 1959; 1:269–271. doi: 10.1007/BF01386390.
[36] Shu-Xi W. The Improved Dijkstra’s Shortest Path Algorithm and Its Application. 2012 International Workshop on Information and Electronics Engineering. Procedia Eng. 2012;29:1186–1190.
[37] Fujita Y., Nakamura Y., Shiller Z. Dual Dijkstra Search for paths with different topologies; Proceedings of the 2003 IEEE International Conference on Robotics and Automation (ICRA ’03); Taipei, Taiwan. 14–19 September 2003; pp. 3359–3364.
[38] Shene C.K. Continuity Issues. [(accessed on 1 June 2018)];2018 Available online: http://pages.mtu.edu/~shene/COURSES/cs3621/NOTES/curves/continuity.html
[39] Guibas L. Geometric Modeling. [(accessed on 1 June 2018)];2018 Availableonline: http://graphics.stanford.edu/courses/cs348a-17- winter/ReaderNotes/handout27.pdf
[40] Farin G. Curves and Surfaces for CAGD: A Practical Guide. 5th ed. Morgan Kaufmann Publishers Inc.; San Francisco, CA, USA: 2002.
[41] De Boor C. A Practical Guide to Splines. Springer Verlag; New York, NY, USA: 1978.
[42] Khatib, O.: Real-time obstacle avoidance for manipulators and mobile robots. Int. J. Robot. Res. 5(1), 90–98 (1986). doi:10.1177/027836498600500106
[43] Arkin, R.C.: Motor Schema Based Mobile Robot Navigation. Int. J. Robot. Res. 8(4),92–112 (1989). doi:10.1177/027836498900800406
[44] Koren, Y., Borenstein, J.: Potential field methods and their inherent limitations for mobile robot navigation. In: Robotics and Automation, 1991. Proceedings., 1991 IEEE International Conference on, vol. 1392, pp. 1398–1404 (1991)
[45] Elbanhawi, M., Simic, M.: Sampling-based robot motion planning: a review. IEEE Access 2, 56–77 (2014).
[46] Magid, E., Keren, D., Rivlin, E., Yavneh, I.: Spline-Based Robot Navigation. In: Intelligent Robots and Systems, 2006 IEEE/RSJ International Conference on, pp. 2296–2301 (2006)
[47] Roth, S., Batavia, P.: Evaluating Path Tracker Performance for Outdoor Mobile Robots. Paper presented at the Automation Technology for Off-Road Equipment, Chicago, Illinois, USA, 26–27/07
[48] Lau, B., Sprunk, C., Burgard, W.: Kinodynamic motion planning for mobile robots using splines. In: Intelligent Robots and Systems, 2009. IROS 2009. IEEE/RSJ International Conference on, pp. 2427–2433 (2009)
[49] Gulati, S., Kuipers, B.: High performance control for graceful motion of an intelligent wheelchair. In: Robotics and Automation, 2008. ICRA 2008. IEEE International Conference on, pp. 3932–3938 (2008)
[50] Girbes, V., Armesto, L., Tornero, J.: “Path following hybrid control for vehicle stability applied to industrial forklifts.”; Robot. Auton. Syst.(2014).
[51] Waring E. Problems concerning Interpolations. Philos. Trans. R. Soc. 1779; 69:59–67. doi: 10.1098/rstl.1779.0008.
[52] Waring E. Problems Concerning Interpolations. The Royal Society Publishing; London, UK: 2015. [(accessed on 15 January 2016)]. Available online: http://rstl.royalsocietypublishing.org/content/69/59.full.pdf+html.
[53] Campana M., Lamiraux F., Laumond J.P. [(accessed on 19 September 2018)];A Simple Path Optimization Method for Motion Planning. Working Paper or Preprint. HAL Archives; Rapport LAAS n° 15108. 2015. <hal-01137844v2>. Available online: https://hal.archives-ouvertes.fr/hal-01137844/file/paper_icra2016_hal.pdf
[54] Park C., Pan J., Manocha D. ITOMP: Incremental trajectory optimization for real-time replanning in dynamic environments; Proceedings of the 22nd International Conference on Automated Planning and Scheduling (ICAPS 2012); Atibaia, Sao Paulo, Brazil. 25–29 June 2012; pp. 207–215.
[55] Garber M., Lin M.C. Constraint-Based Motion Planning Using Voronoi Diagrams. In: Boissonnat J.D., Burdick J., Goldberg K., Hutchinson S., editors. Algorithmic Foundations of Robotics V. Springer; Berlin/Heidelberg, Germany: 2004. pp. 541–558.
[56] Richardson A., Olson E. Iterative path optimization for practical robot planning; Proceedings of the 2011 IEEE/RSJ International Conference on Intelligent Robots and Systems; San Francisco, CA, USA. 25–30 September 2011; pp. 3881–3886.