Autores:  (1) Aya Kherrour, Departamento de Engenharia da Informação e Ciência da Computação da Universidade de Trento;  (2) Marco Robol, Departamento de Engenharia da Informação e Ciência da Computação da Universidade de Trento;  (3) Marco Roveri, Departamento de Engenharia da Informação e Ciência da Computação da Universidade de Trento;  (4) Paolo Giorgini, Departamento de Engenharia da Informação e Ciência da Computação da Universidade de Trento.  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.    As grades são caracterizadas por três parâmetros: Ambientes baseados em grade gerados aleatoriamente:  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).    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: Ambiente de grade personalizado:  •   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 de parede horizontal:  •   Aqui adicionamos todas as paredes possíveis que podem ser colocadas dentro Configuração do comprimento da parede horizontal:  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:  •   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. Custo do caminho:  •   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). Consumo de memória:  •   Representa o tempo total que um algoritmo leva para encontrar uma solução em (ms), medido em milissegundos (ms). Tempo de Resolução:  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.  Este artigo está   sob licença CC 4.0. disponível no arxiv

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

EScholar Technologies

EScholar

Este áudio é produzido no idioma original da história!

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

About Author

COMENTARIOS

Rótulos

ESTE ARTIGO FOI APRESENTADO EM

Related Stories

O guia completo para uma migração bem-sucedida para a nuvem: estratégias e práticas recomendadas

Criando produtos criptográficos centrados no usuário: a importância do feedback do cliente

Toque para ganhar: Telegram pode integrar os próximos 10 bilhões de usuários criptográficos antes de Solana

Vazamento do prompt do sistema Claude Sonnet 3.5: uma análise forense

O guia completo para uma migração bem-sucedida para a nuvem: estratégias e práticas recomendadas

Criando produtos criptográficos centrados no usuário: a importância do feedback do cliente

Toque para ganhar: Telegram pode integrar os próximos 10 bilhões de usuários criptográficos antes de Solana

Vazamento do prompt do sistema Claude Sonnet 3.5: uma análise forense

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps