DEVELOPMENT OF HEURISTIC ALGORITHMS FOR OPTIMIZING THE LOCAL TRACTORY OF UAVS BASED ON OBSTACLE AVOIDANCE PATTERNS
Abstract
A key challenge in developing an information and control system for autonomous navigation of unmanned aerial vehicles (UAVs) in the absence of satellite communications is the generation of a local trajectory in the presence of obstacles (trees, power lines, etc.). The goal of this study is to develop heuristic algorithms that optimize the UAV's local trajectory using LiDAR data and construct a feasible local trajectory based on obstacle avoidance patterns. A two-stage concept is proposed: decomposing the LiDAR point cloud into oriented bounding boxes (OBBs) and generating a trajectory for traversing the OBBs using geometric patterns. The first stage implements a classic (geometric) LiDAR data processing pipeline: voxel thinning, ground plane extraction using the RANSAC method, DBSCAN clustering, and constructing bounding boxes around the clusters. This approach is implemented as a Python software module. Simulations were performed for two scenarios. The first scenario contained three obstacles, one of which was isolated, while the second and third were located in a group. The generated trajectory avoided all obstacles, with a trajectory construction time of 0.29 milliseconds. The second scenario was performed for a set of obstructions obtained by point cloud decomposition; the total number of obstacles, including the ground, was 678. [This is a fragment of the original text. The trajectory construction time in this case was 0.377 seconds. This approach provides predictable performance and a linear computational complexity estimate based on the number of obstacles, making it promising for use in autonomous navigation and UAV motion control systems
References
1. Lee S., An S., Kim J., et al. Grid-Based DBSCAN Clustering Accelerator for LiDAR’s Point Cloud, Electronics, 2024, Vol. 13, No. 17, pp. 3395.
2. Lyu W., Ke W., Sheng H., et al. Dynamic Downsampling Algorithm for 3D Point Cloud Map Based on Voxel Filtering, Applied Sciences, 2024, Vol. 14, No. 8, pp. 3160.
3. Xu Y., So Y., Woo S. Plane Fitting in 3D Reconstruction to Preserve Smooth Homogeneous Surfaces, Sensors, 2022, Vol. 22, No. 23, pp. 9391.
4. Wang J., Ding J., Guo H., et al. Mask OBB: A Semantic Attention-Based Mask Oriented Bounding Box Representation for Multi-Category Object Detection in Aerial Images, Remote Sensing, 2019, Vol. 11, No. 24, pp. 2930.
5. Seidaliyeva U., Ilipbayeva L., Utebayeva D., et al. LiDAR Technology for UAV Detection: From Fun-damentals and Operational Principles to Advanced Detection and Classification Techniques, Sensors, 2025, Vol. 25, No. 9, pp. 2757.
6. Duyun I.A., Duyun T.A., Rybak L.A. Modelirovanie dinamiki dvizheniya gruppy dronov s primeneniem otkrytoy platformy gym-pybullet-drones [Modeling the dynamics of a group of drones using the open platform gym-pybullet-drones], Vestnik Belgorodskogo gosudarstvennogo tekhnologicheskogo universi-teta im. V.G. Shukhova [Bulletin of the Belgorod State Technological University named after V.G. Shu-khov], 2025, No. 5, pp. 137-148.
7. Rybak L.A, Pisarenko A.S., Polyakov V.M. Synthesis of a High-Level Controller for Controlling a Group of Uavs in the Gazebo Simulation Environment, Proceedings 2025 International Conference on Indus-trial Engineering Applications and Manufacturing, 2025, pp. 489-494.
8. Cherkasov V.V., Malyshev D.I., Rybak L.A. Method for localization and trajectory planning of a robotic system based on autonomous vehicles for smart farming, Aip Conference Proceedings, 2025,
Vol. 3205, No. 1: 080002.
9. Dijkstra E.W. A note on two problems in connexion with graphs, Numerische Mathematik, 1959,
Vol. 1, No. 1, pp. 269-271. DOI: 10.1007/BF01386390.
10. Wang K., Meng Z., Wang Z., Wu Z. A trajectory generation method for multi-rotor UAV based on adap-tive adjustment strategy, Applied Sciences, 2023, Vol. 13, No. 6, 3435. DOI: 10.3390/app13063435.
11. LaValle S.M. Rapidly-exploring random trees: A new tool for path planning: Tech. Rep. TR-98–11. Ames: Iowa State University, Computer Science Department, 1998.
12. LaValle S.M., Kuffner J.J. Randomized kinodynamic planning, The International Journal of Robotics Research, 2001, Vol. 20, No. 5, pp. 378-400. DOI: 10.1177/02783640122067453.
13. Lipanov I.D., Khomonenko A.D. Tekhnologii i metody planirovaniya peremeshcheniya BPLA po marsh-rutnym tochkam [Technologies and methods for planning the movement of UAVs along route points], Intellektual'nye tekhnologii na transporte [Intelligent Technologies in Transport], 2024, No. 3 (39), pp. 30-43. DOI: 10.20295/2413-2527-2024-339-30-43.
14. Debnath D., Vanegas F., Sandino J., Hawary A.F., Gonzalez F. A review of UAV path-planning algo-rithms and obstacle avoidance methods for remote sensing applications, Remote Sensing, 2024,
Vol. 16, No. 21, Art. 4019. DOI: 10.3390/rs16214019.
15. Liu M., Zhang H., Yang J., Zhang T., Zhang C., Bo L. A path planning algorithm for three-dimensional collision avoidance based on potential field and B-spline boundary curve, Aerospace Science and Tech-nology, 2024, Vol. 144, 108763. DOI: 10.1016/j.ast.2023.108763.
16. Kay T.L., Kajiya J.T. Ray tracing complex scenes, ACM SIGGRAPH Computer Graphics, 1986,
Vol. 20, pp. 269-278.
17. Xiao B., Wan L., Han X., Xi Z., Ding C., Li Q. Addressing Local Minima in Path Planning for Drones with Reinforcement Learning-Based Vortex Artificial Potential Fields, Machines, 2025, Vol. 13, Art. 600.
18. Miao F. Improved artificial potential field method for local minima, Applied and Computational Engi-neering, 2023, Vol. 10, pp. 47-54.
19. Kim J., Park S., Lee W., Kim W., Doh N., Nam C. Escaping Local Minima: Hybrid Artificial Potential Field with Wall-Follower for Decentralized Multi-Robot Navigation, 2024.
20. Bai Z. Local minimum enhanced artificial potential field method, Applied and Computational Engineer-ing, 2023, Vol. 10, pp. 150-158.
