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/

The MLP architecture consists of Perceptrons the same as mentioned before, with weights for each input and an activation function at the output of each neuron. There are three types of layers, the inputs are just regular values which don’t implement a Perceptron, the hidden layers and output layers are Perceptrons. The length of the Hidden Layers can vary from any value bigger than zero.

To find the optimal weights for all those nets, it is needed to apply a training algorithm. The training algorithm will approximate the inputs to the desired outputs and converge to find the best function to suit those solutions. For our robot control, a Matlab toolbox will be used and its code will be explained:

The code begins with the input data “X” which can be referred to the input layer. The X matrix comes with different inputs “p” for the lines and multiple input sets “N”. The bias is after inserted on all input sets for the Neuron threshold.

[p N] = size(X);
bias = -1;
X = [bias*ones(1,N) ; X];

The MLP implemented consists of only one hidden layer. The hidden layer weights for each Neuron are represented at the “Wx” matrix, the weights for the output layer are represented by the “Wy” matrix. “Tx”, “WxAnt”, “Ty”, and  “WyAnt” are temporary variables to support the code flow. “DWy” and “DWx” are helpers for the backpropagation used further. “MSETemp” stores the error between the expected output and the output got into a vector, which can be plotted to see the algorithm efficiency.

Wx = rand(H,p+1);
WxAnt = zeros(H,p+1);
Tx = zeros(H,p+1);
Wy = rand(m,H+1);
Ty = zeros(m,H+1);
WyAnt = zeros(m,H+1);
DWy = zeros(m,H+1);
DWx = zeros(H,p+1);
MSETemp = zeros(1,epochMax);

The code uses a random permutation between the inputs. The permutation helps the learning machine not to be addicted for an input sequence.


k = randperm(N);
X = X(:,k);
D = D(:,k);

“V” matrix stores the results for each Neuron on the hidden layer, considering their weights, bias, and inputs. The sigmoid function is widely used as an activation function for the MLP network. “Z” matrix implements the sigmoid function for the hidden layer outputs.


V = Wx*X;
Z = 1./(1+exp(-V));

“S” stores the inputs from the output layer, which are the outputs of the hidden layer plus the selected bias. “G” calculates the resulting output with the inputs and weights, “Y” finally applies the activation function for the “G” results. The process until now implemented a Feedforward calculation, to know the outputs received from a set of inputs based on the system weights.

S = [bias*ones(1,N);Z];
G = Wy*S;

Y = 1./(1+exp(-G));

The MLP function error is calculated based on the desired outputs “D” and the outputs got “Y”. A quadratic function is applied to the result “E” for a better approach to analyzing the error, the error is reduced as it is closer to zero.


E = D - Y;

mse = mean(mean(E.^2));

The MLP uses the backpropagation method to update its weights. The backpropagation is based mainly on the gradient descent approach to finding the optimal weights for the approximation function. The sigmoid activation function is widely for its derivative calculation, it requires a low computational effort that speeds up the training process.

“df” stores the sigmoid derivative, “dGy” and “DWy” are keys for the backpropagation algorithm, “mu” is the learning rate. “Wy” is refreshed with the new weights. the “alpha*WyAnt” applies an inertial term to the calculation which helps the algorithm to find the global minimum solution.


df = Y.*(1-Y);
dGy = df .* E;

DWy = mu/N * dGy*S';

Ty = Wy;
Wy = Wy + DWy + alpha*WyAnt;
WyAnt = Ty;

Similar to the previous approach, but now calculating the new weights for the hidden layer. The errors of the hidden layer can’t be compared to the expected error of the whole system, so the backpropagation uses the approach presented at the “dGx” line, “(Wy’ * dGy)” in the place of the “E” error shown before.

df= S.*(1-S);

