lukegarrigan

Coding a Roomba

Last night as I was drifting off to sleep, I was suddenly fuelled by the urge to code my own Roomba simulation. Weird I know, and at the time it seemed like a bloody brilliant idea. I had a tonne of fun coding it, so I hope you have half as much fun reading this blog.

I thoroughly recommend having a read of this blog by Niall Connaughton, he goes through the potential algorithms to solve the Roomba problem, and even on how Roomba actually works, which I’ll touch on later.

Coding a Roomba

As I tend to do, without much thought or preparation, I jump into the coding. Trying to solve a problem without knowing any pre-existing solutions is always a fun challenge – I often imagine it’s how programmers felt before Stack Overflow, don’t know the solution to problem? Tough, try to solve it yourself. We need more of that.

This blog contains snippets of the code, exclusively for parts I deem snippet-able. All the code I write can be found here, so fill ya boots.

Let’s start off by creating our little Roomba:

Next, let’s add some code to get him moving in the direction he’s facing:

    this.pos.x += this.speed * cos(this.angle);
    this.pos.y += this.speed * sin(this.angle);

Let’s constrain him, we wouldn’t want him wondering off would we?

Next, let’s add a bit of a trail, just so we can see at the end if he’s cleaned the whole room:

    if (frameCount % 5 === 0) {
      this.trail.push({ x: this.pos.x, y: this.pos.y });
    }

...

  drawTrail() {
    for (let trail of this.trail) {
      noStroke();
      fill(0, 139, 139);
      circle(trail.x, trail.y, this.r * 2);
    }
  }

The goal

The whole point of a Roomba is to hoover the floor, so we’re gonna want to cover as much of the surface as possible. Let’s assume that Roomba has a build in grid-system, something trivial like following:

This way he can keep track of where he’s been and where he still needs to go. Let’s create a really simple algorithm, where Roomba checks for the closest location he’s not already been and heads towards it. Let’s call the locations food, as though Roomba is going to eat the dots.

for (let snack of food) {
  let d = dist(this.pos.x, this.pos.y, snack.x, snack.y)
  if (d <= closestFoodDistance) {
    closestFoodDistance = d;
    closestFood = snack;
  }
}
this.closestFood = closestFood;
this.closestFoodDistance = closestFoodDistance;

Which ends up something like this:

Not quite the straight lines I imagined, and it didn’t exactly clean the whole floor, not a happy customer.

In order to solve this I’m going to add a weight to make Roomba prioritise moving forward over going to the closest food. Even though the distance between the food directly in front of Roomba and the food directly to his side is technically the same, which ever one is in the list last gets chosen.

Let’s add this weight:

    for (let snack of food) {
      let d = dist(this.pos.x, this.pos.y, snack.x, snack.y);
      let angle = atan2(snack.y - this.pos.y, snack.x - this.pos.x);
      let angleWeight = abs(angle - this.angle) * 50;

      if (d + angleWeight <= closestFoodDistance) {
        closestFoodDistance = d;
        closestFood = snack;
      }
    }

    this.closestFood = closestFood;
    this.closestFoodDistance = closestFoodDistance;

Which, when finished looks like:

There’s still some unacceptable gaps, let’s sort that out – by increasing the density of the locations, i.e. giving him more food.

Much better, still not perfect, but it’ll do.

Obstacles

Our Roomba wants a bigger challenge. A blank canvas just isn’t enough for him any more, let’s add some complexity. I’m going to add some brilliantly designed furniture:

Roomba isn’t happy, he wants to clean on top of that table but the world I’ve created for him won’t allow it.

I need to create a mechanism that will determine whether a location is possible to get to, and if it’s decided that in fact Roomba can’t jump on the table, then he’ll have to look for another location.

The basic idea of my solution is, head towards a location, if you’ve not made much progress on that location in the past X amount of time, remove that item from the locations list.


  checkMakingProgress() {
    const d = dist(
      this.pos.x,
      this.pos.y,
      this.closestFood.x,
      this.closestFood.y
    );

    if ((new Date()) - 100 > this.closestFoodTime && (d + 0.01) >= this.closestFoodDistance) {
      food = food.filter(e => e !== this.closestFood);
      this.closestFood = null;
    } else {
      this.closestFoodDistance = d;
    }
  }

And there we have it, we’ve built a Roomba that can clean a room, more or less.

How a Roomba works

Of course Roomba is much more sophisticated than the algorithm I’ve created here. The first thing Roomba does is it calculates how big the room is, once obtained it’ll calculate the estimated time it’ll take to cover the whole floor.

According to this post:

When it starts you’ll notice a spiral pattern, it’ll spiral out over a larger and larger area until it hits an object. When it finds an object, it will follow along the edge of that object for a period of time, and then it will start cris-crossing, trying to figure out the largest distance it can go without hitting another object, and that’s helping it figure out how large the space is, but if it goes for too long a period of time without hitting a wall, it’s going to start spiraling again, because it figures it’s in a wide open space, and it’s constantly calculating and figuring that out.

It’s similar with the dirt sensors underneath, when one of those sensors gets tripped it changes its behaviors to cover that area. It will then go off in search of another dirty area in a straight path. The way that these different patterns pile on to each other as they go, we know that that is the most effective way to cover a room.

The patterns that we chose and how the algorithm was originally developed was based off of behavior-based algorithms born out of MIT studying animals and how they go about searching areas for food. When you look at how ants and bees go out and they search areas, these kinds of coverage and figuring all of that out comes from that research. It’s not exact, obviously, I’m not saying we’re honeybees, but it’s that understanding of how to search out an area in nature that is the basis behind how our adaptive technology is developed.

https://electronics.howstuffworks.com/gadgets/home/robotic-vacuum2.htm

What to do next

Conceivably, the algorithm I created could be used on any size room, but its efficiency would be somewhat questionable. It’d be interesting to implement Roomba’s spiralling technique and see how much it improves coverage/speed. I should note, that there are other hoover companies that take a completely different approach to Roomba, investigating those could be a fun challenge too.

Leave a Reply