Article

Article title STUDY OF HEURISTIC ALGORITHMS IN PLANNING AND OPTIMIZATION OF ROUTES PROBLEM IN THE ENVIRONMENT WITH OBSTACLES
Authors R.A. Neydorf, V.V. Polyakh, I.V. Chernogorov, O.T. Yarakhmedov
Section SECTION III. MONITORING AND CONTROL IN TECHNICAL SYSTEMS
Month, Year 03, 2016 @en
Index UDC 519.856/629.7.051/004.023
DOI
Abstract We have investigated three possible approaches to solve the problem of finding an efficient (shortest, fastest or safe, etc.) route to a two-dimensional space with obstacles. As a solution for this problem, it used the most famous heuristics: ant colony algorithm (ACA), swarming particles method (SPM) and the evolutionary-genetic algorithm (EGA). Constructed and investigated algorithms modification of these methods that are adapted to solve the above problem. For the option of using SPM shown that the closest to the problem is suitable hybrid behavioral elements swarm, flock of birds and a number of other options for multi-agent interaction. The hybrid algorithm organically includes basic prototype for the fundamental equations of mechanics, the laws of gravitation and stochastic "blurring" of the movement parameters. In the study of ACA shown that it is appropriate to apply the classical partition search space to incomparably small compared to the obstacles fragments. Ant’s agents are used traditional logic of selecting of the transition from a fragment of a fragment: the memory of the most popular routes based on pheromone, and formulated task elements of tactics adopted and situationally based and random decisions. This leads to an effective improvement and quasi route optimization. Using of the EGA, as one of the most popular heuristic optimization techniques, considerable difficulties relating to the distinctive features of the population operators formation, crossover and mutation. The formalization of the mechanisms under the EGA search among the best ways of containing obstacles, making significant adjustments to the conceptual and EGA mathematical models. So, this method yields SPM and ACA performance in this task. As a test research, suggested approach and developed algorithms it was developed special software «The evolutionary-genetic algorithm of route optimization in the environment obstacles», «Path planning with obstacle avoidance by ant colony optimization» and «The method of route optimization in the obstacles avoidance tasks by seekers particles ». With using of that software, it was made numerical experiments, which illustrate the solution of the problem in terms of clusters of different obstacles.

Download PDF

