M.Sc Thesis

M.Sc StudentShnaps Iddo
SubjectOnline Coverage by a Tethered Autonmous Robot in
Planar Unknown Envirinments
DepartmentDepartment of Mechanical Engineering
Supervisor PROF. Elon Rimon
Full Thesis textFull thesis text - English Version


This research is concerned with online tethered coverage, in which a mobile robot of size D is attached to a fixed point S by a cable of finite length L. Starting at S, the robot has to cover an unknown planar environment containing obstacles, and return to S with the cable fully retracted. After discussing the differences between tethered and untethered coverage, the thesis establishes an optimal off-line tethered coverage methodology. Later, it introduces the TC (Tethered Coverage) algorithm that performs online tethered coverage using position and local obstacle detection sensors. The performance of online navigation algorithms is measured by their competitiveness, determined by measuring their total online path length, $l$, relative to the optimal off-line solution lopt. The paper establishes that the TC algorithm has a competitive performance of l ≤ 2 (L/D)* lopt. Our work additionally derives three lower bounds on the competitiveness of the online tethered coverage problem. Two universal (i.e. algorithm independent) lower bounds concerning any tethered coverage algorithm, and an additional lower bound, log(L/D * lopt , concerning a generic family of tethered coverage algorithms of which the TC algorithm is a special case. Examples, simulations, and experiments with a tethered recoiling mechanism illustrate the usefulness of the TC algorithm.