The trend of automation in industry, and in the society in general, is something that probably all of us have noticed. The mining industry is no exception to this trend, and there exists a vision of having completely automated mines with all processes monitored and controlled through a higher level optimization goal. For this vision, access to a reliable positioning system has been identified a prerequisite. Underground mines posses extraordinary premises for localization, due to the harsh, unstructured and ever changing environment, where existing localization solutions struggle with accuracy and reliability over time. 

This thesis addresses the problem of achieving accurate, robust and consistent position estimates for long-term autonomy of vehicles operating in an underground mining environment. The focus is on onboard positioning solutions utilizing sensor fusion within the probabilistic filtering framework, with extra emphasis on the characteristics of lidar data. Contributions are in the areas of improved state estimation algorithms, more efficient lidar data processing and development of models for changing environments. The problem descriptions and ideas in this thesis are sprung from underground localization issues, but many of the resulting solutions and methods are valid beyond this application. 

In this thesis, internal localization algorithms and data processing techniques are analyzed in detail. The effects of tuning the parameters in an unscented Kalman filter are examined and guidelines for choosing suitable values are suggested. Proper parameter values are shown to substantially improve the position estimates for the underground application. Robust and efficient processing of lidar data is explored both through analysis of the information contribution of individual laser rays, and through preprocessing in terms of feature extraction. Methods suitable for available hardware are suggested, and it is shown how it is possible to maintain consistency in the state estimates with less computations. 

Changes in the environment can be devastating for a localization system when characteristics of the observations no longer matches the provided map. One way to manage this is to extend the localization problem to simultaneous localization and mapping (slam). In its standard formulation, slam assumes a truly static surrounding. In this thesis a feature based multi-hypothesis map representation is developed that allows encoding of changes in the environment. The representation is verified to perform well for localization in scenarios where landmarks can attain one of many possible positions. Automatic creation of such maps are suggested with methods completely integrated with the slam framework. This results in a multi-hypothesis slam concept that can discover and adapt to changes in the operation area while at the same time producing consistent state estimates. 

This thesis provides general insights in lidar data processing and state estimation in changing environments. For the underground mine application specifically, different methods presented in this thesis target different aspects of the higher goal of achieving robust and accurate position estimates. Together they present a collective view of how to design localization systems that produce reliable estimates for underground mining environments. 

The mining industry is currently facing a transition from manually operated vehicles to remote or semi-automated vehicles. The vision is fully autonomous vehicles being part of a larger fleet, with humans only setting high-level goals for the autonomous fleet to execute in an optimal way. An enabler for this vision is the presence of robust, reliable and highly accurate localization. This is a requirement for having areas in a mine with mixed autonomous vehicles, manually operated vehicles, and unprotected personnel. The robustness of the system is important from a safety as well as a productivity perspective. When every vehicle in the fleet is connected, an uncertain position of one vehicle can result in the whole fleet begin halted for safety reasons.

Providing reliable positions is not trivial in underground mine environments, where access to global satellite based navigation systems is denied. Due to the harsh and dynamically changing environment, onboard positioning solutions are preferred over systems utilizing external infrastructure. The focus of this thesis is localization systems relying only on sensors mounted on the vehicle, e.g., odometers, inertial measurement units, and 2D LIDAR sensors. The localization methods are based on the Bayesian filtering framework and estimate the distribution of the position in the reference frame of a predefined map covering the operation area. This thesis presents research where the properties of 2D LIDAR data, and specifically characteristics when obtained in an underground mine, are considered to produce position estimates that are robust, reliable, and accurate.

First, guidelines are provided for how to tune the design parameters associated with the unscented Kalman filter (UKF). The UKF is an algorithm designed for nonlinear dynamical systems, applicable to this particular positioning problem. There exists no general guidelines for how to choose the parameter values, and using the standard values suggested in the literature result in unreliable estimates in the considered application. Results show that a proper parameter setup substantially improves the performance of this algorithm.

Next, strategies are developed to use only a subset of available measurements without losing quality in the position estimates. LIDAR sensors typically produce large amounts of data, and demanding real-time positioning information limits how much data the system can process. By analyzing the information contribution from each individual laser ray in a complete LIDAR scan, a subset is selected by maximizing the information content. It is shown how 80% of available LIDAR measurements can be dropped without significant loss of accuracy.

Last, the problem of robustness in non-static environments is addressed. By extracting features from the LIDAR data, a computationally tractable localization method, resilient to errors in the map, is obtained. Moving objects, and tunnels being extended or closed, result in a map not corresponding to the LIDAR observations. State-of-the-art feature extraction methods for 2D LIDAR data are identified, and a localization algorithm is defined where features found in LIDAR data are matched to features extracted from the map. Experiments show that regions of the map containing errors are automatically ignored since no matching features are found in the LIDAR data, resulting in more robust position estimates.

