Missile Defense is NP-Complete

General Discussion
1

For those of you planning out your point-defense systems, here’s an interesting read about the “Weapon-Target Assignment Problem” that turned up today (note: it uses AMMs from the current Mideast conflict as an illustrative example).

As far as Aurora is concerned, this means that:

  • If you’re the attacker, it’s better to have many small missiles than a few large missiles (unless you have good ECM, in which case you can make your large missiles deploy decoys)
  • If you’re the defender, then it is critically important to make sure that your missile detection is up to snuff. Decoys are useful here since they aren’t affected by your tracking speed.
1 Like
2

Yes but no. Originally missile combat was fairly binary a you either swamp the target’s point defense or you did no damage. So yes, ‘optimal’ design was size 1-2 missiles fired in overwhelming swarms. Now ECM, decoys, and target randomization allows for leakers to hit, and there’s value to using larger missiles to allow for more penaids and a larger strike.

3

Missiles are in a much better place vs vb6 in my mind. It seems like a variety of strategies are possible including large missiles, or swarms of small ones.

2 Likes
4

The article seems to work with at least one false assumption:

“The product terms in the objective mean that the marginal value of assigning an additional interceptor to a target depends on how many are already assigned there — there are diminishing returns. This couples all assignments together: you cannot evaluate one assignment without knowing the rest. This nonlinearity destroys the decomposition properties that make the linear assignment problem tractable.”

This is - as far as my understanding goes - wrong.

The first interceptor always protects kill chance (1) multiplied by value.
The second interceptor protects [kill chance (2) - kill chance (1)] multiplied by value.

And so on.
That does not change and it allows for a fixed list, that you work down until you have no interceptors left.
Multiple attacks aimed at the same target are treated as if they were attacking different targets that incidentally had the same value.

Edit: It may be better to divide the value of the target by the number of attacks before assigning any defence.

Since I am just a bear of little understanding I may be wrong on this, but until somebody can show me the error of my ways I think the author of the article you linked had a brainfart.

5

As an example of this, I’ve been using size 12 short range missiles in my current campaign and they’ve been pretty devastating. They have ECCM, increased hit chance (don’t remember the name) and 2 decoys. Against most oponents the decoys soak up a good 50 to 70% of the point défense fire and I pretty consistently get 25 to 40% of my missiles to get through, even with relatively modest, 40-60 missiles volleys.

With a 30 damage warhead a few hits tend to be enough to disable or degrade most ships.

With small missiles I don’t think I would have comparable results, as I would have to drop all additionnal modules, and after some time and some research ECCM and increased hit chance become very impactful.

1 Like
6

My current standard missile is size-24, 9 decoys, 25 point warhead, ECCM, ATG, retargeting and onboard sensors. It is useful even in small numbers, although expensive. The best AI counter so far is a size-3 AMM with its own retargeting and dual warheads.

3 Likes
7

Uhm, don’t forget about the Shock Damage. The bigger the single hit is, the better. In most of my recent campaigns I moved away from size-6 missiles in favor of size-24+ and they are AWESOME. NPR ships are usually beefy anyway.

8

The article seems a reasonable coverage of the basics or shooting at incoming missiles, about the level of maths of a competent 18 year old. It does not cover all of the possible issues of real world weapons and engagements and certainly does not cover the rather different assumptions and baselines of Aurora

9

Possibly you overlooked this bit:

In other words, either the incoming missiles are not homogeneous, or our interceptors aren’t. (Or both.)

If our interceptors are homogeneous but the missiles are not, then you can precalculate net PK for each missile for any number of interceptors.
Then you just start assigning interceptors to the next missile in the list, and after each assignment you reinsert the missile into the list based on the marginal PK of the next interceptor assigned to it.
So, it doesn’t matter which interceptor you pick next, because they are all identical.
And each assignment you make is to the missile where it makes the biggest possible difference.
You get an optimal solution.
That’s an O(log n) insertion you have to do O(n) times, so overall it’s O(n log n).
Yay, polynomial time.

But what if our interceptors are not homogeneous, but the missiles are?
In short, it doesn’t work.
(In fact, it seems like a version of the backpack problem.)

You can sort your interceptor list by SSPK, then make an initial pass to assign the best interceptors one missile each, keeping your missile list sorted by current PK.
Now what?
You have a sorted list of interceptors (based on SSPK) and a sorted list of missiles (based on current PK).
It may seem like you can just keep assigning the best remaining interceptor to the missile with the lowest current PK.
That gets you polynomial time, but it doesn’t guarantee an optimal solution.

Consider a simple example with two identical missiles and five interceptors with these SSPK values:
SSPK
.102
.101
.100
.09
.09

You assign the best interceptor to one of the missiles, and the second best to the other missile.
You assign the third interceptor to the best choice available (the .101 PK missile, which becomes .1909).
The fourth gets assigned to the .102 PK missile, which becomes .18282.
The fifth and final gets assigned to that same missile, which gives it a final PK of .2563662
Total expected kills = .4472662.

But that’s not the best possible.
Suppose you assign the third missile to the worse choice for it (the .102 PK missile, which becomes .1918).
Then you assign the fourth and fifth to the other one (.101 → .18191 → .2555381).
Total expected kills = .4473381.

Clearly the “best remaining interceptor to lowest PK missile” algorithm failed us with those last three assignments.
It actually failed us even earlier, with the second assignment.
Suppose instead of splitting our best two interceptors, we assigned them to the same missile, and the remaining three interceptors to the other missile.
Total expected kills = .4474080 (.192698 + .254710).

In short, as the article attempted to delineate, there is no known polynomial time solution that finds the optimal assignment of non-homogeneous interceptors (even if the missiles are homogeneous).

(And since it is NP-Complete, it is extraordinarily unlikely that an undiscovered polynomial time solution exists.)

3 Likes
10

That’s why sane AD doctrines tend to build layered defence and use unified munitions.

3 Likes
11

Thank you for taking the time to spell that out for me.
I did indeed read past that line and so did not allow for there being different types of interceptors and attackers.

With possible damage counted in millions of lives and (insert plausible and mind-boggling number) of Euros/Dollars/Yen it also makes sense to pursue the 1.5 in 10000 difference that your example showed.

That might be a great example to explain what military intelligence is and what it is for.
When you know (or can make a good guess) what a likely attacker’s capabilities are, you can run the numbers in preparation and when it actually happens you might have a pre-solved plan ready. And/or gotten some extra funds for the network if the projections are threatening enough.

I hereby apologize to the author of the article.

12

Bear in mind, of course, that my example was meant to provide a simple demonstration of the math, not to represent a realistic scenario.

In a real world scenario, the marginal difference between a “fast” solution and an optimal one is likely to be far more than in my contrived example.