Weapon target assignment problem: Difference between revisions

Revision as of 02:36, 11 June 2011

Latest revision as of 00:07, 30 April 2024

(47 intermediate revisions by 30 users not shown)

Line 1:

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

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

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

The basic 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>.

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.

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

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

Line 15 ⟶ 16:

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>

subject to the constraints

:<math>\sum_{j = 1}^{n}x_{ij}\leq W_{i}\text{ for }i = 1, \ldots, m, \, </math>

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

:<math>\sum_{j = 1}^{n} x_{ij}\leq W_{i}W_i \text{ for }i = 1, \ldots, m, \, </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>x_{ij}\ge 0\text{ and integer for }i = 1, \ldots, m \text{ and }j = 1, \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.

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

Line 26 ⟶ 29:

== Algorithms and generalizations ==

It has long been known that assignment problems are [[NP-hard]]. Nonetheless, anAn 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 algorithmsalgorithm]]s have been proposed which provide near-optimal solutions in [[polynomial time]] .<ref>{{cite journal |last1=Ahuja, R|first1=Ravindra K. et|last2=Kumar al|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), pp. |pages=1136–1146, 2007|doi=10.1287/opre.1070.0440}}</ref>.

==Example==

Line 34 ⟶ 37:

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

|-

| Tank || 0.3 || 0.2 || 0.055

|-

| Aircraft || 0.1 || 0.6 || 0.5

Line 40 ⟶ 43:

| 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> 3020(0.6)(0.5)= 96 </math>. One could then assign the remaining aircraft and 2 tanks to target #2, resulting in expected survival value of <math> 2010 (0.4)(0.8)^2 = 2.04856 </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> 96 + 2.04856 + 1.715 = 1210.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.763915 </math>.

==See also==

*[[Auction algorithm]]

*[[Closure problem]]

*[[Generalized assignment problem]]

*[[Linear bottleneck assignment problem]]

Line 56 ⟶ 60:

| authorlink = Ravindra K. Ahuja

| first = Ravindra | last = Ahuja

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

| year = 1993

| title = Network Flows

| publisher = Prentice Hall

Line 64 ⟶ 68:

[[Category:Combinatorial optimization]]

[[Category:Matching (graph theory)]]

[[Category:Combat modeling]]