Institut für Angewandte Mikroelektronik und Datentechnik

Fachbereich Elektrotechnik und Informationstechnik, Universität Rostock

Ralf Salomon, Frank Golatowski

Universität Rostock

Aufbau höherer Strategien für kleine autonome mobile Roboter basierend auf Methoden der dynamischer Rollengenerierung und

lokaler Interaktion

Ralf Salomon

Frank Golatowski

Universität Rostock

Institut für Angewandte Mikroelektronik und Datentechnik

FB Elektrotechnik und Informationstechnik

Arbeitsgebiete

Entwurfsunterstützung harter Echtzeitsysteme

Rapid Prototyping

Eingebettete und Echtzeit-Systeme

Mobile computing systems

Rechnerarchitektur und -systeme

High-level Systementwurf

Chipdesign (FPGA, ASIC)

VLSI

Soft Computing, Evolvable Hardware

Mobile Agenten

Künstliche Intelligenz

Objektorientierte und komponenten-basierte Softwareentwicklung

Ralf Salomon

Frank Golatowski

Universität Rostock

Institut für Angewandte Mikroelektronik und Datentechnik

FB Elektrotechnik und Informationstechnik

Gliederung

1. Dezentraler Ansatz (lokale Interaktion und dynamische Rollenberechnung)

2. Aufgaben und Realisierung

3. Aktueller Stand

4. Zusammenfassung

Ralf Salomon

Frank Golatowski

Universität Rostock

Institut für Angewandte Mikroelektronik und Datentechnik

FB Elektrotechnik und Informationstechnik

Small size league

Ralf Salomon

Frank Golatowski

Universität Rostock

Institut für Angewandte Mikroelektronik und Datentechnik

FB Elektrotechnik und Informationstechnik

Small size league: dezentrale Architektur

Key Challenges

Distributed intelligence

Parsimonious design

Timing constraints

Power awareness

Ralf Salomon

Frank Golatowski

Universität Rostock

Institut für Angewandte Mikroelektronik und Datentechnik

FB Elektrotechnik und Informationstechnik

Selbständig agierende Teammitglieder

• Kohärentes Systemverhalten trotz autonom agierender Agenten

• Aufgabenteilung zwischen den Robotern– Dynamische Rollenverteilung auf die Roboter– Autonome Rollenwahl mittels Potenzialmethode– Dabei Unterstützung mittels sporadischer lokaler

Kommunikation (peer-to-peer)

Ralf Salomon

Frank Golatowski

Universität Rostock

Institut für Angewandte Mikroelektronik und Datentechnik

FB Elektrotechnik und Informationstechnik

Algorithmische Herausforderungen

1. Sinnvolle Rollenverteilung ohne Doppel- und Fehlbelegungen

2. Vermeidung des durch Fehlkommunikation verursachten Thrashings

3. Navigations- und Kollisionsvermeidung4. Beschleunigung von Teilalgorithmen durch

Auslagerung auf rekonfigurierbare Hardware (parsimonious design)

5. Generische Middleware für drahtlose Kommunikationstechnologien

Ralf Salomon

Frank Golatowski

Universität Rostock

Institut für Angewandte Mikroelektronik und Datentechnik

FB Elektrotechnik und Informationstechnik

Zentrale Architektur

Bildverarbeitungs-komponente

Datenkomponente

Strategiekomponente

Roboter komponente

Simulatorkomponente

Roboter komponente

Roboter komponente

Roboter komponente

Ralf Salomon

Frank Golatowski

Universität Rostock

Institut für Angewandte Mikroelektronik und Datentechnik

FB Elektrotechnik und Informationstechnik

Dezentrale Architektur

Ralf Salomon

Frank Golatowski

Universität Rostock

Institut für Angewandte Mikroelektronik und Datentechnik

FB Elektrotechnik und Informationstechnik

Dezentrale Architektur

Ralf Salomon

Frank Golatowski

Universität Rostock

Institut für Angewandte Mikroelektronik und Datentechnik

FB Elektrotechnik und Informationstechnik

