Catch Me If You Can: Planning to Intercept a Moving Target

Course 16-782 Planning & Decision Making

Timeline October 2021

Result Target caught on 5 of 6 maps

Stack C++ · MATLAB MEX

A grid cost map with the target trajectory in magenta and the planned robot path in green — The whole problem in one picture. The target walks the magenta path. The robot starts somewhere else on the map and has to plan the green path so that it arrives at a point on that magenta line before the target passes it.

The problem

A robot has to catch a target moving along a known trajectory through a cost map. Chasing the target directly is the obvious approach and the wrong one: following where it is means always arriving where it was. The robot needs to pick a point on the target's future trajectory that it can reach before the target does, go there, and wait.

That reframes the problem usefully. Instead of a moving goal, we need to choose a single static goal cell subject to a timing constraint, and then run a standard search to it.

Precomputing the goal

My approach precomputes a goal position: a cell in the target's trajectory that the robot can intercept in time, accounting for both the cost of getting to the cell and the cost of waiting there once it arrives.

To select it, a forward Dijkstra search runs from the robot's initial position. That gives the cost of reaching every point on the target's trajectory, and the number of time steps it takes to get there. Keeping only the cells the robot can reach in time, I sort the candidates in a priority queue by the cost of getting to the cell plus the cost of waiting in it, and take the minimum. That cell becomes the goal handed to A*.

time_buffer ← 1                      /* accounts for pre-computation time */
for i in target_steps:
    h_val ← HEURISTIC_DF[target_index]
    time  ← ROBOT_STEPS[target_index]
    if time + time_buffer ≤ i:
        g_val ← h_val + (i - time)   /* cost of getting there + waiting */
        TARGET_G_VAL.push(cell)
return TARGET_G_VAL.top()

The heuristic

With the goal chosen, a 2D backward Dijkstra runs from the goal outward, storing each cell's cost-to-goal in a hash map. Those values become the heuristic for the A* search. The direction matters: running Dijkstra backward from the goal means its g-values are precisely the true cost-to-go for every cell, which makes the heuristic both admissible and consistent, so A* keeps its optimality guarantee.

It is worth noting what this costs. Computing a perfect heuristic by exhaustive search is more expensive than the A* it accelerates, which would be self-defeating in general. Here it pays off because the same Dijkstra expansion is doing double duty: the forward pass chooses the goal, the backward pass guides the search to it.

Weighted A*

The path itself comes from 2D weighted A*, with the weight epsilon set to 100 across all results. A high weight inflates the heuristic and makes the search greedier, trading a bounded amount of optimality for a large speedup, which matters when the whole plan has to be produced before the target gets away. Backtracking happens inside the search, populating the path, and each call to the planner pops the next position off it.

I also wrote a 3D A* over (x, y, time), which is the more principled formulation since it reasons about where the robot can be when, but I could not get it working and the planner does not use it.

Results

The planner caught the target on maps 1 through 4, and on map 6. Map 5 is the interesting failure.

Map   Method     Heuristic     Caught   Time   Moves   Path cost   Precompute (s)
   2D A*      2D Dijkstra    yes    2641    2639      2641       0.997
   2D A*      2D Dijkstra    yes    4673    1235   4457697       2.702
   2D A*      2D Dijkstra    yes     242     241       242       0.214
   2D A*      2D Dijkstra    yes     380     266       380       0.254
   2D A*      2D Dijkstra     no     182     182       182       0.021
   Greedy     --             yes     150     150      5050        --
   2D A*      Euclidean      yes     141       0      2820       0.025
   2D A*      Dijkstra       yes     141       0      2820       0.039

Map 2 robot path and target trajectory — Map 2, the most expensive path at a cost of 4.46 million.

Map 3 robot path and target trajectory — Map 3, caught in 242 steps.

Map 4 robot path and target trajectory — Map 4, caught in 380.

On map 5, weighted A* with the Dijkstra heuristic failed to catch the target, while a plain greedy search succeeded. The trade is visible in the numbers: greedy caught it in 150 moves at a path cost of 5050, against A*'s 182 moves at a cost of 182. A* found the far cheaper path and still lost, because on this map cheapness and speed point in different directions.

Map 5 using weighted A star, which fails to catch the target — Map 5 with 2D A*: cheap path, target missed.

Map 5 using greedy search, which catches the target — Map 5 with greedy search: 33x the cost, target caught.

Map 6 makes the opposite point. A Euclidean heuristic and the Dijkstra heuristic produce identical results, 141 steps at a cost of 2820, but Euclidean gets there with less than two-thirds of the precompute time. When the map is open enough that straight-line distance is a good estimate, paying for an exact heuristic buys nothing.

Map 6 solved with a Euclidean heuristic — Map 6, where a Euclidean heuristic matches Dijkstra's result for less precompute.

The timing caveat

One honest detail from the write-up. The goal computation includes a time buffer to account for its own precompute time, which I set to 5 seconds in the submitted code because of uncertainty about the machine it would be graded on. That buffer is a real trade: increase it and the chosen goal becomes less optimal and the path more expensive, but the robot is guaranteed to arrive before the target. On map 1, with no buffer, a precompute exceeding 1.1 seconds would make the robot too late.

The results in the table were generated with the buffer at zero, for the most optimal cost.

A* Weighted A* Dijkstra Heuristic Search Grid Planning C++

Code on GitHub ↗