Osmand Routenplanung

[Stempel]

Kann sein, dass der Algorithmus in zB Osmand nicht optimal ist. Jedoch macht eine einfache Abschätzung plausibel, dass bei gleichbleibend komplexem Straßennetz das finden der kürzesten Strecke quadratisch mit dem Abstand von Start zu Ziel anwächst. Steigt die Distanz also von 100km auf 1000km, so wird der Rechenaufwand um Faktor 100 steigen. Aus 1 Min wird dann die Dauer eines Fußballspiels.

Im Handy hat man nur 1 CPU und eher mäßige I/O Performance. Google hingegen hat nichts anderes zu tun, als Sääle mit Servern voll zu stellen, die entsprechend I/O mäßig verknüpft sind. Durch ein paar Rechnungen für Routing werden sie bei üblicher Internetsuche kaum merkbar belastet.

Google kann außerdem permanent stauangepasst regelmäßig Standards rechnen, und das immer gleiche Ergebnis an 1000e Autofahrer, die zB von F nach HH Autobahn fahren. Durch sinnvolles Legen der Standardstrecken mit Enden an wichtigen Knotenpunkten kann mit minimalem Aufwand für ganz D oder Europa das Fernverkehrsnetz permanent mit optimal befahrbahren Routen abgedeckt werden. Das immergleiche Ergebnis geht dann an Mio von KFZ Nutzern.

Individuell für mein Handy wird dann noch die Zubringerstrecke berechnet. Das kann dann Osmand vielleicht genau so gut.

 

[Androider10310]

Alles falsch: mein 5 Jahre altes TomTom hat sicher nur ein Bruchteil der CPU Leistung meines 1.5 GHz Quadcore 2 GB RAM Smartphones (Xperia ZL). Und das TomTom braucht für die exakte Routenplanung nach Italien nicht mal 30 Sekunden. Das Argument "Hardware" ist somit unberechtigt.

