Localized Vacuum cleaner

 

 

    The task assigned is to program a high gamma vacuum cleaner. This type of robots have localization and mapping methods, thanks to that it can clean in a more efficient and systematic way. To solve this problem we will implement the BSA coverage algorithm.

 
 
 
    Firstly we have to make an internal representation of the map to apply the algorithm. To avoid going near the obstacles we have applied a dilation to the original image of the map:
Then we divided the map in a 31x31 grid. To get the robot's position we use a translation matrix, the final result can be seen in the next figure:


Now we have to add the algorithm and translate it to speed commands.


I divided the current issue into two parts, the algorithm implementation and the actual movement of the robot that follows the desired path.


The algorithm that we will use is the BSA(Backtracking Spiral Algorithm). It is based on the making of spiral filling paths, when a spiral is finished the robot returns to the nearest empty space. Because of the simplicity of the algorithm the robotic system can execute it in a robust way without needing many sensors or high computation time.



After reading the article "BSA: A Complete Coverage Algorithm", I tried to translate the  orders and conditions to python code. However in the first functional iteration the algorithm got stuck in some positions and leaved white spaces in its trail. After reviewing the functions used one by one, I noticed that when a spiral was finished the next position obtained was not updated correctly in the grid. A complete execution can be seen in the next video:

 


The final ingredient is the actual movement of the robot. To check the robot position i noted the position of corners in the map and in the grid for both x and y axis. After that i obtained two equations using a linear regression model of the data:

Curiously the two lines have the same slope value but with opposite signs. Then to create the forward movement function i used both the equations to stop when the robot reaches a new cell.
 
For the turning part I needed to add a proportionate controller to correct the orientation.
 
In the tests of the complete algorithm along with the movement I became aware of some points where the robot moved too close to the walls so they were corrected in the grid. An example of the execution can be seen in the next video:






Some improvements could be made though. The two that I think that will reduce significantly the duration are the refinement of the turning, to be more precise in the angle estimation adding a derivative part to the controller. 

The other one is the implementation of a more effective path planner when the BSA algorithm detects a final spiral point. The one implemented is the breadth first search algorithm following the next diagram:


If changed to a visualization graph algorithm allowing diagonal movement the path would probably become shorter, an example of this can be seen in the next image:




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

Global Navigation with GPP

Image
  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...
Read more