Protokolldesign – Kommunikation

Öfter sehe ich Fragen in den Foren, die sich um prinzipielles Protokolldesign drehen. Dabei sollen Daten zwischen zwei Teilnehmern ausgetauscht werden und finden keinen (guten) Ansatz. Dies hat auch meist wenig mit den Programmiererfahrungen zu tun. Zuletzt hatte ich einen gestandenen Hard- und Softwareentwickler eines großen Akkuschrauberherstellers am Telefon: “Nachrichten beliebiger länger über eine UART senden geht so einfach?”

JA!

Wenn ihr diesen Blogbeitrag gelesen habt, dann solltet ihr eine Übersicht darüber bekommen haben. Ich werde die möglichen Konzepte dafür nur anschneiden und Beispiele nennen, für weitere tiefergehende Informationen werde ich auf andere Seiten verweisen.

Sychrone Kommunikation

Fangen wir nach dem OSI-Modell ganz unten an: Die Bitübertragungsschicht sollte geklärt werden, bevor das weitere Konzept erstellt wird. Ob eine UART, SPI oder I2C Schnittstelle verwendet wird hängt ganz wesentlich mit dem Entwurf zusammen.

Bei SPI und I2C haben wir eine Schnittstelle nach dem Master/Slave prinzip. Das heißt: Wenn der Master etwas anfragt, dann darf der Slave nur solange senden, wie es dem Master genügt. Allein schon deshalb, weil der Master den Takt/Clock vorgibt.

Daher sind diese Protokoll oft so ausgelegt, dass alle Nachrichten eine feste Länge besitzen. Nur für wenige Pakettypen gibt es Ausnahmen in denen der Master einfach längere Daten abfragen oder senden kann.

Beispiel SPI Temperatursensor

Der Slave wird mit Hilfe der entsprechenden Chip Select (CS) Leitung auf den gemeinsamen Bus geschalten. Der Master beginnt Takt und Daten zu senden. Es ist demnach eindeutig wann eine Nachricht beginnt! Es kann ein Nachrichtenanfang über das CS Signal erkannt werden! (Framing)

Erste Byte: Adressbyte/-register -> Temperaturregister lesen

Zweite Byte: Temperatur High Byte

Dritte Byte: Temperatur Low Byte

Der 16 Bit Temperaturwert ist nun beim Master angekommen.

Beginner Tipp: Der Master muss drei Bytes senden und wird drei Bytes empfangen, da die SPI wie ein Schieberegister arbeitet. Es ist dabei klar, dass nur das Erste gesendete Byte des Masters relevant für den Slave ist (Leseregister) und nur die letzten zwei empfangenen Bytes gültige Temperaturdaten enthalten. Der Rest wird einfach ignoriert und dazu verwendet das Clock Signal weiter zu takten.

Einige SPI-Slaves können nun sofort eine weitere Nachricht verarbeiten, andere erwarten ein kurzes Abschalten des CS. Meine Empfehlung ist jedoch, nach jedem Telegramm das CS zu verwenden. Ein Temperaturlogger der 24 Stunden am Tag jede Sekunde die Temperatur abfragt, könnte auf der Taktleitung schnell ein Glitch bekommen. Damit wäre die gesamte Kommunikation um ein Bit verschoben. Ohne sich über das CS zu synchronisieren würde hier nur noch ein Reset der Baugruppe helfen.

Beispiel I2C Temperatursensor

Da es keinen CS-Leitung gibt, lauschen alle I2C-Slaves auf dem Bus bis sie aufgerufen werden. Dies passiert wenn der Master die Startkennung gefolgt von der passenden Adresse (z.B. 7-Bit Adresse) sendet (Framing). Danach folgt die passende Registeradresse, wie bei der SPI. Bei I2C gibt es nun einige Control-Bits, um die Kommunikation etwas sicherer zu gestalten. Es gibt ein z.B. ein Bit um ein Lese oder Schreibvorgang anzukündigen und der Slave muss nach jedem gelesenen/geschriebenen Byte ein ACK-Bit senden bzw. setzen. So kann der Master eher die Kommunikation abbrechen, wenn der Slave nicht mehr antwortet und muss nicht die gesamte Nachricht absetzen.

Die Kommunikation ist bei der I2C-Schnittstelle durch die Hardware schon etwas weiter für den Benutzer abstrahiert. Eine einfach Möglichkeit einen nicht antworteten Slave bei einer SPI zu erkennen ist schon schwieriger. Wenn der Temperaturwert nur 0x00 0x00 oder 0xFF 0xFF sein sollte wäre das ein Hinweis.

Asynchrone Kommunikation

Hiermit beenden wir den einfachen Teil und kommen zur “Königsklasse”: die asynchrone Kommunikation mit gleichberechtigten Kommunikationsteilnehmern im Vollduplexbetrieb. Eine UART oder auch CSMA CD, wie Ethernet, wäre dafür ein Beispiel. Dies bringt ganz neue Probleme mit sich:

  • Der Takt aller Kommunikationsteilnehmer sollte recht genau sein. Dies erfordert oft aber nicht immer einen Schwingquarz oder ähnliche Maßnahmen.
  • Es darf zeitgleich gesendet und empfangen werden. Wenn eine Anfrage gesendet wird, kann gerade noch eine verspätete Antwort oder andere Anfrage eingehen. Die Zugehörigkeit ist also erstmal undefiniert.
  • Das von mir schon mehrmals erwähnte Framing ist nicht mehr Problem der Bitübertragungsschicht. Mit Framing ist das Erkennen eines zusammengehörenden Nachrichtenpaketes gemeint.
  • Ein anderer Teilnehmer interessiert sich recht wenig dafür ob gerade Zeit ist, diese Nachricht überhaupt verarbeiten zu können. Ausnahme bildet hier das Handshake-Verfahren bei der UART. Bei der Hardwarevariante werden zusätzliche Leitungen zur Flusskontrolle eingesetzt. Man kann der Gegenstelle also mitteilen: “Halt stopp! Ich komme nicht hinterher”. Was auf den ersten Blick nach einer guten Lösung klingt, ist auch kein Wundermittel für alle Probleme. Irgendwann muss auch die ausgebremste Gegenstelle ihre Daten verwerfen, wenn diese nicht mehr senden kann.

Bleiben wir also bei allen nachfolgenden Betrachtungen bei einer UART mit RX- und TX-Leitungen zwischen zwei Teilnehmern.

Meist wird einer dieser Teilnehmer durch das Protokolldesign die Rolle des Masters und der andere die Rolle des Slaves einnehmen. Mit dem Unterschied zur SPI oder I2C, dass der Slave, wenn er denn was wichtiges zu sagen hat, einfach darauf los senden könnte.

Tipp: Bei den Protokollen wo der Master den Clock treibt (SPI/I²C), wird oft ein extra IRQ Pin verwendet, damit der Slave darauf hinweisen kann, dass er was wichtiges mitzuteilen hat.

#1

Betrachten wir die erste Möglichkeit des Framings und damit zum Telegrammaustausch.

Alle Nachrichten haben eine feste oder sogar die selbe Länge. Wir definieren:

  • per Protokolldef. soll es einen Master und einen Slave geben.
  • der Master sendet immer zwei Byte
  • der Slave antwortet mit einer Nachrichtenlänge abhängig der gesendeten Bytes des Masters

