FenixEdu™

Dissertação

{en_GB=Optimization of Landmark Placement for Robot Navigation} {} EVALUATED

Detalhes: {pt=O uso de marcadores como pontos de referência têm sido cada vez mais frequente em diversas aplicações incluindo sistemas de localização em espaços fechados, robótica e realidade aumentada. De um modo geral, a localização dos marcadores é crucial para um desempenho eficiente e confiável da aplicação em questão, como por exemplo, no caso de localização em espaços fechados, onde o erro de posicionamento aumenta de forma significativa devido a obstáculos e oclusões, frequentes nesse tipo de ambiente. Esta tese apresenta um método de optimização para colocação de marcadores em um determinado ambiente, que é representado no plano como um polígono, para fins de navegação de robots terrestres, aéreos ou mesmo subaquáticos munidos de sensores não omnidirecionais. Além disso, o método desenvolvido leva em consideração as dimensões dos marcadores. Em primeiro lugar, é resolvido um problema relaxado assumindo marcadores pontuais e evoluindo para uma abordagem realista considerando pontos de referência não pontuais. O método implementado consiste em duas fases: primeiro, um conjunto de intervalos candidatos a receber um marcador, são calculados por algoritmos de complexidade polinomial; segundo, a colocação dos marcadores é formulado como um problema de Programação Linear Inteira e por intermédio de um solver padrão, obtém-se uma solução globalmente óptima. Quando restringido ao mesmo período de tempo, o método desenvolvido obtém melhor cobertura do que um conjunto de meta-heurísticas considerados. Uma abordagem de optimização multi-critério permitiu estudar um possível trade-off entre a cobertura e o número de marcadores instalados. , en=Landmarks have an important role in a wide range of applications in different fields including indoor positioning, mobile robotics, and augmented reality. In the general case, the localization of the landmarks is crucial for efficient and reliable performance of the application, for instance, in the case of indoor positioning systems where the accuracy of the position estimation drops significantly in occlusion situations. In addition, the position estimation is affected by wheel slippage for ground vehicles and accumulative errors typical from inertial sensors used in aerial vehicles. This thesis presents an optimization method for landmarks placement in a polygonal environment, for ground, underwater, and aerial autonomous vehicles featured with non-omnidirectional sensors. In addition, the developed method considers the dimensions of the landmarks. Firstly, a relaxed problem is solved by assuming pointwise landmarks and evolving to a realistic approach considering non-pointwise landmarks. The implemented method consists of two phases: first, a set of candidate intervals in which a landmark can be placed, are computed by polynomial-time algorithms, and second, the landmarks placement problem is formulated as an Integer Linear Programming (ILP) and a globally optimal solution is obtained through a standard ILP solver. The method satisfies theoretical upper bounds established by Art Gallery Theorems. When constrained to the same period of time our method obtains better coverage than a set of meta-heuristic algorithms considered. A Multi-criteria optimization problem formulation allowed us to study a possible trade-off between the coverage and the number of landmarks.}
Keywords: {pt=Marcadores, Problema de Optimização, Programação Linear Inteira, Localização, en=Landmarks, Mobile robotics, Localization, optimization problem}

Discussão: setembro 30, 2021, 10:0