Software-Entwicklungsprozess

Unterstützung auf drei Ebenen 1. Software-Engineering für autonome

Agentensoftware 2. Beschreibung des Systemverhaltens

– Effiziente Entwicklung und Verifikation von Kernalgorithmen

– Automatische Codegenerierung – Echtzeitverhalten, Deterministik

3. Design Exploration– Kombination effektiver Algorithmen – Entwurfsbeschleunigung durch hohen Abstraktionsgrad

und gleichzeitigem Durchgriff auf niedrigere Entwurfsebenen

Ralf Salomon

Frank Golatowski

Universität Rostock

Institut für Angewandte Mikroelektronik und Datentechnik

FB Elektrotechnik und Informationstechnik

Visionen

1. Vertiefte Einblicke in die Funktionsweise verteilter Intelligenz

2. Sich selbst weiterentwickelnde Systeme mittels abstrakter Spezifikationen

3. Kombination aus eingebetteten Systemen, Software-Engineering und künstlicher Intelligenz auf komplexe, skalierbare Systeme

Ralf Salomon

Frank Golatowski

Universität Rostock

Institut für Angewandte Mikroelektronik und Datentechnik

FB Elektrotechnik und Informationstechnik

Wo stehen wir?

• Zentralisiertes Gesamtsystem komplett in UML beschrieben• Strategie mit Rollenverteilung nach Potenzialmethode• Roboter mit omnidirektionalem Antrieb• Simulator

Containersteuerung

imageEvaluation

thread_imageProcessing

writeData

container

initContainer initThreads stop

evStartevStop

evQuitT

evQuit

position processing

Tm(100)

container_controller

getData

thread_Strategie

calculateStrategy

writeCommandssimulationMode

thread_sendPosition

getData

sendData

simulationMode

containerStart

no yes thread_simulator

getCommands

writeData

simulation

yesnogetCommands

sendData

commandRecode

thread_sendCommands

not insimulationmode

not insimulationmode

wait fornewcommandsand freechannel

Befehle senden

Bildver-arbeitung

Strategie

Positionensenden

Simulator

Ralf Salomon

Frank Golatowski

Universität Rostock

Institut für Angewandte Mikroelektronik und Datentechnik

FB Elektrotechnik und Informationstechnik

Wo stehen wir?

• Zentralisiertes Gesamtsystem komplett in UML beschrieben• Strategie mit Rollenverteilung nach Potenzialmethode• Roboter mit omnidirektionalem Antrieb• Simulator

Ralf Salomon

Frank Golatowski

Universität Rostock

Institut für Angewandte Mikroelektronik und Datentechnik

FB Elektrotechnik und Informationstechnik

Zusammenfassung

• Entwicklung verteilter Intelligenz bei dezentrale Steuerung und lokaler Interaktion

• Beschleunigung der Design Exploration• Integration unter Beachtung der

Computational Efficiency

Ralf Salomon

Frank Golatowski

Universität Rostock

Institut für Angewandte Mikroelektronik und Datentechnik

FB Elektrotechnik und Informationstechnik

Kontaktinformation ?

Lage des Institut

in Rostock-Warnemuende

Universität Rostock

FB Elektrotechnik und Informationstechnik

Institut für Angewandte Mikroelektronik und

Datentechnik

Richard-Wagner Str. 31

18119 Rostock-Warnemünde

Germany

Tel.: +49 381 498 3538

Fax: +49 381 498 3601

Ralf Salomon

Frank Golatowski

Universität Rostock

Institut für Angewandte Mikroelektronik und Datentechnik

FB Elektrotechnik und Informationstechnik

Arbeitsplan (aktualisiert)

Ralf Salomon

Frank Golatowski

Universität Rostock

Institut für Angewandte Mikroelektronik und Datentechnik

FB Elektrotechnik und Informationstechnik

Aufgaben

1. UML Beschreibung der einzelnen Komponenten2. Spezifikation des notwendigen Zeitverhaltens, damit

a) Komponenten ausgetauscht werden können und b) eine dezentrale Realisierung schon im Entwurfsprozess

