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):

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 ${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:

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 ${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.

[faul_sname]

Easier question: Let’s say you have a single node in this graph of ${10}^{100}$ nodes. You want to figure out where that single node should be embedded in your 100-dimensional space, but you only care about its embedding location relative to a few specific other nodes.

You have the following affordances:

1. List the edges that originate at a node. The edges will always be returned in the same order for the same node, but the order is not necessarily the same for different nodes (i.e. the first edge may point along the 57th axis for one node and in the 22nd axis for a different node)

2. Given an edge, retrieve the node at the far end of that edge

3. Compare two nodes to see if they are the same node as each other

That is to say, if you have the following problem definition

import random

class Node:
    key = None
    edges = None

    def __init__(self):
        self.edges = []

class Edge:
    _src = None
    _get_dst = None
    _dst = None

    def __init__(self, src, get_dst):
        self._src = src
        self._get_dst = get_dst

    def get_dst(self):
        if self._dst is None:
            self._dst = self._get_dst()
        return self._dst

class Graph:
    def __init__(self, axis_length, n_dims):
        self.axis_length = axis_length
        self.n_dims = n_dims
        self._nodes = {}
        self._next_node_id = 1

    def get_node_at(self, coords):
        axis_order = list(range(self.n_dims))
        random.shuffle(axis_order)
        if coords not in self._nodes:
            node = Node()
            node.key = self._next_node_id
            self._next_node_id += 1
            for axis in axis_order:
                if coords[axis] == 0:
                    continue
                dst_coords = list(coords)
                dst_coords[axis] -= 1
                dst_coords = tuple(dst_coords)
                def make_edge(dst_coords):
                    def get_dst():
                        return self.get_node_at(list(coords))
                    return Edge(node, lambda: self.get_node_at(dst_coords))
                edge = make_edge(dst_coords)
                node.edges.append(edge)
            self._nodes[coords] = node
        return self._nodes[coords]

    def get_random_node(self):
        return self.get_node_at(tuple([random.randint(0, self.axis_length-1) for _ in range(self.n_dims)]))

and you want a function which will take an arbitrary node and give you the coordinates of that node in a consistent basis in finite time with arbitrarily high probability of correctness

class ComputedBasis:
	def __init__(self):
		self.node_positions_by_key = {}

	def get_coords(node):
    	# Given a node, give the coordinates of that node in some
    	# consistent basis 
    	pass

I claim that this is indeed possible to do, and the steps to do it look nothing like “compute ${10}^{100}$ things”.

Edit: To be explicit about the motivation, once we define this function, we can find a path from our position to the sandwich using something like

def path_to_sandwich(my_node, sandwich_node):
    basis = ComputedBasis()
    my_coords = basis.get_coords(my_node)
    sandwich_coords = basis.get_coords(sandwich_node)
    for axis, (my_pos, sandwich_pos) in zip(my_coords, sandwich_coords):
        if my_pos < sandwich_pos:
           raise(f"""
               Can't get to sandwich from here!
               I can only travel towards the origin on each axis.
                   axis: {axis}
                   my_pos: {my_pos}
                   sandwich_pos: {sandwich_pos}
           """)
     return get_path(basis, my_node, sandwich_node)

def get_path(basis, start_node, goal_node):
    curr_node = start_node
    path = [curr_node]
    goal_coords = basis.get_coords(goal_node)
    while curr_node != goal_node:
        curr_coords = basis.get_coords(curr_node)
    	# Find the first axis where we need to move towards the goal along that axis.
    	for axis, (curr_pos, goal_pos) in zip(cur_coords, goal_coords):
    	    if curr_pos > goal_pos:
    	         step_coords = [p for p in curr_pos]
    	      	 step_coords[axis] -= 1
    	      	 step_coords = tuple(step_coords)
    	      	 break
    	for edge in curr_node.edges:
    	    dst_node = edge.get_dst()
    	    dst_coords = basis.get_coords(dst_node)
    	    if dst_coords == step_coords:
    	    	step_node = dst_node
    	    	break
    	curr = step_node
    	path.append(curr)
    return path

Note that my framing of the problem is slightly different, in that (0, 0, 0, ..., 0, 0, 0) is the point from which there are no outbound edges, rather than (10, 10, 10, ..., 10, 10, 10) in your version. Doesn’t really make a difference logically, just makes the code more readable.

[Nathan Helm-Burger]

Thanks faul-sname. I came to the comments to give a much lower effort answer along the same lines, but yours is better. My answer: lazy local evaluations of nodes surrounding either your current position or the position of the goal. So long as you can estimate a direction from yourself to the goal, there’s no need to embed the whole graph. This is basically gradient descent...

[faul_sname]

Fun side note: in this particular example, it doesn’t actually matter how you pick your direction. “Choose the axis closest to the target direction” performs exactly as well as “choose any edge which does not make the target node unreachable when traversed at random, and then traverse that edge” or “choose the first edge where traversing that edge does not make the target node unreachable, and traverse that edge”.

Edit: at least assuming that the graph is directed

[Johannes C. Mayer]

I might not understand exactly what you are saying. Are you saying that the problem is easy when you have a function that gives you the coordinates of an arbitrary node? Isn’t that exactly the embedding function? So are you not therefore assuming that you have an embedding function?

I agree that once you have such a function the problem is easy, but I am confused about how you are getting that function in the first place. If you are not given it, then I don’t think it is super easy to get.

In the OP I was assuming that I have that function, but I was saying that this is not a valid assumption in general. You can imagine you are just given a set of vertices and edges. Now you want to compute the embedding such that you can do the vector planning described in the article.

I agree that you probably can do better than ${10}^{100}$ though. I don’t understand how your proposal helps though.

[faul_sname]

Do you want me to spoil it for you, do you want me to drop a hint, or do you want to puzzle it out yourself? It’s a beautiful little puzzle and very satisfying to solve. Also note that the solution I found only works if you are given a graph with the structure above (i.e. every node is part of the lattice, and the lattice is fairly small in each dimension, and the lattice has edges rather than wrapping around).

[Robert Kralisch]

the maximum plan length is only $10\cdot 100=1000$ steps

You mean the maximum length for an efficient/​minimal plan, right? Maybe good to clarify (even if obvious in this case). Just a thought.

[Johannes C. Mayer]

Yes right, good point. There are plans that go zick-sag through the graph, which would be longer. I edited that.