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

Optimierung des Straßenverkehrs durch Ampelschaltung

Post by Kreatief »

Hallo zusammen,

ich denke seit einiger Zeit darüber nach, wie man den Straßenverkehr optimieren kann, in dem man die Ampeln durch ein KNN steuern lässt.

Dazu folgendes wunderbares, selbstgezeichnetes Bild:

Image


Fall 1)
Autobahn. Blockabfertigung mit Ampel

Fall 2)
Hauptstraße mit Seitenstraße als Einschleusung auf Hauptstraße. Ebenfalls Ampel.

Fall 3)
Same same. Hier nur mal die Komplexität. Die Entscheidung an der vorderen Ampel kann Auswirkungen auf die hinteren Entscheidungen haben, bzw. auf den Gesamtdurchsatz der durch diese Entscheidung beeinflusst wird. Das Auto mag vielleicht den Durchsatz an dem Punkt des Motorrads erhöhen, stopft aber die Straße so voll, dass es Rückstau gibt und es eine Kettenreaktion auslöst. Hier wäre es ggf. im Sinne der Blockabfertigung sinniger zu warten und die Straße etwas frei werden zu lassen.


Ich sehe das Problem ähnlich gestaltet wie die optimierte Strategiefindung bei Brettspielen. Daher habe ich auch den Thread über Kniffel (viewtopic.php?f=5&t=231) gerne gelesen. Leider sind da die Dateien nicht mehr verfügbar.

Ist mein folgender Ansatz korrekt?

Jede Ampel für sich besteht aus zwei potentiellen Aktionen: Rot oder Grün.
Als Eingangsneuronen benötige ich also die Aktion und den Zustand des Straßenverkehrs. Was genau ist dieser Zustand? Interessant ist doch nur der Füllgrad bestimmter Strecken und somit implizit die Anzahl der Fahrzeuge.
Als Ausgangsneuron gibt es nur eines mit der Wertigkeit der Aktion.
Ist es damit möglich eine optimale Ampelsteuerung zu erzeugen? Jede Entscheidung ist so minimal, kann aber Einfluss auf das Ergebnis am Ende haben. Was optimiert werden soll ist eben der Durchsatz pro Stunde. Durch eine falsche Entscheidung einer bestimmten Ampel, kann der Durchsatz nach vielen Minuten anfangen zu sinken.

Wie bringt man soetwas in ein RL System ein? Mir fehlts da noch ein bissl am gesamten Zusammenhang. Kann mich jemand auf den richtigen Pfad bringen? Wie sehr lässt es sich mit dem Kniffel-Beispiel vergleichen?


EDIT:

Ich habe mal das Beispiel 1 (Blockabfertigung) in einem KNN abgebildet:

Image

Eingangsneuron Ampel bekommt Werte [0;1] für Rot oder Grün
Eingangsneuron Füllgrad bekommt Werte [0;1;2;3;4;5;6;7] für die Anzahl an Fahrzeugen auf der Strecke nach der Ampel
Als Ausgangsneuron habe ich den Durchsatz angegeben.

Meine Trainingsdaten sehen wie folgt aus:

Ampel;Füllgrad;Durchsatz
0;5;5
1;5;3
0;6;3
1;6;3
0;2;2
1;2;3
0;4;4
1;4;5
1;1;2
0;0;0
0;3;3
0;7;3
1;7;3
0;8;3
1;8;3

Damit bekomme ich erstmal recht sinnvolle Ergebnisse.

Durchsatz bei Ampel 0 und Füllgrad 4: 4,20
Durchsatz bei Ampel 1 und Füllgrad 4: 4,62

Durchsatz bei Ampel 0 und Füllgrad 5: 4,6
Durchsatz bei Ampel 1 und Füllgrad 5: 2.99

Das sind natürlich zu wenige Daten und man könnte mit den Anzahl der hidden Neuronen spielen, aber ich denke die passen so erstmal. Zu viele sollten es nicht sein, sonst lernt das NN einfach nur auswendig.

Macht das ganze so Sinn? Kann man das nun auf komplexere Beispiele übertragen? Da muss ich noch mal darauf rumdenken. Idee sollte sein alle anderen Teilstrecken-Füllgrade als Eingangsneuronen mit anzulegen. Damit braucht man aber auch viel mehr Trainingsdaten.

