Konzeption: Indoor Navigation

Für ein kleines Java Projekt zeige ich momentan Gebäudepläne an, mit denen man ein wenig interagieren kann (z.B. Suche nach bestimmten POIs.)

Jetzt fehlt als letztes Feature noch die Navigation.

Intuitiv wollte ich zuerst einfach einen ungerichteten Graphen erstellen und dann mit Dikstra,oder was auch immer den kürzesten Weg berechnen und dann in die Karte einzeichnen.


Allerdings habe ich keine Ahnung wie ich den Anfangsknoten berechnen soll, da die aktuelle Position ja nicht zufällig auf einem Knoten sein muss.
Und aufgrund von den Mauern kann ich auch nicht einfach den nächsten Knoten auswählen.

Weiß jemand wie dieses Problem normalerweise umgangen wird? (z.B. alle Mauern verzeichnen)
Super wäre natürlich auch Literatur (idealerweise online frei verfügbar)´, da ich in den letzten Tagen dazu nichts wirklich gutes gefunden habe.

Verzeichne alle Mauern und wähle so viele Wegknoten, dass alles konkav eingeschlossen ist.
Dann kannst du von deinem aktuellen Standort zu jedem Knoten (in der Nähe) ein Strich ziehen und auf Kollision mit einer Mauer testen, wenn es keine gibt, dann hast du ein geeigneten Knoten. Solltest du auf der Mauer sein, hast du ein Problem .

Das ist jetzt nicht wissenschaftlich aber mal ne Idee.

Bei Half-Life weiß ich, dass Valve mit Flächen als Knoten arbeitet, das könnte auch ein cleverer Ansatz sein.

Ein A* mit mehreren Zielen (den Djkstra-Knoten) ?
Wobei man dann imho auch gleich den A* nehmen könnte, für ne Indoor-Navigation ausreichend.

Hancock schrieb:

Verzeichne alle Mauern und wähle so viele Wegknoten, dass alles konkav eingeschlossen ist.

Zum Vergrößern anklicken....

Das ist dann leider schon ein recht großer Aufwand da ich diese per Hand erstellen müsste.

Vermutlich wird es aber keine besseren Möglichkeiten geben.

Neija, brauchst du denn den Djkstra? Der wird ja vor allem in Navigationsystemen eingesetzt weil es sehr viele Wegpunkte gibt, also viele Straßen in Deutschland.
Für eine Indoor-Navigation könnte doch A* vollkommen ausreichen oder? Wände usw. werden automatisch durch nicht-passierbare Kacheln abgedeckt. Auch Probleme wie Anfangs- und Endpunkt sind dann kein Problem mehr, da die gesammte Fläche durch A*-Kacheln abgedeckt ist, man muss also nur die X- und Y-Koordinate in die nächste Kachel umwandeln, ein 2-Zeiler.

ice-breaker schrieb:

Neija, brauchst du denn den Djkstra? Der wird ja vor allem in Navigationsystemen eingesetzt weil es sehr viele Wegpunkte gibt, also viele Straßen in Deutschland.
Für eine Indoor-Navigation könnte doch A* vollkommen ausreichen oder? Wände usw. werden automatisch durch nicht-passierbare Kacheln abgedeckt. Auch Probleme wie Anfangs- und Endpunkt sind dann kein Problem mehr, da die gesammte Fläche durch A*-Kacheln abgedeckt ist, man muss also nur die X- und Y-Koordinate in die nächste Kachel umwandeln, ein 2-Zeiler.

Zum Vergrößern anklicken....

A* ist doch nur eine Erweiterung des Djkstra Algorithmu,s der um eine Abschätzfunktion erweitert wurde.

Und wie genau meinst du das mit den Kacheln? Bin grundlegend immer von einem Wegegraph ausgegangen...

Ja, du hast mit der Aussage zu A* schon Recht. Beim Djkstra ist es aber wirklich so, dass dort meist Wegpunkte genommen werden, also z.B. bei der Autonavigation sind die Straßen die Edges, und überall wo sich 2 Straßen treffen ist ein Knoten.
Das gleiche gilt zwar theoretisch auch für den A*, aber er wird z.B. in Spielen (und hier wäre es auch sinnvoll) anders implementiert. Es gibt keine fest vorgegebenen Wege und Wegpunkte mehr, sondern du nimmst einfach z.B. einen 20m^2 Raum und unterteilst diesen in viele kleine 50cmx50cm Kacheln. Das ganze kannst du dann schön als zweidimensionales Array speichern
Die Kacheln sind einfach boolean Werte: true ist begehbar und false ist nicht begehbar, z.B. bei Hindernissen. Und von jeder Kachel aus kannst du alle 4 umliegenden Kacheln betreten, du musst also nicht extra die Wege speichern, das kann dynamisch von jeder Position aus gemacht werden.

