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

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