Métricas de rendimiento de algoritmos de búsqueda heurística en entornos de red

3 Entorno experimental y métricas de rendimiento.

Los algoritmos de búsqueda heurística desempeñan un papel importante en campos como la búsqueda de rutas robóticas, ya que determinan la ruta óptima dada una posición inicial y una posición objetivo. Los entornos basados en grid se utilizan comúnmente para representar escenarios ambientales del mundo real, donde se pueden implementar estos algoritmos, como en la navegación autónoma y la robótica [6]. En este estudio, analizamos exhaustivamente algoritmos de búsqueda heurística bien conocidos, a saber, D*, D* Lite, LPA*, LRTA*, RTAA* y ARA* en diferentes entornos de red. Utilizamos la heurística de distancia euclidiana para guiar la búsqueda de los algoritmos y evaluar el impacto de algunas características de la cuadrícula, como la densidad de obstáculos y el tamaño de la cuadrícula, en el rendimiento de los algoritmos.

En nuestro estudio, utilizamos entornos basados en grillas debido a su simplicidad y facilidad de control, además de ser comúnmente utilizados en tareas de planificación de rutas en la comunidad de investigación. Las cuadrículas están compuestas de celdas blancas, que representan estados transitables, mientras que las negras representan obstáculos no transitables. El agente de nuestra simulación puede moverse en ocho direcciones, con un coste igual a 1 para movimientos horizontales y verticales, y √ 2 para movimientos diagonales. Utilizamos dos tipos de entornos de red: entornos de red generados aleatoriamente y entornos de red personalizados.

Entornos basados en grillas generados aleatoriamente: Las grillas se caracterizan por tres parámetros:

tamaño de la cuadrícula (NxN), densidad de obstáculos y la distancia entre los estados de inicio y meta. Para investigar el impacto de cada parámetro en el rendimiento de los algoritmos de búsqueda, variamos cada parámetro de forma independiente mientras manteníamos los demás parámetros constantes. Las variaciones incluyeron variar el tamaño de la cuadrícula, variar la distancia de inicio a meta y variar las densidades de obstáculos. Para cada cuadrícula en una variación, generamos diez instancias aleatorias de los mismos parámetros de la cuadrícula (por ejemplo, una cuadrícula con 0,25 de densidad de obstáculos, tamaño 300x300 y 140 de distancia de inicio a meta, tiene diez instancias, que se generaron aleatoriamente).

Entorno de grid personalizado: Diseñado para simular escenarios más específicos. Estas cuadrículas tienen un tamaño fijo (71x31 unidades) y una posición fija tanto para el estado de inicio como para el de meta, y se dividieron en dos partes según su configuración de obstáculos:

• Configuración de paredes horizontales: para estos experimentos, agregamos paredes horizontales de medio ancho de cuadrícula cada 10 unidades de longitud de cuadrícula. Agregamos las paredes en dos orientaciones: una de izquierda a derecha y otra de derecha a izquierda en la cuadrícula recién generada.

• Configuración de longitud de pared horizontal: aquí, agregamos todas las paredes posibles que se pueden colocar dentro

la longitud de la cuadrícula, y cada vez que generamos una nueva cuadrícula aumentamos todas las longitudes de las paredes en 2 unidades.

Adoptamos estos dos entornos distintos para proporcionar un análisis exhaustivo, buscando revelar información matizada sobre el rendimiento del algoritmo de búsqueda en presencia de dos escenarios de obstáculos diferentes. En el primero, los obstáculos están dispersos aleatoriamente dentro de la cuadrícula, mientras que en el segundo, las estructuras en forma de pared aparecen como una masa de obstáculos conectados.

Para evaluar el rendimiento de los diferentes algoritmos de búsqueda utilizados en los experimentos, hemos seleccionado las siguientes métricas:

• Costo de la ruta: la métrica mide la longitud de la ruta o el número de acciones ejecutadas desde el inicio hasta el estado objetivo. Indica la calidad de la solución.

• Consumo de memoria: Mide la cantidad de memoria requerida para que el algoritmo encuentre una solución. Es relevante comprobar la escalabilidad del algoritmo y se mide en (KB).

• Tiempo de resolución: representa el tiempo total que tarda un algoritmo en encontrar una solución en (ms), medido en milisegundos (ms).

Llevamos a cabo nuestros experimentos en 27 núcleos Intel i9 a 3,30 GHz, equipados con 250 Gb de RAM y ejecutando Ubuntu Linux 22.04. Usando las siguientes configuraciones: Todos los algoritmos usaban la distancia euclidiana como función heurística. Para LRTA* y RTAA*, establecemos el número de nodos gastados en 250 para cada iteración. El algoritmo ARA* se ejecutó con un peso de 2,5 para la heurística. Ejecutamos cada algoritmo 100 veces en cada cuadrícula para tener en cuenta la aleatoriedad y garantizar la confiabilidad de los resultados.