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.
quelle
Antworten:
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.
quelle
ompl::NearestNeighborsSqrtApprox< _T >quelle