mathematics//optimization//combinatorial optimization//weapon-target assignment

Weapon-target assignment is the combinatorial problem of sending agents to targets when several agents may go to the same target, each succeeding independently with its own probability, so as to minimize the expected value lost; the name comes from military operations research, where Manne formulated it in 1958, and the same mathematics allocates fire-fighting drones to fires, rescue robots to victims and inspection crews to sites. Ten water-carrying drones and four fires make the book's case: drone \(i\) puts out fire \(j\) with probability \(p_{ij}\) (given distance, water and the fire's size), and each fire threatens a value \(V_j\).

Weapon-target assignment is the combinatorial problem of sending agents to targets when several agents may go to the same target, each succeeding independently with its own probability, so as to minimize the expected value lost; the name comes from military operations research, where Manne formulated it in 1958, and the same mathematics allocates fire-fighting drones to fires, rescue robots to victims and inspection crews to sites. Ten water-carrying drones and four fires make the book's case: drone iii puts out fire jjj with probability pijp_{ij}pij​ (given distance, water and the fire's size), and each fire threatens a value VjV_jVj​.

min⁡x  ∑jVj∏i (1−pij)xijwith∑jxij≤1\min_{x}\; \sum_{j} V_j \prod_{i}\,(1-p_{ij})^{x_{ij}} \quad\text{with}\quad \sum_{j} x_{ij}\le 1xmin​j∑​Vj​i∏​(1−pij​)xij​withj∑​xij​≤1

The product is the probability that every agent sent to target jjj fails, assuming independent failures; times VjV_jVj​ it is the value expected to be lost there. With nnn identical agents of probability ppp the success is 1−(1−p)n1-(1-p)^n1−(1−p)n, and the returns diminish: at p=0.6p=0.6p=0.6 one agent gives 0.60, two 0.84, three 0.94, four 0.97. The second agent adds 0.24, the third less than 0.10. Because of that curvature the problem is NP-hard in general (its decision version was proved NP-complete in 1986).

The practical recipe is greedy first. Assigning each agent, one at a time, where it most reduces the expected loss is optimal when all agents are identical and very good in many other cases; a local search then improves it for as long as time allows, and an exact solver is worth running when there are tens of agents, much at stake and minutes to spare.

Exact answers come from branch and bound or from a reformulation as an integer linear program, which commercial solvers finish in seconds or minutes for tens of agents. The greedy rule works because the objective has diminishing returns, the property studied in submodular function.

Deciding everything at once is often the wrong frame. Sending one agent, looking, and sending the next only if the first failed reaches the same probability of success with fewer agents on average, at the price of time (sequential allocation).

The formula is only as good as its independence assumption. Drones that share a wind, a wrong estimate of where the fire is or a software fault fail together, and then sending more buys far less than 1−(1−p)n1-(1-p)^n1−(1−p)n promises (common-mode failure).