Nearest-Neighbor-Datenstruktur für nicht-euklidischen Konfigurationsraum

15

Ich versuche, eine Nearest-Neighbour-Struktur für die Verwendung in einem RRT-Bewegungsplaner zu implementieren. Um das besser zu machen als eine lineare Brute-Force-Suche nach nächsten Nachbarn, möchte ich so etwas wie einen kd-Baum implementieren. Es scheint jedoch, dass die klassische Implementierung des kd-Baums davon ausgeht, dass jede Dimension des Raums in "links" und "rechts" unterteilt werden kann. Dieser Begriff scheint nicht auf nichteuklidische Räume wie SO (2) zuzutreffen.

Ich arbeite mit einem seriellen Manipulatorarm mit vollständig rotierenden Verbindungen, was bedeutet, dass jede Dimension des Konfigurationsraums des Roboters SO (2) und daher nicht-euklidisch ist. Kann der kd-tree-Algorithmus geändert werden, um diese Art von Subspaces zu verarbeiten? Wenn nicht, gibt es eine andere Nearest-Neighbour-Struktur, die diese nicht-euklidischen Unterbereiche handhaben kann und dennoch einfach zu aktualisieren und abzufragen ist? Ich habe mir auch FLANN angeschaut , aber aus ihrer Dokumentation war mir nicht klar, ob sie mit nicht-euklidischen Teilräumen umgehen können.

giogadi
quelle
Übrigens sind auch ungefähre Nachbarn in Ordnung (sogar bevorzugt, wenn die Beschleunigung beträchtlich ist)
Giogadi
1
Obwohl Sie eine ausgezeichnete Antwort akzeptiert haben, ist es in der Regel eine gute Idee, einige Tage zu warten, bevor Sie eine Antwort akzeptieren, damit Sie nicht von weiteren Antworten abhalten, die möglicherweise andere Optionen bieten.
Mark Booth
Vielen Dank, Mark, ich war mir nicht sicher, wie lange ich warten sollte, bis ich die Antwort akzeptierte.
Giogadi

Antworten:

6

Sie haben Recht, dass kd-trees normalerweise nur in kleinen, euklidischen metrischen Räumen funktionieren. Es gibt jedoch viel Arbeit für allgemeine Nearest Neighbor-Anwendungen in metrischen Räumen (überall, wo Sie im Wesentlichen eine Abstandsfunktion definieren können).

Die klassische Arbeit befasst sich mit Kugelbäumen , die dann zu metrischen Bäumen verallgemeinert wurden .

Es gibt einige neuere Arbeiten namens Cover Trees, die sogar GPL-Code enthalten. Ich wollte schon seit mehr als zwei Jahren die Leistungsmerkmale zwischen diesen Bäumen und kd-Bäumen untersuchen.

Hoffentlich passt das zu Ihrer Anwendung.

Chris Mansley
quelle
Entschuldigung, das nicht zu akzeptieren; Ich folge nur dem Rat eines anderen Kommentators, um dieser Frage noch ein paar Tage Zeit zu geben, um sie zu "schmoren". Ich fand Ihre Antwort jedoch wirklich hilfreich!
Giogadi
Booo. Ich mache nur Spaß. Ich bin nur froh, dass Sie dies hilfreich fanden.
Chris Mansley