Long-term autonomy of robots requires localization in an inevitably changing environment, where the robots' knowledge about the surroundings are more or less uncertain. Inspired by methods in target tracking, this paper proposes a feature based multi-hypothesis map representation to provide robust localization under these conditions. It is derived how this representation can be used to obtain consistent position estimates while at the same time providing up-to-date map information to be shared by cooperative robots or for visual presentation. Simulations are performed that conceptually highlights the benefit of the developed solution in an environment where uniquely identifiable landmarks are moved between discrete positions. This relates to a real world scenario where a robot moves in a corridor with office doors opened or closed at different times. 

A static world assumption is often used when considering the simultaneous localization and mapping (SLAM) problem. In reality, especially when long-term autonomy is the objective, this is not a valid assumption. This paper studies a scenario where landmarks can occupy multiple discrete positions at different points in time, where each possible position is added to a multi-hypothesis map representation. A selector-mixture distribution is introduced and used in the observation model. Each landmark position hypothesis is associated with one component in the mixture. The landmark movements are modeled by a discrete Markov chain and the Monte Carlo tree search algorithm is suggested to be used as component selector. The non-static environment model is further incorporated into the factor graph formulation of the SLAM problem and is solved by iterating between estimating discrete variables with a component selector and optimizing continuous variables with an efficient state-of-the-art nonlinear least squares SLAM solver. The proposed non-static SLAM system is validated in numerical simulation and with a publicly available dataset by showing that a non-static environment can successfully be navigated.

A static world assumption is often used when considering the simultaneous localization and mapping (SLAM) problem. In reality, especially when long-term autonomy is the objective, this is not valid. This paper studies a scenario where uniquely identifiable landmarks can attend multiple discrete positions, not known a priori . Based on a feature based multi-hypothesis map representation, a multi-hypothesis SLAM algorithm is developed inspired by target tracking theory. The creation of such a map is merged into the SLAM framework allowing any available SLAM method to solve the underlying mapping and localization problem for each hypothesis. A recursively updated hypothesis score allows for hypothesis rejection and prevents exponential growth in the number of hypotheses. The developed method is evaluated in an underground mine application, where physical barriers can be moved in between multiple distinct positions. Simulations are conducted in this environment showing the benefits of the multi-hypothesis approach compared to executing a standard SLAM algorithm. Practical considerations as well as suitable approximations are elaborated upon and experiments on real data further validates the simulated results and show that the multi-hypothesis approach has similar performance in reality as in simulation.

Lidar-based positioning in a 2D map is analyzed as a method to provide a robust, high accuracy, and infrastructure-free positioning system required by the automation development in underground mining. Expressions are derived that highlight separate information contributions to the obtained position accuracy. This is used to develop two new methods that efficiently select which subset of available lidar rays to use to reduce the computational complexity and allow for online processing with minimal loss of accuracy. The results are verified in simulations of a mid-articulated underground loader in a mine. The methods are shown to be able to reduce the number of rays needed without considerably affecting the performance, and to be competitive with currently used methods. Furthermore, simulations highlight the effects of errors in the map and other map properties, and how imperfect maps degrades the performance of different selection strategies.

Robust and highly accurate position estimation in underground mines is investigated by considering a vehicle equipped with 2D laser scanners. A survey of available methods to process data from such sensors is performed with focus on feature extraction methods. Pros and cons of the usage of different methods for the positioning application with 2D laser data are highlighted, and suitable methods are identified. Three state-of-the-art feature extraction methods are adapted to the scenario of positioning in a predefined map and the methods are evaluated through experiments conducted in a simulated underground mine environment. Results indicate that feature extraction methods perform in parity with the method of matching each ray individually to the map, and better than the point cloud scan matching method of a pure ICP, assuming a highly accurate map is available. Furthermore, experiments show that feature extraction methods more robustly handle imperfections or regions of errors in the map by automatically disregarding these regions.

The unscented Kalman filter (UKF) is a method to solve nonlinear dynamic filtering problems, which internally uses the unscented transform (UT). The behavior of the UT is controlled by design parameters, seldom changed from the values suggested in early UT/UKF publications. Despite the knowledge that the UKF can perform poorly when the parameters are improperly chosen, there exist no wide spread intuitive guidelines for how to tune them. With an application relevant example, this paper shows that standard parameter values can be far from optimal. By analyzing how each parameter affects the resulting UT estimate, guidelines for how the parameter values should be chosen are developed. The guidelines are verified both in simulations and on real data collected in an underground mine. A strategy to automatically tune the parameters in a state estimation setting is presented, resulting in parameter values inline with developed guidelines.