СПОСОБ МОНИТОРИНГА ТЕРРИТОРИИ С ПОМОЩЬЮ БПЛА Российский патент 2024 года по МПК G05D1/00 G06F17/40 G01C21/00 

Область техники, к которой относится изобретение

Изобретение относится к летательным аппаратам, в частности к мониторингу территории с помощью беспилотного летательного аппарата.

Уровень техники

Беспилотные летательные аппараты (БПЛА, UAV), также иногда называемые беспилотниками или дронами, постепенно становятся частью повседневной жизни - они выполняют доставку грузов, различные исследования, анализ окружающего пространства, мониторинг территорий, контроль объектов, фото- и видеосъемку, используются в спасательных операциях и находят множество других применений.

Беспилотные летальные аппараты способны передвигаться автономно и помогать в выполнении тех задач, которые ранее осуществлялись людьми. Одной из важных областей использования БПЛА является сканирование объектов или территорий, что позволяет следить за их состоянием. Особенно актуальны такие задачи в сельской местности, где регулярный мониторинг объектов инфраструктуры вручную или наземными средствами затруднителен из-за значительных расстояний между ними.

Стандартные программные средства управления БПЛА предполагают установку точек траектории вручную. Но, с учетом большого объема данных, ручное размещение этих точек в последовательности требует слишком больших усилий и времени. Поэтому требуется разработка способа, позволяющего построить оптимальную траекторию, адаптированную для рассматриваемого типа БПЛА. В настоящем документе раскрывается создание и реализация этого способа.

Сущность изобретения

Согласно настоящему изобретению, раскрывается способ мониторинга территории с помощью беспилотного летательного аппарата (БПЛА), содержащий этапы, на которых:

принимают набор координат, соответствующих точкам на местности, которые необходимо облететь БПЛА;

группируют точки из принятого набора по отдельным кластерам с помощью блока кластеризации на основе алгоритма кластеризации DBScan;

для каждого кластера выполняют планирование пути следующим образом:

входящие в кластер точки соединяют между собой в виде графа без петель с помощью блока соединения точек в кластере на основе алгоритма минимального остовного дерева (MST);

выбирают начальную точку графа;

находят наиболее удаленную от исходной точку в графе в качестве конечной точки; и

планируют путь, выполняя проход по графу от начальной точки до конечной рекурсивно с помощью блока генерации пути на основе алгоритма поиска в глубину (DFS);

формируют по меньшей мере одно полетное задание для БПЛА на основе спланированного пути для каждого кластера; и

выполняют мониторинг с помощью БПЛА на основе сформированного по меньшей мере одного полетного задания.

В одном из вариантов осуществления определяют количество кластеров с учетом среднего расстояния между двумя соседними точками в упомянутом предварительно заданном наборе точек.

В одном из вариантов осуществления количество кластеров определяют таким образом, что расстояние между кластерами превышает среднее расстояние между двумя соседними точками в пределах одного кластера.

В одном из вариантов осуществления для соединения точек в граф формируют матрицу смежности для каждой точки, используя фактическое расстояние между точками в качестве весовой функции, для определения ребер графа.

В одном из вариантов осуществления при планировании пути определяют основной путь от начальной точки до конечной точки, и далее, при выполнении прохода по основному пути, когда обнаруживается, что путь разветвляется, каждую из ветвей проходят рекурсивно и продолжают проход по основному пути.

Краткое описание чертежей

На Фиг. 1 показаны точки из исходного задания, расположенные на фрагменте карты.

На Фиг. 2 показан результат этапа кластеризации.

На Фиг. 3 показан результат этапа соединения точек в кластере.

На Фиг. 4А-4Б показан результат этапа генерации пути.

На Фиг. 5 показан пример полетного задания, нанесенного на карту.

Следует понимать, что фигуры могут быть представлены схематично и не в масштабе и предназначены, главным образом, для улучшения понимания настоящего изобретения.

Подробное описание

