Weapon target assignment problem: Difference between revisions

Revision as of 23:55, 10 June 2011

Revision as of 02:07, 11 June 2011

Line 1:

{{Userspace draft|source=ArticleWizard|date=June 2011}}

The '''weapon target assignment problem''' (WTA) is onea ofclass the fundamentalof [[combinatorial optimization]] problems present in the branchfields of [[Optimization (mathematics)|optimization]] orand [[operations research]] in [[mathematics]]. It consists of finding an optimal assignment of a groupset of weapons of potentially various types to a set of targets. in order to maximize the total expected damage done to the opponent.

InThe its most general form, thebasic problem is as follows:

:There are a number of weapons and a number of targets. The weapons are of type <math> i = 1, \ldots, m </math>. There are <math> W_{i} </math> available weapons of type <math>i</math>. Similarly, there are <math> j = 1, \ldots, n </math> targets, each with a value of <math> V_{j} </math>. Any of the weapons can be assigned to any target. Each weapon type has a certain probability of destroying each target, given by <math> p_{ij} </math>.

:There are a number of ''agents'' and a number of ''tasks''. Any agent can be assigned to perform any task. As opposed to the classic [[assignment problem]] or the [[generalized assignment problem]], more than one ''agent'' can be assigned to each ''task'' and not all ''tasks'' need ''agent'' assigned.

Notice that as opposed to the classic [[assignment problem]] or the [[generalized assignment problem]], more than one ''agent'' (i.e., weapon) can be assigned to each ''task'' (i.e., target) and not all targets are required to have weapons assigned. Thus, we see that the WTA allows one to formulate optimal assignment problems wherein tasks require cooperation among agents. Additionally, it provides the ability to model probabilistic completion of tasks in addition to costs.

== Algorithms and generalizations ==

The weapon target assignment problem is a special case of the [[transportation problem]], which is a special case of the [[minimum cost flow problem]], which in turn is a special case of a [[linear program]]. While it is possible to solve any of these problems using the [[simplex algorithm]], each specialization has more efficient algorithms designed to take advantage of its special structure. If the cost function involves quadratic inequalities it is called the [[quadratic assignment problem]].

==Example==

Both static and dynamic versions of WTA can be considered. In the static case, the weapons are assigned to targets once. The dynamic case involves many rounds of assignment were the state of the system after each exchange of fire (round) in considered in the next round. While the majority of work has been done on the static WTA problem, recently the dynamic WTA problem has received more attention.

==Formal mathematical definition==

The formal definition of the '''weapon target assignment problem''' is often formulated as the following nonlinear [[integer programming]] problem:

:<math>\min \sum_{j = 1}^{n}\left ( V_{j}\prod_{i = 1}^{m}q_{ij}^{x_{ij}} \right )</math>

:Given two sets, ''A'' and ''T'', of equal size, together with a [[weight function]] ''C'' : ''A'' &times; ''T'' &rarr; '''[[real number|R]]'''. Find a [[bijection]] ''f'' : ''A'' &rarr; ''T'' such that the [[cost function]]:

subject to the constraints

:<math>\sum_{j\in T= 1}^{n}x_{ij}=1\leq W_{i}\text{ for }i = 1, \inldots, Am, \, </math>

:<math>x_{ij}\ge 0\text{and integer for }i = 1,j \inldots, m \text{ and }j = A1,T. \ldots, n.</math>

Where the variable <math>x_{ij}</math> represents the assignment of as many weapons of type <math>i</math> to target <math>j</math> and <math>q_{ij}</math> is the probability of survival (<math> 1 - p_{ij} </math>). The first constraint requires that the number of weapons of each type assigned does not exceed the number available. The second constraint is the integral constraint.

::<math>\sum_{a\in A}C(a,f(a))</math>

:is minimized.

Notice that minimizing the expected survival value is the same as maximizing the expected damage.

Usually the weight function is viewed as a square real-valued [[matrix (mathematics)|matrix]] ''C'', so that the cost function is written down as:

== Algorithms and generalizations ==

:<math>\sum_{a\in A}C_{a,f(a)}</math>

The weapon target assignment problem is a special case of the [[transportation problem]], which is a special case of the [[minimum cost flow problem]], which in turn is a special case of a [[linear program]]. While it is possible to solve any of these problems using the [[simplex algorithm]], each specialization has more efficient algorithms designed to take advantage of its special structure. If the cost function involves quadratic inequalities it is called the [[quadratic assignment problem]].

The problem is "linear" because the cost function to be optimized as well as all the constraints contain only linear terms.

==Example==

The problem can be expressed as a standard [[linear program]] with the objective function

A commander has 5 tanks, 2 aircraft, and 1 sea vessel and is told to engage 3 targets with values 5, 10, and 20. Each weapon type has the following success probabilities against each target:

::{| class="wikitable"

:<math>\sum_{i\in A}\sum_{j\in T}C(i,j)x_{ij}</math>

|-

! Weapon Type !! <math> V_{1} = 5 </math> !! <math> V_{2} = 10 </math> !! <math> V_{3} = 20 </math>

subject to the constraints

|-

| Tank || 0.3 || 0.2 || 0.05

:<math>\sum_{j\in T}x_{ij}=1\text{ for }i\in A, \, </math>

|-

| Aircraft || 0.1 || 0.6 || 0.5

:<math>\sum_{i\in A}x_{ij}=1\text{ for }j\in T, \, </math>

|-

| Sea Vessel || 0.4 || 0.5 || 0.4

:<math>x_{ij}\ge 0\text{ for }i,j\in A,T. \, </math>

|}

One feasible solution is to assign the sea vessel and one aircraft to the highest valued target (3). This results in an expected survival value of <math> 30(0.6)(0.5)= 9 </math>. One could then assign the remaining aircraft and 2 tanks to target #2, resulting in expected survival value of <math> 20 (0.4)(0.8)^2 = 2.048 </math>. Finally, the remaining 3 tanks are assigned to target #1 which has an expected survival value of <math> 5 (0.7)^3 = 1.715 </math>. Thus, we have a total expected survival value of <math> 9 + 2.048 + 1.715 = 12.763 </math>.

The variable <math>x_{ij}</math> represents the assignment of agent <math>i</math> to task <math>j</math>, taking value 1 if the assignment is done and 0 otherwise. This formulation allows also fractional variable values, but there is always an optimal solution where the variables take integer values. This is because the constraint matrix is [[totally unimodular]]. The first constraint requires that every agent is assigned to exactly one task, and the second constraint requires that every task is assigned exactly one agent.

==See also==

Line 63 ⟶ 62:

[[Category:Combinatorial optimization]]

[[Category:Matching]]

[[Category:Polynomial-time problems]]

[[Category:Linear programming]]

== References ==

<!--- See http://en.wikipedia.org/wiki/Wikipedia:Footnotes on how to create references using <ref></ref> tags which will then appear here automatically -->

{{Reflist}}

== External links ==

* [http://www.example.com/ example.com]