Nonlinear optimal model and solving algorithms for platform planning problem in battlefield

doi:10.21629/JSEE.2018.05.10

Journal of Systems Engineering and Electronics ›› 2018, Vol. 29 ›› Issue (5): 983-994.doi: 10.21629/JSEE.2018.05.10

• Systems Engineering • Previous Articles Next Articles

Nonlinear optimal model and solving algorithms for platform planning problem in battlefield

Xun WANG^1,*(), Peiyang YAO¹(), Jieyong ZHANG¹(), Lujun WAN²()

¹ Information and Navigation College, Air Force Engineering University, Xi’an 710077, China
² Air Traffic Control and Navigation College, Air Force Engineering University, Xi’an 710051, China

Received:2017-05-29 Online:2018-10-26 Published:2018-11-14
Contact: Xun WANG E-mail:wxkgdxy@163.com;ypy_664@163.com;dumu3110728@126.com;pandawlj@126.com
About author:WANG Xun was born in 1990. He is currently a Ph.D. candidate of Air Force Engineering University. He received his B.S. degree in communication engineering from Shandong University in 2013, and M.S. degree in command information system from Air Force Engineering University in 2013 respectively. His research interests include command information system and mission planning. E-mail: wxkgdxy@163.com|YAO Peiyang was born in 1960. Currently he is a professor in Information and Navigation College, Air Force Engineering University. He received his B.S. degree in 1982 and M.S. degree in 1991 from Xidian University. His research topics include command and control theory and command automation system. E-mail: ypy_664@163.com|ZHANG Jieyong was born in 1983. Currently he is a lecturer in Information and Navigation College, Air Force Engineering University. He received his B.S. degree in 2006, M.S. degree in 2008 and Ph.D. degree in 2012 from Air Force Engineering University respectively. His research interests include mission planning technique and military organizational analysis. E-mail: dumu3110728@126.com|WAN Lujun was born in 1986. Currently he is a lecturer in Air Traffic Control and Navigation College, Air Force Engineering University. He received his B.S. degree in 2007, M.S. degree in 2010 and Ph.D. degree in 2014 from Air Force Engineering University respectively. His research interest is combat agent modeling and simulation. E-mail: pandawlj@126.com
Supported by:
the National Natural Science Foundation of China(61573017);the National Natural Science Foundation of China(61703425);the Aeronautical Science Fund(20175796014);the Shaanxi Province Natural Science Foundation Research Project(2016JQ6062);the Shaanxi Province Natural Science Foundation Research Project(2017JM6062);This work was supported by the National Natural Science Foundation of China (61573017; 61703425), the Aeronautical Science Fund (20175796014) and the Shaanxi Province Natural Science Foundation Research Project (2016JQ6062; 2017JM6062)

Abstract

Abstract:

Platform planning is one of the important problems in the command and control (C2) field. Hereto, we analyze the platform planning problem and present nonlinear optimal model aiming at maximizing the task completion qualities. Firstly, we take into account the relation among tasks and build the single task nonlinear optimal model with a set of platform constraints. The Lagrange relaxation method and the pruning strategy are used to solve the model. Secondly, this paper presents optimization-based planning algorithms for efficiently allocating platforms to multiple tasks. To achieve the balance of the resource assignments among tasks, the m-best assignment algorithm and the pair-wise exchange (PWE) method are used to maximize multiple tasks completion qualities. Finally, a series of experiments are designed to verify the superiority and effectiveness of the proposed model and algorithms.

Key words: platform planning, nonlinear optimal model, Lagrange relaxation method, m-best algorithm, pair-wise exchange (PWE)

Xun WANG, Peiyang YAO, Jieyong ZHANG, Lujun WAN. Nonlinear optimal model and solving algorithms for platform planning problem in battlefield[J]. Journal of Systems Engineering and Electronics, 2018, 29(5): 983-994.

Figures/Tables 15

Fig 1

Fig 2

Fig 3

Fig 4

Table 1

Table 2

Table 3

Table 4

Table 5

Table 6

Table 7

Table 8

Fig 5

Fig 6

Fig 7

References 35

