Projektstudium RoboCup 2002/2003 - protai7 Projektstudium Technische Anwendungen der Informatik protai7 RoboCup 2002/2003 Abschlussveranstaltung 07.08.2003

Projektstudium RoboCup 2002/2003 - protai7

ProjektstudiumTechnische Anwendungen der Informatik

protai7

RoboCup 2002/2003Abschlussveranstaltung

07.08.2003

Lehrstuhl für Rechnerstrukturen, Prof. Dr. GrassLehrstuhl für Numerische Mathematik und Analysis, Prof. Dr. Donner


2 / 74

Was ist RoboCup?

• Internationale Forschungs- und Bildungsinitiative

• Schwerpunkt: Künstliche Intelligenz und Intelligente Robotik

• Populäres Spiel: Fußball


3 / 74

Die Middle Size League

• Robotergröße: ca. 50 x 50 x 50 cm

• Maximales Gewicht 80 kg

• Roboterfarbe: Schwarz

• Regelwerk an FIFA Bestimmungen angelehnt

• Kommunikation der Roboter untereinander ist ausdrücklich erlaubt


4 / 74

Was ist das Projektstudium?

• Praktische Erfahrungen

• Anspruchsvolle wissenschaftliche Themengebiete

• Teamarbeit


5 / 74

Aufgaben und Ziele

• Übernahme des bestehenden Projektes

• Implementierung von Teamfähigkeit

• Einführung von Echtzeit-Scheduling

• Grundlage für nachfolgende Gruppen


6 / 74

Herausforderungen

• Hardware– Programmierung– Diagnose und Instandhaltung

• Software– Sehr komplexes System– Starke Abhängigkeiten der Komponenten

• Teamarbeit– Organisation der Aufgaben– Koordination der Gruppe auf ein Ziel hin


7 / 74

Inhalts-Übersicht

1. Grundlagen

2. Hardware

3. Architektur des Projektes

4. Sensorverarbeitung und Bildverarbeitung

5. Kommunikationssystem

6. Künstliche Intelligenz

7. Vorführung Bildverarbeitung und KI

8. Live-Vorführung auf dem Spielfeld


8 / 74

Welche Hardware steht zur Verfügung?

• Roboter– ActivMedia Pioneer 2– Embedded Board mit

400 MHz CPU– Bewegliche Kamera– Sonar-Sensoren– Odometrie-Sensoren– Pioneer 2

Microcontroller Board


9 / 74

Betriebs-Umgebung

• Standard-Hardware

• Linux (Debian 3.0)

• Echtzeit-Kernel

• Problem: Festplatte im fahrenden Roboter

• Lösung: Disc on Chip


10 / 74

Die Kamera

• Sony EVI-D31• Schwenkbar• Auto-Tracking• Kommunikation per

VISCATM Protokoll (Video System Control Architecture)


11 / 74

Neuerung: Auslesen von Kameradaten

• Serielles Kabel von der Kamera zum Mainboard

• Kommunikation über das VISCATM Protokoll


12 / 74

Interessante Kameradaten

• Belichtungseinstellungen

• Neigungs- und Drehwinkel– Kamera kann im Spiel bewegt werden

• Auto-Tracking Informationen– Bis zu vier Ziele– Aktives und passives Tracking


13 / 74

Auto-Tracking


14 / 74

Inhalts-Übersicht

1. Grundlagen

2. Hardware


4. Sensorverarbeitung und Bildverarbeitung






15 / 74

Hardware-Ansteuerung

Architektur

Sensorverarbeitung

KünstlicheIntelligenz


16 / 74

Architektur


Sensorverarbeitung


Frame Grabber

Kamera(Tracking)

Sonar Odometrie

Aktoren Netzwerk


17 / 74

Architektur

Sensorverarbeitung



Bildverarbeitung

EigenpositionBallfindung

Tracking

Ballfindung

Sonar

Eigenposition

Odometrie

Eigenposition

Sensorfusion

Ballfindung Eigenposition


18 / 74

Architektur


Hardware-Ansteuerung Sensorverarbeitung

Weltmodell

Verhalten


19 / 74

Echtzeitanforderungen bei Robocup

Per

form

ance

Deadline Antwortzeit

• Weiche EchtzeitanforderungenLinux Kernel Realtime Linux

