Robot uprising

On a slightly off-topic note there is a new member in our household nowadays. A little cheerful doomsday machine, playing joyous sounds, driving crazy and happily bumping into stuff. They call it Roomba.

Its official purpose is to clean things up and while its cleansing powers are quite limited, its effect on the overall tidiness of the apartment is astonishing. That is because we adapt. That’s right, we – the humans – adapt to the robots. Why? Well, the before mentioned Roomba makes a real mess out of the mess you left behind. You basically have to tidy up before you can make use of it.

So basically what will happen is that human environments and humankind itself will adapt to all those tiny little helpers called robots, for instance by lowering the stairs and placing navigation beacons everywhere. And while we laugh about the forthcoming robot uprising as of now, rest assured that i will happen and it will be bad. The Roomba reminds me of that fact with a certifying swirl every day.

A modular window class (Part 1)

While I was preparing C++ code for tutorials eventually leading to different form of collision detection the very basic problem of creating and displaying a simple window occurred. I haven’t completely solved it yet but I’d like to share some intermediate insights.

It was certainly not the first time of me thinking about a window system and of course many different libraries exist that already solve the problem. Nonetheless I wanted to do it by myself mostly out of two reasons:

  1. I want to keep the dependencies for the tutorial code as low as possible, and
  2. I find it quite instructional to solve the problem from scratch.

To make things more complicated I wanted the solution to be reusable, modular and cross platform, each in the best spirit of C++. I opted to only use Xlib and Win32 as base libraries for my window system. Read more about the consequences of these decisions in the next part of this series.

Introduction

I’ve created this blog to provide an easy-as-can-be way for me to publish things of interest. This should also push me to write down many more-or-less elaborate ideas of mine. These mainly fall into the field of coding like artificial intelligence, genetic algorithms, collision detection & response, operational transformation and the like. I the end i hope to establish a bunch of tutorials in the spirit of my old (read: ancient) site on Counter-Strike mapping. Let’s see if it works out.

Diplomarbeit

Auswertung von XPath-Ausdrücken auf der Basis von CUDA

Die generische Auszeichnungssprache XML ist mittlerweile als ein Standardformat für strukturierte Daten etabliert. Zahlreiche Anwendungen verwenden XML-basierte Sprachen zum Speichern und Austauschen von Informationen. XML-Kommunikation bildet die Grundlage für Webdienste und -anwendungen. XML-Datenbanken ermöglichen es, große Mengen strukturierter Daten vorzuhalten und bereitzustellen.

Als Kernkomponenten der standardisierten XML-Verarbeitung haben sich XML Schema, XSLT und XQuery herausgestellt. Mit XML Schema können XML-basierte Sprachen spezifiziert und die Konformität von XML-Dokumenten bezüglich eines Schemas validiert werden. XSLT ermöglicht die Umwandlung von XML-Dokumenten zwischen verschiedenen XML-basierten Sprachen. XQuery ist eine Abfragesprache für XML-Datenbanken.

Diese Kernkomponenten werden in einer Vielzahl von Anwendungen und Diensten verwendet. Daher ist es wichtig, dass sie XML-Daten schnell verarbeiten können. Dies ist aufgrund zunehmender Komplexität und wachsenden Datenmengen keine leichte Aufgabe. Zwar ist zeitgleich auch die theoretisch verfügbare Rechenleistung stetig gestiegen, aber zumindest in den letzten Jahren hauptsächlich durch veränderte Rechnerarchitekturen. Mehrkern-Prozessoren und generisch nutzbare Grafikkarten sind inzwischen weit verbreitet.

Insbesondere die theoretische Rechenleistung moderner Grafikkarten ist in den letzten Jahren stark gestiegen und übertrifft die vom Hauptprozessor mittlerweile um mehrere Größenordnungen. Durch Frameworks wie CUDA von NVIDIA oder das Stream SDK von AMD lassen sich die Ressourcen von Grafikkarten auch für andere Anwendungen als Grafikberechnungen verwenden. Seit kurzem existiert mit OpenCL auch ein herstellerübergreifendes Framework.

Trotzdem lassen sich bestehende Anwendungen nicht ohne Weiteres auf die Grafikkarte portieren. Der Grund dafür ist, dass die verwendeten Algorithmen und Datenstrukturen häufig nur für die übliche von-Neumann-Architektur mit einem Hauptprozessor und einem Arbeitsspeicher effizient sind. Heutige Grafikkarten haben allerdings eine massiv-parallele Architektur mit hunderten von Prozessoren und Hierarchien von verteiltem Speicher.

Das Problem besteht also darin, die parallele Rechenleistung moderner Grafikkarten auszunutzen, um XML-Verarbeitung zu beschleunigen. Dazu identifizieren wir XPath als gemeinsam verwendete Schnittstelle in der XML-Verarbeitung, analysieren deren Funktionalität und entwickeln einen effizienten parallelen Algorithmus. Dieser wird im CUDA-Framework implementiert und zu Testzwecken in den XSLT-Prozessor Xalan integriert. Die Korrektheit des Algorithmus wird formal bewiesen.

Auswertung von XPath-Ausdrücken auf der Basis von CUDA (PDF)

Efficient Neural Network Pruning during Neuro-Evolution

A paper based on my student research project got published at the International Joint Conference on Neural Networks, IJCNN 2009. The conference is held jointly by the International Neural Network Society INNS and the IEEE Computational Intelligence Society – the two leading professional organizations for researchers working in neural networks. The paper can be found at the IEEE CS digital library. The abstract reads as follows:

In this article we present a new method for the pruning of unnecessary connections from neural networks created by an evolutionary algorithm (neuro-evolution). Pruning not only decreases the complexity of the network but also improves the numerical stability of the parameter optimisation process. We show results from experiments where connection pruning is incorporated into EANT2, an evolutionary reinforcement learning algorithm for both the topology and parameters of neural networks. By analysing data from the evolutionary optimisation process that determines the network’s parameters, candidate connections for removal are identified without the need for extensive additional calculations.

Efficient Neural Network Pruning during Neuro-Evolution (PDF)

Studienarbeit

Der Einfluss neuronaler Topologien auf die Effizienz der Parameteroptimierung

Die Optimierung großer Neuronaler Netze ist im allgemeinen schwierig. Gründe dafür sind die große Anzahl einstellbarer Parameter (Curse of Dimensionality) und die oft schlechte Kondition des Optimierungsproblems. Verfahren zur Parameteroptimierung dieser Netze sind daher manchmal ineffektiv, häufig aber weniger effizient als bei kleineren, gut konditionierten Problemen. Ziel der Arbeit ist es, ein Verfahren zu entwickeln mit dem die Anzahl der Parameter reduziert und die Kondition verbessert werden kann, ohne den Fehler des Neuronalen Netzes zu verschlechtern.

Wir erzeugen Neuronale Netze mit EANT2. Die Netztopologie wird dabei durch einen Genetischen Algorithmus erstellt, die Parameter werden mit CMA-ES optimiert. EANT2 wurde bereits erfolgreich auf verschiedene Problemstellungen, wie Visual Servoing und Edge/Corner Detection angewandt. Unsere Versuche mit verschiedenen Problemstellungen haben gezeigt, dass die Neuronalen Netze schnell auf eine Größe von etwa 100 Neuronenverbindungen anwachsen, von denen einige unnotig sind, und dass die Netze schlecht konditioniert sind.

Der Einfluss neuronaler Topologien auf die Effizienz der Parameteroptimierung (PDF)