Robot path generation from a Genetic Algorithm

The project presented in this post was accomplished during the Artificial Intelligence class given by professor Caroline. It consisted of using the Genetic Algorithm (GA) to make a robot (from the iRobot Matlab toolbox) navigate from a start point to an end point without hitting any obstacles (walls).

A GA flowchart is shown below to quickly resume the method. At the beginning, a new population of possible solutions is created, each individual of this population can be the solution for a given problem. The population size is strictly fixed to a selected size. Next, an evaluation (or fitness) is applied to each individual of the population, to know how well their solution fits into the problem solution. From there, the process of “evolution” begins, a new generation is created by selecting the best individuals, reproducing them (crossover) and applying a chance of mutation for each individual. At the end, this new generation is evaluated and the process of creating a new generation starts again. The algorithm stops when the evaluation of the population is good enough or the number of generations specified is reached.

flow

source: http://techeffigytutorials.blogspot.com.br/2015/02/the-genetic-algorithm-explained.html

The robot path generation was adapted based on the explanation given of the GA. A brief summary of the developed code in this post is shown:

  1. The start population is created from the possible paths that the robot can follow. Each path (individual) is composed of a sequence of cartesian coordinates (x,y), the path is constructed from the interconnection of those coordinates. It is important to check if the path is valid (no obstacles in the way).
  2. The evaluation (fitness) of the population is retrieved based on the success of the path to reach the destination and the distance traveled from the start point to the finish point.
  3. A new generation is started by selecting the new individuals randomly (Roulette selection) until a selected percentage of the population size. The individuals with the best evaluation have more chances to be selected (Elitism).
  4. The last empty spots of the new population are filled with the reproduction (crossover) of two individuals selected the same way as step 3. The reproduction generates a single child which has one part of the first selected individual and another part of the second individual from a common intersection of both.
  5. With the new population filled, a chance of mutation is applied to each individual. Each Cartesian coordinate have a really small chance of being replaced by another random one. It is also important to check if this new random point is valid to create a path. Mutation is applied to avoid the global minimum solution to the problem.
  6. The population is evaluated again, and the algorithm repeats from step 2 until the requirements are matched.
population_size = 100;
path_size = 10;
%Start point coordinates
start_x = 3;
start_y = 3;
%End point
desired_x = -3;
desired_y = -3;
%survive rate for next generation
keep_alive = 90;
%Number of generations
epoch = 10;
%Mutation chance for each node
mutation_chance = 0.0005; %For each point in the path

Continue reading

Robot navigation using a Multilayer Perceptron Neural Network

The Single-Layer Perceptron (SLP) was one of the first artificial neural networks to be developed. It consists of a system that can classify a series of inputs based on their weights, and distinguish two different type of classes linearly. The activation function, in the case of the picture below, is a step function, meaning the resulting output can assume only two values. An input constant, also known as bias, determines the system threshold to define the output.perceptron-picture

Image source: http://abhay.harpale.net/blog/machine-learning/a-hands-on-tutorial-on-the-perceptron-learning-algorithm/

The limitation of the SLP consists of only separating two classes with a single line, in the example below, if one blue dot were in the middle of the red dots, the training algorithm would not converge to an acceptable solution.

perceptron

Image source: https://glowingpython.blogspot.com.br/2011/10/perceptron.html

xor2

Image source: http://ecee.colorado.edu/

The Multilayer Perceptron solves the problem of the SLP linearity, which can address a wider range of applications.  In the picture above, the MLP is able to learn all three logic gates including the “XOR”, the two dots classes can’t be separated by one line. Professor Marcelo implemented an MLP code with a single hidden layer, available on Matlab repository, which has an example of an MLP learning the behavior of a XOR gate.

mlp

Image source: http://www.mdpi.com/

Continue reading