In this work we present an efficient environment representation based on the use of landmarks and language-based motion programs. The approach is targeted towards applications involving expansive, imprecisely known terrain without a single global map. To handle the uncertainty inherent in real-world applications a partially-observed controlled Markov chain structure is used in which the state space is the set of landmarks and the control space is a set of motion programs. Using dynamic programming, we derive an optimal controller to maximize the probability of arriving at a desired landmark after a finite number of steps. A simple simulation is presented to illustrate the approach.