Why direction-giving is hard: the complexity of using landmarks in one-dimensional navigation

The authors outline a formal model of topological navigation in one-dimensional spaces such as single roads. They formally define the concepts of direction giving and of custom map, as well as some specifications for feature detector models, including the idea of sensor synchronicity. The representations necessary to model and make use of differences between the world itself, the world as perceived by the map maker, and the world as experienced by the navigator are discussed. The difficulty of giving precise meaning to what is meant by a `good´ map is shown, and an operational definition of what is meant by a `landmark´ is given: regardless of starting position, any custom map can attain a landmark with but a single direction. It is shown that even in the simplest case, NP-complete problems arise in the efficient selection and sequencing of sensor modalities, even while attempting to navigate from one single object to another. A heuristic is provided that appears reasonable for map creation, and examples are given of several very different maps, each of which is optimal under eight reasonable criteria