unterstützt wird.

3. Realisierung der dynamischen Rollenzuweisung4. Aufbau eines lokalen drahtlosen Kommunikationsnetzwerkes. 5. Anpassung bzw. Erweiterung existierender

Navigationsalgorithmen6. Entwicklung einer Entscheidungskomponente, die auf

Softcomputing-Methoden basiert7. Test der spezifizierten Algorithmen (Rollenzuteilung und

Rollenaustausch) sowohl durch Simulation als auch im Roboter-Team.

Ralf Salomon

Frank Golatowski

Universität Rostock

Institut für Angewandte Mikroelektronik und Datentechnik

FB Elektrotechnik und Informationstechnik

Aufgaben

Gaining insight into the nature of distributed intelligence

• Dynamische Rollenzuweisung nach Potenzialmethode

• Transformation auf dezentralen Ansatz• Lokale Kommunikation• Lokale Bildverarbeitung durch effiziente Hardware-

Unterstützung (FPGA)• Integration hardwarebasierter

Bilderkennungsalgorithmen• Echtzeitnachweis • Funktionstests mit mobilen Robotern

Ralf Salomon

Frank Golatowski

Universität Rostock

Institut für Angewandte Mikroelektronik und Datentechnik

FB Elektrotechnik und Informationstechnik

Detaillierte Aufgaben: StrategieRollenverteilung und Rollenwahl

• Dynamische Berechnung der Rollen und Rollenverteilung

• Entwicklung interagierendes Feedbacksystem

• Optimierung Strategienauswahl

Ralf Salomon

Frank Golatowski

Universität Rostock

Institut für Angewandte Mikroelektronik und Datentechnik

FB Elektrotechnik und Informationstechnik

Detaillierte Aufgaben: Strategie

• Vorhersage des Verhaltens von Roboter u. Ball

• Spezielle Algorithmen zur Hindernisvermeidung und Wegeplanung

• Integration aller zur Verfügung stehender Rollen in die Rollenverteilungen

• Entwicklung interagierendes Feedbacksystem • Dynamische Berechnung der Rollen und

Rollenverteilung• Optimierung Strategienauswahl

Ralf Salomon

Frank Golatowski

Universität Rostock

Institut für Angewandte Mikroelektronik und Datentechnik

FB Elektrotechnik und Informationstechnik

Rollenverteilung

Potenzialmethode• Analyse aus Sicht des einzelnen Spielers• Verteilung von Gewichten an die Spieler• Bis zu 24 Potenziale pro Spieler• Potenziale für GegenspielerErgebnis: • Potenzial die speziellen Rollen auszuüben• Rollenvergabe nach den Potenzialen

Ralf Salomon

Frank Golatowski

Universität Rostock

Institut für Angewandte Mikroelektronik und Datentechnik

FB Elektrotechnik und Informationstechnik

Arbeitsplan (aus Antrag)

Ralf Salomon

Frank Golatowski

Universität Rostock

Institut für Angewandte Mikroelektronik und Datentechnik

FB Elektrotechnik und Informationstechnik

Der R.O.P.E.S Prozess

Rapid Object-Oriented Process for Embedded Systems

Ralf Salomon

Frank Golatowski

Universität Rostock

Institut für Angewandte Mikroelektronik und Datentechnik

FB Elektrotechnik und Informationstechnik

Datenfluss im Container

• Ablaufsteuerung der Software im RoboCup Projekt

• Abarbeitung der Module in Threads

• Realmodus• Simulationsmodus

Bildverar-beitung

BefehleSenden

Simulator

Strategie

PositionenSenden

Con

tain

er

Ralf Salomon

Frank Golatowski

Universität Rostock

Institut für Angewandte Mikroelektronik und Datentechnik

FB Elektrotechnik und Informationstechnik

Zustandsdiagramm Container

Bildver-arbeitung

BefehleSenden

Strategie

PositionenSenden

Simulator

Containersteuerung

Ralf Salomon

Frank Golatowski

Universität Rostock

