Bitbots: Simple Robots Solving Complex Tasks

Abstract

Sensing uncertainty is a central issue in robotics. Sen-sor limitations often prevent accurate state estimation, and robots find themselves confronted with a compli-cated information (belief) space. In this paper we define and characterize the information spaces of very simple robots, called Bitbots, which have severe sensor limi-tations. While complete estimation of the robot’s state is impossible, careful consideration and management of the uncertainty is presented as a search in the informa-tion 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 topo-logical representation of it and then perform pursuit-evasion (i.e., locate all moving targets inside this en-vironment). This paper introduces Bitbots, and provides both theoretical analysis of their information spaces and simulation results.