A real-time exhaustive search algorithm for the weapon-target assignment problem

Document Type : Article

Authors

Faculty of New Sciences and Technologies, Department of Aerospace Engineering, University of Tehran, Tehran, Iran

Abstract

Weapon-Target Assignment (WTA) as an important part of aerial defense cycle has long been ‎studied. Challenges are usually finding fast-computing methods to search optimal or near-‎optimal solution in cases of a large number of weapons and targets. This viewpoint is more ‎mathematically considerable but practically has limited usage in the mentioned context. A ‎real-time search algorithm is proposed which decomposes the WTA problem and by ‎decreasing the size of solution space and deleting impossible solutions, enables real-time ‎exhaustive search algorithm. Implementation of the algorithm for three typical scenarios shows ‎excellent real-time performance and the possibility of finding exact solutions for large-scale ‎problems.‎

Keywords


References:
. Ahuja, R.K., Kumar, A., Krishna, C.J. & et al. (2003). Exact and Heuristic Algorithms for the Weapon Target Assignment Problem.
. Benaskeur, A.R., Kabanza, F., Beaudry & et al. (2008) A Probabilistic Planner for the Combat Power Management Problem, ICAPS: 12-19.
. Bogdanowicz, Z.R. (2012). Advanced Input Generating Algorithm for Effect-Based Weapon–Target Pairing Optimization, IEEE Transactions On Systems, Man, And Cybernetics—Part A: Systems And Humans, 42(1): 276-280.
.
Chi, H., Liu, J., Chen, Y. & et al. (2006). Survey of the research on dynamic weapon-target assignment problem, Journal of Systems Engineering and Electronics, 17(3):559-565.
. Frini, A., Guitouni, A. and Benaskeur, A., (2017). Solving Dynamic Multi-Criteria Resource-Target Allocation Problem Under Uncertainty: A Comparison of Decomposition and Myopic Approaches. International Journal of Information Technology & Decision Making, 16(06), pp.1465-1496.
. Gürdal A., Marden J.R. & Shamma J.S. (2007). Autonomous Vehicle-Target Assignment: A Game-Theoretical Formulation, Transactions of the ASME, 129: 584-596.
. Imanipour, N. (2006). 'A Heuristic Approach Based on Tabu Search for Early/Tardy Flexible Job Shop Problems', Scientia Iranica, 13(1).
. Jiuyong Z., Chuanqing X., Xiaojing W. & et al. (2012). ACGA Algorithm of Solving Weapon - Target Assignment Problem, Open Journal of Applied Science, 2(4): 74-77.
. Johansson, F. & Falkman G. (2009). An empirical investigation of the static weapon-target allocation problem, Proceedings of the 3rd Skövde Workshop on Information Fusion Topics: 63-67
. Johansson, F. & Falkman, G. (2010). A Suite of Metaheuristic Algorithms for Static Weapon-Target Allocation. GEM: 132-138.
. Khamis A., Hussein A., Elmogy A. (2015) Multi-robot Task Allocation: A Review of the State-of-the-Art. In: Koubâa A., Martínez-de Dios J. (eds) Cooperative Robots and Sensor Networks. Studies in Computational Intelligence, Springer, 604: 31-51. 
. Lechevin, N., Rabbath, C.A. & Lauzon M. (2009). A Distributed Network Enabled Weapon-Target Assignment for Combat Formations, Optimization & Cooperative Ctrl. Strategies, Springer LNCIS, 381: 47–67.
. Li, J., Chen, J., Xin, B. & Chen, L. (2017). Efficient Multi-objective evolutionary algorithms for solving the multi-stage weapon-target assignment problem: A comparison study, IEEE Congress on Evolutionary Computation (CEC): 435-442.
. Ling, W., Hang, Y. W., Fa-xing, L. & et al. (2008). An Anytime Algorithm Based On Modified GA For Dynamic Weapon-Target Allocation Problem, IEEE Congress on Evolutionary Computation: 2020-2025
. Lotter, D.P., Nieuwoudt, I. & Van Vuuren J. (2013). A multiobjective approach towards weapon assignment in a ground-based air ‎defense environment, Orion. 2013 ; 29(1):31-54.
. Lotter, D.P. & Van Vuuren, J. (2016). A Tri-Objective, Dynamic Weapon Assignment Model for Surface-Based Air Defence. ORiON, 32(1):1-22.
. Lotter, D.P., (2012). Modeling weapon assignment as a multiobjective decision problem, partial fulfillment of the requirements for the degree MComm, Stellenbosch University.
. Mei-Zi, L. (2010). Constrained Weapon–Target Assignment: Enhanced Very Large Scale Neighborhood Search Algorithm, IEEE Transactions On Systems, Man, And Cybernetics—Part A: Systems And Humans, 40(1): 198-204.
. Plamondon, P., Chaibdraa, B. & Benaskeur, A.R. (2006). A Multiagent Task Associated MDP (MTAMDP) Approach to Resource Allocation, AAAI Spring Symposium, 2006.
. Rathinam, B., Govindan, K., Neelakandan, B. , et al. (2015) Rule based heuristic approach for minimizing total flow time in permutation flow shop scheduling. Tehnički vjesnik, 22(1), pp.25-32.
. Sahin, M.A. & Kemal Leblebicioglu, K. (2014) Approximating the optimal mapping for weapon-target assignment by fuzzy reasoning, Information Sciences 255: 30–44.
. Seung, H.R., Hwa-Sung, K.& Seung-Won, S. (2012) The Effect of Decentralized Resource Allocation in Network-Centric Warfare, IEEE, The International Conference on Information Network: 478-481.
.Tokgöz, A. & Bulkan, S. (2013). Weapon target assignment with combinatorial optimization techniques. International Journal of Advanced Research in Artificial Intelligence (IJARAI), 2(7):39-50.
. Wen, Y., Liu, L., Wang, Z. , et al. (2015), May. Multi-UCAVs targets assignment using opposition-based genetic algorithm. In Control and Decision Conference (CCDC), 2015 27th Chinese (pp. 6026-6030). IEEE.
. Yan, Y., Zha, Y., Qin, L., et al. (2016), August. A research on weapon-target assignment based on combat capabilities. In Mechatronics and Automation (ICMA), 2016 IEEE International Conference on (pp. 2403-2407).
. Zbigniew, R. Bogdanowicz. (2012). Advanced Input Generating Algorithm for Effect-Based Weapon–Target Pairing Optimization. IEEE Transactions On Systems, Man, And Cybernetics—Part A: Systems And Humans, 42(1), January.
. Zhou, D., Li, X., Pan, Q., et al. (2016). Multiobjective weapon-target assignment problem by two-stage evolutionary multiobjective particle swarm optimization, IEEE International Conference on Information and Automation Ningbo: 921-926.
. Zhou, T., Zhang, J., Shi, J., et al. Multidepot UAV Routing Problem with Weapon Configuration and Time Window. Journal of Advanced Transportation, 2018.
. Zhu, B., Zou F. & Wei J. A Novel Approach to Solving Weapon-target Assignment Problem Based on Hybrid Particle Swarm Optimization Algorithm, International Conference on Electronic & Mechanical Engineering and Information Technology, IEEE, 12-14 August: 1385-1387. (2011).  
. Ziaee, M. Single machine scheduling problem with convex multi-resource dependent processing times and job deadlines', Scientia Iranica, 24(2), pp. 847-855. (2017).