Dein Startpunkt und Endpunkt mappst du also auf eine Kachel, das ist ja ziemlich einfach auf Grund der quadratischen Kacheln. Und dann einfach eine A*-Berechnung und fertig. Du brauchst keine vorgelegten Wegpunkte usw. du musst nur die Information speichern welche teile begehbar sind und welche nicht.

Richtig gute Quellen finden man leider zu der Kachelnavigation nicht.
Und die Frage ist außerdem wie man dann sinnvoll die Navigation über mehrere Gebäude-ebenen (was auch möglich ist) sinnvoll umsetzt.

Bin daher leider noch nicht wirklich weiter gekommen bei dem Problem.

Richtig gute Quellen finden man leider zu der Kachelnavigation nicht.

Zum Vergrößern anklicken....

Hä? Die Kachelwelt ist doch meist der Einstieg in das Navigationsthema.
Die andere Sichtweise (die aber das selbe meint) ist über Graphen oder spezieller bei einem festen Startpunkt Bäume.
Jede Kachel ist ein Knoten des Graphen und jede existierende Kante von Knoten A zu Knoten B repräsentiert die Möglichkeit direkt von A nach B gehen zu können.

In der Kachelwelt hat also jede Kachel 4 oder 8 Nachbarn, je nachdem ob man auch schräg gehen darf. Falls eine Nachbarkachel eine Wand ist kann man sie natürlich nicht betreten. Es reicht also die "begehbaren" Kacheln im Graphen zu repräsentieren.

Sonst nimm dir halt mal ein Karopapier und mal ein bisschen... schwarz für wand und weiß für begehbar.
Ein Zimmer beseht dann zB aus 3x3 weißen Kacheln die von schwarzen Kacheln umgeben sind.
Wenn sich Kacheln maßstabsgetreu in die Welt abbilden lassen sollen musst du natürlich eine Auflösung wählen die fein genug ist. Ne Wand wird dann locker 2, 3 Kacheln einnehmen und begehbare Räume viele hundert.

http://www.cs.washington.edu/robotics/mcl/animations/fastslam-still.gif

In der Robotik mit realen Sensoren kommt dann erscchwerend hinzu, dass Sensoren immer Fehler machen und man daher nur von einer "vermuteten" Wand sprechen kann wenn ein Sensor ein Objekt sieht. Dh der Verdacht erhärtet sich mit der Zeit, dass eine bestimmte Kachel WAND ist - eben je öfter sie gesehen wird. Dh du repräsentierst eine Kachel in einem Programm nicht nur durch bools (1 und 0) sondenr durch Zahlen die eine Wahrscheinlichkeit angeben, dass eine Kachel eine Wand ist.
Darstellen kann man das über immer dunklere Pixel, je sicherer der Roboter sich ist:
http://www.cimat.mx/~jbhayet/icons/slam.jpg

Hier nochmal ein Bild wo man die Kachelwelt dank grober Pixel gut erkennen kann:
http://www.pirobot.org/blog/0015/map-1b.png

Zum Thema Gebäude-Ebenen
Sofern es sich um ein fliegendes Objekt handelt was auch ungewöhnliche Wege wie "aus Fenster raus und durch höheres Fenster wieder rein" kann wirst du um ein 3D-Modell nich drumrum kommen. Was ist also die 3D-Kachel? Ein Würfel natürlich
http://slam6d.sourceforge.net/images/bremenCity.jpg
http://www.iri.upc.edu/people/rvalencia/images/iros09.png

Sofern der Robi oder wer auch immer NICHT fliegen kann spricht nichts dagegen die verschiedenen Ebenen einfach "nebeneinander" zu verwalten.
Dh eine Treppenhauskachel hat dann nicht nur 4 (8) Nachbarn sondern in eine Richtung eben noch 1 bis 2 Zusätzliche.
Ich kann nämlich nicht nur wieder zurück in die Etage aus der ich komme sondern auch in eine höhere Etage (+1 Nachbarkachel) oder sogar auch eine tiefere (dann +2 Nachbarkacheln)