route berechnen?

[Newbie44]

Hallo,

ich hab mal eine frage an alle hier, die sich mit navigation schon mal beschäftigt haben. es geht nicht um eine spezielle programmiersprache (is ja eh alles sehr ähnlich)

Wie macht man einen Navigationsalgorythmus? Hat jemand schon mal sowas gemacht, bzw hat es vor das ganze zu machen? Ich bin heute nämlich mit nem Navigationssystem gefahren und finde es einfach nur genial.

Die Route war perfekt, schön kurz und ich bin rechtzeitig angekommen.

Jedoch wie sieht so ein algorythmus aus?

gruß

sebastian

[Matze]

Hi,

der A*-Algorithmus, den ich für mein Snake nutze, falls du das mitverfolgt hast, kann auch für Navis eingesetzt werden. Siehe hierzu auch das Beispiel von Wikipedia.

Edit: Wieso geht denn diese URL nicht mit den [url]-Tags? Naja, dann so: http://de.wikipedia.org/wiki/A*-Algorithmus#Beispiel

[Newbie44]

hey danke, wusste gar nicht das es schon so nen algo gibt. aber ich finde es echt beeindruckend was heutzutage schon alles möglich ist. aber seit ich auf die navigation gekommen bin, find ich es spannend wie das alles funktioniert.

Bin mal gespannt auf das Galileo Navigationssystem

ach ja dann noch ne frage, kennt jemand ne navigationssoftware die opensource ist, damit man sich das ganze mal ansehen kann?

@Matze

Hab leider dein Thema nicht verfolgt, bin ja auch nur noch selten online

[Der_Unwissende]

HI,
der konkrete Algorithmus dürfte sicherlich je nach System etwas anders ausfallen, aber an sich kannst Du Dich ganz einfach vom Routing insperieren lassen. Daten von einer IP-Adresse an eine andere zu leiten ist selten direkt möglich, auch hier geht es also um nichts anderes als eine Route (einen Weg) zu finden. Zudem wird beim Routing auch gleich versucht Staus u.Ä. zu berücksichtigen.

Bei Navigationssystemen dürfte der Ansatz prinzipiell ähnlich funktionieren (ohne Gewähr!). An sich bietet es sich aber schon an, dass Du einfach mit Graphenalgorithmen arbeitest. Dabei wird nicht jede Straße gleich bewertet, man wird sicherlich eher mit verschieden großen Rastern arbeiten (z.B. lässt sich der kürzeste Weg von einer Stadt in eine andere getrennt vom Weg in den jeweiligen Städten betrachten!). Ähnlich dürfte es dann wiederum in einzelnen Städten aussehen, da gibt es schließlich auch wieder Bezirke (bzw. eine Rasterung), so dass man erstmal nur die kürzeste (besser gesagt schnellste/kostengünstigste) Route in den entsprechenden Sektor sucht und erst von dem Punkt aus weiter ins Detail geht (die eigentliche Straße).

Gruß Der Unwissende

[roter Kasten]
A*, Dijkstra, ... sind dann alles mögliche Algorithmen um einen kürzesten Weg zu finden. Wie gesagt, Graphenalgorithmen eben
[/roter Kasten]

[leddl]

Zitat:

Zitat von Newbie44

hey danke, wusste gar nicht das es schon so nen algo gibt.

:stupid: Wie sollte dein Navi doch sonst geleitet haben? :mrgreen: Und warum fragst du dann danach? :stupid:

[Udontknow]

Hallo!

In diesem Tutorial habe ich mal per Backtracking die Wegfindung realisiert, vielleicht hilft es ja.

Cu,
Udontknow

[Newbie44]

Zitat:

Zitat von Der_Unwissende

HI,
man wird sicherlich eher mit verschieden großen Rastern arbeiten

da is was dran mit den rastern, is mir auch aufgefallen, das navi zeigt ja nicht alle straßen auf einmal an, in den verschiedenen zoom größen. je näher man rangeht, desto mehr details findet man.

es könnte auch so sein, das das navi erst die großen strassen berechnet, und dann die kleinen, sprich erst den groben weg, und den dann noch optimiert.

wäre das denkbar oder zu unhandlich?

[Matze]

Zitat:

Zitat von Newbie44

