Investigadores en planificación de movimientos para robótica enfrentan un cuello de botella recurrente: validar configuraciones de robots frente a entornos percibidos como nubes de puntos. La validación equivale a comprobar colisiones esféricas contra miles o millones de puntos, y acelerar esa operación es clave para planificar a frecuencia de bucle de control.
Hace dos años, el autor Clayton W. Ramsey propuso CAPT, un k-d tree modificado con búsqueda paralela SIMD que evitaba retrocesos. Su gran debilidad era el tiempo y la memoria de construcción en nubes densas, con escalado O(n²) cuando los duplicados en las hojas dominaban la estructura.
En una reciente conferencia en Viena, Ching Chen y Tsung-Tai Yeh publicaron MVT (Multilevel Voxel Table), que reemplaza el árbol de partición del espacio por una rejilla tridimensional dispersa organizada en un árbol de tres capas segmentado por dimensión. La ventaja es doble: el vóxel de cualquier esfera consultada se calcula con aritmética simple, y no requiere duplicar puntos. La búsqueda se vectoriza con SIMD, manteniendo la aceleración paralela del CAPT sin sus costes.
Ramsey ha publicado una implementación en Rust (paquete mvtable) que simplifica la estructura original almacenando todas las filas en un Box<[]>, e introduce una variante MutableMvt con un coste aproximado de 2× en tamaño y 1,5× en construcción. También realiza un barrido empírico del ancho de vóxel sobre los robots Fetch, Panda, UR5 y Baxter, y descubre que el óptimo se sitúa siempre entre 10 y 20 cm, mientras que la recomendación original de los autores resulta hasta 20 veces más lenta en Baxter.