Estructura de datos del vecino más cercano para el espacio de configuración no euclidiana

15

Estoy tratando de implementar una estructura de vecino más cercano para usar en un planificador de movimiento RRT. Para hacerlo mejor que una búsqueda lineal de fuerza bruta más cercana al vecino, me gustaría implementar algo como un árbol kd. Sin embargo, parece que la implementación clásica del árbol kd supone que cada dimensión del espacio se puede dividir en "izquierda" y "derecha". Esta noción no parece aplicarse a espacios no euclidianos como SO (2), por ejemplo.

Estoy trabajando con un brazo manipulador en serie con enlaces totalmente rotativos, lo que significa que cada dimensión del espacio de configuración del robot es SO (2) y, por lo tanto, no euclidiana. ¿Se puede modificar el algoritmo kd-tree para manejar este tipo de subespacios? Si no es así, ¿hay otra estructura de vecino más cercano que pueda manejar estos subespacios no euclidianos sin dejar de ser fácil de actualizar y consultar? También eché un vistazo a FLANN , pero de su documentación no estaba claro si pueden manejar subespacios no euclidianos.

giogadi
fuente
Por cierto, los vecinos más cercanos aproximados también están bien (incluso preferidos, si la aceleración es considerable)
giogadi
1
Si bien ha aceptado una respuesta excelente, generalmente es una buena idea esperar unos días antes de aceptar una respuesta para no desalentar las respuestas adicionales que podrían ofrecer otras opciones.
Mark Booth
Gracias Mark, en realidad no estaba seguro de cuánto esperar antes de aceptar la respuesta.
giogadi

Respuestas:

6

Tiene razón en que los árboles kd generalmente solo funcionan en espacios métricos euclidianos pequeños. Pero, hay mucho trabajo para las aplicaciones vecinas generales más cercanas en espacios métricos (en cualquier lugar donde pueda definir una función de distancia esencialmente).

El trabajo clásico es sobre árboles de bolas , que luego se generalizaron a árboles métricos .

Hay algunos trabajos más nuevos llamados árboles de cobertura que incluso tienen código GPL. He querido analizar las características de rendimiento entre estos árboles y árboles kd durante más de dos años.

Con suerte, eso se ajusta a su aplicación.

Chris Mansley
fuente
Perdón por no aceptar; simplemente siguiendo el consejo de otro comentarista para darle a esta pregunta unos días más para "guisar". Sin embargo, ¡realmente encontré útil tu respuesta!
giogadi
Booo Es una broma. Estoy feliz de que hayas encontrado esto útil.
Chris Mansley