# DX-IFD: An Intelligent Force Deployment System

Junpeng Bao, Yuepeng Zhang, Wenqing Wang, Jun Zeng, De Zhang, Ruiyu Yuan

## ► To cite this version:

Junpeng Bao, Yuepeng Zhang, Wenqing Wang, Jun Zeng, De Zhang, et al., DX-IFD: An Intelligent Force Deployment System. 10th IFIP International Conference on Artificial Intelligence Applications and Innovations (AIAI), Sep 2014, Rhodes, Greece. pp.298-306, 10.1007/978-3-662-44654-6_29 hal-01391327

HAL Id: hal-01391327

https://inria.hal.science/hal-01391327

Submitted on 3 Nov 2016

HAL is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est destinée au dépôt et à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

<figure><img src="image_1.png" /></figure>
# DX-IFD: An Intelligent Force Deployment System

Junpeng Bao¹, Yuepeng Zhang², Wenqing Wang¹, Jun Zeng², De Zhang², Ruiyu Yuan¹

1. Department of Computer Science & Technology, Xi'an Jiaotong University, Xi'an 710049, P.R. China

baojp@mail.xjtu.edu.cn

2. Xi'an Institute of Surveying & Mapping, Xi'an 710000, P.R. China

## Abstract.

It is easy to gather a huge amount of information from a battlefield by satellites, manned or unmanned aerial vehicles. But it becomes an important issue to effectively deal with the tremendous information and create reasonable solutions based on that. This paper introduces an Intelligent Force Deployment system DX-IFD, which combines topography heuristic information and military principles with the Genetic Algorithm to automatically identify the battlefield features and make the optimized force deployment in terms of the topography, the enemy status and our mission. A Relative Position Code method is presented to encode the deployment, which ensures the optimized formation will be kept after genetic operations. According to basic military principles, we propose a force deployment assessment scheme which evaluates a deployment solution from three aspects: unit fitness, formation fitness and relationship fitness. The DX-IFD system can quickly response to the change of battlefield situation, evaluate and create the optimized deployment in different configuration conditions. It greatly improves the force ability to quickly react and occupy the dominant positions in a battle.

**Keywords:** Intelligent Force Deployment, Genetic Algorithm, Topography Analysis
# 1 Introduction

The modern information technology and computer science have made a deep impact on military. A variety of automatic weapons and systems are changing the way of war. A huge amount of information, which is gathered from battlefields, enemies and ourselves, has to be properly treated on time, otherwise any opportunity is fleeting. In contrast with computer, mankind is good at fuzzy decision making based on knowledge rather than precise computation. It is obviously impossible for a person to manually deal with a large scale of various data in minutes. However, artificial intelligence applications can help us to quickly process big data, analyze miscellaneous situations and find appropriate candidate solutions. Hence, a commander will decide promptly on correct actions with substantial rational power rather than temerity.

This paper introduces an Intelligent Force Deployment system DX-IFD, which aims to automatically identify the battlefield features and make the optimized force deployment in terms of the topography, enemy status and our mission. This system can quickly response to the change of battlefield situation, evaluate and create the optimized deployment in different configuration conditions. As a result, DX-IFD improves the force ability to quickly react and occupy the dominant positions in a battle.

# 2 Related work

Since 1980s, United States Department of Defense has been studying the application of expert system in the military. Franklin et al.[1] introduced some applications for the military expert system and pointed out the key problems existed in the representation and reasoning about the uncertain knowledge and machine learning. In 2012, Haberlin et al.[2] presented a battle management system based on event simulation and optimization for military decision support. The Turkish army [3,4] researched the simulation system for military deployment and military logistics transport deployment optimization. The system exploited the probability statistics and regression tree to analyze the principal influence factors. Kettani et al.[5] in Canadian Department of National Defense proposed a spatial reasoning method to analyze battlefield situation and support military decision.

