A search and coverage algorithm for mobile robot

Abstract

This paper presents a new work space modeling and search algorithm for complete coverage of robotic environment. The proposed algorithm named spatial cell diffusion (SCD) encodes the target area as groups of Gray codes for grid cells with size of instantaneous robot coverage and extends its sweep area by diffusing occupied cells outwards through continuous spiral movement. Based on the direct and rotational motions of robot, directions of search are categorized into eight ways by combining four cardinal points {N, S, W, E} with two senses of rotation {CW, CCW}. According to the direction of search selected, robot navigates and sweeps the target region cell by cell in consistent manner. While executing a coverage operation, robot changes its direction of motion and reverses the sense of rotation at a boundary cell of work space model. The spatial cell diffusion search algorithm proposed can be applied to on-line coverage of unknown environment as well as off-line coverage of known work space. The feasibility and effectiveness of the algorithm are demonstrated by simulation results for coverage work of target area.