Setup
Here’s the setup: I have an $N$ x $N$ grid of tiles, and a list of $M$ agents that need to move across the grid. Each agent has its own start tile $S(a)$, end tile $E(a)$, and an exact number of steps $D(a)$ it must make. Each step consists of a one-tile move horizontally, vertically, or staying in place. For each agent, $D(a)$ is usually much larger than the Manhattan distance between $S(a)$ and $E(a)$, so the path the agent takes is not necessarily a straight line from $S(a)$ to $E(a)$. Furthermore, the sum of all $D(a)$ is expected to be much larger than $N$ x $N$, so every tile will be used at least once. Agent paths are allowed to intersect with other paths and with themselves, and the number of agents on a tile at any given time doesn’t matter.
The Problem
I would like to find paths for each agent that begin at $S(a)$, end at $E(a)$, and are exactly $D(a)$ steps long, with the goal of minimizing the maximum number of times any given tile is used. More formally, given an agent path $P_0 \ldots P_n$, let $C(P, t)$ be the number of times tile $t$ appears in $P$, and let $A(t)$ be the sum of $C(P, t)$ over all agent paths. I would like to find agent paths that minimize the maximum $A(t)$ over all tiles $t$.
My intuition tells me that this problem is almost certainly NP hard, so I’m looking for some kind of approximation or heuristic.
First Attempt
My first stab at solving this was to find each path sequentially. For each agent, I create a 3-dimensional $N$ x $N$ x $D(a)$ search space, then use A* search to find the min-cost path from $[S(a), 0]$ to $[E(a), D(a)]$. The cost of each node in the search is the number of times that tile has been used by previous paths. Then, once the path is found, I add to the cost of each tile used, and proceed to the next agent. Of course, this leads to the problem that while the last agent path will be pretty good, the first agent path will be essentially random because the grid is yet totally unused. So, I just loop this process a few times; once the last path is computed and the tile costs updated, I loop back to the first path, subtract from the grid the costs that agent contributed, then recompute that path and add the new costs in. After 3 or 4 loops, I converge on a pretty reasonable solution.
But I’m hoping there’s a better idea out there. Any ideas or references to similar problems that I could read up on would be very welcome.
