Abstract Planning with sensing uncertainty is central to robotics. Often, sensor limitations prevent accurate state estimation of the robot. To solve robotics tasks given such sensing uncertainty two general approaches are usually taken. The first approach is to estimate the state first and to solve the given task next using the estimated state information. Hovewer, estimation of the state may sometimes be harder than solving the original task. The other approach is to avoid estimating of the state, solving the task based only on sensor information that comes to robot. These approaches can be further generalized, by defining the information space, the space of all the histories of actions and sensors of the robot. All possible solutions to the given task lie in this space, including the solutions given by the above two approaches. Considering information spaces brings better understanding of the problems involving uncertainty, and also allows finding better solutions to such problems.