z.B.

  1. erste Byte: 0x01 für lesender Befehl
  2. zweite Byte: 0x02 für Temperaturregister

Der Slave hat nun zwei Bytes zu senden. Diese werden vom Master empfangen und als Temperaturwerte behandelt. Das Framing wird für den Master bei jeder neuen Nachricht begonnen. Das Framing des Slaves basiert auf dem Intervall von zwei Bytes.

Probleme bei dieser Variante:

  • der Slave kann z.B. beim Start der Schaltung desychronisieren und verwechselt damit die Reihenfolge der zwei Bytes. Der Slave sollte daher über einen zeitbasierenden Reset verfügen: Länger als X ms kein Byte erhalten? Dann kommt als nächstes sicher das erste Byte! Der Master sollte um diese Funktion wissen und etwas Zeit zwischen der Kommunikation lassen.
  • Das Framing des Masters kann durch die asynchrone Kommunikation ebenfalls schief gehen. Sendet der Master gerade seine Anfrage und der Slave beantwortet gerade noch die vorangegangen, kommt es zu Race Conditions die schwer bis gar nicht lösbar sind.
  • Bekommt der Master in der Zeit X keine Antwort oder zu wenig Bytes, muss ein Timeout erfolgen und darf nicht in einer Endlosschleife ewig warten. Dies gilt übrigens für ausnahmslos alle nachfolgenden Beispiele und Möglichkeiten.

Lösungen und Vorteile:

  • Gemütlich kommunizieren! Genug Zeit für die Nachrichtensychronisation belassen und schon treten die oberen Probleme kaum mehr auf.
  • Einfaches Protokolldesign für den Master.
  • Ist jeder Befehl des Masters immer nur ein Byte groß, ist ein Framing beim Slave nicht nötig -> ebenfalls sehr einfaches Protokolldesign des Slaves.
slave_out_of_sync

slave device desychronized

Ein Beispiel für dieses Protokolldesign ist mir bei einem Motortreiber bereits begegnet und ebenfalls bei dieser Relaiskarte:

http://www.produktinfo.conrad.com/datenblaetter/175000-199999/197720-an-01-ml-8FACH_RELAISKARTE_24V_7A_de_en_fr_nl.pdf

#2

Um zu vermeiden, dass der Slave seine Synchronisation über längere Zeit ohne “Anhaltspunkte” halten muss, kann ein Startbyte und/oder ein Endebyte an die Nachricht angehängt werden.

Dies Framing-Bytes sollten entweder einzigartig oder zumindest leichter wiederzufinden sein. Dazu könnte die Länge der Nutzdaten mit versendet werden. Dies führt zu dem Vorteil, dass Nachrichten ganz unterschiedlicher Länge versendet werden können. Die Empfänger vergleichen auf das Startbyte und geht bei dem nachfolgendem Byte von der Länge der Nachricht bis zum Endebyte aus.

Die Start- und Endebytes dienen dabei der Verifikation und im Fall einer desynchronisierung wird der Empfänger im Datenstrom ein Startbyte suchen.

Nachteile dieser Variante:

  • Das Protokoll kann sich auf ein falsches Byte in den Nutzdaten einschwingen und damit wird ein falsches Längenbyte ansetzen.
  • Ist daraufhin die Länge der Zeichen fälschlich hoch, kann die synchronisierung einige Pakete dauern.
  • Die erneute synchronisierung ist nicht sichergestellt und hängt von den Nutzdaten ab.

Folgende Tabelle stellt eine beispielhafte Nachricht mit binärem Inhalt vor:

Startbyte

Länge Befehl Nutzdaten Endebyte
0x01 0x02 0x11 0x01

0x02

Angenommen dies Nachricht wird mehrmals versendet und der Empfänger verliert bei „Befehl“ das Framing, dann versucht er erneut das Startbyte zu finden:

  1. Befehl 0x11 ist kein Startbyte
  2. Nutzdaten 0x01 ist das erkannte Startbyte
  3. Endebyte wird als Länge angenommen, also 2
  4. das neue Endebyte muss sich nun bei Befehl befinden
  5. dort ist kein Endebyte -> Nachricht nicht gültig
  6. neues Startbyte suchen -> Nutzdaten ist das erkannte Startbyte
  7. usw.

Wie zu erkennen ist, würde bei diesem wiederkehrenden Nachrichteninhalte keine erneute Synchronisation erfolgen.

Obwohl ein zusätzliches Endebyte in Kombination mit dem Startbyte und der Länge eine recht niedrige Wahrscheinlichkeit ergibt, dass eine falsche Nachricht durch kommt, ist dieses Protokolldesign nicht bei sensiblen Daten und Anwendungen zu empfehlen.

Da es nur einfache Vergleiche und Zähler enthält, ist es von der Rechenzeit her sehr sparsam und für die schwächsten Mikrocontroller noch gut geeignet.

Bekannte Beispiele sind Protokolle für die LED-Ansteuerung:

tpm2: http://www.ledstyles.de/index.php/Thread/18969-tpm2-Protokoll-zur-Matrix-Lichtsteuerung/

oder mit fester Länge bei unterschiedlichen Befehlen:

minidmx: http://www.dmx.snoefler.de/

#3

Ein sehr sicheres Framing erhält man durch Einsatz von eindeutigen Start und Endebytes. Bei einem String ist Beispielsweise die nachfolgende 0x00 immer ein eindeutiges Zeichen für das Ende der Zeichenkette (im Speicher). Ebenfalls sind Zeilenumbrüche wie Carriage Return oder Line Feed (<CR><LF>) ein guter Marker für das Ende einer versendeten Nachricht.

Dies wird zum Beispiel bei den AT-Commands von Funkmodulen und bei den NMEA GPS Module so gehandhabt.

http://www.telit.com/fileadmin/user_upload/products/Downloads/2G/Telit_AT_Commands_Reference_Guide_r23.pdf

https://de.wikipedia.org/wiki/NMEA_0183

Damit dürfen leider keine binären Daten übertragen werden, sonst besteht die Gefahr, dass diese Terminierungszeichen darin auftauchen.

#3.1

Also Lösung könnte man die Zahlenwerte in ein String wandeln. Alternativ besteht die Möglichkeit die gesamte binäre Nachricht in ein HEX Zeichenfolge in ASCII Darstellung zu wandeln.

Also z.B.: 64F3ABE1<LF>

Nachteilig wäre der etwas höhere Rechenaufwand und die doppelte Bandbreite, da aus einem Byte zwei werden.

Umgesetzt wird dies ebenfalls bei GSM-AT-Modems, bei der SMS-Codierung als “HEX” ist es dem fehlerbehafteten PDU-Format vorzuziehen.

#4

Eines der stabilsten Protokolle wird leider viel zu selten eingesetzt. Es geht um das Byte Stuffing. Dabei gibt es wieder ein Ende- und/oder Startbyte das einmalig ist. Alle weiteren Daten können binär übertragen werden. Wenn jedoch eines der eindeutigen Zeichen vorkommt, werden diese durch ein sogenanntes Escape-Zeichen und einem definierten Zeichen ersetzt. Durch das zusätzliche Escape-Zeichen, muss dieses Zeichen ebenfalls ersetzt werden. So wird das Protokoll absolut eindeutig.

