On the application of graph neural networks for indoor positioning systems

Abstract

Due to the inability of GPS (Global Positioning System) or other GNSS (Global Navigation Satellite System) methods to provide satisfactory precision for the indoor localization scenario, indoor positioning systems resort to other signals already available on-site, typically Wi-Fi given its ubiquity. However, instead of relying on an error-prone propagation model as in ranging methods, the popular fingerprinting positioning technique considers a more direct data-driven approach to the problem. First of all, the area of interest is divided into zones, and then a machine learning algorithm is trained to map between, for instance, power measurements from Access Points (APs) to the localization zone, thus effectively turning the problem into a classification one. However, although the positioning problem is a geometrical one, virtually all methods proposed in the literature disregard the underlying structure of the data, using generic machine learning algorithms. In this work we consider instead a graph-based learning method, Graph Neural Networks, a paradigm that has emerged in the last few years and constitutes the state-of-the-art for several problems. After presenting the pertinent theoretical background, we discuss two possibilities to construct the underlying graph for the positioning problem. We then perform a thorough evaluation of both possibilities, and compare it with some of the most popular machine learning alternatives. The main conclusion is that these graph-based methods obtain systematically better results, particularly with regards to practical aspects (e.g. gracefully tolerating faulty APs), which makes them a serious candidate to consider when deploying positioning systems.

Debido a la incapacidad del GPS (Global Positioning System o Sistema de Posicionamiento Global) o de otros métodos de navegación por satélite (GNSS por sus siglas en inglés) de proporcionar un posicionamiento en espacios interiores con suficiente precisión, se suele recurrir a otras señales ya disponibles en el lugar, típicamente Wi-Fi por su gran adopción. Existen diversas técnincas que utilizan la señal de Wi-Fi para realizar el posicionamiento modelando la propagación de la señal para alcanzar el objetivo. Sin embargo, debido a su alta complejidad, estos modelos de propagación son propensos a errores. Una alternativa que se popularizó es el posicionamiento en base a huellas (fingerprinting) que considera un enfoque basado en datos más directo al problema. El método consiste en dividir el área de interés en zonas y entrenar un algoritmo de aprendizaje automático para establecer una relación entre, por ejemplo, las mediciones de potencia de los puntos de acceso (Access Points o APs) y la zona de localización, convirtiéndose así en un problema de clasificación. Si bien el problema de posicionamiento es en última instancia un problema geométrico, prácticamente todos los métodos propuestos en la literatura ignoran la estructura subyacente de los datos, utilizando para su resolución algoritmos genéricos de aprendizaje automático. Este trabajo propone utilizar un método de aprendizaje basado en grafos (Graph Neural Networks o GNN), un paradigma que ha surgido en los últimos años y que constituye el estado del arte para varios problemas. Tras presentar el marco teórico pertinente, discutimos dos posibilidades para construir el grafo subyacente al problema de posicionamiento. A continuación realizamos una evaluación exhaustiva de ambas posibilidades y las comparamos con algunas de las alternativas más populares de aprendizaje automático. La principal conclusión es que estos métodos basados en grafos obtienen sistemáticamente mejores resultados, especialmente en lo que respecta a los aspectos prácticos (por ejemplo, tolerar fallas en APs), lo que los convierte en excelentes candidatos a considerar a la hora de diseñar e implementar sistemas de posicionamiento.