Grundidee eines fertigen Algorithmus sollte sein: Lege alle Füllgrade der jetzigen Situation an und lasse das Netz zweimal durchlaufen. Einmal mit Ampel 0 und einmal mit 1. Der höchste Durchsatz gewinnt (mit Wahrscheinlichkeit um die 10% ein zufälliges Ergebnis zu wählen).

Was mir nur nicht ganz klar ist: Wie komme ich denn an die Trainingsdaten? Wie kann ich denn wissen was der Durchsatz pro Stunde ist, wenn davon sehr viele Entscheidungen abhängen und eben nicht nur die eine. Es ist ja nicht so, dass ich die eine Entscheidung treffe und dann extern die Fahrten simuliere und am Ende einen konkreten Durchsatz bekomme. Die Entscheidung Autos einzuschleusen oder die Blockabfertigung zu aktivieren oder deaktivieren treffe ich ja permanent.
Das muss doch das System irgendwie selber machen. Ich kann mir das nur so erklären, dass der am Ende erlangte Durchsatz gar nicht bestimmt werden kann sondern einfach nur als zusätzlicher Eingang anliegt und einfach den Durchsatz für genau den aktuellen Zustand angibt.
Wie lernt dann das System von seinen eigenen Entscheidungen die ja direkten Einfluss auf den Durchsatz haben? Wo existiert hier der Rückfluss?


EDIT 2:

Weiter gehts. Wieder was gelernt:

Trainingsdaten sollten selbst erstellt werden. Stichwort unsupervised learning (sofern korrekt in den Kontext gebracht).
Dazu folgende Formel: Inputs = [s, a], Output = Q(s, a) + alpha * [r +gamma * Qmax(s', a') - Q(s, a)]
Der entsprechende Wert wird als Wert für das Ausgangsneuron gesetzt und das Pattern abgelegt.

Dazu folgender Text:
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)
Jetzt ist nur die Frage was man als Belohnung r annimmt. Da bin ich noch nicht sicher. Der aktuelle Durchsatz? Aber der wird unter Umständen viel weiter hinten bestimmt und somit hätte die aktuelle Aktion keinen sofortingen Einfluss darauf. Könnte es dennoch funktionieren, da einfach alle Rewards versetzt sind? Das müsste doch dann negative Auswirkungen auf die Bewertung der jeweiligen Neuronen haben. Ideen?
User avatar
TJetter
Posts: 346
Joined: Sat 13. Oct 2012, 12:04

Re: Optimierung des Straßenverkehrs durch Ampelschaltung

Post by TJetter »

Klingt nach einem spannenden Thema, das es in sich hat...
Hier meine ersten Gedanken/Rückmeldungen/Ideen dazu:
Kreatief wrote:Ist mein folgender Ansatz korrekt?

Jede Ampel für sich besteht aus zwei potentiellen Aktionen: Rot oder Grün.
Als Eingangsneuronen benötige ich also die Aktion und den Zustand des Straßenverkehrs. Was genau ist dieser Zustand? Interessant ist doch nur der Füllgrad bestimmter Strecken und somit implizit die Anzahl der Fahrzeuge.
Als Ausgangsneuron gibt es nur eines mit der Wertigkeit der Aktion.
Ist es damit möglich eine optimale Ampelsteuerung zu erzeugen? Jede Entscheidung ist so minimal, kann aber Einfluss auf das Ergebnis am Ende haben. Was optimiert werden soll ist eben der Durchsatz pro Stunde. Durch eine falsche Entscheidung einer bestimmten Ampel, kann der Durchsatz nach vielen Minuten anfangen zu sinken.

Wie bringt man soetwas in ein RL System ein? Mir fehlts da noch ein bissl am gesamten Zusammenhang. Kann mich jemand auf den richtigen Pfad bringen? Wie sehr lässt es sich mit dem Kniffel-Beispiel vergleichen?
Am Anfang steht sicherlich eine erste Grundsatzüberlegung/-entscheidung:
Soll jede Ampel für sich durch einen eigenen 'Agenten' entspr. RL gesteuert werden, oder soll ein einziger Agent alle Ampeln des bestrachteten Verkehrs-Systems steuern? Ersteres ginge dann schon in die Richtung einer Schwarmintelligenz. Beides lohnt sich sicher, weiter zu verfolgen. Der Schwarmansatz hat natürlich den Reiz, dass er lokal, d.h., bei jeder einzelnen Ampel identisch ansetzt. Damit muss man das bestehende System nicht erweitern/anpassen wenn man eine weitere Ampel einführt. Der zweite Ansatz (nur ein Agent) könnte schneller zum Erfolg führen.
Da ich im Kopf zunächst von einem einzigen Agenten ausgegangen bin, versuche ich erst einmal, dieses Szenario hinzuschreiben. Vielleicht habe ich weiter unten ja noch Energie für den Schwarmansatz ;-)