1	YU F L, TU F, PATTIPATI K R. Integration of a Holonic organizational control architecture and multiobjective evolutionary algorithm for flexible distributed scheduling. IEEE Trans. on Systems, Man, and Cybernetics-Part A: Systems and Humans, 2008, 38 (5): 1007- 1017.
2	LEVCHUK G M, LEVCHUK Y N, LUO J, et al. Normative design of organizations. IEEE Trans. on Systems, Man, and Cybernetics-Part A: Systems and Humans, 2002, 32 (3): 346- 359. doi: 10.1109/TSMCA.2002.802819
3	HUTCHINS S G, KEMPLE W G, KLEINMAN D L, et al. Maritime headquarters with maritime operations center: a research agenda for experimentation. Proc. of the 14th International Command and Control Research and Technology Symposium, 2009: 1-33.
4	SUN Y. Research on design and evaluation method for agile command and control organization. Xi’an, China: Air Force Engineering University, 2017. (in Chinese)
5	KAN Z, BAOPING L. Study on the combination evaluation of military resources allocation efficiency. Proc. of the 3rd IEEE International Conference on Information Management, 2017: 199-202.
6	HAN X, BUI H, MANDAL S, et al. Optimization-based decision support software for a team-in-the-loop experiment: asset package selection and planning. IEEE Trans. on Systems, Man, and Cybernetics: Systems, 2013, 43 (2): 237- 251. doi: 10.1109/TSMCA.2012.2201467
7	HAN X, MANDAL S, PATTIPATI K R, et al. An optimizationbased distributed planning algorithm: a blackboard-based collaborative framework. IEEE Trans. on Systems, Man, and Cybernetics: Systems, 2014, 44 (6): 673- 686. doi: 10.1109/TSMC.2013.2276392
8	BALOS I D, CIOACA C, BOSCOIANU M. Solutions to improve the decision-making process for dynamic allocation of resources in military pre-conflict environments. Proc. of the 8th International Conference on Manufacturing Science and Education, 2017, 121: 07001.
9	ROBERTSON D W. A note on the classical origin of "circumstances" in the medieval confessional. Studies in Philology, 1946, 43 (1): 6- 14.
10	KUZNETSOV A V. Allocation of limited resources in a system with a stable hierarchy (on the example of prospective military communications system). Upravlenie Bol’shimi Sistemami, 2017, 66, 68- 93.
11	MARUSICH L R, BAKDASH J Z, ONAL E, et al. Effects of information availability on command-and-control decision making: performance, trust, and situation awareness. Human factors, 2016, 58 (2): 301- 321. doi: 10.1177/0018720815619515
12	HAN X. Optimization-based decision support algorithms for network identification and dynamic resource management. Connecticut, USA: University of Connecticut, 2016.
13	RAMIREZ-ATENCIA C, BELLO-ORGAZ G, R-MORENO M D, et al. Solving complex multi-UAV mission planning problems using multi-objective genetic algorithms. Soft Computing, 2017, 21 (17): 4883- 4900. doi: 10.1007/s00500-016-2376-7
14	WILHELM J, ROJAS J, EBERHART G, et al. Heterogeneous aerial platform adaptive mission planning using genetic algorithms. Unmanned Systems, 2017, 5 (1): 19- 30. doi: 10.1142/S2301385017500029
15	MISHRA M, AN W, SIDOTI D, et al. Context-aware decision support for anti-submarine warfare mission planning within a dynamic environment. IEEE Trans. on Systems Man & Cybernetics Systems, 2017, 1- 18.
16	GUHA S, MUNAGALA K, PENG S. Approximation algorithms for restless bandit problems. Proc. of the 20th ACMSIAM Symposium on Discrete Algorithms-Society for Industrial and Applied Mathematics, 2009: 28-37.
17	AZIZA H, KRICHEN S. Bi-objective decision support system for task-scheduling based on genetic algorithm in cloud computing. Computing, 2018, 100 (2): 65- 91.
18	PANDA S K, JANA P K. Efficient task scheduling algorithms for heterogeneous multi-cloud environment. Journal of Supercomputing, 2015, 71 (4): 1505- 1533.
19	WU H, LIU J. A multi-agent genetic algorithm based on natural coding for emergency resources scheduling problems. Proc. of the IEEE Evolutionary Computation, 2016: 2706-2711.
20	REVIEWS E M. The multiple traveling salesman problem: an overview of formulations and solution procedures. Omega, 2009, 34 (3): 209- 219.
21	LAPORTE G. The vehicle routing problem: an overview of exact and approximate algorithms. European Journal of Operational Research, 2007, 59 (2): 231- 247.
22	FILIPPI C, MANSINI R, STEVANATO E. Mixed integer linear programming models for optimal crop selection. Computers and Operations Research, 2017, 81 (C): 26- 39.
23	BOUKOUVALA F, MISENER R, FLOUDAS C A. Global optimization advances in mixed-integer nonlinear programming, MINLP, and constrained derivative-free optimization, CDFO. European Journal of Operational Research, 2016, 252 (3): 701- 727.
24	LEYFFER S. Integrating SQL and branch and bound for mixed integer nonlinear programming. Computational Optimization & Applications, 1998, 18 (3): 259- 309.
25	WESTERLUND T, PETTERSSON F. An extended cutting plane method for solving convex MINLP problems. Computers & Chemical Engineering, 1995, 19 (1): 131- 136.
26	AGLER J. The implicit function theorem and free algebraic sets. Transactions of the American Mathematical Society, 2016, 368 (5): 3157- 3175.
27	BERTSEKAS D P. Constrained optimization and Lagrange multiplier methods. Boston: Academic Press, 2014.
28	KIM S, KOJIMA M, TOH K C. A Lagrangian-DNN relaxation: a fast method for computing tight lower bounds for a class of quadratic optimization problems. Mathematical Programming, 2016, 156 (1/2): 161- 187.
29	DERRAC J, GARCÍA S, MOLINA D, et al. A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms. Swarm and Evolutionary Computation, 2011, 1 (1): 3- 18.
30	SUN Y, YAO P Y, SHUI D D, et al. Uncertain optimal model and solving method to platform scheduling problem in battlefield. Journal of Systems Engineering and Electronics, 2016, 27 (1): 157- 165.
31	ZHANG Y, LIU S H. Survey of multi-robot task allocation. CAAI Trans. on Intelligent Systems, 2008, 3 (2): 115- 120.
32	KUHN H W, TUCKER A W. Nonlinear programming. GIORGIO G, Tinne H K. ed. Traces and emergence of nonlinear programming. Basel: Birkhäuser, 2014: 247- 258.
33	ZHANG L Y, SIDOTI D, PATTIPATI K R, et al. Approaches for solving m-best 3-dimensional dynamic scheduling problems for large m. Proc. of the 19th IEEE International Conference on Information Fusion, 2016: 53-58.
34	BERTSEKAS D P, CASTANON D A. Rollout algorithms for stochastic scheduling problems. Journal of Heuristics, 1999, 5 (1): 89- 108. doi: 10.1023/A:1009634810396
35	BERTAZZI L. Improved rollout search for the vehicle routing problem with stochastic demands. Social Science Research Network Electronic Journal, 2016. doi: 10.2139/ssrn.2759840