БПЛА часто используются для картографирования, сканирования, мониторинга. При этом часто они сканируют поля, например, в сельском хозяйстве, где используются различные типы БПЛА, различные датчики или алгоритмы. Чтобы сфотографировать местность с квадрокоптера или самолета вертикального взлета и посадки (VTOL), нужны координаты местности, по которой будет пролетать самолет. В рамках настоящего изобретения подразумевается, что наборы координат таких точек известны заранее и задаются извне - например, предоставляются заказчиком. В среднем один набор координат для задач мониторинга содержит около 1000 значений долготы и широты. Эти точки могут быть отображены на карте, как показано на Фиг. 1.

Точки, представленные в примере на Фиг. 1, являются местами, где расположены столбы, удерживающие линии электропередачи. В общем случае точкой может быть любой требуемый объект, над которым необходимо пролететь в целях мониторинга - например, станок-качалка, трансформаторный шкаф, дерево в посадке и т.д. Технологическая задача заключается в отслеживании состояния этих столбов. БПЛА требуется пролететь над каждым столбом и сфотографировать его. В результате из большого количества изображений собирается единый ортофотоплан - единое изображение. Для решения задачи необходимо создать полетное задание - сгенерировать траекторию полета БПЛА. В контексте задачи траектория - это последовательность координат точек в формате, подходящем для запуска в программе управления полетом. Предполагается, что БПЛА перемещается от точки к точке по кратчайшему пути с поправкой на динамические возможности аппарата.

Стандартные программные средства управления квадрокоптером предполагают установку точек траектории вручную. Но, с учетом большого объема данных, ручное размещение этих точек в последовательности требует слишком больших усилий и времени. Поэтому актуальна разработка способа, позволяющего построить оптимальную траекторию, адаптированную для рассматриваемого типа БПЛА. В настоящем документе раскрывается создание и реализация этого способа.

С точки зрения математики задача сводится к поиску оптимального маршрута. Критерием оптимизации при преобразовании набора точек в последовательность является минимизация суммарной длины маршрута. Поставленная задача является NP-полной, то есть оптимальное решение может быть достигнуто только полным перебором, что невозможно для исходного количества точек, особенно с учетом того, что каждая точка независима от других. Таким образом, на практике приходится решать задачу приближенно.

Известно несколько алгоритмов для нахождения приблизительного оптимального пути, однако ни один из них в неизменном виде не подходит для оптимального решения требуемой задачи. В настоящем изобретении предлагается новый способ планирования пути для БПЛА, повышающий точность планирования и обеспечивающий снижение времени и ресурсов на полный облет всех точек.

Коротко, предложенный способ содержит следующие этапы. Первоначально данные группируются с помощью DBScan, поскольку полетов может быть несколько. Затем для каждого кластера будет найдено MST, чтобы определить минимальный граф, который затем передается в DFS на заключительном этапе.

Далее предложенный способ будет описан более подробно.

DBscan

После нанесения всех точек на график в вышеупомянутом примере стало заметно, что они расположены на таком расстоянии друг от друга, которое используемые беспилотники не смогли бы покрыть за один полет, поэтому в любом случае набор точек должен быть разделен на несколько полетных заданий. Для этого используется алгоритм кластеризации. В рассматриваемом случае это DBScan, который хорошо зарекомендовал себя в задачах такого типа. Этот алгоритм способен объединять множество близко расположенных точек в единый кластер. Все кластеры, идентифицированные с помощью DBScan в наборе данных из заданного примера, можно увидеть на Фиг. 2. Оси указывают координаты широты и долготы. Вынесенный фрагмент Фиг. 2 показывает, что кластер представляет собой набор близко расположенных точек. Каждый кластер представляет собой сегмент общей сети линий электропередачи, который необходимо сфотографировать. После кластеризации данных получается набор точек для каждого полетного задания.

Количество кластеров изначально не известно, но приблизительно известно среднее расстояние между двумя соседними точками. В среднем это расстояние составляет 25 метров для столбов в пределах одного кластера, в то время как расстояние между кластерами составляет от 6 до 100 км. Летать на такие расстояния трудно и опасно. Чтобы избежать этого, используемый алгоритм делит все данные на кластеры. Далее каждый кластер должен рассматриваться как отдельное полетное задание обработки данных.

