Ph.D Thesis

Ph.D StudentGabriely Yoav
SubjectOn-Line Motion Planning Problems in Robotics
DepartmentDepartment of Mechanical Engineering
Supervisor PROF. Elon Rimon
Full Thesis textFull thesis text - English Version


The thesis is concerned with on-line problems where a mobile robot of size D has to achieve a task in an unknown planar environment whose geometry is acquired by the robot during task execution. The critical parameter in such problems is physical motion time which corresponds to length or cost of the path traveled by the robot. The competitiveness of an on-line algorithm measures its performance relative to the optimal off-line solution to the problem. While competitiveness usually means constant relative performance, this thesis generalizes competitiveness to any functional relationship between on-line performance and optimal off-line solution. Given an on-line task, its competitive complexity class is a pair of lower and upper bounds on the competitive performance of the best on-line algorithms for the task, such that the two bounds satisfy the same functional relationship, in terms of optimal off-line solution, up to constants. The thesis classifies some common on-line motion planning problems into their competitive classes.

The thesis also introduces a complementary notion of competitiveness which characterizes on-line navigation algorithms when the target is unreachable from the robot’s start position. The disconnection competitiveness of an on-line navigation algorithm measures the path length it generates in order to conclude target unreachability relative to the shortest off-line path that proves target unreachability from the same start position. An on-line navigation algorithm for a disc-shaped mobile robot, called CBUG, is described. This algorithm has a quadratic connection competitiveness, which is also the best achievable performance over all on-line navigation algorithms. The disconnection competitiveness of CBUG is analyzed and shown to be quadratic in the length of the shortest off-line disconnection path. Moreover, it is shown that quadratic disconnection competitiveness is the best achievable performance over all on-line navigation algorithms. Thus CBUG achieves optimal quadratic competitiveness with respect to connection and disconnection paths. Motivated by these results, a generic equivalence between connection and disconnection competitiveness is established. An on-line navigation algorithm possesses a disconnection competitiveness bound if and only if it possesses a connection competitiveness bound.