Target Selection in UAV Cooperative Control Under Uncertain Environment: Genetic Algorithm
Target Selection in UAV Cooperative Control under Uncertain Environment: Genetic Algorithm Approach
JOSE B. CRUZ, JR, GENSHE CHEN, DONGXU LI, DENIS GARAGIC
Department of Electrical Engineering
OhioStateUniversity
205 Dreese Lab, 2015 Neil Ave, Columbus, OH43210
USA
Abstract:-Target selection is one of the core steps to effectively exploit the capabilities of cooperative control of multiple Unmanned Aerospace Vehicle (UAV) teams. The purpose of target selection is to find an appropriate allocation of the limited number of UAVs and weapons against a collection of targets with the objective of maximizing target value damage while minimizing collateral damage, which has become increasingly decisive as the emphasis in conflicts shifts toward minimizing casualties on civilians/non-combatants. Generally, target selection is an NP-complete problem. In addition, in modern battle environment there continue living uncertain information, for example, location of target. In this paper, we present a new fuzzy logic based target selection model considering the collateral damage and a new target selection algorithm using genetic algorithm based optimization. We describe the issues on how to model the collateral damage effects and the method of using fuzzy membership function to quantify the imprecision information. We also discuss the adaptation and implementation of the GA search strategy to the target selection problem in the cooperative control of multiple UAVs. Simulation results indicate that the fuzzy model and genetic algorithm strategy is a feasible approach for the target selection problem.
Key-Words: - Cooperative Control, Target Selection, Collateral Damage, Genetic Algorithm, Fuzzy Logic
1 Introduction
The use of UAVs has been increasing recently. The role of UAV is evolving from reconnaissance purpose to offensive mission, as a missile-launching platform. The capabilities of UAV will be further improved if multiple UAVs are cooperative [1]-[3]. Realization of cooperation among UAVs requires a method of assigning targets to the vehicles such that all targets are prosecuted in an optimal manner, and ensure that constraints are met. Basically, this leads to the target selection problem. The target selection problem falls into two main categories: static and dynamic. Static target selection means that the assignment may be made at time t such that all of the UAVs are committed, while dynamic target selection is made at any of several discrete points of time, based on current state information.
Target selection has several characteristics. First of all, we are facing two types of targets: RED (enemy military facilities) and white (civilian facilities). Secondly, in modern battlefields, there exists vague and uncertain information in the decision making. For instance, the accuracy of target location may not be known 100%. Also, the UAVs are usually equipped with a limited number of munitions, which may be of different types and hence having different capabilities. Further more, certain type of targets may be more valuable than others. Finally, the collateral damage to civilian properties and the incidental injury or death of civilians is to be minimized. Therefore, the assignment of UAV to targets includes many aspects such as the values of targets, the kill probabilities of the weapons, the risks of UAV attrition, the number and types of munitions available, the locations of the targets, the distances between the red targets and white objects, and the weapon maximum effective radiusetc.
The target selection problem falls into the categories: NP-hard or NP-complete. The complexity of solving such problems requires computational efforts that increase polynomially with the size of the problem. The exact solution may be obtained using the optimization algorithms (e.g. linear programming, dynamic programming, etc) [4]-[5]. However, if the problem is not amenable to optimization algorithms due to unacceptably large computation time, another option is to go for solutions which can be obtained quickly at the risk of sub-optimality. These are called approximate or heuristic algorithm. A heuristic algorithm is very efficient in handling combinatorial explosion encountered in target selection problem. Under this light, we introduce a genetic algorithm (GA) based heuristic algorithm for the static target selection problem.
The Genetic Algorithm (GA) is a stochastic search method that models the process of nature selection and genetics [6]-[7]. It is an iterative algorithm that maintains a pool of feasible solutions, during each iteration. The GA starts with a set of randomly selected chromosomes as the initial population that encodes a set of possible solutions. Variables of a problem are represented as genes in a chromosome, and chromosomes are evaluated according to their fitness values, which are obtained by evaluating the considered fitness or cost function. Recombination typically involves two operators: (1) crossover and (2) mutation. Genetic operators alter the composition of genes to create new chromosomes referred to as offspring. The selection operator is an artificial version of nature selection, a Darwinian survival of the fittest among populations, to create populations from generation to generation. Chromosomes with better fitness have higher probabilities of being selected in the next generation. After several generations, GA can converge to the best solution. GA has many advantages over other heuristic techniques. For example, GA can be implemented in a few lines of computer code, it requires only primitive mathematical operators, and it has high probability to escape local optima.
The important contributions presented in the paper include: (1) A GA based search strategy solves multi-objective optimization in the target selection problem. The GA handles possible combinatorial explosion. (2) A fuzzy decision logic is used to specify the cost function. The fuzzy membership function accommodates the intrinsic uncertainties in battle environment. (3) A new model includes the white targets effect to reflect collateral damage penalty. The remainder of this paper is organized as follows. Section 2 provides the mathematical modeling of the target selection problem; Section 3 describes the GA algorithm; Simulation results are discussed in section 4; finally, section 5 gives the conclusion.
2 Problem Formation
Target selection (TS) is a Resource Allocation (RA) problem. It is the calculation of the optimal UAV allocation subject to the resource constraints. The objective of TS can be roughly divided into three classes: 1) To Attack Red Forces (maximizing target value damage), 2) To Avoid White Objects (minimizing collateral damage), and 3) To Save Blue Forces (minimizing UAV attrition). In this paper, three sub-objectives are represented by, and, which stand for attacking red forces, saving blue forces and avoiding white objects respectively.Due to the intrinsic uncertainties in the battlefield, the concept of fuzzy membership functions has been utilized in the modeling of the problem. The problem and the constraints are described below.
Assume that the team composition has finished and the team tasking has been identified [1]. Our objective is to find a possible UAV target allocation that maximizes red target value damaged while minimizing collateral damage. The decision variables determine which UAV is assigned to which target. The overall objective function can be considered as a linear combination of those sub-goals and, shown below.
(1)
where and are scalars, which convey the information of the relative importance of each sub-goal in the mission, interpreted from the commander’s preference between attacking red targets and avoiding white objects [8]. Nowwe formulate each sub-objective. The sub-objective function is formulated in the following form:
(2)
where is the number of UAVs; the number of targets;isthe decision variable. if target is assigned to UAV, otherwise. represents the benefit associated with the possible assignment of , whichdepends on the properties of UAV and target as well as their current states. And since each UAV can be assigned to at most one target, there existsanotherconstraint, formulated in equation (2), i.e., .
From above, we know that one of the critical questions in target selection problem is how to choose. First, let us consider the sub objective on attacking the red targets. In this case,
(3)
Here is a scalar, which is chosen such that the term; is determined using fuzzy membership function, which will be described later, and is the current state of UAV. It is noted that has nothing to do with the optimization variable. Obviously, to determine, and should be calculated first.
1). Determination of’s. The parameter in equation (3) stands for the possible benefit that can be gained by the possible assignment of UAV to target. And it can be determined by:
(4)
where is Red target valuesthat indicate relative importance of each target; is the probability that target is a real target to attack; is the probability of being destroyed for target given that UAV is assigned to attack it. Assume that UAV would make use of all of its available resource to attack target, by the simple statistical calculation, could be determined by the following equation.
(5)
where is the blueweaponkill probability for UAV to target and is the number of weapons for UAV.
2) Fuzzy membership function.In the problem of determining, its value is related to relevance between the effective weapon range and the actual distance between UAV and target. We use the fuzzy concept to represent the uncertainties on the edge instead of using a step function. This problem is that given the effective range and the distance, to determine the degree of satisfaction of assigning UAV to target, represented by the fuzzy membership function. It is noted that is used in to represent the general state information, and now to be clear, the distance is used instead of. The exponential function is chosen and the “transition band” is considered as with the center. And is formulated as
(6)
In the equation above, 1% in the denominator in the power term is chosen such that when the difference between and is greater than 5% of , the exponential term will decay less than 1%, which is suitable for the “transition band”. Now, let be 500, the shape of the membership function is shown in Figure 1 below.
Fig.1: Fuzzy Membership Function
with
It is clear that range of is a close interval between 0 and 1. When the target falls within the UAV’s weapon effective radius, is close to 1; while when the target is out of the effective radius, the degree of satisfaction tends to zero exponentially. is applied here instead of a sharp transition of the step function in order to compensate the vagueness from the UAV effective maximum attacking radius and the noisy distance measurement from the sensor.
Regarding the sub objective on avoiding white objects, those distances between each white object and the red targets will be of concern. More specifically, if one of the white objects, which has been identified, is close to some targets and within the weapon maximum effective radius of UAV, the possibility of being destroyed for this white object will be very high during our attack of those red targets. In a real war conflict, the damage to these civilian objects should be minimized. Based on this consideration, those’s in equation (2) can be formulated as follows:
(7)
where is the effective value of the white object , and defined as . Here is the relative value of importance for the white object andis its corresponding correct identification probability. is the total number of white objects under consideration. Again, is the fuzzy membership function, capturing the possibility that white object can be destroyed, based on the distance between white object and target relative to the weapon maximum effective radius of UAV . In particular, stands for the distance between white object and red target, and is the blue weapon maximum effective radius. Similar to the fuzzy membership function in, is defined as:
(8)
With each sub-objective function defined above, the overall target selection problem becomes to find a set of admissible such that the objective in equation (1) is minimized under constraints condition equation (2).
(9)
Obviously this will require solving a problem with a large search space. For example, for one target and UAVs, where each UAV is a potential assignment to attack this target, the number of possible target UAV pairings is. For targets and UAVs, number of possible pairing is of the order of . Thus, as the number of target increases, the number of such combinations or possible target-UAV pairing increases exponentially. This is the reason for choosing the GA algorithm.
3 Genetic Algorithm for Target
Selection Problem
In this paper, we propose a GA based heuristic method to solve the target selection problem. The basics of GA are reviewed next. GA mechanics for target selection problem are introduced in section 3.2.
3.1 Description of the Genetic Algorithm
The genetic algorithm is a stochastic optimization algorithm that was originally motivated by the mechanisms of natural selection and evolutionary genetics. The underlying principle of GA was first published by Holland in 1962. The mathematical framework was developed in the late 1960s, and has been presented in Holland's pioneering book, Adaptive in Natural and Artificial Systems [6]. Over the last decade, GA has been extensively used as search and optimization tools in various problem domains, including the sciences, commerce and engineering. The primary reasons for their success are their broad applicability, ease of use and global perspective [7], [9]. More detail about the GA can be found in [7], [9].
The GA is a powerful search algorithm based on the mechanics of natural selection and natural genetics. There are some differences between the GA and traditional searching algorithms. They can be summarized as follows:
- The algorithm works with a population of strings, searching many peaks in parallel, as opposed to a single point.
- The GA works directly with strings of characters representing the parameter set, not the parameters themselves.
- The GA uses probabilistic rules instead of deterministic rules.
- The GA uses objective function information instead of derivatives or other auxiliary knowledge.
The GA is inherently parallel, because it simultaneously evaluates many points in the parameter space (search space). Considering many points in the search space, GA has a reduced chance of converging to local optimum and would be more likely to converge to global optimum. In the most conventional search techniques, a single point is considered based on some decision rules. These methods can be dangerous in multimodal (many peaks) search spaces because they are very likely to converge to local optima. However, the GA works with a population of binary strings, searching many peaks in parallel. By employing genetic operators, they exchange information between the peaks; hence, reducing the possibility of ending at a local optimum.
The GA requires only information concerning the quality of the solution produced by each parameter set (objective function values). This differs from many optimization methods that require derivative information or, worse yet, a complete knowledge of the problem structure and parameters. Since the GA does not require such problem-specific information, it is more flexible than most search methods.
Typically the GA is characterized by the following components:
- A genetic representation (or an encoding) for the feasible solution to the optimization problem
- A population of encoded solution
- A fitness function that evaluates the optimality of each solution
- Genetic operators that generate a new population from the existing population
- Control parameters
The GA may be viewed as an evolutionary process wherein a population of solutions evolves into a sequence of generations. During each generation, the fitness of each solution is evaluated, and solutions are selected for reproduction based on their fitness. Selection embodies the principle of “survival of the fittest”. “Good” solutions are selected for reproduction while “bad” solutions are eliminated. The “goodness” of a solution is determined from its fitness value. The selected solutions then undergo recombination under the action of the crossover and mutation operators. It has to be noted that the genetic representation may differ considerably from the natural form of the parameters of the solutions. Fixed-length and binary-coded strings for representing solutions have dominated GA research.
The power of the GA arises from crossover. Crossover causes a structured, yet randomized exchange of genetic material between solutions, with the possibility that “good” solutions can generate “better” ones.
Crossover occurs only with some probability (the crossover probability or crossover rate). When the solutions are not subjected to crossover, they remain unmodified. Notable crossover techniques include the single-point, the two-points, and the uniform types [7], [9].
Mutation involves the modification of the value of each “gene” of a solution with some probability. The traditional role of mutation in GAs has been that of restoring lost or unexplored genetic material into the population to prevent the premature convergence of GAs to suboptimal solutions.
Apart from selection, crossover, and mutation, various other auxiliary operations are common in GAs. Of these, the scaling mechanism is widely used. Scaling involves a readjustment of fitness values of solutions to sustain a steady selective pressure in the population, and to prevent the premature convergence of the population to suboptimal solutions. The pseudo-code of the GA is below:
Simple genetic algorithm ( )
{
initialize population;
evaluate population;
convergence not achieved
{
scale population fitness;
select solutions for next population;
perform crossover and mutation;
evaluate population;
}
}
3.2 GA Mechanics for Target Selection
Problem
We now describe the details in employing the proposed GA to solve the target selection problem.
3.2.1 Chromosome Coding and Decoding
The GA works with a population of strings, not the parameters themselves. For simplicity and convenience, integer coding is used in this article. With integer coding, the permutation is coded as a vector of targets and the value of the component indicates that to which the target the UAV is assigned. Take UAV=4 and Target=4 as an example. The chromosome represents an assignment list where UAV 4 is assigned to target 1, UAV 1 is assigned to target 2, UAV 3 is assigned to target 3, and UAV 2 is assigned to target 4. It is noted that there are exact (total number of target) genes (component) in chromosome (individual) and their corresponding values are integers between 1 and (total number of UAV). The decoding procedure is the reverse procedure of coding.