M.Sc Thesis | |

M.Sc Student | Veksler Yaron |
---|---|

Subject | Evasive On-Line Navigation of an Autonomous Robot in Planar Unknown Environments |

Department | Department of Mechanical Engineering |

Supervisor | PROF. Elon Rimon |

Full Thesis text |

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.