M.Sc Thesis

M.Sc StudentBaratz Rom
SubjectBattery Powered Coverage of Planar Environments by an
Autonomous Mobile Robot
DepartmentDepartment of Mechanical Engineering
Supervisor PROF. Elon Rimon
Full Thesis textFull thesis text - English Version


This thesis is concerned with battery powered coverage of planar environments by an autonomous mobile disc-robot of size D in known and unknown environments, while utilizing a single charging station at which the robot begins and finishes the coverage task. The restrictions imposed on the robot include finite battery capacity which limits the length of each individual coverage path, and a sensory input from a single on-board scanning range sensor.

In this thesis, both the off-line and on-line Battery Powered Descending Coverage (BPDC) algorithms are defined and analyzed. The performance analysis of both algorithms is based on the notion of competitiveness, which measures the algorithm path length, l, relative to the length of the optimal off-line coverage path, lopt. The off-line BPDC algorithm developed in this thesis is shown to have a constant factor upper bound: l≤3√(2)lopt . This bound is further improved in simple environments down to: l≤√(2)lopt. For the on-line BPDC algorithm, a proof sketch is included in this thesis, in which it is conjectured that the algorithms performance is bound by: l≤log2(L/2D)lopt , where L is the maximal length of a single battery-powered coverage path. Moreover, this bound is tight.

This thesis also includes a proof for a raised lower bound on the length of the optimal off-line coverage path, lopt. This improved approximation of lopt is used in the execution examples that compare the performance of the BPDC algorithms against existing algorithms tackling the battery powered coverage problem. The results of these simulations are used to show the effectiveness of the BPDC algorithms when compared both to existing algorithms, and to an unknown optimal coverage path. Finally, the execution examples demonstrate the compatibility of the BPDC algorithms to implementation with regard to computational resources and robustness with regards to localization errors.