Egerstedt, MagnusHristu-Varsakelis, DimitriosRecently there has been renewed interest in the study of abstractions of control laws for intelligent machines as a tool for managing the specification complexity of the control strategies necessary to accomplish most tasks of practical interest. This work considers the use of abstract descriptions of motion control programs and of the environment, and explores some new problems of system theoretic interest that arise as a result. We study the problem of active localization for a mobile robot moving on a sparsely-described uncertain environment and show how that problem can be posed as that of observability of a finite automaton. We present algorithms (based on Hidden Markov Models) that answer the question of i) whether or not a representation of the environment (in the form of a directed graph) is observable, and ii) what is the shortest navigation policy that allows the robot to uniquely identify its location on the graph.en-USTechnical Report