MST

Следующим допущением предложенного изобретения является тот факт, что анализируются столбы, соединенные проводами. То есть, как правило, сеть соединенных столбов будет представлять собой дерево, или, другими словами, граф без зацикливаний. Часто используемые алгоритмы, такие как RRT, могут подойти для поставленной задачи, однако, учитывая, что эти точки на карте расположены на прямой, а ответвления появляются редко, что видно, например, на Фиг. 1, предлагается использовать менее популярный, но более подходящий алгоритм MST (minimum spanning tree) - это алгоритм для соединения всех точек в единую цепочку и минимизации расстояния между ними.

Чтобы построить траекторию, необходимо расположить все точки в последовательности, используя любой из методов построения MST - например, алгоритм Прима или алгоритм Крускала. Эти методы работают с матрицей смежности. Матрица представляет собой пустой набор данных, в которую добавляются данные о расстояниях между точками, которые представляют собой ребра графа в случае данной задачи. Таким образом, создается и заполняется матрица смежности для каждой точки, используя фактическое расстояние между точками в качестве весовой функции. Расстояния берутся из данных геобиблиотеки. На Фиг. 3 можно увидеть результаты применения алгоритма MST. Для удобства представления на Фиг. 3 и далее работа алгоритма иллюстрируется только одним кластером из многих - кластером, выделенным красным цветом на Фиг. 2, однако следует понимать, что обрабатываются все кластеры, полученные после обработки на предыдущем этапе.

В результате набор точек соединен в виде графа без петель.

Полученные данные наглядно демонстрируют, что исходные наборы точек действительно представляют дерево и в результате задача сводится к тому, чтобы обойти дерево по наиболее оптимальному пути. Важно учитывать, что на обратном пути движение по графу не требуется: имеется двумерное пространство с точками, что позволяет возвращаться из веток к их началу, не посещая те точки, в которых уже были, а наоборот, пролетая напрямую к необходимой точке.

DFS

Для построения итогового пути рассматривается дерево как диаметр и набор меньших деревьев, исходящих из этого диаметра. Это позволяет решать задачу рекурсивно, изначально выбирая начальную и конечную точки основного маршрута. После основного пути нужно обратить внимание на более мелкие участки. Чтобы завершить процесс создания полетного задания, используется алгоритм DFS. Этот алгоритм позволяет найти крайние точки и тем самым выбрать основной путь для кластера.

Сначала берется произвольная точка графа. Затем, проходя по краям графа, находятся точки, наиболее удаленные от исходной с разных сторон. На Фиг. 4A показаны результаты выделения основного пути.

На той же Фиг. 4A видно, что после нахождения основного пути остались ответвления. Чтобы добавить их к полетному заданию, осуществляется проход по основному маршруту от одного конца до другого. Когда обнаруживается, что, согласно графу, путь разветвляется, каждая из ветвей проходится рекурсивно.

Чтобы завершить создание итогового пути, осталось добавить разветвления. Для этого осуществляется проход по каждой ветви от ее начала с использованием алгоритма DFS, получая таким образом желаемый путь. Когда проход по ветви закончен, происходит возврат к началу и продолжается движение по основному пути. На Фиг. 4Б показано, что после описанного процесса полетное задание дополняется ответвлениями.

Результаты эксперимента

Исходные данные содержали около тысячи значений широты и долготы. Используя DBScan, эти точки собрали в кластеры. Алгоритм MST позволил создать граф с наименьшими возможными краями. Окончательный путь был собран с использованием алгоритма DFS.

Результатом обработки представленных данных является файл с расширением .kml. Здесь содержится информация о точках, расположенных в последовательности для выполнения полетного задания. Этот файл позволяет импортировать данные в QGroundControl или любую другую программу для работы с полетными заданиями. На Фиг. 5 показана итоговая последовательность точек, расположенных на карте - полетное задание.

В настоящем изобретении выполняется обработка большого массива точек на карте, не связанных между собой. Разработаны способы и реализовано программное обеспечение для автоматической генерации полетного задания с последовательным набором координат.