White et al.[6] presented a hybrid heuristic/evolutionary algorithm for automatically generating spatial deployment plans that minimize power consumption. Aleti et al.[7] put forward Heuristic for Component Deployment Optimization (BHCDO), which
constructs solutions based on a Bayesian learning mechanism to improve quality of
new deployment architectures. Lian et al.[8] proposed a method for 3D deployment
optimization of sensor network based on an improved Particle Swarm Optimization
(PSO) algorithm. Guan et al.[9] also proposed a PSO algorithm to minimize the aver-
age outage area rate of the LED deployment scheme in VLC systems.

Chinese researchers studied more on air defense force deployment issues than the
land force deployment. The stochastic optimization method is a very popular way.
Wang[10] and Xiong et al.[11] separately introduced the PSO based algorithm for the
optimized hybrid deployment of air defense troops. Kong et al.[12] presented a grey
comprehensive correlation analysis method and a double bee population evolutionary
genetic algorithm for air defense force position optimization problem. Chen [13]
combined a Genetic Algorithm with a local neighborhood search strategy for the
firepower unit deployment issue.

3 The DX-IFD system

3.1 System architecture

The DX-IFD system is an intelligent force deployment system based on the topography
analysis. It exploits empirical military knowledge to automatically and intelligently
deal with the topography information and create optimized force deployment solutions
according to the military requirements.

The figure 1 shows the DX-IFD system main workflow. The system is composed of five steps. First, it collects battlefield picture photos by satellites or unmanned aerial vehicles. Second, it analyzes the features in these photos to identify objects, such as plain, hill, river, residential area etc. Third, it determines the fitness value for different types of troops in an area, such as armored troops, artillery troops, and infantry troops etc. At this step, the system employs a rule based uncertainty reasoning scheme to take both military knowledge and geographic into account. Fourth, it makes a digital grey map for each troop type to illustrate its fitness at anywhere of the battlefield, and then grey maps are combined into color maps according to a special order. Finally, it creates the optimized force deployment solutions based on the color fitness maps according to military requirements.

This paper concentrates on the last step, especially on the GA based intelligent force
deployment method and the force deployment assessment scheme.
<figure><img src="image_2.png" /><figcaption>**Fig. 1.** The DX-IFD system main workflow</figcaption></figure>
## 3.2 The optimization goal

The force deployment task is to assign blended troop units into most appropriate areas in the given geographic space and satisfy the given military requirements. The troop units are of various types, including headquarters, armored units, artillery units, and infantry units etc. Apparently, the force deployment task is a Constraint Satisfaction Problem in theory, which is a typical Non-deterministic Polynomial (NP) problem. We abstract the problem as follows.

1. The troop units of various types are represented by different sizes of squares that located somewhere in the battlefield map.

2. The fitness of a troop unit in an area is measured by the Relative Average Grey (RAG) value of the unit in the square.

3. The spatial location relationship among all of the deployed units should conform to a certain formation.

4. The spatial relationship between our deployment and the enemy has to satisfy some constraints.

Thus, the optimization goal of the force deployment is to locate k squares on the given color map so as to maximize the entire assessment value on the whole. Namely, it can be described in the following formulas.

$$ 
\begin{array}{l}
\text{Max}\{F(U)\}, \quad U = [u_1, u_2, \dots, u_k], \\
\text{s.t.} \quad U \subset G \\
\text{s.t.} \quad T(u_i) \in \{\text{Headquarters}, \text{Armored}, \text{Infantry}, \dots\}, \quad i = \{1, 2, \dots, k\} \\
\text{s.t.} \quad S(U) \to D \\
\text{s.t.} \quad R(U, E) \to C
\end{array}
$$

Where $u_i(i=1, \dots, k)$ denotes a troop unit, $U$ denotes the whole deployment, $F(U)$ means the entire fitness of the whole deployment, $G$ denotes the given battlefield color map. $T(u_i)$ means the troop type of the $u_i$. $S(U)$ means the spatial location relationship of the $U$, $R(U,E)$ means the spatial relationship between our deployment $U$ and the enemy $E$.

## 3.3 Intelligent deployment algorithm