Kernel

durchschnittliche Latenzzeit

10ms 5µs

maximale Latenzzeit

>10s 50µs


20 / 74

Echtzeit unter Linux – zwei Ansätze:

Preemptive Patch für Kernel

-MontaVista Scheduler

-KU-RT Linux

-TimeSys

Integration eines Mikrokernels

-RT-Linux

-RTAI


21 / 74

Echtzeit unter Linux - RTAI

Hardware

Real-Time Hardware Abstraction Layer (RTHAL)

Kernel-Module

RTAI-Modul

RTAI-Modul

RTAI-Modul

Kernel-SpaceKernel-Space

User-SpaceUser-SpaceRealtime-

ApplikationLinux-

Programme

LinuxKernel

Fifo, Mailbox, SHMEM

LXRT


22 / 74

Design-To-Time Scheduling Algorithmus

• Statischer Scheduling-Algorithmus• Effiziente Nutzung der zur Verfügung

stehenden Zeit• Dynamische Auswahl verschiedener

Algorithmen anhand von– Laufzeit– Qualität

• Ausführung als Echtzeittask oder als Taskmit höchster Priorität


23 / 74

Design-To-Time Scheduling Algorithmus

Pascha

Taskgraph

C++ Code

Design To Time

Scheduling

Algorithmus

DecisionDAG

Dispatcher

Creator


24 / 74

Echtzeit-Scheduling


Sensorverarbeitung


RTAIRealTime OS

Kernel TaskGraph

Dispatcher

Kamera-daten

Sonar/Odometrie-

daten

Kernel Modul

RTAI


25 / 74

Inhalts-Übersicht

1. Grundlagen

2. Hardware


4. Sensorverarbeitung u. Bildverarbeitung






26 / 74

Eigenpositionsfindung

1. Extrahiere Linien aus Bild2. Berechne Lage der Linien im Roboter-Koordinaten-

System

1. Extrahiere Linien aus Bild

Fehler


System3. Linien-Matching mit gespeichertem Spielfeld-Modell und

Hypothesen-Erzeugung4. Bewertung der Hypothesen mittels Fehlerfunktion und

Auswahl der besten Hypothese


System3. Linien-Matching mit gespeichertem Spielfeld-Modell und

Hypothesen-Erzeugung


27 / 74

Eigenpositionsfindung protai6

1. SeedSearch2. Zuordnung von SeedPoints zu drei Gruppen

(Spielfeldbegrenzung, Spielfeldlinie vorne, Spielfeldlinie hinten) anhand einfacher Annahmen

3. Liniensplittung und Verwurf der Verbindungspunkte


28 / 74

Eigenpositionsfindung

protai6• Sehr schnell• Gute Ergebnisse bei guter Farbkalibrierung• Viele SeedPoints und Farbklassifizierung notwendig

protai7• protai6-Algorithmus mit erweiterter Farbkalibrierung sowie

schnellerer Farbklassifizierung und SeedSearch• Durchschnittliche Laufzeit 18ms


29 / 74

Farbklassifizierung

• Partitionierung des RGB-Farbraums

• Ziel: Robustheit gegenüber Helligkeitsänderungen tundefiniergelbblaugrünrotschwarzweißf ,,,,,,255: 3


30 / 74

Der HSV-Farbraum

• Robustheit gegenüber Helligkeitsveränderungen lässt sich durch Wechsel in einen anderen Farbraum realisieren

• Eine Farbe wird durch die Komponenten Hue (Farbton), Saturation (Farbsättigung) und Value (Helligkeit) definiert


31 / 74

Farbklassifizierung

protai6• Definiere Farbbereichsgrenzen für die Farbklassen im

HSV-Raum vor Programmstart (Farbkalibrierung)• Konvertierung des RGB-Tripels in ein HSV-Tripel zur

Laufzeit• Test für die zuvor definierten Farbbereichsgrenzen

protai7• Definiere Farbbereichsgrenzen vor Programmstart• Konvertierung aller RGB-Tripel in HSV-Tripel, Test für die

zuvor definierten H-S-V-Intervalle und Speicherung der Farbklasse in einer Lookup-Tabelle (16 MB)


32 / 74

Farbkalibrierung

• Suche nach Bereichsgrenzen der Partitionen {weiß,schwarz,rot, ...} (hier im HSV-Raum)

