АЛГОРИТМ ПОСТРОЕНИЯ ТРАЕКТОРИИ ДВИЖЕНИЯ БЕСПИЛОТНЫХ АППАРАТОВ ДЛЯ МОНИТОРИНГА СОСТОЯНИЯ СЕЛЬСКОХОЗЯЙСТВЕННЫХ ПОЛЕЙ

Аннотация

Организация непрерывного мониторинга значительных пространств с динамически меняющимися условиями и обстановкой является одной ключевых задач в различных направ- лениях жизнедеятельности человека. Особо остро эта задача стоит в России с учетом ее территорий (земель), предназначенных для сельскохозяйственной деятельности. Особую важность организации непрерывного мониторинга подчеркивает и развитие концепции и технологий точного земледелия. В качестве средств для решения этой системной задачи могут использоваться различные робототехнические и беспилотные системы, оснащенные необходимым оборудованием в соответствии с локальными задачами непрерывного монито- ринга. Непрерывный мониторинг при этом может быть обеспечен только применением эффективных алгоритмов построения траектории движения используемых подвижных ро- бототехнических и беспилотных (в первую очередь авиационных) систем. Повышение эф- фективности таких алгоритмов с математической точки зрения всегда усложняется цик- личностью траекторий движения, т.е. построением гамильтонова цикла. В рамках данной работы предлагается метод конструирования оптимальной траектории движения при вы- полнении задач непрерывного циклического мониторинга сельскохозяйственных полей. Метод основан на поиске гамильтонова цикла на графе карты местности и позволяет автоматиче- ски строить оптимальный замкнутый путь для произвольной карты местности. Отличи- тельной особенностью метода является использование модифицированного алгоритма поис- ка гамильтонова цикла. Алгоритм может быть масштабирован для карт, соответствую- щих графам с большим (более 100) количеством вершин, для которых стандартный алго- ритм поиска гамильтонова цикла методом перебора требует значительно большего времени выполнения, чем предложенный алгоритм. Показано, что используемый алгоритм обладает в 17 раз меньшей константой роста временной сложности, чем стандартный алгоритм поис- ка гамильтонова цикла. Это позволяет увеличить количество вершин графа, используемого для поиска гамильтонова цикла в режиме реального времени (от 0.1 до 100 секунд), на поря- док (от 30 до 500). Разработанный алгоритм может быть внедрён в современные беспилот- ные системы мониторинга состояния сельскохозяйственных полей для оптимизации траек- тории движения беспилотных аппаратов в режиме реального времени (0.1-100 секунд), внося тем самым вклад в динамично развивающуюся область точного земледелия.