Genetic Algorithm (GA) is a popular method to effectively solve optimization problem. It focuses on the representation and assessment of solutions to the problem, rather than precisely mathematical analysis process. The Intelligent deployment algorithm indeed
exploits the GA to make the optimized force deployment solutions. It releases us from
plenty of complicated uncertain deduction of deployment transformation. The key
points of the Intelligent deployment algorithm are the representation and the assess-
ment of force deployment solution.

3.3.1 The representation of force deployment solution

A force deployment solution is represented by a k-dimensional vector, called deployment
vector, in which each dimension is responsible for a specific troop unit, and the type of
a unit corresponds to its position in the vector. The construction of the deployment
vector is based on prescient military knowledge that is stored in a database. Naturally, it
depends on specific military requirements.

In theory, a unit area consists of 2-dimensional space coordinates and the radius.
But for a given level of the troop unit, the area size is fixed, which can be obtained from
the database. In order to reduce the length of the vector and improve the computational
efficiency, 2-dimensional space coordinates is only used to represent a unit.

In Genetic Algorithm, a deployment vector (i.e. individual) is encoded into a
sequence of code, i.e. a genome. A directly coding strategy takes a troop unit's absolute
position as a gene code, which corresponds to the unit's Cartesian coordinates in the
battlefield map. But this strategy would destroy deployment formation and is not
conducive to a better formation. For example, there are two deployment solutions A
and B. A is on the left of the battlefield while B is on the right, then they exchange half
of the vector respectively and generate another two new solutions whose part of the
units are on the left and the others on the right. Obviously, it is not a valid formation
because a deployment cannot be scattered across the whole battlefield.

We propose a Relative Position Code (RPC) method, which takes the relative co-
ordinates, i.e. polar coordinates, to code a genome. A genome consists of two parts:
polar coordinates of the headquarters and the other deployment units' polar coordi-
nates, as shown in the figure 2. The headquarters polar coordinates are relative to the
enemy position, but the other units' polar coordinates are relative to the headquarters.

<figure><img src="image_3.png" /><figcaption>Fig. 2. A deployment vector and Relative Position Code</figcaption></figure>
Formation is actually the spatial location relationship among each unit. It is a very important constraint of force deployment. Because units have to keep reasonable distance and effective connection from each other. A wrong formation causes deadly chaos. The RPC method accurately keeps this relationship so as to avoid the formation damaged by absolute position coding. No matter how to cross and exchange the old genome sequences, the new created genome sequences are valid because each gene is still relative to the origin of polar coordinate, i.e. the headquarters, in the new genome. The RPC method ensures that the optimized formation will be kept after crossing operation.

### 3.3.2 The assessment of force deployment solution

We present a 10-point score scheme to assess an individual and conform to generally grading habits. A force deployment solution $U$ is assessed from three aspects: unit fitness $A(U)$, formation fitness $D(U)$ and relationship fitness $R(U)$, i.e.

$$F(U) = w_0 A(U) + w_1 D(U) + w_2 R(U) \quad (1)$$

Where the range of each fitness value is [0,1] and the weights ($w_0, w_1, w_2$) are adjustable parameters, such as $w_0=4.5, w_1=2.5, w_2=3.0$.

The unit fitness evaluates how much each deployment unit suits for specific topology. Namely, is a unit deployed to a suitable topography? In practice, it is often not the best solution to put every unit on its best position. When the whole solution is the best, many parts of the solution, i.e. units, may not locate at the best position. A reasonable deployment solution not only makes a tradeoff between all units but also considers the overall formation and the relationship with enemy. It is a complicated multi-parameters optimization problem to find a reasonable deployment solution.

The formation fitness evaluates whether the overall formation of a deployment is reasonable. It refers to the space geometry relation among the deployment units. There is a basic principle, i.e. “Act according to circumstances”, the optimized deployment solution must face to the specific topography. Moreover, it must consider the spatial relationship among all units, satisfy certain geometric constraints and follow the basic military principles.

The relationship fitness assesses whether a deployment solution is effective against the enemy according to enemy information. Our deployment should be revised when the enemy position changes. The most basic requirement is that our offensive firepower should be toward the enemy and do not put our back to the enemy. Additionally, we should keep a proper distance with the enemy, neither too close nor too far.
### 3.3.3 The unit fitness

