Mobile devices are increasingly expected to support high-performance cyber-physical applications in small form factors, e.g., drones and rovers. However, the gap between hardware limitations of these devices and application requirements is still prohibitive - conflicting goals such as robust, accurate, and efficient execution must be managed carefully to achieve acceptable operation. In this paper, we explore the tradeoff between performance and efficiency in such cyber-physical systems, specifically with respect to localization (a core task for any mobile autonomous device). We perform a design space exploration (DSE) given a number of configurable parameters for both localization algorithm and platform layers. Given the configuration space, we formulate a cross-layer multi-objective optimization problem to explore the tradeoff between localization accuracy and power consumption. We then propose a predictive model for robust execution that can be used to determine desirable configurations at runtime in the face of environmental changes.