|
Post by lawson on Oct 25, 2016 21:08:20 GMT
As far as predicting enemy movements, don't think anything too sophisticated is needed. Based on what I remember reading about the bots for Robocode ages ago, using a weighted average of the target position predicted assuming constant speed (linear predictor) and the target position predicted assuming constant acceleration (quadratic predictor) gives results that are 90% as accurate as the best learning predictors. Note: Robocode is 2D and only includes guns. Extending this to a 3D play field could be done by using the constant speed and constant acceleration predictors to locate and scale an area where the target is likely to be located when shells hit. (say a circle of minimum diameter that covers both predicted target positions) For guns, you'd want to fill this predicted area with shells based on some probability distribution. (say a flat-top, Gaussian, Poisson, a smoothed histogram of actual hits, etc.) For missiles, you'd want to make sure the missile path stayed within the predicted target area. (though, proportional navigation + a target acceleration correction should do as well or better with less calculation) To keep computation load reasonable, how about only running missile guidance at finite set of ranges to target, or at a rate scaled by distance to target? (i.e. make navigation update frequency proportional to "Constant/(distance+1)" or something). If this was combined with missiles fleets staggering impacts, it could cut down on navigation computations a lot. To deal with fuel burn messing up the gimbol and thrust controllers, you need to compensate the controller gains for the change in missile mass and inertia. Just multiplying the gain by the current mass or moment of inertia is usually enough. This works because the physical manipulations or forces applied to the system are divided by the mass or inertia when the physical system converts force to acceleration. (I'd also like to see this done for capital ships, it should settle down crazy RCS and engine gimboling) Similar compensations can be made if the missile controller has a variable update rate. (and controller gains should have real units. I.e. a PID position controller the P gain is [N/m], D gain is [N-s/m], and I gain is [N/s-m] etc.) Marty
|
|
|
Post by nivik on Oct 25, 2016 21:24:13 GMT
I'm going to bow out of this thread until I've done more research into the problem and have a simulation set up to perform testing. If you're in a hurry, you can do it in 2d. Just drawpixel(x,y,color) is all you actually need. I'm not really in a hurry, nor do I know if I'll actually do it at all. If I do, though, I'll probably implement it in NetLogo or some other turtle-based multi-agent simulation tool (maybe SARL? I need an excuse to dig into SARL). I'm well aware of my options, though! I've done quite a bit of multi-agent simulation. My master's thesis relied heavily on it. As far as predicting enemy movements, don't think anything too sophisticated is needed. Based on what I remember reading about the bots for Robocode ages ago, using a weighted average of the target position predicted assuming constant speed (linear predictor) and the target position predicted assuming constant acceleration (quadratic predictor) gives results that are 90% as accurate as the best learning predictors. Note: Robocode is 2D and only includes guns. Extending this to a 3D play field could be done by using the constant speed and constant acceleration predictors to locate and scale an area where the target is likely to be located when shells hit. (say a circle of minimum diameter that covers both predicted target positions) For guns, you'd want to fill this predicted area with shells based on some probability distribution. (say a flat-top, Gaussian, Poisson, a smoothed histogram of actual hits, etc.) For missiles, you'd want to make sure the missile path stayed within the predicted target area. (though, proportional navigation + a target acceleration correction should do as well or better with less calculation) I'm partial to the idea of using APN for one missile, and flocking/swarming for the rest in its group. Flocking can be done by repelling the nearest neighbor and attracting towards the leader's vector, and as per The Algorithm Design Manual 2nd Ed (Skiena), p. 580, nearest-neighbor search on n items can be done in O(n log n) time. We wouldn't have to run the NN finding ever tick, either, so flocking should be scalable to a linear-time operation.To keep computation load reasonable, how about only running missile guidance at finite set of ranges to target, or at a rate scaled by distance to target? (i.e. make navigation update frequency proportional to "Constant/(distance+1)" or something). If this was combined with missiles fleets staggering impacts, it could cut down on navigation computations a lot. Hmm. Scaling the load in this way is an interesting idea. I'm a bit wary of scaling back early in the missile's flight, though, since that's where it costs the least amount of delta-v to alter the missile's trajectory.To deal with fuel burn messing up the gimbol and thrust controllers, you need to compensate the controller gains for the change in missile mass and inertia. Just multiplying the gain by the current mass or moment of inertia is usually enough. This works because the physical manipulations or forces applied to the system are divided by the mass or inertia when the physical system converts force to acceleration. (I'd also like to see this done for capital ships, it should settle down crazy RCS and engine gimboling) Similar compensations can be made if the missile controller has a variable update rate. (and controller gains should have real units. I.e. a PID position controller the P gain is [N/m], D gain is [N-s/m], and I gain is [N/s-m] etc.) I think the Palumbo paper uses a scalar gain factor called the "navigation factor," and I believe that -- in general -- PN/APN/EPN has PID-like behavior (proportional guidance is the main giveaway there).Marty
|
|
|
Post by nivik on Oct 26, 2016 18:35:41 GMT
I'm starting to scrape together an idea for how I'm going to simulate this, and different techniques to test.
For the PN/APN/EPN + flocking technique, I think I've figured out how to do flocking in linear time. Missiles will only repel from their nearest neighbor rather than all missiles in the flock, making the repulsion/attraction component of the algorithm a constant-time operation, and I'll use a kd-tree to determine nearest neighbor. We can construct a kd-tree in O(n log n) time, but if we only do our kd-tree construction and nearest-neighbor search every log2(num_missiles) timesteps, we'll average O(n) time. That means that larger missile swarms may be more prone to fratricidal collisions, but I think the time savings will be worth it.
We can both calculate attractive/repulsive force and perform nearest-neighbor finding using the squared distances between missiles, which eliminates an squared-root operations. That should keep the per-missile time cost of flocking/stationkeeping under the per-missile time cost of running guidance for each missile.
So, every time step we'll attract towards the flight vector of the lead missile, and repel from our current known nearest neighbor, at a cost of O(k) per missile, O(n) overall. Every log2n time steps, we rediscover the nearest neighbors for the entire flock at a cost of O(n log2n) overall for that time step, or O(n) on average.
I think the work can be spread out (at the cost of some accuracy) by doing nearest neighbor search for a few missiles each time step from an older kd-tree, and inserting those missiles' positions relative to a shifting reference point into a new kd-tree. The relative positioning of the missiles would be a bit inaccurate compared to an all-at-once approach, but spreading the work out would reduce stuttering/spiking, so it may be worth it.
I intend to start working on a simulation for this in the next couple of days.
|
|
|
Post by captinjoehenry on Oct 26, 2016 19:18:19 GMT
I'm starting to scrape together an idea for how I'm going to simulate this, and different techniques to test. For the PN/APN/EPN + flocking technique, I think I've figured out how to do flocking in linear time. Missiles will only repel from their nearest neighbor rather than all missiles in the flock, making the repulsion/attraction component of the algorithm a constant-time operation, and I'll use a kd-tree to determine nearest neighbor. We can construct a kd-tree in O(n log n) time, but if we only do our kd-tree construction and nearest-neighbor search every log2(num_missiles) timesteps, we'll average O(n) time. That means that larger missile swarms may be more prone to fratricidal collisions, but I think the time savings will be worth it. We can both calculate attractive/repulsive force and perform nearest-neighbor finding using the squared distances between missiles, which eliminates an squared-root operations. That should keep the per-missile time cost of flocking/stationkeeping under the per-missile time cost of running guidance for each missile. So, every time step we'll attract towards the flight vector of the lead missile, and repel from our current known nearest neighbor, at a cost of O(k) per missile, O(n) overall. Every log 2n time steps, we rediscover the nearest neighbors for the entire flock at a cost of O(n log 2n) overall for that time step, or O(n) on average. I think the work can be spread out (at the cost of some accuracy) by doing nearest neighbor search for a few missiles each time step from an older kd-tree, and inserting those missiles' positions relative to a shifting reference point into a new kd-tree. The relative positioning of the missiles would be a bit inaccurate compared to an all-at-once approach, but spreading the work out would reduce stuttering/spiking, so it may be worth it. I intend to start working on a simulation for this in the next couple of days. One thing that strikes me is the fact that more or less all missiles only have their main drive for maneuvering so they would have to do a main engine burn to perform station keeping and that I would think would throw in a whole horde of issues. Maybe only do it during a correction burn? It should cut down on calculations and it would avoid burning the main engine just to station keep when that'll throw off an intercept
|
|
|
Post by nivik on Oct 26, 2016 19:37:33 GMT
One thing that strikes me is the fact that more or less all missiles only have their main drive for maneuvering so they would have to do a main engine burn to perform station keeping and that I would think would throw in a whole horde of issues. Maybe only do it during a correction burn? It should cut down on calculations and it would avoid burning the main engine just to station keep when that'll throw off an intercept I'm actually starting to think maybe having an assigned position in formation and using a simple PID to maintain that position might be the way to go, honestly. To be honest, most of the algorithms I've been considering involve missiles that're accelerating actively towards the target throughout their terminal flight: I basically treat them like they have solid rocket motors. So in that context, main engine maneuvering isn't a big issue. Even so, I don't worry too much if a missile is ahead or behind of its friends, only if it's laterally/tangentially dispersed. If a missile gets ahead or behind by 100 meters, that's a lot less likely to result in a miss than being laterally off by 100 meters. I'd probably design missiles intended to have a coast phase to have translational RCS thrusters. Alternatively, you could program the missiles to spend the last moments before coast minimizing their relative velocity to one another rather than trying to maintain a specific position in the formation. Once you add in throttle control and translational RCS, missile guidance gets a whole new dimension added. However, right now we don't see a lot of throttle control in CDE, nor do we see it mentioned much in literature, so I've been ignoring it for the most part in my considerations. That may be a mistake.
|
|
|
Post by cuddlefish on Oct 26, 2016 19:41:27 GMT
Well, that might be a pretty solid argument for (once RCS behavior is calmed down a bit) mounting maneuver engines on the missiles. I can't imagine they'd need to do more than 100m/s or so of jostling, and at a decent circa 1.2 km/s out of dime a dozen, sub-kilogram Hydrazine engines (my model is <18Cr and 153 grams <3Cr and 150 grams for 240N at 1.17km/s) you wouldn't be adding an unfeasible amount of 'dead' mass.
Edit: Did a little more material ops on that thruster - I'd left it using UHMWPE for the pump from when I'd had a much higher mass flow, swapping back to standard PE produced dividends.
|
|
|
Post by nivik on Oct 26, 2016 19:48:05 GMT
Well, that might be a pretty solid argument for (once RCS behavior is calmed down a bit) mounting maneuver engines on the missiles. I can't imagine they'd need to do more than 100m/s or so of jostling, and at a decent circa 1.2 km/s out of dime a dozen, sub-kilogram Hydrazine engines (my model is <18Cr and 153 grams for 240N at 1.17km/s) you wouldn't be adding an unfeasible amount of 'dead' mass. I'd definitely like guidance algorithms to use RCS if it's present, but I also wouldn't want it to be a required component to make missile guidance work at all. I think there's a balance to be struck there, and there's an argument to be made for distinguishing between "minimum-time intercept" algorithms (constant and heavy engine usage; useful for KKVs, counter-missiles) and "minimum-error intercept" algorithms (focus on coast phase and precision tweaks to trajectory; useful for flak and nuke saturation attacks).
|
|
|
Post by captinjoehenry on Oct 26, 2016 21:41:10 GMT
Well, that might be a pretty solid argument for (once RCS behavior is calmed down a bit) mounting maneuver engines on the missiles. I can't imagine they'd need to do more than 100m/s or so of jostling, and at a decent circa 1.2 km/s out of dime a dozen, sub-kilogram Hydrazine engines (my model is <18Cr and 153 grams for 240N at 1.17km/s) you wouldn't be adding an unfeasible amount of 'dead' mass. I'd definitely like guidance algorithms to use RCS if it's present, but I also wouldn't want it to be a required component to make missile guidance work at all. I think there's a balance to be struck there, and there's an argument to be made for distinguishing between "minimum-time intercept" algorithms (constant and heavy engine usage; useful for KKVs, counter-missiles) and "minimum-error intercept" algorithms (focus on coast phase and precision tweaks to trajectory; useful for flak and nuke saturation attacks). Well the thing is in most common situation of launching missiles at a fleet in a different orbit there is going to be a coast phase between engaging and hitting your target. I have yet to have any real luck with missiles launched during combat and that honestly seems counter productive given the range advantage missiles grant so at some point you are going to have to shut down the main engine and then you are just coasting unless you have some sort of RCS.
|
|
|
Post by nivik on Oct 26, 2016 23:30:25 GMT
I'd definitely like guidance algorithms to use RCS if it's present, but I also wouldn't want it to be a required component to make missile guidance work at all. I think there's a balance to be struck there, and there's an argument to be made for distinguishing between "minimum-time intercept" algorithms (constant and heavy engine usage; useful for KKVs, counter-missiles) and "minimum-error intercept" algorithms (focus on coast phase and precision tweaks to trajectory; useful for flak and nuke saturation attacks). Well the thing is in most common situation of launching missiles at a fleet in a different orbit there is going to be a coast phase between engaging and hitting your target. I have yet to have any real luck with missiles launched during combat and that honestly seems counter productive given the range advantage missiles grant so at some point you are going to have to shut down the main engine and then you are just coasting unless you have some sort of RCS. Yeah, as I've said, my interest mostly lies in combat guidance. The strategic guidance can be adequately handled by the existing maneuver planning utilized by the AI. I agree that missiles' most notable advantage is as strategic range weapons. However, the sort of missile I'm most interested in are small interceptors to serve as a form of point defense against enemy strategic missiles and drones. That sort of missile will almost exclusively be launched in combat. Counter-missiles are a great way of testing a guidance algorithm due to the demands placed upon them: - They must have a high acceleration and delta-v to engage enemy munitions before they get into range of your capital ships.
- Due to their acceleration, interceptions are going to occur high relative velocities (6 to 14 km/s).
- The intended targets are much smaller than capital ships
- The intended targets have much higher acceleration profiles than capital ships.
- The counter-missile's payload is of limited size and capability.
So a counter missile has to:
- Disable something with the cross-section of a beach ball...
- ...at relative velocities equal to that of the Apollo capsule on re-entry...
- ...using a flak or nuclear warhead the size of a watermelon.
Which is really awesome. That's why I focus so much on this particular type of algorithm.
|
|
|
Post by captinjoehenry on Oct 27, 2016 0:36:08 GMT
Well the thing is in most common situation of launching missiles at a fleet in a different orbit there is going to be a coast phase between engaging and hitting your target. I have yet to have any real luck with missiles launched during combat and that honestly seems counter productive given the range advantage missiles grant so at some point you are going to have to shut down the main engine and then you are just coasting unless you have some sort of RCS. Yeah, as I've said, my interest mostly lies in combat guidance. The strategic guidance can be adequately handled by the existing maneuver planning utilized by the AI. I agree that missiles' most notable advantage is as strategic range weapons. However, the sort of missile I'm most interested in are small interceptors to serve as a form of point defense against enemy strategic missiles and drones. That sort of missile will almost exclusively be launched in combat. Counter-missiles are a great way of testing a guidance algorithm due to the demands placed upon them: - They must have a high acceleration and delta-v to engage enemy munitions before they get into range of your capital ships.
- Due to their acceleration, interceptions are going to occur high relative velocities (6 to 14 km/s).
- The intended targets are much smaller than capital ships
- The intended targets have much higher acceleration profiles than capital ships.
- The counter-missile's payload is of limited size and capability.
So a counter missile has to:
- Disable something with the cross-section of a beach ball...
- ...at relative velocities equal to that of the Apollo capsule on re-entry...
- ...using a flak or nuclear warhead the size of a watermelon.
Which is really awesome. That's why I focus so much on this particular type of algorithm.
That is definitely true but if it is at all possible I want to intercept that scary missile fleet as far from me as possible with some counter missiles reducing the risk of my cap ships unplanned deconstruction. So while it is definitely the most interesting challenge to tackle it honestly isn't the most useful. I mean it's great but without some sort of competent guidance during the pre coast phase of an attack run it isn't going to be hugely useful. Mind you it will work wonders for the terminal approach but that can have some rather large velocity issues due to the enemy maneuvering to avoid your missiles once they enter coasting and if you enter coasting to early the enemy will have enough time to take out your missiles before they can engage so it is definitely an interesting problem that is more generally useful.
|
|
|
Post by nivik on Oct 27, 2016 1:26:21 GMT
That is definitely true but if it is at all possible I want to intercept that scary missile fleet as far from me as possible with some counter missiles reducing the risk of my cap ships unplanned deconstruction. So while it is definitely the most interesting challenge to tackle it honestly isn't the most useful. I mean it's great but without some sort of competent guidance during the pre coast phase of an attack run it isn't going to be hugely useful. Mind you it will work wonders for the terminal approach but that can have some rather large velocity issues due to the enemy maneuvering to avoid your missiles once they enter coasting and if you enter coasting to early the enemy will have enough time to take out your missiles before they can engage so it is definitely an interesting problem that is more generally useful. Are we talking about an orbital mechanics-dominated coast phase on the order of millions of meters, or a "combat map" coast-phase of between 10-50 kilometers?
|
|
|
Post by captinjoehenry on Oct 27, 2016 1:56:07 GMT
That is definitely true but if it is at all possible I want to intercept that scary missile fleet as far from me as possible with some counter missiles reducing the risk of my cap ships unplanned deconstruction. So while it is definitely the most interesting challenge to tackle it honestly isn't the most useful. I mean it's great but without some sort of competent guidance during the pre coast phase of an attack run it isn't going to be hugely useful. Mind you it will work wonders for the terminal approach but that can have some rather large velocity issues due to the enemy maneuvering to avoid your missiles once they enter coasting and if you enter coasting to early the enemy will have enough time to take out your missiles before they can engage so it is definitely an interesting problem that is more generally useful. Are we talking about an orbital mechanics-dominated coast phase on the order of millions of meters, or a "combat map" coast-phase of between 10-50 kilometers? I am talking about coasting once combat is entered. Mostly dealing with the range lasers can engage at being far longer than the distance a missile can travel under power. I assume the player is dealing with the orbital manuvers
|
|
|
Post by zuthal on Oct 27, 2016 4:46:08 GMT
I mean, we wouldn't even need the coast phase if we could a) have engines not burn at max throttle and b) set some details about missile behaviour.
I would say, set a terminal range (i.e. range after which the missile is to accelerate just full tilt), or maybe alternatively a terminal time-to-target, and then, if that isn't too computationally expensive, have the missile before then limit engine thrust such that it will have, when entering terminal range, just enough fuel left that it runs out when it hits the target (and you could also set other behaviours, of course).
|
|
|
Post by nivik on Oct 27, 2016 4:57:24 GMT
Are we talking about an orbital mechanics-dominated coast phase on the order of millions of meters, or a "combat map" coast-phase of between 10-50 kilometers? I am talking about coasting once combat is entered. Mostly dealing with the range lasers can engage at being far longer than the distance a missile can travel under power. I assume the player is dealing with the orbital manuvers 100 kilometers is the current maximum weapon range. Missiles can cover that distance under power and still be quite capable, particularly if their payload is relatively small. Not every missile can, but it's certainly both possible and practical. Here's my current counter-missile. Its powered range envelope is 98 km if it doesn't maneuver: It doesn't get really effective at interceptions until about 75km. However, once it's at that range, it can swat Strikers and Devastators in their coast phase pretty easily: However, that said, I think a power-coast-power algorithm can be done pretty easily. Given that you know how much delta-v you're going to store in reserve, you can calculate approximately what position the missile will be at burnout, what its target-relative velocity will be, and what range it'll have from the target. You'd then calculate what direction you want the missile to be going at that point in time by using the same target-leading algorithm you'd use for a ballistic weapon like a railgun. While in coast, the missile would continuously update its time to closest approach and compare it to its remaining burn time. When its time to closest approach becomes less than its remaining burn time, it then goes back under power for terminal guidance and from that point onwards acts like a normal missile. The only part of this that seems tricky to me is determining the missile's location when it goes into coast. That position and the target lead deflection angle for the ballistic part of the trajectory are very closely tied to one another; closely enough that the first powered phase may need to use simple trajectory projection/prediction as opposed to a PN variant (PN is an negative-feedback error minimization algorithm, and thus doesn't actually project or guarantee any particular flightpath). In my prior experience, target predictive guidance is most effective early in a missile's flight, while PN variants tend to be better later in flight, so this actually could work out quite nicely.
|
|
|
Post by captinjoehenry on Oct 27, 2016 14:49:12 GMT
I am talking about coasting once combat is entered. Mostly dealing with the range lasers can engage at being far longer than the distance a missile can travel under power. I assume the player is dealing with the orbital manuvers 100 kilometers is the current maximum weapon range. Missiles can cover that distance under power and still be quite capable, particularly if their payload is relatively small. Not every missile can, but it's certainly both possible and practical. Here's my current counter-missile. Its powered range envelope is 98 km if it doesn't maneuver: It doesn't get really effective at interceptions until about 75km. However, once it's at that range, it can swat Strikers and Devastators in their coast phase pretty easily: However, that said, I think a power-coast-power algorithm can be done pretty easily. Given that you know how much delta-v you're going to store in reserve, you can calculate approximately what position the missile will be at burnout, what its target-relative velocity will be, and what range it'll have from the target. You'd then calculate what direction you want the missile to be going at that point in time by using the same target-leading algorithm you'd use for a ballistic weapon like a railgun. While in coast, the missile would continuously update its time to closest approach and compare it to its remaining burn time. When its time to closest approach becomes less than its remaining burn time, it then goes back under power for terminal guidance and from that point onwards acts like a normal missile. The only part of this that seems tricky to me is determining the missile's location when it goes into coast. That position and the target lead deflection angle for the ballistic part of the trajectory are very closely tied to one another; closely enough that the first powered phase may need to use simple trajectory projection/prediction as opposed to a PN variant (PN is an negative-feedback error minimization algorithm, and thus doesn't actually project or guarantee any particular flightpath). In my prior experience, target predictive guidance is most effective early in a missile's flight, while PN variants tend to be better later in flight, so this actually could work out quite nicely. Just to be clear I am mostly talking about missiles after performing orbital maneuvers that engage enemy ships which have long range laser weapons. Not can this push the starting range of the engagement out to 250km but the missile in question will have already used at least a bit of its delta v for the orbital maneuvers. I believe it is safe to assume the player will be plotting and carrying out the maneuvers so no need to automate that part. End of the day this is the scenario: After expending some amount of delta v under manual guidance to intercept the missile enters combat with a ship with 250km range lasers. The lasers should be assumed to be effective but they could simply be dummy lasers to push out the starting engagment range. As such most missiles will have to do an initial burn to get close to the target and enter a cruise phase while still quite a distance out. During the cruise phase the enemy will be engaging with counter weapons either lasers or something else and maneuvering to avoid intercept.
|
|