|
Post by nivik on Oct 7, 2016 13:45:32 GMT
I guess my perspective is skewed because I play a lot of realistic flight sims and recreate ICBM flight profiles in KSP, but in my mind missiles fly primarily ballistic trajectories and have an initial powered phase followed by a long coast period. Even in the atmosphere but especially in space, missiles can coast and continue to be highly effective long, long after they've burnt out. Air to air missiles in real life like the AIM-120D only burn for 3-7 seconds, yet fly 90+ miles to kill targets. ICBMs are even more extreme examples of this, performing one long, aggressive burn at 45° to enter a high orbit with a vertical semi-major axis before proceeding to coast many minutes to apogee before deploying their submunitions which again fall for several minutes back to earth before reentering the atmosphere. We don't have the advantage of flight (and therefore unpowered steering) that we get with an atmosphere, but we do avoid the disadvantage of drag which also comes with atmospheres. This depends. If the target doesn't change its behavior, its position can be predicted with a high degree of accuracy, and coasting is effective. For capital ships, I think a missile could coast for a while after burnout and be accurate (if the missile took into account that its acceleration would stop at a certain time and "lead the shot" as a result). However, targets that are actively maneuvering with significant amounts of acceleration -- like missiles and drones -- are difficult to predict, since their movement is dictated by their behavior instead of physics. I will note that after burnout, missiles are going to be much easier to intercept by countermissiles and kinetic point defense due to their predictability. Right now kinetic point defense is a bit last-ditch, and countermissiles aren't terribly accurate, but it's something to keep in mind. The way I'd handle this (as a layman) with an eye to reducing the number of pathfinds follows - may be stuff you've tried before, may be useless, but felt like typing it out It seems like the goal with a Flak missile barrage is to get a certain density of shot across the entire uncertainty in your target's position post detonation. How many missiles are used to attain this would purely be a factor of how many are needed, and how redundant you want to be against point defense. The most efficient way to allocate those missiles is going to be in a formation - allowing each missile to "cover" a specific section of the enemy possibility space with a payload, without inefficient doubling causing gaps, as they might easily do if they're all path-finding independently. Nukes can be used in a similar way - spacing the missiles to ensure something gets within lethal distance no matter how they maneuver. Nukes also have another 'hidden' plus of formation coordination - if they sync their detonation time, they will have the best odds of achieving multiple simultaneous bursts rather than the first burst killing the bunch. So, where does this lead my brain? It seems like the pathfinding should be structured around 'Walls' of missiles. Each Wall pathfinds as a group (I think we can assume sensor fusion of the various missiles, given we don't actually have sensor modules in game), trying to place the wall center such that the entire uncertainty space (based on the known G potential of the target's drive - I assume that good recon would be able to amass a database the gunners can use when arming the warheads, given lack of space stealth and ability to measure the exhaust plumes of ships) is covered by killzone of the warheads (either within Proxy distance of a nuke, or covered by a certain density of fragmentation at the desired closing speed), with the spacing of the 'Wall' being malleable to cover the entire projected space + some safety margin as thickly as possible with the number of missiles allotted. This means that the individual behavior of missiles should be able to be pared entirely down to station-keeping within the shifting formation vector, and any formation adjustments that need to be done as missiles are lost to PD. As a novice rather than someone who knows their shit - it seems like that stationkeeping would be less burdensome than target tracking? If that's the case, letting you replace the N target finds for a salvo with 1 target find and N stationkeeps would be a serious profit, if it can be done. Thoughts from the people who actually know what they are talking about? Hmm. I'm not a missile guidance expert, but I'm an MSCS in AI, so I'll pretend like I'm an authority. :3 The core problem is more or less the same -- the missile is here, and wants to be over there -- but because the missiles have very similar flight profiles to one another, the difference in relative position, velocity, acceleration, and jerk between the movement of a formation waypoint and an enemy target is huge. Missiles will normally be tens of meters off from their waypoint and their velocity vector off by a couple degrees and meters per second, instead of 20 kilometers and -2,000 m/s. Position in a formation is also much less crucial: it doesn't matter if you're ahead or behind a couple missile-lengths. As such, your formation-keeping algorithm can be a much simpler one. It won't be optimal, and missiles will be off a little bit, but it doesn't really matter. Similarly, if the lead missile needs to make a significant vector change, it could override the other missiles and command them to all mirror its maneuver exactly, then release them to fall back into formation when it's back on course. That would help limit missiles going wide off of a turn, then slamming back through the formation as they overshoot getting back on course. Really, what I think you'd want is a swarming or flocking algorithm. A classic example is Boids: en.wikipedia.org/wiki/Boids. This uses three basic rules to ensure that you get a cohesive group, without the missiles having to predict anything at all: collision avoidance, an attraction towards the center of the swarm, and an repulsion from all other members of the swarm. This naturally results in a well-distributed formation, without any one missile having to be told where its place is. They figure it out on their own without too much thinking, which is exactly what you want in this situation. This would have to be modified to ensure the missiles are super attracted to the "smart" missile in the pack, or otherwise actually try to hit the target, but it's the approach that immediately comes to my mind when I see this sort of problem. Edit: that said, I believe the naive version of the Boids algorithm is going to require N 2 computations because of the repulsive effects between each missile and the other missiles in the swarm has to be calculated. You'd need to figure out how to bring that down to something more linear.
|
|
|
Post by Crazy Tom on Oct 7, 2016 17:57:25 GMT
All this talk of missile guidance reminded me of this:
|
|
|
Post by nivik on Oct 7, 2016 18:34:44 GMT
All this talk of missile guidance reminded me of this: <snip> ...*sigh* I understood that far too well for my own good.
|
|
|
Post by ross128 on Oct 7, 2016 18:35:42 GMT
One rather simple option that would change a lot, is the ability to simply set a different aim point and terminal behavior.
The current algorithm seems to aim slightly behind the center of the target's heat signature (which is usually the center of the radiator section), then pitch sharply toward it in the last couple of seconds. This usually results in detonating either right behind the engine or squarely between the radiators, depending on how nimble the missile is and how good its approach was. It also results in frequently detonating with the missile turned nearly on its side.
While it's a pretty okay guidance solution for nukes, since detonating right behind the engine can get very good results from those, it doesn't work as well for kinetic missiles because the warhead can end up pointed away from the target when it goes off.
A simple solution for KKVs would be to aim slightly ahead of the center of radiance (possibly an option set in the remote control module), and prioritize impacting normal to the hull over hitting a specific spot. It would hopefully use pretty much the same lightweight guidance algorithm, just with an offset point of aim and a terminal stage that ignores the aim point in favor of improving the angle of impact.
Though calculating the offset and the potential angle of impact might be intensive on their own, I don't know.
One thing that is funny is a well-tuned gyrojet has an optimum range band where it experiences none of these guidance problems, the missiles just drill right through the center of the radiator section flawlessly. Maybe it has to do with the cannon aiming at the center of mass, and this offsets the missiles' tendency to trail the target?
|
|
|
Post by nivik on Oct 7, 2016 20:53:10 GMT
One rather simple option that would change a lot, is the ability to simply set a different aim point and terminal behavior. The current algorithm seems to aim slightly behind the center of the target's heat signature (which is usually the center of the radiator section), then pitch sharply toward it in the last couple of seconds. This usually results in detonating either right behind the engine or squarely between the radiators, depending on how nimble the missile is and how good its approach was. It also results in frequently detonating with the missile turned nearly on its side. While it's a pretty okay guidance solution for nukes, since detonating right behind the engine can get very good results from those, it doesn't work as well for kinetic missiles because the warhead can end up pointed away from the target when it goes off. A simple solution for KKVs would be to aim slightly ahead of the center of radiance (possibly an option set in the remote control module), and prioritize impacting normal to the hull over hitting a specific spot. It would hopefully use pretty much the same lightweight guidance algorithm, just with an offset point of aim and a terminal stage that ignores the aim point in favor of improving the angle of impact. Though calculating the offset and the potential angle of impact might be intensive on their own, I don't know. One thing that is funny is a well-tuned gyrojet has an optimum range band where it experiences none of these guidance problems, the missiles just drill right through the center of the radiator section flawlessly. Maybe it has to do with the cannon aiming at the center of mass, and this offsets the missiles' tendency to trail the target? The current algorithm is aiming directly at the heat signature; if you set up a sandbox scenario against a space station, it's easier to see. I think the missiles just don't consider acceleration: they aim at where the ship will be if it coasts, not where it'll be under power. That inevitably causes it to spend most of its time burning to intercept a point well behind where it aught to...particularly because the missile is probably considering relative velocity, which means it's likely ignoring its own -- very considerable -- acceleration. A good test for this would be to test a high acceleration missile and a low acceleration missile at different ranges so they're going around the same speed when they get to the target. My gut instinct is that the low-acceleration missile will be noticeably more accurate against slow-moving or tumbling targets. The cannon lead prediction algorithm, however, probably does consider relative acceleration (or at least angular acceleration), because it only has to do it once in a while for the gazillion projectiles it spews..and it has to in order to have a prayer of hitting a maneuvering target at range. So your gyrojet gets a good, solid kick in the direction it AUGHT to go, and probably lacks the acceleration to significantly alter its course before it's close enough where the guidance algorithm does more good than harm.
|
|
|
Post by ross128 on Oct 7, 2016 21:05:23 GMT
Well, my observation was based on lobbing missiles at a station. So there isn't any acceleration to consider. Whenever it approached the station from the rear or the front, it would just go for the center (which makes sense, from that angle the radiators form a ring) but whenever it approached from the sides, it had a strong tendency to consistently aim at a point of empty space just "behind" the station, where the engines would have been if it was a ship, and then make a last-second correction toward the radiators just before impact. That behavior was puzzling, I couldn't really think of any reason for it to do that other than an attempt to hit the station's (non-existant) engines.
It is true though that the difference is much more pronounced against targets with engines though. Against those missiles will often fail at the last-second correction and miss wildly.
|
|
|
Post by nivik on Oct 7, 2016 23:07:22 GMT
Well, my observation was based on lobbing missiles at a station. So there isn't any acceleration to consider. Whenever it approached the station from the rear or the front, it would just go for the center (which makes sense, from that angle the radiators form a ring) but whenever it approached from the sides, it had a strong tendency to consistently aim at a point of empty space just "behind" the station, where the engines would have been if it was a ship, and then make a last-second correction toward the radiators just before impact. That behavior was puzzling, I couldn't really think of any reason for it to do that other than an attempt to hit the station's (non-existant) engines. It is true though that the difference is much more pronounced against targets with engines though. Against those missiles will often fail at the last-second correction and miss wildly. Hmm. Maybe it has to do with the missile's own acceleration? Or something about the geometry of the situation, if basic proportional navigation is being used. Or maybe the aimpoint really is off somehow. My mistake!
|
|
|
Post by ross128 on Oct 7, 2016 23:13:14 GMT
I suppose it's possible that a lot of intercepts just happen to start with a lot of velocity in that direction for some reason. I definitely don't have any solid explanation for why it behaves like that, I can only speculate.
|
|
|
Post by geraldmonroe on Oct 10, 2016 20:15:41 GMT
I have actually implemented several better missile guidance algorithms than the one you see in game. None of them are enabled in game for one reason, and that is performance. 100+ missiles running a root finding algorithm for an intercept course will bring the game to a crawl. The current algorithm is naive, does not use numerical integration at all, and it still is somewhat of a performance problem (on my machine) with 100+ missiles. I'm still looking into better algorithms that don't kill performance (such as possibly trying to treat a fleet of missiles as "one big missile" to save on calculation time), and I hope to have something better by the next major patch. Hey, thanks for weighing in on this! You definitely have a point about performance. Hmm. Maybe a sort of leader/follower arrangement? Missiles within N distance (or time?) of a "leader" are slaved to it, and only attempt to maintain their assigned position in the formation, while the leader takes care of guidance. Loss of the leader could either have an in-game effect of disrupting the formation's guidance, or leadership could automatically be taken up by the missile in that formation that's closest to the target. There'd have to be some consideration for how missiles tend to be "trickled" out when fired in the middle of a tactical engagement, though. You could have a "leader" set waypoints along its path of travel (maybe with waypoint position being target-relative), and for a certain timeframe afterwards, any follow-up shots would follow those waypoints. By making waypoints target-relative, that could allow some basic compensation for changing conditions in the short term. Probably not effective for countermissiles or anti-drone operations, but I think it may work for large and slow targets where the "solution" is less likely to degrade significantly in a given timeframe. It's an interesting control problem. I'll keep thinking about it. Fusing optimal guidance with swarming behavior seems like a good off-the-cuff solution, but I like the idea of path planning where the path can be heuristically updated to compensate for changing conditions...particularly considering that follow up shots either hitting or missing (how far, and by how much) are additional data points that could be leveraged to get better path updates. I have an idea. Wonder if it's workable. First, solve for the missile intercept, which in this game you do while the game is paused. Yeah, missiles would be treated as fleets as the difference in gravity/orbits between different missiles in a fleet is negligible. Once the missile is on it's intercept, have it mirror any moves made by the target. Target accelerates +x +10 m/s? So does the missile. The missile isn't physically modeled in the overall game world. Instead, you have a model where the dV cost to the missile is subtracted from each counter-move it makes, with a higher cost if no rocket motor is immediately available along the axis the target is maneuvering. As long as you make dV cost have a little bit of a premium (say 10%), it's physically correct. You really could build a missile that does exactly what it does in the game. As long as the missile doesn't run out of dV and the target doesn't do any last ditch dodging along an axis the missile doesn't have immediately available thrust along, at the instant the missile is on terminal approach, and none of the defenses and countermeasures work, the missile hits. You model the graphics of the missile using a fairly simple interpolation between the missile and the target, it's fake but human eyes won't be able to tell that the course isn't correct.
|
|
|
Post by ross128 on Oct 10, 2016 22:00:53 GMT
We can't abstract it to that level because we don't just need to know if the missile hits or not. For one thing, the vast majority of missiles have proximity fuses so they don't actually "hit" in the traditional sense: they get close enough to trigger the prox fuse, detonate, and then either radiate heat in a sphere (nukes), launch one or more projectiles in the direction they were facing (flak/EFP missiles), or both (EFP nukes).
So we need to know where the missile is and what direction it's facing when it detonates, and if it does actually impact the hull we need to know what the angle and velocity of the impact were. So physically modelling the missile the way we do now is pretty necessary, especially if we want to preserve missile classes that are built on emergent properties of that simulation.
I think mainly we just need a few different options for targeting behaviors. The current missile behavior works pretty well for proximity nukes, but other weapons have different priorities that would be better served by different targeting parameters.
|
|
|
Post by nivik on Oct 11, 2016 2:07:03 GMT
I have an idea. Wonder if it's workable. First, solve for the missile intercept, which in this game you do while the game is paused. Yeah, missiles would be treated as fleets as the difference in gravity/orbits between different missiles in a fleet is negligible. Once the missile is on it's intercept, have it mirror any moves made by the target. Target accelerates +x +10 m/s? So does the missile. The missile isn't physically modeled in the overall game world. Instead, you have a model where the dV cost to the missile is subtracted from each counter-move it makes, with a higher cost if no rocket motor is immediately available along the axis the target is maneuvering. As long as you make dV cost have a little bit of a premium (say 10%), it's physically correct. You really could build a missile that does exactly what it does in the game. As long as the missile doesn't run out of dV and the target doesn't do any last ditch dodging along an axis the missile doesn't have immediately available thrust along, at the instant the missile is on terminal approach, and none of the defenses and countermeasures work, the missile hits. You model the graphics of the missile using a fairly simple interpolation between the missile and the target, it's fake but human eyes won't be able to tell that the course isn't correct. The main issue with that is that the missile's handling characteristics are far different from that of the target. If the target speeds up 10m/s, the missiles don't need to speed up 10m/s. They need to change their heading by whatever amount allows them to intercept the target 10 meters * remaining-time-to-impact. In order to accurately calculate their time-to-impact, missiles need to consider their position, their current velocity, how their velocity is changing due to their acceleration, and how their acceleration is changing due to the missile becoming lighter as it burns propellant. So any accurate guidance algorithm is a third-order polynomial equation; anything else will drastically overestimate their time-to-impact, which will result in the missile overshooting the target for most of its flight, then making a hard turn at the end to try to correct its error. Finding the roots to a cubic equation is a pain in the butt: you can see the cubic formula here. Similarly, this paper shows that the EPN algorithm involves cubic equations, and the optimal guidance law uses at least one exponential function. Solving these is computationally expensive, unfortunately, which is the root cause of the slowdown problem qswitched mentioned. One possible solution is very similar to yours, though, except that a "leader missile" solves the equation once, and the other missiles mirror what it does, because the flight profiles of the missiles are very similar to one another, so the errors introduced by copycatting are much lower.
|
|
|
Post by normalitybytes on Oct 11, 2016 17:35:13 GMT
How about a swarm approach? One - or a few - missiles use a somewhat more sophisticated intercept algorithm. Possibly, depending on salvo size, you seperate the salvo into subswarms, each guided by one missile, each swarm using a different - or differently parameterized - algorithm. All other missiles in the (sub-)swarm do only what is necessary to maintain station relative to their neighbors, possibly with the station distance as a function of target distance. Just aligning on two vectors should take very little computing power. Thus, you have your salvo-as-one-big-missile approach without significant loss in precision.
Switchover should be implemented, of course, in case the swarm leader is incapacitated.
|
|
|
Post by titanuranus on Oct 11, 2016 18:47:08 GMT
I have actually implemented several better missile guidance algorithms than the one you see in game. None of them are enabled in game for one reason, and that is performance. 100+ missiles running a root finding algorithm for an intercept course will bring the game to a crawl. The current algorithm is naive, does not use numerical integration at all, and it still is somewhat of a performance problem (on my machine) with 100+ missiles. I'm still looking into better algorithms that don't kill performance (such as possibly trying to treat a fleet of missiles as "one big missile" to save on calculation time), and I hope to have something better by the next major patch. If you wanted to, a possible (silly) kludge could be to tie missile guidance to the type of remote control (standard uses current guidance, simple lead, advanced lead, good enough to differentiate between ships and flares, ect), and then limit the number of missiles using advanced guidance in any particular fleet (not stored, just launched).
|
|
|
Post by nivik on Oct 11, 2016 21:52:02 GMT
How about a swarm approach? One - or a few - missiles use a somewhat more sophisticated intercept algorithm. Possibly, depending on salvo size, you seperate the salvo into subswarms, each guided by one missile, each swarm using a different - or differently parameterized - algorithm. All other missiles in the (sub-)swarm do only what is necessary to maintain station relative to their neighbors, possibly with the station distance as a function of target distance. Just aligning on two vectors should take very little computing power. Thus, you have your salvo-as-one-big-missile approach without significant loss in precision. Switchover should be implemented, of course, in case the swarm leader is incapacitated. I think that's a solid approach, and is one of the solutions I'd be leaning towards, personally. In particular, this paper -- which I've only skimmed so far -- explains a swarming algorithm approach that's near-linear, where the polynomial nature of the attractive/repulsive force calculations per-agent are mitigated by limiting each missile's search space through some implementation of nearest-neighbor search. The paper also has the benefit of showing that the clustering can be done in a massively parallel fashion with GPU acceleration, which means that, if necessary, very large numbers of swarming missiles' AI could be handled...at the cost of increased code complexity and impact to maintainability. I doubt the trade-off would be worth it, particularly given the latency of moving data between main memory and the GPU every physics tick, but it shows that it's possible. I'd have to do an actual computational analysis to determine the actual difference in computation time between per-missile optimal guidance and swarming, but with a low number of neighbors considered -- two is probably enough to avoid collisions -- combined with optimizations to avoid recalculating neighbors for every missile every tick...I think you could see a reduction in computational load of between 50% and 75% fairly easily. That's a SWAG, and I don't guarantee it, but at that point it's an N=3 potential fields problem, which is basically just "addition" with some control logic around it. Edit: I re-read this and realize I went a bit into left field. I'm happy to answer any questions folks may have! I have a bit of a passion for AI and I don't get to do it in my day job, so it'd seriously be my pleasure.
|
|
|
Post by normalitybytes on Oct 12, 2016 0:49:23 GMT
I'd have to do an actual computational analysis to determine the actual difference in computation time between per-missile optimal guidance and swarming, but with a low number of neighbors considered -- two is probably enough to avoid collisions -- combined with optimizations to avoid recalculating neighbors for every missile every tick...I think you could see a reduction in computational load of between 50% and 75% fairly easily. That's a SWAG, and I don't guarantee it, but at that point it's an N=3 potential fields problem, which is basically just "addition" with some control logic around it. Edit: I re-read this and realize I went a bit into left field. I'm happy to answer any questions folks may have! I have a bit of a passion for AI and I don't get to do it in my day job, so it'd seriously be my pleasure. Collisions shouldn't be much of a problem in any case, as long as missiles don't trigger each other's warheads. Collisions would happen at very low relative velocities and - worst case - would throw the missiles off course.
|
|