Modeling the trajectories of a group of unmanned aerial vehicles based on the ADRRT-Connect algorithm in the problem of placing seismic sensors

Modeling the trajectories of a group of unmanned aerial vehicles based on the ADRRT-Connect algorithm in the problem of placing seismic sensors

Anton I. Saveliev
PhD in Technical Sciences, Saint Petersburg Federal Research Center of the Russian Academy of Sciences (SPC RAS), Laboratory of Autonomous Robotic Systems, Senior Research Scientist, 39, 14 line V.O., Saint Petersburg, 199178, Russia, This email address is being protected from spambots. You need JavaScript enabled to view it., ORCID: 0000-0003-1851-2699

Dmitry A. Anikin
SPC RAS, Laboratory of Autonomous Robotic Systems, Software Engineer, 39, 14 line V.O., Saint Petersburg, 199178, Russia, This email address is being protected from spambots. You need JavaScript enabled to view it., ORCID: 0009-0007-6998-5687

Vadim M. Agafonov
PhD in Physics and Mathematics, Associate Professor, LLC R-Sensors, General Director, 7A, ul. Pervomaiskaya, Dolgoprudny, Moscow region, 141700, Russia, This email address is being protected from spambots. You need JavaScript enabled to view it., ORCID: 0000-0003-1943-7504

Gennady N. Erokhin
Doctor of Physical and Mathematical Sciences, Immanuel Kant Baltic Federal University (IKBFU), 14, ul. A. Nevskogo, Kaliningrad, 236016, Russia, This email address is being protected from spambots. You need JavaScript enabled to view it., ORCID: 0000-0001-7656-9496

Received February 9, 2024

Abstract
Optimal route planning is a key aspect of successfully delivering geosensors using unmanned aerial vehicles (UAVs) to geographically distributed targets. The optimality of the route depends on the time required to plan the route and execute the flight to a target or group of targets, considering traffic safety and dynamic constraints. The trajectory calculation algorithm must always find a route, if one exists, and if it is impossible to find one, inform the operator about this circumstance. This article proposes a method based on a set of algorithms that ensure efficient distribution of targets among group members based on information about the targets and characteristics of the unmanned aerial vehicles used. The method involves constructing optimal routes considering minimizing path length, avoiding sharp turns and loops, as well as avoiding obstacles and avoiding collisions with other unmanned aerial vehicles within the group. To test the proposed method, software was developed using the ROS/Gazebo environment. The proposed method is a comprehensive solution to the problem of optimal route planning for UAVs with an emphasis on efficiency, safety, and efficiency in the context of geosensor delivery using unmanned aerial vehicles.

Key words
UAV, movement trajectories, optimal target distribution, group control, modeling.

Acknowledgements
The study was supported by the Russian Science Foundation grant No. 22-69-00231, https://rscf.ru/en/project/22-69-00231/.

DOI
10.31776/RTCJ.12303

Bibliographic description
Saveliev, A.I., Anikin, D.A., Agafonov, V.M. and Erokhin, G.N. (2024), "Modeling the trajectories of a group of unmanned aerial vehicles based on the ADRRT-Connect algorithm in the problem of placing seismic sensors", Robotics and Technical Cybernetics, vol. 12, no. 3, pp. 184-193, DOI: 10.31776/RTCJ.12303. (in Russian).

UDC identifier
004.094

