You want to get to your sandwich:

Well, that’s easy. Apparently we are in some kind of grid world, which is presented to us in the form of a lattice graph, where each vertex represents a specific world state, and the edges tell us how we can traverse the world states. We just do BFS to go from (where we are) to $T$ (where the sandwich is):

BFS search where color represents the search depth.

Ok that works, and it’s also fast. It’s $O (| V | + | E |)$ , where $| V |$ is the number of vertices and $| E |$ is the number of edges... well at least for small graphs it’s fast. What about this graph:

Or what about this graph:

In fact, what about a 100-dimensional lattice graph with a side length of only 10 vertices? We will have $10^{100}$ vertices in this graph.

With side length, I mean the following. This is a 1-dimensional graph of side length 10:

This is a 2-dimensional graph of side length 10:

If you have a 1GHz CPU you can do 1,000,000,000 operations per second. Let’s assume that with BFS we can evaluate 1,000,000,000 vertices per second.

In a year you can do $10^{16}$ operations. That means it would take $10^{84}$ years to iterate through $10^{100}$ vertices.

The Big Bang was $1.4 \cdot 10^{10}$ years ago.

BFS is definitely intractable now. But what the heck, the maximum plan length for optimal plans (plans that get to the sandwich as fast as possible) is only $10 \cdot 100 = 1000$ steps, which doesn't seem that long. That corresponds to going from one corner of a 100-dimensional hypercube of side length 10 to another, where we can only move by 1 unit in any dimension of the cube at a time.

Embedding the Graph

Ok, let's consider our 2D graph again from the beginning such that we can have some visuals, but everything in this section generalizes to lattice graphs of arbitrary dimensions.

You might have noticed that this graph:

clearly screams “I want to be embedded in 2D Euclidean space”. Well actually it is already embedded in 2D Euclidean space, we just did not draw the coordinates yet. Let’s fix that:

OK. The obvious thing to do now is to compute displacement vectors:

If $S$ is the vertex we start at, and $T$ is the vertex we want to get to, we can now get a vector that points from $S$ to $T$ . This is of course super fast. We just need to subtract two integers. In an $n$ -dimensional lattice graph we need $n$ subtractions.

BFS gave us a plan, i.e. a sequence of edges, that we could use to move on the graph from $S$ to $T$ . Now we have a juicy vector, but how can we use the vector to get our sandwich?

Well, one simple algorithm is to just check which edge lines up the most with the displacement vector. We move on the edge and update the displacement vector according to how we moved.

Ok, great. Now we can efficiently move from $S$ to $T$ , by always selecting the closest edge. Also if two edges are equally close, we pick the edge that is counterclockwise of the displacement vector:

Note how we need to update the displacement vector each time we move, otherwise we would always move downward.

Problem solved. Now we efficiently iteratively unroll a plan and get our sandwich. Even in a 100-dimensional graph of side length 10.

Well not really, there are a bunch of problems we need to address to make this work in practice.

Open Problems

If we have the graph with $10^{100}$ vertices, we can’t store it. There are only $10^{80}$ atoms in the universe.
How can we compute the embedding of the lattice graph? We just assumed that we had it. If we don’t assume that we have edges with regular labels this problem is not trivial.
Even if we have infinite memory, we can’t compute the embedding for a lattice graph of $10^{100}$ vertices. Iterating through all vertices would take way too long, as we have seen above.