Scala Akka Workshop – Evolving a Robot in an Actor Cluster

It is quite extraordinary what is possible nowadays with a group of interested developers and powerful tools such as Scala and Akka.

Three months ago we had our first Akka Workshop here at the Vienna Scala User Group (VSUG), in which 25 developers participated in a real-time networked programming challenge. They had to compete in the non-zero-sum game of Prisoners Dilemma, which was powered by a central host, and network communication implemented with Akka.

Building an Akka Cluster

In the second workshop I wanted to raise the stakes a bit: what if we could make use of Akka’s clustering features? What if we could develop a cluster and a distributed algorithm on top of that cluster, during a 3 hour workshop?

Rafael, co-organizer of the VSUG, found a programming challenge that would be perfect for the task: a robot that has to navigate a grid-like environment and collect cans to get points. He got the idea from the book Complexity: A Guided Tour by Melanie Mitchell.

The challenge was that the robot could only see a few surrounding cells, and it’s difficult to determine the best decision to make in each situation. The robot has no memory and has to act quickly – it has only 200 turns to pick up all the cans.

Tricky: the robot can only see its immediate surroundings (walls and cans). This makes a total of 128 different situations. In each of these, it can do one of 6 things: Go Up, Down, Left, Right, PickUp a can or Walk Randomly.

The main reason this task was perfect because the author of this particular robot challenge used evolutionary algorithms to find the best programming for the robot. And evolutionary algorithms can easily be distributed in a cluster.

First Steps during the Workshop

We prepared the workshop in a similar manner to the last one – there was a public GitHub repository for everyone to get started quickly. This time, a lot of the logic necessary for evaluating a robot for an evolutionary algorithm was already implemented. But everything else had to be done during the workshop: the Akka cluster itself, and the evolutionary algorithm on top of it.

In the first hour we tried to get the cluster running. Akka’s clustering implementation is pretty straightforward – after exchanging a few IP addresses, we could already see a few machines pop up on our cluster visualization.

But there was something odd: a few machines dropped out of the cluster after a while, and stopped receiving messages from other machines. After a little bit of investigation, we found out that not everyone could ping other machines in the wireless network we used. It was pretty weird, considering that no-one had problems reaching my laptop, or connecting to the internet. It seemed to be some kind of network split.

Luckily, Yves, owner of Sektor5 where the event was hosted, explained to me that some Linux network drivers have issues with wireless routers broadcasting in multiple frequencies, and ultimately we could solve the problem by forcing those clients to use 2.4 Ghz.

Starting the Robot (R)evolution

After addressing some of the networking problems, the basic Akka cluster was running and we could focus on implementing the distributed evolutionary algorithm.

The basic idea was this: developers could create solutions to the robot problem, and broadcast them to the cluster. Robots were simply represented by a list of 128 decisions (one for each situation it could encounter). As shown before, in each of those situations the robot could either go Up, Down, Left or Right, PickUp (a can) or move randomly.

So it was simple to create initial solutions to the problem. Also, code was provided to evaluate those solutions and calculate the number of points each robot would get. The robot would be evaluated on 20 different fields of size 10×10, and got points for each can it collected (or minus points for running into walls).

Now the challenge was to combine solutions to create better ones, in the spirit of evolutionary programming. Wolfgang was careful to introduce everyone to the basics of genetic operations, so that everyone would know how to implement the basic algorithm.

The initial, randomly created robots performed poorly and started with negative points as low as -100k for running against walls, and trying to pick up cans that weren’t there. Quickly, however, the first positive solutions appeared on the screen and reached up to 90k points. This was already a 90% solution to the problem. The best solution, collecting all cans (which is probably not possible), would be 100k points.

Once a robot solution was created in the cluster, they were broadcasted to everyone else so others could base their solutions on them. We also tracked the evolutionary origin of robots, so we could see how often solutions jumped from cluster node to cluster node, and how many improvements happened on each machine.

On this particular robot,  we already saw several developers contributing to its evolution. We watched for a few minutes to see if it would evolve to achieve even more points – or “higher Fitness”, as it is called in evolutionary programming lingo. But it seemed to be stuck, and not improving at all.

Mutant Robots to the Rescue

So it seemed we were stuck in a local optimum, something very common with evolutionary algorithms. If there is not enough randomness in the system, solutions quickly converge to a solution that cannot draw on other “approaches”, because it was evolved from a very limited set of solutions.

We thought that increasing the randomness, or “mutation rate” in our system, could lead to a better solution. Also, we decided to throw away our current population, reset the cluster, and start from new.

After everyone implemented mutations, small random changes to the robots decisions, we watched the cluster start with new solutions, slowly improving and getting over the 50k points mark. From then it quickly reached again 90k, but this time it did not stop there.

Final Solution

The robot improved more and more, and finally stopped improving at 97980 points – that’s almost 98% of the cans collected!

Impressive – I didn’t think that we would actually get a solution that was so good, in such a short time! In just three hours our 26 participants implemented a cluster with Akka, and an evolutionary algorithm on top of it.

Philip, who contributed most to the final solution, put his code on a GitHub repository. Thanks for sharing!

In Philip’s Actor implementation we can see that he regularly broadcasted the best robot to the cluster, for everyone to improve on it. Also, he added other robots received from the cluster to his population, and he always kept the best 100. By constantly sending himself CrossoverRandomRobots messages, he made sure that his CPU was fully utilized and evolving.

Excerpt of Philip’s evolutionary algorithm implementation:

  def receive = {

    case SendBestRobot =>
      broadcast ! population.head
      ...

    case robot: Robot => addToPopulation(robot)

    case CrossoverRandomRobots =>
      val code1 = randomRobot.code
      val code2 = randomRobot.code
      val cut = Random.nextInt(code1.code.length)
      val crossedCode = code1.code.take(cut) ++ code2.code.drop(cut)
      addToPopulation(RobotCode(crossedCode, "Philip", List(code1, code2)).evaluate)
      self ! CrossoverRandomRobots

    ...

We can see that he crossed-over the code of two random parent robots, cutting them at a random position and recombining them. The mutation code (not shown here) was also very interesting. His strategy was to go through every single position in the robot code, and see if a random replacement of that number resulted in a better robot. It seems it wasn’t necessary to mutate more than one number at the same time. Check out the full code for more details.

Behind the Scenes

One of the big challenges was to provide a simple API for the developers, that can be quickly understood in the timeframe of a workshop. Judging from what people told us after the workshop, we succeeded in reducing accidental complexity. So nobody had any troubles understanding how the evolutionary algorithm can be implemented.

Thanks everyone for participating in this workshop, it was a lot of fun. I also want to thank all the organizers of the VSUG who made this workshop possible, especially Wolfgang and Rafael.

Wolfgang, who made a talk about genetic algorithms previously at the VSUG, helped create the quickstart code base for the workshop, as well as the code for visualizing the robots behavior – thanks a lot for helping out! This made it possible to show the behavior of the clusters best robots live on the video projector.

Many thanks go to xTradesoft for sponsoring all the drinks and the delicious food and cakes. Finally, thanks go to Sektor5 for hosting us and for providing great technical support during the event 😉

Links

• The Akka Workshop Meetup Page
• YouTube Video of the robot with the highest fitness
• Philip’s implementation of the distributed evolutionary algorithm
• Melanie Mitchell – Complexity: A Guided Tour (the book where we got the robot idea from, see page 130)
• Cluster Visualizer (the Play Framework app that listens to the cluster and shows the best robots)
• Quickstart Scala Project (the code the participants used as a starting point)