Brandon Pelfrey Mathematics and Computational Curiosities

Drunk Robots On a Grid

Robots? Grids? The Problem

One day during lunch, some co-workers and I were wondering about random walks and I thought of a silly problem:

Imagine two robots on an \( n \times n \) grid. The robots’ starting positions are given. At each step through time, each robot will uniformly-random move to an adjacent cell with probability \(\alpha\), and otherwise stays put with probability \((1 - \alpha)\). What’s the expected time until the two robots collide?

Background: Robot Position Over Time

First, consider what happens over time to just one of these robots.

To facilitate discussion, we can logically number each cell in the grid going from \(1\) to \(n\) and let the vector \( \mathbf p_t \) be the probability distribution of the robot’s position at time \(t\) (The \(i\)th component of the vector is the likelihood of finding the robot in the \(i\)th cell).

In the interior of the grid, the robot has a \(\frac \alpha 4\) chance of going in either of the four cardinal directions, and likewise, it has a \(\frac \alpha 3\) and \(\frac \alpha 2\) chance of moving to a neighboring cell when on the edge and corner of the grid, respectively. If we let \( \mathbf N_i \) be the set of neighboring cells adjacent to grid cell \(i\), then we can easily express the probability of finding the robot in any other cell after \(k\) time steps by the following simple procedure:

  1. Assemble a vector \( \mathbf p_0 \) which contains, for each grid cell, the probability that the robot can be found in that grid cell at the start. If the robot is known with certainty to be starting in a particular cell, then this vector would simply a \(1\) for that cell, and \(0\) for all others.
  2. Construct the transition matrix \( \mathbf\pi_{ij} \) which encodes the probability that a robot in cell \(i\) would be found in cell \(j\) after \(1\) time step.
  3. If we multiply our \( \mathbf p_0 \) by \( \mathbf \pi_{ij} \) then we would have a new vector which tells us the probabilities of finding our robot in all the other grid cells one time step later.
  4. In general, we can find the distribution after \(k\) steps by applying \(\mathbf \pi\) \(k\) times:

\[ \mathbf p_k = (\mathbf \pi \underset{k \; times}{\dots} \mathbf \pi) \mathbf p_0 = \mathbf \pi^k \mathbf p_0 \]

As an example, if we have a \(63 \times 63\) cell grid and place the robot at the center of the grid, the probability of finding the robot in any particular spot on the grid diffuses over time:

[animation code]

It’s natural to ask what the steady-state distribution looks like (\( \lim_{k \rightarrow \infty} \mathbf \pi^k\)). As you’d expect from a simple MC like this, you can just look at the dominant eigenvector of \(\mathbf \pi\). Not surprisingly, scipy confirms it’s a constant-valued function; That is, over sufficiently long time horizon, the robot is equally likely to be found in any cell.

Fun Connection to Diffusion Process

The fact that this looks like diffusion isn’t surprising. Assuming \(\alpha = 1\) for a moment (It doesn’t fundamentally affect the observation here):

which are (to first order) approximations of the first time derivative on the left hand side, and a scalar multiple of the Laplacian

which is exactly a diffusion process. (Left as a fun exercise to the reader, you can even make the probabilities of heading one direction vs. another vary over space and you’ll just get anisotropic diffusion like you’d expect.)

Well this is silly. Just simulate it, right?

By golly, we have formulas. Let’s just simulate a bunch of paths for the two robots and directly calculate what the expected time is, right? Hmm, no.

At each point in time, each robot can be thought of as making \(4\) moves at a time. Because we have two robots, there are \(8\) choices per time step, meaning the number of paths to be considered over \(n\) time steps explodes very quickly, \(\Theta(8^n)\). I could make some allusions to grains of sand and stars in the universe, but I think you get the idea: this brute-force approach is untenable.

Back to Two Robots

We still can’t solve the expected time until the robots first collide, but on the way, we can answer an easier question:

Given the same dynamics as the original problem, and the robot starting positions \( \mathbf p_a\) and \( \mathbf p_b\), how many times would we expect the robots to collide in the first \(n\) time steps?

First is finding out what the chances are they collide on any given time step, \(k\).

We already know that the position distribution of a single robot starting at cell \(a\) in the grid, \(\mathbf p_a\) is given by \( \mathbf \pi^k \mathbf p_a\). At every point in the grid, \(i\), the two robots have a probability \( \mathbf {p_a}_i \mathbf {p_b}_i \) of both simultaneously being at that grid cell on time step \(k\).

We want to consider a collision on any cell, and so we be happy with any one of these events taking place:

which is just an inner product over two vectors

So this is the probability that the two robots collided in some cell (we don’t care which) on the \(k\)th time step. The question asks how many we’d expect in the first \(n\) steps, so we’ll need to sum over the first \(n\) time steps

The matrices, \( \mathbf Q_k = (\mathbf \pi^k)^\top (\mathbf \pi^k) \), are given by the recurrence

Given two robots initialized at \((10, \frac n 2)\) and \((n - 10, \frac n 2)\) (Inset slightly from the left and right edges, vertically centered), the joint distribution of finding the two colliding in any given cell evolves like the following animation.

It makes sense that the distribution elongates horizontally: these are the shortest paths on the grid. Believe it or not, even on this small grid, in the 3600 time steps visualized in the animation, you would still expect to never see a single collision between the two robots.

Fun side note: Using diffusion as a mechanism for finding shortest paths has been known for some time. It was recently the star of a cool paper by Keenan Crane