Distributed Solving of Weapon Target Assignment Problem using Learning Automata

Document Type : Original Article

Author

Instructor, Department of Computer Engineering, Technical and Vocational University, Tehran, Iran

Abstract

This article presents a method to solve the weapon target assignment problem, which is one of the problems of distributed constraint optimization. The previous methods do not guarantee the convergence problem properly and when faced with scale increase, they do not work correctly and effectively. Also, some of these methods solve the weapon target assignment problem in a centralized manner. While the method presented in this article solves the problem in a decentralized and distributed manner with better "accuracy" and "speed".
The present article solves the weapon target assignment problem by using learning automata, which is a relatively simple method and requires little information, and the results of implementations show that when the scale of the problem becomes larger, the proposed method it solves the problem with a better speed than other methods, so that the objective function is minimized. Also, this method can well address the shortcomings of previous methods without the need for other exploratory methods in real-time multi-agent environments.

Keywords

Smiley face

References

[1]     J. J. Enright, "Efficient routing of multi-vehicle systems: limited sensing and nonholonomic motion constraint"s. 2008.
[2]    S. P. Lloyd and H. S. Witsenhausen, "Weapons allocation is NP-complete," in 1986 summer computer simulation conference, 1986, pp. 1054-1058.
[3]    P. A. Hosein, J. T. Walton, and M. Athans, "Dynamic weapon-target assignment problems with vulnerable C2 nodes", Massachusetts Inst of Tech Cambridge Lab for Information and Decision Systems, 1988.
[4]     P. A. Hosein and M. Athans, "Preferential defense strategies", pp.1-25, 1990.
[5]    P. A. Hosein and M. Athans, "Some analytical results for the dynamic weapon-target allocation problem", MASSACHUSETTS INST OF TECH CAMBRIDGE LAB FOR INFORMATION AND DECISION SYSTEMS, 1990.
[6]     S. Han, "Stochastic theory and method for effectiveness analysis of missile weapon systems", BeiJing National Defense Industry Press, pp. 77-78, 2001.
[7]     Z. J. Lee, C. Y. Lee, and S. F. Su, "A Hybrid Genetic Algorithm Applied to Weapon-Target Assignment Problem", 2004.
[8]     D. Khosla, "Hybrid genetic approach for the dynamic weapon-target allocation problem", in Battlespace digitization and network-centric warfare, pp. 4396, pp. 244-259: International Society for Optics and Photonics.
[9]    R. K. Ahuja, J. B. Orlin, and A. Tiwari, "A greedy genetic algorithm for the quadratic assignment problem," COMPUT OPER RES, vol. 27, no. 10, pp. 917-934, 2000.
[10]   Z. R. Bogdanowicz, A. Tolano, K. Patel, and N. P. Coleman, "Optimization of weapon–target pairings based on kill probabilities," IEEE transactions on cybernetics, vol. 43, no. 6, pp. 1835-1844, 2012.
[11]   K. Volle, J. Rogers, and K. Brink, "Decentralized cooperative control methods for the modified weapon–target assignment problem," J GUID CONTROL DYNAM, vol. 39, no. 9, pp. 1934-1948, 2016.
[12]   H. Cai, J. Liu, Y. Chen, and H. Wang, "Survey of the research on dynamic weapon-target assignment problem," J SYST ENG, vol. 17, no. 3, pp. 559-565, 2006.
[13]   J. Chen, J. Yang, and G. Ye, "Auction algorithm approaches for dynamic weapon target assignment problem," in 2015 4th International Conference on Computer Science and Network Technology (ICCSNT), vol. 1, pp. 402-405, 2015.
[14]   H. Alimohammady and V. Tabatabavakily, "A Novel Algorithm for Radar Jamming Resource Allocation", Electronic and Cyber Defense, vol. 7, no. 3, pp. 53-70, 2019.
[15]   K. Tuyls, "Learning in Multi-agent Systems. An Evolutionary Game Theoretic Approach," 2004.
[16]   M. A. Thathachar and P. S. Sastry, Networks of learning automata: Techniques for online stochastic optimization. Springer Science & Business Media, 2003.
[17]   M. D. Pendrith and M. J. McGarity, "An analysis of non-Markov automata games: Implications for reinforcement learning." University of New South Wales, School of Computer Science and Engineering, 1997.
[18]   P. Vrancx, K. Verbeeck, and A. Nowé, "Networks of learning automata and limiting games," in Adaptive Agents and Multi-Agent Systems III. Adaptation and Multi-Agent Learning: Springer, 2005, pp. 224-238.
[19]   R. K. Ahuja, A. Kumar, K. C. Jha, and J. B. Orlin, "Exact and heuristic algorithms for the weapon-target assignment problem," OPER RES, vol. 55, no. 6, pp. 1136-1146, 2007.
[20]   M.-Z. Lee, "Constrained weapon–target assignment: Enhanced very large scale neighborhood search algorithm," IEEE T SYST MAN CY A, vol. 40, no. 1, pp. 198-204, 2009.
[21]   J. M. Rosenberger, H. S. Hwang, R. P. Pallerla, A. Yucel, R. L. Wilson, and E. G. Brungardt, "The generalized weapon target assignment problem," Texas Univ at Arlington 2005.
[22]   A. G. Kline, D. K. Ahner, and B. J. Lunday, "Real-time heuristic algorithms for the static weapon target assignment problem," J HEURISTICS, vol. 25, no. 3, pp. 377-397, 2019.
[23]   Z. R. Bogdanowicz, "Advanced input generating algorithm for effect-based weapon–target pairing optimization," IEEE T SYST MAN CY A, vol. 42, no. 1, pp. 276-280, 2011.
[24]   A. Tokgöz and S. Bulkan, "Weapon target assignment with combinatorial optimization techniques," International journal of advanced research in artificial intelligence, vol. 2, no. 7, pp. 39-50, 2013.
[25]   F. Johansson and G. Falkman, "Real-time allocation of defensive resources to rockets, artillery, and mortars," in 2010 13th International Conference on Information Fusion, 2010, pp. 1-8: IEEE.
[26]   B. Xin, Y. Wang, and J. Chen, "An efficient marginal-return-based constructive heuristic to solve the sensor–weapon–target assignment problem," IEEE T SYST MAN CYB: Systems, vol. 49, no. 12, pp. 2536-2547, 2018.
[27]   W. Jian and C. Chen, "Sensor-weapon joint management based on improved genetic algorithm," in 2015 34th Chinese Control Conference (CCC), 2015, pp. 2738-2742: IEEE.
[28]   Z. T. Wang, H. J. Zhang, Y. Huang, K. Cheng, and T. Y. Wu, "Fire distribution optimization based on quantum immune genetic algorithm," in 2011 International Conference of Information Technology, Computer Engineering and Management Sciences, vol. 1, pp. 95-98, 2011.
[29]   F. Xue-yuan, X. Qing-hua, and T. Feng, "Dynamic target assignment base on ameliorated genetic algorithm," in 2010 International Conference on Computer Application and System Modeling (ICCASM 2010, vol. 15, pp. 443 -445, 2010.
[30]   D. G. Galati, "Game theoretic target assignment strategies in competitive multi-team systems," University of Pittsburgh, 2005.
[31]   S. Zeng, W. Wang, D. Ding, and Y. Zhang, "Target allocation method based on dynamic game," Electronics Optics & Control, vol. 18, no. 2, pp. 26-29, 2011.
[32]   Y. Yang and X. Liu, "Task assignment based on improved dynamic contract net and ant colony search strategy," in Proceedings 2013 International Conference on Mechatronic Sciences, Electric Engineering and Computer (MEC), 2013, pp. 2880-2883: IEEE.
[33]   R. Ghorbani Saber, M. Ranjbar, S. Balochian, and A. Izadipour, "Modelling and optimal solving of dependent sensor-weapon/threat assignment and scheduling problem by a metaheuristic algorithm based on GRASP," Electronic and Cyber Defense, vol. 8, no. 1, pp. 35-50, 2020 (in persian).
[34]   M. Alighanbari and J. P. How, "Decentralized task assignment for unmanned aerial vehicles," in Proceedings of the 44th IEEE Conference on Decision and Control, 2005, pp. 5668-5673: IEEE.
[35]   S.-Y. Tang, S. Mei, Y.-F. Zhu, Y.-L. Lei, and Q. Li, "Distributed weapon target assignment algorithm based on extended contract net protocol," Systems Engineering and Electronics, vol. 33, no. 3, pp. 568-574, 2011.
[36]   L. Cao and A. Zhang, "Cooperative target assignment for unmanned combat aerial vehicles based on Bayesian optimization algorithm with decision graphs," in 2013 Ninth International Conference on Natural Computation (ICNC), pp. 439-443, 2013.
[37]   Y. Chen, H. Cai, and L. Xing, "An improved algorithm of policies optimization of dynamic weapon target assignment problem," Systems Engineering-Theory & Practice, vol. 7, pp. 160-165, 2007.
[38]   L. Wang, H. Zheng, and X. Zheng, "Survey on resource-constrained project scheduling under uncertainty [J]," Control and Decision, vol. 29, no. 4, pp. 577-584, 2014.
[39]   K. S. Narendra and M. A. L. Thathachar, Learning Automata: An Introduction. Dover Publications, 2013.
[40]   A. R. Eckler and S. A. Burr, "Mathematical Models Of Target Coverage And Missile Allocation," 1972.
[41]   S. Matlin, "A Review of the Literature on the Missile-Allocation Problem," OPER RES, vol. 18, no. 2, pp. 334-373, 1970.
[42]   A. S. Manne, "A Target-Assignment Problem," OPER RES, vol. 6, no. 3, pp. 346-351, 1958.
[43]   M. A. Sahin and K. Leblebicioglu, "A genetic algorithm for weapon target assignment problem," presented at the Proceedings of the 2009 Summer Computer Simulation Conference, Istanbul, Turkey, 2009.
[44]   S. Mirjalili, "Genetic Algorithm," in Evolutionary Algorithms and Neural Networks: Theory and Applications Cham: Springer International Publishing, 2019, pp. 43-55.
[45]  K. D. Hoang, F. Fioretto, P. Hou, M. Yokoo, W. Yeoh and R. Zivan. “Proactive dynamic distributed constraint optimization”. In: Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2016, pp. 597–605.
[46]   A. Petcu and B. Faltings. “DPOP: A scalable method for multiagent constraint optimization”. In IJCAI 05, pp. 266-271, 2005.
Electronic and Cyber Defense
Volume 11, Issue 1 - Serial Number 41
No. 41, Spring
May 2023
Pages 47-55

Files

History

  • Receive Date: 21 January 2022
  • Revise Date: 26 July 2022
  • Accept Date: 24 December 2022
  • Publish Date: 22 May 2023

Share

How to cite

Statistics