Teaching a robot how to vacuum clean with genetic algorithms!

< change language

In this post I want to showcase the beginning of what I think will be a really cool project. After reading a really nice book (that Bill Gates himself recommends) on machine learning, I decided to experiment with genetic algorithms.

For that matter, the main goal here will be to develop a genetic algorithm that teaches a vacuum cleaner how it should move in a dirty room to clean it in the best way possible (that is what is happening in the animation above). The first step is to define what I mean by room: a room will be a rectangular grid where each cell has a number from $0$ to $1$. A cell with a $0$ is perfectly clean and a cell with a number $1$ is as dirty as a piece of floor can get. Below we see a $5\times 5$ room with a robot (in red) already in the middle of the room:

As I read in The Master Algorithm (and frankly I found it very enlightening), when one is going to use genetic algorithms we must previously define the structure of the solution and then the genetic algorithm will fill in the parameters for us.

Having said so, the genetic algorithm will try to learn a decision tree, which will be a binary tree where each node can be of one of two types:

• Action node: an action node is always a leaf in our decision tree. If we reach an action node, the robot will move according to the action value of that node;
• Sensing node: a sensing node is never a leaf in our decision tree. It has a relative position, to which the robot will look, and a threshold. If the level of dirt in the node we looked at is below the threshold, we will follow the left subtree of this node; otherwise we will follow the right subtree of this node.

As an example, consider the tree with only $3$ nodes, such that the root is a sensing node $(RIGHT+UP, 1/3)$ with left subtree an action node $(LEFT)$ and right subtree another action node $(UP)$. Say the robot is the red square on the image above. To decide where he will move next he traverses its decision tree: the root is a sensing node and so it will look to where the node says (RIGHT and UP) and will notice that there is a very dirty square. The level of dirt of that square is certainly bigger than $1/3$ which is the node threshold, so we proceed to the right subtree. The right subtree is just an action node and so we perform its action, deciding to go UP.

All robots in a population will start with random decision trees and then the genetic algorithm will keep mutating the trees! To create a random decision tree I used a recursive approach. We start by deciding if the root node is going to be an action node or a sensing node. Either way, the parameters of the node are filled in randomly. After that, if we created a sensing node we create two random decision trees and set them as the left and right subtrees of this node, but with a twist! The deeper we go, the less likely we are to create another sensing node and the more likely we are to create an action node. This is so that, in general, starting random trees are small.

With this set in place, mutating a decision tree is also simple (please bear in mind that the mutation events that I am going to describe happen with probabilities that were chosen rather arbitrarily). Again, we do this recursively by traversing the tree and deciding to mutate, or not, each node:

• If the node is a sensing node and we are going to mutate it, we can either:
  
  1. Amputate its subtrees and turn this node into an action node;
  2. Swap the left and right subtrees;
  3. Pick another value as threshold;
  4. Change the square to which we look when we reach this node.
• If the node is an action node and we are going to mutate it, we can either:
  
  1. Expand this node into a sensing node and set random decision trees as the child;
  2. Change the square to which we will move when we reach this node.

Having defined these behaviours, carrying out the simulation is easy: we create a starting population with $N$ individuals and a set of $K$ random rooms per generation. We make each robot clean each room and store their score, which will just be the sum of the cells they cleaned. We then pick the top performing $45\%$ robots. Those will proceed to the next generation and each one of them is also going to be copied and then mutated. The remaining $10\%$ of the next generation is created randomly from scratch.
Notice that this differs a bit from what I used to find on the internet in the sense that the first $45\%$ aren't mutated nor bred together, while the second $45\%$ are forced to be mutated. I took this approach because it was a bit easier than implementing a crossover algorithm for the decision trees, but I might do it as well in the future.

Either way this algorithm performs really nicely! In the end of the post you will find an animation of the best performing robot after a simulation with $100$ generations.

All the code I wrote (and am still writing) for this is available in my GitHub repo. There you can also find a small Java application for you to train your own generations of robots! You can choose the number of robots, the number of rooms each robot trains in and the number of generations. In the end it displays the animation of the best robot in a random room! Here is a screenshot of the app:

I am thinking of writing a series of blog posts as a "tutorial" on how to code all this. Would it be interesting? Let me know!!

Also, consider supporting me on Patreon if you like my content and would like extra benefits!

Neste post quero mostrar uma fase inicial daquilo que está a sre um projeto super interessante. Depois de ter lido um livro bestial sobre aprendizagem automática [ou machine learning], que o próprio Bill Gates recomenda, fiquei com imensa vontade de experimentar usar algoritmos genéticos para alguma coisa.

Foi assim que estabeleci o seguinte objetivo: desenvolver um algoritmo genético que ensina um robot a aspirar o chão de uma sala (é isso que está a acontecer na animação do início do post). O primeiro passo é definir o que é uma sala: uma sala é uma grelha retangular onde cada célula tem um número entre $0$ e $1$. Uma célula com o número $0$ está perfeitamente limpa e uma célula com o número $1$ está tão suja quanto é possível e imaginável. De seguida vemos uma imagem de uma sala $5\times 5$ com um robot (a vermelho) no centro:

