Search
Abstract
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.
Citations
-
1 2
CrossRef
-
0
Web of Science
-
1 2
Scopus
Authors (3)
Cite as
Full text
full text is not available in portal
Keywords
Details
- Category:
- Articles
- Type:
- artykuł w czasopiśmie wyróżnionym w JCR
- Published in:
-
Journal of Computational Science
no. 20,
pages 8 - 16,
ISSN: 1877-7503 - Language:
- English
- Publication year:
- 2017
- Bibliographic description:
- Redlarski G., Dąbkowski M., Pałkowski A.: Generating optimal paths in dynamic environments using RiverFormation Dynamics algorithm// Journal of Computational Science. -Vol. 20, (2017), s.8-16
- DOI:
- Digital Object Identifier (open in new tab) 10.1016/j.jocs.2017.03.002
- Verified by:
- Gdańsk University of Technology
seen 109 times
Recommended for you
Swarm-Assisted Investment Planning of a Bioethanol Plant
- G. Redlarski,
- M. Krawczuk,
- A. Kupczyk
- + 2 authors