wäre das denkbar oder zu unhandlich?

Ich vermute, das Navi schaut erst nach den Straßen, auf denen am schnellsten gefahren werden darf (Autobahnen, Bundesstraßen, Land-/Kreisstraßen), sofern diese nicht zu allzu großen Umwegen führen. Dann werden kleinere Straßen berücksichtigt, wenn es beispielsweise durch Orte geht oder man in Zielnähe ist bzw. auf dem Weg zu Schnellstraßen. Natürlich müssen Einbahnstraßen berücksichtigt werden.

Das fand ich kürzlich so faszinierend: Das Navi lotste uns einmal im Kreis herum und ich wunderte mich, was das soll, habe dann jedoch gesehen, dass man nicht direkt links abbiegen durfte, wo wir hin mussten und so machte das Navi einen intelligenten Bogen.

[Newbie44]

das stimmt, das wäre die beste lösung zum navigieren. aber wenn man mal mit knotenpunkten rechnet, nur mal bei autobahnen, das sind ja da schon viele, aber es gibt enorm viele knotenpunkte die man beachten müsste.

das navi müsste die ja alle durchprüfen, was jetzt der beste weg wäre, eigentlich müsste dsa ja länger dauern, es geht aber immer unheimlich schnell, das is das was mich so wundert.

scheint ein ziemlich schneller algorithmus zu sein

[leddl]

Zitat:

Zitat von Matze

Ich vermute, das Navi schaut erst nach den Straßen, auf denen am schnellsten gefahren werden darf (Autobahnen, Bundesstraßen, Land-/Kreisstraßen

Das kommt natürlich drauf an, was der Zweck der Routenberechnung ist :zwinker:
Im Normalfall kannst du zwischen schnellster und kürzester Route (und evtl. noch diverse anderen) wählen. Ich zB lasse immer die kürzeste berechnen und manchmal verbiete ich Autobahnen sogar komplett, da ich ganz genau weiß dass ich auf Bundes- und Landstraßen *hüstel* ein bißchen schneller unterwegs bin, als das Navi es vorsieht :mrgreen:
Und dann werden aber wirklich nicht unbedingt die größten möglichen Straßen gewählt, sondern dann findet man sich ganz schnell auch mal auf nem kleinen Feldweg wieder, weil man damit die 100m Umweg einer Kurve spart :lol:

//Edit:

Zitat:

Zitat von Newbie44

das stimmt, das wäre die beste lösung zum navigieren. aber wenn man mal mit knotenpunkten rechnet, nur mal bei autobahnen, das sind ja da schon viele, aber es gibt enorm viele knotenpunkte die man beachten müsste.

das navi müsste die ja alle durchprüfen, was jetzt der beste weg wäre, eigentlich müsste dsa ja länger dauern, es geht aber immer unheimlich schnell, das is das was mich so wundert.

Ich gehe davon aus, dass bereits durch heuristische Verfahren ein ungefährer Weg errechnet wird, wodurch dann sehr viele Wege gar nicht mehr berechnet werden müssen. Wenn dann noch die dynamische Programmierung angewendet wird, fallen wieder einige Wege weg, so dass die endgültige Menge an vollständig zu berechnenden Wegen halbwegs überschaubar sein wird.

[Der_Unwissende]

Zitat:

Zitat von Matze

Ich vermute, das Navi schaut erst nach den Straßen, auf denen am schnellsten gefahren werden darf (Autobahnen, Bundesstraßen, Land-/Kreisstraßen), sofern diese nicht zu allzu großen Umwegen führen. Dann werden kleinere Straßen berücksichtigt, wenn es beispielsweise durch Orte geht oder man in Zielnähe ist bzw. auf dem Weg zu Schnellstraßen. Natürlich müssen Einbahnstraßen berücksichtigt werden.

Hier denke ich lohnt sich eben diese Rasterung. So kann man ja leicht einen Ort oder ein Land rastern und dort für Start- und Zielpunkt den nächsten Punkt suchen. Möchte man sich z.B. nur innerhalb Berlins bewegen, wird kaum die Deutschlandkarte betrachtet. Möchte man hingegen nach München, nun ja,...
Hat man die beiden Knoten, die dieser gröbsten Granularität entsprechen, kann man weiter in Detail gehen. Im einfachsten Fall haben beide bereits den gleichen Knoten, dann ist natürlich nichts weiter zu tun. Ansonsten sucht man eben den kürzesten Weg. Verwendet man dabei gerichtete Graphen, so lassen sich solche Dinge wie die Fahrt im Kreis leicht (und effektiv) berücksichtigen. Jede Verbindung zwischen zwei Knoten hat zudem sicherlich eine Angabe der Kosten. Die dürften eben auf Autobahnen besonders günstig sein, in Verkehrsberuhigten Zonen hingegen entsprechend hoch!
Was man dann nur noch machen muss ist eben für jede Rasterung den entsprechend kürzesten Weg zu finden (z.B. die A9 für die Tour Berlin-München). Dann halt den Weg auf die A9 usw.

[Newbie44]

ja genau das is mir auch schon aufgefallen, ab und zu gibts mal kleine fehler und man wird rückwärts in eine einbahnstraße geschickt (is mir auch schon passiert)

irgendwie find ich das immer lustig wenn solche fehler passieren, nur die programmierer habens da nicht so einfach die fehler zu beheben, der algo is ja ein modifizierter A*, hab ich gerade bei google gelesen.

aber so ne detailliete beschreibung wie ich am schnellsten von A nach B komme gibt es nicht.

Map24 machts ja mit einer Java Anwendung, vielleicht kann man sich den quellcode von den mal anschauen, gibt ja java decompiler, die echt gut funktionieren.

es seid denn, jemand kennt noch ne seite, wo man einen navi algo komplett sehen kann

[leddl]

Zitat:

Zitat von Newbie44

ja genau das is mir auch schon aufgefallen, ab und zu gibts mal kleine fehler und man wird rückwärts in eine einbahnstraße geschickt (is mir auch schon passiert)

Das sind im Normalfall aber keine Berechnungsfehler :zwinker: Das passiert, wenn dein Kartenmaterial nicht up 2 date ist oder wenn die GPS-Verbindung kurz flöten gegangen ist und das Navi dadurch durcheinandergeraten ist :zwinker:

[Matze]

Zitat:

Zitat von Newbie44

es seid denn, jemand kennt noch ne seite, wo man einen navi algo komplett sehen kann

Ich glaube nicht, dass es da etwas in Open-Source geben wird, denn es handelt sich um hochkomplexe Algorithmen, mit denen man auch gut Geld verdienen kann. Aber vielleicht gibt's auch was.
Dir würde der Source vermutlich auch nichts nutzen, da du sicher nicht verstehen würdest, was die tausenden Zeilen Code genau machen. ;) Eine schematische Übersicht wäre da hilfreicher, nur habe ich noch keine gefunden.

