  We consider a graph observability problem: how many edge colors are needed
for an unlabeled graph so that an agent, walking from node to node, can
uniquely determine its location from just the observed color sequence of the
walk?
  Specifically, let G(n,d) be an edge-colored subgraph of d-dimensional
(directed or undirected) lattice of size n^d = n * n * ... * n. We say that
G(n,d) is t-observable if an agent can uniquely determine its current position
in the graph from the color sequence of any t-dimensional walk, where the
dimension is the number of different directions spanned by the edges of the
walk. A walk in an undirected lattice G(n,d) has dimension between 1 and d, but
a directed walk can have dimension between 1 and 2d because of two different
orientations for each axis.
  We derive bounds on the number of colors needed for t-observability. Our main
result is that Theta(n^(d/t)) colors are both necessary and sufficient for
t-observability of G(n,d), where d is considered a constant.
  This shows an interesting dependence of graph observability on the ratio
between the dimension of the lattice and that of the walk. In particular, the
number of colors for full-dimensional walks is Theta(n^(1/2)) in the directed
case, and Theta(n) in the undirected case, independent of the lattice
dimension.
  All of our results extend easily to non-square lattices: given a lattice
graph of size N = n_1 * n_2 * ... * n_d, the number of colors for
t-observability is Theta (N^(1/t)).
