Artificial Intelligence – Facultad de Ingeniería, UASLP

Adviser: Dr. José Ignacio Núñez Varela

A Robot kinematic has a microprocessor, such as two or more motor actuators, and different sensors that help control the kinematics of this, however, the response of a system is not instantaneous, there is a margin of error in the response of the actuators and there are environmental factors that are variable and cannot be controlled / measured. Therefore, there are many techniques to control systems according to the behavior of sensors and actuators.

To implement an optimization searching algorithm (e.g. Genetic Algorithms), based on artificial techniques, which finds the best configuration for getting high speed on a Line Follower.

By COVID situation it was impossible to me to implements a software on a real robot, so I change the approach to a simulation of a line follower.

I developed a simulator of a Line Follower which finds its best configuration to follow a line in the lower time possible with Genetic Algorithms. I use Processing for the implementation of this system.

The objective on each robot in this system is to follow the ellipse limited by a black line in the shortest time possible, if one Robot stop touching the black line then it is said that this one went off the track and I did not achieve his goal.

For robots processing the track is painted divided on 4 different colors, each one of this represents a different area on it, for example the green part is the area inside the ellipse, with this separation it’s possible to know when a robot its outside the track and where the line to follow is. When each robot has processed its next moving, the track is painted with only white and black.

The robot it’s a square with two ‘light sensors’ on it, each sensor can see if one specific pixel of the field is white or not.

The sensors are positioned on the center of the Y axis of the robot, but its horizontal position is variable and can be defined to each instance of the robot (Sensors are the white points on the robot).

The robot is always moving to the front but its speed can be assigned in the construction of the instance.

To follow the line, robots can change its orientation and see if the sensors are in black or white.

The system first creates the initial population, then starts on loop to do the steps: computation of one generation, reduce the population to the best individuals, create new generation by crossover and new random individuals, mutation on the individuals of the new generation.

In this part all generation is simulated on the field.

There is a list of the best robots of all generations, in the reduction part this list is actualized by selecting the best 50 individuals front the ‘actual best robots’ and the current generation.

On this part by tournament selection and 90% probability of crossover (if it doesn’t happen, then the best robot on the tournament is added) 45 new individuals for the next generation are made, and five new individuals with random values are also implemented (with the purpose of give variety on the population).

The crossover is by uniform crossover operator, that is, randomly selecting between the two parents which variable will belong to the child. For example, for the variable ‘vel’, it is selected randomly by two options, ‘vel’ from one parent or another.

Mutation’s probability is 0.9, when an individual gets selected each of its variables are modified by an Randomly value on Gauss distribution, with the approach of get trends on this values and not only random change it.

For each robot is calculated by the time it spends on finish two laps at the track. if a robot doesn’t finish both laps then it receives a penalty based on how far it needed to end.

After finish the development of the system, I test it with 31 executions of 150 generations. The system gave data with the variables of the best instance of each execution and the fittest in each generation.

I made a graph with the average execution to get the visualization of how the fittnes in average is changing.

I also look for when a solution is find (at the first none of the robots completes the two laps)

Average: 7.258064516

Median: 5

Mode: 5

With the last graph I made again the average execution but without atypical runs.

There is a table with the variables of the fittest of each run.

I also made a run with 2997 generations, the fitness robot which the system could find is with a value from 91.

The best configuration found is: { 6, -21, 23, -16, 23, 14}

Genetic Algorithms are so useful to find configurations of something. With this approach Robot’s control can be improve.

This system will find a solution in the 5th generation on the most of the cases.

The best configuration of a line follower with two sensors is to gets a distance between them farest as possible. To follow a line, the approach is when both sensors are in white turn a little to one side, when only one sensor is in black do a strong turn to its side, and the turn with both sensors on black doesn’t matters. The speed needs to be medium.

Repository of the project https://github.com/CFOP/Line-Follower-with--Genetic-Algorithm

Video of the project https://www.youtube.com/watch?v=QEgTwicO3s8

Tema 2. Algoritmos Genéticos, Abdelmalik Moujahid, Inaki Inza y Pedro Larranaga, Departamento de Ciencias de la Computación e Inteligencia Artificial, Universidad del País Vasco–Euskal Herriko Unibertsitatea: http://www.sc.ehu.es/ccwbayes/docencia/mmcc/docs/t2geneticos.pdf

PID control tuning using genetic algorithm, keevitajamees, Youtube, 9/Oct/2020: https://www.youtube.com/watch?v=guNk-u9nGdA

Machine Learning Control: Overview, Steve Brunton, YouTube, 10/Jun/2018: https://www.youtube.com/watch?v=3yU2k8R9JeU&t=20s

Machine Learning Control: Genetic Algorithms, Steve Brunton, YouTube, 11/Jun/2018: https://www.youtube.com/watch?v=CZE86BPDqCI

Machine Learning Control: Tuning a PID Controller with Genetic Algorithms, Steve Brunton, YouTube, 11/Jun/2018: https://www.youtube.com/watch?v=S5C_z1nVaSg