Bitbots: Simple robots solving complex tasks

Sensing uncertainty is a central issue in robotics. Sensor limitations often prevent accurate state estimation, and robots find themselves confronted with a complicated information (belief) space. In this paper we define and characterize the information spaces of very simple robots, called Bitbots, which have severe sensor limitations. While complete estimation of the robot's state is impossible, careful consideration and management of the uncertainty is presented as a search in the information space. We show that these simple robots can solve several challenging online problems, even though they can neither obtain a complete map of their environment nor exactly localize themselves. However, when placed in an unknown environment, Bitbots can build a topological representation of it and then perform pursuit-evasion (i.e., locate all moving targets inside this environment). This paper introduces Bitbots, and provides both theoretical analysis of their information spaces and simulation results.