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
1. Johansson, F. and Falkman, G. An empirical investigation  of the static weapon-target allocation problem",  Proceedings of the 3rd Skovde Workshop on Information  Fusion Topics, pp. 63{67 (2009).  2. Ling, W., Hang, Y.W., Faxing, L., et al. An anytime  algorithm based on modi_ed GA for dynamic weapontarget  allocation problem", IEEE Congress on Evolutionary  Computation, pp. 2020{2025 (2008).  3. Yan, Y., Zha, Y., Qin, L., et al. A research on weapontarget  assignment based on combat capabilities", In  Mechatronics and Automation (ICMA), 2016 IEEE  International Conference on, pp. 2403{2407 (2016).  4. Wen, Y., Liu, L., Wang, Z., et al. Multi-UCAVs targets  assignment using opposition-based genetic algorithm",  In Control and Decision Conference (CCDC),  2015 27th Chinese, pp. 6026{6030, IEEE (2015).  5. Jiuyong, Z., Chuanqing, X., Xiaojing, W., et al.  ACGA algorithm of solving weapon-target assignment  problem", Open Journal of Applied Science, 2(4),  pp. 74{77 (2012).  6. Zhu, B., Zou, F., and 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, pp. 1385{1387 (2011).  7. Mei-Zi, L. 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), pp.  198{204 (2010).  8. Zhou, T., Zhang, J., Shi, J., et al. Multidepot UAV  routing problem with weapon con_guration and time  window", Journal of Advanced Transportation (2018).  9. Sahin, M.A. and Kemal Leblebicioglu, K. Approximating  the optimal mapping for weapon-target assignment  by fuzzy reasoning", Information Sciences, 255,  pp. 30{44 (2014).  10. Gurdal A., Marden, J.R., and Shamma, J.S.  Autonomous vehicle-target assignment: A gametheoretical  formulation", Transactions of the ASME,  129, pp. 584{596 (2007).  11. Lechevin, N., Rabbath, C.A., and Lauzon, M. A  distributed network enabled weapon-target assignment  for combat formations", Optimization & Cooperative  Ctrl. Strategies, Springer LNCIS, 381, pp. 47{67  (2009).  12. Seung, H.R., Hwa-Sung, K., and Seung-Won, S. The  e_ect of decentralized resource allocation in networkcentric  warfare", IEEE, The International Conference  on Information Network, pp. 478{481 (2012).  13. Plamondon, P., Chaibdraa, B., and Benaskeur, A.R.  A Multiagent Task Associated MDP (MTAMDP)  approach to resource allocation", AAAI Spring Symposium  (2006).  14. Johansson, F. and Falkman, G. A suite of metaheuristic  algorithms for static weapon-target allocation",  GEM, pp. 132{138 (2010).  15. Tokgoz, A. and Bulkan, S. Weapon target assignment  with combinatorial optimization techniques", International  Journal of Advanced Research in Arti_cial  Intelligence (IJARAI), 2(7), pp. 39{50 (2013).  16. Lotter, D.P., Nieuwoudt, I., and Van Vuuren, J. A  multiobjective approach towards weapon assignment  in a ground-based air defense environment", Orion,  29(1), pp. 31{54 (2013).  17. Li, J., Chen, J., Xin, B., and Chen, L. E_cient  multi-objective evolutionary algorithms for solving the  multi-stage weapon-target assignment problem: A  comparison study", IEEE Congress on Evolutionary  Computation (CEC), pp. 435{442 (2017).  18. Lotter, D.P. and Van Vuuren, J. A tri-objective,  dynamic weapon assignment model for surface-based  air defence", ORiON, 32(1), pp. 1{22 (2016).  19. Zhou, D., Li, X., Pan, Q., et al. Multiobjective  weapon-target assignment problem by two-stage evolutionary  multiobjective particle swarm optimization",  IEEE International Conference on Information and  Automation Ningbo, pp. 921{926 (2016).  20. Lotter, D.P. Modeling weapon assignment as a multiobjective  decision problem", Partial Ful_llment of  the Requirements for the Degree MComm, Stellenbosch  University (2012).  N. Feghhi et al./Scientia Iranica, Transactions D: Computer Science & ... 28 (2021) 1539{1551 1551  21. Ahuja, R.K., Kumar, A., Krishna, C.J., et al. Exact  and heuristic algorithms for the weapon target assignment  problem", Operations Research, 55(6), pp. 1136{  1146 (2007).  22. Chi, H., Liu, J., Chen, Y., et al. Survey of the  research on dynamic weapon-target assignment problem",  Journal of Systems Engineering and Electronics,  17(3), pp. 559{565 (2006).  23. Khamis, A., Hussein, A., and Elmogy, A. Multi-robot  task allocation: A review of the state-of-the-art", In  Cooperative Robots and Sensor Networks, A. Koub_aa,  D.J. Mart__nez-de, Eds., Studies in Computational Intelligence,  Springer, 604, pp. 31{51 (2015).  24. Ziaee, M. Single machine scheduling problem with  convex multi-resource dependent processing times and  job deadlines", Scientia Iranica, 24(2), pp. 847{855  (2017).  25. Imanipour, N. A Heuristic approach based on tabu  search for early/tardy exible job shop problems",  Scientia Iranica, 13(1), pp1{13 (2006).  26. Bogdanowicz, Z.R. Advanced input generating algorithm  for e_ect-based weapon-target pairing optimization",  IEEE Transactions on Systems, Man,  and Cybernetics{Part A: Systems and Humans, 42(1),  (January, 2012).  27. Frini, A., Guitouni, A., and Benaskeur, A. 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 (2017).  28. Rathinam, B., Govindan, K., Neelakandan, B., et  al. Rule based heuristic approach for minimizing  total ow time in permutation ow shop scheduling",  Tehni_cki vjesnik, 22(1), pp. 25{32 (2015).  29. Bogdanowicz, Z.R. Advanced input generating algorithm  for e_ect-based weapon-target pairing optimization",  IEEE Transactions On Systems, Man, And  Cybernetics{Part A: Systems And Humans, 42(1), pp.  276{280 (2012).  30. Benaskeur, A.R., Kabanza, F., Beaudry, E., et al. A  probabilistic planner for the combat power management  problem", ICAPS: 12{19 (2008).