Russian Federation
Russian Federation
Russian Federation
UDK 519.7 Математическая кибернетика
The article is devoted to the analysis of the behavior of a mobile robot using finite state machine algorithms in order to find a way to the goal and avoid obstacles. After justifying the use of such methods, the analysis of a standard deterministic finite automaton is done. Further, the theory of Markov processes is applied to this algorithm, as a result of which the state machine becomes part of the hidden Markov model. This allows you to apply probabilistic methods to modeling the behavior of the robot. This probabilistic behavior is most promising in complex environments with unpredictable obstacle configurations. To compare the efficiency of deterministic and probabilistic finite state machine, we applied a genetic algorithm. In the numerical experiment that we conducted in the Scilab software, we considered two main types of environments in which a mobile robot can move - an office-type environment and a polygonal-type environment. For each type of environment, we alternately applied each of the indicated behavior algorithms. For the genetic algorithm, we used one hundred individuals who were trained over 1000 generations to find the most optimal path in the specified environments. As a result, it was found that the deterministic finite state machine algorithm is the most promising for movement in an office-type environment, and the probabilistic finite state machine algorithm gives the best result in a complex polygonal environment.
Genetic algorithms, robot behavior, finite state machines, Markov models, 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:https://doi.org/10.1038/nature14422.
2. Yudincev, B.S. Sintez neyrosetevoy sistemy planirovaniya traektoriy dlya gruppy mobil'nyh robotov / B.S. Yudincev // Sistemy upravleniya, svyazi i bezopasnosti. - 2019. - № 4. - S. 163-186. - DOI:https://doi.org/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:https://doi.org/10.1109/ACCESS.2020.3021605.
4. Arkin, R. Behavior-Based Robotics / R. Arkin. - MIT Press. Cambridge, 1998. - 491 p. - DOIhttps://doi.org/10.5860/choice.36-5109.
5. Darincev, O.V. Sintez gibridnyh intellektual'nyh algoritmov planirovaniya traektorii / O.V. Darincev, A.B. Migranov // Fundamental'nye issledovaniya. - 2015. - № 12-4. - S. 676-681
6. Floreano, D. Evolutionary robotics / D. Floreano, P. Husbands, S. Nolfi // Springer handbook of robotics. - Springer, 2008. - Pp. 1423-1451. - DOIhttps://doi.org/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:https://doi.org/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:https://doi.org/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:https://doi.org/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:https://doi.org/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:https://doi.org/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. - DOIhttps://doi.org/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:https://doi.org/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:https://doi.org/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. - DOIhttps://doi.org/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:https://doi.org/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:https://doi.org/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:https://doi.org/10.1016/j.procs.2018.01.113.
20. Munasypov, R.A. Metodika sinteza strategii dvizheniya avtonomnogo mobil'nogo robota na osnove evolyucionnyh processov / R.A. Munasypov, S.S. Moskvichev // Vestnik Ufimskogo gosudarstvennogo aviacionnogo tehnicheskogo universiteta. - 2012. - T. 16, № 3. - S. 56-62.
21. Metod planirovaniya traektorii dvizheniya tochki v prostranstve s prepyatstviem na osnove iterativnoy kusochno-lineynoy approksimacii / V.O. Antonov, M.M. Gurchinskiy, V.I. Petrenko, F.B. Tebueva // Sistemy upravleniya, svyazi i bezopasnosti. - 2018. - № 1. -S. 168-182.
22. Alekseev, E.R. Scilab: Reshenie inzhenernyh i matematicheskih zadach / E.R. Alekseev, O.V. Chesnokova, E.A. Rudchenko. - M. : ALT Linux; BINOM. Laboratoriya znaniy. - 2008. - 269 s.