Es liegt an der Software. Und als Software-Entwickler (der auch schon Routing Algorithmen geschrieben hat) kann ich sehr wohl beurteilen, daß ein solcher Algorithmus relativ "popelig" ist. (Hätte ich genug Zeit, würde ich so 'ne App auch selbst schreiben, aber ich gebe lieber Geld aus um fertige Software zu kaufen, wenn sie ordentlich die Erwartungen erfüllt.)

Insofern hoffe ich, daß die Osmand Entwickler wenigstens mal ein paar Tage in einen ordentlichen Suchalgorithmus investieren. Es ist wirklich nicht schwer und mit ein wenig mehr Hirn (und mehreren Augen) bekommt man daß auch ordentlich performant hin.

 

[NavGuenni]

Kann sein, dass der Algorithmus in zB Osmand nicht optimal ist. Jedoch macht eine einfache Abschätzung plausibel, dass bei gleichbleibend komplexem Straßennetz das finden der kürzesten Strecke quadratisch mit dem Abstand von Start zu Ziel anwächst. Steigt die Distanz also von 100km auf 1000km, so wird der Rechenaufwand um Faktor 100 steigen.

Bei Anwendung eines Highway Hierarchies Algorithmus ist das nicht so.
Leider ist es nicht so einfach, an der Entwicklung teilzunehmen, als theoretische Grundlagen zu finden.
So fehlen mir die nötigen Vorkenntnisse und Erfahrung in der Programmiersprache, und beim Blick auf den Code kann ich deshalb auch nicht feststellen, was dort passiert.
Noch nicht mal eine Möglichkeit die Entwicklung des Routings zu fördern habe ich gefunden. Zur Aussage "It is also possible to fund specific new Features" bei OsmandFunctionalitySummary - osmand - This article summarizes `OsmAnd's` key functionality - Global Mobile Map Viewing & Navigation for Offline and Online OSM Maps - Google Project Hosting konnte ich keine konkrete Möglichkeit entdecken.

Gruß,
Günther

 

[Ungewiss]

Wie schon gesagt: laut osmand Forum ist die Berechnung in den aktuellen Nightlies schon deutlich schneller. Dennoch bei Weitem nicht mit dem Offline Routing von z.B. skobbler (auch OSM als Basis) konkurrenzfähig. Das errechnet 3 Routen in der Zeit, in der Osmand eventuell die Stadt bei der Adresssuche gefunden hat.

 

[Lenoid]

Alles falsch: mein 5 Jahre altes TomTom hat sicher nur ein Bruchteil der CPU Leistung meines 1.5 GHz Quadcore 2 GB RAM Smartphones (Xperia ZL). Und das TomTom braucht für die exakte Routenplanung nach Italien nicht mal 30 Sekunden. Das Argument "Hardware" ist somit unberechtigt.

Das hat aber auch nur einen Bruchteil der Kartendetails.


Habt ihr es mal mit den reinen Straßenkarten versucht?
Generell ist OsmAnd noch nicht wirklich für die Navigation geeignet. Das sieht man auch am fehlenden 3D-Modus. Es hat einfach andere Stärken.
Als Navi empfehle ich Mapfactor Navigator.

 

[Androider10310]

Das hat aber auch nur einen Bruchteil der Kartendetails.

Kartendetails sind für das Routing unerheblich. Nur die reinen Straßen zählen und die sind genau so viel bei TomTom als auch bei allen anderen Navigationsprogrammen. (Je nach Aktualität der Karten sind' halt mal ein paar Straßen mehr oder weniger; was aber nicht in's Gewicht fällt.)

 

[Lenoid]

Kommt drauf an, bei der OSM muss eine wesentlich größere Datenbank durchwühlt werden. Zudem ist der Algorithmus bei TT logischerweise wesentlich ausgereifter.

Wie gesagt, Osmand ist für Navigation derzeit einfach nicht gemacht, das kommt hoffentlich noch.

 

[Silverbird]

Kommt drauf an, bei der OSM muss eine wesentlich größere Datenbank durchwühlt werden. Zudem ist der Algorithmus bei TT logischerweise wesentlich ausgereifter.

Wie gesagt, Osmand ist für Navigation derzeit einfach nicht gemacht, das kommt hoffentlich noch.

Die Daten von OSM und TeleAtlas(TT) sollten annähernd gleich sein. Bei OSM vllt. eher weniger, denn da dort noch nicht alle Städte und Gemeinden vollständig eingetragen sind und es auch nicht überall 3D-Modelle gibt.

 

[NavGuenni]

Habt ihr es mal mit den reinen Straßenkarten versucht?

hab ich versucht, keinen Unterschied bemerkt.

Generell ist OsmAnd noch nicht wirklich für die Navigation geeignet.

Steht im Widerspruch zur Beschreibung im Store, aber mag wohl so sein. Ist das eine offizielle Aussage von OSMAND?

Das sieht man auch am fehlenden 3D-Modus.

Den sehe ich nun wirklich nicht als relevant an.

Es hat einfach andere Stärken.

z.B. Die POI-Suche die mir nur wenig bringt, wenn ich mit n'em anderen Navi unterwegs bin

Als Navi empfehle ich Mapfactor Navigator.

Habe ich tatsächlich am WE ausprobiert. der zeigt mal was Routing ist: unter 10 s

 

[Lenoid]

Die Daten von OSM und TeleAtlas(TT) sollten annähernd gleich sein. Bei OSM vllt. eher weniger, denn da dort noch nicht alle Städte und Gemeinden vollständig eingetragen sind und es auch nicht überall 3D-Modelle gibt.

Ich kann mir nicht vorstellen, dass TT-karten jeden noch so kleinen Feldweg beinhalten und allein D mehrere GB groß ist.

Steht im Widerspruch zur Beschreibung im Store, aber mag wohl so sein. Ist das eine offizielle Aussage von OSMAND?

Ja, damit wird leider geworben. Es steht allerdings auch da, dass Online-Routenplanung schneller geht. Ist sozusagen ein kleiner versteckter Hinweis.
Aber wie gesagt, ohne 3D-Modus ist das eh kein echtes Navi.

Auf kürzeren Strecken gibts ja keine Probleme. Wenn man mal eine längere fahren muss bleibt ja der Workaround mit Mapfactor, auch wenn das ärgerlich ist. Aber ich denke, dass sie das Routing noch hinbekommen werden (inkl. 3D-Modus).
Die App wird ja ständig weiterentwickelt. Navigation ist halt immer noch eine Baustelle, damit muss man sich abfinden.

 

[Ungewiss]

Ich kann mir nicht vorstellen, dass TT-karten jeden noch so kleinen Feldweg beinhalten und allein D mehrere GB groß ist.

Navteq Karten, wie sie Garmin nutzt, enthalten in Deutschland das Kartenmaterial der Vermessungsämter und damit auch sehr viele Waldwege. Die Deutschlandkarte ist auch größer als die OSM Karte. Die Topo Karten sind locker doppelt so groß - das hat mit dem Routing nichts zu tun.

Teste skobbler offline, das nutzt auch OSM Karten. Da merkst du den "kleinen" Unterschied.

Ja, damit wird leider geworben. Es steht allerdings auch da, dass Online-Routenplanung schneller geht. Ist sozusagen ein kleiner versteckter Hinweis.

Achja. "Hier verkaufen wir Ihnen ein tolles Auto, das alles kann. Falls Sie sich damit fortbewegen möchten, müssen Sie aber leider schieben oder es abschleppen lassen".

Aber wie gesagt, ohne 3D-Modus ist das eh kein echtes Navi.

Den brauche _ich_ wirklich nicht.

Die App wird ja ständig weiterentwickelt. Navigation ist halt immer noch eine Baustelle, damit muss man sich abfinden.

Ich bin aktiver OSM Mapper. Dafür ist Osmand auch praktisch. Aber das Routing funktioniert von Anfang an nicht brauchbar und das wird immer lächerlicher. Obwohl man damit wirbt.

 

[Lenoid]

Den brauche _ich_ wirklich nicht.

Mag ja sein, trotzdem ist es seit 10 Jahren(?) absoluter Standard, es gibt schon lange kein Navi mehr ohne.
Es geht auch nicht darum ob man es braucht sondern dass wenn absolute Standards fehlen diese Funktion noch nicht ausgereift sein kann.

Ich bin aktiver OSM Mapper. Dafür ist Osmand auch praktisch. Aber das Routing funktioniert von Anfang an nicht brauchbar und das wird immer lächerlicher. Obwohl man damit wirbt.

Routing geht, nur halt nicht für lange Strecken, zumindest nicht offline. Allerdings muss ich zugeben, dass der Hersteller besser darauf hinweisen sollte.

 

[dvdram]

Der Server (zB Google) bekommt vom Client (Dein Handy) die Eckdaten für das Routing (zB HH->M). Dann rechnet der Server alles aus mit einer größeren Datenbank als am Handy speicherbar und einer erheblich besseren CPU und I/O Performance.

Dann bekommst Du das Ergebnis als kleine wenige kB große Datei auf Dein Handy geschickt. Das ist dann wieder online.

So ähnlich stelle ich mir das auch vor: Ausgangspunkt und Ziel werden als Adressen oder als Koordinaten an einen Server übermittelt, der errechnet die Route und gibt einen GPX-Track zurück, also eine Datei mit ganz vielen Zwischenpunkten, deren Abstände so klein ist, daß das Gerät den Weg dazwischen zwei Punkten mit Sicherheit findet.

Unterwegs wird nur geprüft, ob Du auch "richtig" fährst und die Route zB mit aktueller Verkehrsinfo abgeglichen und wenn nötig neu berechnet. Alles nur beim Server. Dein Handy weiß alleine nie über Staus und so Bescheid.

Wieviele Daten fallen denn da unterwegs für die Übertragung an? Hat das schon mal jemand nachgemessen?

Mit der Computerleistung eines Servers lassen sich leicht Optimierungsprobleme wie kürzeste oder schnellste Strecke über mehrere 100km und hochstrukturiertem Straßennetz lösen. Ein Handy schafft das nie. Es ist nämlich alles andere als ein "popeliger Suchalgorithmus".

Auf der anderen Seite: es gab Routenberechnungen für den PC, lange bevor es Mehrkernprozessoren gab. Das, was heute an Rechenleistung in einem Smartphone steckt, davon haben wir vor 10 Jahren als PC-Benutzer geträumt. Und trotzdem konnten unsere PC Routen berechnen, auch ohne dafür die ganze Nacht laufen zu müssen. Also sollte das auf einem modernen Smartphone heute erst recht vernünftig laufen.

Ich finde es auch schade, daß OSMand (noch) nicht vernünftig Routen über mehr als 300km berechnen kann. Aber ich habe mir einfach angewöhnt, Zwischenstops einzulegen. Mehr als 200km am Stück ist sowieso Gift für meinen Rücken, und Pipi muss man ja auch mal ab und zu.

Wer eine Strecke von mehr als 300km zurücklegen muss, und es dabei so eilig hat, daß keine Zeit für Pausen übrig ist, sollte sowieso nicht aktiv am Verkehr teilnehmen. Dafür wurden nämlich Züge und Flugzeuge erfunden.

 

[Lenoid]

Auf der anderen Seite: es gab Routenberechnungen für den PC, lange bevor es Mehrkernprozessoren gab. Das, was heute an Rechenleistung in einem Smartphone steckt, davon haben wir vor 10 Jahren als PC-Benutzer geträumt. Und trotzdem konnten unsere PC Routen berechnen, auch ohne dafür die ganze Nacht laufen zu müssen. Also sollte das auf einem modernen Smartphone heute erst recht vernünftig laufen.

Dazu muss man aber auch sagen, dass die Karten nicht ansatzweise so detailliert waren. Wenn ich mir MS Autoroute anschaue ist dessen Karte ja leer. In alten Versionen waren nicht mal alle Orte drin.
Der Hersteller muss OSMAnd noch optimieren keine Frage. Ich habe auch das Gefühl, dass OsmAnd zumindest beim rendern nur einen Kern nutzt. Denn mein Note 8.0 (4x1,6GHz Exynos 4) ist nicht extrem viel schneller als mein Pro (1x1,0GHz S2). Wobei hier vielleicht auch die externe SD (Class 10) limitieren könnte.

 

[Androider10310]

Die Leute, die hier schreiben, daß ein Smartphone viel zu schwach sei um popelige 1000 KM Route in unter 1 Minute zu rechnen, derhat wohl noch nie ein Navigationssystem gehabt. Bereits ein grafisches Kartennavigationssystem in unserem Geschäftswagen hat vor 12 Jahren schon Routen in ca. 1-2 Minuten gerechnet, die quer durch Deutschland und in's nahe Ausland führten. Und die Karten waren damals schon sehr detailiert und hatten schon diverse POIs angezeigt. Mein altes TomTom schafft das in unter einer Minute (von Norddeutschland bis an die Adria) und rechnet in wenigen Sekunden eine geänderte Strecke aus, wenn man z.B. nicht exakt der berechneten Route folgt. Sorry, aber das ist dummes Zeug, daß ein aktuelles Smartphone nicht genügend Rechenpower hätte. Man braucht überhaupt keine Großrechner um solches Kartenmaterial zu durchsuchen und ein Wegealgorithmus durchzulaufen. Hört doch bitte mit diesen unqualifizierten Ausreden aus - Osmand kann's halt nicht. Das ist alles.

 

[dvdram]

Androider10310: im Kern der Sache stimme ich mit Dir überein. Aber ich sehe die Ursachen für das schlechte Abschneiden von Programmen wie OSMand an anderer Stelle, und zwar bei dem verwendeten Kartenmaterial: es gibt insgesamt nur 4 oder 5 kommerzielle Anbieter für Karten für Navi-Geräte, und die lassen sich ihre Dienste teuer bezahlen. Nicht umsonst kostet eine Aktualisierung der Karten für das Navi, das man mit fünf Jahre alten Karten für'n Fünfziger auf dem Wühltisch eines Kaufhauses bekommt, locker das Vierfache dieses Preises.

Und diese Anbieter tun auch alles, um zu verhindern, daß es Konkurrenz gibt, insbesondere kostenlose Konkurrenz. Ich weiß, daß diese Anbieter sich im Hintergrund gegenseitig mit Patent-, Muster- und Copyright-Klagen überziehen, daß einem Schwindelig wird.

Selbst Dienste wie OSMand leiden darunter, auch, wenn ihre Karten durch Mitarbeit jedes einzelnen Benutzers entstehen. Wehe, irgend etwas sieht zufällig so aus wie auf der Karte von Hersteller X! Und was passiert, wenn OSMand zufällig einen Algorithmus verwendet, der dem von Hersteller Y gleicht, ist nicht schwer zu erraten.

Ich glaube, daß die Ursache für das schlechte Abschneiden von Programmen wie OSMand eher in dieser Art von Technologie-Blockade zu suchen sind.

 

[Androider10310]

Glaube ich eher nicht, denn Osmand muß auch nicht mit den anderen kommerzeillen konkurrieren. Osmand kann seine eigene Marktnische füllen, und die muß nicht absolut aktuelle Karten haben oder besonders tolle live Dienste. Sondern die große STärke ist, daß die Karten offline heruntergeladen werden können. Diese dann kostenlos (durch einmaligen Preis beim Kauf von Osmadn+ abgedeckt). Es gibt genügend Kunden, denen das genügt.

 

[dvdram]

Es geht nicht darum, ob OSMand mit jemanden konkurrieren muss. Es geht um das Damoklesschwert namens "Copyright und Patente".

Probiere es doch einfach selber aus: erstelle eine Straßenkarte Deiner Stadt oder Deines Stadviertels, und stelle sie online allen Menschen zur Verfügung. Sobald Deine Karte nach mehr als einer Strichzeichnung aussieht und somit auch nur im Entferntesten einem kommerziellen Straßenatlas ähnelt, wirst Du Post einer Rechtsabteilung mit der Aufforderung zur Zahlung bekommen. Und dabei ist es völlig egal, ob Du als Grundlage Fotos von Google-Earth nimmst, den alten Diercke-Atlas aus der Schule, mit einer hohen Leiter selber Aufnahmen machst, oder aus dem Gedächtnis zeichnest. Luftaufnahmen mit einer Drohne solltest Du gleich vergessen, denn dann bekommst Du einen solchen Brief noch viel schneller.

 

[Stempel]

Osmand kann's halt nicht. Das ist alles.

Dein Sachverstand kommt hier bestens an. Große Anerkennung!

Osmand ist für Detailsuche gemacht, was die Suche nach Wander- und Fahrradstrecken belegt. Außerdem steht das detallierte Kartenmaterial dafür.

Wollte Osmand ein Autofahrer Fernfahrservice sein, würde es die Kartendaten gleich auf Straßenkarten niederer Auflöung abspecken und seinen Algorithmus darauf optimieren. Wer das will, soll sich halt woanders umsehen, aber bitte Osmand dann in Ruhe lassen.

Um zu testen, ob Osmand für Jemanden passt, genügt das Austesten der kostenlosen Probeversion.

 

[Lenoid]

Wollte Osmand ein Autofahrer Fernfahrservice sein, würde es die Kartendaten gleich auf Straßenkarten niederer Auflöung abspecken und seinen Algorithmus darauf optimieren.

Dummerweise gibt es ja Straßenkarten die nicht mehr Details als die von Navteq und co. enthalten.
Ob es mit diesen besser funktioniert kann ich nicht sagen, da es keine direkte Auswahlmöglichkeit gibt.

Aber es stimmt schon, der Fokus und die Stärken von Osmand liegen woanders als in der Navigation. Allerdings wird diese sicher noch verbessert werden.