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

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.)

Answer 2

I think you are mixing 2 separate issues into the same problem which can most likely be isolated.

1. Pathfinding / Collision Avoidance
2. Calculating intended destination

Pathfinding / Collision Avoidance

This has been extensively studied, many specific factors come into play when deciding on how to implement this...

• How dynamic is the movement of the objects (RTS style low resolution grid or racing game)?
• How congested is the scene going to get with dynamic entities (Decide if you need to take into account crowd movements to optimize path)?

The result of these questions will most likely lead you to some A* incarnation specific to the situation it will be used in, and result in the ability for the chaser to have a target point in the world, and move towards it in the most efficient way.

Calculating intended destination

Now that an object can say "I want to go here, give me the best path", we can independantly look at chasing a target.

From homing rocket algorithms I have implemented, I used the following:

• Estimate time to reach target (using some heuristic, possibly just path to object)
• Extrapolate the position of the target by the time it will take for chaser to reach it (along is current velocity/path)
• Compare estimated time to target with actual time to future position, if not within some tolerance, offset estimate and iterate process again until satisfied
• Set chasers target as extrapolated position

This will be slow to start with, but some easy optimizations can be made by adjusting the tolerance of time to target estimates, and not recalculating the entire pathing tree every frame.

You can also detect changes in target velocity / path to trigger a recalculation

Answer 3

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 4

A quick search for "AI chasing" turned up this algorithm:

http://www.peachpit.com/articles/article.aspx?p=102090&seqNum=4

Which looks to be pretty good. Depending on how effecient, quickly you want to catch the target, there are other algorithms you can look at.

Try googling for Flocking algorithms, and I'm pretty sure I have seem some "dynamic" A* algorithms (but I can't seem to find them right this minute) that might also be useful.

Also, Neural Networks might work ok here, assuming there aren't too many obstacles in your world. Something with maybe 2 inputs (distance to target, and delta radians to face target) and 2 outputs (desired speed, and desired heading)