Generating optimal paths in dynamic environments using River Formation Dynamics algorithm

摘要

The paper presents a comparison of four optimisation algorithms implemented for the purpose of finding the shortest path in static and dynamic environments with obstacles. Two classical graph algorithms the Dijkstra complete algorithm and A* heuristic algorithm - were compared with metaheuristic River Formation Dynamics swarm algorithm and its newly introduced modified version. Moreover, another swarm algorithm has been compared - the Ant Colony Optimization and its modification. Terms and conditions of the simulation are thoroughly explained, paying special attention to the new, modified River Formation Dynamics algorithm. The algorithms were used for the purpose of generating the shortest path in three different types of environments, each served as a static environment and as a dynamic environment with changing goal or changing obstacles. The results show that the proposed modified River Formation Dynamics algorithm is efficient in finding the shortest path, especially when compared to its original version. In cases where the path should be adjusted to changes in the environment, calculations carried out by the proposed algorithm are faster than the A*, Dijkstra, and Ant Colony Optimization algorithms. This advantage is even more evident the more complex and extensive the environment is. (C) 2017 Elsevier B.V. All rights reserved.