Global Localization of Unmanned Ground Vehicles Using Swarm Intelligence and Evolutionary Algorithms

Mobile robot localization is a complex task, specially in unstructured indoor environments, due to noise and wrong scan-to-map association. The localization procedure becomes critical when the vehicle has low confidence about its last pose estimate, situation that requires a global localization procedure. An intuitive approach to solve the Global Localization Problem (GLP) is to distribute several pose hypotheses all over the map and select the most likely one according to an optimization heuristic such as Monte Carlo, Swarm Intelligence or Evolutionary Algorithm. However, hardware limitations and environment characteristics may affect the localization efficacy. Furthermore, we found relatively few studies exploring the effectiveness and the computing cost of different localization methods under different scenarios e.g. offices, corridors and big warehouses. In this work, we analyze different global localization methods based on multi-hypothesis optimization metaheuristics. We use the scan-to-map matching error computed by a pose tracking algorithm, the Perfect Match (PM), as the metric to score the hypotheses. Our main contribution is to propose an enhanced localization system by integrating a multi-hypothesis global localization method with the PM. We also analyzed different optimization heuristics applied to the GLP under typical and special conditions. Using simulations and real-world experiments, we measured the success rate and computing cost using several population sizes. Results show that studied methods perform differently in distinct scenarios, but our proposals based on Genetic Algorithm (GA) and Particle Swarm Optimization (PSO) showed an average success rate above 83%, while other methods did not achieved 80%. Furthermore, PM-based methods exhibit lower computing cost when compared to the traditional Adaptive Monte Carlo Localization (AMCL) after the 100th iteration. In summary, our study shows that the GA-based proposal, which performed slightly better than the PSO-based, represents the best candidate to integrate a robust localization system.