Quando li A Revolução do Algoritmo Mestre (que achei francamente esclarecedor), percebi que quando usamos algoritmos genéticos temos de definir, à priori, a estrutura da solução de que estamos à procura; os algoritmos genéticos só preenchem os parâmetros.

Tendo percebido isso, decidi que o algoritmo genético ia tentar aprender uma árvore de decisão, que para este projeto seria uma árvore binária onde cada nó é de um de dois tipos:

• Nó de ação: um nó de ação é sempre uma folha na nossa árvore de decisão. Se chegarmos a um nó de ação, o robot limita-se a deslocar-se para a posição indicada nesse nó.;
• Nó com sensor: um nó com sensor nunca é uma folha. Tem indicada uma posição - para onde o robot vai olhar - e um valor numérico que serve de bitola. Se o nível de sujidade da célula para onde olhámos estiver abaixo da bitola, seguimos pela a sub-árvore esquerda, caso contrário seguimos pela sub-árvore direita.

Tome-se como exemplo uma árvore com $3$ nós apenas, onde a raíz é o nó com sensor $(DIREITA+CIMA, 1/3)$, onde a sub-árvore esquerda é o nó de ação $(ESQUERDA)$ e onde a sub-árvore direita é o nó com ação $(CIMA)$. Suponhamos que o robot é o quadrado vermelho da imagem em cima. Para decidir para onde vai temos de atravessar a árvore de decisão: a raíz é um nó com sensor, portanto olhamos para o quadrado em CIMA e à DIREITA (célula com rebordo encarnado) e notamos que é uma célula bastante escura (muito suja). O nível de sujidade dessa célula é certamente maior que $1/3$, que era a bitola da raíz da árvore. Por causa disso, seguimos para a sub-árvore direita onde encontramos um nó com ação que nos manda seguir para CIMA.

Todos os robots numa população começam com árvores de decisão aleatórias e depois o algoritmo genético vai ter a árdua tarefa de induzir mutações! Para criar árvores de decisão aleatórias usei um método recursivo. Começamos por decidir o tipo de nó da raíz e depois escolhemos os seus parâmetros aleatoriamente. Se o nó for do tipo com sensor, criamos outras duas árvores de decisão aleatórias e usamo-las como sub-árvores esquerda e direita do nó que acabámos de criar. Há apenas um pequeno detalhe: quanto mais "fundo" estivermos na árvore, mais provável é que um nó seja um nó de ação e menos provável é que seja um nó com sensor. Fazemos isto para que, em geral, as árvores aleatórias não sejam grandes.

Com tudo isto já definido é relativamente fácil de induzir as mutações nas árvores (note-se que as mutações que vou descrever acontecem com probabilidades que eu escolhi de forma relativamente arbitrária). Usamos de novo uma metodologia recursiva: atravessamos a árvore, tentando induzir mutações em cada nó:

• Se o nó for um nó com sensor, podemos:
  
  1. Amputar as suas sub-árvores e transformá-lo num nó com ação;
  2. Trocar as sub-árvores esquerda e direita;
  3. Escolher uma nova bitola;
  4. Mudar a célula para onde temos de olhar.
• Se o nó for um nó com ação, podemos:
  
  1. Transformar o nó num nó com sensor e atribuir árvores aleatórias como sub-árvores;
  2. Mudar a célula para onde nos deslocamos quando chegamos a este nó.

Com estes comportamentos definidos só falta a estrutura da simulação: criamos uma população inicial com $N$ indivíduos e para cada geração criamos $K$ salas aleatórias. Pomos cada robot a limpar cada sala e damos uma pontuação que vai ser o somatório dos valores das células que foram limpas. Da população toda, escolhemos o top $45\%$. Esses seguem para a próxima geração; são também copiados - para perfazerem outros $45\%$ da próxima geração - e nas cópias induzimos mutações. Os $10\%$ que faltam são compostos por robots novos aleatórios.
Repare-se que isto é um pouco diferente daquilo a que eu estava habituado a ver na internet: os primeiros $45\%$ não são mutados nem se reproduzem entre si, ao passo que os segundos $45\%$ são necessariamente alterados. Segui esta via porque achei um pouco mais simples do que implementar um algoritmo para reproduzir árvores de decisão... talvez o faça no futuro.

De qualquer das maneiras o algoritmo funciona bastante bem! No fim do post encontram uma animação do melhor robot de uma das simulações que fiz.

Todo o código que escrevi (e ainda estou a escrever) para isto pode ser encontrado neste repo do GitHub. Também encontram lá um pequeno executável em Java para poderem fazer as vossas próprias simulações! Pode escolher-se o número de robots na população, o número de salas em que cada geração treina e o número de gerações da simulação! No fim o programa mostra uma animação do melhor robot numa sala criada aleatoriamente. De seguida encontram uma captura de ecrã do programa:

Estou a pensar escrever uma série de posts em formato de "tutorial" sobre como programar isto. Parece-vos interessante? Dêem-me o vosso feedback!!

Já agora, considerem apoiar-me através do Patreon se gostam do meu conteúdo e se querem benefícios extra!

- RGS

Become a Patron!