Chasing after a moving target?

Question

Suppose that you have a world with two players in it the chaser and the target. Suppose that the chaser moves slightly faster than the target. If you are the chaser and you know for a fact that the target is intelligent and trying not to get caught, what would be a good approach for chasing down and ultimately catching the target? (I'm leaving the details of the world a big vague, since I'm hoping to learn a general algorithm or family of techniques for solving this problem rather than optimizing too much on the structure of the world.)

Initially I figured that using something like Dijkstra's algorithm or A* and constantly recomputing the route as the target moved would be a good idea, but there may actually be a better solution that works by taking a more roundabout route so as to corner the target. This could also be modeled as a two-player game that could be solved with minimax or UCT, but the search space could be so huge that it would be completely infeasible to do any reasonable searches.

Has this problem been extensively studied? If so, is there a set of well-known techniques that could be used here?

Thanks!

(My apologies if this is a duplicate; I couldn't seem to find another question like this one, but if there is one I'd be happy to close this one).

Answer 1

Disclaimer : I do not have an extensive knowledge about the literature on this topic. However, I have done a few things like that in the past (namely, tracking the origin of a sound source)

The simple thing when you want to chase a target is to head directly toward it. This is what you did. However, the target will move in the meantime. So the algorithm is optimal only when the target does not move.

The first element of complexity we can have is that the target has a fixed trajectory (that is unknown to the chaser). I am pretty sure that if the trajectory of the target can be any kind of function, then there is no better algorithm than the previous simple one. However, you can always make some reasonable assumptions (the target's velocity can not change too quickly, i.e its acceleration is bounded) that allows you to come up with better algorithms.

So, what I would do as a first move is to implement a Kalman filter. This gives you an estimate of the trajectory of the target. You can make some quick computations, and it will give you the trajectory the chaser should take to intercept it in minimal time.

Now, if you want something fancier (that I do not recommend for the moment), you can try to learn the trajectory of the target (but why would you want that? Kalman filters are often optimal). So you could estimate its trajectory with neural networks, with boosting algorithms, etc... But I honestly don't believe this would be useful.

I said this is the first layer of complexity. The second layer of complexity would be to consider that the target adapts its trajectory according to what the chaser does. This would lead to some adversarial search. It might be interesting, but I am not enough confident in this topic to talk more about it.

Answer 2

Since you're looking for a wide variety of opinions, I'll summarize something I found astonishing from the Wikipedia article on the Sidewinder missile: early heat-seeking missiles tried to steer such that the target would remain in the center of their detector. This meant, in practice, that missiles tried to chase their targets. An important development in the Sidewinder missile is that it tries to stabilize the relative position of the target on its sensors. (Mariners have known for ages that a ship on a constant bearing is actually on a collision course.)

This improved algorithm tends to draw a straight line from the predator to the prey and provides good behavior when the prey tries to evade. (Every curve the prey takes gives the predator another shortcut.)