Was sind die neuesten Algorithmen für die Wegfindung auf einer kontinuierlichen Karte der Erde?

14

Angenommen, ich besitze irgendwo in den Fjorden Norwegens ein solarbetriebenes autonomes Überwasserschiff, das einen relativ aktuellen Kartensatz, einen GPS-Empfänger und keine Möglichkeit zum Downlinken detaillierter Befehle von mir enthält. Dieses Schiff muss zum Beispiel zum frühestmöglichen Zeitpunkt die Insel Hainan erreichen.

  • Was sind die deterministischen Algorithmen zum Auffinden einer Seeroute auf einem Globus?
  • Was ist ihre Zeit und Gedächtniskomplexität?

  • Kann ich beispielsweise A * verwenden, nachdem ich die Karte des Globus in ein Diagramm mit verbundenen Polygonen (dh Delaunay-Triangulation auf einer Kugel / einem Ellipsoid) umgewandelt habe, und was sind andere mögliche Ansätze?

Die Antworten sollten idealerweise Verweise auf Beiträge enthalten, in denen die oben genannten Fragen diskutiert werden.

Wie von Rob Lang herausgestellt , müssen die Algorithmen die üblichen Kriterien erfüllen: Führen Sie ohne zeitliche Einschränkungen zum kürzesten Weg zwischen zwei beliebigen Punkten auf den Ozeanen und Meeren der Erde, oder weisen Sie auf einen anderen Fehler bei der Wegfindung hin.

Hier gibt es interessante Unterthemen (Handel mit Vorberechnungszeit / Speicherplatz für Online-Berechnungen, Bereitstellung leicht suboptimaler Routen vor Ablauf einer Frist usw.), die jedoch das Hauptproblem ergänzen.

Hirschjäger
quelle
1
@JDong - Landbasierte Navigation folgt im Großen und Ganzen Routen / Straßen, daher kommt A * natürlich vor. Ein vorgefertigtes Diagramm würde ich verwenden.
Deer Hunter
1
Ah, ich habe den kritischen Teil Ihrer Frage verpasst: "kontinuierlich". In diesem Fall könnten möglicherweise Vektor- oder potenzielle Felder vielversprechend sein.
JDong
1
@RobLang - Frage bearbeitet.
Deer Hunter
1
Für eine Seeroute müssen Sie den Meeresspiegel, den Wind und den Wasserfluss in die Berechnungen einbeziehen. Um was für ein Schiff handelt es sich? OpenSeaMap bietet einige Versandwege. Wenn Sie diese verwenden könnten, würde A * funktionieren. Ich denke auch, dass diese Frage für diese Beta zu weit gefasst ist.
PiTheNumber
1
Ich denke, diese Frage ist in Ordnung, wenn nur die besten Algorithmen zur dynamischen Wegfindung für kontinuierliche Räume von heute gefragt werden. Ich könnte versuchen, dies später nach ein wenig Recherche zu beantworten.
JDong

Antworten:

7

Das deterministische Erfordernis ist nicht allzu einschränkend. Das bedeutet nur, dass Ihr Fahrzeug sicher ist, in welchem ​​Zustand es sich befindet. Abgesehen davon möchten Sie wahrscheinlich Wege so planen, dass Sie Hindernissen ausweichen können. Ich habe dies am besten mit stichprobenbasierten Planern gesehen. Steven LaValle schrieb die zentrale wissenschaftliche Ressource zu diesem Thema: Planungsalgorithmen .

Der RRT * -Algorithmus gehört zu den Planern, die er beschreibt. Dieser Algorithmus generiert den Zustandsraumbaum mit Zufallsstichproben und einigen Heuristiken, um Machbarkeit (z. B. Vermeidung von Hindernissen) und Optimalität sicherzustellen. Details zu RRT * finden Sie im Buch von LaValle oder auf der Website von Sertac Karaman . Die asymptotischen Zeit- und Speichereigenschaften werden als O (nlogn) zum Verarbeiten und O (n) für Abfragen beschrieben. Der Algorithmus ist auch in der Raumkomplexität linear, O (n).

jdmartin86
quelle
Upvoted für die Schiedsrichter. Ich werde in Betracht ziehen, zuzustimmen, nachdem ich LaValles Buch gelesen und das RRT * -Stoff durchgesehen habe. Vielen Dank!
Deer Hunter
4

Für Ihre weitere Überlegung sind potenzielle Felder eine interessante, kostengünstige Wahl für die Wegfindung. Sie würden am Zielort eine starke Gebühr erheben, und der Agent würde schließlich die Gebühr erheben. Ein eher technischer Artikel der Internationalen Stiftung für autonome Agenten und Multiagentensysteme bietet weitere Einblicke.

Vektorfelder sind ebenfalls eine sehr kostengünstige Lösung, werden jedoch häufiger für die Pfadfindung mehrerer Agenten verwendet . Vektorfelder eignen sich jedoch sehr gut für Freiflächen. Keine der oben genannten Methoden garantiert jedoch den kürzesten Weg, wobei eine optimale Wegführung für eine bessere dynamische Reaktion geopfert wird.

Kombinierte Ansätze sind ebenfalls von großer Bedeutung, beispielsweise die vorherige Verwendung von A * zum Generieren von Wegpunkten und die Verwendung von Vektorfeldern, um zu jedem Wegpunkt zu gelangen. Dies wird wahrscheinlich ein viel optimaleres Verhalten auf einer Makroskala ergeben.

Denken Sie daran, falls Sie eine Schwimmroboterarmee erwerben.

JDong
quelle