РАЗРАБОТКА ЭВРИСТИЧЕСКИХ АЛГОРИТМОВ ОПТИМИЗАЦИИ ЛОКАЛЬНОЙ ТРАКТОРИИ БПЛА НА ОСНОВЕ ПАТТЕРНОВ ОГИБАНИЯ ПРЕПЯТСТВИЙ
Аннотация
Важной задачей при создании информационно-управляющей системы для обеспечения автономной навигации беспилотных летательных аппаратов (БПЛА) в условиях отсутствия спутниковой связи является формирование локальной траектории движения при наличии препятствий (деревья, линии электропередач и др.). Целью исследования является разработка эвристических алгоритмов, обеспечивающих оптимизацию локальной траектории БПЛА с использованием данных LiDAR и построения допустимой локальной траектории на основе паттернов огибания препятствий. Предложена концепция, основанная на двух этапах: декомпозиция облака точек LiDAR в виде ориентированных ограничивающих параллелепипедов (OBB) и формирование траектории обхода OBB с использованием геометрических паттернов. На первом этапе реализован классический (геометрический) конвейер обработки LiDAR-данных: воксельное прореживание, выделение плоскости земли методом RANSAC, кластеризация DBSCAN и построение параллелепипедов вокруг кластеров. Данный подход реализован в виде программного модуля на языке Python. Выполнено моделирование для двух сценариев. Первый сценарий содержал 3 препятствия, одно из которых являлось одиночным, а второе и третье располагались рядом в группе. Сгенерированная траектория позволила выполнить обход всех препятствий, время построения траектории составило 0,29 миллисекунд. Второй сценарий выполнен для набора OBB, полученных в результате декомпозиции облака точек, общее количество препятствий вместе с «землёй» составило 678. Время выполнения построения траектории в этом случае составило 0,377 секунд. Подход обеспечивает предсказуемое быстродействие и линейную оценку вычислительной сложности по числу препятствий, что делает его перспективным для применения в системах автономной навигации и управления движением БВС.
Список литературы
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.
