Structure de données du plus proche voisin pour l'espace de configuration non euclidien

15

J'essaie d'implémenter une structure de voisin le plus proche à utiliser dans un planificateur de mouvement RRT. Afin de faire mieux qu'une recherche linéaire du plus proche voisin par force brute, j'aimerais implémenter quelque chose comme un arbre kd. Cependant, il semble que l'implémentation classique de l'arbre kd suppose que chaque dimension de l'espace puisse être divisée en "gauche" et "droite". Cette notion ne semble pas s'appliquer aux espaces non euclidiens comme SO (2), par exemple.

Je travaille avec un bras manipulateur série avec des liens entièrement en rotation, ce qui signifie que chaque dimension de l'espace de configuration du robot est SO (2), et donc non euclidienne. L'algorithme kd-tree peut-il être modifié pour gérer ces types de sous-espaces? Sinon, existe-t-il une autre structure de voisin le plus proche qui peut gérer ces sous-espaces non euclidiens tout en étant facile à mettre à jour et à interroger? J'ai également jeté un coup d'œil à FLANN , mais il n'était pas clair pour moi d'après leur documentation s'ils pouvaient gérer des sous-espaces non euclidiens.

giogadi
la source
Au fait, les voisins les plus proches sont également très bien (même préférés, si l'accélération est considérable)
Giogadi
1
Bien que vous ayez accepté une excellente réponse, il est généralement préférable d'attendre quelques jours avant d'accepter une réponse afin de ne pas décourager d'autres réponses qui pourraient offrir d'autres options.
Mark Booth
Merci Mark, je ne savais pas vraiment combien de temps attendre avant d'accepter la réponse.
giogadi

Réponses:

6

Vous avez raison de dire que les arbres kd ne fonctionnent généralement que dans de petits espaces métriques euclidiens. Mais, il y a beaucoup de travail pour les applications générales du plus proche voisin dans les espaces métriques (partout où vous pouvez définir une fonction de distance essentiellement).

Le travail classique porte sur les arbres à boules , qui ont ensuite été généralisés aux arbres métriques .

Il existe des travaux plus récents appelés arbres de couverture qui ont même du code sous GPL. Cela fait plus de deux ans que je souhaite étudier les caractéristiques de performance entre ces arbres et les arbres kd.

J'espère que cela correspond à votre application.

Chris Mansley
la source
Désolé de ne pas accepter; il suffit de suivre les conseils d'un autre commentateur pour donner à cette question quelques jours de plus pour "ragoût". J'ai vraiment trouvé votre réponse utile!
giogadi
Booo. Je rigole. Je suis juste heureux que vous ayez trouvé cela utile.
Chris Mansley