Caminhos mais curtos em localização em espaços fechados

Dissertação de Mestrado em Matemática apresentada à Faculdade de Ciências e Tecnologia da Universidade de CoimbraOs sistemas de posicionamento global, basedos na navegação por satélites, têm sido amplamente utilizados para localização no exterior. Em espaços fechados estes sistemas não são operacionais, no entanto, a localização no interior de edifícios é um problema com aplicações em áreas diversas, tais como a saúde ou o turismo, e em desenvolvimento. Este trabalho integra um projeto para implementação de um sistema de navegação em edifícios, baseado na rede sem fios pré-existente. Em geral os algoritmos que determinam a localização nestas condições são afetados pelo ruído que resulta da oscilação do sinal emitido pelos dispositivos eletrónicos. Pretende-se apresentar uma ferramenta complementar a estes algoritmos, que permita reduzir possíveis erros produzidos na localização. O objetivo da ferramenta é calcular limites inferiores para o tempo que um indivíduo precisa para se deslocar entre dois pontos de um edifício, como forma de eliminar localizações erradas. Este cálculo baseia-se na representação do edifício por um grafo, e no desenvolvimento de um método para determinar o caminho mais curto entre quaisquer dois pontos do edifício. A escolha do método a utilizar é baseada em testes computacionais realizados em problemas gerados aleatoriamente.The global positioning systems, based on satellite navigation, have been widely used for outdoor location. Such systems are not reliable when operating indoors, however, the location inside buildings is a timely problem with applications in many fields, such as health and tourism, which has been attracting the attention of researchers and practitioners. This work is part of a project to implement a navigation system within buildings, based on a pre-existing wireless network. The algorithms which determine the position under these conditions are often affected by noise, resulting from the oscillation of the signal emitted by the electronic devices. It is intended to present a complementary tool to these algorithms, which can reduce possible errors produced by the location. The purpose of the tool is to compute lower bounds for the time that a person needs to move between two points of a building, in order to eliminate wrong locations. This calculation is based on the representation of the building by a graph, and the development of a method for finding the shortest path between any two points in the building. The choice of the method to use is supported by tests on randomly generated problems