Ein kleines Problem ist, dass nicht genau gesagt werden kann wie viel Overhead dieses Protokoll hat, da es immer auf die Nutzdaten ankommt. Eine Nachricht die viele Start-, Ende- oder Escapebytes enthält, wird länge alles Nachrichten ohne. Für dieses Problem gibt es ebenfalls Lösungsansätze auf die ich hier jedoch nicht eingehen werde.

Hier ist eine kleine bebilderte Umschau zum Bit und Byte Stuffing:

https://web.cs.wpi.edu/~rek/Undergrad_Nets/B06/BitByteStuff.pdf

Tipp: Oft wird das Startbyte gar nicht gebraucht. Im Gegensatz zum Endebyte könnt ihr es gern weglassen. Das Endebyte ist jedoch nötig um die Nachricht abzuschließen und verarbeiten zu können. Würde man sich nur am Startbyte orientieren, müsste zum Auswerten der vorangegangenen Nachricht bis zur nächsten Nachricht gewartet werden.

Empfangsparser erstellen

Das Empfangen von Zeichen sollte immer mit einer Statemachine getan werden. In vielen Anwendungen ist es wichtig, dass der Task nicht blockierend arbeitet und auch weitere Aufgaben vom Controller verarbeitet werden können.

Oft ist es Ratsam eine kleine Software FIFO die empfangenen UART-Zeichen einlesen zu lassen, per Interrupt oder auch DMA. In der Hauptschleife wird nun geprüft ob neue Zeichen zur Verfügung stehen. Sollten Zeichen vorhanden sein, werden diese in den Protokollparser gegeben.

statemachine

example state machine of a receiver

Wie man sich evtl. denken kann, benötigt dieser Parser einen Puffer der die Größte zu erwartende Nachricht speichern kann. Andernfalls würde der Speicher überlaufen. Dies ist natürlich zuvor immer zu prüfen.

Steht nach dem Startbyte die Nachrichtenlänge, müsste diese eingelesen werden und es wird heruntergezählt. Bei 0 sollte dann ein Endebyte empfangen werden oder es ist etwas schief gegangen.

Sicherung

#1

Viele kleine Mikrocontroller haben schon eine eingebaute CRC-Einheit. Eine an die Nachricht angehängte CRC sollte ein Minimum sein, wenn sensible Anwendungen erstellt werden. Ungültige Nachrichten mit fehlerhaft übertragenem Inhalt werden im einfachsten Fall verworfen.

#2

Somit kommen wir zu einer zweiten Sicherung im Protokolldesign: die Retransmits. Sollte eine Nachricht nach einer bestimmte Zeit nicht beantwortet werden, kann die Nachricht wiederholt werden. Dies muss nicht für jede Nachricht gelten und kann auch dem Benutzer überlassen werden.

#3

Das wiederholte Senden von Nachrichten hat jedoch eine weitere Tücke. Der Sender kann nicht sicherstellen ob die Nachricht bei der Gegenstelle nicht ankam oder ob nur die positive Bestätigung (acknowledge) verloren gegangen ist.

Sollten Nachteile dadurch entstehen, wenn die Gegenstelle zwei aufeinanderfolgende gültige Nachrichten erhält, sollte eine Sequenz ID eingeführt werden. Daran kann erkannt werden, ob die Nachricht nur ein Retransmit darstellt und nur die ACK-Nachricht nachgeholt werden muss oder die übliche Reaktion durchgeführt werden muss.

Beispiel:

Der Slave multipliziert eine Zahl immer mit dem Inhalt der Nachricht des Masters und sendet eine Bestätigung, falls die Multiplikation erfolgt ist. Wenn nun das ACK des Slaves verloren geht, sendet der Master die selbe Nachricht erneut, ohne zu wissen das die Multiplikation bereits erfolgt ist. Eine Sequenz ID lässt den Slave erkennen ob er diese Nachricht schon mit einem ACK beantwortet hat oder noch bearbeiten muss.

Eine andere gute Lösung ist es, den Master einfach das Produkt (Faktor * Faktor = Produkt) abfragen zu lassen, um erneut synchronisieren zu können, diesmal jedoch auf einer ganz anderen Ebene.

 

Ich habe sicher noch einige Varianten vergessen Ich hoffe jedoch die wichtigsten Protokolldesignschritte herausgestellt zu haben. Falls ihr noch Fragen habt, schreib einfach einen Kommentar.

Veröffentlicht unter Allgemein | Kommentar hinterlassen

Masterthesis

Meine Masterthesis wurde mit einem Preis bedacht:

http://www.htwk-leipzig.de/de/hochschule/aktuelles/nachrichten/nachrichten-details/detail/sensormodul-fuer-atemluft-hilft-krankheiten-aufzuspueren/

Es ging in meiner Arbeit darum in ein bestehendes Medizinprodukt der Leipziger Firma Fischer Analysen Instrumente GmbH (FAN) ein neues Sensormodul zu integrieren. Dieses soll über ein Array von Metalloxid-Halbleitergassensoren (MOX) die Konzentration von Wasserstoff und Methan erfassen. Also nicht nur Wasserstoff, wie im oberen Artikel erwähnt. Dieses Produkt gäbe es ja bereits bei FAN.

Das große Problem bei Gaskonzentrationsmessungen ist die Selektivität. Durch ein Array und die richtigen Algorithmen kann die Selektivität stark gesteigert werden. Gerade Sensoren die auf chemischen Prinzipien beruhen, wie der MOX, reagieren auf viele verschiedene oxidierende und reduzierende Gase mit einer Messsignaländerung. Durch Filterelemente und bestimmte Zusammensetzungen der Funktionsschichten (die reagierenden Elemente des Sensors) können unterschiedliche Kennlinien erzeugt werden. Durch verschiedene MOX und komplexer Machine-Learning-Algortihmen kann ein recht genauer absoluter Messwert errechnet werden. Ein aufwändiges Problem dabei ist, an die erforderlichen Vergleichsmessungen und Rohdaten zu kommen, um entsprechende Lernverfahren anstoßen zu können.

Weitere Schwierigkeit war die möglichst geringe Energieaufnahme, da es ein tragbares batteriebetriebenes Medizinprodukt (Handheld) ist. Außerdem war wenig Bauraum vorhanden, sonst wäre es möglich (viel teurere) Infrarotspektrometer einzusetzen. Diese basieren auf dem physikalischen Prinzip, dass bestimmte Gasarten bei bestimmten Wellenlängen reflektieren oder absorbieren.

Veröffentlicht unter Allgemein | Kommentar hinterlassen

Simulation von Bewegungsabläufen

Da ich meinem Roboter gern noch Kniegelenke spendieren würde und er damit das Laufen wieder selbstständig erlernen soll, habe ich mich an eine Simulation gewagt. (Bitte den gerade verlinkten Beitrag lesen, damit ihr diesen hier verstehen könnt.)

