Das Autorennspiel Torcs glänzt schon in der Standardinstallation mit vielen Strecken, Perspektiven und einem modularen Aufbau, der auch Client-Server-Szenarien für akademische Wettbewerbe ermöglicht. Die 3D-Engine und KI-Integration sind ausgereift und halten auch höheren Ansprüchen stand. Das aktuelle Linux-Magazin (Tim Schürmann, "Auto-Fahrschule", Linux-Magazin 09/2010) beschäftigt sich mit dem Erstellen und dem Steuern künstlicher Rennwagen. Eine wichtige Rolle dabei spielen deutsche Universitäten, deren Teams auf KI-Konferenzen wie der GECCO und der CIG mitfahren. Linux-Magazin Autor Tim Schürmann hat mit Matthias Linhardt und Martin Butz von der Psychologischen Fakultät der Universität Würzburg zwei deutsche KI-Spezialisten zu Ihrem Engagement bei den Weltmeisterschaften und technischen Details der Bot-Programmierung befragt.

Linux-Magazin: Wie funktionieren die künstlich intelligenten Rennfahrer unter Torcs? Gibt es in den Wettbewerben Unterschiede zum "normalen" Rennspiel?

Martin Butz: Der Controller (auch Client genannt) ist der Codeteil, den die Teilnehmer schreiben und der den Rennwagen in der TORCS-Spielwelt steuert. Er ist sozusagen der virtuelle Fahrer. Er unterscheidet sich jedoch vom regulären Torcs-Bot, von dem mehrere in der Standard-Torcs-Installation enthalten sind. Im Wettbewerb verfügen die KIs über keinerlei globales Streckenwissen (also auf welcher Strecke er fährt, wie die nächste Kurve aussieht, wo die Ideallinie ist, wo welcher Gegner sich aufhält, wo auf der Strecke er sich befindet.
Im Competition-Setup von Torcs, wie es in der Simulated Car Racing Championship und unserem neuen Demolition Derby Verwendung findet, erhält der Controller nur begrenzten sensorischen Input. Der umfasst nur lokale Sensorik, wie sie auch an einem echten Fahrzeug technisch realisierbar wäre zum Beispiel durch Streckenrandabtastung über Range-Finder-Laser, eigene Vor- und Seitwärtsgeschwindigkeit, Radgeschwindigkeit, oder die Motordrehzahl.

Abbildung 1: Schon in der Standardinstallation bringt Torcs zahlreiche Rennstrecken mit. Darunter sind auch einige Offroad-Tracks, hier im staubigen Outback Australiens.

Linux-Magazin: Sie sind also der Veranstalter des Demolition Derbys, während italienische Hochschulen die SCRC ausrichten?

Martin Butz: Die Italiener richten die SCRC hauptamtlich seit 2008 aus. Dieses Jahr sind wir das erste mal mit dabei und haben vor allem zu der realistischeren Sensorik beigetragen. Zum Beispiel sind jetzt die Distanzsensoren verrauscht und es gibt noch einen zusätzlichen Fokussensor mit einer genaueren Auflösung, der aber gleichzeitig langsamer reagiert. Er liefert nur einmal pro Sekunde neue Informationen. Das Demolition Derby war meine Idee und wird jetzt zum ersten Mal angeboten - Matthias und ich sind dabei die Hauptverantwortlichen.

Linux-Magazin: Wie kamen Sie darauf, einen Torcs-KI-Wettbewerb auszurichten?

Martin Butz: Auch wir kamen von der Teilnehmerseite und waren begeistert von der Herausforderung, nur mit lokaler Sensorik arbeiten zu müssen. Unser Controller COBOSTAR gewann dann zwei der drei Austragungen 2009, woraufhin der Wunsch entstand, wir mögen doch den Wettbewerb mit ausrichten.
Solche Wettbewerbe haben Vorteile im Vergleich zu normalen Konferenzbeiträgen. Ein Wettbewerb gibt klare Vorgaben und ermöglicht die direkte Vergleichbarkeit von verschiedenen Ansätzen bezüglich einer bestimmten Aufgabenstellung. Je realitätsnaher der Wettbewerb, desto spannender und erkenntnisorientierter werden die Resultate.
Der Torcs-Wettbewerb untersucht die Möglichkeiten, autonome Autos, denen nur simulierte lokale Sensorik zur Verfügung steht, effektiv zu steuern - entweder um möglichst effizient zu fahren oder um möglichst effektiv mit anderen Fahrern zu "interagieren.

Abbildung 2: Auch die Fahrzeuge und 3D-Objekte längs der Strecke lassen sich frei definieren und mit Open-Source-Software erstellen.

Linux-Magazin: Warum wurde neben dem Simulated Car Racing Championship noch ein Demolition Derby ins Leben gerufen?

Martin Butz: Wir hoffen, dass sich sowohl der Spaßfaktor als auch der Erkenntnisgewinn maximieren lässt und die Computational Intelligence auch für ein breiteres Publikum interessant macht. Ähnliche Effekte sieht man ja zum Beispiel auch auf den doch mittlerweile sehr berühmten RoboCup Wettbewerben.

Matthias Linhardt: Wir wollten die Einstiegshürde deutlich senken, aber gleichzeitig trotz geringerem Aufwand ein mindestens ebenso spannendes und packendes Erlebnis bieten wie in der SCRC. Deshalb haben wir ein für das DD angepasstes Schadensmodell entwickelt, das ein simples aber effizientes Regelwerk erlaubt und einen einfachen, aber gut erweiterbaren Demonstrations-Controllers realisiert.
Zusätzlich werden wir in den nächsten Wochen für die DD-Competition auf der CIG noch eine Erweiterung veröffentlichen, die eine Evolution des Controllers, zum Beispiel mittels CMA, erlaubt.

Martin Butz: Das Destruction Derby fokussiert die Herausforderung auf die Gegnerinteraktion -- Vermeidung, Jagen und Stellen von Gegnern. Somit ist die Herausforderung eine ganz andere: während es im SCRC vor allem darauf ankommt die Ideallinie und Idealgeschwindigkeit um den Kurs zu berechnen, ist im DD die größte Herausforderung, zu antizipieren, wie sich die gegnerischen Autos verhalten, um sie dadurch effizient vermeiden und gleichzeitig im richtigen Moment erwischen zu können.

Linux Magazin: Warum fiel die Wahl gerade auf TORCS?

Matthias Linhardt: Torcs bietet als Open-Source-Projekt die besten Voraussetzungen. Es lässt sich relativ leicht an die Competition-Bedürfnisse anpassen und erweitern, was beispielsweise das Server-Client-Setup mit begrenzter Sensorik beweist. Zudem bietet es eine ausgereifte Physikengine und ansprechende Visualisierung - nicht zuletzt aber auch die Gleichberechtigung von Windows und Linux Benutzern.

Martin Butz: Im Vergleich zu einem kommerziellen Simulator fallen darüber hinaus natürlich auch keine Kosten an und es gibt keine Copyright Beschränkungen.

Linux-Magazin: Wie viele Einsendungen gibt es im Durchschnitt pro Veranstaltung und wie sah das Echo bei der GECCO2010 aus?

Martin Butz: Im letzten Jahr entwickelte sich die Anzahl der Einsendungen sehr dynamisch. Zum ersten Termin gab es sechs Einsendungen, dann elf, und auf der IEEE CIG 2009 waren dann immerhin dreizehn Controller im Wettbewerb. Das Feedback von der GECCO lässt hoffen, dass sich mehrere Teams für den nächsten Wettbewerb anmelden werden.

Linux-Magazin: Wie hat sich die Qualität der Einsendungen entwickelt? Werden die Bots immer besser oder tendenziell sogar schlechter?

Martin Butz: Im Vergleich zum letzten Jahr wurden mehrere Sensoren stark verrauscht, aber die Streckendistanzsensoren haben eine längere Reichweite bekommen. Somit sollte die Informationsverarbeitung insgesamt schwieriger sein, dafür aber die Antizipation der nächsten Kurve etwas einfacher. Das Resultat auf der GECCO sah nun so aus, dass unser COBOSTAR Kontroller vom letzten Jahr trotz der Veränderungen in der Sensorik und ohne weitere Anpassungen im Qualifying immer noch die besten Zeiten lieferte.
Allerdings waren dann in den Rennen mit Gegnern andere vorne, da auch die Distanzsensoren zu den Gegnern verrauscht wurden, und COBOSTAR aus den Gegnerdistanzsensoren deren Geschwindigkeit über die Zeit berechnet. Mit verrauschten Sensoren fluktuiert die abgeleitete Geschwindigkeit stark und somit sah COBOSTAR sozusagen immer wieder Phantomgegner auf sich zu rauschen, denen er versucht auszuweichen.

Abbildung 3: Ein winterlicher Zweikampf zwischen zwei computergesteuerten Robots.

Linux-Magazin: Welche KI-Verfahren/Algorithmen werden derzeit von den Bot-Programmierern bevorzugt?

Martin Butz: Es gibt sehr viele verschiedenen Techniken, die zum Einsatz kamen: angefangen von regelbasierten Verfahren, über optimale Kontrollverfahren, Fuzzy Logik, bis hin zu reinen Lernverfahren fast komplett ohne Vorwissen. Die erfolgreichsten waren aber die, die mehrere KI-Techniken kombinierten, meist in Anlehnung an Subsumptionsansätzen a là Marvin Minskey und Rodney Brooks, welche diese in den 80er Jahren propagierten. Es gibt meist eine Grundstrategie, die dann je nach Umstand modifiziert wird.
Aufgrund der Ausrichtung des Wettbewerbs weg von traditionellen KI Techniken hin zum Maschinellen Lernen und modernen Computation Intelligence Techniken hatten mehr als die Hälfte der Beiträge Lernkomponenten integriert oder zumindest ihre Strategieparameter automatisiert optimiert.

Linux-Magazin: Wie unterscheiden sich die Anforderungen an die KI beim Demolition Derby von einem "normalen" Rennen? Prinzipiell würde es doch ausreichen, die Gegner stupide anzuvisieren und dann Gas zu geben?

Matthias Linhardt: Die Anforderungen an die KI sind sehr unterschiedlich. Während bei der regulären SCRC der Umgang mit der Strecke den wichtigsten Teil ausmacht, liegt der Fokus beim DD auf der Gegnerinteraktion. Der von uns zu Demonstrationszwecken angebotene DD-Controller verfolgt eine minimalistische Vorgehensweise: Er wählt seine Fahrtrichtung zu dem nächstgelegenen Gegner, versucht dabei die Streckenränder zu meiden, macht 180-Grad-Drehungen (U-Turns) auf der Streckenseite mit mehr Platz zum Wenden, falls der Gegner hinter ihm ist, oder fährt die Strecke ab und sucht den Gegner, wenn er nicht in Sensorreichweite ist.
Dieser Controller ist extrem simpel, dennoch bereitet es einem menschlichen Fahrer einige Schwierigkeiten, ihn zu besiegen. So eine KI lässt sich viel schneller und einfacher programmieren als eine auch nur halbwegs erfolgreiche KI für die SCRC. Allerdings lässt sich die Performanz von einer auf Gegnerinteraktion fokussierten KI nicht so leicht evaluieren: Es kommt sehr auf die Gegner und deren Strategien an, auf die er im Wettbewerb treffen wird, und das lässt sich nicht vorher testen.

Abbildung 7: Die Torcs-Engine ist robust und fast beliebig skalierbar. Hier ein Setup über zwei HD-Monitore mit einer Auflösung von 3800 mal 1200 Pixel. Nur an brillianten Texturen und Grafiken fehlt es bisweilen noch.

Linux-Magazin: Gibt es ein konkretes Anwendungsgebiet? Kommen die Bot-Algorithmen auch noch in anderen, praxisrelevanten Bereichen zum Einsatz oder dienen sie lediglich der Unterhaltung?

Matthias Linhardt: Ein direktes Anwendungsgebiet gibt es momentan noch nicht. Grundsätzlich ist es zu einem späteren Zeitpunkt aber durchaus vorstellbar, die in der Simulation gemachten Erfahrungen auf die Praxis zu übertragen. Gerade weil die dem Controller zur Verfügung stehenden Informationen, auf deren Grundlage er seine Fahrentscheidungen treffen muss, im Gegensatz zu gängigen Spielen realitätsnah sind.
Entgegen den meist verwendeten globalen Informationen wie x-y-Koordinaten des Fahrzeugs müssen die Controller in den Competitions ja mit lokalen, egozentrischen Informationen auskommen, zum Beispiel den angesprochenen Range Finder Lasern, die die Informationen zum weiteren Straßenverlauf liefern. Diese lokale Sensorik entspricht vielmehr der realisierbaren Technik, die momentan für autonome (Fahr-)Systeme oder Fahrassistenzsysteme denkbar wäre. GPS ist da von der Genauigkeit und auch durch die nie perfekte Aktualität der Karten nur sehr eingeschränkt nutzbar.

Abbildung 4: Aus der Vogelperspektive lässt sich der Erfolg oder Misserfolg der eigenen KI am Besten verfolgen.

Martin Butz: Ich erwarte, dass die entwickelten Techniken sowohl für das Design von realistischeren Kontrollern in Spielen zum Einsatz kommen werden - also Kontrollern, die sich menschenähnlicher verhalten und somit den Spaßfaktor weiter erhöhen können. Andererseits ist auch die Autoindustrie an den entwickelten Techniken interessiert, zum Beispiel für Fahrassistenzsysteme. Wir kollaborieren in diese Richtung gerade mit der Honda Research Institute Europe GmbH in Offenbach.

Linux-Magazin: Warum gibt es beim Demolition Derby verschiedene Einschränkungen? Beispielsweise nimmt das Auto keinen Schaden, wenn es frontal mit einem anderen Fahrzeug zusammenstößt. Gerade dies ist aber doch eine spannende Entscheidungsfrage.

Matthias Linhardt: Wir sind uns bewusst, dass die getroffenen Einschränkungen dem Realismus abträglich sind. Wir haben sie dennoch gewählt, um klare Fronten zu schaffen. Das ursprünglich implementierte Schadensmodell ist so komplex, dass es keine einfachen Vorhersagen erlaubt. Das wiederum macht eine Strategiefindung für Controller extrem schwer, da zu viele Variablen existieren. Genau das wollten wir aber nicht, sondern ein einfaches, jederzeit nachvollziehbares Schadensmodell, das durch die vereinfachten Alles-Oder-Nichts-Regeln eindeutige Vorhersagen des Verhaltens ermöglicht und somit Raum für interessante Fahrstrategien bietet.

Martin Butz: Es kommt auch immer auf die Sensorik an - in der aktuellen Implementierung ist es sehr schwierig, dem Kontroller Informationen zu geben, wie viel Schaden der Gegner gerade bereits hat. Außerdem wollten wir vermeiden, dass Kontroller eingereicht werden, die eher eine Vermeidestrategie fahren, darum auch der allgemeine Schadens-Reset, wenn ein gegnerisches Auto ausscheidet.

Linux-Magazin: Der Gewinner im Demolition Derby ist derjenige, der zum Schluss überlebt. Kommt es nicht gerade bei künstlicher Intelligenz häufiger vor, dass sich mehrere Wagen festfahren oder im Kreis aneinander vorbei rauschen und somit unter dem Strich ein Patt entsteht?

Abbildung 6: Das Sensormodell von Torcs ist ebenso modular aufgebaut wie das Spiel selbst, doch hat der Bot nur wenige Aktionsmöglichkeiten (Gas geben, Bremsen, Lenken, Schalten).

Matthias Linhardt: Wenn beide Controller dieselbe Strategie fahren, könnte das vorkommen. In solchen Fällen muss bei Schadensgleichheit ein Patt entschieden werden. Bei unterschiedlichem Schaden gewinnt der Controller mit weniger Schaden.

Linux-Magazin: Wie ist die GECCO 2010 verlaufen? Wer ist der Gewinner und welche KI-Strategie hat er verfolgt?

Martin Butz: Der Gewinner des SCRC auf der GECCO 2010, Enrique Onieva Caracuel mit dem Racer AUTOPIA, hat eine modulare Architektur, die er mit evolutionären Methoden optimiert hat. Die Grundstrategie transferiert die Information der Distanzsensoren auf Lenkwinkel und die gewünschte Geschwindigkeit. Letztere wird nochmals in entsprechendes Kontrollverhalten - also Bremsen oder Gasgeben - umgerechnet. Die Gegnervermeidung wurde mit einem zusätzlichen kleinen Regelwerk realisiert. Gleichzeitig ist eine Strategieanpassung in der neuen Aufwärmphase eingebaut, falls der Kontroller während diese Phase aus der Strecke fliegt.

Abbildung 5: Für die Wettbewerbe haben Entwickler ein eigenes Client-Server-Modell entworfen, das der KI nur wenige Millisekunden für Entscheidungen lässt.

Linux Magazin: Wie sehen die weiteren Planungen aus? Dürfen wir mit weiteren Wettbewerben rechnen? Stehen die Termine schon für das nächstes Jahr?

Martin Butz: Erst einmal hoffen wir auf zahlreiche Einsendungen für die CIG am 22.August. Für das nächste Jahr stehen noch keine Termine fest, es ist aber jetzt schon sicher dass das DD und auch SCRC auch auf der GECCO nächstes Jahr angeboten werden.

Links zum Thema:
Tim Schürmann, Auto-Fahrschule: Linux-Magazin 09/2010, S. 86.
Tim Schürmann, Ausbaufähig: Linux-User, 05/2010, S. 54,
Marcel Hilzinger: Tritt ins Gaspedal
Marcel Hilzinger: Die Rennsaison ist eröffnet:
Torcs:
GECCO
CIG:
Biographie Martin Butz:
Biographie Matthias Linhardt:

Das Autorennspiel Torcs glänzt schon in der Standardinstallation mit vielen Strecken, Perspektiven und einem modularen Aufbau, der auch Client-Server-Szenarien für akademische Wettbewerbe ermöglicht. Die 3D-Engine und KI-Integration sind ausgereift und halten auch höheren Ansprüchen stand. Das aktuelle Linux-Magazin (Tim Schürmann, "Auto-Fahrschule", Linux-Magazin 09/2010) beschäftigt sich mit dem Erstellen und dem Steuern künstlicher Rennwagen. Eine wichtige Rolle dabei spielen deutsche Universitäten, deren Teams auf KI-Konferenzen wie der GECCO und der CIG mitfahren. Linux-Magazin Autor Tim Schürmann hat mit Matthias Linhardt und Martin Butz von der Psychologischen Fakultät der Universität Würzburg zwei deutsche KI-Spezialisten zu Ihrem Engagement bei den Weltmeisterschaften und technischen Details der Bot-Programmierung befragt.