Russian Federation
GRNTI 50.07 Теоретические основы вычислительной техники
BBK 3297 Вычислительная техника
One of the difficult problems to solve has always been and still remains the problem of finding a path either in a graphic chart or a graphic maze of large size. The main problem is that traditional algorithms require a lot of time due to combinatorial complexity. At the same time, both classical algorithms based on the search of variants (such as Dijkstra's algorithm, A*, ARA*, D* lite), and stochastic algorithms (ant algorithm, genetic), alongside with algorithms based on morphology (wave) are not always able to achieve the goal. The article proposes a new modification of the path-finding algorithm, which is a hybrid of the following: the morphological operations on graphic chart approach and genetic algorithm having a useful property of elasticity in time. The experiments (both synthetic and real data) have shown the feasibility of the proposed idea and its comparison with the most commonly used algorithms of contemporaneity.
path search, genetic algorithms, morphological transformations of images
1. Alhanjouri M., Alfarra B. Ant Colony versus GeneticAlgorithm based on Travelling Salesman Problem //International Journal of Computer Technology andApplications. - Vol. 2, 2011. - pp. 570-578.
2. Cormen T., Leiserson C., Rivest R., Stein C. Introductionto Algorithms. - 3rd edition. - The MIT Press, 2009. -1292 p.
3. Delling, D.; Sanders, P.; Schultes, D.; Wagner, D.Engineering Route Planning Algorithms // Algorithmics ofLarge and Complex Networks: Design, Analysis, andSimulation. - Springer, 2009. - pp. 117-139.
4. Dorigo M., Maniezzo V. Colorni A.Ant System:Optimization by a Colony of Cooperating Agents // IEEETransactions on Systems, Man, and Cybernetics-Part B. -pp. 29-41.
5. Gonzalez R.C., Woods R.E. Digital Image Processing. -4rd edition. - Prentice-Hall, 2018. - 976 p.
6. Hangl S., Ugur E., Piater J. Autonomous robots: potential,advances and future direction // Elektrotechnik undInformationstechnik. - 2017, Volume 134, Issue 6. - pp.293-298.
7. Koenig S., Likhachev M. D* lite // Eighteenth nationalconference on Artificial intelligence. - Edmonton, Alberta,Canada, 2002. - pp. 476-483.
8. Likhachev M.; Gordon G.; Thrun S. ARA*: formalanalysis // School of Computer Science, Carnegie MellonUniversity, 2003.
9. Maze classification. Lists of Maze generation methods,Maze solving methods, and classes of Mazes in general.
10. Russell S., Norvig, P. Artificial Intelligence: A ModernApproach, 2rd Edition. - M.: Wiliams, 2006. - pp. 157-162.
11. Rutkovskaya D., Pilinsky M., Rutkovsky L. Neuralnetworks, Genetic algorithms and Fuzzy systems., 2nd ed.- M: Hotline-Telecom, 2008. - 452 p.
12. Savostin I. A., Trubakov A. O. Application of geneticprogramming for the solution of the problem of theoptimal robot's motion path construction / / [Proc. of theXVI international scientific-practical conference ofstudents, postgraduates and young scientists ""Youth andmodern information technologies.""] - Tomsk, 2018. - rp.118-119.
