M.Sc Thesis | |

M.Sc Student | Gabriely Yoav |
---|---|

Subject | Covering Algorithems for Mobile Robot |

Department | Department 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-ε)
l0 , where ε is
an arbitrarily small positive parameter.__ __