Institut für Angewandte Mikroelektronik und Datentechnik

FB Elektrotechnik und Informationstechnik

Zustandsdiagramm Container

imageEvaluation

thread_imageProcessing

writeData

container

initContainer initThreads stop

evStartevStop

evQuitT

evQuit

position processing

Tm(100)

container_controller

getData

thread_Strategie

calculateStrategy

writeCommandssimulationMode

thread_sendPosition

getData

sendData

simulationMode

containerStart

no yes thread_simulator

getCommands

writeData

simulation

yesnogetCommands

sendData

commandRecode

thread_sendCommands

not insimulationmode

not insimulationmode

wait fornewcommandsand freechannel

Ralf Salomon

Frank Golatowski

Universität Rostock

Institut für Angewandte Mikroelektronik und Datentechnik

FB Elektrotechnik und Informationstechnik

Die Datenablage

CRobotSettings

CStaticElements

CInitialisierung

CDynamicElements

CPlayingField

CRobotTypeA

CTacticSettings

CCommunicationSettings

CRobotTypeB

CElements

CPlayer COpponent CBall

CGameSettings CDynamicTacticBallSettings

Ralf Salomon

Frank Golatowski

Universität Rostock

Institut für Angewandte Mikroelektronik und Datentechnik

FB Elektrotechnik und Informationstechnik

Die Rollenverteilung

CRulesystemOne

CRulesystemBasis

CRulesystemTwo CRulesystemPotenzial

CRulesystemThree CRulesystemFour

Ralf Salomon

Frank Golatowski

Universität Rostock

Institut für Angewandte Mikroelektronik und Datentechnik

FB Elektrotechnik und Informationstechnik

Die Rollen

CPassiveRole

CActiveRole

CPassgeber

CRole

CExtraRole

CPassempfaenger

CSchütze

CBallholer

CDribbler

CBallbefreier

CPositionierer

CAbsicherer

CWartender

CFreudentaumel

CBlockierer

CTorwartCElfmeterschuetze

CFreistossschuetze

Ralf Salomon

Frank Golatowski

Universität Rostock

Institut für Angewandte Mikroelektronik und Datentechnik

FB Elektrotechnik und Informationstechnik

Ablauf der Strategieberechnung

Übergabe der Positionen

Rollenverteilung

Rollenberechnung

Zurückgabe der Befehle

Für jeden Spieler

Ralf Salomon

Frank Golatowski

Universität Rostock

Institut für Angewandte Mikroelektronik und Datentechnik

FB Elektrotechnik und Informationstechnik

Zentrale Strategiekomponente

• Umwandlung von Bildinformationen zu Befehlen für die Roboter

• Basiert auf rollenbasierten Ansatz (Rollenverteilung, Rollenausführung)

• Potenzialmethode zur Rollenverteilung

Ralf Salomon

Frank Golatowski

Universität Rostock

Institut für Angewandte Mikroelektronik und Datentechnik

FB Elektrotechnik und Informationstechnik

Tests mit dem Simulator

• Nachweis der Funktionalität,Einsetzbarkeit

• Simulator als Idealisiertes Abbild der Realität

Ralf Salomon

Frank Golatowski

Universität Rostock

Institut für Angewandte Mikroelektronik und Datentechnik

FB Elektrotechnik und Informationstechnik

Ergebnisse der Tests

• Zusammenarbeit Strategiemodul mit Container und Simulator möglich

• Rollenverteilung einfach, aber robust• Rollen funktionieren• Hindernisvermeidung meistens erfolgreich• Torwart ist sehr gut

Ralf Salomon

Frank Golatowski

Universität Rostock

Institut für Angewandte Mikroelektronik und Datentechnik

FB Elektrotechnik und Informationstechnik

Ergebnisse Strategiemodul

• Lauffähiges Strategiemodul zum Testen und Weiterentwickeln

• Klare Struktur • Verständlichkeit ist gegeben• Erweiterbarkeit ist möglich• Dokumentation mit Rhapsody und UML• Zusammenarbeit mit Container und

Simulator