Métricas de desempenho de algoritmos de pesquisa heurística em ambientes de grade

3 Ambiente experimental e métricas de desempenho

Algoritmos de busca heurística desempenham um papel importante em campos como pathfinding robótico, pois determinam o caminho ideal dada uma posição inicial e uma posição final. Ambientes baseados em grade são comumente usados para representar cenários ambientais do mundo real, onde esses algoritmos podem ser implementados, como em navegação autônoma e robótica [6]. Neste estudo, analisamos de forma abrangente algoritmos de busca heurística bem conhecidos, nomeadamente D*, D* Lite, LPA*, LRTA*, RTAA* e ARA* em diferentes ambientes de grade. Utilizamos a heurística da distância euclidiana para orientar a busca dos algoritmos e avaliar o impacto de algumas características da grade, como a densidade dos obstáculos e o tamanho da grade, no desempenho dos algoritmos.

Em nosso estudo, utilizamos ambientes baseados em grade devido à sua simplicidade e facilidade de controle, além de serem comumente utilizados em tarefas de planejamento de caminhos na comunidade de pesquisa. As grades são compostas por células brancas, representando estados transponíveis, enquanto as pretas representam obstáculos não transponíveis. O agente em nossa simulação pode se mover em oito direções, com custo igual a 1 para movimentos horizontais e verticais, e √ 2 para movimentos diagonais. Usamos dois tipos de ambientes de grade: ambientes de grade gerados aleatoriamente e ambientes de grade personalizados.

Ambientes baseados em grade gerados aleatoriamente: As grades são caracterizadas por três parâmetros:

tamanho da grade (NxN), densidade do obstáculo e distância entre o início e o estado final. Para investigar o impacto de cada parâmetro no desempenho dos algoritmos de busca, variamos cada parâmetro independentemente, mantendo os demais parâmetros constantes. As variações incluíram variar o tamanho da grade, variar a distância do início ao gol e variar as densidades dos obstáculos. Para cada grade em uma variação, geramos dez instâncias aleatórias dos mesmos parâmetros da grade (por exemplo, uma grade com 0,25 de densidade de obstáculo, tamanho 300x300 e 140 de distância do início ao objetivo, tem dez instâncias, que foram geradas aleatoriamente).

Ambiente de grade personalizado: Projetado para simular cenários mais específicos. Essas grades têm tamanho fixo (71x31 unidades) e posição fixa para os estados inicial e final, e foram divididas em duas partes com base na configuração dos obstáculos:

• Configuração de parede horizontal: Para estes experimentos, adicionamos paredes horizontais com meia largura da grade a cada 10 unidades de comprimento da grade. Adicionamos as paredes em duas orientações: uma vez da esquerda para a direita e uma vez da direita para a esquerda na grade recém-gerada.

• Configuração do comprimento da parede horizontal: Aqui adicionamos todas as paredes possíveis que podem ser colocadas dentro

o comprimento da grade, e cada vez que geramos uma nova grade aumentamos todos os comprimentos das paredes em 2 unidades.

Adotamos esses dois ambientes distintos para fornecer uma análise completa, buscando revelar insights diferenciados sobre o desempenho do algoritmo de busca na presença de dois cenários dificultadores diferentes. No primeiro, os obstáculos estão espalhados aleatoriamente dentro da grade, enquanto no segundo, as estruturas semelhantes a paredes aparecem como uma massa de obstáculos conectados.

Para avaliar o desempenho dos diferentes algoritmos de busca utilizados nos experimentos, selecionamos as seguintes métricas:

• Custo do caminho: A métrica mede o comprimento do caminho ou o número de ações executadas desde o início até o estado final. Indica a qualidade da solução.

• Consumo de memória: Mede a quantidade de memória necessária para o algoritmo encontrar uma solução. É relevante verificar a escalabilidade do algoritmo, e ela é medida em (KB).

• Tempo de Resolução: Representa o tempo total que um algoritmo leva para encontrar uma solução em (ms), medido em milissegundos (ms).

Realizamos nossos experimentos em 27 núcleos Intel i9 de 3,30 GHz, equipados com 250 Gb de RAM e rodando Ubuntu Linux 22.04. Usando as seguintes configurações: Todos os algoritmos usaram a distância euclidiana como função heurística. Para LRTA* e RTAA*, definimos o número de nós gastos como 250 para cada iteração. O algoritmo ARA* foi executado com peso 2,5 para a heurística. Executamos cada algoritmo 100 vezes em cada grade para levar em conta a aleatoriedade e garantir a confiabilidade dos resultados.