Applying the MOVNS (multi-objective variable neighborhood search) algorithm to solve the path planning problem in mobile robotics

摘要

Mobile robots must calculate the appropriate navigation path before starting to move to its destination. This calculation is known as the Path Planning (PP) problem. The PP problem is one of the most researched topics in mobile robotics. Taking into account that the PP problem is an NP-hard problem, Multi Objective Evolutionary Algorithms (MOEAs) are good candidates to solve this problem. In this work, a new multi-objective evolutionary approach based on the Variable Neighborhood Search (MOVNS) is proposed to solve the PP problem. To the best of our knowledge, this is the first time that MOVNS is proposed to solve the path planning of mobile robots. The proposed MOVNS handles three different objectives in order to obtain accurate and efficient paths. These objectives are: the path safety, the path length, and the path smoothness (related to the energy consumption). Furthermore, in order to test the proposed MOEA, we have used eight realistic scenarios for the paths calculation. On the other hand, we also compared our proposal with other approaches of the state of the art, showing the advantages of MOVNS. In particular, in order to evaluate the obtained results we applied different quality metrics. Moreover, to demonstrate the statistical robustness of the obtained results we also performed a statistical analysis. Finally, the study shows that the proposed MOVNS is a good alternative to solve the PP problem, producing good paths with less length, more safety, and more smooth movements. We think this is an important contribution to the mobile robotics, and therefore, to the field of expert and intelligent systems. (C) 2016 Elsevier Ltd. All rights reserved.