Optimal Path in a Hostile Environment by using Delaunay Triangulation
Article Sidebar
Main Article Content
Abstract
This study aims to propose and illustrate the process of using the Delaunay triangulation to find an optimal path for aerial operation. The optimal path is defined as the shortest path when avoiding all risks of enemy radar detection and terrain collision. The scope of this study is to demonstrate details of this process step by step as well as its effectiveness and limitation. The demonstration is the applied synthesis 3d terrain. The proposed process begins with randomly locating the vertex of the Delaunay triangulation. Then selected vertexes are elements to generate the Delaunay triangulation. The edges of the Delaunay triangulation are considered as available fly paths for aircraft over the 3D terrain. Secondly, the edges regard a high risk of enemy radar detection and terrain collision to be removed from the available edge paths. Dijkstra’s algorithm is the tool to analyze the remaining edges for the shortest path. The last step is to smoothen the shortest path by using polynomial interpolation of the vertexes from the previous step. The results have shown that the idea of using the Delaunay triangulation for the optimization path is effective and robust. It is possible for path planning for aerial operations in various cases. This study can also be extended to the Navy, Army and civilian path planning problems.
Article Details
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
The author has the sole responsibility for the material published in RTNA Journal of Science and Technology, which the editorial board may not agree on that material.
RTNA Journal of Science and Technology owns the copyright of the text, the illustration, or other material published in the journal. No parts or the whole of the material published may be disseminated or used in any form without first obtaining written permission from the academy.
References
Murphy R, Uryasev S, Zabarankin M. Trajectory optimization in a threat environment. Research Report 9 [Internet]. Florida: University of Florida, Department of Industrial and Systems Engineering; 2003 Jan. Available from https://www.researchgate.net/publication/ 251451092_Trajectory_optimization_in_a_threat_environment_Research_report
Turnbull O, Lawry J, Lowenberg M, Richards A. A cloned linguistic decision tree controller for real-time path planning in hostile environments. Fuzzy Sets Syst. 2016 Jun 15;(293):1-29.
Banfi J, Campbell M. High-Level Path Planning in Hostile Dynamic Environments. In Proceedings of the 18th International Conference on Autonomous Agents and Multi-Agent Systems [Internet]; 2019 Jan; Montreal, Canada. Montreal; Conference: AAMAS; 2019 [cited 2023 Jan 12]; p.1799-1801. Available from: https://www.researchgate.net/ publication/335125982_High-Level_Path_Planning_in_Hostile_Dynamic_Environments
Yang L, Qi J, Xiao J, Yong X. A literature review of UAV 3D path planning. In Proceeding of the 11th World Congress on Intelligent Control and Automation [Internet]; 2014 Jun 1; Shenyang, IEEE; 2014 [cited 2023 Feb 1]; p. 2376-81. Available from: https://ieeexplore.ieee.org/document/7053093 doi: 10.1109/WCICA.2014.7053093.
Bruce J, Veloso M. Real-time randomized path planning for robot navigation. In IEEE/RSJ international conference on intelligent robots and systems [Internet]; 2002; Lausanne, Switzerland. [place unknown]; IEEE; 2002 [cited 2023 Feb 12]; p. 2383-88. Available from: https://ieeexplore.ieee.org/document/1041624 doi: 10.1109/IRDS.2002.1041624.
Aurenhammer F. Voronoi diagrams: A survey of a fundamental geometric data structure. ACM Comput Surv. 1991 Seb 1;23(3): 345-405.
Garrido S, Moreno LE, Blanco D. Voronoi diagram and Fast Marching applied to path planning. In Proceedings of the 2006 IEEE International Conference on Robotics and Automation [Internet]; 2006 May 15-19; Orlando, Florida, USA. [place unknown]: DBLP; 2006 [cited 2023 Mar 3]; p.3049-54. Available from: https://www.researchgate.net/ publication/221072916_Voronoi_Diagram_and_Fast_Marching_applied_to_Path_Planning doi:10.1109/ROBOT.2006.1642165
Garrido S, Moreno L. Mobile robot path planning using voronoi diagram and fast marching. In: Luo Z, editor. Robotics, Automation, and Control in Industrial and Service Settings. [place unknown]: IGI Global; 2015. p. 92-108.
Al-Dahhan M, Schmidt, K. Path Planning Based on Voronoi Diagram and PRM for Omnidirectional Mobile Robots. In: DTSS2019 international conference [Internet]; 2019 Oct; Ankara, Turkey.
Özcan M, Yaman U. A continuous path planning approach on Voronoi diagrams for robotics and manufacturing applications. Procedia Manuf. 2019;38:1-8.
Delaunay B. Sur la sphère vide. Bulletin de l'Académie des Sciences de l'URSS, Bull Acad Serbe Sci Cl Sci Math Nat Sci Nat. 1934;6:793–800.
Skolnik M. Radar Handbook. 3rd ed. Boston: McGraw-Hill, 1990.
Mahafza B. Radar Systems Analysis and Design Using MATLAB. 3rd ed. New York: CRC Press, 2013.
Skolnik M. Introduction to Radar Systems. 3rd ed. New York: McGraw-Hill; 2001.
Mahafza BR, Elsherbeni A. MATLAB Simulations for Radar Systems Design. New York: Chapman & Hall/CRC; 2003.
Willis NJ. Bistatic Radar. Raleigh, NC: SciTech; 2005.
Dijkstra EW. A note on two problems in connexion with graphs. Numer Math. 1959;1: 269-71.
Cormen TH, Leiserson CE, Rivest RL, Stein C. Introduction to Algorithms. 2nd ed. New York: McGraw-Hill; 2001.
Broumi S, Bakal A, Talea M, Smarandache F, Vladareanu L. Applying Dijkstra algorithm for solving neutrosophic shortest path problem. In: 2016 International Conference on Advanced Mechatronic Systems (ICAMechS) [Internet]; 2016 Nov 30 – 2016 Dec 3; Melbourne, VIC, Australia; 2016 International Conference on Advanced Mechatronic Systems (ICAMechS); 2017 [cited 2023 Mar 20]; p.412-6. Available from: IEEE doi: 10.1109/ICAMechS.2016.7813483
Qing G, Zheng Z, Yue X. In: Path-planning of automated guided vehicle based on improved Dijkstra algorithm [Internet]; 2017 May 28-30; Chongqing, China; 2017 29th Chinese control and decision conference (CCDC); 2017 [cited 2023 Apr 12]; p.7138-43. Available from IEEE doi: 10.1109/CCDC.2017.7978471.
Schatzman M. Numerical Analysis: A Mathematical Introduction. Oxford: Clarendon; 2002.
Dai R, Cochran JE. Path planning and state estimation for unmanned aerial vehicles in hostile environments. J Guid Control Dyn. 2010 Apr;33:595-601.
Artuñedo A, Godoy J, Villagra J. A comparison of local path-planning interpolation methods for autonomous driving in urban environments. Industriales research meeting 17.