A fast algorithm to solve large-scale matrix games based on dimensionality reduction and its application in multiple unmanned combat air vehicles attack-defense decision-making. (English) Zbl 1533.91097
Summary: In the scenario of attack-defense involved with unmanned combat air vehicles (UCAVs), it is often envisioned that a large group of UCAVs is deployed to complete some complex tasks which could be specifically modeled as large-scale matrix games. Solving such matrix games by the traditional linear programming approaches, however, could be quite time-consuming and thus cannot be implemented in real-time which is, in fact, a key requirement for real air combat. On this account, an algorithm, termed as dimensionality reduction based matrix game solving algorithm (DR-MG), is proposed in this paper to solve large-scale matrix games in a timely manner. Our algorithm builds on the technique of dimensionality reduction which inherently finds the convex hull vertices of a vector set. Through establishing the connection between Nash equilibria of the matrix games before and after dimensionality reduction, the proposed algorithm is capable of finding the solutions while only dealing with the matrix game with reduced dimensions. As a consequence, it is expected the time complexity of the proposed algorithm is significantly decreased, and thus the algorithm could be applicable in real air combat. Finally, numerical results are provided to show the effectiveness of our algorithm.
MSC:
| 91A68 | Algorithmic game theory and complexity |
| 91A07 | Games with infinitely many players |
| 93C85 | Automated systems (robots, etc.) in control theory |
| 93A16 | Multi-agent systems |
| 90C25 | Convex programming |
Keywords:
large-scale matrix game; dimensionality reduction; multi-UCAV air combat; convex optimizationSoftware:
QhullReferences:
| [1] | Li, S.; Chen, M.; Wang, Y.; Wu, Q., Air combat decision-making of multiple UCAVs based on constraint strategy games, Defence Technol. (2021), (in press) |
| [2] | Wang, M.; Wang, L.; Yue, T.; Liu, H., Influence of unmanned combat aerial vehicle agility on short-range aerial combat effectiveness, Aerosp. Sci. Technol., 96, Article 105534 pp. (2020) |
| [3] | Wang, M.; Wang, L.; Yue, T.; Liu, H., Influence of unmanned combat aerial vehicle agility on short-range aerial combat effectiveness, Aerosp. Sci. Technol., 96, Article 105534 pp. (2020) |
| [4] | Gu, Y.; Yu, X.; Guo, K.; Qiao, J.; Guo, L., Detection, estimation, and compensation of false data injection attack for UAVs, Inf. Sci., 546, 723-741 (2021) |
| [5] | Bagul, P.; Rana, Z. A.; Jenkins, K. W.; Könözsy, L., Computational engineering analysis of external geometrical modifications on MQ-1 unmanned combat aerial vehicle, Chin. J. Aeronaut., 33, 4, 1154-1165 (2020) |
| [6] | Kurdi, H.; Aldaood, M. F.; Al-Megren, S.; Aloboud, E.; Youcef-Toumi, K., Adaptive task allocation for multi-UAV systems based on bacteria foraging behaviour, Appl. Soft Comput., 83, Article 105643 pp. (2019) |
| [7] | Liu, H.; Peng, F.; Modares, H.; Kiumarsi, B., Heterogeneous formation control of multiple rotorcrafts with unknown dynamics by reinforcement learning, Inf. Sci., 558, 194-207 (2021) · Zbl 1489.93007 |
| [8] | Shi, C.; Yang, G., Augmented lagrange algorithms for distributed optimization over multi-agent networks via edge-based method, Automatica, 94, 55-62 (2018) · Zbl 1400.93011 |
| [9] | Shi, C.; Yang, G., Distributed learning over networks: Effect of using historical observations, IEEE Trans. Autom. Control, 65, 12, 5503-5509 (2020) · Zbl 1536.93339 |
| [10] | Zhang, J.; Kou, G.; Peng, Y.; Zhang, Y., Estimating priorities from relative deviations in pairwise comparison matrices, Inf. Sci., 552, 310-327 (2020) · Zbl 1486.91032 |
| [11] | Wang, H.; Kou, G.; Peng, Y., An iterative algorithm to derive priority from large-scale sparse pairwise comparison matrix, IEEE Trans. Syst. Man Cybern.: Syst., 1-14 (2021) |
| [12] | Mi, X.; Liao, H.; Zeng, X.; Xu, Z., The two-person and zero-sum matrix game with probabilistic linguistic information, Inf. Sci., 570, 487-499 (2021) · Zbl 1530.91014 |
| [13] | von Neumann, J.; Morgenstern, O., The Theory of Games and Economic Behavior (1944), Princeton University Press · Zbl 0063.05930 |
| [14] | Liu, L.; Zhang, L.; Liao, S.; Liu, J.; Wang, Z., A generalized approach to solve perfect bayesian nash equilibrium for practical network attack and defense, Inf. Sci., 577, 245-264 (2021) · Zbl 1527.91032 |
| [15] | Sedakov, A.; Qiao, H.; Wang, S., A model of river pollution as a dynamic game with network externalities, Eur. J. Oper. Res., 290, 3, 1136-1153 (2021) · Zbl 1487.91086 |
| [16] | Wang, L.; Zhao, N.; Liu, D., Complex disaster management: A dynamic game among the government, enterprises, and residents, J. Clean. Prod., 266, Article 122091 pp. (2020) |
| [17] | Zhang, T.; Li, C.; Ma, D.; Wang, X.; Li, C., An optimal task management and control scheme for military operations with dynamic game strategy, Aerosp. Sci. Technol., 115, Article 106815 pp. (2021) |
| [18] | Austin, F.; Carbone, G.; Hinz, H.; Lewis, M.; Falco, M., Game theory for automated maneuvering during air-to-air combat, J. Guidance Control Dyn., 13, 6, 1143-1149 (1990) · Zbl 0729.90855 |
| [19] | Cruz, J. B.; Simaan, M. A.; Gacic, A.; Jiang, H.; Letelliier, B.; Li, M.; Liu, Y., Game-theoretic modeling and control of a military air operation, IEEE Trans. Aerosp. Electron. Syst., 37, 4, 1393-1405 (2001) |
| [20] | Cruz, J. B.; Simaan, M. A.; Gacic, A.; Liu, Y., Moving horizon nash strategies for a military air operation, IEEE Trans. Aerospace Electron. Syst., 38, 3, 989-999 (2002) |
| [21] | Liu, Y.; Simaan, M. A.; Cruz, J. B., An application of dynamic nash task assignment strategies to multi-team military air operations, Automatica, 39, 8, 1469-1478 (2003) · Zbl 1153.93469 |
| [22] | Chen, X.; Deng, X.; Teng, S., Settling the complexity of computing two-player nash equilibria, J. ACM, 56, 3, 1-57 (2009) · Zbl 1325.68095 |
| [23] | Duan, H.; Li, P.; Yu, Y., A predator-prey particle swarm optimization approach to multiple UCAV air combat modeled by dynamic game theory, IEEE/CAA J. Autom. Sin., 2, 1, 11-18 (2015) |
| [24] | Li, W.; Shi, J.; Wu, Y.; Wang, Y.; Lyu, Y., A multi-UCAV cooperative occupation method based on weapon engagement zones for beyond-visual-range air combat, Defence Technol. (2021), (in press) |
| [25] | Maschler, M.; Solan, E.; Zamir, S., Game Theory (2013), Cambridge University Press · Zbl 1403.91003 |
| [26] | Zou, F.; Yen, G. G.; Tang, L.; Wang, C., A reinforcement learning approach for dynamic multi-objective optimization, Inf. Sci., 546, 815-834 (2021) · Zbl 1475.90099 |
| [27] | Martinez, A. M.; Kak, A. C., PCA versus LDA, IEEE Trans. Pattern Anal. Mach. Intell., 23, 2, 228-233 (2002) |
| [28] | Ma, J.; Yuan, Y., Dimension reduction of image deep feature using PCA, J. Vis. Commun. Image Represent., 63, Article 102578 pp. (2019) |
| [29] | Duan, Y.; Yang, C.; Chen, H.; Yan, W.; Li, H., Low-complexity point cloud denoising for lidar by PCA-based dimension reduction, Opt. Commun., 482, Article 126567 pp. (2021) |
| [30] | Fukunaga, K., Introduction to Statistical Pattern Recognition (1990), Academic Press · Zbl 0711.62052 |
| [31] | He, Z.; Wu, M.; Zhao, X.; Zhang, S.; Tan, J., Representative null space LDA for discriminative dimensionality reduction, Pattern Recogn., 111, Article 107664 pp. (2021) |
| [32] | Tian, Q.; Arbel, T.; Clark, J. J., Task dependent deep LDA pruning of neural networks, Comput. Vis. Image Underst., 203, Article 103154 pp. (2021) |
| [33] | Wei, W.; Dai, H.; Liang, W., Regularized least squares locality preserving projections with applications to image recognition, Neural Networks, 128, 322-330 (2020) · Zbl 1472.62104 |
| [34] | Liu, Y., Advanced isomap based on data nuggets algorithm, (2019 IEEE 5th International Conference on Computer and Communications (ICCC) (2019)), 57-60 |
| [35] | Miao, J.; Yang, T.; Sun, L.; Fei, X.; Niu, L.; Shi, Y., Graph regularized locally linear embedding for unsupervised feature selection, Pattern Recogn., 122, Article 108299 pp. (2022) |
| [36] | Liu, S.; Guo, S.; Wang, W.; Qiao, H.; Wang, Y.; Luo, W., Multi-view laplacian eigenmaps based on bag-of-neighbors for RGB-D human emotion recognition, Inf. Sci., 509, 243-256 (2020) |
| [37] | Dong, Y.; Feng, J.; Zhang, H., Cooperative tactical decision methods for multi-aircraft air combat simulation, J. Syst. Simul., 14, 6, 723-725 (2002) |
| [38] | C. Jiang, Q. Ding, J. Wang, J. Wang, Research on threat assessment and target distribution for multi-aircraft cooperative air combat, Fire Control Command Control 33(11) (2008) 8-12+21. |
| [39] | Xu, X.; Yang, R.; Fu, Y., Threat assessment in air combat based on ELM neural network, (2019 IEEE International Conference on Artificial Intelligence and Computer Applications (ICAICA), IEEE (2019)), 114-120 |
| [40] | Li, S.; Wu, Q.; Chen, M.; Wang, Y., Air combat situation assessment of multiple UCAVs with incomplete information, Chinese Intelligent Systems Conference, Springer, 18-26 (2020) |
| [41] | Bertismas, D.; Ttsitskikilis, J., Introduction to Linear Optimization (1997), Athena Scientific |
| [42] | Huang, H.; Han, J., Mathematical programming (2006), Tsinghua University Press |
| [43] | Graham, R. L., An efficient algorithm for determining the convex hull of a finite planar set, Inf. Process. Lett., 1, 4, 73-82 (1972) |
| [44] | Andrew, A. M., Another efficient algorithm for convex hulls in two dimensions, Inf. Process. Lett., 9, 5, 216-219 (1979) · Zbl 0423.68032 |
| [45] | Barber, C. B.; Dobkin, D. P.; Huhdanpaa, H., The quickhull algorithm for convex hulls, ACM Trans. Math. Software, 22, 4, 469-483 (1996) · Zbl 0884.65145 |
| [46] | Di, W.; Hong, Q.; Bo, Z.; Min, W., Online support vector machine based on convex hull vertices selection, IEEE Trans. Neural Networks Learn. Syst., 24, 4, 593-609 (2013) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