Das Problem mit Zufallszügen und zusätzlichen Kniegelenken ist ganz einfach: Der Roboter wird öfter so stürzen, dass er aufgerichtet werden muss. Das macht natürlich arbeit, da die Trainingsphase durch die zusätzlichen Möglichkeiten von Bewegungsabläufen sehr viel länge dauern wird. Die Anzahl an Möglichkeiten steigen mit Hüft- und Kniegelenken und eine alte Positionen (History) an den Eingängen von 729 auf 531.441 Möglichkeiten.

Mit einer PC-Simulation kann viel einfacher bewertet werden, ob der Roboter tatsächlich umgekippt ist bzw. in einer unerwünschten Position landet und außerdem ob er die Füße bei der Laufbewegung über den Boden schleifen lässt. Was bei einem rutschigem Untergrund noch ganz gut ging, wird bei einem Teppich zum Problem.

Diese zusätzlichen Möglichkeiten eröffnen dem Agent ganz neue Bewertungsansätze und das neuronale Netzwerk kann darauf konditioniert werden „schöne“ und schnelle Bewegungsabläufe zu erlernen. Nach der Simulation soll das erlernte ANN einfach in den Roboter überspielt werden. Ist die Simulation sehr nah an die Realität, führt dies zu einem lauffähigem Roboter mit Kniegelenken, ohne Programmierung der Bewegungsabläufe.

Für diese Art der Simulation werden nur relativ wenige Eigenschaften der Physik gebraucht. Wir brauchen Gravitation bzw. Erdbeschleunigung und damit auch korrekt simulierte Gewichte der einzelnen Komponenten und der Massenmittelpunkte. Damit fällt schon einmal alles so wie es soll.

Damit auch die Servomotoren simuliert werden können, bedarf es einer Beschleunigungskraft die auf die Achsen wirkt und einer Haltekraft, wenn das Getriebe blockiert, bzw. der Servo mit Motorenergie auf Position geregelt wird.

Als Simulationsumgebung habe ich mich erst an einer reinen Python-Umgebung versucht. Mit dem Modul PyODE können Objekte erstellt und mit Gelenken verbunden werden. Das ist insgesamt recht Aufwändig und außer Zahlen gibt es nichts zu sehen. Kombiniert man die Physik-Engine mit VPython kann eine 3D-Welt erstellt werden. Jeder Schritt wird also einzeln vorgenommen: PyODE errechnet die Bewegung der Massen und mit VPython muss ein entsprechendes 3D-Objekt um diese Massen gelegt werden. Für einfache Sachen wie ein doppeltes Pendel war es auch recht gut lösbar, aber bei größeren Aufbauten habe ich komplett die Übersicht verloren und meine 3D-Welt ist immer mehr aus der Reihe getanzt.

Eine gute Entscheidung war es daher die freie 3D-Software Blender  zu installieren und erste Gehversuche damit zu unternehmen. Ich habe früher einmal mit Cinema4D gearbeitet und im Studium kurz mit Autodesk und Inventor, aber Blender toppt sie alle an Komplexität! Dafür ist jedoch auch unglaublich viel möglich und genau die Sachen die ich benötige: 3D-Design, Physik-Simulation und Zugriff auf alle Objekte und Eigenschaften mit der Skriptsprache Python (Annahme).

Nach einigen Stunden Einarbeitung (6 h?) ist mir ein einfaches Model von einem möglichen zukünftigem Roboter gelungen:

Dazu habe ich pro Gelenk jeweils ein Hinge (Scharnier) eingesetzt, aber die Bewegung auf -45° bis +45° begrenzt, was auch schön zu erkennen ist. Aktuell sind die Hinge noch freischwingend und werden nicht von einem Motor getrieben. Jedoch habe ich im Video bereits ab der vierten Sekunden das vordere Hüftgelenk angestoßen, so dass der „Roboter“ umfällt.

Ich bin nun leider an einer Stelle angelangt an der ich die Koordinaten und Winkel der Objekte und Gelenke zur Simulationszeit in Python benötige. Leider habe ich noch keine Möglichkeit gefunden diese Daten zu extrahieren. Wenn jemand weiß, welche Objekte dazu benötigt werden, dann bitte ein Kommentar da lassen. Damit geht es an dieser Stelle weiter, wenn ich weitere Erkenntnisse erlangen konnte.

Meinen aktuellen Arbeitsstand gibt es wie immer auf meiner Github-Seite:

https://github.com/Counterfeiter/RoboSimulation

Veröffentlicht unter Allgemein | Kommentar hinterlassen

Weihnachtslieder zum Fest

Wer noch ein Last-Minute Weihnachtsgeschenk braucht das garantiert selbstgemacht ist, der hole jetzt bitte ein ATTiny45 (4 KB Flash) oder ATTiny85 (8 KB Flash) aus der Bastelkiste! Denn mein Tiny-Song-Driver hat von Corina Dattler ein paar neue Noten für Weihnachtslieder spendiert bekommen.

Zur Auswahl wären:

  • O du fröhliche
  • Leise rieselt der Schnee
  • Fröhliche Weihnacht überall

für andere Anlässe gibt es noch:

  • Zum Geburtstag viel Glück
  • Für Elise
  • Wedding March

Die kreative Verpackung der Elektronik überlasse ich eurer Fantasie. Um jedoch einen 27 mm Piezo-Beeper richtig laut zu bekommen, empfehle ich Nespresso-Kapseln als „Boxengehäuse“.

Inspiration kann sich auch hier geholt werden: https://www.facebook.com/Dekowerkstatt-Dattler-340059932846663/

NespressoBots als Weihnachtsglöckchen für den Baum, ist eine sehr schöne Idee!

nespresso

Wer möchte kann auch gern noch ein paar Platinen von der gezeigten Sorte bekommen. Ich würde diese zum Versandpreis im Umschlag verschicken, weil bald Weihnachten ist.

Veröffentlicht unter Allgemein | Kommentar hinterlassen

Robot controlled by artificial neural network

In meinem vorletztem Blogpost ging es um ein einfaches Beispiel für Neuronale Netze und Reinforcement Learning: Hello World ANN Projekt. Ich empfehle jedem mit dem einfachen Beispiel anzufangen.

Hier soll es nun um einen Roboter gehen der mit vier Servomotoren, etwas Lego, Kleber und Schrauben in einer Stunde zusammengebaut wurde. Er ist mit Sicherheit keine Schönheit und auch mein erster Roboter überhaupt. Davor hat mich die Thematik Roboter, egal in welcher Form, gar nicht interessiert, aber ich verstehe schon langsam die Faszination dahinter.

Hier ein Bild des schlauen Gefährten:

img_3787

Außer der vier Servomotoren als Beine gibt es noch eine Ultraschallkapsel zur Entfernungsmessung und das STM32F407 Discovery-Board als Steuerzentrale, bekannt aus einigen meiner anderen Projekte. Die externen Kabel sind zur Stromversorgung und Programmierung (weiß) und ein UART-USB-Wandler (schwarz), um zu schauen, was der Robi gerade so treibt (Debug printf).

Jetzt hatte ich natürlich keine Ahnung davon wie man die Beine optimal ansteuert, um eine Vorwärtsbewegung zu programmieren. Programmieren wollte ich schon mal gar nicht. Ich wollte ein künstliches neuronales Netz mit der Aufgabe „beauftragen“. Zumal die Aufgabe gar nicht einfach ist, an welchem Tier ohne Kniegelenke und Fuß sollte man sich als aufmerksamer Mensch orientieren? Vorschläge gern in den Kommentaren…

