The Targeting Problem
The fundamental problem to be solved in targeting is to find the targeting angle (Z) at which to shoot, so as to maximize the probability of an impact given the information available (X)
The information that is available (X) is:
- the observed past motions of the enemy robot
- the current state of the enemy robot (position, speed, direction, etc)
Mathematicaly stated, you are attempting to find the angle (Z) for which the estimated probability that the target will be hit at that angle (Y) will be heighest, given the conditional information available (X).
So: Z = max Z' where Z' = P(Y|X)
The probability is essentially one of estimating a conditional probability density, based upon a small and sparse data set - which is a very hard problem to solve well!
There are many possible approaches.
Segmentation algorithms attempt to solve the problem by attempting to directly estimate the conditional probabilities P(Y|X), by simply recording the real statistics as they happen.
In the simplest case, no state information is used, so the estimates are simply P(Y), i.e. the chance that the enemy robot will be struck at any particular angle, as measured so far. This is done by building-up a histogram/table of what angle you should have fired at to hit the enemy robot, each shot. of Clearly, this approach will only work well if the enemy robot's state is unimportant to the firing angle (i.e. if it is stationary, or always moving in a circle at constant speed and distance around your robot).
In more complex approaches, some state information is used. Unfortunatly, in general state information is continuous, which means that it cannot be simply recorded to make a probability table, as can be done in the nieve approach above. To solve this problem, the continuous state information is quantized into seperate states. For example, the movement of the enemy might be quantized into three states (travelling left, staying still, travelling right). Three seperate histograms can then be generated as above, showing hit angle frequencies, when the enemy state was each of the possibilities.
Unfortunatly, this also means that the data set (observed hit angles) is being split into three, and so the data available becomes much more sparse. This reduces the accuracy of the estimated probabilities.
In more extreme cases, one might want to consider a large number of possible enemy states, e.g. two states for enemy direction, three for enemy speed, five for enemy distance, say. This results in 2*3*5=30 histograms to be constructed, which reduces the data in each historgram by a factor of 30 (assuming the data is equally spread). Clearly, this becomes a problem quite quickly as more states are added, especially given the typical data set (~20 shots per round).
Another possible approach would be to attempt to model the problem in a continuous way way, so that the conditional probabilties P(Y|X) can be directly pulled-out.
One way of doing this would be to estimate the probability density function using a guassian mixture model, for example. So, for any given current state (X), the probability of a hit for any given angle (Y) can be pulled-out.
Equally, one might try to use a neural network to model the probability density function. There are various ways of doing this with a neural network; the approach that I would use would be to quantize the hit angles (Y) into a number of seperate levels. For each, I would have a neural network (multi-layer perceptatron) which would target the classification problem - estimating whether there will be a hit or not at that particular network's angle. In theory, the neural networks will converge to estimate the probability density function, thus solving the problem.
Vector quantization is another approach which could be used. The space of state vs hit angle could be considered as a set of vectors (points). A number of "representitive vectors" could then be generated, using k-means, or the classic iterative Vector Quantization algorithm. The "representitive vectors" have a neighbourhood which can be used either for segmentation as above, or the representitive vector's Y's could be used directly as the estimated best Z' (though this may not work well in some cases).
