FPS: Algoritmo de Planejamento de Caminho Rápido Baseado em Gráfico de Visibilidade Esparsa e Busca em Largura Bidirecional

A maioria dos algoritmos de planejamento usados é baseada em mapas de grade de ocupação, mas em situações complicadas, os mapas de grade de ocupação têm uma sobrecarga de busca significativa. Este artigo propõe um planejador de caminhos baseado no gráfico de visibilidade (g-graph) para o robô móvel que utiliza métodos esparsos para agilizar e simplificar a construção do g-graph. Primeiramente, a estrutura de grade complementar é projetada para reduzir os custos de iteração de atualização do gráfico durante o processo de coleta de dados em cada quadro de dados. Em segundo lugar, uma abordagem de filtro baseada no comprimento da aresta e no número de vértices do contorno do obstáculo é proposta para reduzir nós e arestas redundantes no g-graph. Em terceiro lugar, uma busca em largura bidirecional é combinada ao processo de busca de caminho no algoritmo proposto de planejador de caminho rápido para reduzir o desperdício na exploração do espaço. Finalmente, os resultados da simulação indicam que o planejador de g-graph esparso proposto pode melhorar significativamente a eficiência de construção do g-graph e reduzir o tempo de busca de caminhos. Em ambientes altamente convolutos desconhecidos ou parcialmente conhecidos, nosso método é 40% mais rápido que o Planejador FAR e produz caminhos 25% mais curtos do que ele. Além disso, o experimento físico mostra que o planejador de caminhos proposto é mais rápido que o Planejador FAR tanto no processo de atualização do g-graph quanto no processo a laser. O método proposto neste artigo apresenta desempenho mais rápido na busca de caminhos do que o método convencional baseado na grade de ocupação.