Integrated On-Line Localization, Mapping and Coverage Algorithm of Unknown Environments for Robotic Vacuum Cleaners Based on Minimal Sensing

This paper presents a new complete coverage algorithm of a robotic vacuum cleaner (RVC) with a low-cost sensor in an unknown environment. To achieve complete coverage, the RVC must have navigation systems for precise position estimation with localization and a prior map or a map using information that has been continuously collected from the environment. To do this, two-dimensional laser range finders and vision sensors are becoming increasingly popular in mobile robotics, and various methods using sensors like these have been introduced by many researchers. However, it is difficult to apply the methods to sensors used in most RVCs due to their constraints. In this paper, we present a new method applied to most RVCs. For developing the method, we considered the two main problems of maintaining low computational load, and coping with low-cost sensor systems with limited range, detection uncertainty and measurement error. To solve the problems, we propose an assumption that major structures of an indoor environment are rectilinear, and can be represented by sets of parallel and perpendicular lines. Then we derive an algorithm that uses this assumption to map the environment, localize the robot and plan the coverage path with a new cellular decomposition approach. Simulation and experiments verify that the proposed method guarantees complete coverage. (C) Koninklijke Brill NV, Leiden, 2011