The unit fitness of a deployment solution is defined as follows.

$$A(U) = \frac{1}{|U|} \sum_{u_i \in U} \left( \frac{1}{255 \times |u_i|} \sum_{p \in u_i} \text{Grey}(p) \right) \quad (2)$$

Where $|U|$ denotes the number of units in an individual $U$. $|u_i|$ denotes the area of the unit $u_i$. Grey($p$) is the actual fitness of a unit type at the point $p$, i.e. how much the point $p$ is suitable for the unit $u_i$, which is in the range of [0,255].

The Grey($p$) value is read from the fitness grey map of the specific type of unit. For a given battlefield, the grey map depends on the type of deployment unit. For example, an armored unit's grey map is obviously different from an infantry unit on the same field. Because an area where is suitable for infantry, may be adverse to the armored, such as hillside. These fitness grey maps are made at the step 4 of the DX-IFD system main workflow, as shown in the figure 1.

In fact, a pixel grey value needs only 1 byte. But for a colorful RGB image, a pixel has three bytes. Therefore, three grey maps of different unit types can be compounded in a colorful RGB image. It is convenient for data management.

### 3.3.4 The formation fitness

The formation of a deployment solution should try to meet some rules that describe relatively fixed geometric relationship. The position of the headquarters is defined as the formation's origin. Thus, a formation is described by a serial of unit's polar coordinates that is relative to the headquarters.

The formation fitness of a deployment solution is measured by the deviation between the polar coordinate of the unit and the ideal polar coordinate, i.e.

$$D(U) = \frac{1}{|U| - 1} \sum_{i=2}^{|U|-1} \left[ 0.5 \exp\left(-\frac{(d_i - ed_i)^2}{\sigma_{di}^2}\right) + 0.5 \exp\left(-\frac{(r_i - er_i)^2}{\sigma_{ri}^2}\right) \right] \quad (3)$$

Where $d_i$ and $ed_i$ respectively denote the straight-line distance and ideal distance between the $i$-th unit and the headquarters. $r_i$ and $er_i$ respectively denote the angle and ideal angle between this unit direction and horizontal direction. $\sigma_{di}$ and $\sigma_{ri}$ respectively denote the standard deviation of ideal distance and ideal angle. It is defined that first dimension in a deployment vector corresponds to the headquarters.
### 3.3.5 The relationship fitness

The figure 3 illustrates relations between our deployment and the enemy. The enemy bearing point (the o point) is regarded as the origin of polar coordinate. The distance between o and the deployment center (the c point), denoted as $d_c$, should be as close as possible to an ideal distance $d_e$. The c point is better on the way to the front of enemy. Thus, the direction angle from o to c, denoted as $r_c$, should be opposite to the enemy direction angle $r_e$. The head unit (the h point) is expected to point to the enemy. So the

head unit angle $r_h$ should equal $r_c$, the distance between o and h, denoted as $d_h$, should less than $d_c$. Considering these factors comprehensively, the relationship fitness is defined as follows.

<figure><img src="image_4.png" /><figcaption>Fig. 3. The spatial relations between the deployment and enemy</figcaption></figure>

$$R(U) = a \exp\left(-\frac{(r_h - r_e)^2}{\sigma_h^2}\right) \times \mu(d_e - d_h) + b \exp\left(-\frac{(r_e - r_e - 180)^2}{\sigma_r^2}\right) + c \exp\left(-\frac{(d_c - d_e)^2}{\sigma_d^2}\right) \quad (4)$$

Where $\sigma_h$, $\sigma_r$ and $\sigma_d$ are standard deviation of head unit angle, deployment center angle and deployment center distance respectively. Angles are measured in degree. $\mu$ is the sign whether the deployment direction is facing to or back to the enemy, it is defined as follows.

$$\mu(d_e - d_h) = \begin{cases} 1, & d_e > d_h \\ -1, & d_e < d_h \\ 0, & \text{otherwise} \end{cases} \quad (5)$$

## 4 Experimental results