Настоящее изобретение позволяет эффективно планировать путь для прохождения с помощью БПЛА множества точек на карте, устраняя необходимость в ручном труде или в автоматическом полном переборе, при этом минимизируя время прохождения маршрута и ресурсы, необходимые для его прохождения (топливо, энергию, объем памяти и т.д.).

На базе предложенного способа планирования пути можно выполнять мониторинг. Способ мониторинга территории с помощью БПЛА содержит прием предварительно заданного набора координат, соответствующих точкам или объектам, которые необходимо облететь с помощью БПЛА в целях мониторинга, планирование пути согласно вышеописанным подходам, формирование одного или более полетных заданий на основе спланированного пути (например, согласно кластерам) и выполнение мониторинга с помощью БПЛА на основе одного или более полетных заданий.

Применение

Устройства, системы и способы согласно настоящему изобретению можно использовать для планирования пути БПЛА, чтобы БПЛА мог выполняющих доставку грузов, различные исследования, анализ окружающего пространства, контроль объектов, фото- и видеосъемку, спасательные операции, автономный мониторинг для задач охраны территорий, сельхозугодий, картографии, дистанционного химико-физического анализа, контроля всхожести и спелости урожая, химической обработки и т.д.

В частности, одним из конкретных примеров применения является анализ линий электропередач, что является важной задачей для поддержания стабильной работы сельскохозяйственных предприятий.

Также возможно применение настоящего изобретения в пилотируемых летательных аппаратах в режиме автономного движения (автопилота).

Дополнительные особенности реализации

Каждый из этапов предложенного способа реализуется с помощью соответствующего блока - блока кластеризации (на базе DBscan), блока соединения точек в кластере (на базе MST) и блока генерации пути (основного пути и пути с ответвлениями на базе DFS). Данные блоки воплощаются в программно-аппаратном виде на основе процессора и памяти, выполняющих набор команд, соответствующих действиям в рамках выполняемого этапа способа.

Различные иллюстративные блоки и модули, описанные в связи с раскрытием сущности в данном документе, могут реализовываться или выполняться с помощью процессора общего назначения, процессора цифровых сигналов (DSP), специализированной интегральной схемы (ASIC), программируемой пользователем вентильной матрицы (FPGA) или другого программируемого логического устройства (PLD), дискретного логического элемента или транзисторной логики, дискретных аппаратных компонентов либо любой комбинации вышеозначенного, предназначенной для того, чтобы выполнять описанные в данном документе функции. Процессор общего назначения может представлять собой микропроцессор, но в альтернативном варианте, процессор может представлять собой любой традиционный процессор, контроллер, микроконтроллер или конечный автомат. Процессор также может реализовываться как комбинация вычислительных устройств (к примеру, комбинация DSP и микропроцессора, несколько микропроцессоров, один или более микропроцессоров вместе с DSP-ядром либо любая другая подобная конфигурация).

Некоторые блоки или модули по отдельности или вместе могут представлять собой, например, компьютер, и включать в себя процессор, который сконфигурирован для вызова и выполнения компьютерных программ из памяти для выполнения этапов способа или функций блоков или модулей в соответствии с вариантами осуществления настоящего изобретения. Согласно вариантам осуществления, устройство может дополнительно включать в себя память. Процессор может вызывать и выполнять компьютерные программы из памяти для выполнения способа. Память может быть отдельным устройством, независимым от процессора, или может быть интегрирована в процессор. Память может хранить код, инструкции, команды и/или данные для исполнения на наборе из одного или более процессоров описанного устройства. Коды, инструкции, команды могут предписывать процессору выполнять этапы способа или функции устройства.

Функции, описанные в данном документе, могут реализовываться в аппаратном обеспечении, программном обеспечении, выполняемом посредством одного или более процессоров, микропрограммном обеспечении или в любой комбинации вышеозначенного, если это применимо. Аппаратные и программные средства, реализующие функции, также могут физически находиться в различных позициях, в том числе согласно такому распределению, что части функций реализуются в различных физических местоположениях, то есть может выполняться распределенная обработка или распределенные вычисления.