Main gedanklicher Ansatz für einen einzelnen Agenten wäre folgender:
- Definition momentaner Zustand (= 'State' in RL Terminologie):
-- Rot/Grün Zustand aller im System befindlicher Ampeln
(auch solcher Ampeln, die vielleicht 'klassisch' angesteuert werden. Eine neue Ampelsteuerung wird man ja evtl. in bestehende, klassisch gesteuerte Verkehrsanlagen sukzessive eingliedern wollen).
-- Bisherige Dauer der jeweils aktiven Ampelphase für jede Ampel (wie lange ist sie schon rot bzw. grün?)
-- Inputs von allen realistischerweise zu erwartenden Sensoren im betrachteten Verkehrssystem. Hier wird man wahrscheinlich einfach anfangen, mit einer Induktionsschleife vor jeder Ampel o.ä. Das wäre also ein belegt/nicht belegt Zustand für jede Ampel. Was auch Sinn machen könnte, wäre eine mittlere Fahrzeugfrequenz über die letzte Minute o.ä. für jede Induktionssschleife. Solch einen Wert könnte man für jede Ampel (bzw. Induktionsschleife) ja problemlos errechnen.
Ein Füllgrad ist wahrscheinlich nicht ganz so einfach zu ermitteln, vielleicht über eine vorgeschaltete Kameraauswertung... Kann man ja mal annehmen, dass das gut funktionieren wird, google & Co machen's ja auch ;-)
-- Tageszeit? Wochentag? Feiertag? (bestimmt erst in einer fortgeschrittenen Version ;-) )

- Definition einer Aktion (= 'Action' in RL Terminologie)
-- Änderungskommando für eine oder mehrere Ampeln im System. D.h., ein boolsches Feld (true/false) für jede Ampel.
Das beinhaltet damit auch die folgende 'Sonderaktion', nämlich wenn alle Änderungsanfragen auf 'false' gesetzt werden:
-- Nichts verändern (d.h., alle Ampeln so lassen, wie sie sind). Das ist eine wichtige Aktion! Der Agent (der das NN nutzt, um seine Aktionsmöglichkeiten zu bewerten) wird zyklisch nach der nächsten durchzuführenden Aktion gefragt. Das wird recht häufig 'Nichts verändern' sein, das ist aber eben auch eine aktive Entscheidung in einem bestimmten Zustand, die zu Veränderungen des selbigen führen wird.

- Definition der Belohnung nach jeder Aktion (= 'Reward' in RL Terminologie). Nicht zu verwechseln mit dem langfristigen Gewinn (= 'Return')!
-- Da wird es knifflig: Was ist eine gute Belohnung bzw. Bestrafung (= negative Belohnung)? Dazu folgende Überlegungen:
-- Der Reward sollte erst bestimmt werden, nach dem die letzte Aktion 'wirken' konnte. Das definiert somit auch den 'Arbeitstakt' des RL-Systems:
1. Agent nach Aktion fragen und ausführen
2. Zielsystem (= 'Environment' in RL Terminologie = die Verkehrsanlage) eine 'vernünftige' Zeit lang laufen lassen (z.B. 10 s)
3. Neuen Zustand und Reward ermitteln, dem Agenten mitteilen und ihn dann nach der nächsten Aktion fragen. Aus dem Reward und mit Hilfe seiner bestehenden NN-Bewertungsfunktion ('Q-Function') bildet der Agent ein neues Trainingsmuster und fügt dieses seiner Lerndatenbank (MemBrain Lesson) hinzu. Die Zeit während die Simulation nach der letzten Aktion läuft kann der Agent im übrigen sehr gut zum Trainieren seines NN (Q-Function) nutzen.
-- Der Reward muss so definiert werden, dass er das zu erreichende Ziel repräsentiert. Doch was ist dieses Ziel? Klar ist: Durchsatz maximieren. Doch: Was ist denn der Durchsatz? Dazu müsste ja das Verkehrssystem einen einzigen EIngang und einen einzigen Ausgang haben. Kann man davon ausgehen? Und selbst wenn: Innerhalb des Systems kann es in Teilstraßen zu totalem Stau kommen und trotzdem kann der Durchsatz durch das Gesamtsystem maximal sein. Das ist aber bestimmt nicht das Ziel. Hier würde es bestimmt helfen, einen negativen Belohnungsanteil für jede Ampel beizusteuern, bei der der Verkehr lange staut. Je länger, um so mehr Bestrafung.
In der Definition des Rewards sehe ich den meisten Bedarf an 'Gehirnschmalz' ;-) Vielleicht sehe ich aber auch momentan hier den Wald vor lauter Bäumen nicht...
<EDIT>: Vielleicht hilft hier die Summe aller Füllgrade bzw. ein daraus abgeleiteter Wert?

