Global Navigation with GPP

  This time the objective is to create a plan or path to guide a robot to a distant location, specifically a taxi. To solve this the Gradient Path Planing (GPP) will be used. This algorithm gives us the shortest way to reach the target by calculating the descending gradient of a given grid, similar to this figure:


    In our case the planing will be done with an ascending gradient instead of a descending one, but this will be explained later.

  

    At first instance we need to be aware that the GPP method needs a metric grid map of the world, this means that the map will consist of diferent cells that will mantain some correlation with the real world distances between objects, fo example it could look like this:


 
 
        Now that we have the map, we need to fill the cells to calculate the path. In the algorithm we are using the target will generate an expansive wave that will assign lower values to the cells that are further from the target and greater ones to the closer cells, this wave will continue until the robot is reached (and a bit more for precaution) . Then we must give some type of penalty to the cells that are near an obstacle to avoid them. The main difference of the approach that is used in this part, is that the map we have (in grayscale) has the buildings (obstacles) represented as the lower value possible (0) and the road (available space to move) with the maximum value (255) so the procedure will be the same but changing the cells values accordingly to this new statement. 

    Finally, we obtain maps like these:
 
 

       
 
     Then the path is calculated by obtaining the consecutive cells that increases the value of the last one and that is closer to the final destination.
 
 
    Although, since there are numeric limits to the array representation, it can only contain integer numbers between 0 and 255, due to this if the objective is very far away it can lead to some unexpected results when the number overflows and
gives a wong map, this can be solved simply by reducing the difference between consecutive cells:          
      
  •     more differentiation:


  •  Less differentiation:

 
     
 
 
 
 
      At last but not least, once the gradient and the path have been calculated, it is time for the car to move. Since it is an holomonic car, to simplify the movement only four configurations (north, east, south, west) will be considered for the orientation of the car.

    Finally, by joining the path with the movement the behaviour of the car is the following:
 









Comments

Post a Comment

Popular posts from this blog

Local Navigation with VFF

Image
       The main objective of the local navigation in robotic systems is to get to a near target in the safest and most efficient way possible. One of the many algorithms to solve this problem is the Virtual Force Field , developed by Borenstein and Koren.       The fundaments of it are that every obstacle in the environment generates a repulsive force towards the robot and the target generates an attractive force in the robot. So, with this two facts in mind we can find the combination of both forces that will guide the robot to its destination similar to the next image:        For a simplification each object generates only                      one mayor force, instead of multiple repulsive forces.      Now, we want to make a reactive navigation system for a car with an  implementation of  this algorithm. Since the sensor we are usin...
Read more

Autoparking

Image
  We have to make a program that parks a car in a parallel disposition. To do so the car must follow a trajectory similar to the one in this image: On the hardware part, we can access three 2D lasers positioned on the front, right and rear of the car. We can also send linear and angular speed commands.   The software implementation is based on a finite-state machine architecture.The algorithm can be divided into four main states: -First we have to find a free space and advance some distance to have enough space to move in reverse.  -Secondly we move backwards and move the steering wheel in the same direction of the space where we want to park.  -Then we steer in the other direction while moving backwards.  -Finally, to relocate the car into a position in line with the other car we can advance forward or backwards while steering to one side or the other depending on the situation. To find a free space to park we check the right-side laser, until we find a positio...
Read more