Composição de mapas planares e planejamento de rotas aplicados à navegação de robôs móveis e linhas de transmissão

Abstract

Finding the shortest path between two points in thematic maps is a common problem. However, this planning can be slightly complex, taking into account the large number of variables and constraints of the problem. This thesis proposes the use of map overlay and optimization techniques to find the optimal route approximation, considering all necessary topological information and constraints. Furthermore, a post-processing technique to refine the solution is shown. The problem can be modeled by a set of thematic maps without loss of generality. Cost functions are assigned to each region in order to estimate the difficulty to transpose that region. The map overlay technique is used to couple all the thematic map information. This technique produces a combined map which contains all the information of each map. A triangle discretization has been used to decompose the map in convex regions. After the discretization, the vertices of the triangles are the nodes of the search graph. The graph is constructed taking into account the distance between nodes. This distance is defined as the minimal number of edges between the nodes. One can assure the best solution only considering all possible connections. However, this addresses the worst case and the computational cost is prohibitive in most cases. A post-processing technique has been proposed to find good solutions without a significative increasing of considered connections. To achieve the initial solution path, the Dijkstra algorithm has been used. Two route planning problems are addressed in this work, the robot motion planning in outdoor environments and the design of routes for transmission lines. In both cases, practical systems have been used to test the developed method.