Copyright © 2014 by Intelligent Systems Laboratory, Computer Science Department, Technion - Israel Institute of Technology, Haifa 3200003, Israel. All rights reserved


TheGrue.org

Robot Navigation Project

Robot Navigation ProjectThis project involves the implementation of several robot navigation algorithms on the Range-finder interface platform.

The problem navigation algorithms try to solve is to get a robot from a starting position to a target position without entering any obstacles in the way. To solve this problem a model is designed. The model involves a two dimentional workspace with obstacles in the form of closed polygons. The obstacles do not touch each other and touching their boundry is not considered entering the obstacle. The robot itself is a point which can move in the workspace. The Range-finder interface platform was provided for creating simulations of robot navigation in such a model.

 

 

The Range-finder interface provides tools that enable the creation of navigation algorithms. It enables polygon obstacles definition, it provides geometrical functions, it provides an easy to use graphical interface and it provides obstacle manipulation functions such as testing if a line intersects with an obstacle and gives a function that returns the obstacles seen at a given range.

The main idea of this project was to use the Range-finder interface to create navigation algorithms. These algorithms will later be given as examples in the use of the interface. Furthermore this project was to help find some of the bugs in the interface.

The algorithms are devided into three basic types of algorithms:

  • Global navigation algorithms
  • Local navigation algorithm with touch sensors
  • Local navigation algorithms with variable range sensors

GLOBAL NAVIGATION ALGORITHMS:

A global navigation algorithm is an algorithm where the knowledge of all of the positions and shapes of the obstacles is available at the begining of the algorithm. The main idea in these algorithms is to find the shotest path from the starting position to the target position. The following algorithms were implemented:

  • Robot navigation using the visibility graph.
  • Robot navigation using the tangent graph.

Both of these algorithms provide optimal paths.

Local Navigation Algorithms with touch sensors:

In local navigation algorithms with touch sensors the only knowledge of the obstacles available is the obstacle being touched. It's shape is unknown and only the portion of the obstacle being touched is known. The main idea in this type of algorithm is to make sure the robot reaches the target. The following local navigation algorithms with touch sensors were implemented.

  • Bug1
  • Bug2

 

LOCAL NAVIGATION ALGORITHMS WITH VARIABLE RANGE SENSORS:
In local navigation algorithms with variable range sensors it is possible to know the position and shape of all obstacles in range as long as long as the line between the robot's position and the point from the obstacle which is seen is not blocked by another obstacle. The main idea in this type of algorithm is to make sure the robot reaches the target but also to use the extra information received from the range sensor to improve the route's length. The following local navigation algorithms with variable range sensors were implemented

 

  • Visbug
  • Tangentbug

THE RESULTS:
All of the algorithms stated here were implemented. The local navigation algorithms can run in two modes:

  • A route mode where the route of the robot is created and drawn.
  • A step mode where the algorithm goes one step at a time allowing the viewer to better understant how the algorithm works.

 

Following are several run examples:

 

Robot Navigation Project

A bug1 algorithm run

Robot Navigation Project

A bug2 algorithm run

Robot Navigation Project

A visbug run with range 100

Robot Navigation Project

 

A tangentbug run with range 100

 

Source Code (TAR)

Executables (TAR)

Report (PS)