Важной задачей при создании информационно-управляющей системы для обеспечения автономной навигации беспилотных летательных аппаратов (БПЛА) в условиях отсутствия спутниковой связи является формирование локальной траектории движения при наличии препятствий (деревья, линии электропередач и др.). Целью исследования является разработка эвристических алгоритмов, обеспечивающих оптимизацию локальной траектории БПЛА с использованием данных LiDAR и построения допустимой локальной траектории на основе паттернов огибания препятствий. Предложена концепция, основанная на двух этапах: декомпозиция облака точек LiDAR в виде ориентированных ограничивающих параллелепипедов (OBB) и формирование траектории обхода OBB с использованием геометрических паттернов. На первом этапе реализован классический (геометрический) конвейер обработки LiDAR-данных: воксельное прореживание, выделение плоскости земли методом RANSAC, кластеризация DBSCAN и построение параллелепипедов вокруг кластеров. Данный подход реализован в виде программного модуля на языке Python. Выполнено моделирование для двух сценариев. Первый сценарий содержал 3 препятствия, одно из которых являлось одиночным, а второе и третье располагались рядом в группе. Сгенерированная траектория позволила выполнить обход всех препятствий, время построения траектории составило 0,29 миллисекунд. Второй сценарий выполнен для набора OBB, полученных в результате декомпозиции облака точек, общее количество препятствий вместе с «землёй» составило 678. Время выполнения построения траектории в этом случае составило 0,377 секунд. Подход обеспечивает предсказуемое быстродействие и линейную оценку вычислительной сложности по числу препятствий, что делает его перспективным для применения в системах автономной навигации и управления движением БВС.
