Approximately locating an invisible agent in a graph with relative distance queries

In a pursuit evasion game on a finite, simple, undirected, and connected graph G, a first player visits vertices m1,m2,… of G, where mi+1 is in the closed neighborhood of mi for every i, and a second player probes arbitrary vertices c1,c2,… of G, and learns whether or not the distance between ci+1 and mi+1 is at most the distance between ci and mi. Up to what distance d can the second player determine the position of the first? For trees of bounded maximum degree and grids, we show that d is bounded by a constant. We conjecture that d=O(logn) for every graph G of order n, and show that d=0 if mi+1 may differ from mi only if i is a multiple of some sufficiently large integer.