Implementação de algoritmo baseado em otimização por colônia de formigas aplicado ao planejamento de caminhos para robô móvel

Abstract

Path planning for mobile robots is one of the central themes in mobile robotics, as robots are expected to be able to plan their movements autonomously. Numerous strategies have been developed over the last few decades. Some of these are based at some point on the realization of a search for an optimal path in a space of possible solutions generated. In this context, with the development of metaheuristics in the last two decades, which are able to provide effective methods for the realization of these searches, these arise as a developing alternative to the use of classic methods to provide good solutions to the problem of path planning. That said, this work deals with the implementation of two algorithms based on Ant Colony Optimization (ACO) applied to the path planning problem for mobile robots allied to the classic strategy of cells decomposition of the robot workspace. The algorithms are: (1) Max-Min Ant System (MMAS) and (2) Fast Two-Stages Max-Min Ant System (FTS-MMAS). The purpose of the algorithms is to find an optimal path in the decomposed map. In order to verify the efficiency of all the implemented strategy, the ACO algorithms were submitted to a series of simulated tests, in order to measure its performance in relation to execution time and path length obtained in a simple scenario, two more complex scenarios and one scenario of larger size. At last, an experiment in a real robot was carried out, this one having as main objective to certify if the robot would be able to execute the planned path. The results for the simulated tests indicated that the ACO algorithms implemented have similar performances in relation to the length of the possible paths. In relation to the execution time, a difference in performance was observed, with the FTS-MMAS algorithm being faster. The MMAS algorithm presented a significantly longer execution time. The experiment performed in the real robot with the FTS-MMAS algorithm had acceptable performance in the path length and planning time criteria. Discrepancies between the planned and executed paths were observed, mainly in the curves, due to the non-holonomic constraints and the controller that generates the signals for the motors. Finally, this work provides a basis for the Automation and Robotics Research Group (GPAR - Grupo de Pesquisa em Automação e Robótica) in the DEE/UFC for future path planning work, involving topics such as Control and Computational Intelligence.