Making a robot learn how to move, part 1 — Evolutionary algorithms
How nature inspires engineering.
This is the first part or a series of posts. To have a short introduction, read my Intro post. You can find the code for this project on this GitHub repository.
It is not rare for technology and engineering to take inspiration from nature’s great designs. In this post, I will talk about genetic or evolutionary algorithms, their role in robotics, and more widely in computer science. Evolutionary algorithms are inspired by the natural process of evolution and natural selection. Evolution is a widely known theory, that explains how animals adapt to their surroundings and environments, developing particular body features that make them more suitable to that environment. This happens when parents generate offrspring, with a mixture of their genes. Genes also undergo to random changes: this means that new generations of creatures can develop new peculiar features that make them more fit to the environment. The survival of the fittest explains that those animals tend to live longer and reproduce, generating a new generation with the same evolved genes.
How can we use this fascinating idea? Evolutionary algorithms are based on the same concepts.
Imagine you have a problem, and you want to find a solution. Every possible solution is made by a series of parameters, w. We then define a fitness function, h(w). This function defines how good it’s our solution, i.e. our combination of parameters. Given initial random solutions, how do we find better solutions? As evolution suggests, we select and combine the best performing solutions, finding a new one that shares parameters with both. After this, we make a small random mutation in those parameters. We repeat those steps several times finding a new generation of solutions, and we measure how good those are using the fitness function. After some iterations selection, genetic combination and random mutaments will generate solutions that have very high performances. Pretty amazing, right?
These algorithms can be used to evolve a controller for the robot that can make it move with high precision, even if we don’t have physical informations about the robot.
First, a brief introduction of the task: trajectory tracking is a common task for robotic manipulators. We want each of the joints of the arm to follow a predefined trajectory in time. The problem is that we don’t know which torques to use on these joints to make them follow precisely this trajectory, since moving one could interfer with the movement of the other due to dynamical coupling. So how can we find a function that defines a mapping between the current state of the robot, the desired movement of each joint, and the torque needed in that state to achieve that movement? Mathematically, it is defined as f(state, acceleration desired) -> τ, and is normally obtained by the inverse dynamical model. As an example, imagine this: you have a robot arm made of 3 joints. Each joint has a particular angle, let’s say 0º each one. At time step t+1, your desired trajectory wants the angles to be -1°,0º,1º. Thus, you want the first to have a negative angular acceleration, the second zero acceleration, and the third a positive one. Which torques do you need to give as input to achieve this? One could say, well, a negative one, zero, and positive one. But it’s not that easy: due to dynamical coupling, the second joint will move anyway if the others move, so you need a torque even to have zero acceleration to balance dynamical effects!
A way to approximate any non-linear function with a series of parameters is using neural networks. Neural networks can approximate any kind of function with a series of weights, doing matrix multiplications and using non linearities. But how can we find the right weights/parameters that achieve exactly our desired function? Usually, NNs are trained using gradient descent algorithms like backpropagation. The problem, in our case, is that the error of the network is not differentiable: that means that, when it receives in input the current state and desired acceleration, it outputs a particular torque. But we do not know which should have been the actual torque to give the system. We do not have the true values that are used in classic supervised learning to compute gradient descent. This means we don’t know how to tune our parameters, we don’t know the correct direction that is usually found using partial derivatives to make the error smaller.
Select the best solutions, combine and evolve the parameters, and test the new solutions, storing the best ones
This is where evolutionary algorithms become very helpful. As said, we can see how good a solution is (i.e. the parameters of our network that outputs desired torques) by computing how far the trajectory of the robot is far from the desired one (basically, we integrate the norm of the position error at each time step) We can then combine and randomly mutate the parameters of the best performing combination of parameters, i.e. the genes. At each iteration, we create new solutions evolving the best ones. We then run this genetic controller on our robot to make it follow our trajectory, computing the total error. If the error is lower than before, we have a new best solution that we store and try to evolve further! The steps are the same at each iteration: select the best solutions, combine and evolve the parameters, and test the new solutions, storing the best ones. In this way, by genetic evolution, we find the best set of weights for our neural network, thus evolving a neuro-controller in a bio-inspired way.
It’s interesting to see how a small neural network, with just 2 hidden layers and around 80 neurons, is able to evolve into a powerful controller with evolutionary algorithms, without the need to compute a single derivative, in just around 50 iterations. The robot is thus evolving step by step, discovering new ways to move and follow the trajectory.
Here I show a desired trajectory (in blue) and how the robot follows it with a classic PD controller, or with a genetically evolved neural network controller (in red). Notice the different interesting behaviors of the latter. The robot starts both in a wrong position and with a wrong velocity, going in the opposite direction, so the controllers have to make a turn.
In this post I briefly described how a collegue of mine and I developed a neuro-controller for a robot, allowing it to move in a precise way even without knowing anything about the dynamic model of itself, using bio-inspired algorithms. You can find all the code for this project in this GitHub repository.
In the next posts, I will show other techniques to achieve the same result, using new approaches. Feel free to comment or ask questions about anything!
