We discuss the generation of symbolic feedback control sequences for navigating a sparsely-described and uncertain environment, together with the problem of sensing landmarks sufficiently well to make feedback meaningful. We explore the use of a symbolic control approach for mitigating the lack of a detailed map of the environment and for reducing the complexity associated with finding control laws which steer a control system between distant locations. Under our language-based approach, control inputs take the form of symbolic strings. The decision process that generates those strings is guided by estimates of the vehicle's location within a set of important landmarks and by the statistical effectiveness of each string. This arrangement, and in particular the symbolic nature of the control set, allows us to formulate and solve a class of optimal navigation problems which would be exceedingly difficult to handle if approached at the level of sensors and actuators. Our approach is illustrated in a series of numerical indoor navigation experiments.