The figure 4 (a) shows a randomly created deployment solution whose final assessment value is 2.9187. Obviously, its formation is so poor that it cannot effectively attack enemy at all. In the figure, the blue arrow marks the enemy bearing point and the
direction. Each deployment unit is marked by a red rectangle with a unit type label, such as “H” for headquarters, “AR” for armored unit, “INF” for infantry unit and “AA” for anti-aircraft artillery unit.

The figure 4 (b) shows a good deployment solution recommended by the DX-IFD system algorithm, of which the assessment value is 7.7757. This deployment is reasonable and the spatial relationships between each unit are in line with military principles. Moreover, it can effectively attack the enemy.

<figure><img src="image_5.png" /><figcaption>Fig. 4. (a) A worse deployment solution ($F(U)=2.9187$). (b) A good deployment solution recommended by the DX-IFD system algorithm ($F(U)=7.7757$)</figcaption></figure>

## 5 Conclusions

Intelligent force deployment is a complicated multi-parameter optimization process. The DX-IFD system combines topography heuristic information and military principles with the Genetic Algorithm to automatically deal with the topography information and create optimized force deployment solutions according to the military requirements. The RPC method is presented to encode the deployment, which ensures the optimized formation will be kept after genetic operations. According to basic military principles, we propose a force deployment assessment scheme which evaluates a deployment solution from three aspects: unit fitness, formation fitness and relationship fitness. The test result shows that the system can automatically generate the optimized deployment solution for the given topography and enemy information. However, some system parameters need to be further refined.
Reference

1. J. E. FRANKLIN, et al. Expert System Technology for the Military: Selected Samples. Proceedings of the IEEE. 1988, 76(10):1327-1366

2. R. Haberlin and A. Brodsky. Battle Management System (BMS): An Optimization for Military Decision Makers. In proceedings of the 2012 IEEE ICDE. 2012, pp. 78-81

3. U. Z. Yıldırım and A. Balcıoğlu. A Design of Experiments Approach to Military Deployment Planning Problem. In proceedings of the 2008 Winter Simulation Conference. 2008, pp. 1234-1241

4. İ.Akgün and B.Tansel. Optimization of Transportation Requirements in the Deployment of Military Units. Computers and Operations Research, 2007, 34(4): 1158 – 1176

5. D. Kettani and J. Roy. A Qualitative Spatial Model For Information Fusion and Situation Analysis. In proceedings of the ISIF2000. 2000, pp. 16-23

6. J. White, et al. ScatterD: spatial deployment optimization with hybrid heuristic/evolutionary algorithms. ACM Transactions on Autonomous and Adaptive Systems, 2011, 6(3): 18-43.

7. A. Aleti, I. Meedeniya. Component deployment optimization with Bayesian learning. In proceedings of the 14th ACM SIGSOFT. 2011, pp. 11-20.

8. X.Y. Li, et al. Three-dimensional deployment optimization of sensor network based on an improved Particle Swarm Optimization algorithm. In proceedings of the 10th IEEE WCICA.2012, pp. 4395-4400.

9. R. Guan, et al. PSO-based LED deployment optimization for visible light communications. In proceedings of 2013 IEEE WCSP. 2013, pp. 1-6.

10. Y.B. Wang, J.J. Wang, Y.L. Wang. Study of Hybrid Force Disposition Based on Particle Swarm Optimization. Tactical Missile Technology. 2009, (3): 44-47

11. Z. Xiong, R.M. Xu, F. Tian. Improved Particle Swarm Optimization algorithm applied to hybrid force disposition optimization. Computer Engineering and Applications, 2012, 48(6):235-237.

12. D.J. Kong, L.Y. Chen, H.F. Zhang, Y. Ma. Study on Modeling Troops Disposition of Army Anti-Aircraft Missile Unit. Ordnance Industry Automation. 2011, 30(1):12-16

13. J. Chen, C. Chen, J. Zhang, B. Xin. Deployment Optimization for Point Air Defense Based on Memetic Algorithm. ACTA AUTOMATICA SINICA. 2010, 36(2):242-248