References

  1. Zaitsev, D., Bryksin, V., Belotelov, K., Kompaniets, Yu. et al. (2022), “Algorithms and Measuring Complex for Classification of Seismic Signal Sources, Determination of Distance and Azimuth to the Point of Excitation of Surface Waves”, Informatics and Automation, 21, pp. 1211-1239, DOI: 10.15622/ia.21.6.5. (in Russian).
  2. Nazarova, A. and Zhai, M. (2018), “Problems of using robotic systems in earthquake rescue operations”, Robotics and Technical Cybernetics, 3(20), pp. 31-38. (in Russian).
  3. Sevostyanova, N., Lebedev, I., Lebedeva, V. and Vatamaniuk, I. (2021), “An innovative approach to automated photo-activation of crop acreage using uavs to stimulate crop growth”, Informatics and Automation, 20(6), pp. 1395–1417. (in Russian).
  4. Petrenko, V.I., Tebueva, F.B., Antonov, V.O. and Sakolchik, A.V. (2023), “Distribution of tasks in a clustered field of goals for homogeneous and heterogeneous UAV groups”, Robotics and Technical Cybernetics, 11(2), pp. 99-109. (in Russian).
  5. Spivey, M.Z. and Powell, W.B. (2004), “The dynamic assignment problem”, Transportation science, 38(4), pp. 399-419, DOI: 10.1287/trsc.1030.0073.
  6. Kuhn, H.W. (1955), “The Hungarian method for the assignment problem”, Naval research logistics quarterly, 2(1‐2), pp. 83-97, DOI: 10.1002/nav.3800020109.
  7. Zavlanos, M.M. and Pappas, G.J. (2008), “Dynamic assignment in distributed motion planning with local coordination”, IEEE Transactions on Robotics, 24(1), pp. 232-242, DOI: 10.1109/TRO.2007.913992.
  8. Ni, M., Yu, Z., Ma, F. and Wu, X. (2011), “A Lagrange relaxation method for solving weapon-target assignment problem”, Mathematical Problems in Engineering, DOI: 10.1155/2011/873292.
  9. Rockafellar, R.T. (1999), Network flows and monotropic optimization, Athena scientific, Belmont, USA.
  10. Sikanen, T., 2008. Solving weapon target assignment problem with dynamic programming. Independent research projects in applied mathematics, Vol. 32.
  11. Mukhedkar, R. and Naik, S. (2013), “Weapon target allocation problem using fuzzy model”,  J. of Application or Innovation in Engineering & Management, 2(6), pp. 279-289.
  12. Wacholder, E. (1989), “A neural network-based optimization algorithm for the static weapon-target assignment problem”, ORSA Journal on computing, 1(4), pp. 232-246.
  13. Lu, Y., Miao, W. and Li, M. (2013), “The Air Defense Missile Optimum Target Assignment Based on the Improved Genetic Algorithm”, Journal of Theoretical & Applied Information Technology, 48(2).
  14. Liu, B., Qin, Z., Wang, R., Gao, Y.B. et al. (2009), “A hybrid heuristic ant colony system for coordinated multi-target assignment”, Information Technology Journal, 8(2), pp. 156-164.
  15. Rabbani, Q., Khan, A. and Quddoos, A. (2019), “Modified Hungarian method for unbalanced assignment problem with multiple jobs”, Applied Mathematics and Computation, 361, pp. 493-498, DOI: 10.1016/j.amc.2019.05.041.
  16. Sullivan, J.C.W. and Pipe, A.G. (1998), “Path planning for redundant robot manipulators: a global optimization approach using evolutionary search”, In: SMC'98 Conference Proceedings. 1998 IEEE International Conference on Systems, Man, and Cybernetics (Cat. No. 98CH36218), 3, pp. 2396-2400, IEEE, DOI: 10.1109/ICSMC.1998.725015.
  17. Hart, P.E., Nilsson, N.J. and Raphael, B. (1968), “A formal basis for the heuristic determination of minimum cost paths”, IEEE transactions on Systems Science and Cybernetics, 4(2), pp. 100-107, DOI: 10.1109/TSSC.1968.300136.
  18. LaValle, S. (1998), “Rapidly-exploring random trees: A new tool for path planning”, Research Report 9811.
  19. Nagatani, K., Iwai, Y. and Tanaka, Y. (2001), “Sensor Based Navigation for car-like mobile robots using Generalized Voronoi Graph”, In: Proceedings 2001 IEEE/RSJ International Conference on Intelligent Robots and Systems. Expanding the Societal Role of Robotics in the the Next Millennium (Cat. No. 01CH37180), vol. 2, pp. 1017-1022, IEEE, DOI: 10.1109/IROS.2001.976302.
  20. Stentz, A. (1994), “Optimal and efficient path planning for partially-known environments”, In: Proceedings of the 1994 IEEE international conference on robotics and automation, pp. 3310-3317, IEEE, DOI: 10.1109/ROBOT.1994.351061.
  21. Le, A.T., Bui, M.Q., Le, T.D. and Peter, N. (2017), “D Lite with Reset: Improved Version of D Lite for Complex Environment”, In: 2017 First IEEE International Conference on Robotic Computing (IRC), 160-163, IEEE, DOI: 10.1109/IRC.2017.52.
  22. Karaman, S. and Frazzoli, E. (2011), “Sampling-based algorithms for optimal motion planning”, The international journal of robotics research, 30(7), pp. 846-894, DOI: 10.1177/0278364911406761.
  23. Otte, M. and Frazzoli, E. (2015), “RRTX: Real-Time Motion Planning/Replanning for Environments with Unpredictable Obstacles”, In: Algorithmic foundations of robotics XI: selected contributions of the eleventh international workshop on the algorithmic foundations of robotics, 461-478, Springer International Publishing, DOI: 10.1007/978-3-319-16595-0_27.
  24. Chen, Y. and Wang, L. (2022), “Adaptively Dynamic RRT*-Connect: Path Planning for UAVs Against Dynamic Obstacles”, In: 2022 7th International Conference on Automation, Control and Robotics Engineering (CACRE), 1-7, IEEE.
  25. Gazebo: simulation environment (2023), available at: https://gazebosim/org/home (Accessed December 12, 2023).
  26. ROS - Robotic Operating System (2023), available at: https://www/ros/org/ (Accessed December 12, 2023).
  27. Eigen (2023), available at: https://eigen.tuxfamily/org/index.php?title=Main_Page (Accessed December 12, 2023).
  28. Grid Map: Universal grid map library for mobile robotic mapping (2023), available at: https://github.com/ANYbotics/grid_map (Accessed December 12, 2023).
  29. PX4: Open Source Autopilot for Drones (2023), available at: https://px4.io/ (Accessed December 12, 2023).
  30. QGroundControl (2023), available at: https://qgroundcontrol.com/ (Accessed December 12, 2023).