Vacuum Cleaner

The goal of this project is be able to make a low-end vacuum cleaner. This cleaner would have to ensure to clean as much area as possible of a predetermined map that simulates a house. Since the goal is to emulate the behavior of the ones that are in the client market (of low-end), the vacuum cleaner must cover a good area in a reasonable time period:

To achieve the objective, three different functionalities are presented using finite state machines (FSM). In this post we will explain all of them and we will analyze which one got the best results.

First strategy: Bump & Go

In this first approximation we are using a FSM of 4 states: going forward, going backwards, and turning left or right, depending on which side the bumper hits:

The robot begins with "FORWARD" as initial state. In the moment he hits a wall, he will change his state to "BACKWARD", and he would start moving with the same velocity as he had in forward state, but now with negative value (backwards movement). He will be moving backward a predetermined time, and once that time period finished, he would change his internal state to "TURN LEFT" or "TURN RIGHT", depending in which bumper he hit before. If central bumper is pressed, we will "flip a coin" and choose randomly if we turn left or right. During turn left/right state, the robot will be moving with a velocity: ANGULAR_VELOCITY * R, where R is a random value between 0 and 1, during  a predetermined time. Once turn period finish, he will change again to forward state.

Important note: In order to estimate the turning and backing time, we are not using the sleep function of the time library. Applying this in a ROS system would be  translated into blocking system. It is for that reason that we are using the time library for python to count how many seconds we need to stay in each state. We define the stopwatch() function to check every iteration if the desire time period for each state expires or not:

RESULTS:

After 10-15 minutes of work, this is the path and the area covered by the vacuum cleaner:

We can see that getting random values for turning velocities can help in getting to some narrow areas of the house. It also helps in not getting stuck in some corners (We are avoiding loops of turning left and right all the time without moving of the same place). Also, the central bumper functionality give us some more randomize movements and helps getting to other places (less repetitive patterns).

Nevertheless, we can obviously improve the functionality to cover more area in the same amount of time.

Second strategy:  Lidar & Go

There is another tool to use in this problem: the Lidar. With this sensor we can make the vacuum cleaner not to hit any wall or object of the house. Using this option we can make the same all functionality as in the first strategy, changing a few things:

• Now, in order to change from "forward" state to "backward" state, the robot should be at a distance < DISTANCE_THRESHOLD previously defined in the program (value in millimeters). We will store in this state the angle in which it is the more approximated obstacle.
• If the angle we obtained previously is < 90 it means that its at his right, so we will change to "turn left" state. In the other hand, if the angle is > 90 it means that its at his left and we need to change to "turn right" status. Finally, if the angle is exactly 90 the obstacle is in front of the robot and we can make the "flip the coin" case to choose to which side turn. 

In order to do this we created the getDistance() function that returns the minimum distance from the robot to the obstacle and the angle where we obtain that value in tuple form:

 

The parameter "laserData" we receive can be obtained from the method HAL.getLaserData()

RESULTS:

After 15 minutes of work, this is the path and the area covered by the vacuum cleaner:
 

We can understand in this strategy that the "flip coin" mechanic does not have many value in the algorithm, because getting exactly 90 degrees where it is the closest distance to the obstacle is really difficult. In fact, this isn't bad. In the previous strategy sometimes the frontal bumper was pressed when the obstacle was at ~80-100 grades, so in this strategy we have more accuracy in the movement algorithm. That can be a reason why we got a better score this time.

In spite of all this pros, we have to understand that using Lidar prevents the cleaner of reaching the areas that are really close to walls ore other objects. This is a problem if we need to apply this strategy in a real scene, cause it will not make the best clean service.

Thrid strategy:  Spiral state

Circular movements such as spirals or circles can make our vacuum cleaner able to clean more area in a really small amount of time. In this last strategy we are including a new state to the FSM: the "spiral" state. The new initial state is going to be the "spiral" state, where the vacuum cleaner is going to move creating a spiral. 

Since circular movements can be really good to clean some area in a small amount of time, but making in it frequently can make the cleaner really slow to clean and not able to go in to narrow paths. 

In order to avoid that problem, the state "spiral" will be executed every MINIMUM_SPIRAL_PERIOD seconds and not every time we do an iteration of the different states of the FSM. 

In addition, in this strategy we are fixing other problem that we were having in the previous  strategy: void robot loop movements in narrow paths. To avoid this, we are introducing a new function called setBestWVelocity() that will consider which angular velocity is good depending the time that the robot has been moving forward: This function is using the previous formula we were using in the other strategies: ANGULAR_VELOCITY * R, where R is a random value (that now depends of the time parameter)

 

The "time" parameter means the time period in seconds that the robot has been in "forward" status.

The new FSM looks like this:

RESULTS:

 After exactly 15 minutes of work, this is the path, score and the area covered by the vacuum cleaner:

 As we can see, introducing this new state increase the amount of area covered in the same time. However, its really important to understand that the value of the constants parameters affects a lot in the algorithm and can be the key of doing a better service of this vacuum cleaner, specially the following ones:

• LINEAR_VEL: Increasing the linear velocity in the long term makes movement algorithm considerable better. But you may also notice that backwards velocity is the negative value of the linear velocity, and a considerable high value may have a negative effect.
  
• ANGULAR_VEL: Finding an appropriated value would make turns states more efficient.
  
• MINIMUM_SPIRAL_PERIOD: Need to have a balanced value. Low values will slow down the algorithm. High values will vanish spiral state's benefits.

In the same line as in the second strategy, using Lidar prevents the cleaner of reaching the areas that are really close to walls ore other objects. This is a problem if we need to apply this strategy in a real scene, cause it will not make the best clean service. We might consider then applying this strategy with a bump and go functionality. 

FINAL SOLUTION DEMONSTRATION: