Optimierung des Straßenverkehrs durch Ampelschaltung

Sie haben ein bestimmtes Projekt zu bearbeiten und wissen nicht, wie Sie an die Aufgabe heran gehen sollen? Sie sind sich nicht sicher, ob Ihr Netzentwurf zu Ihrem Problem passt oder ob es da Optimierungsmöglichkeiten gibt? Ist es überhaupt sinnvoll an Ihre Daten mit einem NN basierten Ansatz heranzugehen? Ist MemBrain das richtige Werkzeug für Ihr Problem und Ihre Infrastruktur?

Hier ist der richtige Platz für diese Art von Fragen.
Kreatief
Posts: 10
Joined: Tue 5. Jan 2016, 09:43

Re: Optimierung des Straßenverkehrs durch Ampelschaltung

Post by Kreatief »

Wie könnte es weiter gehen.
Ich denke interessant sind zunächst die zwei Hauptpunkte: Das Netz und die Bewertung
Zum Netz sollte man festlegen wie genau die Neuronen aussehen und damit komme ich genau auf Ihren Punkt bzgl des komprimierten Inputs der TT.

Meine Idee:
Pro Ampel wird ein NN angelegt, dass folgende Neuronen bekommt:

INPUT:
- Ampelschaltung [1;0] (Was immer einem TT entspricht, der die Kreuzung passieren darf oder nicht)
- Zustand jeder Teiltransportstrecke (eventuell besser: jedes Materialflusselements), dass einen irgendwie gearteten Einfluss auf die Entscheidung haben kann
-- Dabei muss jeder Zustand folgende Infos beinhalten:
--- Anzahl TTs im Materialflusselement
--- Ziel der TT
--- Startzeitpunkt der TT (damit keine verhungert)

OUTPUT:
- Bewertung der Entscheidung


Kommt das hin?
Wie würde man nun den Zustand als Input abbilden? Wie viele Neuronen bräuchte man hier? Für jedes Materialflusselement (das somit statisch ist) ein Neuron mit Wert für die Anzahl der TTs (Transportdauer durch das MF-Element dürfte hier egal sein, da es durch die Simulation im Durchsatz am Ende enthalten ist).
Wie bildet man die (dynamischen) TTs mit ihren Zielen und Startzeitpunkten ab?
User avatar
TJetter
Posts: 341
Joined: Sat 13. Oct 2012, 12:04

Re: Optimierung des Straßenverkehrs durch Ampelschaltung

Post by TJetter »

Kreatief wrote:Wie bildet man die (dynamischen) TTs mit ihren Zielen und Startzeitpunkten ab?
Zu den Startzeitpunkten: Wie wäre es mit nur einer einzigen Info: Maximale Verweilzeit aus allen im Materialflusselement (MFE) befindlichen TT? Also die Verweilzeit des am längsten im MFE befindlichen TT? Könnte ausreichen und wäre eine schön kompakte Info, in einem Neuron abzubilden und diese Info könnte auch gleichzeitig in die Belohnung/Bestrafung pro RL-Iteration mit eingehen. Damit würde der Agent für 'verhungern' bestraft und für kurze Verweilzeiten belohnt bzw. weniger bestraft.

Schwieriger mit dem Zielort: Ich nehme an, in einem MFE können sich TT unterschiedlichen Zielorts befinden? Dann könnte man z.B. für jeden möglichen Zielort ein Eingangsneuron vorsehen, dass entsprechend der Anzahl TT im MFE mit dem zugehörigen Zielort weniger oder stärker aktiviert wird (also mit der Anzahl TT im MFE belegt wird, die diesen Zielort haben). Das könnte für den Agenten dann eine gewisse 'Zielortpriorität' repräsentieren, an der er seine Entscheidungen u.U. festmachen könnte.
Kreatief wrote:Meine Idee:
Pro Ampel wird ein NN angelegt, dass folgende Neuronen bekommt:
Das würde bedeuten, auch für jede Ampel einen eigenen RL-Agenten aufzusetzen (der sein eigenes NN pflegt), also der 'Schwarmansatz'. Ist mit einer schön objektorientiert aufgesetzten SW-Architektur in Summe wahrscheinlich einfacher und pflegeleichter, als einen einzigen Agenten mit unzähligen Inputs zu haben. Zudem kann man eine solche Architektur ja jederzeit auf einen einzigen Agenten heruntersetzen, wenn sich der Multi-Agenten-Ansatz als nicht zielführend erweist.
Thomas Jetter
User avatar
TJetter
Posts: 341
Joined: Sat 13. Oct 2012, 12:04

