Weapon target assignment problem: Difference between revisions

Revision as of 23:55, 10 June 2011

Latest revision as of 00:07, 30 April 2024

(54 intermediate revisions by 30 users not shown)

Line 1:

{{UserspaceMore draft|source=ArticleWizardcitations needed|date=JuneApril 20112024}}

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[[weapon]]s 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:

The '''weapon target assignment problem''' is one of the fundamental [[combinatorial optimization]] problems in the branch of [[Optimization (mathematics)|optimization]] or [[operations research]] in [[mathematics]]. It consists of finding an optimal assignment of a group of weapons of potentially various types to a set of targets.

: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>.

In its most general form, the problem is as follows:

:ThereNotice are a number of ''agents'' and athat number of ''tasks''. Any agent can be assigned to perform any task. Asas 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 ''tasks''targets needare ''agent''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.

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 where the state of the system after each exchange of fire (round) is 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.

== 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==

In spite of the name, there are nonmilitary applications of the WTA. The main one is to search for a lost object or person by heterogeneous assets such as dogs, aircraft, walkers, etc. The problem is to assign the assets to a partition of the space in which the object is located to minimize the probability of not finding the object. The "value" of each element of the partition is the probability that the object is located there.

==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_{a\in A}C(a,f(a))</math>

:is minimized.

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

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

:<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>

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

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

== Algorithms and generalizations ==

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

An exact solution can be found using [[branch and bound]] techniques which utilize [[relaxation (approximation)]].<ref>{{cite journal |last1=Andersen |first1=A.C. |last2=Pavlikov |first2=K. |last3=Toffolo |first3=T.A.M. |year=2022 |title=Weapon-Target Assignment Problem: Exact and Approximate Solution Algorithms |journal=Annals of Operations Research |volume=312 |issue=2 |pages=581–606 |doi=10.1007/s10479-022-04525-6|url=https://findresearcher.sdu.dk/ws/files/204132463/WTA.pdf }}</ref> Many [[heuristic algorithm]]s have been proposed which provide near-optimal solutions in [[polynomial time]].<ref>{{cite journal |last1=Ahuja |first1=Ravindra K. |last2=Kumar |first2=Arvind |last3=Jha |first3=Krishna C. |last4=Orlin |first4=James B. |year=2007 |title=Exact and Heuristic Algorithms for the Weapon-Target Assignment Problem |journal=Operations Research |volume=55 |issue=6 |pages=1136–1146 |doi=10.1287/opre.1070.0440}}</ref>

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

==Example==

subject to the constraints

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_{j\in T}x_{ij}=1\text{ for }i\in A, \, </math>

|-

:! Weapon Type !! <math>\sum_{i\in A}x_V_{ij1} =1\text 5 </math> !! <math> V_{2} for= 10 </math> !! <math> V_{3}j\in T,= \,20 </math>

|-

| Tank || 0.3 || 0.2 || 0.5

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

|-

| Aircraft || 0.1 || 0.6 || 0.5

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.

|-

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

|}

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> 20(0.6)(0.5)= 6 </math>. One could then assign the remaining aircraft and 2 tanks to target #2, resulting in expected survival value of <math> 10 (0.4)(0.8)^2 = 2.56 </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> 6 + 2.56 + 1.715 = 10.275 </math>. Note that a better solution can be achieved by assigning 3 tanks to target #1, 2 tanks and sea vessel to target #2 and 2 aircraft to target #3, giving an expected survival value of <math> 5(0.7)^3 +10(0.5)(0.8)^2 + 20(0.5)^2 = 9.915 </math>.

==See also==

*[[Stable marriage problem]]

*[[Auction algorithm]]

*[[Closure problem]]

*[[Generalized assignment problem]]

*[[Linear bottleneck assignment problem]]

*[[Quadratic assignment problem]]

*[[Stable marriage problem]]

== References ==

{{Reflist}}

== Further reading ==

* {{cite book

| authorlink = RainerRavindra BurkardK. Ahuja

| first = RainerRavindra | last = BurkardAhuja

|author2=T. L. Magnanti |author3=J. B. Orlin

| coauthors = M. Dell'Amico, S. Martello

| year = 20091993

| title = AssignmentNetwork ProblemsFlows

| publisher = SIAMPrentice Hall

| isbn = 978-0-89871613-63617549-4 X

}}

[[Category:Combinatorial optimization]]

[[Category:Matching (graph theory)]]

[[Category:Polynomial-timeCombat problemsmodeling]]

[[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]