Und dann wäre da noch....
- Das Environment!
-- Ein RL Projekt benötigt unumgänglich ein realistisches Zielsystem bzw. idealerweise eine gute Simulation dessen:
Der Agent muss permenent mit dem Environment interagieren, um aus Erfahrungen zu lernen. Dabei macht er am Anfang garantiert sehr lange alles falsch und 'probiert wild in der Gegend herum'. Abgesehen davon, dass man das echten Verkehrsteilnehmern nicht zumuten könnte, und es auch für unsereins nicht gerade einfach wäre, an eine Versuchsanlage zu kommen, würde es viel zu lange dauern: Nach jeder Aktion müsste der Agent 10 s lang auf Feedback aus dem System warten, nur um ein einziges Lernmuster zu erhalten. Gerade am Anfang, wenn man noch viel an dem RL-System optimieren muss, ist das äußerst mühsam. In einer Simulation kann man den Verkehrsfluss und somit den ganzen Lernvorgang dagegen beliebig beschleunigen.
Man müsste mal im Netz nach fertigen verfügbaren Verkehrssimulatoren schauen, die entsprechend flexibel und durch andere Software ansteuerbar sind. Keine Ahnung, ob es sowas gibt. Ansonsten wäre das natürlich ein wunderschönes Software-Projekt für sich alleine...

Hier übrigens ein Link zu einem wunderbaren Buch über RL, einmal als html-Version und einmal als pdf. Ich habe die Papierversion, ist aber nicht ganz billig:
https://webdocs.cs.ualberta.ca/~sutton/ ... -book.html
http://neuro.bstu.by/ai/RL-3.pdf
Gibt es leider nicht auf deutsch, soweit ich weiß.

So, jetzt geht der Post erst mal raus, ich versuche, den Schwarm-Ansatz später nachzuholen.
Thomas Jetter
Kreatief
Posts: 10
Joined: Tue 5. Jan 2016, 09:43

Re: Optimierung des Straßenverkehrs durch Ampelschaltung

Post by Kreatief »

Hallo Herr Jetter,

vielen Dank für die ausführliche Antwort.

Im Grunde sind meine Gedanken kongruent zu Ihren Ausführungen.
Beim Reward hänge ich am meisten. Dazu mal ein paar Gedanken:

Eine Zeit zu warten und dann den Reward zu ermitteln birgt doch folgendes Problem: Während dieser Zeit muss ich permament neue Entscheidungen treffen, also das System befragen. Angenommen ich lasse das Auto durch und von hinten kommen unendlich viele Autos nach. Nun kann ich ja nicht sagen, ich warte mal 10s und schaue wie das System reagiert, erst dann treffe ich eine neue Entscheidung an der Ampel für das wartende Auto.
Da haperts bei mir einfach.

Eine andere Idee bzw Frage:

Wäre es machbar die Belohnung zu definieren als den Durchsatz der aktuell am Ziel anliegt? Auch wenn man weiss, dass eine Entscheidung weit vorher keinen direkten Einfluss hat, da die Zeitkomponente mit reinspielt? Die Überlegung ist, dass der Durchsatz zu den Entscheidungen parallel verläuft, aber eben mit einem Offset. Würde das System damit umgehen können?
Angenommen eine Entscheidung ist eigentlich sehr gut, aber der aktuelle Durchsatz (der durch die Entscheidung nicht beeinflusst wurde) ist schlecht. Damit würde das Neuron eine schlechte Bewertung bekommen. Eine spätere Entscheidung ist eigentlich schlecht, aber der Durchsatz ist nun gut (da nun der Einfluss der ersten Entscheidung wirkt). Das System würde das Neuron gut bewerten. Das klingt erstmal falsch. Aber kann das System auf Lange Sicht damit umgehen? Würde es nicht anfangs nur stark oszillieren, sich dann aber fangen?


Zu dem Problem der Ermittlung der Trainingsdaten aufgrund der Zeit:
Meine Idee wäre es, dass ich mit sehr grober Simulation (alle Autos fahren immer genau 50km/h, alle Teilstrecken sind genau 1km lang) das System vorlernen lasse und es dann vorgelernt in einem Livesystem anwende.
Damit wären die Entscheidungen nicht mehr ganz so schlecht und es geht eher um Optimierungen (Exploitation).
Zu kurz gedacht?

Die Idee der Schwarmintelligenz gefällt mir, da ich an das Problem der Anpassung nicht gedacht habe. Es wäre schon optimal, wenn eine Anpassung des Straßennetzes nicht zur Folge hätte, dass alles von neuem gelernt werden muss. Wobei die Frage ist, ob das nicht dennoch gemacht werden muss. Da jede neu hinzugefügte Teilstrecke als Eingang jedes Netztes anliegen muss, egal wo die Ampel ist, sofern die Teilstrecke in irgendeiner Form Einfluss auf den Fluss der Ampel haben kann.
User avatar
TJetter
Posts: 346
Joined: Sat 13. Oct 2012, 12:04

Re: Optimierung des Straßenverkehrs durch Ampelschaltung

Post by TJetter »

Kreatief wrote:Eine Zeit zu warten und dann den Reward zu ermitteln birgt doch folgendes Problem: Während dieser Zeit muss ich permament neue Entscheidungen treffen, also das System befragen. Angenommen ich lasse das Auto durch und von hinten kommen unendlich viele Autos nach. Nun kann ich ja nicht sagen, ich warte mal 10s und schaue wie das System reagiert, erst dann treffe ich eine neue Entscheidung an der Ampel für das wartende Auto.
Sie haben Recht, evtl. muss das System schneller auf Zustandsänderungen (wie etwa herannahende Autos) reagieren können, um effektiv zu sein. Deshalb sollte das Aktionsintervall kleiner sein, vielleicht 1 s. Dann würde ich aber im 'Environment' eine Regel einführen, dass der Zustand einer Ampel eine Mindestzeit lang konstant bleiben muss, bevor eine entsprechende Änderungsaktion erlaubt ist. Der Agent muss vom Environment ohnehin vor jeder Aktionsentscheidung mitgeteilt bekommen, unter welchen Aktionen er überhaupt wählen kann - es sind ja nicht zwangsläufig immer alle erlaubt. Da fällt mir ein: Das Environment darf einem Agenten natürlich ohnehin nicht erlauben, eine Ampel auf grün zu stellen, wenn die senkrecht dazu verlaufende Strecke gerade grün hat.
Wenn dann ohnehin keine Aktion erlaubt ist, wird der Agent in einem bestimmten Update-Zyklus erst gar nicht befragt. Aus seiner Sicht ist dieser Zwischenzustand dann nicht existent, das ist vollkommen i.O. so.
Kreatief wrote:Wäre es machbar die Belohnung zu definieren als den Durchsatz der aktuell am Ziel anliegt? Auch wenn man weiss, dass eine Entscheidung weit vorher keinen direkten Einfluss hat, da die Zeitkomponente mit reinspielt? Die Überlegung ist, dass der Durchsatz zu den Entscheidungen parallel verläuft, aber eben mit einem Offset. Würde das System damit umgehen können?
Angenommen eine Entscheidung ist eigentlich sehr gut, aber der aktuelle Durchsatz (der durch die Entscheidung nicht beeinflusst wurde) ist schlecht. Damit würde das Neuron eine schlechte Bewertung bekommen. Eine spätere Entscheidung ist eigentlich schlecht, aber der Durchsatz ist nun gut (da nun der Einfluss der ersten Entscheidung wirkt). Das System würde das Neuron gut bewerten. Das klingt erstmal falsch. Aber kann das System auf Lange Sicht damit umgehen? Würde es nicht anfangs nur stark oszillieren, sich dann aber fangen?
Das ist tatsächlich DAS Kernfeature von RL: Die Belohnung sollte immer nur das eigentliche Endziel widerspiegeln und oft entsteht ein akkumulierter Return erst im Laufe einer langen oder auch endlosen Kette aus Zuständen und Aktionen mit Ihren einzelnen Rewards. Ich bin nicht der Experte in RL aber, es wurde entwickelt um gerade damit umzugehen: Der Agent lernt über viele Iterationen hinweg, Aktionen in bestimmten Zuständen zu bewerten, anhand langfristig zu erwartendem Gesamt-Return.

