Hallo. Ich möchte eine Modellautoanlage bauen, bei der Autos vorausschauend fahren können. Das System gibt es bereits (Miniaturwunderland Hamburg, Faller Car-System, OpenCarSystem), aber ich möchte es ein wenig verbessern und verändern. Außerdem reizt mich das Entwickeln. Die Autos fahren nur vorwärts auf einer Linie (Fahrdraht - lenkt die Autos). Dabei überqueren sie Magnetkontakte, die messen können, ob ein Auto über sie drüberfuhr, oder nicht. Betrachten wir das ganze nun aus Informatiker-Sicht, kann man die Kontakte als Knoten und die Verbindungslinien (Fahrdraht) als Kanten bezeichnen. Bisher lotse ich (in der Simulation) die Autos mittels Dijkstra-Algorithmus zum Ziel. Das ist theoretisch möglich, aber in der Praxis stoße ich auf folgende Probleme: - Wenn jedes Auto immer nur den kürzesten Weg zum Ziel nimmt, bildet sich irgendwann ein Stau. - Es ist unrealistisch, dass große Autos (LKW) durch kleine Straßen fahren. Es mag schon mal vorkommen, aber nicht oft. - In der Realität fährt man, trotz Navi-Ansage, nicht über die Straßen, auf denen viel Verkehr ist (siehe Punkt 1). Welcher Algorithmus ist für dieses Vorhaben geeignet? Wie kann ich den Dijkstra-Algorithmus modifizieren, sodass er für das Vorhaben geeignet ist? Vielen Dank für jede hilfreiche Antwort. Euer Sam
:
Verschoben durch Moderator
Projekt M. schrieb: > Wenn jedes Auto immer nur den kürzesten Weg zum Ziel nimmt, bildet sich > irgendwann ein Stau. Und ? Realität. Projekt M. schrieb: > Es ist unrealistisch, dass große Autos (LKW) durch kleine Straßen > fahren. Wenn du weisst, welches Fahrzeug du steuerst, kannst du Strassen ausschliessen. Projekt M. schrieb: > In der Realität fährt man, trotz Navi-Ansage, nicht über die Straßen, > auf denen viel Verkehr ist Wie ungeschickt. Das Navi weiss sogar, wie viel Verzögerung der Stau bringt. Schickt es einen dort lang, ist das trotzdem der schnellste Weg.
Michael B. schrieb: > Projekt M. schrieb: >> Wenn jedes Auto immer nur den kürzesten Weg zum Ziel nimmt, bildet sich >> irgendwann ein Stau. > > Und ? Realität. In der Realität gibt es zigtausende Ausweichstrecken. Auf einer kleinen Modellanlage, nicht. So verstopft irgendwann alles. Das will ich vermeiden. > Projekt M. schrieb: >> Es ist unrealistisch, dass große Autos (LKW) durch kleine Straßen >> fahren. > > Wenn du weisst, welches Fahrzeug du steuerst, kannst du Strassen > ausschliessen. Wie meinst du das? Ich steuere alle Fahrzeuge auf einmal. Das soll ja automatisch funktionieren, deshalb der Algorithmus. > Projekt M. schrieb: >> In der Realität fährt man, trotz Navi-Ansage, nicht über die Straßen, >> auf denen viel Verkehr ist > > Wie ungeschickt. Das Navi weiss sogar, wie viel Verzögerung der Stau > bringt. Schickt es einen dort lang, ist das trotzdem der schnellste Weg. Korrekt. Aber wie macht es das? Das Navi bindet aktuelle Verkehrszahlen in seine Routenplanung mit ein, vermengt das ggf. mit Erfahrungswerten und bastelt daraus die optimale Route. Und das, obwohl sich sekündlich die Verkehrsdichte ändert. Das müsste mein gesuchter Algorithmus auch können. Aber wie?
Vorausschauendes Fahren waere mit Mitfahrer. D.h. immer die naechste Hellsehperson mitnehmen. Damit waere auch das Problem geloest, dass im Auto durchschnittlich weniger als 2 Personen sitzen. ;)
Projekt M. schrieb: > Das müsste mein gesuchter Algorithmus auch können. Das Navi trackt einfach die GPS Daten anderer nach Navi fahrenden Autos und weiss daher die mittlere Geschwindigkeit einer Strecke, egal aus welchem Hrund, und berechnet damit die Route, natürlich nicht im Voraus sondern mit einiger (halbstündlich?) Verzögerung. Du kannst sogar predicten wann welches Auto wo sein wird, bist also besser dran als ein Navi. Und wenn du den Autotyp kennst von jedem gesteuerten Objekt, kannst du Einschränkungen wie Maximalgeschwindigkeit oder Straßenbreite mitfinrechnen. Realistischer wird das nicht wenn man optimal steuert.
Projekt M. schrieb: > Ich steuere alle Fahrzeuge auf einmal. Hört sich irgendwie nach einer blöden Idee an. Du sendest also einen Steuerbefehl immer an alle? Sinnvoller ist es doch jedes Fahrzeug für sich zu Steuern. Da mögen überall die selben Softwareroutinen zur Anwendung kommen, aber die Daten mit denen diese "Gefüttert" werden sind für jedes Fahrzeug individuell. Vielleicht solltest du dir erstmal Gedanken machen, wie du dein Problem in kleinere Teilprobleme zerlegst und diese dann eins nach dem anderen lösen.
Michael B. schrieb: > Projekt M. schrieb: >> Das müsste mein gesuchter Algorithmus auch können. > > Das Navi trackt einfach die GPS Daten anderer nach Navi fahrenden Autos > und weiss daher die mittlere Geschwindigkeit einer Strecke, egal aus > welchem Grund, und berechnet damit die Route, natürlich nicht im Voraus > sondern mit einiger (halbstündlich?) Verzögerung. Wo welches Auto ist, weiß ich auch :) > Du kannst sogar predicten wann welches Auto wo sein wird, bist also > besser dran als ein Navi. Stimmt. Aber jedes Auto wird seine Route ändern, wenn es merkt, dass die Straße, durch die es fahren will, zu voll ist. Somit kann ich das nicht immer sofort vorhersagen. Wann muss ich also diese Überprüfung nach der Verkehrsdichte der nächsten Straße machen? > Und wenn du den Autotyp kennst von jedem gesteuerten Objekt, kannst du > Einschränkungen wie Maximalgeschwindigkeit oder Straßenbreite > miteinrechnen. Gibt es dafür eine Formel oder ein prinzipielles Vorgehen? > Realistischer wird das nicht wenn man optimal steuert. Ok. Dann lass uns die Realität gegen Funktionstüchtigkeit eintauschen :)
Forum: Projekte & Code Hier könnt ihr Projekte, Schaltungen oder Codeschnipsel vorstellen. Projekte bitte nur mit Code oder Schaltplan posten (falls ihr nur Fotos vorstellen möchtet, bitte in "Zeigt her eure Kunstwerke"). Bitte hier keine Fragen posten.
Gib doch mal ein paar Infos dazu. Wird das alles zentralgesteuert? Landen alle Infos bei der Zentrale, werden die Infos an die Autos weitergeleitet die dann selbst entscheiden oder gibt die Zentrale alles vor? Durch Kontaktpunkte im Boden kann man Anhäufungen von Autos erkennen. Man könnte jedem Auto eine kleine Karte spendieren z.B. ein Feld 16x16 und dort die Anzahl der Autos übermitteln. So kann ein Auto erstmal versuchen Punkte mit einer hohen Fahrzeugdichte zu umfahren oder ggf. die Geschwindigkeit zu reduzieren wenn es doch da durch möchte.
Thomas schrieb: > Gib doch mal ein paar Infos dazu. > > Wird das alles zentralgesteuert? Landen alle Infos bei der Zentrale, > werden die Infos an die Autos weitergeleitet die dann selbst entscheiden > oder gibt die Zentrale alles vor? Ja. Alles wird zentral gesteuert. Der Computer schaltet Weichen/Abzweigungen und lenkt so die Autos. Die Autos an sich sind „machtlos“. Sie können nur ihre Geschwindigkeit ändern und ihre Lichter an und aus schalten. Dadurch, dass sie eine Art „Lenker“ an der Vorderachse befestigt haben, folgen sie dem Fahrdraht. Ähnlich wie ein Zug der Schiene. Die Lichter sind quasi nur „Kosmetik“ und werden erst später relevant. > Durch Kontaktpunkte im Boden kann man Anhäufungen von Autos erkennen. > > Man könnte jedem Auto eine kleine Karte spendieren z.B. ein Feld 16x16 > und dort die Anzahl der Autos übermitteln. So kann ein Auto erstmal > versuchen Punkte mit einer hohen Fahrzeugdichte zu umfahren oder ggf. > die Geschwindigkeit zu reduzieren wenn es doch da durch möchte. Ich unterteile (gedanklich) die Straßen in Abschnitte. Jeder Abschnitt enthält einen Kontaktpunkt bzw. Magnetsensor. Sobald ein Fahrzeug einen Sensor ausgelöst hat, befindet es sich auf dessen Abschnitt. Auf jedem Abschnitt kann maximal ein Fahrzeug fahren/halten. Wäre die von dir vorgeschlagene Karte demzufolge ein Abschnitt? Oder eine Folge von Abschnitten, also eine Straße?
Du kannst deine Fahrzeuge in Klassen aufteilen und die Kanten des Graphen entsprechend gewichten, d.h. für einen LKW ist eine Strecke "teurer/länger" als für einen PKW. Ebenso, wenn Teilstrecken schon besetzt sind. Sollte dann zu entsprechenden Ausweichstrecken kommen.
Es ist ein Unterschied, ob man nur Befehle ausgibt oder auch die Rückmeldungen der Fahrzeuge verarbeiten kann wie bei G*. Beispiel https://www.heise.de/news/Virtueller-Stau-auf-Google-Maps-als-Kunstwerk-4651651.html
Projekt M. schrieb: > Auf jedem Abschnitt kann maximal ein Fahrzeug fahren/halten. Irgendwie erinnert dieses Konzept an Blockabschnitte im Bahnbetrieb, wo aber dazwischen auch noch ein Abschnitt frei bleiben muß; geht bei Bahnen halt nicht anders, weil die eben - im Gegensatz zu KFZ - nicht auf Sicht fahren (können). Egal ob PKW oder LKW, der ja so 3-4 mal so lang ist? Ein Abschnitt muß ja dann ausreichend lang für 'nen LKW plus den Sicherheitsabstand zum Vorder-KFZ sein; dieser ist aber im wesentlichen von der aktuellen Geschwindigkeit abhängig, was direkt zur nächsten Frage führt: Egal ob der Verkehr im Schritttempo dahinkriecht oder mit 50 km/h fließt (was den 10-fachen Sicherheitsabstand erfordert, etwa die Länge eines LKW)? Also ich kann mir irgendwie schwer vorstellen, wie man unter diesen Bedingungen die Autos so steuern sollte, daß das Ergebnis zumindest Ähnlichkeiten mit einem normalen innerstädtischen Verkehrsfluß hat? Hast Du möglicherweise auch noch Ampeln auf Deiner Anlage? Weil ein Ampelhalt von 2 PKW hintereinander trotzdem dabei trotzdem zwei Abschnitte benötigen würde, also eine Länge auf der in der Realität beim Ampelhalt rund 10 PKW passen würden. Projekt M. schrieb: > In der Realität fährt man, trotz Navi-Ansage, > nicht über die Straßen, auf denen viel Verkehr ist Sorry, da muß ich jetzt mal nachfragen: Du hast schon selbstfahrend eine relevante Kilometerleistung (also nicht nur alle paar Jahre mal 'n paar km) im Großstadtverkehr zurückgelegt? Idealerweise zumindest teilweise auch (noch) selbst navigiert? Denn falls ja, solltest Du eigentlich Wissen, daß man innerstädtisch bei etwas längere Strecken fast immer den größten Teil der Strecke Hauptstraßen benutzt, obwohl der Verkehr dort deutlich dichter ist als in den parallel verlaufenden Gassen und auf diese Weise i.d.R. auch schneller ans Ziel kommt.
Projekt M. schrieb: > Welcher Algorithmus ist für dieses Vorhaben geeignet? Wie kann ich den > Dijkstra-Algorithmus modifizieren, sodass er für das Vorhaben geeignet > ist? Dijkstra (oder A*) kannst Du schon nehmen. Wenn Du nicht den kürzesten, sondern den schnellsten Weg suchst, must Du die Kanten mit der Fahrzeit und nicht der Länge bewerten. Wenn Du A* nehmen möchtest, könntest Du dann die langsamste Geschwindigkeit auf der Luftlinie zum Ziel als Heuristik nehmen.
Michael P. schrieb: > Du kannst deine Fahrzeuge in Klassen aufteilen und die Kanten des > Graphen entsprechend gewichten, d.h. für einen LKW ist eine Strecke > "teurer/länger" als für einen PKW. Ebenso, wenn Teilstrecken schon > besetzt sind. Sollte dann zu entsprechenden Ausweichstrecken kommen. Ich habe mir folgendes überlegt: Die Kantenlänge (auf den Graphen bezogen) ist nicht die tatsächliche Länge des Abschnitts. Ich will ja nicht den kürzesten, sondern den schnellsten Weg herausfinden. Stattdessen ist die Kantenlänge die Zeit t, die ein Auto zum durchfahren des Abschnitts benötigt. t = s / v s ist dabei die Länge des Abschnitts (fix) v ist dabei die Geschwindigkeit, mit der das Auto durch den Abschnitt fahren kann (variabel) Befindet sich kein Auto auf dem Abschnitt danach, ist v gleich v_max, also die maximale Geschwindigkeit, die das Auto fahren kann (innerorts 50 km/h). Befindet sich ein Auto auf dem Abschnitt danach, ist v entweder gleich der Geschwindigkeit des Fahrzeugs danach, falls dieses Fahrzeug fährt, oder gleich v_min, also der minimalsten Geschwindigkeit, die ein Auto überhaupt fahren kann. Ist das Prinzip zielführend? Michi S. schrieb: > Hast Du möglicherweise auch noch Ampeln auf Deiner Anlage? > Weil ein Ampelhalt von 2 PKW hintereinander trotzdem dabei trotzdem zwei > Abschnitte benötigen würde, also eine Länge auf der in der Realität beim > Ampelhalt rund 10 PKW passen würden. Außerorts wird die Abstandslänge etwas größer, als innerorts. Ein LKW ist ca. 3 mal so lang, wie ein Sprinter (was das kleinste Auto sein wird). > Projekt M. schrieb: >> In der Realität fährt man, trotz Navi-Ansage, >> nicht über die Straßen, auf denen viel Verkehr ist > > Sorry, da muß ich jetzt mal nachfragen: > Du hast schon selbstfahrend eine relevante Kilometerleistung (also nicht > nur alle paar Jahre mal 'n paar km) im Großstadtverkehr zurückgelegt? > Idealerweise zumindest teilweise auch (noch) selbst navigiert? > > Denn falls ja, solltest Du eigentlich Wissen, daß man innerstädtisch bei > etwas längere Strecken fast immer den größten Teil der Strecke > Hauptstraßen benutzt, obwohl der Verkehr dort deutlich dichter ist als > in den parallel verlaufenden Gassen und auf diese Weise i.d.R. auch > schneller ans Ziel kommt. Korrekt. Es geht nur darum, dass nicht alle Autos über eine verstopfte Kreuzung fahren wollen, wenn eine Seitenstraße frei ist.
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.