[Newbie44]

Aber es wäre echt mal sehr interessant so einen ablauf zu sehen. ich meine es gibt doch schon soviel opensource, darum wundert es mich das es sowas noch nicht gibt.

aber wenn jemand was in die richtung findet, auch ist ein Strucktugramm sehr sinnvoll

[OregonGhost]

Zitat:

Map24 machts ja mit einer Java Anwendung, vielleicht kann man sich den quellcode von den mal anschauen, gibt ja java decompiler, die echt gut funktionieren.

Ich bezweifle, dass die Java-Anwendung die kompletten Kartendaten herunterlädt, um die Routenplanung auszuführen :roll:
Das passiert serverseitig, sonst könnte man das ja in der Tat leicht stehlen.

Mir sind keine OS-Navigationsalgorithmen bekannt. Davon abgesehen brauchst du ja nicht nur den Algorithmus - detaillierte Kartendaten kosten eine Stange Geld. Das ist sicherlich auch ein Grund, weshalb es keine kostenlose Navigationssoftware gibt.

[Der_Unwissende]

Zitat:

Zitat von Newbie44

Aber es wäre echt mal sehr interessant so einen ablauf zu sehen. ich meine es gibt doch schon soviel opensource, darum wundert es mich das es sowas noch nicht gibt.

