Autores:  (1) Aya Kherrour, Departamento de Ingeniería de la Información y Ciencias de la Computación de la Universidad de Trento;  (2) Marco Robol, Departamento de Ingeniería de la Información y Ciencias de la Computación de la Universidad de Trento;  (3) Marco Roveri, Departamento de Ingeniería de la Información y Ciencias de la Computación de la Universidad de Trento;  (4) Paolo Giorgini, Departamento de Ingeniería de la Información y Ciencias de la Computación de la Universidad de Trento.  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.    Las grillas se caracterizan por tres parámetros: Entornos basados en grillas generados aleatoriamente:  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).    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: Entorno de grid personalizado:  •   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 paredes horizontales:  •   aquí, agregamos todas las paredes posibles que se pueden colocar dentro Configuración de longitud de pared horizontal:  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:  •   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. Costo de la ruta:  •   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). Consumo de memoria:  •   representa el tiempo total que tarda un algoritmo en encontrar una solución en (ms), medido en milisegundos (ms). Tiempo de resolución:  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.  Este documento está   bajo licencia CC 4.0. disponible en arxiv

Part of HackerNoon's growing list of open-source research papers, promoting free access to academic material.

EScholar Technologies

EScholar

Este audio es producido en el idioma original de la historia!

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

About Author

COMENTARIOS

ETIQUETAS

ESTE ARTÍCULO FUE PRESENTADO EN

Related Stories

Creación de productos criptográficos centrados en el usuario: la importancia de los comentarios de los clientes

¿Quieres ganar un concurso de redacción de HackerNoon? Esto es lo que recomiendan los ganadores del concurso #crypto-api

Crecimiento de las criptomonedas: creación de perfiles de usuarios eficaces

Nómadas digitales escuchen: lo que necesitan saber sobre la nueva visa DTV de Tailandia

Creación de productos criptográficos centrados en el usuario: la importancia de los comentarios de los clientes

¿Quieres ganar un concurso de redacción de HackerNoon? Esto es lo que recomiendan los ganadores del concurso #crypto-api

Crecimiento de las criptomonedas: creación de perfiles de usuarios eficaces

Nómadas digitales escuchen: lo que necesitan saber sobre la nueva visa DTV de Tailandia

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps