How can I find the shortest path between 100 moving targets? (Live demo included.)

Question

Background

This picture illustrates the problem:

I can control the red circle. The targets are the blue triangles. The black arrows indicate the direction that the targets will move.

I want to collect all targets in the minimum number of steps.

Each turn I must move 1 step either left/right/up or down.

Each turn the targets will also move 1 step according to the directions shown on the board.

Demo

I've put up a playable demo of the problem here on Google appengine.

I would be very interested if anyone can beat the target score as this would show that my current algorithm is suboptimal. (A congratulations message should be printed if you manage this!)

Problem

My current algorithm scales really badly with the number of targets. The time goes up exponentially and for 16 fish it is already several seconds.

I would like to compute the answer for board sizes of 32*32 and with 100 moving targets.

Question

What is an efficient algorithm (ideally in Javascript) for computing the minimum number of steps to collect all targets?

What I've tried

My current approach is based on memoisation but it is very slow and I don't know whether it will always generate the best solution.

I solve the subproblem of "what is the minimum number of steps to collect a given set of targets and end up at a particular target?".

The subproblem is solved recursively by examining each choice for the previous target to have visited. I assume that it is always optimal to collect the previous subset of targets as quickly as possible and then move from the position you ended up to the current target as quickly as possible (although I don't know whether this is a valid assumption).

This results in n*2^n states to be computed which grows very rapidly.

The current code is shown below:

var DX=[1,0,-1,0];
var DY=[0,1,0,-1]; 

// Return the location of the given fish at time t
function getPt(fish,t) {
  var i;
  var x=pts[fish][0];
  var y=pts[fish][1];
  for(i=0;i<t;i++) {
    var b=board[x][y];
    x+=DX[b];
    y+=DY[b];
  }
  return [x,y];
}

// Return the number of steps to track down the given fish
// Work by iterating and selecting first time when Manhattan distance matches time
function fastest_route(peng,dest) {
  var myx=peng[0];
  var myy=peng[1];
  var x=dest[0];
  var y=dest[1];
  var t=0;
  while ((Math.abs(x-myx)+Math.abs(y-myy))!=t) {
    var b=board[x][y];
    x+=DX[b];
    y+=DY[b];
    t+=1;
  }
  return t;
}

// Try to compute the shortest path to reach each fish and a certain subset of the others
// key is current fish followed by N bits of bitmask
// value is shortest time
function computeTarget(start_x,start_y) {
  cache={};
  // Compute the shortest steps to have visited all fish in bitmask
  // and with the last visit being to the fish with index equal to last
  function go(bitmask,last) {
    var i;
    var best=100000000;
    var key=(last<<num_fish)+bitmask;
    if (key in cache) {
      return cache[key];
    }
    // Consider all previous positions
    bitmask -= 1<<last;
    if (bitmask==0) {
      best = fastest_route([start_x,start_y],pts[last]);
    } else {
      for(i=0;i<pts.length;i++) {
        var bit = 1<<i;
        if (bitmask&bit) {
          var s = go(bitmask,i);   // least cost if our previous fish was i
          s+=fastest_route(getPt(i,s),getPt(last,s));
          if (s<best) best=s;
        }
      }
    }
    cache[key]=best;
    return best;
  }
  var t = 100000000;
  for(var i=0;i<pts.length;i++) {
    t = Math.min(t,go((1<<pts.length)-1,i));
  }
  return t;
}

What I've considered

Some options that I've wondered about are:

1. Caching of intermediate results. The distance calculation repeats a lot of simulation and intermediate results could be cached.
   However, I don't think this would stop it having exponential complexity.

2. An A* search algorithm although it is not clear to me what an appropriate admissible heuristic would be and how effective this would be in practice.

3. Investigating good algorithms for the travelling salesman problem and see if they apply to this problem.

4. Trying to prove that the problem is NP-hard and hence unreasonable to be seeking an optimal answer for it.

Answer 1

Have you searched the literature? I found these papers which seems to analyse your problem:

• "Tracking moving targets and the non- stationary traveling salesman problem": http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.85.9940

• "The moving-target traveling salesman problem": http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.57.6403

UPDATE 1:

The above two papers seems to concentrate on linear movement for the euclidian metric.

Answer 2

Greedy method

One approach suggested in the comments is to go to the closest target first.

I've put up a version of the demo which includes the cost calculated via this greedy method here.

The code is:

function greedyMethod(start_x,start_y) {
  var still_to_visit = (1<<pts.length)-1;
  var pt=[start_x,start_y];
  var s=0;
  while (still_to_visit) {
    var besti=-1;
    var bestc=0;
    for(i=0;i<pts.length;i++) {
      var bit = 1<<i;
      if (still_to_visit&bit) {
        c = fastest_route(pt,getPt(i,s));
        if (besti<0 || c<bestc) {
          besti = i;
          bestc = c;
        }
      }
    }
    s+=c;
    still_to_visit -= 1<<besti;
    pt=getPt(besti,s);
  }
  return s;
}

For 10 targets it is around twice the optimal distance, but sometimes much more (e.g. *4) and occasionally even hits the optimum.

This approach is very efficient so I can afford some cycles to improve the answer.

Next I'm considering using ant colony methods to see if they can explore the solution space effectively.

Ant colony method

An Ant colony method seems to work remarkable well for this problem. The link in this answer now compares the results when using both greedy and ant colony method.

The idea is that ants choose their route probabilistically based on the current level of pheromone. After every 10 trials, we deposit additional pheromone along the shortest trail they found.

function antMethod(start_x,start_y) {
  // First establish a baseline based on greedy
  var L = greedyMethod(start_x,start_y);
  var n = pts.length;
  var m = 10; // number of ants
  var numrepeats = 100;
  var alpha = 0.1;
  var q = 0.9;
  var t0 = 1/(n*L);

  pheromone=new Array(n+1); // entry n used for starting position
  for(i=0;i<=n;i++) {
    pheromone[i] = new Array(n);
    for(j=0;j<n;j++)
      pheromone[i][j] = t0; 
  }

  h = new Array(n);
  overallBest=10000000;
  for(repeat=0;repeat<numrepeats;repeat++) {
    for(ant=0;ant<m;ant++) {
      route = new Array(n);
      var still_to_visit = (1<<n)-1;
      var pt=[start_x,start_y];
      var s=0;
      var last=n;
      var step=0;
      while (still_to_visit) {
        var besti=-1;
        var bestc=0;
        var totalh=0;
        for(i=0;i<pts.length;i++) {
          var bit = 1<<i;
          if (still_to_visit&bit) {
            c = pheromone[last][i]/(1+fastest_route(pt,getPt(i,s)));
            h[i] = c;
            totalh += h[i];
            if (besti<0 || c>bestc) {
              besti = i;
              bestc = c;
            }
          }
        }
        if (Math.random()>0.9) {
          thresh = totalh*Math.random();
          for(i=0;i<pts.length;i++) {
            var bit = 1<<i;
            if (still_to_visit&bit) {
              thresh -= h[i];
              if (thresh<0) {
                besti=i;
                break;
              }
            }
          }
        }
        s += fastest_route(pt,getPt(besti,s));
        still_to_visit -= 1<<besti;
        pt=getPt(besti,s);
        route[step]=besti;
        step++;
        pheromone[last][besti] = (1-alpha) * pheromone[last][besti] + alpha*t0;
        last = besti;
      }
      if (ant==0 || s<bestantscore) {
        bestroute=route;
        bestantscore = s;
      }
    }
    last = n;
    var d = 1/(1+bestantscore);
    for(i=0;i<n;i++) {
      var besti = bestroute[i];
      pheromone[last][besti] = (1-alpha) * pheromone[last][besti] + alpha*d;
      last = besti;
    }
    overallBest = Math.min(overallBest,bestantscore);
  }
  return overallBest;
}

Results

This ant colony method using 100 repeats of 10 ants is still very fast (37ms for 16 targets compared to 3700ms for the exhaustive search) and seems very accurate.

The table below shows the results for 10 trials using 16 targets:

   Greedy   Ant     Optimal
   46       29      29
   91       38      37
  103       30      30
   86       29      29
   75       26      22
  182       38      36
  120       31      28
  106       38      30
   93       30      30
  129       39      38

The ant method seems significantly better than greedy and often very close to optimal.