top of page

Goal

The objective of this practice is to implement the logic of a Gradient Path Planning (GPP) algorithm. Global navigation through GPP, consists of:

 

Gallery

  • Selected a destination, the GPP algorithm is responsible for finding the shortest path to it, avoiding, in the case of this practice, everything that is not road.

  • Once the path has been selected, the logic necessary to follow this path and reach the objective must be implemented in the robot.

With this, it is possible for the robot to go to the marked destination autonomously and following the shortest path.
 

Global navigation with GPP
    The objective of this practice is to implement an autonomous taxi that can go to the point specified on the map. To do this we will first need to implement the map using Gradient Path Planning (GPP).

    GPP works on the principle of potential fields. The obstacles in the path serve as potential wall to the path planner, and the target serve as potential well. By combining all the potential walls and wells, a path is constructed as a downward slope. The robot follows that path to reach it’s destination.
To implement this  we will use the Wave Front Algorithm, which is a BFS based approach to build a path from source to destination. The algorithm works by assigning weights to a grid of cells. Given the source and target, the algorithm starts from the target node and moves outwards like a ripple, while progressively assigning weights to the neighboring cells.
For example, if we use the cells immediately up down left and right  to the one we are considering we will get a cross, and if append each cell we use to a list and then consider all the cells in the list (making some sort of light wave front algorithm) we get something like this (all the values are set to 255 to better se the result)


 

Screenshot from 2021-01-06 09-31-37.png

    Then we add the rest of the points to consider (the corners for the square) and the correct values of the cells (the euclidean distance to the selected point ) and get this.

Screenshot from 2021-01-06 09-33-00.png

    The next step is to make the expansion stop when it has passed 20 cells the coordinates of the taxi.
After some changes we get this, to get the green line we just check the lowest square near a point (the starting point is the first) and make this again and again until we get to the destination. Before anything we make the walls bigger so hat the car does not crush.


 

    To make the car move we have to send it speeds, an to get the we check the squares around the car, get the angle to the square with less value (closer to the destination), an add this angle to -angle of the car, this is the angular speed,  the linear difference depends on the angle.

   After making this we get the full functioning car. It is not the fastest but it works fine, it doesn't crash with the walls and goes where pointed .

© 2020 por Alberto Delgado

bottom of page