dGx = df .* (Wy' * dGy);
dGx = dGx(2:end,:);
DWx = mu/N* dGx*X';
Tx = Wx;
Wx = Wx + DWx + alpha*WxAnt;
WxAnt = Tx;

A robot navigation can be implemented from an MLP for practical application, the Matlab tool box for the simulation environment “iRobot Create” is available at: https://sourceforge.net/projects/createsim/.

iRobot

The idea is to use the available sonar sensors located at the right, front and left sides to allow the robot to make decisions on moving inside the room. The robot moves with two wheels located at the left and right, and the wheels speed can be controlled separately. To do so, it is needed to gather different inputs representing the distances the robot is reading, and from those distances, choose both wheels speeds

The MLP needs to be trained to interpret different distance inputs and return a valid motion to the wheels speed. To do so, it is required to analyze different robot positions and collect their inputs and desired action, the MLP will approximate those choices and implement a “magic” function which can return outputs with inputs that were not listed, closer to the training set.

The “ReadSonarMultiple” function inside the iRobot toolbox returns the robot Sonar readings for the distances. “SetDriveWheelsCreate” sets the speed of the robot wheels, between -0.5 and 0.5 speeds, in the example shown, the robot would spin in its center in a clockwise rotation.


front = ReadSonarMultiple(serPort,2);
right = ReadSonarMultiple(serPort,1);
left = ReadSonarMultiple(serPort,3);

SetDriveWheelsCreate(serPort,0.5,-0.5);

The first approach to collect a training set was manually controlling the robot around the room and registering the distance and speed every time a wheel speed changed. It caused a problem because since the controlling was not rigorous, ambiguous data appeared which means one input could have two different outputs. It caused the MLP training not to converge, and the robot would not navigate properly.

The best solution came by placing the robot at different positions, especially for critical situations, also trying various matchings of input distances and output speeds. Depending on the chosen training set, the robot could find a stable state where the wheels speed tended to zero or even being stuck at a wall corner.

The Matlab toolbox developed by professor Marcelo has a function called “trainMLP” which takes different parameters to find the best weights for a training set.


function [Wx,Wy,MSE]=trainMLP(p,H,m,mu,alpha,X,D,epochMax,MSETarget)

% Input parameters:
% p: Number of the inputs.
% H: Number of hidden neurons
% m: Number of output neurons
% mu: Learning-rate parameter
% alpha: Momentum constant
% X: Input matrix. X is a (p x N) dimensional matrix, where p is a number of the inputs and N is a training size.
% D: Desired response matrix. D is a (m x N) dimensional matrix, where m is a number of the output neurons and N is a training size.
% epochMax: Maximum number of epochs to train.
% MSETarget: Mean square error target.
%
% Output parameters:
% Wx: Hidden layer weight matrix. Wx is a (H x p+1) dimensional matrix.
% Wy: Output layer weight matrix. Wy is a (m x H+1) dimensional matrix.
% MSE: Mean square error vector.

Not only having a good training set, to have a satisfactory solution to converge, but the parameters such as the learning rate, momentum, number of hidden neurons and number of iterations should also be appropriately chosen. There is not an optimal set of parameters for every application. The code below lists the procedures and parameters used to have an acceptable solution. “matmap()” function converts the wheels speed parameters (-0.5 to 0.5) to the sigmoid function limits (0 to 1). In the end, the weights are saved into a .mat file to be used in the script that controls the robot.


p = 3; % Number of inputs - 3 sonars
H = 16; % Number of hidden neurons
m = 2; % Number of output neurons - left and right wheels speed

mu = 7; % Learning rate
alpha = 0.000000000001; % Momentum parameter

epoch = 100000; % Number of iterations
MSEmin = 10e-20; % Minimal error threshold

X = [3.0 3.0 3.0 2.0 1.0 0.2 3.0 3.0 3.0 3.0 0.2;   %right sonar
     3.0 0.5 0.1 3.0 3.0 3.0 3.0 3.0 3.0 0.2 0.2;   %front sonar
     3.0 3.0 3.0 3.0 3.0 3.0 2.0 1.0 0.2 0.2 3.0;]  %left sonar

D = [0.5 0.4 0.3 0.4 0.4 0.5 0.4 0.4 -0.2 -0.5 0.5; %right wheel
     0.4 0.2 0.0 0.4 0.4 -0.2 0.4 0.4 0.5 0.5 -0.5;]%left wheel
D = matmap(D);

[Wx,Wy,MSE]=trainMLP(p,H,m,mu,alpha,X,D,epoch,MSEmin);
semilogy(MSE);

save('weights','Wx','Wy')

The source file can be found in:

https://github.com/YangTavares/Deep_learning/blob/master/iRobot_YangT/icreator_test.m

The graph below plots the mean square error of the training algorithm for each iteration:

mse

To run the robot in the room, the simulator GUI is opened, and the file on GitHub is loaded: https://github.com/YangTavares/Deep_learning/blob/master/iRobot_YangT/Custom%20Files/robot_learn_control.m

The video below shows the trained MLP used to control the navigation of the robot in the room, the green lines represent the Sonar sensors:

Different maps were tested, and a red trace is plotted to show where the robot moved in approximately 3 minutes:

nav_1

nav_2

nav_4

It is important to mention that there are a variety of Machine Learning methods to implement this and the MLP may not be the best one to suit for this application, but it ‘s nice to show an application of the algorithm and how it behaves for the specified problem.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s