Für die Beinbewegung musste ich erstmal einen Servo-Treiber schreiben, der auch eine Geschwindigkeitsbegrenzung der Bewegung erlaubt. Die Beine sollten also nicht so schnell wie möglich von einer Position zu anderen rauschen.Womöglich wäre sonst der ganze Roboter schon auseinander gefallen.

Nun ein paar Gedanken zum Modell mit KNN/ANN und Q-Learning:

  • Um die Aufgabe durch Q-Learning lösen zu können, muss ein MDP modellierbar sein. Das heißt vereinfacht, nur Zustände keine Analogwerte als Ausgangswerte. So direkt kann das ANN die Motoren also nicht ansteuern.
  • Die Anzahl der Möglichkeiten die das System annehmen kann, sollten nicht zu groß werden, sonst würde der Lernprozess viel zu lange dauern.
  • Die Eingangswerte sollten die aktuellen Motorpositionen sein. Damit das ANN aber ein Gedächtnis bekommt müssen auch ältere Zustände als Input eingefügt werden. Dies könnte man zwar mit einem RNN geschickter lösen, aber dieses Netzwerk steht mit der FANN lib nicht zur Verfügung und lernt auch algorithmisch viel aufwändiger.
  • Besteht die optimale Bewegung aus vier Grundschritten werden 4 * 3 Input-Neuronen nötig: Vier Motoren mit der aktuellen Position und zwei alte Positionen für jeden Motor.
  • Die Output-Neuronen können keine anlogen Werte liefern. Da beim Q-Learning die beste Aktion maximiert wird(wer mag kann auch minimieren), stehen nur States am Ausgang des ANNs zur Verfügung.  Daher sollte die Anzahl der Motorpositionen pro Motor limitiert werden.
  • Sind am Ausgang drei Positionen pro Motor möglich, berechnen sich die möglichen Zustände der Eingänge wie folgt:
    power(Zustände, Input-Neuronen) = power( 3, 12 ) = 531441 Möglichkeiten
    Etwas viel um diese in annehmbarer Zeit halbwegs abdecken zu können. Jedoch gibt es sicher sehr viel ähnliche Bewegungen, die zum selben Ergebnis führen (symmetrische Bewegungen x-,y-Achse).

Nach diesem Gedankenspiel und natürlich einigen Stunden an Versuchen bin ich auf folgende ANN-Konfiguration gekommen:ann_config

Der Agent vergibt die Rewards (maximiert eine gute Aktion), wie in nachfolgendem Bild dargestellt.

agent

Für den Lernprozess habe ich einige Varianten aus den aktuellen Patenten und Papers der von google übernommenen Firma Deep Mind übernommen und getestet:

https://www.google.com/patents/US20150100530 -> Patent zum Q-Learning auf einer alten Kopie des ANNs

https://storage.googleapis.com/deepmind-data/assets/papers/DeepMindNature14236Paper.pdf -> ein paar Tipps und Tricks, wie Deep Mind die Netzwerke parametriert hat

Das Kopieren des ANNs (Patent) sorgt natürlich dafür, dass doppelter Speicher für die Gewichtungen und Verbindungen der Netze reserviert werden muss. Ein Netzwerk wird dabei nur trainiert und die Bibliothek FANN erzeugt hierfür noch einiges an Hilfsvariablen. So war recht schnell der Speicher voll (128 KB). Damit konnte ich das Kopieren des ANNs nur unzureichend testen. Jedoch habe ich letztendlich auch ohne das Vorgehen gute Ergebnisse erhalten. Die Begründung das Netz aller X Trainingszyklen zu kopieren, ist ein zu starker Lernanstieg bei guten Aktionen, der zu einer Art Schwingung und Instabilität führt, ähnlich wie es bei anderen Reglern passieren kann. Ich stell mir das Vorgehen/Patent wie ein Tiefpassfilter für ANNs vor.

Experience Replay habe ich diesmal intensive verwendet. Dazu habe ich 100 Trainingszyklen aufgezeichnet. Nachdem der Speicher voll war habe ich einfach das aktuelle Ereignis an eine zufällige Position des Speichers geschrieben, also einen alten Wert überschrieben. Danach wurden in jeder Iteration 20 zufällige Trainingszyklen ausgewählt, die Bereits vom Agent bewertet wurden. Mit dieser Minibatch wurde ab dem hundertstem Trainingszyklus trainiert. Der Unterschied ist, dass die Gewichtungen des Netzwerks erst nach dem Durchlauf einer kompletten Minibatch aktualisiert werden (eine Epoche). Dies verhindert ein Verändern der selben Gewichtungen in unterschiedliche Richtungen, da mehrere Daten als Referenz zur Verfügung stehen und sich dadurch bessere Strategien ergeben („der Blick fürs Ganze“).

Da die Minibatch natürlich nur Mini ausfällt, sollte man es mit der Lernrate nicht übertreiben, sonst wird die aktuelle Auswahl überbewertet. Die resultierenden Ausgänge sollten sehr selten -1.0 (min) oder +1.0 (max) sein und möglichst wenige Ausgänge sollten die selben Werte annehmen.

Eine falsche Lernrate führte zu folgendem, zugegeben recht witzigem, Ergebnis:

Die unterschiedlichen Bewegungsabläufe sind durch absichtlich hinzugefügten Ist-Winkel-Jitter der Servomotoren zu erklären. Die starke Änderung durch den leichten Winkel-Jitter ist mit Overfitting erklärbar.

Oder menschlicher ausgedrückt: Vorwärts ist er ein alter Mann mit Krückstock und Rückwärts ein Betrunkener der versucht Halt zu finden, indem er alle Gliedmaßen weiter auseinander streckt.

Es stellte sich während meiner Experimente heraus, dass die Ultraschallmessung den Abstand nicht immer korrekt wiedergab. Ein Tiefpassfilter erschien mir nicht ausreichend, da einige Werte zu stark abwichen. Ich nehme nun fünf Messungen pro abgeschlossene Bewegung und berechne den Median. Die Ergebnisse wurden damit deutlich besser, da weniger widersprüchliche Aktionen für Verwirrung stiften konnten.

Ein paar Dinge die nicht funktioniert haben oder nur einen sehr geringen Einfluss zeigten:

  • Die Fehlerrückführung in das ANN sollte nicht durch adaptive Lernraten vorgenommen werden. Da eine kleine Lernrate durchaus Messfehler verzeiht und verhindert das die Ausgangs-Neuronen schnell bei ihrem Maximalwert sättigen. Mit FANN sollte unbedingt der BATCH-Algorithmus verwendet werden.
  • Anfangs hatte ich Probleme mit der gerade beschriebenen Sättigung. Die Beine des Roboters haben sich nicht mehr bewegt. Um das zu verhindern habe ich zusätzliche Rewards für die Bewegung jedes Beines vergeben. Dies war jedoch nach der korrekten Einstellung nicht mehr nötig, da natürlich implizit eine Beinbewegung für einen positiven Reward nötig ist.
  • Deep Mind meinte im Atari Paper bessere Ergebnisse erzielt zu haben, wenn der Reward bei -1,0 oder 1,0 abschnitten wird, da ja auch das Netzwerk keinen Output über dieser Größe zulässt. Ich kann das nicht bestätigen, jedoch war der Reward nicht so oft über diesem Wert.
  • Weniger Lernzyklen als 300 brauchen nicht ausprobiert werden. Dazu ist die Anzahl der Möglichkeiten zu groß. Meist habe ich 700 genommen. Je nach Einstellung dauert eine Lernphase um die 12 Minuten.
  • Mehr als ein alter Schritt (Bewegungs-History) ist nicht nötig, da auch bei größerer History der Roboter nur zwei verschiedene Bewegungen erlernt. Außerdem würde sonst die Eingangsmöglichkeiten schnell ansteigen. Dies erfordert mehr Trainingszyklen, um diese auch effektiv auszunutzen. Jedoch kann man dies Reduzierung erst sehen, wenn schon versucht wurde ein Netzwerk mit größerer History zu trainieren, jedoch nur zwei Bewegungen als effektiv angenommen wurden.

