SmartPATH: An Efficient Hybrid ACO-GA Algorithm for Solving the Global Path Planning Problem of Mobile Robots

摘要

Path planning is a fundamental optimization problem that is crucial for the navigation of a mobile robot. Among the vast array of optimization approaches, we focus in this paper on Ant Colony Optimization (ACO) and Genetic Algorithms (GA) for solving the global path planning problem in a static environment, considering their effectiveness in solving such a problem. Our objective is to design an efficient hybrid algorithm that takes profit of the advantages of both ACO and GA approaches for the sake of maximizing the chance to find the optimal path even under real-time constraints. In this paper, we present smartPATH, a new hybrid ACO-GA algorithm that relies on the combination of an improved ACO algorithm (IACO) for efficient and fast path selection, and a modified crossover operator to reduce the risk of falling into a local minimum. We demonstrate through extensive simulations that smartPATH outperforms classical ACO (CACO), GA algorithms. It also outperforms the Dijkstra exact method in solving the path planning problem for large graph environments. It improves the solution quality up to 57% in comparison with CACO and reduces the execution time up to 83% as compared to Dijkstra for large and dense graphs. In addition, the experimental results on a real robot shows that smartPATH finds the optimal path with a probability up to 80% with a small gap not exceeding 1m in 98%.