Real-Time Target Interception with Multi-Goal A*

Project Overview

Imagine a robot trying to catch a moving target—like a drone intercepting a package in mid-air. The target follows a known path, but the robot must navigate around obstacles to reach it in time. This project builds a real-time motion planner that figures out where to intercept the target while minimizing travel cost (think: energy or distance). The twist? The robot can move in 8 directions (including diagonals), and must plan fast enough to keep up with the target's movement.

Problem Constraints

• Costmap — each cell has a positive integer traversal cost
• Collision threshold — cells at or above threshold are obstacles
• Target trajectory — discrete positions like [(5,6), (5,7), (4,5)]
• Real-time — target moves one step per second
• Grid size — up to 2000×2000 cells

Multi-Goal A* Algorithm

The key insight: we don't just search in 2D space—we search in space and time together. The target is at position (5,6) at time 0, then (5,7) at time 1, and so on. Our planner finds a path where the robot arrives at the same place as the target at the same time. This creates a 3D search space: ⟨X, Y, T⟩ where T is the time step.

Search Strategy

The algorithm explores states in order of estimated total cost. At each state, the robot can move in any of 8 directions, or stay put (useful when waiting is cheaper than a detour):

1int dX[9] = {-1, -1, -1, 0, 0, 1, 1, 1, 0};
2int dY[9] = {-1,  0,  1,-1, 1,-1, 0, 1, 0};
3for (int dir = 0; dir < 9; dir++) {
4  int newX = curr.x + dX[dir];
5  int newY = curr.y + dY[dir];
6  int newT = curr.t + 1;
7  // ... validate and expand
8}

Success! The algorithm finds the robot at the same position as the target at the right time. We then trace back through parent pointers to recover the full path.

Relaxed Mode

Sometimes finding the perfect intercept takes too long. When we're running low on planning time (less than ⅓ remaining), the planner enters relaxed mode—it accepts catching the target early rather than exactly on schedule. Better to catch it a bit early than miss entirely:

1if (curr_time >= (2 * target_steps) / 3) {
2  if (currNode.t <= goal.t) return true;
3} else {
4  if (currNode.t == goal.t) return true;
5}

This is a practical trade-off: we sacrifice guaranteed optimality for reliability. The planner aims for the best solution but gracefully degrades when time is critical.

Backward A* Heuristic

A-Star is only as fast as its heuristic is good. The heuristic estimates 'how far is this state from the goal?'—if the estimate is too low, we waste time exploring bad paths; if it's too high, we might miss the optimal path. We use Backward A-Star: starting from the goal positions, we compute the actual minimum cost to reach them from every cell.

Think of it as flooding outward from the goals, recording the cost to reach each cell. This precomputation happens once, then every A-Star query gets perfect heuristic estimates in O(1) time:

1if (new_cost < heuristicArray[newIndex]) {
2  heuristicArray[newIndex] = new_cost;
3  openSet.push(Node(newX, newY, 0, new_cost, 0));
4}

Storing heuristics in a 1D array provides O(1) lookup while keeping memory manageable for large grids.

Data Structures

With grids up to 2000×2000 cells (4 million cells!), naive data structures would be too slow or consume too much memory. Every lookup and storage operation needed careful optimization.

Node Structure

• x, y, t — position and time step
• g — cost from start
• h — heuristic estimate to goal
• f = g + h — total estimated cost

Memory Optimizations

• 1D arrays for heuristic and g-scores — reduced memory overhead
• Flattened indexing via GETMAPINDEX — O(1) access
• Global path queue — efficient next-move retrieval

Challenges and Trade-offs

The fundamental tension: finding the best path takes time, but the target won't wait. Several techniques helped balance this:

• Relaxation mechanism — accept 'good enough' when time runs short
• Precomputed heuristics — do expensive work once, reuse for every query
• 1D storage — flatten 2D arrays to squeeze out every bit of performance

The result: a planner that delivers optimal paths when possible, but always delivers some valid path even under pressure.

Conclusion

This project tackled a challenging real-time planning problem: intercepting a moving target while navigating obstacles. The solution combines several techniques:

• 3D state space — reason about position and time together
• Backward A-Star — precompute perfect heuristics for fast search
• Relaxed goal checking — graceful degradation under time pressure
• Memory-efficient storage — scale to massive 2000×2000 grids

The implementation shows how to balance competing demands: optimality, speed, and memory—delivering reliable interception even for large, complex environments.