M.Sc Thesis

M.Sc StudentGabriely Yoav
SubjectCovering Algorithems for Mobile Robot
DepartmentDepartment of Mechanical Engineering
Supervisor PROF. Elon Rimon


This thesis is concerned with mobile robot coverage of areas populated by unknown obstacles. The thesis focuses on the on-line version of the problem, where the robot must use its sensors to discover obstacles during the coverage process, while attempting to minimize the length of the covering path.

The thesis contains several novel mobile robot coverage algorithms, which efficiently cover unknown planar areas using the robot’s sensors. In the thesis, the mobile robot is equipped with a square-shaped DxD covering tool.  The coverage algorithms impose an incremental grid on the environment, such that each cell of the grid is identical to the covering tool. All the covering algorithms run in linear time in the number of grid cells. We describe algorithms that generate two basic covering patterns: spiral covering patterns, and scan covering patterns that intentionally to minimizes the number of undesired turns.  For each covering pattern we consider a preliminary and a full version of the algorithm. The full algorithms cover completely general grids with covering path whose length depends on the obstacles perimeter in the grid

Finally, we derived the following universal lower bound. Let  l0   denote the length of the optimal off-line covering path. Then for every sensor-based covering algorithm there exist a planar environment in which the algorithm will generate a covering path whose length, denoted l , satisfies  l ≥  (2-ε) l, where ε is an arbitrarily small positive parameter.