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 S (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:
A 3D lattice 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 10100 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 1016 operations. That means it would take 1084 years to iterate through 10100 vertices.
The Big Bang was 1.4⋅1010 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⋅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:
Some example 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 10100 vertices, we can’t store it. There are only 1080 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 10100 vertices. Iterating through all vertices would take way too long, as we have seen above.
Vector Planning in a Lattice Graph
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 S (where we are) to T (where the sandwich is):
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 10100 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 1016 operations. That means it would take 1084 years to iterate through 10100 vertices.
The Big Bang was 1.4⋅1010 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⋅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 10100 vertices, we can’t store it. There are only 1080 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 10100 vertices. Iterating through all vertices would take way too long, as we have seen above.