Optimal Path in a Hostile Environment by Using Voronoi Diagram
Article Sidebar
Main Article Content
Abstract
The objective of this study is to investigate the use of Voronoi diagram to find optimal paths for military aircrafts in hostile environment. In the past, choosing the best paths for military forces depended on commanders’ experience and expertise. For modern warfare, battlefields become more sophisticated with bigger forces, combined forces, mobile radars, autonomous systems etc. As a result, making decision and choosing the best possible options are complicated and difficult. It is essential to have an algorithm which is able to aid and predict the best available choice. In this study, area of interest is divided by Voronoi diagram. Then areas which covered by radar systems are calculated and removed from Voronoi diagram. The Dijkstra’s algorithm is used to search throughout the remaining paths for the optimal path. Then polynomial interpolation is used to smoothen the path and make it possible for air mission.
Downloads
Article Details
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
Journal of TCI is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0) licence, unless otherwise stated. Please read our Policies page for more information...
References
Al-Dahhan, M. R. H., & Schmidt, K. W. Path Planning Based on Voronoi Diagram and PRM for Omnidirectinal Mobile Robots. 2019.
Artuñedo, A., Godoy, J., & Villagra, J. A comparison of local path-planning interpolation methods for autonomous driving in urban environments. In Industriales research meeting, p. 147, 2017.
Aurenhammer, F., Voronoi diagrams: A survey of a fundamental geometric data structure, ACM Computing Surveys, 23, 345-405, 1991.
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, 1799-1801, 2019.
Beard, R. W., McLain, T. W., Goodrich, M. and Anderson, E. P., Coordinated target assignment and intercept for unmanned air vehicles, IEEE Transactions on Robotics and Automation, 18, 911–922, 2002.
Bortoff, S. A., Path planning for UAVs, In Proceedings of the American Control Conference, 6, 364 – 368, 2000.
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), 412-416, IEEE, 2016.
Candeloro, M., Lekkas, A. M., & Sørensen, A. J., A Voronoi-diagram-based dynamic path-planning system for underactuated marine vessels, Control Engineering Practice, 61, 41-54. 2017.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., Stein, C., Dijkstra's algorithm, Introduction to Algorithms (Second ed.), MIT Press and McGraw-Hill, 595–601, 2001.
Dai, R., & Cochran Jr, J., Path planning and state estimation for unmanned aerial vehicles in hostile environments, Journal of guidance, control, and dynamics, 33(2), 595-601. 2010.
Dijkstra, E., A note on two problems in conexion with graphs, Numerische Mathematik, 1, 269-271, 1959.
Garrido, S., Moreno, L., and Blanco, D., Voronoi diagram and Fast Marching applied to path planning, In Proceedings of ICRA, 3049-3054, 2006.
Garrido, S., & Moreno, L., Mobile robot path planning using voronoi diagram and fast marching, In Robotics, Automation, and Control in Industrial and Service Settings, 92-108, IGI Global, 2015.
Liang, Y., Juntong, Q., Jizhong, X. and Xia, Y., A literature review of UAV 3D path planning, IEEE Xplore, 2015.
Mahafza, B., Radar Systems Analysis and Design Using MATLAB, Chapman & Hall/CRC, 2000.
Mahafza, B and Elsherbeni, A., MATLAB Simulations for Radar Systems Design, Chapman & Hall/CRC, 2004.
Makarov, I., Polyakov, P., & Karpichev, R., Voronoi-based Path Planning based on Visibility and Kill/Death RatioTactical Component, In AIST (Supplement), 129-140, 2018.
Mclain T. W. and Beard, R. W., Trajectory planning for coordinated rendezvous of unmanned air vehicles, In Proceedings of the AIAA Guidance, Navigation, and Control Conference, 1247–1254, 2000.
Murphy, R., Uryasev, S. and Zabarankin, M., Trajectory optimization in a threat environment, Research report 9, Department of Industrial and Systems Engineering, University of Florida, 2003.
Özcan, M., & Yaman, U., A continuous path planning approach on Voronoi diagrams for robotics and manufacturing applications, Procedia Manufacturing, 38, 1-8. 2019.
Qing, G., Zheng, Z., & Yue, X., Path-planning of automated guided vehicle based on improved Dijkstra algorithm, In 2017 29th Chinese control and decision conference (CCDC), 7138-7143, IEEE, 2017.
Richards, 2005 Richards, M. A., Fundamentals of Radar Signal Processing, New York: McGraw-Hill, 2005.
Schatzman, M., Numerical Analysis: A Mathematical Introduction, Oxford, Clarendon Press, 2002.
Shi, Y., Zhang, L., & Dong, S., Path Planning of Anti-ship Missile based on Voronoi Diagram and Binary Tree Algorithm, Defence Science Journal, 69(4), 369-377. 2019.
Skolnik, M., Radar Handbook, McGraw-Hill, 1990.
Skolnik, M. Introduction to Radar Systems, 3rd Ed. New York: McGraw-Hill, 2001.
Tang, F., You, X., Zhang, X., & Li, K., Hexagon-Based Generalized Voronoi Diagrams Generation for Path Planning of Intelligent Agents, Mathematical Problems in Engineering, 2020.
Turnbull, O., Lawry, J., Lowenberg, M., & Richards, A., A cloned linguistic decision tree controller for real-time path planning in hostile environments, Fuzzy Sets and Systems, 293, 1-29, 2016.
Willis, N. J. Bistatic Radar, Raleigh, NC: SciTech Publishing, 2005.
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, 2376-2381, IEEE, 2014.