Wenn die passenden Parameter gefunden sind, dann könnte es so aussehen:

Der komplette Quellcode ist wie immer in meinem Github-Account zu finden:

https://github.com/Counterfeiter/Q-LearningRobot

Es ist nach jedem Parameterwechsel interessant zu sehen, was der Roboter diesmal anstellt und gelernt hat. Es ist schon erstaunlich, wie er sich das Laufen selbst beibringen kann. Ich habe mir nicht mal die Arbeit gemacht bei gegenüberliegenden Servos die Winkelposition zu invertieren. Da auf der einen Seite das Bein bei gleicher Ansteuerung vorn und auf der anderen Seite nach hinten gezogen wird. Das findet das Netz recht schnell selbst heraus.

Auch deuten die aktuelle veröffentlichten Untersuchungen und erteilten Patente darauf hin, dass man ganz dicht hinter der „neusten“ Forschung experimentiert. In welchen anderen Bereichen kann ein Hobby dies schon aufweisen? Vielleicht findet man durch ein paar Versuche selbst noch optimalere Ergebnisse…. spannend!

Ich hoffe auf viele weitere Roboter die aufbauend auf diesen Grundlagen und dem Quellcode das Licht der Hobbywelt erblicken. Lasst mich von eure eigenen Kreationen über die Comments wissen…

Veröffentlicht unter Allgemein | 6 Kommentare

HC-SR04 Driver

Ein Ultraschallabstandssensor ist für mein aktuelles Projekt recht praktisch und den HC-SR04 hatte ich noch in der Bastelkiste liegen.

Der Ultraschallsensor funktioniert recht simpel: Auf eine fallende Flanke am Trigger-Eingang wird das Signal abgesetzt. Nach einer kurzen und definierten Verzögerung (Offset), wir der Echo-Ausgang auf High gesetzt, so lange bis das Echo des Ultraschalls zurück kehrt. Sollte das Signal verloren sein, z.B. bei zu weiten Entfernungen oder bei zu weichen Oberflächen, bleibt der Echo-Pin für 200 ms auf High. Dies signalisiert den Fehler.

Eigentlich ganz einfach. Einen fertigen Treiber dafür zu finden und zu übernehmen, sollte ja schnell gemacht sein. Die ersten google Treffer waren leider nicht überzeugen. Alles sehr kompliziert geschrieben. Zu viel Quellcode für zu wenig Funktion deutet darauf hin, dass der Sensor nicht verstanden wurde oder die Programmiererfahrung nicht ausreichend ist.

Nagut, also doch einen eigenen kleinen Treiber schreiben. Es sind ja auch nur meine Ansprüche an den Treiber und funktionieren tun sie hoffentlich alle.

Mein Projekt beruht auf einem CortexM4 (STM32F4) und mittlerweile habe ich mich ganz gut an den CubeMX von ST Microelectonics gewöhnt, wahrscheinlich weil einige Kinderkrankheiten mittlerweile beseitigt sind. CubeMX geniert zu einzelnen Peripheriebetandteilen Quellcode. Die GPIOs können zum Beispiel bequem per GUI ausgewählt werden, wie die Timer auch.

Zugegeben, auch deswegen ist mein Treiberquellcode schmal und enthält nicht die Initialisierung der Hardware. Die Initialisierung ist aber schnell erklärt.

CubeMX oder eigene Konfig (andere µC)

Einen Timer mit PWM-Funktion anlegen. Das Duty Cycle wird auf ca. 0,5 gesetzt (nicht kritisch) und der Timer muss aller 20 ms überlaufen. Praktisch ist es, wenn dabei ein Timer-Maximalwert von 20000 eingestellt werden kann. Das rechnet sich leichter (für Menschen), jedoch kann der Timer-Vorteiler nicht bei jedem Mikrocontroller so genau eingestellt werden. Über die 20 ms sollten aber genug Auflösung gegeben sein -> möglichst hoher Timer-Endwert.

Der PWM-Pin des Timers triggert das Echo. Die fallende Flanke muss beim Timeroverflow passieren. Evtl. muss dazu der Ausgang invertiert werden (im Timer Modul).

Der Overflow-Interrupt des Timers sollte Konfiguriert werden.

Der Echo-GPIO-Eingang sollte ein Interrupt bei fallender Flanke auslösen.

Der Quellcode

static volatile int hcsr04_timestamp = 0;
static volatile int overflow_flag = 0;

//timer PWM (DC 0,5) falling edge at overflow (trigger pin) -> 20 ms interval = 20000 digits
//and falling edge gpio interrupt (echo pin)
//ready to run
//if not, set it up in this function
void hcsr04_startMeasure(void)
{
 //start the timer, to measure the echo flight time right after the falling trigger edge
 __HAL_TIM_ENABLE_IT(&htim12, TIM_IT_UPDATE);
 HAL_TIM_PWM_Start(&htim12, TIM_CHANNEL_1);
}

//returns actual distance or if a error occurs 0 mm
uint32_t hcsr04_getLastDistance_mm(void)
{
 if(hcsr04_timestamp == 0) return 0; // timer overflow signal -> problem with measurement
 int ret = ((hcsr04_timestamp * 343) / 1000 - 154) / 2; //mm per 10 us - 154 mm offset -> double distance => / 2
 return ret < 0 ? 0 : ret > 2000 ? 0 : ret;
}

//callback, use it in timer overflow interrupt
void hcsr04_cb_timeroverflow(void)
{
 //check for sensor error (200 ms timeout)
 overflow_flag++;
}

//callback, use it in pin interrupt (falling edge)
void hcsr04_cb_pin_fallingedge(void)
{
 if(overflow_flag > 1 || overflow_flag < 0)
 {
  //discard one more measure after 200 ms timeout
  overflow_flag = -1;
  hcsr04_timestamp = 0;
 } else {
  //save the value of the timer, to calculate the distance
  hcsr04_timestamp = (overflow_flag != 1) ? 0 : htim12.Instance->CNT;

  //reset overflow flag
  overflow_flag = 0;
 }
}

Die zwei Funktionen mit dem Namen cb, sollten bei den entsprechenden Interrupt-Funktionen aufgerufen werden.

Folgender Test-Quellcode list die Distanz aus:

