M.Sc Thesis

M.Sc StudentVeksler Yaron
SubjectEvasive On-Line Navigation of an Autonomous Robot in Planar
Unknown Environments
DepartmentDepartment of Mechanical Engineering
Supervisor PROF. Elon Rimon
Full Thesis textFull thesis text - English Version


This thesis is concerned with on-line navigation of a circular mobile robot of size  in an unknown hostile environment. The hostility of the environment in this thesis requires the robot to avoid traveling through open areas where it can be easily noticed. To move evasively through the unknown environment, the robot is allowed to move along an evasive motion graph consisting of contact preserving path segments and locally shortest lines connecting these obstacle-encircling paths.

In this thesis, the evasive motion graph of a general environment is defined, and the optimal off-line navigation path is calculated, using the A-star algorithm. The evasive motion graph construction method ensures the graph is planar.

Next, the evasive on-line algorithm is introduced. This algorithm builds a partial evasive motion graph based on the currently known environment discovered by the robot during the navigation, using a laser sensor and position sensor. The graph is then explored within a series of expanding search ellipses, utilizing the nearest neighbor algorithm.

The performance analysis of the evasive on-line navigation algorithm is based on competitiveness, which measures the on-line algorithm's path length , relative to the optimal off-line path length, . The evasive on-line algorithm developed in this thesis is shown to have a log-quadratic competitive upper bound:

, where D is the disc robot size. The tightness of the upper bound is exemplified by a corridor environment for which the robot's on-line path is found to be of the order  . The universal lower bound over all navigation algorithms using laser sensors of any detection range is found in this thesis, and proved to be quadratic:. The usefulness of the algorithm is shown in an exterior example representing an outdoor environment.