Vielmehr beschäftigt mich die Frage: Was ist 'das Ziel'? Siehe meine Anmerkungen zur Beschaffenheit des Verkehrssystems und seiner Teilstrecken. Deshalb sehe ich die Vermeidung von Staus und langen Wartezeiten auf allen Teilstrecken als ebenso wichtig. Vielleicht sollte man sich sogar darauf verlassen, dass man die mittlere Wartezeit aller Autos minimiert oder deren Durchlaufzeit-Mittel durch die Verlehrsanlage minimiert? Nehmen wir mal an, jedes Kfz bekommt bei der Einfahrt in das Verkehrssystem einen Zeistempel aufgeprägt und bei der Ausfahrt (oder bei Zielerreichung innerhalb des Systems - Parken) wird die benötigte Fahrzeit ermittelt. (nicht ganz ausgereift die Idee, ich weiß, aber irgendwas in dieser Richting eben ;-) ).

Eine Anmerkung noch: Bei RL werden keine einzelnen Neuronen bewertet. Es werden viel mehr Aktionen in bestimmten Zuständen bewertet. Wenn man NN zur Abbildung der Q-Function verwendet, dann ist eine RL-Aktion dabei im Regelfall nicht einem Neuron zugeordnet, sondern wird durch ein Tupel aus Eingangsneuronen repräsentiert. Z.B. ein Neuron für jede der möglichen 'Ampelwechsel-Befehle' einer bestimmten Aktion.
TJetter wrote:Zu dem Problem der Ermittlung der Trainingsdaten aufgrund der Zeit:
Meine Idee wäre es, dass ich mit sehr grober Simulation (alle Autos fahren immer genau 50km/h, alle Teilstrecken sind genau 1km lang) das System vorlernen lasse und es dann vorgelernt in einem Livesystem anwende.
Damit wären die Entscheidungen nicht mehr ganz so schlecht und es geht eher um Optimierungen (Exploitation).
Zu kurz gedacht?
RL ist ein kontinuierlicher Lern- und Steuerprozess. Das befähigt ihn, sich kontinuierlich an eine sich verändernde Umgebung (Environment) anzupassen. Das bedingt aber auch, dass im Realbetrieb die gleichen Informationen vorliegen und die gleichen Aktionen möglich sind wie in der Simulation. Deshalb muss die Simulation zumindest von den Schnittstellen her identisch zur Realsituation sein. Natürlich ist es möglich, die Simulation intern einfacher zu halten als die Realität (das wird immer der Fall sein). Aber so etwas wie Anfahrzeiten und -verzögerungen von Fahrzeugen wegzulassen sowie auch die zufällige Streuung von Fahrzeug-Verhaltensparametern nicht einzubeziehen, halte ich für wenig aussichtsreich.
Aber auch hier gilt: Ich bin kein Experte für RL und letztlich entscheiden Machbarkeit und Experiment.
Kreatief wrote:Die Idee der Schwarmintelligenz gefällt mir, da ich an das Problem der Anpassung nicht gedacht habe. Es wäre schon optimal, wenn eine Anpassung des Straßennetzes nicht zur Folge hätte, dass alles von neuem gelernt werden muss. Wobei die Frage ist, ob das nicht dennoch gemacht werden muss. Da jede neu hinzugefügte Teilstrecke als Eingang jedes Netztes anliegen muss, egal wo die Ampel ist, sofern die Teilstrecke in irgendeiner Form Einfluss auf den Fluss der Ampel haben kann.
Da haben Sie prinzipiell Recht, aber vielleicht stolpern wir ja noch über eine gute Idee, wie ein einheitlicher, lokaler Zustand sinnvoll für jede Ampel aussehen könnte? Der einzelne Agent würde dadurch erheblich einfacher und performanter und es wäre näher an der Realität, als jede Ampel mit unglaublich vielen Sensor-Inputs von anderen Ampelstellen zu versehen. Ich für meinen Teil muss darüber erst mal etwas weiter nachdenken, es reizt mich jedenfalls sehr, hier eine Lösung zu finden. Einfacher ist i.d.R. immer besser.

Viele Grüße
Thomas Jetter
Kreatief
Posts: 10
Joined: Tue 5. Jan 2016, 09:43

Re: Optimierung des Straßenverkehrs durch Ampelschaltung

Post by Kreatief »

Um das doch sehr komplexe Thema zu vereinfachen würde ich gerne folgende Annahmen festlegen:

1. Es gibt in unserem Straßennetz eine definierte Anzahl von Quellen für Autos
2. Es gibt in unserem Straßennetz eine definierte Anzahl von Senken für Autos
3. Der Durchsatz an den Quellen garantiert, dass ein Zieldurchsatz an den Senken erreicht werden kann.
4. Der Durchsatz oder auch Stau auf Teilstrecken ist für die Bewertung des Zieles zu ignorieren.
5. Es sollen keine Autos "verhungern".
6. Ziel des RL Algorithmus ist es, den Durchsatz an allen Senken zu optimieren

Dies entspricht mehr einem klassischen Materialfluss. Eventuell macht es Sinn sich hierauf zu beschränken und ggf anschließend auf das Straßennetz zu adaptieren.

ad 4) Für das Ziel (siehe Punkt 6) ist es an sich unerheblich wie die Situation im Netz aussieht (solange dadurch nicht der Zieldurchsatz verschlechtert wird). Jedoch sollten keine Autos verhungern (Punkt 5), sprich, nie an gewissen Ampeln eingeschleust werden. Das passt auch zu Ihrer Anmerkung ggf. eine Start- und Endzeit der Autos mit einzubeziehen. Das dürfte wesentlich sinniger sein, als der pure Durchsatz.


Dazu ein Beispielszenario zur Veranschaulichung:

Image


Q = Quelle
S = Senke
Loop = Kreislauf
Die Zahlenwerte entsprechen den Geräteleistungen (Quellen und Loops) (Transportträger pro Stunde), sowie den zu erwartenden und zu optimierenden Durchätzen (Senken) (Transportträger pro Stunde).

Vielleicht können wir uns an dem Beispiel in den folgenden Diskussionen durch hangeln.

Wie man sieht, werden die einzelnen Komponenten (Loop, Senken) mit mehr Transportträgern versorgt, als notwendig. Die Geräteleistung setze ich als gegeben voraus. Im Livebetrieb liegt aber nicht immer die maximale Menge an (Varianz).
Ziel ist es nicht, die Loops auf maximale Leistung zu bringen (sonst würde ich ggf. immer Q7 fahren lassen, damit möglichst viel im Loop ankommt), sondern die Senken S1-S6 mit maximaler Leistung zu versorgen. Daher macht es nicht Sinn Q7 extrem zu bevorzugen, auch wenn da viele Transportträger anliegen, weil an den Senken S5 und S6, wo diese Quelle hingefahren werden soll, nur 60 pro Stunde aufnehmen müssen, aber 100 anliegen.
User avatar
TJetter
Posts: 346
Joined: Sat 13. Oct 2012, 12:04

Re: Optimierung des Straßenverkehrs durch Ampelschaltung

Post by TJetter »

Kreatief wrote:Vielleicht können wir uns an dem Beispiel in den folgenden Diskussionen durch hangeln.
In Ordnung. Allerdings ersehe ich aus dem Bild noch nicht genug:
1.) Wo sind 'Ampeln'?
2.) Welche Zustandswerte sind permanent verfügbar ('Sensorik')?
3.) Wie bestimmt sich die Zielroute für einzelne Transportträger? Sind diese autonom bzw. wodurch werden sie gesteuert? Ist das relevant?
Thomas Jetter
Kreatief
Posts: 10
Joined: Tue 5. Jan 2016, 09:43