//start timer
 hcsr04_startMeasure();
 while(1)
 {
 printf("Distance: %d\n", (int)hcsr04_getLastDistance_mm());
 HAL_Delay(200); //delay 200 ms
 }

Erklärung zum Treiber:

Sollte der Timer-Interrupt öfter auftreten als der GPIO-Interrupt , liegt eine Messstörung vor. Damit diese erkannt wird und 0 mm ausgegeben werden kann, zählt das overflow_flag die Überläufe. Außerdem hat sich herausgestellt, dass manchmal eine gültige aber falsche Messung direkt nach einem Overflow auftritt (auch auf dem Oszi gesehen). Das overflow_flag verwirft daher die erste Messung nach einem Overflow ebenfalls. Natürlich könnte man es auch so umschreiben, dass immer die letzte gültige Messung ausgegeben wird, jedoch bekommt dann das Anwendungsprogramm darüber keinen Hinweis. Bei einem längeren Signalverlust könnte das zu einem Problem werden, um welches sich nicht der Treiber sondern die Applikationsschicht kümmern muss.

Jede Mikrosekunde (Timer-Tick) bewegt sich der Schall bei 20 °C mit einer Geschwindigkeit von ca. 0,343 mm. Die Berechnung sorgt für eine rundungsfehlerfreie Ausgabe. Dazu muss man nur die Formel so umstellen, dass Divisionen möglichst spät und damit durch hohe Zahlen durchgeführt werden. Die 154 mm sind der Offset der durch die langsame Sensorreaktion entsteht (siehe Datenblatt).

Abschließend

Dadurch, dass kaum Hardwarespezifische Dinge im Quellcode getan werden, sollte dieser Treiber problemlos auf alle Mikrocontroller portiert werden können.

Veröffentlicht unter Allgemein | 1 Kommentar

Künstliche neuronale Netze auf einem Mikrocontroller

Einleitung

Wo man auch hinschaut, alles spricht von künstlicher Intelligenz (KI, eng: AI). Jene die sich mit dem Thema etwas eingehender beschäftigen betitelten es eher als machine learning bzw. machinelles Lernen.

Einen kleinen Überblick gab es diese Woche auch auf 3sat, beim Wissenschaftsmagazin nano, das ich nur allen wärmsten empfehlen kann. Nicht unbedingt nur diese Folge, sondern allgemein ist diese Magazin sehr gut umgesetzt.

Die wirklich interessanten Einsatzgebiete sind jedoch zu uninteressant, um diese im TV einem allgemeinen Publikum aufzubereiten. Große Datenmengen analysieren, zuordnen oder durch Regression Vorhersagen treffen.

Beispiele:

  • Suchanfragen an den Benutzer anpassen: Wenn ich zuvor wieder und wieder etwas über das Programmieren gesucht habe, dann werde ich bei der Eingabe von „C Aufbau“ nicht die Note meinen, da ich anscheinend eher weniger musikalisch bin. Ich bin also an der Programmiersprache interessiert. Dazu müssen logischerweise möglichst viele Daten über mich gesammelt werden. Natürlich kann das Netzwerk was meine Daten aufbereitet auch andere Anfragen bearbeiten: Hobbys? Beruf? Interessen? -> Welche Werbung soll präsentieren werden? Insgesamt also eine Win-Win Situation?! Ein potenzieller Arbeitgeber der Zugriff auf diese Daten hätte, könnte meine C-Kenntnisse von der KI abfragen lassen. Dann lande ich im Ranking mit der Anfrage „C Aufbau“ auf den hinteren Plätzen. Wobei man mit „C function pointer callback“ in den vorderen Plätzen landet. Wer nicht glaubt wie einfach das ist, sollte mal folgendes Spiel probieren: http://20q.net/
  • Spracheingabe und Sprachausgabe: Siri und co. lassen grüßen und das in einer sehr guten Qualität. Zur Sprachausgabe werden bisher Laute aneinander gehängt, dass könnte sich auch bald ändern. Es gibt schon Netzwerke die direkt Binärdaten bearbeiten. Mit WaveNet lassen sich auch Emotionen in die Aussprache bringen. Leider ist der Rechenaufwand noch zu groß.
  • Bilderkennung: Ein gutes Beispiel von Klassifikation? Auch! PCs die Katzen- von Hundebilder unterscheiden können und bei den sozialen Netzwerken werden sofort die hochgeladenen Fotos mit den richtigen Freunden markiert. Jedoch kann der PC auch von den Bildern lernen und selbst tätig werden (von Kreativität möchte ich nicht sprechen). Ein bekanntes Beispiel ist googles DeepDream oder das Beispiel aus der Nano-Sendung.

Für die meisten Aufgaben könnte man die unterschiedlichsten machine learning -Verfahren verwenden. Durchgesetzt hat sich gerade bei sehr komplexen Aufgaben das künstliche neuronale Netzwerk. Dabei gibt es viele verschiedene Netzwerkstrukturen, die auch weiterhin Forschungsschwerpunkte bleiben werden. Welche Netzwerkstruktur kann welches Problem am besten lösen? Sind es die rückführenden Netzwerke, die Convolutional Neural Networks oder eine Kombination daraus die mein Aufgabenstellung lösen können? Vom eigentlichem Deep Learning wird immer dann gesprochen wenn das Netzwerk sehr viele Layer und Neuronen besitzt.

Was wohl immer zutrifft: Je komplexer die Aufgabe desto größer die nötige Rechenleistung oder desto cleverer der Entwurf des Netzwerkes.

Deep Learning auf dem Mikrocontroller?

Wenn man mit einem neuronalem Netzwerk soo viele Probleme lösen kann, wäre es doch praktisch diese Möglichkeit auf einem „kleinen“ CortexM Mikrocontroller ebenfalls verfügbar zu haben. Da Speicher und Prozessorleistung sehr begrenzt ist würde man wohl eher nicht vom Deep Learning sprechen. Für einfache „Multilayer-Feedforward-Netzwerke“ reicht es aber allemal.

Dafür habe ich die C-Bibliothek FANN (Fast Artificial Neural Network Library) auf den CortexM4 (mit FPU) portiert und verschiedene Benchmark-Untersuchungen unternommen. Diese werde ich evtl. später noch aufbereiten und auf dem Blog präsentieren.

Fazit war jedoch: Trainieren kann man ja auf dem PC und Ausführen auf dem Mikrocontroller, da alleine die Trainigdateien über der verfügbaren Flash-Größe liegen können. Dazu muss natürlich dem Mikrocontroller das angelernte Netzwerk übergeben werden. Das geschieht bei FANN über das Dateisystem, mit Hilfe von Konfigurationsdateien. Um keine Veränderungen an FANN selbst vornehmen zu müssen, habe ich dieses kleine Read-only Dateisystem entworfen.

Letztendlich habe ich mit der System Workbench FANN für den STM32F4 mit FPU (Hardware FPU Befehlssatz) cross-compiliert. Die entsprechende lib ist Bestandteil des Beispielprojektes und kann für weitere Versuche auf dem STM32F4 Discovery-Board oder anderen CortexM mit FPU verwendet werden. Später werde ich dem original FANN Github-Fork ein Static Lib – System Workbench Projekt hinzufügen.

Hello World or Blinky Neural Network Project

