Интеллектуальная
Маршрутизация

Обзор

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

Моделирование разворотов

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

Соединители полоса-полоса

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

U-образный разворот

Когда радиус поворота меньше 50% ширины захвата, для соседних полос будут сгенерированы U-образные развороты, как этот. Существует параметр для удлинения прямого сегмента до поворотной полосы, чтобы дать больше места для поворота и минимизировать уплотнение почвы.

Идеальный U-образный разворот

Когда радиус поворота равен ровно 50% ширины захвата, для соседних полос будут сгенерированы идеальные U-образные развороты, как этот, без прямого сегмента между ними.

Луковичный разворот

Когда радиус поворота больше 50% ширины захвата, для соединения двух соседних полос используется луковичный разворот. Он применяется только в случае, если U-образный разворот не подходит.

P-образный разворот

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

Соединители полоса-поворотная полоса

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

Дуговые соединители

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

Соединители Дюбена

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

Резервный соединитель

Если всё остальное не работает, мы создаём резервный соединитель, который напрямую соединяет две точки (между двумя полосами или полосой и поворотной полосой) и отображается в интерфейсе как большая красная линия. Пользователь должен выполнить этот разворот вручную перед продолжением маршрута.

Укорачивание разворотов

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

Удлинение разворотов

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

Укороченные соединения поворотной полосы

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

Без настройки

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

С настройкой

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

Навигация по поворотным полосам

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

Полные проходы по поворотным полосам

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

Предпочитать крайнюю поворотную полосу

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

Поведение по умолчанию

Проходы по поворотным полосам естественным образом прикрепляются к средней поворотной полосе.

Развороты, прикреплённые к крайней поворотной полосе

При включённой настройке "Предпочитать крайнюю поворотную полосу" все проходы по поворотным полосам прикрепляются к самой внешней поворотной полосе при наличии возможности.

Маршрутизация по нескольким внутренним полосам

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

Крестообразные проходы по поворотным полосам

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

Управляемые поворотные полосы

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

До сглаживания

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

После сглаживания

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

Алгоритмы / Шаблоны

Алгоритм по умолчанию

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

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

Избегать пропуска проходов

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

Непрерывные полосы (Boustrophedon)

Предопределённый шаблон туда-обратно, начинающийся с одной стороны поля и идущий к другой. Отлично подходит для простых полей и полей с небольшими препятствиями.

Если вы замечаете слишком много проходов по поворотным полосам, мы рекомендуем запустить наш алгоритм по умолчанию и включить "Избегать пропуска проходов". Это позволит избежать крайних случаев проходов по поворотным полосам за счёт потери однородности.

Кластерная спираль

Предопределённый шаблон, всегда обеспечивающий пропуск как минимум N полос в схеме "вперёд-назад". Лучше всего работает на простых полях и полях с небольшими препятствиями.

Змейка

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

Маршрутизация с учётом ёмкости

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

Несколько машин с зоной ожидания

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

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

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

Экспериментальные функции

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

Планы маршрутов по данным журнала

Используя данные журнала вашей машины, мы можем воссоздать маршрут вашего транспортного средства, обеспечивая воспроизведение маршрута, анализ и скоро — планирование на основе данных журнала. Это позволяет охватить ту же площадь, что и предыдущая операция, или реализовать более сложную функциональность, например посев между рядами или обработку пропущенных рядов. Умные алгоритмы используют данные журнала для точного воссоздания полос даже при наличии пропущенных данных.
В настоящее время мы экспериментируем с поддержкой John Deere и Trimble PTx FarmENGAGE, но если вы используете определённый формат, мы будем рады совместно работать над его поддержкой.

Воссоздание полос из данных датчиков

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

Воспроизведение маршрута на реальных данных

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

Прицепные орудия

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

Сеточное представление поля

Перспективный подход, часто используемый в автономии, заключается в дискретизации рабочей зоны в виде сетки, где поиск типа hybrid A* может использоваться для нахождения кратчайшего управляемого пути между любыми двумя точками сетки. Ниже приведён пример части поля, дискретизированной таким образом. Зелёные участки — это проходы по поворотным полосам и считаются предпочтительными для движения, коричневый — допустимое пространство поворотной полосы, а красный — опасная зона, при попадании в которую транспортное средство может покинуть поле.

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

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

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

Параметры конфигурации

Список возможных параметров для передачи алгоритму маршрутизации с кратким пояснением. Дополнительную информацию см. в нашей документации API или свяжитесь с нами.