Loading [MathJax]/jax/output/HTML-CSS/jax.js

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×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!




- RGS

Become a Patron!
Teaching a robot how to vacuum clean with genetic algorithms! Teaching a robot how to vacuum clean with genetic algorithms! Reviewed by Unknown on August 20, 2018 Rating: 5

No comments:

Powered by Blogger.