В случае если объем данных велик, может производиться многопоточная обработка данных, которая в простом представлении может выражаться в том, что все множество подлежащих обработке данных разделяется на набор подмножеств, и каждое ядро процессора выполняет обработку в отношении назначенного для него подмножества данных.

Вышеупомянутая память может быть энергозависимой или энергонезависимой памятью или может включать в себя как энергозависимую, так и энергонезависимую память. Специалисту в области техники должно быть также понятно, что, когда речь идет о памяти и о хранении данных, программ, кодов, инструкций, команд и т.п., подразумевается наличие машиночитаемого (или компьютерно-читаемого, процессорно-читаемого) запоминающего носителя. Машиночитаемый запоминающий носитель может представлять собой любой доступный носитель, который может использоваться для того, чтобы переносить или сохранять требуемое средство программного кода в форме инструкций или структур данных, и к которому можно осуществлять доступ посредством компьютера, процессора или иного устройства обработки общего назначения или специального назначения.

В качестве примера, а не ограничения, машиночитаемые носители могут содержать постоянное запоминающее устройство (ROM), программируемое постоянное запоминающее устройство (PROM), стираемое программируемое постоянное запоминающее устройство (EPROM), электронно-стираемое программируемое постоянное запоминающее устройство (EEPROM), флэш-память, оперативную память (RAM), статическую память с произвольным доступом (SRAM), динамическую память с произвольным доступом (DRAM), синхронную динамическую память с произвольным доступом (SDRAM), синхронную динамическую память с произвольной выборкой с двойной скоростью передачи данных (DDR SDRAM), синхронную динамическую память с произвольной выборкой с повышенной скоростью (ESDRAM), DRAM с синхронной линией связи (SLDRAM) и оперативную память с шиной прямого доступа (DR RAM) и т.п.

Информация и сигналы, описанные в данном документе, могут представляться с помощью любой из множества различных технологий. Например, данные, инструкции, команды, информация, сигналы, биты, символы и элементарные сигналы, которые могут приводиться в качестве примера в вышеприведенном описании, могут представляться посредством напряжений, токов, электромагнитных волн, магнитных полей или частиц, оптических полей или частиц либо любой комбинации вышеозначенного.

Процессор может включать в себя один или более процессоров. В то же время, один или более процессоров могут быть процессором общего назначения, например центральным процессором (CPU), прикладным процессором (AP) и т.п., блоком обработки графики, таким как графический процессор (GPU), визуальный процессор (VPU) и т.д.

Следует понимать, что хотя в настоящем документе для описания различных элементов, компонентов, областей, слоев и/или секций могут использоваться такие термины, как "первый", "второй", "третий" и т.п., эти элементы, компоненты, области, слои и/или секции не должны ограничиваться этими терминами. Эти термины используются только для того, чтобы отличить один элемент, компонент, область, слой или секцию от другого элемента, компонента, области, слоя или секции. Так, первый элемент, компонент, область, слой или секция может быть назван вторым элементом, компонентом, областью, слоем или секцией без выхода за рамки объема настоящего изобретения. В настоящем описании термин "и/или" включает любые и все комбинации из одной или более из соответствующих перечисленных позиций. Элементы, упомянутые в единственном числе, не исключают множественности элементов, если отдельно не указано иное.

Функциональность элемента, указанного в описании или формуле изобретения как единый элемент, может быть реализована на практике посредством нескольких компонентов устройства, и наоборот, функциональность элементов, указанных в описании или формуле изобретения как несколько отдельных элементов, может быть реализована на практике посредством единого компонента.

В одном варианте осуществления элементы/блоки/модули предложенного устройства находятся в общем корпусе, могут быть размещены на одной раме/конструкции/печатной плате/кристалле и связаны друг с другом конструктивно посредством монтажных (сборочных) операций и функционально посредством линий связи. Упомянутые линии или каналы связи, если не указано иное, являются типовыми, известными специалистам линиями связи, материальная реализация которых не требует творческих усилий. Линией связи может быть провод, набор проводов, шина, дорожка, беспроводная линия связи (индуктивная, радиочастотная, инфракрасная, ультразвуковая и т.д.). Протоколы связи по линиям связи известны специалистам и не раскрываются отдельно.

