4. Obstacle avoidance

OBSTACLE AVOIDANCE

In the fourth exercise, our goal is avoid all the obstacles in the F1 circuit, using local navigation, more concretely virtual force field (VFF). We will have targets that we'll have to achieve, and also obstacles that we'll have to avoid.

VIRTUAL FORCE FIELD

First, I'm going to explain what VFF is. This method consists on two imaginary forces: attractive and repulsive.

ATTRACTIVE FORCE

The attractive force is a vector from the robot to the target. We have to know that is directly proportional to the distance. This means that the more distance we have between the robot

and the target, bigger will be the attractive force. To not give too much value to this force, we have to establish a limit where from that distance, the force will be constant.

You can see how it works in the video on the right.

It's important to convert the absolute target coordinates to relative, which are the coordinates relative to the robot.

We have to know when we are working in absolute or relative coordinates.

After establish a limit for the force, we will have something similar to the left image.

REPULSIVE FORCE

The repulsive force is a vector obtained by the summation of all the repulsive forces, that are the vectors from the obstacle to the robot, in opposite direction.If we are close to an obstacle, this force will be bigger than if we are far from it. From a certain distance this value will be 0.

It's the opposite of the attractive force, repulsive force is inversely proportional to the distance.

First, we have to be sure that our code works for one laser measure. When we already have the repulsive force working for one measure, we have to sum all the laser measures and obtain the average vector. You can see the result in the left video.

I've decided to obtained the distance of the repulsive vector with an exponential function that depends on the distance to the obstacle. Thus, if the obstacle is near, the repulsive force will be much bigger than if the obstacle is far.

When we already have both forces, we have to calculate the resultant force, which is the the weighted sum of both vectors. According to what we want, we have to adjust a parameters to give more weight to the attractive force if we want our robot more brave, or to the repulsive force if we want it safer.

RESULTANT FORCE

In this draw you can see easily how VFF works. Once we have all the forces, we can calculate the resultant force.

This force follows the equations:

resultant_x = alpha * attractive_force_x + beta * repulsive_force_x

resultant_y = alpha * attractive_force_y + beta * repulsive_force_y

Where alpha and beta are the values with the weight you want to do each force. If you want your car braver, you will give more weight to alpha. In the other case, you will give more value to beta.

You can see the final video of the forces, where the green force is the attractive one, the red force is the total repulsive and the black is the resultant, what indicate the car which direction should it take

captura-de-pantalla-de-2016-04-21-123537

Some specifications about how I've done the repulsive force. Since it has to be bigger if the obstacle is closer, and as I didn't want a linear proportionality, I've design an exponential function to calculate this distance. With this function, if the obstacle is a distance of 0, the distance of repulsive vector will be 16, and if it's farther from 7, will the repulsive vector will be near from 0.

Another thing to take into account is that I've given more value to the repulsive vector of the obstacles closer to a determined distance.

We also have to know that there is an offset between the laser and the robot. The index 0 of the laser, is the angle -90 for the robot. Thus, the index 90 of the laser will be the angle 0 for the robot. So we have to adjust the laser information so the robot receives the information correctly.

VELOCITIES

The last step is calculate the linear and angular velocities for the car. I have given a simple implementation: starting from the maximum velocities, I obtain the value between 0 and 1 of the distance in x and y from the resultant force vector With this, we can have an idea of how inclined is the resultant arrow and multiply this difference to the maximum velocity. Thus, we obtain a lower value if the arrow is more inclined.

With the linear velocity it's the same, if the arrow is shorter, we obtain a lower value

I've added an special case, to have more angular velocity if the obstacle is in the front: If the length of the repulsive vector is bigger than a value and its angle is near to 0, this means that we are in front of an obstacle, so we give to the car more angular velocity.

Let's see an example:

In this example, after calculate the values, we will obtain:

For W vector: y = 0.449 and x = 0.89

For R vector: y = 0.89 and x = 0.449

As we can see, with the implementation said before, the angular velocity would have a bigger value with R vector, and linear velocity would be bigger in W vector.