|
Post by nivik on Oct 20, 2016 22:59:32 GMT
That is awesome! Ok so as I said I don't really know about it that much so thanks for educating me. It definitely is a very interesting thing and it would be great if we could get this in game! Implementation of this particular type of system would be non-trivial. I just want to give fair warning on that front. It was literally one of the options for a semester project for a graduate-level multi-agent systems course, and that's without having to consider performance. Auction algorithms aren't typically used in such a time-critical application, and when they are, they aren't usually competing for CPU time as much as they will be in a computer game. It's a uniquely constrained, extremely fascinating problem. If qswitched actually went this route and made it work, I think he could probably author or co-author a paper on it and get it published. I'd need to do more research into prior work, but in the 30 minutes or so I was digging around earlier, there wasn't much literature about real-time auctions of short-duration tasks on a resource-constrained platform.
|
|
|
Post by 314159 on Oct 21, 2016 12:51:28 GMT
In practice, I'd probably recommend an auction-based system instead, for performance reasons. THE AUCTION ALGORITHM: A DISTRIBUTED RELAXATION METHOD FOR THE ASSIGNMENT PROBLEM is a paper from 1987 which describes a distributed algorithm for task allocation via auction. This has an overall time complexity of O(n*m*log(n*c)), where n is the number of missiles, m is the number of targets, and c is the maximum (integer) "value" of a target, and appears to show a more-or-less linear speedup when distributed over multiple threads/processors. There are other papers which present faster algorithms, but in general auction-based heuristics are well-suited for this sort of problem. Extremely interesting. It's not quite my area of speciality (although it might be close), but still extremely interesting. My only issue is with the mentioned time complexity - we can probably assume that both number of targets and maximum integer is bound by number of missiles [1], meaning overall complexity is less than O(n²*log(n²)). I assume that's only necessary once? If so, you can implement the (abstract) targeting procedure for missiles as such: 1) Missile is launched. 2) Missile chooses a target. 3) Missile pursues target. 4) On change in target state (i.e. flare, breaking apart, ordnance launch, flare burns out, or destruction), repeat target assignment only on relevant targets; return to 3. 5) Hit. In this case, the auction method would solve 2), as would a random assignment. In fact, that's what I personally would recommend to be implemented at first, because it's so easy to do: Each missile, on launch, is randomly assigned one target depending on signature (and possibly dV necessary to intercept). Should they split, repeat that on all of the split-off object. This would, at once, solve both the issue of all missiles homing towards the same target, and flares being overpowered. In this scenario, flares would allow you to avoid a certain percentage of missiles, which'd still be powerful. As for step 3, I'd consider aiming the missile to hit the target, assuming it continuously accelerates at 1/2 or so of its maximum acceleration. Or choose that number randomly too. Anyways, those are just some thoughts I had. [1] Yes, you might fire ten missiles at twenty targets, but at that point runtime is pretty much irrelevant
|
|
|
Post by nivik on Oct 21, 2016 13:17:13 GMT
In practice, I'd probably recommend an auction-based system instead, for performance reasons. THE AUCTION ALGORITHM: A DISTRIBUTED RELAXATION METHOD FOR THE ASSIGNMENT PROBLEM is a paper from 1987 which describes a distributed algorithm for task allocation via auction. This has an overall time complexity of O(n*m*log(n*c)), where n is the number of missiles, m is the number of targets, and c is the maximum (integer) "value" of a target, and appears to show a more-or-less linear speedup when distributed over multiple threads/processors. There are other papers which present faster algorithms, but in general auction-based heuristics are well-suited for this sort of problem. Extremely interesting. It's not quite my area of speciality (although it might be close), but still extremely interesting. My only issue is with the mentioned time complexity - we can probably assume that both number of targets and maximum integer is bound by number of missiles [1], meaning overall complexity is less than O(n²*log(n²)). I assume that's only necessary once? If so, you can implement the (abstract) targeting procedure for missiles as such: 1) Missile is launched. 2) Missile chooses a target. 3) Missile pursues target. 4) On change in target state (i.e. flare, breaking apart, ordnance launch, flare burns out, or destruction), repeat target assignment only on relevant targets; return to 3. 5) Hit. In this case, the auction method would solve 2), as would a random assignment. In fact, that's what I personally would recommend to be implemented at first, because it's so easy to do: Each missile, on launch, is randomly assigned one target depending on signature (and possibly dV necessary to intercept). Should they split, repeat that on all of the split-off object. This would, at once, solve both the issue of all missiles homing towards the same target, and flares being overpowered. In this scenario, flares would allow you to avoid a certain percentage of missiles, which'd still be powerful. As for step 3, I'd consider aiming the missile to hit the target, assuming it continuously accelerates at 1/2 or so of its maximum acceleration. Or choose that number randomly too. Anyways, those are just some thoughts I had. [1] Yes, you might fire ten missiles at twenty targets, but at that point runtime is pretty much irrelevant Step 3 is an entirely different conversation. Look up "proportional navigation," "augmented proportional navigation," and "optimal guidance law" if you like vector mathematics. Long story short, missile guidance in this application sort of needs to consider jerk (change in acceleration). With our missiles, jerk is constant (constant mass flow rate). There's a thread on missile guidance somewhere where I get more into detail on that, and cite a big honking ugly paper that I tweeted to qswitched. (He'd already seen it.) Yeah, target reassignment really only needs to occur when the bipartite graph (IE: # of missiles and targets) changes. In reality, we'd probably only run the algorithm on missiles in the same salvo or which were launched within a given amount of time from one another. You could also price "existing missile allocations" into the target's value, which would cause follow-up missile salvos to take that into account when making their decisions, without actually having to include the prior missiles in the actual auction process. Random assignment is better than no assignment, but at the very least I'd recommend weighting the allocation by assigning each target a value (probably based on heat output), picking the highest value target, allocating a missile to it, subtracting the "damage potential value" of the missile from the target value, and then repeating. You might also add a random noise factor just to prevent every missile from going to the biggest shiniest thing. This would make the missile allocation a bit more intelligent without really costing much in the way of processing time and without the complication of an auction algorithm.
|
|
|
Post by zuthal on Oct 22, 2016 12:25:08 GMT
What I would do for a very simple (downside: naïve, upside: easy to implement and likely light on computational load) target allocation algorithm is the following: Calculate the total heat output (i.e. simply sum up the megawatts) of all targets. The missile chooses a random target out of all of these, with the probably of P_target/P_total, where P_target is the heat output of the target, and P_total is the total heat output of all targets. You should also be able to set, per missile, a minimum heat output. Targets below that heat output will not be considered.
This would have the following effects on flares: -Massively reduce their effectiveness from the current state. -Make more flares equal a larger protective effect -Make flares that have less heat output each than the ship itself still be effective
Parameters to be set per missile design: Cutoff heat output, in MW (with a minimum of, say, 10 kW) Parameters to either be determined automagically or set manually: Update rate. This being the time interval in which the missile target allocation for that missile type is updated. Longer times for this make the missile more likely to waste itself on an already dead enemy, but also makes flares less effective.
|
|
|
Post by 314159 on Oct 24, 2016 21:31:58 GMT
Step 3 is an entirely different conversation. Look up "proportional navigation," "augmented proportional navigation," and "optimal guidance law" if you like vector mathematics. Long story short, missile guidance in this application sort of needs to consider jerk (change in acceleration). With our missiles, jerk is constant (constant mass flow rate). There's a thread on missile guidance somewhere where I get more into detail on that, and cite a big honking ugly paper that I tweeted to qswitched . (He'd already seen it.) Agreed; it's still important for the missile to actually hit, but you can assume it to be independent of the other issues. And I probably had something in mind for the guidance, but I can't remember what exactly. Proportional guidance is, of course, fairly easy and effective. Well, that's what the random allocation will deliver on average. Sure, you don't get guarantees, but for many missiles it holds true - while not assuming missiles can communicate. They might, in practice, but that allocation is completely independent of inter-missile comms. It should also be easy to implement, of course.
|
|
|
Post by zuthal on Oct 25, 2016 1:01:07 GMT
I made a little graph to compare different possible weighting algorithms. In this, x is the target power (in arbitrary units), P is the total power radiated by all targets, and y is the probability of the target being chosen by the missile. One problem with algorithms that are not linear, though: The sum of all weights of all targets will not, generally, be 1.
|
|
|
Post by fallingaggressively on Oct 25, 2016 11:43:53 GMT
So I was testing out missile defense armaments, trying for minimum levels with vanilla tech, and I noticed something odd happen. My ship had accelerated at half a gee and I was moving out of the engagement envelope of the missiles which gave me a side view of the cluster of missiles. The lasers having had a bit of dwell time on the lead missile had turned it a nice yellow color and it looked for all the world like the rest of the pack started to chase the glowing hot lead missile! It certainly wasn't the ship they were gunning for, they missed by a very large margin.
Who needs flares?!
|
|