Task	$t_{p, i}$	$t_{s, i}$	C2	STRK	AW	BMD	CMD	SUW	USW	MIW	ISR(A)	ISR(S)	ISR(G)	BDA
TAMD GREEN(T₁)	30	0	5	0	12	14	10	0	0	0	12	0	4	0
TAMD BLUE(T₂)	30	0	3	0	8	8	7	0	0	0	6	0	4	0
Attack MSL Bases(T₃)	30	0	2	7	0	0	0	0	0	0	0	0	5	7
AEW Area(T₄)	30	0	5	0	0	0	0	0	0	0	5	0	0	0
Attack C2 Nodes(T₅)	30	0	2	6	0	0	0	0	0	0	0	0	0	5
SURF SURV Area(T₆)	30	0	2	0	0	0	0	0	0	0	0	5	0	0
DEF vs. CDCM Attack(T₇)	24	0	2	0	0	0	8	0	0	0	0	5	0	0
Attack Air Bases(T₈)	24	0	2	5	5	0	0	0	0	0	0	0	2	3
Attack IADS(T₉)	18	0	2	8	5	0	0	0	0	0	0	0	0	5
MIW in Strait(T₁₀)	10	6	2	0	0	0	0	0	0	5	0	4	0	0
CVG Penetrate(T₁₁)	4	26	5	0	10	0	8	10	6	0	5	5	0	0

