Finding an optimal solution for targeting ships in a naval engagement
I have an engagement between two fleets of n and m ships, each ship in the friendly fleet with its own with salvo damage, and each ship in the enemy fleet with its own hp amount. The goal of this algorithm is to find the optimal solution (if such solution exists) to how to assign targets to your ships, (ex: ship 1 in my fleet targets ship 3 in your fleet) in such a way that the salvo will maximize the amount of damage done to the enemy fleet.
Important. By damage, I mean the amount of damage/hp value of an enemy ship destroyed. If an enemy ship has 100hp and deals 20dmg, its "value" is 100/20 = 5. So destroying that ship incurs a score of 5. And lastly, only the score of destroyed ships is taken into account. If it is impossible to destroy any ships with a single salvo, the score will then include the damaged ships.
I have attempted a greedy method, an iterative improvement method, and a hill ascent method too, but none of them are capable of reaching an optimal solution. I have also tried another method, where a large amount of randomized target choice sets are made, and evaluated, and the best one is picked out of al of them. This is the one that has produced the best results, but it is incredibly innefficient and almost never produces the optimal result.
I believe there has to be a way of calculating an optimal solution that does not require checking every single possible targeting choice, but I cannot find a way of doing so. It also seems like this problem is like a weird form of the multiple knapsack problem. With the knapsacks being the enemy hp pools, and the items the dmg values of the shots. Except this time the last item placed into a knapsack can exceed the size limit of the knapsac but only the fraction of the item's value that fits into the kanpsack is useful.
Even if it is not a solution to the problem, any thoughts or help are very much appreciated!
Linear programming will do the job perfectly here. In this case, the decision variables are integers, so we are dealing with ILP. Here is a small description on how to model your problem as a linear program.
Data: F_dmg[n] // an array containing the damage of friendly ships E_hp[m] // an array containing the hp points of the ennemy ships M // constant, the highest hp among all ships V[m] // the 'value' of ennemy ships Decision variables: X[n][m] // a matrix of booleans (0 or 1) // X[i][j] = 1 if the ship i attacks the ship j, 0 otherwise Dmg[m] // an array of integer, representing the total damage taken by each ennemy ship IsAlive[m] // an array of booleans, representing the fact that the ship is destroyed or not (0 if dead, 1 if alive) Constraints: // a friend ship can attack at most one ennemy ship for all i in 1..n, sum(j in 1..m) X[i][j] <= 1 // the damage sustained by a ship cannot exceed its hp for all j in 1..m, sum(i in 1..n) Dmg[m] <= E_hp[j] // the damage sustained by a ship has to be coherent with the attacks it receives for all j in 1..m, sum(i in 1..n) Dmg[j] <= X[i][j] * F_dmg[i] // a ship is destroyed if the damage sustained is equal to its hp for all j in 1..m, M * IsAlive[j] >= E_hp[j] - Dmg[j] Objective function maximize sum(j in 1..m) (1 - IsAlive[j]) * V[j]
Write that in OPL, feed it to an ILP solver and you'll get an optimal answer real fast if your input is not absolutely gigantic.
[PDF] optimal air defense strategies for a naval task group a , We develop solution methods for the air defense problem of a naval task group in this Keywords: Air Defense, Naval Task Group, Formation, Weapon Target Allocation. Problem 5.3.1 Best Engagement Construction (BEC) Algorithm (SAP) since we intend to locate ships in predefined sectors on the surface. The escort tree has been cannibalized to buff CVs. Gives a nice +20% naval targeting for CVs. Same remark than for the base strike doctrine. Very strong submarine tree, the best one for an overall total of +55% detection and +50% raiding. However, again, if your enemy has all its convoys escorted, the subs will be useless.
This either is, or is very similar to, the Weapon Target Assignment Problem.
Unfortunately that problem is NP-hard, and according to the 2003 paper "Exact and Heuristic Algorithms for the Weapon Target Assignment Problem" (Ahuja, Kumar et al.), even instances as small as 20 weapons and 20 targets can't be solved to provable optimality. (I only read the abstract.)
[PDF] Navy Force Structure and Shipbuilding Plans, Policy of the United States on minimum number of battle force ships. So we started on a new path for that last fall, and what we're finding We cannot wait to identify solutions to our mine countermeasure needs, and must make regional aggressors have optimized their forces to target, naval forces will� Tracking the Target. Sensing the presence of a target is an essential first step to the solution of the fire control problem. To successfully engage the target and solve the problem, updates as to the target's position and its velocity relative to the weapon system must be known or estimated continuously.
Must me quite similar to a depth first algorithm that will try and find the optimal route it will then return the optimal route for each ship and return. An array of targets that each ship should target
The Arsenal Ship And The U.S. Navy, Precision warfare should increase the target kill rate while reducing the number of of technologies which enhance the ability to locate, identify, and track targets in greater Forward-deployed Arsenal Ships are the Navy's solution. Arsenal Ship is "best defined as providing multifunctional support to the land battle in its� Ship Hull Design. Design ships with better flows! CAESES ® enables you to build robust parametric ship models with smarter shape control. It is the leading software solution for naval architects that are interested in CFD-based hull optimization – to create better flows around their designed vessels.
[PDF] optimal air defense strategies for a naval task group a thesis , We develop solution methods for the air defense problem of a naval task group in this Keywords: Air Defense, Naval Task Group, Formation, Weapon Target Allocation. Problem 5.3.1 Best Engagement Construction (BEC) Algorithm (SAP) since we intend to locate ships in predefined sectors on the surface. Finding an optimal solution for targeting ships in a naval engagement Hot Network Questions Can I charge for flying video editing as a private pilot in US?
U.S. Carrier Group tactics, The USS Abraham Lincoln battle group (a fleet of warships centered around the aircraft carrier USS Abraham Lincoln) during the RIMPAC exercises on 20 June 2000. Naval tactics play a crucial role in modern battles and wars. The presence of land, changing The need to obtain a targeting solution has to be balanced against the� Solutions for key ship types We offer fully integrated energy, handling and operational solutions with powerful benefits. Our vessel products reduce cost, maximise performance and address lifecycle challenges – from initial ideas and planning, right through to long-term asset management.
Left-click on the intended target, it is then highlighted by a small circle drawn on the water around it. An information window is shown in the upper right corner of the display. The info window will indicate the nationality and type of ship, plus any other ships accompanying it as a supporting fleet.
- how many n and m are we talking about? how much is max health and max damage?
- What he wants to optimize is not the damage though, its the score. And you only get score if the damage sustained by a ship exceeds or equals its hp
- Just saw that, editing the answer. Thanks for the notice :)
- No problem. Was going to suggest the same depending on constraints
IsAlivebeing boolean makes this an Integer LP, right? Otherwise looks good :)
- Thanks, I could 'smell' the NP-hardness of the problem from its description, but I would never have guessed the name.
- @m.raynal: I remember hearing of some weapon-themed NP-hard problem years ago, and then when this question appeared featuring weapons... "I wonder if that's that same problem..." ;)
- side note: I don't know if it's only on my machine, but it looks like the LaTeX compiler did rebel against the authors of the paper ... sum symbols are flying and piling on top of each other all around the paper :-)
- @m.raynal: Same here, I thought maybe my poor laptop needed a reboot!