• Wir haben zwei verschiedene Verfahren implementiert

manuell

semi-automatisch


33 / 74

Farbkalibrierung – manuell

• Klick in Region berechnet Minima und Maxima der HSV-Werte innerhalb eines Umkreises

• Vorschau aller Farbregionen des Bildes und Berechnung von Überlappungsbereichen


34 / 74

Farbkalibrierung – semi-automatisch

• Aufnahme einer definierten Szene• Berechnung der Mittelwerte und der Varianzen der HSV-

Tripel jeder Farbpartition• Multiplikation der Varianzen mit einstellbaren Faktoren

liefert Intervallgrenzen• Automatische Auflösung von Überlappungen durch

Gewichtung der Varianzen


35 / 74

SeedSearch

• Suche nach Farbübergängen entlang von Geraden• Ziel: Robustheit gegenüber Störungen und

Laufzeitoptimierung• Wir haben vier verschiedene Verfahren entwickelt


36 / 74

SeedSearch mit Fenster

• Robustheit gegenüber Störungen durch individuelle Aktivierungsgrenzen und Filterung in 3x3-Fenster

Übergangsaktivierungen

ws r bgr ge u


37 / 74

SeedSearch mit Überspringen

• Robustheit gegenüber Störungen durch Aktivierungen• Überspringen von je 3 Pixeln bis Farbübergang erreicht,

dann Backtracking

Übergangsaktivierungen

ws r bgr ge u


38 / 74

Ballfindung

• Merkmale– Form:

• Kreisscheibe (evtl. teilweise verdeckt)• Nur bestimmter Radius möglich, abhängig von der Höhe im Bild

– Farbe:• Farbpartition rot (aber Reflexionen und Schattenwürfe)


39 / 74

Ballfindung

• Suche nach roten Farbclustern ausschließlich mit SeedPoints

• Berechne erwartete Ausmaße anhand der Höhe im Bild• Sind die Ausmaße zu gering könnte der Ball teilweise

verdeckt sein; Berechne Ballzentrum mit Dreiecksverfahren


40 / 74

Gegnererkennung

• Suche nach schwarzen Farbclustern ausschließlich mit SeedPoints

• Berechne erwartete Ausmaße anhand der Höhe im Bild


41 / 74

Sonar und Odometrie

• Alle 50 ms kann je einer der 8 Sonarsensoren abgerufen werden.

• Sonarinformationen werden für die Eigenpositionsfindung und Hindernis/Gegner-Erkennung verwendet

• Odometrieinformationen werden alle 50 ms abgefragt und für die Eigenpositionsfindung verwendet.


42 / 74

Tracking

• Abfrage der Auto-Tracking-Funktion der Kamera über die serielle Schnittstelle

• Verwendung für Ballfindung, Gegnererkennung und Eigenpositionsfindung (z.B. über Torerkennung) möglich


43 / 74

Sensorfusion

• Sensormesswerte sind immer fehlerbehaftet (Varianz)• Sensormesswerte verschiedener Sensoren sowie

verschiedener Zeitpunkte müssen zu einem optimalen Wert fusioniert werden

• Der Kalman Filter ist optimal im Sinne, dass die Varianz minimiert wird

Kalman Filter

SensorZeitstempel

Messwert

Varianz

Letzter WertZeitstempel

Messwert

Varianz


44 / 74

Sensorfusion der Eigenpositionsfindung

BildverarbeitungZeitstempel

Messwert

Varianz

SonarZeitstempel

Messwert

Varianz

OdometrieZeitstempel

Messwert

Varianz


Messwert

Varianz

Kalman Filter


45 / 74

Sensorfusion der Ballfindung

BildverarbeitungZeitstempel

Messwert

Varianz

TrackingZeitstempel

Messwert

Varianz

KommunikationZeitstempel

Messwert

Varianz


Messwert

Varianz

Kalman Filter


46 / 74

Inhalts-Übersicht

1. Grundlagen

2. Hardware








47 / 74

Gruppenkommunikationsprotokoll (GKP)

• Aufgaben des CommSystems– Ermöglicht Erweiterung der KI auf Teamplay– Bietet zusätzliche Daten für die Sensorfusion– Dient als zusätzlicher Sensor für

Ballfindung und Gegnererkennung

