Navegação de múltiplos agentes sobre superfícies arbitrárias utilizando planarização dinâmica

Abstract

Path planning of multiple agents on arbitrary surfaces is a recent research topic. The quality of the paths generated to arbitrary surface is poor compared to method proposed to planar surfaces. A major limitation to improve the quality is related to the computational cost of computing distances over arbitrary surface. Traditional path planning algorithms designed to planar surface use Euclidian distance with has constant computational cost, in the other hand, arbitrary surfaces require Geodesic distances with in turn has a considerable higher computational cost. This project proposes novel dynamic planarization around each agent with will allow the use of Eucledian distance during the local navigation, that way, classic path planning algorithms designed for planar surface can be used over arbitrary surface. The main benefit is the increased quality of paths for agents. The proposed solution uses geodesic distance in the global navigation, responsible for defining the initial path. However, for the local navigation, or obstacle avoidance, our solution allows the use of classic techniques. To allow the use of these methods we propose a planarization of the surface adjacent to the agent in order to replace the use of geodesic distance with Euclidean distance in the local navigation. Additionally, the algorithm is massively parallel and implemented in the CPU and GPU to explore the best features of each.