# How to maximize hits on a moving target

I have a problem which can be boiled down to the following simplification: An irregular target is moving on a 2d plane in a non-random but unknown way. I have a number of snapshots of the target in the 2d plane, so I have N samples of the targets location. The movement is back-and-forth / circular in nature, so it does not move across the plane but on the plane.

I want to shoot the plane in such a way that I hit >99% of the targets surface, while minimizing misses while the target is moving and minimizing the amount of hits needed. I cannot observe the target while shooting it, so I have to base my hits on previous observations. I also don't know the starting or current position of the target, just the location of the plane it moves upon.

The assumption is that the N samples I have will sufficiently 'predict' the possible locations of the target in the future (it's all I have). I also assume I can hit the plane with 100% accuracy.

One of the methods I came up with is create a probability distribution of the targets location over time, then hitting the plane with an intensity related to the probability the target is at that location. This way I cannot ensure however I hit enough of the targets surface. I can simulate hits, misses, and target coverage, but I don't know how to calculate these.

Are there any other ways I can calculate this? Simulate it? Are there any real-world examples that already do something similar?

I have an analogy to further simplify it: I have a video snapshot of a moving target, and I want to paint the target using a paintball gun. I don't want to hit the background, and I have to shoot at it blindly. My paintball gun has a 100% accuracy.

Thanks for any suggestions!

A lot of control systems use a Kalman filter to solve this problem. On the Wikipedia page, they even use the example of tracking objects in a video.

• Sounds great, but this (as far as I've read so far) uses some form of tracking to create a dynamic system. In my problem I cannot observe the target, so I don't know in which state the target is at the moment. Because of this I am looking for a static distribution of my 'hit density', as if I fire all the paintball bullets at once. This can be used in a more sophisticated system though! – Kamiel Wanrooij Nov 27 '11 at 20:08
• Are your $n$ samples of the form $(x_1,t_1),\dots,(x_n,t_n)$, where $x_i$ is the 2D position at time $t_i$? Or do you just have a set of position observations with unknown times? In the second case, you're probably correct to build up a distribution and then sample from that distribution using a rejection sampling method like the Ziggurat algorithm. – dls Nov 27 '11 at 23:11
• We do have the times, but there is no distinct start time. So when I observe 100 moving targets for a few minutes, there is no way to relate t1 of the first target to t1 of the second target. And also no way to determine t1 of my actual target when shooting it. So as far as I know I have to treat the time dimension as unusable... – Kamiel Wanrooij Nov 28 '11 at 16:43

There are many approaches for this, the most trivial one would be to average the movement over the last few samples and assume the target will continue to move in that direction with the same average speed.

Of course this will be wrong if a target is near to some border of the plane or just doesn't continue to move like this.

Take for example a target that always moves to the left for a few seconds and then to the right again, obviously there is a pattern but how to tell a program to spot this pattern?

The solution is a machine learning approach. You could use Bayesian Learning for Neural Networks to predict the position. There is a lot to read and many refinements to do, so you have to know how much work you want to invest.

• Oh, I forgot to mention, it moves around an unknown center point. So the movement is not linear but more wobbly circular / back and forth. Machine learning would be cool but I cannot make adjustments in real time since the current position is never know. I cannot hit and observe the target at the same time. – Kamiel Wanrooij Nov 27 '11 at 14:57