A Step-by-Step Algorithm for Finding the Optimal Strategy for the Behavior of a Group of Robots
https://doi.org/10.17587/mau.21.689-695
Abstract
The solution of the multi-criteria problem, which includes the distribution of objectives, the planning of trajectories and the optimization of energy consumption, is considered in the realization of the collective interaction of robots. It is proposed to use a genetic algorithm according to the chosen conditions (constraints) and optimality criteria to find the best strategy for group behavior. The considerable difficulty in choosing how to control a team of autonomous mobile robots represents the distribution of tasks among agents that operate under conditions of parametric and information uncertainty, possess "modest" hardware, power and functionality. Therefore, the implementation of a multi-stage search for an optimal solution requires a specialized approach that takes into account the whole range of dynamic parameters, allowing for real-time target correction and degradation of robots until they fail. The basis of the proposed neurogenetic algorithm is a new algorithm for calculating the fitness function, in which the results of the neural network method of trajectory planning for a group of robots are used, as well as information about the initial charge of the batteries of robotic agents of the collective, the energy consumption of each agent and the preliminary estimation of the energy required by some agent to perform the individual tasks available to it. In order to ensure an acceptable performance of the algorithm and given the high dynamism of the external environment, it was decided to limit the search for solutions to only one step (the next working beat of the collective). The paper presents the results of the simulation of the task of finding the optimal behavior of robots, the algorithm of calculation of the specialized fitness function and the options of step-by-step search of the global strategy of distribution of tasks, which make it possible to increase the efficiency of the use of the team of robots due to the guaranteed production of the result while minimizing the total time of completion of all the tasks, as well as to increase the working time of the team due to the correct energy consumption.
About the Authors
O. V. Darintsev
USATU; Mavlyutov Institute of Mechanics, Ufa Investigation Center, R. A.S.
Russian Federation
D. Sc., Ufa, 450077, Russian Federation; Ufa, 450054, Russian Federation
Russian Federation
D. Sc., Ufa, 450077, Russian Federation; Ufa, 450054, Russian Federation
A. B. Migranov
Mavlyutov Institute of Mechanics, Ufa Investigation Center, R. A.S.
Russian Federation
Сand. Sc., Ufa, 450054, Russian Federation
Russian Federation
Сand. Sc., Ufa, 450054, Russian Federation
References
1. James Dwight McLurkin. Analysis and Implementation of Distributed Algorithms for Multi-Robot Systems: Dissertation, Massachusetts Institute of Technology, 2008, 166 p.
2. Zhu Hua. Control of the movement of a group of mobile robots in a system of the type "convoy": Dissertation for the degree of candidate of technical sciences, Zhu Hua, Moscow, 2018, 108 p. (in Russian).
3. Glasius R., Komoda A., Gielen S. Neural Network Dynamics for Path Planning and Obstacle Avoidance, Neural Networks, 1995, no. 8 (1), pp. 125—133.
4. Ziemke T. Adaptive behavior in autonomous agents, Presence, 2003, no. 7(6), pp. 564—587.
5. Kruglikov S. V., Kruglikov A. S. An a priori planning of joint motions for USV as a problem of guaranteed control/estimation, Applied Mechanics and Materials. TransTech Publications, Switzerland, 2014, vol. 494—495, pp. 1110—1113.
6. Darintsev O. V. The use of advanced and virtual reality technologies in the implementation of algorithms for managing a team of robots, Piece Intelligence, 2013, no. 3, pp. 479—487.
7. Renzaglia A. A., Martinelli A. Potential field based approach for coordinate exploration with a multi-robot team, 8th IEEE International Workshop on Safety, Security and Rescue Robotics (SSRR), doi: 10.1109/SSRR.2010.5981557.
8. Renzaglia A. Cognitive-based adaptive control for cooperative multi-robot coverage, IEEE International Conference on Robotics and Intelligent System (IROS), 2010, doi: 10.1109/IROS.2010.5649249.
9. Darintsev O. V., Migranov A. B. Distributed control system of mobile robots groups, Vestnik USATU, 2017, vol. 21, no. 2 (76), pp. 88—94 (in Russian).
10. Gary M., Johnson D. Computers and inaccessible tasks, Moscow, Mir, 1982, 416 p. (in Russian).
11. Ni M., Yu Z., Ma F., Wu X. A Lagrange Relaxation Method for Solving Weapon-Target Assignment Problem, Hindawi Publishing Corporation Mathematical Problems in Engineering, 2011, vol. 1, pp. 1—10.
12. Liu B., Qin Z., Wang R., Gao Y-B., Shao L-P. A Hybrid Heuristic Ant Colony System for Coordinated Multi-Target Assignment, Information Technology Journal, 2009, vol. 8, no. 2, pp. 156—164.
13. Darintsev O. V., Migranov A. B. Applications of approximate and intelligent trajectory planning methods for groups of mobile robots, Scientific Review. Technical science, 2015, no. 1, pp. 150—151, available at: https://science-engineering.ru/ru/article/view?id=973 (date of access: 13/08/2020) (in Russian).
14. Darintsev O. V., Migranov A. B. Comparative analysis of intelligent planning methods, Proceedings of the R. R. Mavlyutov Institute of mechanics of the Ufa scientific center of the Russian Academy of Sciences, 2012, vol. 9, no. 2, pp. 53—58 (in Russian).
15. Wilkins J. 3 technologies for energy efficient robots, EU Automation. 24 august 2017, available at: https://www.automation. com/automation-news/article/3-technologies-for-energy-efficientrobots (access date: 03/05/2019).
16. Mazumdar A. Parallel elastic elements improve energy efficiency on the STEPPR Bipedal walking robot, IEEE/ASME Transactions on Mechatronics, 2016, no. SAND2016—11799J, pp. 1—11.
17. Liu W., Winfield A. F., Sa J., Chen J, Dou L. Towards energy optimization: emergent task allocation in a swarm of foraging robots, Adaptive behavior, 2007, vol. 15, no. 3. pp. 289—305.
18. Yan Z., Fabresse L., Laval J., Bouraqadi N. Team size optimization for multi-robot exploration, 4th international conference on simulation, modeling and programming for autonomous robots (SIMPAR 2014), Springer, 2014, pp. 554—565.
19. Yan Z., Fabresse L., Laval J., Bouraqadi N. Building a ROS-based testbed for realistic multi — robot simulation: taking the exploration as an example, Robotics, 2017, vol. 6, iss. 21. pp. 1—21.
20. Gong D., Yan J., Zuo G. A review of gait optimization based on evolutionary computation, Applied computational intelligence and soft computing, 2010, Article ID 413179, pp. 1—12.
21. Darintsev O. V. and Migranov A. B. The Use of Genetic Algorithms for Distribution of Tasks in Groups of Mobile Robots with Minimization of Energy Consumption, 2019 International Multi-Conference on Industrial Engineering and Modern Technologies (FarEastCon), Vladivostok, Russia, 2019, pp. 1—6, doi:10.1109/FarEastCon.2019.8934927.
22. Darintsev O., Migranov A. Task Distribution Module for a Team of Robots Based on Genetic Algorithms: Synthesis Methodology and Testing, 2019 XXI International Conference Complex Systems: Control and Modeling Problems (CSCMP), Samara, Russia, 2019, pp. 296—300, doi: 10.1109/CSCMP45713.2019.8976649.
23. Darintsev O. V., Migranov A. B., Yudintsev B. S. Neural network algorithm for trajectory planning for a group of mobile robots, Artificial Intelligence, 2011, vol. 1, pp. 154—160 (in Russian).
Review
For citations:
Darintsev O.V., Migranov A.B. A Step-by-Step Algorithm for Finding the Optimal Strategy for the Behavior of a Group of Robots. Mekhatronika, Avtomatizatsiya, Upravlenie. 2020;21(12):689-695. (In Russ.) https://doi.org/10.17587/mau.21.689-695
Views:
684
.png)
Email this article 