Publicado em: 23/11/2011

Dissertação de Mestrado em Computação Gráfica

UNIVERSIDADE FEDERAL DO RIO GRANDE DO SUL
INSTITUTO DE INFORMÁTICA
PROGRAMA DE POS-GRADUAÇÃO EM COMPUTAÇÃO

——————————————————————

DEFESA DE DISSERTAÇÃO DE MESTRADO

Aluno: Leonardo Garcia Fischer

Orientadora: Profa. Dra. Luciana Porcher Nedel

Título: //”3DS-BVP: A Path Planner for Arbitrary Surfaces”

Linha de Pesquisa:Computação Gráfica

Data: 30/11/2011

Hora: 09h

Local: Sala 103 – Prédio 43413(67) – Instituto de Informática

Banca Examinadora:

Prof. Dr. Anderson Maciel (UFRGS)

Prof. Dr. Marcelo Walter (UFRGS)

Prof. Dr. Rafael Piccin Torchelsen (UFFS)

Presidente da Banca: Profa. Dra. Luciana Porcher Nedel

Abstract:

Efficient path planning methods are being explored along the years to allow the movement of autonomous robots or virtual agents. Basically these algorithms search the environment for a path with low probability of collision with obstacles that conduces the agent from an initial to a goal position. Although the first path planning algorithms to compute routes in graphs were presented more than 50 years ago, there is still a lot of effort into improving the current approaches.

The current path planning algorithms usually assume that the environment can be easily projected on a plane. There are also other algorithms that can easily deal with higher dimensional spaces. But a class of environments that cannot be easily treated by current algorithms is the one composed by arbitrary surfaces. These surfaces, with holes and bends for instance, cannot be directly projected on a plane. Because the path must be on the surface, on a given point the algorithm must compute a 2D path in a 3D surface, which is not trivial to map for a higher dimensional path planning algorithm.

This work presents a new technique for path planning on 3D surfaces called 3DS-BVP. This new path planner is based on a previous path planning algorithm for 2D environments. The former algorithm, called BVP-Path-Planner, uses Boundary Value Problems (BVP) and harmonic functions to generate potential fields. By following the gradient descent of these potential fields, it is possible to produce smooth paths free from local minima from any point of the environment to a given goal position.

Our algorithm generates a potential field directly on the 3D surface using a numerical method inspired on the one used by the BVP-Path-Planner. The 3DS-BVP works over complex surfaces of arbitrary genus or curvature, represented by a triangle mesh, without the need of 2D parametrizations.

Our results demonstrate that our technique can generate paths with similar quality as those generated by the BVP-Path-Planner in planar environments. The same algorithm is also able to generate paths in arbitrary surfaces at interactive frame rates.

Keywords: 3D path planning, motion planning, potential fields, Laplace’s equation