Под функциональной связью элементов следует понимать связь, обеспечивающую корректное взаимодействие этих элементов друг с другом и реализацию той или иной функциональности элементов. Частными примерами функциональной связи может быть связь с возможностью обмена информацией, связь с возможностью передачи электрического тока, связь с возможностью передачи механического движения, связь с возможностью передачи света, звука, электромагнитных или механических колебаний и т.д. Конкретный вид функциональной связи определяется характером взаимодействия упомянутых элементов, и, если не указано иное, обеспечивается широко известными средствами, используя широко известные в технике принципы.

Несмотря на то, что примерные варианты осуществления были подробно описаны и показаны на сопроводительных чертежах, следует понимать, что такие варианты осуществления являются лишь иллюстративными и не предназначены ограничивать настоящее изобретение, и что данное изобретение не должно ограничиваться конкретными показанными и описанными компоновками и конструкциями, поскольку специалисту в данной области техники на основе информации, изложенной в описании, и знаний уровня техники могут быть очевидны различные другие модификации и варианты осуществления изобретения, не выходящие за пределы сущности и объема данного изобретения.

Изобретение относится к способу мониторинга территории с помощью беспилотного летательного аппарата (БПЛА). Для мониторинга территории принимают набор координат, соответствующих точкам на местности, которые необходимо облететь БПЛА, группируют точки из принятого набора по отдельным кластерам с помощью блока кластеризации на основе алгоритма кластеризации DBScan, для каждого кластера входящие в него точки соединяют между собой в виде графа без петель с помощью блока соединения точек в кластере на основе алгоритма минимального остовного дерева (MST), выбирают начальную точку графа, находят наиболее удаленную от исходной точку в графе в качестве конечной точки и планируют путь, выполняя проход по графу от начальной точки до конечной рекурсивно с помощью блока генерации пути на основе алгоритма поиска в глубину (DFS), формируют по меньшей мере одно полетное задание для БПЛА на основе спланированного пути для каждого кластера, и выполняют мониторинг с помощью БПЛА на основе сформированного по меньшей мере одного полетного задания. Обеспечивается построение оптимальной траектории, адаптированной для рассматриваемого типа БПЛА. 4 з.п. ф-лы, 6 ил.

1. Способ мониторинга территории с помощью беспилотного летательного аппарата (БПЛА), содержащий этапы, на которых:

принимают набор координат, соответствующих точкам на местности, которые необходимо облететь БПЛА;

группируют точки из принятого набора по отдельным кластерам с помощью блока кластеризации на основе алгоритма кластеризации DBScan;

для каждого кластера выполняют планирование пути следующим образом:

входящие в кластер точки соединяют между собой в виде графа без петель с помощью блока соединения точек в кластере на основе алгоритма минимального остовного дерева (MST);

выбирают начальную точку графа;

находят наиболее удаленную от исходной точку в графе в качестве конечной точки; и

планируют путь, выполняя проход по графу от начальной точки до конечной рекурсивно с помощью блока генерации пути на основе алгоритма поиска в глубину (DFS);

формируют по меньшей мере одно полетное задание для БПЛА на основе спланированного пути для каждого кластера; и

выполняют мониторинг с помощью БПЛА на основе сформированного по меньшей мере одного полетного задания.

2. Способ по п. 1, в котором определяют количество кластеров с учетом среднего расстояния между двумя соседними точками в упомянутом предварительно заданном наборе точек.

3. Способ по п. 2, в котором количество кластеров определяют таким образом, что расстояние между кластерами превышает среднее расстояние между двумя соседними точками в пределах одного кластера.

4. Способ по п. 1, в котором для соединения точек в граф формируют матрицу смежности для каждой точки, используя фактическое расстояние между точками в качестве весовой функции, для определения ребер графа.

5. Способ по п. 1, в котором при планировании пути определяют основной путь от начальной точки до конечной точки, и далее, при выполнении прохода по основному пути, когда обнаруживается, что путь разветвляется, каждую из ветвей проходят рекурсивно и продолжают проход по основному пути.