METHOD OF SPATIAL-TEMPORAL DIVERSITY OF TRAJECTORIES OF A GROUP OF ROBOTS IN THE CONTEXT OF OBSTACLES
Abstract
When developing algorithms for planning the paths of robots forming a group, the problem of ensuring that they do not collide with each other and with possible obstacles arises. In addition, the group may be required to maintain a given formation template in those sections of the group's movement where this is possible taking into account obstacles. However, a narrow spatial corridor of permissible movement of the group is often formed, which can be caused by both the initial requirements for the trajectory (for example, the condition of its location in a certain vicinity of a given point), and the presence of obstacles and other interference effects. The presence of such a restrictive corridor can lead to a forced convergence and even intersection of the spatial trajectories of movement of individual robots in the group. One possible solution to this problem is to specify or adjust the time parametric representations of these individual trajectories so that two robots with spatial trajectories approaching each other are at their closest points at different times. Moreover, the time interval separating the moments of these two robots being at these points should be selected depending on the speed of the robots and their dimensions. The developed method of space-time separation of the trajectories of individual robots in a group is based on this idea. The method involves the formation and solution of a special linear programming problem relative to the target moments of time of previously selected nodes of the spatial trajectory of each slave robot. The limiting factor for changing these moments is the maximum possible speed of the robot. For each robot, a preliminary selection of a set of trajectories of other robots in the group is made, from which it is then necessary to detach in space-time. This occurs depending on the priority of the robots in the group. Examples of numerical implementation of the algorithm based on the proposed method are given, confirming its effectiveness
References
1. Sun F., Li H.,·Zhu W.,·Kurths J. Fixed-time formation tracking for multiple nonholonomic wheeled mo-bile robots based on distributed observer, Nonlinear Dynamics, 2021, Vol. 106, pp. 3331-3349.
2. Dong X., Yu B., Shi Z., Zhong Y. Time-Varying Formation Control for Unmanned Aerial Vehicles: The-ories and Applications, IEEE Transactions on Control Systems Technology, Vol. 23 (1), pp. 340-348.
3. Arteaga-Escamilla C.M., Castro-Linares R., Álvarez-Gallegos J. Leader–follower formation with re-duction of the off-tracking and velocity estimation under visibility constraints, International Journal of Advanced Robotic Systems, 2021, Vol. 18 (610).
4. Bezruk G.G., Martynova L.A., Saenko I.B. Dinamicheskiy metod poiska antropogennykh ob"ektov v morskom dne s ispol'zovaniem avtonomnykh neobitaemykh podvodnykh apparatov [Dynamic method of searching for anthropogenic objects in the seabed using autonomous uninhabited underwater vehi-cles], Tr. SPIIRAN [SPIIRAS Proceedings], 2018, Vol. 3 (58), pp. 203-226.
5. Pack D.J., DeLima P., Toussaint G.J., York G. Cooperative control of UAVs for localization of inter-mittently emitting mobile targets, IEEE Transactions on Systems, Man, and Cybernetics, Part B, 2009, Vol. 39 (4), pp. 959-970.
6. Shepeta A.P., Nenashev V.A. Tochnostnye kharakteristiki opredeleniya koordinat ob"ektov v dvu-khpozitsionnoy sisteme malogabaritnykh bortovykh RLS [Accuracy characteristics of object location in a two-position system of small onboard radars], Informatsionno-upravlyayushchie sistemy [Information and Control Systems], 2020, Vol. 2, pp. 31-36.
7. Nenashev V.A.; Khanykov I.G. Formation of Fused Images of the Land Surface from Radar and Optical Images in Spatially Distributed On-Board Operational Monitoring Systems, Journal of Imaging, 2021, Vol. 7 (251).
8. Nenashev V.A., Khanykov I.G. Formirovanie kompleksnogo izobrazheniya zemnoy poverkhnosti na osnove klasterizatsii pikseley lokatsionnykh snimkov v mnogopozitsionnoy bortovoy sisteme [For-mation of a fused image of the land surface based on pixel clustering of location images in a multi-position onboard system], Informatika i avtomatizatsiya [Informatics and Automation], 2021, Vol. 20, No. 2, pp. 302-340.
9. Martynova L.A. Metod effektivnogo uderzhaniya polozheniya ANPA na marshrutnoy traektorii pri vedenii seysmorazvedki [Features of ABBA Group management during seismic exploration], Infor-matsionno-upravlyayushchie sistemy [Information and Control Systems], 2018, Vol. 3, pp. 34-44.
10. Martynova L.A., Konyukhov G.V., Pashkevich I.V., Rukhlov N.N. Osobennosti gruppovogo upravleniya ANPA pri vedenii seysmorazvedki [Features of ABBA Group management during seismic exploration], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2017, No. 9 (194), pp. 21-33.
11. Kostjukov V., Medvedev M., Pshikhopov V. Method for optimizing of mobile robot trajectory in repeller sources field, Informatics and Automation, 2021, Vol. 20 (3), pp. 690-726.
12. Kostyukov V.A., Medvedev M.YU., Pshikhopov V.Kh. Algoritm planirovaniya puti v dvukhmernoy srede s poligonal'nymi prepyatstviyami na klasse kusochno-lomanykh traektoriy [Path planning algorithm in a two-dimensional environment with polygonal obstacles on a class of piecewise-broken trajectories], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2023, No. 5 (235), pp. 34-48.
13. Ferguson D., Stentz A. Using interpolation to improve path planning: The field D* algorithm, J. of Field Robotics, 2006, Vol. 23, No. 2, pp. 79-101. DOI: 10.1002/rob.20109.
14. Daniel K., Nash A., Koenig S., Felner A. Theta*. Any-angle path planning on grids, J. of Artificial Intel-ligence Research, 2010, Vol. 39, p. 533-579. DOI: 10.1613/jair.2994.
15. Guibas L.J., Knuth D.E., Sharir M. Randomized incremental construction of Delaunay and Voronoi diagrams, Algorithmica, 1992, 7 (1), pp. 381-413.
16. Morozova N.S. Virtual'nye formatsii i virtual'nye lidery v zadache o dvizhenii stroem gruppy robotov [Virtual formations and virtual leaders in the problem of the motion of a group of robots in formation], Vestnik Sankt-Peterburgskogo universiteta. Seriya 10. Prikladnaya matematika. Informatika. Protsessy upravleniya [Bulletin of St. Petersburg University. Series 10. Applied Mathematics. Computer Science. Control Processes], 2015, No. 1, pp. 135-149.
17. Kantorovich L.V., Krylov V.I. Priblizhennye metody vysshego analiza [Approximate methods of higher analysis]. Moscow-Leningrad: Gos. izd-vo fiz.-mat. literatury, 1962, 708 p.
18. Kostyukov V.A., Medvedev M.Yu., Pshikhopov V.Kh. Algoritmy planirovaniya sglazhennykh individu-al'nykh traektoriy dvizheniya nazemnykh robotov [Algorithms for planning smoothed individual trajecto-ries of ground robots], Mekhatronika, avtomatizatsiya, upravlenie [Mechatronics, Automation, Control], 2022, Vol. 23, No. 11, pp. 585-595.
19. Kostyukov V.A., Medvedev M.Yu., Pshikhopov V.Kh. Planirovanie dvizheniya nazemnykh robotov v srede s prepyatstviyami: algoritmy postroeniya traektoriy v gruppe pri zadannom shablone [Motion planning of ground robots in an environment with obstacles: algorithms for constructing trajectories in a group for a given template], Mekhatronika, avtomatizatsiya, upravlenie [Mechatronics, Automation, Control], 2023, No. 01.
20. Pshikhopov V.Kh., Medvedev M.Yu. Detsentralizovannoe upravlenie gruppoy odnorodnykh podvizhnykh ob"ektov v dvumernoy srede s prepyatstviyami [Decentralized control of a group of homogeneous mov-ing objects in a two-dimensional environment with obstacles], Mekhatronika, avtomatizatsiya, uprav-lenie [Mechatronics, Automation, Control], 2016, Vol. 17 (5), pp. 346-353