Nun ja, irgendwie dürfte das komplette Kartenmaterial von einer Stadt schon recht teuer sein, von einem Land oder Europa mal ganz zu schweigen. Da mag Opensource dann schon an den Kosten scheitern. Und für den Rest gibt es ja einfache Ansätze, die man nach und nach optimieren kann. Wie gesagt, das Routing bei Netzen geht wahrscheinlich schon einen ähnlichen Weg (zumindestens sind die Anforderungen schon mal sehr sehr ähnlich!). Und dort gibt es dann natürlich auch OpenSource (da einige bekannte OS-Betriebssysteme natürlich auch ihre Stärken in Netzwerken, z.B. als Router haben).

[edit]
Roter Kasten streikt heute (in diesem Thread), wollte das mit den Karten nicht sinnlos wiederholen!
[/edit]

[Newbie44]

das mit den kartendaten wundert mich ja eben. die sind echt unheimlich teuer. scheint ne menge arbeit diese zu machen.

die 2 größten firmen die das machen (die mir jetzt einfallen) sind soweit ich weis Navteq und Teleatlas

[Der_Unwissende]

Zitat:

Zitat von Newbie44

das mit den kartendaten wundert mich ja eben. die sind echt unheimlich teuer. scheint ne menge arbeit diese zu machen.

Was wundert Dich denn da?! Ich meine alle Straßen samt Richtung, zusammen mit den Angaben über die geltende Geschwindigkeiten (und natürlich auch anzahl der Spuren), dann noch zusätzlich die Verknüpfung mit den GPS-Daten. Da behaupte ich doch einfach mal, dass es allein in einer Stadt schon unheimlich anstrengend sein dürfte, für alle in D oder Europa...

[matashen]

Ich möchte hier mal einen negativen Komentar anbringen. :)

Positiv:
Ich finde Navis ganz gut um in einer größeren Stadt ein bestimmtes Haus zu finden. Dürfte also für Servicetechniker interessant sein !?!

Negativ:
Langstrecken über Navi fahren ist wohl der absolute Schwachsinn. Bis jetzt hab ich auch kein Navi gesehen (bei Geschäftsfahrten will meistens der Fahrer - mach ich ungern- das Navi benutzen)
das sauber geroutet hätte Bsp. Wohnort nach Nürnberg, kenn ich perfekte Route auswendig. Navi Rechnet 190km über was weis ich für Verbindungen als schnellste und wir sinds dann um 70!km kürzer und 45min schneller gefahren (ohne gegen Beschränkungen zu verstoßen - bevor da jemand was falsches denkt). Anderes Beispiel. Wollte auf ein Konzert, Kumpel mit Navi über meine Strecke ausm FF sind wir 150km gefahren Laut Navi war die Verbindung 280km und 3Std Fahrzeit - tja da waren wir dann auch etwas schneller :-D

Wenn jemand mal so nen genialen Code entwickelt der das in perfekto kann, Hut ab. Aber derzeitiger Stand der Technik - In Stadt ja - Fernverbindung, auf keinen Fall - Da leist ich mir dann doch lieber den Satz Straßenkarten ausm Discounter für ein paar Euro.
Das zu einem Perfekten System auch ein Perfekter Kartensatz gehört versteht sich von selbst,das wird auch denke ich weiter verbessert.

Anmerkung:
Für die meisten Leute handelt es sich eh mehr um ein Prestigeobjekt. Denn wenn ich einmal die Woche zum Einkaufen fahre und täglich in der Arbeit sitze, frag ich mich wozu brauch ich dann ein Navi, für einmal im Jahr in die Alpen?. Schließlich ist ja keiner so gemein und reißt Tagsüber eine Straßenverbindung weg und verpflanzt diese an einen anderen Ort um Leute zu verwirren, und die tägliche Strecke sollte man dann doch kennen.

Gruß und viel Spaß beim zerpflücken meiner Meinung zum Thema Navi :mrgreen:

[Matze]

Die modernen Navis, zumindest die, die in besseren Autos verbaut sind, funktionierten bei mir bisher einwandfrei. Es gibt bei Navis auch gewaltige Unterschiede, doch das gehört nicht zum Thema Navi-Algorithmen. ;)

Eine nette Powerpoint-Präsentaion gibt's übrigens hier.

[matashen]

Da muss ich Matze zustimmen, mein Beitrag war absolut Off-Topic :twisted:

Und die Präsentation ist gutes Material: Danke Matze !

Gruß Matthias