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

Огляд

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

Моделювання розворотів

Ми підтримуємо різні типи розворотів, які вибираються автоматично залежно від комбінації геометрії поля та характеристик техніки. Якщо дві смуги знаходяться в межах 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 або зв'яжіться з нами.