Abstract As robots interact with the physical world, their usefulness depends directly on how effectively they can sense and move through their environments. Unfortunately, sensors provide only limited (and sometimes incorrect) information. In extreme cases, no sensors at all will be available. Therefore, for robots to be useful, they must act effectively in spite of uncertainty about the current state. This reality motivates a careful study of the information requirements of the problems we intend to solve. What sensing and actuation abilities are needed to complete a given task? Are some robot systems provably "more powerful," in terms of the tasks they can complete, than others? Can we find meaningful equivalence classes of robot systems? This thesis presents two related lines of research that make progress toward answering these questions. First, we introduce a new technique for comparing the power of robot systems based on how they progress through their information spaces, which encapsulate the robots' state uncertainty. The goal is to understand the relative power of different sets of sensors and actuators and to determine which of these sets enable the robot to complete its task. This line of research is inspired by the theory of computation, which has produced similar results for abstract computing machines. The central idea is a dominance relation over robot systems, formalizing the idea that some robots are more powerful than others. This comparison induces a partial order over the set of robot systems. We prove some basic properties of this partial order, show that it is directly related to the robots' ability to complete tasks, and give several examples. Second, we apply these ideas to the problem of active, global localization for mobile robots. Sensor systems of varying ability have been proposed and successfully used to complete this task. We probe the lower limits of this range by describing three extremely simple robot models and addressing the active localization problem for each. The robot, whose state includes its position and orientation, moves in a fully known, simply connected polygonal environment. We pose the localization task as a planning problem in the robot's information space. We consider robots equipped with (1) angular and linear odometers, (2) a compass and contact sensor, and (3) an angular odometer and contact sensor. We present localization algorithms for models 1 and 2 and show that no algorithm exists for model 3. An implementation with simulation examples is presented. These three results, combined with the comparison results mention above, allow us to fully classify a set of 15 robot models according to their ability to complete the localization task.