Разработка программного обеспечения для построения оптимальной траектории движения сельскохозяйственной техники

АННОТАЦИЯ

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

ABSTRACT

In the article the process of creating software aimed at solving the lack of an optimal plan of agricultural field processing is considered, as well as the lack of control over the implementation of this plan. As a result of this work the software has been created allowing the agronomist to trace the motion trajectory of agricultural machinery in fields of both simple and complex configuration with semi-automatic and automatic mode.

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

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

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

Создание программы было произведено посредством кроссплатформенной программной платформы Qt 4.7, в котором главным преимуществом является возможность использования удобного графического интерфейса, путем подключения заранее созданных библиотек. Архитектура разрабатываемого программного обеспечения построена на системе плагинов. Данная система позволяет добавлять в программу различные модули, необходимые для реализации задачи научно исследовательской работы. Такими модулями, к примеру, являются: модуль получения координат узлов поля, модуль создания траектории обработки поля, модуль корректировки траектории и так далее.

Затем, после создания основополагающей части программного обеспечения, разработка переключилась на вопрос оцифровки поля [4,7]. Данный вопрос неоднократно обсуждался командой разработчиков. В конечном итоге был сделан вывод о том, что для создания алгоритма обработки полей и его тестирования достаточно получить географические координаты узлов поля (формат широта долгота с точностью до 6 знаков после запятой), затем реализовать на этой основе модуль, который будет считывать данные из программного обеспечения "Автограф", записывать эти данные в определенной последовательности в текстовый файл, который в свою очередь будет являться входным данным при подключения данного модуля к основному программному обеспечению. Данное решение является наиболее рациональным, так как главной задачей является создание траектории на любом участке, заданным координатным способом. В последствии, при установке программного обеспечения на технику заказчика, будет производится более качественная оцифровка с введением локальных координат, целью которых является уменьшение погрешности до 1-2 см, ведь при использовании географических координат точность определения положения достигает порядка 6км, что неприемлемо для данной разработки [8,9]. При использовании локальных координат на выходе модуля составления координат узлов поля, мы также получаем упорядоченный текстовый файл. Это говорит о универсальности алгоритма модуля составления координат. Таким образом, после подключения данного модуля, на главном окне приложения мы видим карты с необходимыми узлами, на которых в последствии мы реализовали траекторию.

Описание алгоритма: на вход подается поле как вектор точек с произвольным обходом (левым/правым).Отрезки, образующие контур, делятся на группы по углу, образуемому с осью абсцисс или же осью ординат. Группа — подмножество отрезков исходного контура, угол которых разнится максимум на заданную величину эпсилон. Каждая группа обладает весом (понятие, вычисляемое суммарной длинной всех отрезков группы). Затем выбирается направление разбиения (на данный момент это среднее направление группы, обладающей максимальным весом). Далее поле разбивается на загоны — участки у которых есть свои "входы", "выходы", разворотные полосы и на которых, собственно, строятся траектории. Загонов может быть несколько типов (например, прямоугольные, овальные), под каждый из которых написана своя реализация составления траектории. Разбиение происходит так: идем по контуру так, что поле находится слева от нас, если натыкаемся на узел – "впуклость", тогда выпускаем из него делящий луч по выбранному направлению разбиения, ищем точки пересечения с существующим контуром, вставляем их в контур вместе с ребрами разбиения. Затем выделяем из получившегося плоского графа грани повторным обходом, которые и являются загонами. Затем, строится граф, вершинами в котором являются все возможные "входы" и "выходы" загонов, траектория внутри загона тоже считается одной вершиной. Ребра — минимальные стоимости переезда между вершинами. Задача поиска оптимальной по длине траектории сводится к поиску кратчайшего гамильтонова пути в этом графе. Данная задача, в основном решаем с помощью эвристики, если же число вершин позволяет, то полным перебором.

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

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

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

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

Таким образом, процесс работы на втором этапе разработки включал в себя частичную перестройку структуры алгоритма, связанную с накоплением ошибки погрешности расчетов, в последствии из-за чего происходил некачественный расчет траектории, сбой программы.

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

Рисунок 1. Построение траектории на полях с прямоугольной конфигурацией

Данный путь был построен за 18 секунд при ширине сеялки в 20 метров. Таким образом, реализация алгоритма кругового построения траектории на полях простой конфигурацией является выполненной. Алгоритм построения траектории не является ресурсоемким процессом, как вывод соответствует всем минимальным системным характеристикам среднестатистического персонального компьютера.

Следующим шагом было испытание данного алгоритма на полях сложной конфигурации. При использовании данного алгоритма на северных полях хозяйств Омской области, обладающий весьма сложной геометрией, были получены не совсем благоприятные результаты. На местах сложных разворотов алгоритм переходил за границы поля, как вывод был сбой программы. Последующая оптимизация и устранение ошибок не дало положительных результатов и, как вывод, область применимости данного алгоритма ограничилась полями простой конфигурации, географически расположенных в Центральном, Приволжском, Южном федеральных округах. Процентная доля полей простой конфигурации составляет порядка 70 процентов относительно всех сельскохозяйственных полей Российской Федерации.

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

Описание полуавтоматического алгоритма: все пространство разбивается на квадраты определенного размера, в этом пространстве задается начальная координата (x, y, theta) и конечная. Имеется «statelattice» состоящий из набора элементарных движений вида: start_theta, end_x, end_y, end_theta а также цены данного движения, здесь координаты относительные, т.е. начало всегда (0,0,start_theta), конец (end_x, end_t, end_theta).

Далее реализуется некоторый графовый алгоритм. Проведем сравнительный анализ наиболее подходящих алгоритмов для реализации поставленной задачи [10]:

   1.  Алгоритм поиска А* (прима)

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

Рисунок 2. Пример нахождения  оптимального пути при помощи алгоритма А*

   2.  Алгоритм Дейкстры

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

Рисунок 3. Пример нахождения  оптимального пути при помощи алгоритма Дейкстры

Время сходимости алгоритма пропорциональной числу препятствий на карте.

    3. Jump Point Search (прыжковые точки)

Улучшенная версия алгоритма поиска пути A*. Отличие состоит в том, что ускорение поиска пути достигается благодаря «перепрыгиванию» точек, которые исключаются из расчёта. Такие точки описываются двумя правилами выбора соседей в процессе рекурсивного поиска: отдельное правило обработки при прямолинейном движении и отдельное – для диагонального. По сравнению с похожими алгоритмами, в данном алгоритме не требуется предварительная обработка и разметка карты, что приводит к существенному снижению требований по величине доступной памяти. Каждая точка на карте (карта занятости пространства) имеет не более 8(восьми) соседей, которые могут являться либо препятствием, либо пустые, т.е. свободны для прохождения. Шаг по по вертикали/горизонтали имеет стоимость 1; шаг по диагонали – 1,414. Движение сквозь препятствия запрещено.

Рисунок 4. Пример нахождения оптимального пути при помощи алгоритма Jump Point Search

Для поставленной задачи планирования маршрута передвижения наиболее подходит алгоритм Jump Point Search , так как он быстрее и эффективнее алгоритма А* и от количества препятствий на карте его скорость работы практически не зависит.

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

Данный алгоритм строит траекторию по типу «змейки». Основным преимуществом данного алгоритма по отношению к алгоритму круговой траектории является возможность редактирования и частичного управления процессом, а также гибкая возможность использования на полях любой конфигурации [5].

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

Рисунок 5. Построение траектории с использованием алгоритма типа «змейка»

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