Platform	Number	C2	STRK	AW	BMD	CMD	SUW	USW	MIW	ISR(A)	ISR(S)	ISR(G)	BDA
CVN	1	5	6	5	0	2	5	2	1	5	5	2	5
CG	2	3	5	8	7	6	4	3	3	7	5	0	0
DDG	3	2	5	8	7	6	4	3	3	6	4	0	0
SSN	3	0	3	0	0	0	5	4	2	1	3	1	0
P3	3	1	0	0	0	0	6	2	0	0	6	0	3
MH53	1	0	0	0	0	0	0	0	4	0	0	0	0
AWACS	2	5	0	5	0	0	0	0	0	8	3	1	0
JSTAR	1	3	0	0	0	0	0	0	0	0	1	6	3
U2	1	0	0	0	0	0	0	0	0	3	2	4	3
RJ	1	2	0	0	0	0	0	0	0	4	3	3	2
UAV	3	0	0	0	0	0	0	0	0	0	1	5	5
AEF	1	5	7	5	0	0	1	0	0	4	1	3	3

Task	Platform 1	Platform 2	Platform 3	Platform 4	Quality/%
TAMD GREEN (T₁)	CG	DDG	JSTAR		100
TAMD BLUE(T₂)	DDG	DDG	UAV		100
Attack MSL Bases(T₃)	UAV	AEF			100
AEW Area (T₄)	CVN				100
AttackC2 Nodes(T₅)	CG	SSN	UAV		100
SURF SURV Area (T₆)	P3	P3			100
DEF vs. CDCM Attack(T₇)					0
Attack Air Bases(T₈)	SSN	SSN	AWACS	U2	100
Attack IADS(T₉)					0
MIW in Strait (T₁₀)	P3	MH53	RJ		92.83
CVG Penetrate(T₁₁)					0
Average					72.08

Task	Platform 1	Platform 2	Platform 3	Platform 4	Quality/%
TAMD GREEN (T₁)	CG	DDG	JSTAR		100
TAMD BLUE(T₂)	DDG	DDG	UAV		100
Attack MSL Bases(T₃)	UAV	AEF			100
AEW Area (T₄)	AWACS				100
AttackC2 Nodes(T₅)	CG	SSN	UAV		100
SURF SURV Area (T₆)	P3	P3			100
DEF vs. CDCM Attack(T₇)	CVN				63.00
Attack Air Bases(T₈)	SSN	SSN	AWACS	U2	100
Attack IADS(T₉)					0
MIW in Strait (T₁₀)	P3	MH53	RJ		92.83
CVG Penetrate(T₁₁)	CVN	SSN	AWACS		82.03
Average					85.26

Task	Platform 1	Platform 2	Platform 3	Platform 4	Quality
TAMD GREEN (T₁)	CG	DDG	JSTAR		100%
TAMD BLUE(T₂)	DDG	P3	UAV		95.32%
Attack MSL Bases(T₃)	UAV	AEF			100%
AEW Area (T₄)	AWACS				100%
AttackC2 Nodes(T₅)	CVN	SSN	UAV		100%
SURF SURV Area (T₆)	P3	P3			100%
DEF vs. CDCM Attack(T₇)	CG				90.86%
Attack Air Bases(T₈)	SSN	SSN	AWACS	U2	100%
Attack IADS(T₉)					0%
MIW in Strait (T₁₀)	DDG	MH53	RJ		100%
CVG Penetrate(T₁₁)	CVN	SSN	AWACS		82.03%
Average					88.02%

Nonlinear optimal model and solving algorithms for platform planning problem in battlefield

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

Share this article

Figures/Tables 15

References 35

Related Articles 0

Recommended Articles

Metrics

Comments