Planejamento de caminhos 3D em ambiente estático

Abstract

Resumo: O Planejamento de caminhos no R3 é um problema computacional que tem despertado o interesse dos pesquisadores por sua vasta aplicabilidade em otimização. Dados um ambiente 3D com obstáculos, um ponto origem e um ponto destino, a resposta esperada é se existe algum caminho, livre de obstáculos, entre origem e destino e havendo, qual dos caminhos minimiza custo. Este problema pertence à classe de complexidade computacional NP-Difícil. A presente pesquisa se propõe a estudar este problema e propor técnicas que permitam obter o caminho mínimo em tempo computacional razoável. A pesquisa consiste em elaborar algoritmos, propor otimizações, analisar seus desempenhos e qualidade dos seus resultados na intenção de, pelo menos, se aproximar do ótimo em tempo polinomial. Apesar de se vislumbrar inúmeras aplicações práticas, a pesquisa se atém apenas a propor variações do algoritmo planejador que recebe dados do ambiente e retorna um caminho a ser seguido, ignorando como os dados de entrada foram obtidos e como os dados de saída se converterão em ações posteriormente. Este trabalho propõe com otimizações simples que em teoria reduzem drasticamente o custo computacional para este problema no caso geral.

Abstract: Path planning inR3 is a computational problem that has aroused the interest of researchers due to its wide applicability in optimization. Given a 3D environment with obstacles, a source point and a target point, the expected answer is whether there is a path, free of obstacles, between source and target and if so, which path minimizes cost. This problem belongs to the NP-Hard computational complexity class. This research proposes to study this problem and propose techniques that allow obtaining the shortest path in reasonable computational time. The research consists of developing algorithms, proposing optimizations, analyzing their performance and the quality of their results with the intention of at least approaching the optimum in polynomial time. Despite envisioning numerous practical applications, the research just sticks to proposing variations of the planner algorithm that receives data from the environment and returns a path to be followed, ignoring how the input data were obtained and how the output data will be converted into actions posteriorly. This work proposes simple optimizations that in theory drastically reduce the computational cost for this problem in the general case.