Re: Optimierung des Straßenverkehrs durch Ampelschaltung

Post by Kreatief »

1. Ampeln sind hier alle Einschleuspunkte in andere Materialflusskomponenten (Loop, Zielstrecken):

Image


2. Wir wissen zu jeder Zeit in welcher Materialflusskomponente sich welcher Transportträger befindet (Loop, Zielstrecke, Einführstrecke etc.)

3. Das habe ich vergessen zu erwähnen. Quellen Q1-Q6 bedienen Senken S1-S4. Quelle Q7 bedient S5-S6.
Welcher Transportträger zu welchem Ziel fährt ist von außen vorgegeben und müsste somit als Eingangsinformation des Netzes anliegen
User avatar
TJetter
Posts: 346
Joined: Sat 13. Oct 2012, 12:04

Re: Optimierung des Straßenverkehrs durch Ampelschaltung

Post by TJetter »

Kreatief wrote:2. Wir wissen zu jeder Zeit in welcher Materialflusskomponente sich welcher Transportträger befindet (Loop, Zielstrecke, Einführstrecke etc.)

3. Das habe ich vergessen zu erwähnen. Quellen Q1-Q6 bedienen Senken S1-S4. Quelle Q7 bedient S5-S6.
Welcher Transportträger zu welchem Ziel fährt ist von außen vorgegeben und müsste somit als Eingangsinformation des Netzes anliegen
Ich muss an dieser Stelle nochmals nachhaken:
Streben die Transportträger ihr Ziel selbsttätig an (sofern sie freie Fahrt erhalten) oder ist es Sache der Ampeln (= eher Weichen?), die TT zum Ziel zu lenken?

Mit welchen Hilfsmitteln soll denn die Simulation und die RL-Implementierung umgesetzt werden? Wenn MemBrain für das NN hinter dem RL-Algorithmus (Q-Function) zum Zuge kommen soll, dann muss dafür zumindest Windows herhalten. Anbieten würde sich also z.B. sehr gut C# für die Umsetzung des RL.
Soll/muss die Simulation 'from Scratch' erstellt werden oder gibt es da evtl. einen fertigen Simulator? Bei meinen ersten Recherchen bin ich im Freeware-Bereich nur auf 'OpenSim' gestoßen:
http://opensimulator.org/wiki/Main_Page
Ob dieser Simulator überhaupt geeignet wäre, weiß ich nicht. Er ist eher auf virtuelle Welten a la 'Second Life' und entsprechende Viewer ausgelegt. Ob er sich dazu eignet, Materialflussstraßen und zugehörige 'Ampeln' o.ä. zu simulieren, weiß ich nicht. Auch ist mir noch nicht ersichtlich, in wie weit es die Schnittstellen des Simulators erlauben, eine definierte Zeit in die Simulation einzubringen, inkl. Pause-Funktion.
Thomas Jetter
Kreatief
Posts: 10
Joined: Tue 5. Jan 2016, 09:43

Re: Optimierung des Straßenverkehrs durch Ampelschaltung

Post by Kreatief »

Die Ampeln steuern nicht das Routing. Das wird von außen vorgegeben. Die Ampeln steuern nur, ob ein Transportträger fahren darf oder nicht und nicht wohin. Wobei natürlich das Ziel einen Einfluss auf das NN haben, da ja die Ziele optimal ausgelastet werden sollen.

Einen Simulator würde ich selbst erstellen und in C++ entwickeln und Membrain per dll einbinden.
User avatar
TJetter
Posts: 346
Joined: Sat 13. Oct 2012, 12:04

Re: Optimierung des Straßenverkehrs durch Ampelschaltung

Post by TJetter »

Verstanden.

Dann sollten wir eine Möglichkeit finden, die Zielsetzungen der TT als möglichst einfachen, komprimierten Input ans Netz zu bringen, es macht sicherlich keinen Sinn, dass der Agent über jeden einzelnen TT Bescheid weiß. Vielleicht lässt sich ja eine mengenmäßige Aussage treffen über die momentan anliegenden Transportanfragen zwischen verschiedenen Quellen und zugehörigen Senken.

Wie soll es denn weitergehen, gibt es bestimmte konkrete Fragen, die wir hier erst einmal noch klären sollten?

Viele Grüße
Thomas Jetter
Post Reply