Ziel (sehr einfach): Ein einfaches Netzwerk wird trainiert, um eine der vier LEDs des Discovery-Boards nach der Trainingsphase blinken zu lassen. Der Benutzer kann sich durch zwei Buttons die LED aussuche. Aufbau KNN:

  • Vier Eingänge: der aktuelle Status jeder LED -> -1.0 = LED ist aus; +1.0 = LED ist an
  • Vier Ausgänge: soll LED an oder ausgeschalten sein -> -1.0 = LED aus; +1.0 = LED an
  • ein Hidden Layer mit 12 Neuronen (unnötig viel 😉 )

Ziel (einfach): Ein einfaches Netzwerk wird trainiert, um ein Blinkmuster auf den LEDs darzustellen. Dazu muss das Netzwerk auf die Übergänge zwischen den LEDs achten. Es darf keine LED doppelt aufleuchten, jedoch dürfen auch LEDs weggelassen werden. Der Benutzer kann sich durch zwei Buttons das Blinkmuster innerhalb der Spezifikation aussuche. Aufbau KNN:

  • Vier Eingänge: der aktuelle Status jeder LED -> -1.0 = LED ist aus; +1.0 = LED ist an
  • Vier weitere Eingänge: der vorhergehende Status jeder LED -> -1.0 = LED war aus; +1.0 = LED war an
  • Vier Ausgänge: soll LED an oder ausgeschalten sein -> -1.0 = LED aus; +1.0 = LED an
  • ein Hidden Layer mit 12 Neuronen (unnötig viel 😉 )

Es gibt unterschiedliche Arten, wie man ein neuronales Netzwerk trainieren kann. Mit Trainingsdaten wäre dieses „Hello World“ Projekt recht langweilig geworden. Ohne Trainingsdaten funktioniert es über das Reinforment Learning ganz ausgezeichnet. Dafür braucht es einen Agent. Dieser belohnt oder bestraft das Netzwerk, wenn die Aktion gerade nach Wunsch oder auch nicht stattfand. Den Agent könnte man sich programmieren, wenn die Möglichkeiten viel zu groß sind oder (wie in diesem Beispiel) man übernimmt  selbst die Aufgabe des Agents.

Da FANN keine Routinen für das bestärkende Lernen zur Verfügung gestellt, musste ich diese selbst implementieren. Ich habe mich für den Q-Learning Algorithmus entschieden und habe hier sehr gute Informationen und auch Implementierungsbeispiele erhalten:

http://outlace.com/Reinforcement-Learning-Part-3/

Einfach ausgedrückt funktioniert es so: Die Lernphase hat eine festgelegte Anzahl an Trainingszyklen. Am Anfang steht das untrainierte Netz. Es wird eine Zufallsaktion ausgeführt und auf die Bewertung gewartet. Die Bewertung ist schlecht, wenn der Fehler zwischen der erwarteten Aktion und der ausgeführten Aktion groß ist. Der Fehler wird durch einen Gradientenabstiegsverfahren (Backpropagation) Rückwärts durch das Netzwerk „geschickt“ und die Gewichtungen der Neuronenverbindungen werden angepasst. Nach und nach werden die Zufallsaktionen durch Vermutungen/Ausgaben die das Netzwerk trifft ersetzt. Bis am Ende fast ausschließlich Aktionen des Netzwerkes präsentiert werden.

Ein Problem besteht darin, innerhalb der Zufallsaktionen möglichst viele Möglichkeiten des Systems abzudecken, um das Netzwerk ausreichend trainieren zu können. Das Verhalten spiegelt sich auch in dem Hello World Projekt wieder: Nur eine LED blinken lassen benötigt nur ca. 10 Trainingszyklen, weil der Zufall hoffentlich jede LED einmal aufleuchten lassen hat. Für die Übergänge der LEDs gibt es viel mehr Möglichkeiten und daher werden auch mindestens 75 besser jedoch 100 Trainingszyklen gebraucht. Was natürlich für recht viel Arbeit sorgt und man muss selbst hochkonzentriert die Aktion bewerten. Daher ist mein Video auch weniger informationsreich geworden als geplant, weil ich mich stark auf die LED-Übergänge konzentrieren musste.

Genug der vielen Theorie, hier das Video des Projektes:

Das komplette Projekt gibt es wie immer auf meiner Github-Seite:

https://github.com/Counterfeiter/ANN-QLearning-CortexM4

Es ist darauf zu achten, dass FANN mit dynamischer Speicherreservierung arbeitet und das damit der Heap im Auge behalten werden sollte.

Gehen wir etwas in den Quellcode. Ein Netzwerk wird mit Standardwerten angelegt. Diese können aber durch einzelne FANN-Funktionen verändert werden. In diesem Beispiel wird die Aktivierungsfunktion aller Layer angepasst:

//create ann -> 1 hidden layer & (one input and one output layer)
 struct fann *ann = fann_create_standard(3, num_inputs, 12, num_outputs);

//use symmetric to deal with -1.0 and +1.0 -> normal for 0.0 to 1.0
 fann_set_activation_function_hidden(ann, FANN_SIGMOID_SYMMETRIC_STEPWISE);
 fann_set_activation_function_output(ann, FANN_SIGMOID_SYMMETRIC_STEPWISE);

Mit fann_run wird das Netzwerk ausgeführt. Dazu muss natürlich der Input-Vektor übergeben werden. Dieser muss selbstverständlich so viele Werte besitzen wie es Input-Neuronen im Netzwerk gibt. Die Rückgabe ist ein Pointer auf den Output-Vektor, der natürlich so lang ist wie es Neuronen am Ausgang gibt.

Da es beim Reinforcement Learning meist nur einen Datensatz gibt, wird dies effektiv mit fann_train angelernt. Da wir trainieren, müssen zu den Inputs auch die passenden Outputs übergeben werden. Q-Learning sorgt dabei dafür, dass im Ausgang der eingetretene Fehler „markiert“ wurde.

Wie man sieht, die FANN-lib nimmt erstaunlich viel Arbeit ab. Es sind gerade mal fünf verschiedene Funktionen angewendet wurden, um mit neuronalen Netzwerken arbeiten zu können. Klasse!

Wer sich selbst versuchen möchte, mein Vorschlag um die Funktionen weiter voranzutreiben: Es gibt durch die beschränkte Anzahl an Eingabevektoren keine Anhaltspunkt darauf wie oft eine LED vorher geblinkt hat. Das heißt, es ist nicht möglich das eine LED zwei mal aufleuchtet, bevor es zur nächsten LED übergeht. Die Lösung wäre für jede LED eine Zählvariable (normiert auf -1.0 bis 1.0) mit in den Input zu geben. Dies resultiert in ein beliebig komplexes Blinkmuster. Da die Möglichkeiten weiter steigen, müsste zielführend ein programmierter Agent das Netzwerk anleiten und über mehrere 100 bis 1000 Trainingszyklen führen. Die Anzahl der Hidden Layer und Neuronen wird, je nach Komplexität des gewünschten Blinkmusters, ansteigen müssen.

Ich wünsche happy coding mit neuronalen Netzen. Ich würde mich freuen, wenn ihr eure Ergebnisse in den Kommentaren hinterlasst.

 

 

Veröffentlicht unter Allgemein | 1 Kommentar