• Client/Server-Architektur– CommServer / Software-Access-Point– CommClient als eigener Prozess


48 / 74


• Gruppenkommunikationsprotokoll– Anerkanntes Kommunikationsparadigma– Handling von Paketverlusten– Begrenzung der maximalen Verzögerung

• Probleme des IEEE 802.11 GKP– Keine Bestätigung der Broadcastnachrichten– Keine garantierte begrenzte Verzögerung– Keine Erkennung inaktiver Clients– Nur der Access-Point hat ein aktuelles Bild der

Gruppe


49 / 74


• Datenpaket / Header (36 Bit)

Ident ID-Nummer des Clients

Seq Sequenznummer des Pakets

Akk SeqNr des letzten erhaltenen Pakets

Mode Aktueller Modus (0: Broadcast,

1: Peer2Peer, 2: TimeSync)


50 / 74


• Datenpaket / Header (36 Bit)

Login Login-Modus (0: No Login, 1: Login, 2: Relogin)

Sync Zeitsynchronisation (0: No Sync, 1: Sync)

Clients Gesamtzahl der eingeloggten Clients

Active Active-Flags aller max. 11 Clients


51 / 74


• Datenpaket / Nutzdaten– Zeitstempel– Eigenposition– Ballposition– Gegnerposition– Ballbesitz

• Beliebig erweiterbar um weitere Daten

des Weltmodells und der KI


52 / 74


• Funktionsweise / Übersicht


53 / 74

Zeitsynchronisation

• Notwendig für verteilte (Echtzeit-) Anwendungen

• Notwendig zur Erkennung temporaler Abhängigkeiten in verteilten Systemen (WLAN)

• Zeitdifferenz– um einen gewissen Offset– durch asynchrone Systemuhren


54 / 74

Zeitsynchronisation

• Initiale Zeitsynchronisation– Ausgleich des Offsets beim Login– Übernahme der Zeit des CommServers

• Problem: Werteanpassung des im IEEE 802.11 Standard definierten Uhren-synchronisationsprotokolls– Doppelte Zeitpunkte– Zeitsprünge


55 / 74

Zeitsynchronisation

• Werteanpassung vs. Ratenanpassung


56 / 74

Zeitsynchronisation

• Implementierung einer ans WLAN angepassten Version eines für den CAN-Bus entwickelten Protokolls– Einsatz eines TSC-Timers (TimeStampCounter)– Einsatz einer Softwareuhr mit Ratenanpassung– Erweiterung des CommSystems um einen

TimeSync-Modus


57 / 74


• Erweiterungsmöglichkeiten– Übertragung weiterer Informationen aus dem

Weltmodell– Integration aller übertragenen Daten in die

Sensorfusion und KI– Übertragung von KI-Flags für dynamisches

Rollenverhalten


58 / 74

Inhalts-Übersicht

1. Grundlagen

2. Hardware








59 / 74

Künstliche Intelligenz

Kommandofusion

Verhalten Verhalten Verhalten

Kommando

Kommando

KF

V V

K K

ArbitrationstrategyKommando

Arbitrationstrategy Arbitrationstrategy

AS AS


60 / 74

Teamverhalten

• Kooperatives Verhalten

• Dezentrale Entscheidungen

• Informationsaustausch

• Rollenzuweisung


61 / 74

Simulator

• Ersetzt die reale Umgebung

• Ersetzt Sensoren und Aktoren

• Einsatz zum Test der KI

• Einsatz zum Test der Sensorverarbeitung


62 / 74

GrabBall


63 / 74

GrabBall - Teamverhalten


64 / 74

ScoreGoal


65 / 74

ScoreGoal - Teamverhalten


66 / 74

Pass


67 / 74

Positionsspiel


68 / 74

Torwartposition


69 / 74

Torwart GrabBall


70 / 74

Beispiel: 2 gegen 1


71 / 74

Beispiel: 2 gegen 1


72 / 74

Beispiel: 2 gegen 1


73 / 74

Beispiel: 2 gegen 1


74 / 74

Vielen Dank für die Aufmerksamkeit!

Documents

Projektstudium RoboCup 2002/2003 - protai7 Projektstudium Technische Anwendungen der Informatik protai7 RoboCup 2002/2003 Abschlussveranstaltung 07.08.2003