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?

Kicking off the Akka Workshop at Sektor5, Vienna

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.

Scala Akka Workshop Robot

The environment of the robot: a 10×10 field surrounded by walls. The robot has to pick up as many cans as possible.

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.
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.

Developers who connected their laptops to the cluster

Developers who connected their laptops to the cluster

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.


Wolfgang explaining the robot problem and evolutionary algorithms

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!

Best robot and its generations history. 10 people contributed to this robots evolution.

Best robot with fitness 97980 and its generations history. 10 people contributed to this robots evolution.

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 😉



This entry was posted in Akka, Play framework, Scala, Slick. Bookmark the permalink.
  • Nikolay Kushin

    For me personally it is still unclear why there is “a total of 128 different situations” :) As I thought it should be 3^4 * 2 = 162 (4 surrounding cells with 3 possible states plus cell with robot containing can or clear), shouldn’t it be? :)

    • Nikolay Kushin
    • // Christian Papauschek

      Good thinking. The reason is that we excluded cases with 3 and 4 surrounding walls, which are (2 + 2 * 2 * 4 = 18), and cases with 2 opposite walls (2 ^ 4 = 16), which makes 162 – 18 – 16 = 128 😉

      • Nikolay Kushin

        This condition doesn’t work on fields 1×1, 1xN and Nx1 😉 Why did you do this restriction? For optimisation reasons or something else?

        • // Christian Papauschek

          Yes, call it premature optimization 😉 I wanted to be careful to send as little data as possible over the wireless network, so the RobotCode had to be as small as possible.

  • Pingback: This week in #Scala (03/03/2014) | Cake Solutions Team Blog