Real-time path planning in large dynamic environments based on a Voronoi diagram

Abstract

Planejamento de caminho é a habilidade de encontrar um caminho livre de obst áculos a partir de uma posição inicial arbitrária até uma posição nal dada. Uma limitação no momento de procurar este caminho, é o tamanho do ambiente onde a busca é realizada. Grandes ambientes aumentam o tempo computacional de algoritmos para um nível indesejado. Neste trabalho, abordamos o problema do planejamento de caminho em grandes ambientes. A nossa abordagem é baseada em uma implementação recente de um algoritmo de alta performance para criação de um diagrama de voronoi dinâmico para sítios complexos. Usamos este como uma estrutura para o planejamento de caminho. A nossa abordagem é capaz de produzir caminhos suaves com afastamento arbitrário. Mais do que isto, ela lida com obst áculos dinâmicos e permite espaço para comportamentos que mudem a direção de movimento. Nossos resultados mostram que é possível produzir, em tempo real, caminhos suaves com afastamento arbitrário em grandes ambientes dinâmicos.

Path planning is the ability to nd a path free of obstacles from an arbitrary initial position to a given nal position. One constraint when nding this path, is the size of the environment in which the search is made. Large environments increase the computational time of algorithms to an unwanted level. In this work, we address the problem of path planning in large environments. Our approach is based on a recent implementation of a high performance algorithm for the creation of a dynamic voronoi diagram for complex sites. We use it as the underlying structure for path planning. Our approach is able to produce smooth paths with arbitrary clearance.More than this, it handles dynamic obstacles and allow space for steering behaviors. Our results show that it is possible to produce, in real-time, smooth paths with arbitrary clearance in large dynamic environments.