Re: Optimierung des Straßenverkehrs durch Ampelschaltung

Post by TJetter »

Nachtrag: Es wäre natürlich immer noch sehr schön, die Abhängigkeiten des einzelnen Agenten zu eliminieren, der Erweiterbarkeit wegen. Gibt es eine Systemgröße, die diese Abhängigkeiten ungefähr repräsentieren könnte, die aber Ihr Datenlayout nicht mit jeder Änderung bzgl. der MFE und Ampeln ändert?
Thomas Jetter
Kreatief
Posts: 10
Joined: Tue 5. Jan 2016, 09:43

Re: Optimierung des Straßenverkehrs durch Ampelschaltung

Post by Kreatief »

Die Verweilzeit finde ich gut so. Den Ansatz sollten wir so weiter verfolgen.

Bezüglich Zielort:
Auch das sehe ich genauso. Pro Ziel ein Eingangsneuron. Das NN muss dabei einiges lernen, was ich für sehr spannend halte:
Loop1 Ausgang (Übergang zu Loop2) fragt z.B. für S1 an. S1 ist voll, die anderen Senken leer. Nun gibt es zwei extrem Fälle:
a) Loop2 ist komplett leer: Das NN sollte die TE (Transporteinheit) dennoch fahren, da der Loop2 diese problemlos aufnehmen und puffern kann
b) Loop2 ist sehr voll: Das NN sollte die TE nicht fahren, sondern lieber eine für die anderen Senken bevorzugen.

Zu Ihrem Nachtrag:
Da stimme ich Ihnen auch zu, sehe aber aktuell noch keine Systemgröße. Darüber muss ich weiter nachdenken, würde dies aber erstmal als nachgelagertes Problem betrachten. Im Zweifel müssen die NN neu erlernt werden. Zunächst interessiert mich aber erstmal die praktikable Umsetzung überhaupt.

Ich habe ebenso weiter über den Reward nachgedacht und tue mich damit weiterhin sehr schwer.
Ziel des RL ist es den maximalen Durchsatz an allen Senken zu erreichen und dabei die Transportzeiten der TEs zu minimieren.
Hierfür einen Reward zu definieren erscheint mir schwierig. Es würde auf eine wohl komplexere Formel hinauslaufen, für die man in meinen Augen zu viel Wissen braucht.
Daher meine Frage an Sie:
Sollte man diese beiden Ziele als aktuelle Information als Eingänge anlegen (aktuelle Transportzeit TE, ggf. im Verhältnis zum Rest oder auch zu einer gewählten Maximalgröße, sowie der aktuelle Durchsatz an den Senken) und den Reward selber immer auf 0 setzen? So würden die Informationen auch in das NN einfließen, aber als unabhängige Größen. Man müsste keine Formel aufstellen, die man mühsam anpassen muss, bis sie Sinn ergibt.

Wäre so etwas denkbar?
netGuy
Posts: 21
Joined: Mon 11. Jan 2016, 09:05

Re: Optimierung des Straßenverkehrs durch Ampelschaltung

Post by netGuy »

Kreatief wrote: Sollte man diese beiden Ziele als aktuelle Information als Eingänge anlegen (aktuelle Transportzeit TE, ggf. im Verhältnis zum Rest oder auch zu einer gewählten Maximalgröße, sowie der aktuelle Durchsatz an den Senken) und den Reward selber immer auf 0 setzen? So würden die Informationen auch in das NN einfließen, aber als unabhängige Größen. Man müsste keine Formel aufstellen, die man mühsam anpassen muss, bis sie Sinn ergibt.

Wäre so etwas denkbar?
Hallo,
ich arbeite zusammen mit Kreatif am Materialflusssteuerungsprojekt.
Ich habe folgende Überlegung zum Reward:
Könnte man den nicht erst nach Ankunft der TT in der Ziel-Senke mit einbeziehen?
Also weg vom immediate Ansatz hin zum Time-Delayed-Reward.
Und z.B. die Ankunft mit 100 bewerten und die Transportzeit(TZ) als beeinflussenden Faktor betrachten:
Reward = (1/TZ)*100
Dann würde eine kürzere Transportzeit automatisch einen höheren Reward bedeuten?
[EDIT]:
Ich habe noch einmal mit Kreatif gesprochen und wir haben den Delayed-Reward folgendermaßen definiert:
- Zu Beginn werden alle Entscheidungen ohne Reward bewertet.
- Ermittlung des Rewards nach Ablauf einer festgelegten Zeitspanne von 1 Stunde und mittels folgendem Schema:
Image

Hierbei können wir dann mit den Parametern alpa und beta noch etwas "experimentieren". Wobei der Durchsatz immer stärker gewichtet wird als die Transportdauer.
Wir denken, dass dieser Ansatz eher zielführend ist. Die erforderlichen Daten können über Schnittstellen vom Live-System, bzw. dem Simulator abgegriffen werden.

Gruß
User avatar
TJetter
Posts: 341
Joined: Sat 13. Oct 2012, 12:04

Re: Optimierung des Straßenverkehrs durch Ampelschaltung

Post by TJetter »

netGuy wrote:- Zu Beginn werden alle Entscheidungen ohne Reward bewertet.
- Ermittlung des Rewards nach Ablauf einer festgelegten Zeitspanne von 1 Stunde und mittels folgendem Schema:
Bild
- Vermutlich kleiner Tippfehler: Der Term 'beta * tr' müsste wahrscheinlich 'beta * 1/ttr' lauten, oder?
- Die Idee, den Reward pro abgeliefertem TT und in Abhängigkeit von dessen Durchlaufzeit zu vergeben, finde ich sehr gut: Damit sind die Belohnungen genau für das vergeben, was erreicht werden soll.
- Den zweiten Term (Anzahl TT pro Stunde) könnte man damit wahrscheinlich also auch weglassen. Der Agent wird ohnehin darauf hinarbeiten, den Gesamt-Return über die Zeit hinweg zu maximieren, also möglichst häufig zu möglichst hohen Rewards zu gelangen. Das entspricht der Bedeutung nach bereits dem zweiten Term.
- Ich würde allerdings nicht für eine feste Anfangszeit die Rewards aussetzen (also auf 0 setzen), sondern von Beginn an konsequent mit jedem angekommenen TT einen Reward vergeben. Die relative Transportdauer würde ich dabei nicht über eine sich dynamisch verändernde durchschnittliche Transportdauer berechnen, sondern mit einer konstanten Transportdauer für die entsprechende Strecke als Nenner. Z.B. könnte man die theroretische minimal erreichbare Transportdauer für die zugehörige Q/S Kombination als Bezugsgröße verwenden. Hätte aus meiner Sicht zwei Vorteile:
-- Man ist ab dem ersten 'Zieleinlauf' in der Lage, einen verlässlichen Reward zu berechnen
-- Der Agent ist nicht in der Lage, einen hohen Reward dadurch zu erreichen, dass er die mittlere Durchlaufzeit in die Höhe treibt, sondern er muss konsequent daran arbeiten, die Durchlaufzeiten zu minimieren.

Wir gehen ja momentan von einem 'Schwarmansatz' aus, korrekt? Damit haben wir also pro 'Ampel' einen Agenten.
Bei mir tun sich da momentan vor allem noch die folgenden teilweise miteinander zusammenhängenden Fragen auf:
- Wie berechnet sich der Reward eines bestimmten Agenten? Oder gehen wir davon aus, dass jeder Agent den Auftrag hat, eine bestimmte Senke zu bedienen?
- Sollten alle Agenten einfach den selben Reward erhalten? Schließlich sollen sie ja auf ein maximales Gesamtergebnis hinarbeiten, macht also u.U. Sinn.
- Wie werden die Rewards der einzelnen Senken ggf. kombiniert zu einem Gesamtreward?
- Wie bestraft man 'verhungern'? Vielleicht muss für extreme 'Verhungerer' eine Bestrafung eingeführt werden, die mit deren Verweildauer im System wächst (also den Reward ins Negative treibt)
Thomas Jetter
netGuy
Posts: 21
Joined: Mon 11. Jan 2016, 09:05

Re: Optimierung des Straßenverkehrs durch Ampelschaltung

Post by netGuy »

TJetter wrote:Z.B. könnte man die theroretische minimal erreichbare Transportdauer für die zugehörige Q/S Kombination als Bezugsgröße verwenden.
Die Idee finde ich gut. Somit ergibt sich dann der folgende Reward:
Image
Die theor. min. errb. Trandsportdauer kann ja einfach auf analytischem Wege bestimmt werden.

Frage: Dann blieben alle Rewards immer auf die theor. minmal erreichb. Transportdauer bezogen?
TJetter wrote:Wie bestraft man 'verhungern'? Vielleicht muss für extreme 'Verhungerer' eine Bestrafung eingeführt werden, die mit deren Verweildauer im System wächst (also den Reward ins Negative treibt)
Hier müssten wir eventuell eine Bedingung, durch die Definition einer Obergrenze, in die Reward-Funktion integrieren? Eventuell wird es dann eher eine Stufenfunktion.
Image
TJetter wrote:Wir gehen ja momentan von einem 'Schwarmansatz' aus, korrekt? Damit haben wir also pro 'Ampel' einen Agenten.
Beim Schwarmansatz würde ich alle Agenten gleich belohnen/bestrafen. Da alle "gleichberechtigt" sein sollten. Könnte man den Gesamtreward als Summe der Teilrewards darstellen?

TJetter wrote: Wie berechnet sich der Reward eines bestimmten Agenten? Oder gehen wir davon aus, dass jeder Agent den Auftrag hat, eine bestimmte Senke zu bedienen?
Genau. Uns geht es um die Optimierung der Senken, da die Quellen ja durch die Geräteleistungen vorgegeben sind und nicht weiter optimiert werden können.
Konkret soll die Frage beantwortet werden: Kann ich in das nachfolgende MFE rein?

Somit ergeben sich m.E. die folgenden "Entscheidungspunkte":
Zur besseren Unterscheidung habe ich die Entscheidungspunkte der Quellen Q1-Q6 rot und die von Q7 grün markiert.
Image

So sollte auch sichergestellt sein, dass auch immer die "korrekten" TT an den Senken (S1-S7) ankommen - sprich die mit der maximalen Verweildauer für die aktuelle Entscheidung.
[EDIT]:
Somit könnte man als Eingangsneuronen:
- die Ampel (0;1)
- die maximale Verweildauer des am längsten im aktuellen Entscheidungsabschnitt befindlichen TT
- pro nachfolgendes MFE ein Neuron für die darin befindlichen TT und
- den aktuellen Reward
anlegen?
Der Ausgang wäre dann die Bewertung der Eingänge.
Beispiel für den Entscheidungspunkt an Q1:
Image

Die verstecken Schichten sind hier nur mal der Vollständigkeit halber mit abgebildet. Mit geht es hier lediglich um den grundsätzlichen Ansatz.
Die genaue Topologie lege ich dann danach noch fest.
User avatar
TJetter
Posts: 341
Joined: Sat 13. Oct 2012, 12:04

Re: Optimierung des Straßenverkehrs durch Ampelschaltung

Post by TJetter »

Im Hinblick auf die Netzstruktur zitiere ich am besten noch einmal aus dem ersten Post von Kreatif:
Re: "Richtige" Netzarchitektur für das Spiel KNIFFEL ?

Postby Admin » Thu 3. Nov 2011, 22:31
Also, ich beginne mal mit einer Wiederholung des Ablaufs, den ich in dem anderen RL-bezogenen Thread gepostet habe.
Einige kleine Präzisierungen bzgl. der Bezeichner habe ich vorgenommen. Außerdem habe ich noch den Parameter 'alpha' (=Schrittweite) eingeführt, er ist in der klassischen RL-Literatur vorgesehen. Man kann ihn auf 1 setzen, dann kommt wieder das raus, was ich vereinfachend im anderen Thread geschrieben hatte. Es macht aber bestimmt Sinn, diese Schrittweite alpha (als Konstante) in die Implementierung aufzunehmen, dann hat man noch einen weiteren Parameter zum Experimentieren.


- Der Agent legt im momentanen Zustand s für jede darin mögliche Aktion a den Input (momentaner Zustand s, Aktion a) an das Netz an an und holt sich aus dem Netz den Output Q(s, a).
- Mit einer gewissen Wahrscheinlichkeit führt der Agent die Aktion mit dem höchsten Output Qmax(s, a) aus ('Exploitation'). Mit der Restwahrscheinichkeit führt der Agent stattdessen eine zufällig gewählte Aktion aus ('Exploration'). Die ausgeführte Aktion a wird gemerkt (im Speicher gehalten).
- Der Agent erreicht dadurch einen neuen Zustand s' und erhält eine Belohnung r. Achtung: 'Belohnung' kann auch ein negativer Wert sein.
- Der Agent legt im neu erreichten Zustand s' wieder für jede mögliche Aktion den Input (s', a') an und holt sich aus dem Netz den Output Q(s', a').
- Der Wert der höchstwertigen Aktion Qmax(s', a') wird gemerkt:
- Ein neues Trainingsmuster wird abgelegt und zwar für Inputs = [s, a], Output = Q(s, a) + alpha * [r +gamma * Qmax(s', a') - Q(s, a)], wobei alpha und gamma zwischen 0 und 1 gewählt werden.
- Das neue Trainingsmuster wird dem bereits erarbeiteten Fundus von Trainingsmustern hinzugefügt und über alle Trainingsmuster ein Trainingsschritt durchgeführt (= 1x Teach Lesson)
- Ist die maximale Größe des Trainingssatzes erreicht (z.B. 50000 Muster), dann wird das älteste Muster vom Trainingssatz gelöscht.
- Das Ganze beginnt von vorne

Der Faktor 'gamma' führt dazu, dass der Agent nicht nur den erzielten momentanen Gewinn r erlernt, sondern auch noch den (geschätzten) nächsten zu erreichenden Gewinn Qmax(s', a') mit einbezieht. So pflanzt sich erzielter und zu erwartender zukünftiger Gewinn durch die Zustands-/Aktionspaare zurück fort. Ein höherer Wert von Gamma (Richtung 1) macht den Agenten 'weitsichtiger'. Ein niedriger Wert von Gamma führt dazu, dass der Agent mehr auf kurzfristige Gewinnerzielung trainiert wird.
Zu Beginn des Trainings sollte viel Exploration (also 'ausprobieren') stehen. Je schlauer der Agent wird, um so mehr kann man auf Exploitation (also Ausnutzung von erlerntem Wissen) umsatteln.

(Quelle: viewtopic.php?p=973#p973)
Das bedeutet, dass das NN folgendermaßen aussehen muss:
- Eingänge:
-- Den für eine nächste Entscheidung relevanten Zustand
-- Die zu beurteilende, einzelne mögliche Aktion
- Ausgang:
-- Geschätzte Wertigkeit der zu beurteilenden Aktion in diesem Zustand (also des Zustands-Aktionspaars A/S)

D.h., der Reward geht nicht als Eingang in das Netz. Vielmehr geht er anteilig in den Ziel-Ausgangswert eines zu erlernenden und dem Trainingsdatensatz hinzuzufügenden Patterns ein.

Der Zustand (= Teil der Eingänge des Netzes) sollte den momentanen Zustand der Ampel (rot/grün bzw. 1/0) mit beinhalten.

Eine Aktion kann aus meiner Sicht eine der drei folgenden sein:
- Ampelzustand umschalten
- Ampelzustand unverändert lassen
Damit würde es also zwei Ampelneuronen am Eingang geben, eines mit dem momentanen Zustand und eines für die zu bewertende Aktion

Die weiteren im NN-Entwurf benannten Inputs machen bestimmt als Teil des Zustands Sinn. Zusätzlich würde ich aber noch ein Neuron hinzufügen, dass angibt, wie lange die Ampel bereits im selben Zustand war.

Darf eine Umschaltung der Ampel eigentlich in jedem Fall stattfinden, oder sind evtl. Kollisionen zu befürchten? Im letzteren Fall ist es Sache des Environments (also der Simulation bzw. des Live-Systems), den Agenten nur diejenigen Aktionen wählen dürfen zu lassen, die auch wirklich möglich sind.
Thomas Jetter
netGuy
Posts: 21
Joined: Mon 11. Jan 2016, 09:05

Re: Optimierung des Straßenverkehrs durch Ampelschaltung

Post by netGuy »

TJetter wrote:Der Zustand (= Teil der Eingänge des Netzes) sollte den momentanen Zustand der Ampel (rot/grün bzw. 1/0) mit beinhalten.

Eine Aktion kann aus meiner Sicht eine der drei folgenden sein:
- Ampelzustand umschalten
- Ampelzustand unverändert lassen
Damit würde es also zwei Ampelneuronen am Eingang geben, eines mit dem momentanen Zustand und eines für die zu bewertende Aktion

Die weiteren im NN-Entwurf benannten Inputs machen bestimmt als Teil des Zustands Sinn. Zusätzlich würde ich aber noch ein Neuron hinzufügen, dass angibt, wie lange die Ampel bereits im selben Zustand war.
Check.
Hab das Netz für die Strecke Q1->S1 mal gemäß Ihren Anmerkungen für den ersten Entscheidungspunkt an Q1 angepasst.
Somit hätte ich die folgenden 8 Eingänge:
- Aktueller Ampelzustand
- Neuer Ampelzustand
- Dauer des aktuellen Ampelzustands
- Längste Verweildauer im aktuellen MFE (müsste hier ja einfach die Verweildauer der TT am E-Punk sein)
- Anzahl TT Loop 1
- Anzahl TT Loop 3
- Anzahl TT in Senke 1
- Anzahl TT im gesamten System für Senke 1
-----------------------------------------------------------------
Noch eine Frage zum Verständnis:
Der Reward fließt ja erst nach Ankunft der TT in der Zielsenke mit ein.
Solange kann ich ja das aktuelle Trainingspattern noch nicht bewerten, da wir ja ohne immediate Reward auskommen wollen. D.h. er "erbt" den Reward nach Ankunft der TT in der Senke und aktualisiert dann die betreffenden Trainingsmuster? (Sorry muss hier "laut denken", irgendwie hänge ich hier gerade ein wenig.)
User avatar
TJetter
Posts: 341
Joined: Sat 13. Oct 2012, 12:04

Re: Optimierung des Straßenverkehrs durch Ampelschaltung

Post by TJetter »

netGuy wrote:Noch eine Frage zum Verständnis:
Der Reward fließt ja erst nach Ankunft der TT in der Zielsenke mit ein.
Ein Reward wird nach jeder Aktion des Agenten (auch nach einer 'Ampel-bleibt-wie-sie-ist-Aktion) vergeben. Er wird allenfalls zu Anfang immer 0 sein, da zunächst keine TT an den Senken eintreffen. Auch 0 ist ein gültiger Reward.
Irgendwann im Verlauf ergeben sich dann höhere Rewards. Diese pflanzen sich im Action/State Raum 'nach hinten' fort und zwar dadurch, dass der Trainingswert zu einer Paarung S/A sich ja aus zwei Teilen zusammensetzt:
- Dem nach der Aktion erhaltenen Reward
- einem Anteil des geschätzten maximalen Aktions-Werts im eingetretenen Nachfolgezustand (Maximum über alle in diesem Zustand möglichen Aktionen)

Der Agent lernt also, Entscheidungen in bestimmten Zuständen auf- bzw. abzuwerten, abhängig von den Werten der durch diese Aktionen eingetretenen Nachfolgezustände.

Nach dem, was ich über RL gelernt habe, sollte der Agent dadurch prinzipiell lernen können, mit dem Zeitversatz des Rewards umzugehen. Ich würde aber, wie bereits einige Posts vorher gesagt, auch eine minimal zulässige Ampelwechselzeit einführen, so dass der Agent nach einem Ampelwechsel zunächst einmal keine Aktion durchführen kann, sondern die Aktion eine gewisse Zeit auf den Zustand einwirken kann. Das sollte den Effekt des Zeitversatzes etwas zähmen.
Außerdem steht der Agent in Konkurrenz zu anderen Agenten oder Steuerungsmechanismen, was das Lernen erheblich erschweren könnte. Das würde dann eher dafür sprechen, nur einen Agenten einzusetzen, der alle Ampeln steuert. Letztlich werden aber nur Experimente Klarheit schaffen, denke ich.
Thomas Jetter
Post Reply