Россия
Россия
Россия
УДК 519.7 Математическая кибернетика
Статья посвящена анализу поведения мобильного робота с использованием алгоритмов конечных автоматов с целью поиска пути до цели и обхода препятствий. После обоснования использования таких методов, делается разбор стандартного детерминированного конечного автомата. Далее к этому алгоритму применяется теория марковских процессов, в результате чего конечный автомат становится частью скрытой марковской модели. Это позволяет применить вероятностные методы к планированию поведения робота. Этот вероятностный характер поведения наиболее перспективен в сложных средах с непредсказуемой конфигурацией препятствий. Для сравнения эффективности детерминированного и вероятностного конечного автоматов мы применили генетический алгоритм. В численном эксперименте, который мы провели в среде Scilab, мы рассмотрели два основных типа сред, в которых может передвигаться мобильный робот – среда офисного типа и среда полигонального типа. Для каждого типа сред мы поочерёдно применяли каждый из указанных алгоритмов поведения. Для генетического алгоритма мы использовали сто особей, которые обучалась на протяжении 1000 поколений находить наиболее оптимальный путь в указанных средах. В результате было обнаружено, что алгоритм детерминированного конечного автомата наиболее перспективен для движения в среде офисного типа, а алгоритм вероятностного конечного автомата даёт наилучший результат в сложной полигональной среде.
Генетические алгоритмы, поведение роботов, конечные автоматы, марковские модели, Scilab.
1. Robots that can adapt like animals / A. Cully, J. Clune, D. Tarapore, J.B. Mouret // Nature. – 2015. - V. 521 (7553). - Pp. 503–507. - DOI: 10.1038/nature14422.
2. Юдинцев, Б.С. Синтез нейросетевой системы планирования траекторий для группы мобильных роботов / Б.С. Юдинцев // Системы управления, связи и безопасности. – 2019. - № 4. – С. 163-186. – DOI: 10.24411/2410-9916-2019-10406.
3. Path Planning for Mobile Robot Navigation in Unknown Indoor Environments Using Hybrid PSOFS Algorithm / M.N.A. Wahab, C.M. Lee, M.F. Akbar, F.H. Hassan // IEEE Access. - 2020. - Vol. 8. - Pp. 161805-161815. - DOI: 10.1109/ACCESS.2020.3021605.
4. Arkin, R. Behavior-Based Robotics / R. Arkin. – MIT Press. Cambridge, 1998. – 491 p. - DOI:10.5860/choice.36-5109.
5. Даринцев, О.В. Синтез гибридных интеллектуальных алгоритмов планирования траектории / О.В. Даринцев, А.Б. Мигранов // Фундаментальные исследования. – 2015. – № 12-4. – С. 676-681
6. Floreano, D. Evolutionary robotics / D. Floreano, P. Husbands, S. Nolfi // Springer handbook of robotics. - Springer, 2008. – Pp. 1423-1451. - DOI:10.1007/3-540-64957-3.
7. Fogel, D.B. Nils barricelli-artificial life, coevolution, self-adaptation / D.B. Fogel // Computational Intelligence Magazine. – 2006. – Vol. 1. – Pp. 41-45. – DOI: 10.1109/MCI.2006.1597062.
8. Fraundorfer, F. Visual odometry / F. Fraundorfer, D. Scaramuzza // IEEE Robotics and Automation Magazine. – 2011. - Vol. 18, № 4. – Pp. 80-92. – DOI: 10.1109/MRA.2011.943233.
9. Accelerating large-scale inference with anisotropic vector quantization / R. Guo, P. Sun, E. Lindgren [et al.] // Proceedings of the 37th International Conference on Machine Learning. – 2020. - Vol. 119. – Pp. 3887-3896.
10. Savage, J. Semantic reasoning in service robots using expert systems / J. Savage, D. Rosenblueth, M. Matamoros [et al.] // Robotics and Autonomous Systems. – 2019. – Vol. 114. – Pp. 77-92. – DOI: 10.1016/j.robot.2019.01.007.
11. Marocco, D. Active vision and feature selection in evolutionary behavioral systems / D. Marocco, D. Floreano // From animals to animats : Proceedings of the Seventh International Conference on Simulation of Adaptive Behavior. – 2002. – Pp. 247- 255. – DOI: 10.7551/mitpress/3121.003.0042.
12. Mohanan, M.G. Probabilistic Approach to Robot Motion Planning in Dynamic Environments / M.G. Mohanan, A. Salgaonkar // SN Computer Science. – 2020. - Vol. 1. - C. 181. – DOI: 10.1007/s42979-020-00185-0.
13. Rabiner, L. An introduction to hidden Markov models / L. Rabiner, B. Juang // IEEE ASSP Magazine. – 1986. – Vol. 3. – Pp. 4-16. - DOI:10.1109/MASSP.1986.1165342.
14. Map representation using hidden markov models for mobile robot localization / J. Savage, O. Fuentes, L. Contreras, M. Negrete // 13th International Scientific-Technical Conference on Electromechanics and Robotics. – 2018. – C. 161. – DOI: 10.1051/MATECCONF/201816103011.
15. Negrete, M. A Motion-Planning System for a Domestic Service Robot / M. Negrete, J. Savage, L. Contreras // SPIIRAS Proceedings. – 2018. - Vol. 60(5). – Pp. 5-38. – DOI: 10.15622/sp.60.1.
16. Vidal, E. Probabilistic finite-state machines / E. Vidal, F. Thollard // IEEE Transactions on Pattern Analysis and Machine Intelligence. – 2005. - Vol. 27. – Pp. 1013-1025. - DOI:10.1109/TPAMI.2005.147.
17. Nelson, A. Fitness functions in evolutionary robotics: A survey and analysis / A. Nelson, G.J. Barlow, L. Doitsidis // Robotics and Autonomous Systems. – 2009. – Vol. 57. – Pp. 345-370. – DOI: 10.1016/j.robot.2008.09.009.
18. Yakoubi, M. A. The path planning of cleaner robot for coverage region using genetic algorithms / M.A. Yakoubi, M.T. Laskri // Journal of Innovation in Digital Ecosystems. – 2016. - Vol. 3. – Pp. 37-43. – DOI: 10.1016/j.jides.2016.05.004.
19. Benhlima, S. Genetic algorithm based approach for autonomous mobile robot path plannings / S. Benhlima, L. Chaymaa, A. Bekri // Procedia computer science. – 2018. – Vol. 127(3). – Pp. 180-189. – DOI: 10.1016/j.procs.2018.01.113.
20. Мунасыпов, Р.А. Методика синтеза стратегии движения автономного мобильного робота на основе эволюционных процессов / Р.А. Мунасыпов, С.С. Москвичев // Вестник Уфимского государственного авиационного технического университета. – 2012. – Т. 16, № 3. – С. 56-62.
21. Метод планирования траектории движения точки в пространстве с препятствием на основе итеративной кусочно-линейной аппроксимации / В.О. Антонов, М.М. Гурчинский, В.И. Петренко, Ф.Б. Тебуева // Системы управления, связи и безопасности. - 2018. - № 1. -С. 168-182.
22. Алексеев, Е.Р. Scilab: Решение инженерных и математических задач / Е.Р. Алексеев, О.В. Чеснокова, Е.А. Рудченко. – М. : ALT Linux; БИНОМ. Лаборатория знаний. – 2008. – 269 с.