Keywords Purpose; route; obstacle; mathematical model; optimization; group behavior; heuristics; swarming particles algorithm; ant colony algorithm; evolutionary-genetic algorithm
References 1. Pshikhopov V.Kh. Intellektual'noe planirovanie traektoriy podvizhnykh ob"ektov v sredakh s prepyatstviyami [Intelligent trajectories simulating of moving objects in environments with obstacles], ed. by V.Kh. Pshikhopova. Moscow: Fizmatlit, 2014, 350 p.
2. Zaeva K., Semenov A. Sistema poiska minimal'nogo puti v srede s poligonal'nymi prepyatstviyami [Minimal path search engine in an environment with polygonal obstacles], 24-ya Mezhdunarodnaya konferentsiya po komp'yuternoy grafike i zreniyu: trudy konferentsii [The 24rd International Conference on Computer Graphics and Vision September 30 – October 3, 2014 Rostov-on-Don, Russia]. Rostov-on-Don, Akademiya arkhitektury i iskusstv YuFU. GrafiKon’2014, pp. 163-166.
3. Dutta S. Obstacle Avoidance of Mobile Robot using PSO-based Neuro Fuzzy Technique, International Journal of Computer Science and Engineering, 2010, Vol. 2, No. 2, pp. 301-304.
4. Koren Y., Borenstein J. Potential field methods and their inherent limitations for mobile robot navigation, Proceedings of the IEEE Int. Conf. on Robotics and Automation, 1991, pp. 1398-1404.
5. Fujimori A., Nikiforuk P., and Gupta M. Adaptive navigation of mobile robots with obstacle avoidance, IEEE Transactions on Robotics and Automation, 1997, Vol. 13, No. 4, pp. 596-602.
6. Hansen E.A., Zilberstein S. LAO*: A heuristic search algorithm that finds solutions with loops, Artificial Intelligence, 2001, No. 129, pp. 35-62.
7. Engineer F. Fast Shortest Path Algorithms for Large Road Networks, In Proceedings of the 36th Annual ORSNZ Conference, Wellington, New Zealand. 2001.
8. Kalyaev I.A., Gayduk A.R. Printsipy postroeniya sistem planirovaniya povedeniem intellektual'nykh robotov na baze odnorodnykh neyropodobnykh struktur [Principles of behavior of construction planning systems intelligent robo-ing on the basis of similar neural structures], Materialy VIII konferentsii «Ekstremal'naya robototekhnika» [Materials of the VIII Conference "Extreme Robotics"]. St. Petersburg: SPbGTU, 1997, pp. 14-23.
9. Kalyaev A.V. Chernukhin Yu.V. Noskov V.N., Kalyaev I.A. Odnorodnye upravlyayushchie struktury adaptivnykh robotov [Homogeneous control structures of adaptive robots]. Moscow: Nauka, 1990, 152 p.
10. Avotin E.B. i dr. Dinamika planetokhoda [Dynamics of Planetary], ed. by B.N. Petrova and A.L. Kemurdzhiana. Moscow: Nauka, 1979, 438 p.
11. Poluyan A.Yu., Mareychenko I.V. Postroenie bionicheskogo poiska dlya zadach ob ekstremal'nom puti na osnove strategii adaptatsii [Building a bionic search for problems on the extreme path on the basis of an adaptation strategy], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2013, No. 7 (144), pp. 58-64.
12. Chernyshev Yu.O., Poluyan A.Yu. Primenenie bionicheskikh algoritmov dlya resheniya zadachi o naznachenii [The use of bionic algorithms to solve the problem of the appointment], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2011, No. 7 (120), pp. 14-22.
13. Zaporozhets D.Yu., Kureychik V.V. Gibridnyy algoritm resheniya zadach transportnogo tipa [Hybrid algorithm for solving vehicle type], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2013, No. 7 (144), pp. 80-85.
14. Chen S., Eshaghian M.M. A fast recursive mapping algorithm, Department of computer and information science. New Jersey, USA: New Jersey, 2013, pp. 219-227.
15. McLean A., Cameron S. Path planning and collision avoidance for redundant manipulators in 3D, Intelligent Autonomous Systems. Karlsruhe, Germany: IOS Press, 1995, pp. 381-388.
16. Starostin N.V., Pankratova M.A. Geneticheskiy algoritm resheniya zadachi otobrazheniya grafa [Genetic algorithm for displaying a graph], Vestnik NNGU [Herald of UNN], 2013, No. 5-1, pp. 204-209.
17. Hoefler T., Snir M. Generic Topology Mapping Strategies for Large-scale Parallel Architectures, University of Illinois at Urbana-Champaign Urbana, 2011, pp. 75-85.
18. Neydorf R.A., Polyakh V.V. Lokalizatsiya oblastey poiska evolyutsionno-geneticheskogo algoritma pri reshenii zadach mnogoekstremal'nogo kharaktera [Seatch area localization by evolutionary-genetic algorithm in solving tasks with multiextremal character], Mezhdunarodnyy nauchnyy zhurnal «Nauka. Tekhnologii. Proizvodstvo» [International scientific journal "Science. Technologies. Production"], 2015, No. 5 (9), pp.32-35.
19. Neydorf R.A. Polyakh V.V. Metod mnogoekstremal'nogo poiska s ispol'zovaniem evolyutsionno-geneticheskogo algoritma i vyborochnogo kriteriya Ct'yudenta [The method of multiextremal search using an evolutionary-genetic algorithm and selective Student criterion], Mezhdunarodnyy nauchnyy zhurnal "Innovatsionnaya nauka" [International Scientific Journal "Innovative science"], 2015, No. 3, pp. 135-139.
20. Neydorf R.A., Polyakh V.V. Issledovanie mnogoekstremal'nykh zavisimostey s ispol'zovaniem evolyutsionno geneticheskogo metoda i odnovyborochnogo kriteriya St'yudenta [The study of multiextremal dependencies using evolutionary-genetic method and one-sample Student's criterion], Trudy XXVIII Mezhdunarodnoy nauchnoy konferentsii «Matematicheskie metody v
tekhnike i tekhnologiyakh» – MMTT-28 [Proceedings of the XXVIII International Scientific Conference "Mathematical Methods in Engineering and Technology" – ММТТ-28], 2015, Vol. 6, pp. 83-87.
21. Neydorf R.A., Chernogorov I.V., Polyakh V.V., Yarakhmedov O.T. Obnaruzhenie i otsenka ekstremal'nykh osobennostey prostranstva poiska evristicheskimi algoritmami [Detection and evalution extreme features of heuristic algorithm search space], Sbornik tezisov II Vserossiyskoy nauchno-tekhnicheskoy konferentsii «Teoreticheskie i prikladnye problemy
razvitiya i sovershenstvovaniya avtomatizirovannykh sistemy upravleniya voennogo naznacheniya» [Abstracts of II All-Russian scientific conference "Theoretical and applied problems of development and improvement of auto-disaggregated as military control systems"], 2015, pp. 189-190.
22. Eberhart R.C., Kennedy J.A. New optimizer, using particle swarm theory, Proceedings of the Sixth International Symposium on Micromachine and Human Science, Nagoya, Japan, 1995, pp. 39-43.
23. Kennedy J., Eberhart R. Particle Swarm Optimization, Proceedings of IEEE International Conference on Neural Networks, Piscataway: New Jersey, 1995, pp. 1942-1948.
24. Shi Y., Eberhart R.C. A modified particle swarm optimizer, Proceedings of the IEEE Congress on Evolutionary Computation, Piscataway: New Jersey, 1998, pp. 69-73.
25. Clerc M., Kennedy J. The particle swarm-explosion, stability, and convergence in a multi-dimensional complex space, IEEE Transactions on Evolutionary Computation, 2002, pp. 58-73.
26. Mendes, J. Kennedy, J. Neves. The fully informed particle swarm: simpler, maybe better, IEEE Transactions on Evolutionary Computation, 2004, Vol. 8, Issue 3, pp. 204-210.
27. Neydorf R.A. Chernogorov I.V. Parametricheskaya nastroyka algoritma poiskovoy optimizatsii metodom royashchikhsya chastits s ispol'zovaniem planirovaniya eksperimenta [Parametrical configuration of the algorithm of search optimization by the method of swarm particles using experiment planning], Mezhdunarodnyy Nauchnyy Institut "Educatio" [International Research Institute], 2015, Vol. 4, No. 2 (9), pp. 44-49.
28. Neydorf R.A., Chernogorov I.V. Rasshirenie funktsionala metoda royashchikhsya chastits kinematicheskoy i dinamicheskoy modifikatsiey algoritma ego realizatsii [Functional expansion of swarming particles method by cinematic and dynamic algorithm modification of its realization], OOO "Aeterna": Sbornik statey «Rol' nauki v razvitii obshchestva» [Ltd. "Aeterna",
Collection of articles "The role of science in the development of society"]. Sektsiya SB-17, 2015, Vol. 1, pp. 24-28.
29. Neydorf R.A., Chernogorov I.V. Parametricheskoe issledovanie algoritma royashchikhsya chastits v zadache poiska global'nogo ekstremuma [Parametrical research of algorithm of swarm particles in problem of finding the global extremum], Trudy XXVIII Mezhdunarodnoy
nauchnoy konferentsii «Matematicheskie metody v tekhnike i tekhnologiyakh» – MMTT-28 [Proceedings of the XXVIII International Scientific Conference "Mathematical Methods in Engineering and Technology" – MMTT-28], 2015, Vol. 3, pp. 75-59.
30. Neydorf R.A., Chernogorov I.V., Polyakh V.V., Yarakhmedov O.T. Eksperimental'noe issledovanie vozmozhnostey resheniya mnogoekstremal'nykh zadach optimizatsii evristicheskimi metodami [Experimental study on solution possibilities of multiextremal optimization problems through heuristic methods], Vestnik DGTU [Herald of DSTU], 2015, Vol. 15, No. 4 (83), pp. 82-93.
31. Neydorf R.A., Derevyankina A.A. Metodologiya resheniya mnogoekstremal'nykh zadach modifitsirovannym metodom royashchikhsya chastits [Methodology solutions multiextremal problems by swarming modified particles], Innovatsiya, ekologiya i resursosberegayushchie
tekhnologii na predpriyatiyakh mashinostroeniya, aviastroeniya, transporta i sel'skogo khozyaystva: trudy IX Mezhdunarodnoy nauchno-tekhnicheskoy konferentsii [Innovation, ecology and resource-saving technologies at enterprises of machine building, aircraft industry, transport and agriculture: Proceedings of the IX International Scientific and Technical Conference]. Rostov-on-Don: ITs DGTU, 2010, pp. 328-330.
32. Neydorf R.A., Derevyankina A.A. Reshenie mnogoekstremal'nykh zadach metodom delyashchikhsya roev [The solution of multi tasks by dividing swarms], Vestnik DGTU [Herald of DSTU], 2010, Vol. 10, No. 4 (47), pp. 492-499.
33. Neydorf R.A., Derevyankina A.A. Reshenie zadach raspoznavaniya metodom royashchikhsya chastits s deleniem roya [The solution of problems of recognition by swarming particle swarm division], Izvestiya YuFU, Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2010, No. 7 (108), pp. 21-28.
34. Neydorf R.A., Pankov–Kozochkin P.A. Primenenie evristicheskikh metodov optimizatsii dlya zadach neyrosetevoy operativnoy korrektsii SAU [The use of heuristic optimization methods for problems of neural network operative correction SAU], Sbornik trudov IV Mezhdunarodnogo nauchno-metodicheskogo simpoziuma "Sovremennye problemy
mnogourovnevogo obrazovaniya" MMTT-22 [Proceedings of the IV International scientificmethodological symposium "Current problems of multilevel education" ММТТ-22], 2009, Vol. 11, pp. 121-127.
35. Dorigo M., Gambardella L.M. Ant colony system: a cooperative learning approach to the traveling salesman problem, IEEE Transactions on Evolutionary Computation, 1997, Vol. 1, No. 1, pp. 53-66.
36. Dorigo M., Di Caro G. & Gambardella L.M. Ant Algorithms for Discrete Optimization, Artificial Life, 1999, No. 5 (2), pp. 137-172.
37. Kazharov A.A., Kureychik V.M. Murav'inye algoritmy dlya resheniya transportnykh zadach [Ant algorithms to solve transport problems], Teoriya i sistemy upravleniya [Theory and control systems], 2010, No. 1, pp. 30-43.
38. Shtovba S.D. Murav'inye algoritmy [Ant algorithms], Matematika v prilozheniyakh [Mathematics in Applications], 2004, No. 4, pp. 70-75.
39. Toksari M.D. Ant Colony Optimization for finding the global minimum, Applied Mathematics and Computation, 2006, No. 176, pp. 308-316.
40. Liu X., Fu H. An effective clustering algorithm with ant colony, Journal of Computers, 2010, Vol. 5, No. 4, pp. 598-605.
41. Pang C.Y., Li X. Apply Ant Colony Algoritm to Search All Extreme Points of Function, 5th IEEE Conf. on industrial Electronics and Applications, 2009, pp. 1517-1521.
42. Neydorf R.A., Yarakhmedov O.T. Razrabotka, optimizatsiya i analiz parametrov klassicheskogo murav'inogo algoritma pri reshenii zadachi kommivoyazhera v polnosvyaznom grafe [Design, optimization and analysis of the parameters of classical ant algorithm for solving the traveling salesman problem in a fully-connected graph], Mezhdunarodnyy nauchnyy zhurnal «Nauka. Tekhnologii. Proizvodstvo» [International scientific journal "Science. Technologies. Production"], 2015, Vol. 2, No. 3, pp. 18-22.
43. Neydorf R.A., Yarakhmedov O.T. Statisticheskoe issledovanie optimizatsionnykh svoystv resheniya klassicheskim murav'inym algoritmom zadachi kommivoyazhera [Statistical research optimization properties of solutions of the travelling salesman problem by ant algorithm], Mezhdunarodnyy Nauchnyy Institut "Educatio" [International Research Institute], 2015, No. 4 (11), pp. 141-144.
44. Neydorf R.A., Yarakhmedov O.T. Issledovanie vozmozhnostey optimal'nogo resheniya zadachi kommivoyazhera parametricheski optimizirovannym murav'inym algoritmom [Analysis of abilities of optimal solution of the travelling salesman problem by parametrically optimized
ant algorithm], Trudy XXVIII Mezhdunarodnoy nauchnoy konferentsii «Matematicheskie metody v tekhnike i tekhnologiyakh» – MMTT-28 [Proceedings of the XXVIII International Scientific Conference "Mathematical Methods in Engineering and Technology" – ММТТ-28], 2015, Vol. 6, 108 p.
45. Fatemeh K.P., Fardad F., Reza S.N. Comparing the Performance of Genetic Algorithm and Ant Colony Optimization Algorithm for Mobile Robot Path Planning in the Dynamic Environments with Different Complexities, Journal of Academic and Applied Studies, 2013, Vol. 3 (2), pp. 29-44.

Comments are closed.