Investigadores de China desarrollan iLLM-A* para planificar rutas en mapas extensos con mil veces más velocidad
Un nuevo algoritmo innovador combina modelos de lenguaje y técnicas avanzadas para mejorar radicalmente la planificación de rutas en mapas extenso.
Investigadores de la Universidad Nacional de Defensa Tecnológica en China han desarrollado un nuevo algoritmo llamado iLLM-A*, que combina modelos de lenguaje con una versión optimizada del algoritmo A* para la planificación de rutas en mapas de gran escala. Este método promete reducir en más de mil veces el tiempo de búsqueda en comparación con técnicas existentes, lo que podría revolucionar áreas como la robótica autónoma, la logística, las simulaciones y los videojuegos.
La planificación de rutas en entornos extensos y basados en cuadrículas representa un reto significativo para algoritmos tradicionales como A* y Dijkstra, cuyos costes de tiempo y memoria crecen de forma desproporcionada con el tamaño del mapa. Para abordar esta problemática, iLLM-A* introduce un enfoque híbrido que mejora sustancialmente la eficiencia sin comprometer la calidad de las rutas generadas.
El método analiza las limitaciones del enfoque anterior, LLM-A*, que utiliza un modelo de lenguaje grande (LLM) para generar puntos de ruta, y busca optimizar varios aspectos. Entre las innovaciones, se implementa un proceso de aprendizaje dinámico mediante una base de datos de ejemplos que permite ajustar de forma iterativa la generación de puntos de ruta. Además, se incorpora una regla de selección que limita el número de puntos usados en la búsqueda a los dos más cercanos al punto de inicio cuando se generan más de dos, reduciendo así la carga computacional.
Las pruebas realizadas en diferentes tamaños de mapas (desde N=50 hasta N=450) demostraron que iLLM-A* supera significativamente a otros métodos como A*, Opt-A* y LLM-A*. En concreto, logró una aceleración media de mil veces en la búsqueda del camino más corto en comparación con LLM-A*, alcanzando picos de hasta 2.350 veces en ciertos casos. Además, el consumo de memoria se redujo en casi un 60%, llegando solo a 3,62 MB en mapas de tamaño máximo, frente a los 28,67 MB que requiere A* optimizado.
La calidad de las rutas también mejoró, con una desviación menor respecto a la longitud óptima (104,39% frente a 107,94%) y una mayor estabilidad en los resultados. Estas mejoras hacen que el algoritmo sea especialmente útil en aplicaciones que demandan una planificación rápida en mapas extensos y complejos, como la navegación de robots en logística, la gestión en videojuegos de gran escala o simulaciones en sistemas digitales. La innovación representa un avance significativo hacia soluciones de planificación de rutas altamente eficientes y viables para uso en tiempo real en diversos campos tecnológicos.