Перейти к содержанию

Покрытие области: декомпозиция, галсы, развороты

Второй слой ядра. На вход — полигон съёмки, бесполётные зоны, граница разрешённого ВП, ширина захвата и требуемая высота. На выход — множество галсов с геометрией и стоимостью прохода каждого. Дальше галсы уходят в распределение по бортам (04-fleet-routing.md).

Формально это Coverage Path Planning (CPP); для группы аппаратов — mCPP. Задача изученная, готовых кирпичей достаточно, писать с нуля не нужно.

Пайплайн

полигон  ─┐
NFZ      ─┼─► [1] вычитание препятствий ─► [2] выбор угла галсов ─► [3] генерация галсов
граница ВП┘                                      ▲                         │
                                            ветер, форма                    ▼
                                                                  [4] стоимость прохода
                                                                     и разворотов
                                                                            │
                                                                            ▼
                                                                  [5] порядок обхода

1. Вычитание препятствий и разрезание на выпуклые куски

Бесполётные зоны (R-IN-6) вычитаются из полигона съёмки; граница разрешённого ВП (R-IN-5) пересекается с ним. Получается, вообще говоря, невыпуклая область с дырами.

Дальше — трапецоидальная или бустрофедонная декомпозиция: разрезание на выпуклые куски, внутри каждого галсы прямые и непрерывные. Без декомпозиции галс, пересекающий дыру, придётся разрывать, и на месте разрыва появится незапланированный разворот.

Тонкость, которую стоит решить явно: бесполётная зона запрещает пролёт, но область под ней всё равно может требовать съёмки — например, если NFZ ограничена по высоте. В базовой версии считаем NFZ сплошным запретом и честно показываем непокрытый остаток в отчёте. Скрывать его нельзя: «доля покрытия» — одна из метрик валидатора.

2. Выбор угла галсов — здесь мы обходим Planner

В Geoscan Planner угол выбирается вручную бегунком, и документация прямо называет причину:

Необходимость оптимизировать полигон «по направлению» возникает, например, если на месте проведения работ сила и направление ветра неблагоприятны (сильный ветер вдоль линий облета полигона).

Два фактора тянут угол в разные стороны:

Фактор А — число разворотов. Чем длиннее галсы, тем их меньше, тем меньше разворотов. Минимум достигается, когда галсы идут вдоль «длинной оси» области. Для выпуклого многоугольника оптимальный угол — перпендикуляр к направлению минимальной ширины (вычисляется за O(n) методом rotating calipers).

Фактор Б — ветер. Разберём точно, потому что результат контринтуитивный и в этом вся ценность.

Пусть V_a — воздушная скорость, W — скорость ветра, α — угол между направлением галса и направлением ветра. Продольная и поперечная составляющие: W∥ = W·cos α, W⊥ = W·sin α. Путевая скорость вдоль галса (см. 05-energy-and-wind.md):

V_g = sqrt(V_a² − W⊥²) + W∥

Сравним два предельных случая для пары галсов «туда-обратно» длиной L каждый:

Галсы вдоль ветра (α = 0, попутно и встречно):

T = L/(V_a + W) + L/(V_a − W) = 2·L·V_a / (V_a² − W²)

Галсы поперёк ветра (α = 90°, чистый снос в обе стороны):

T = 2·L / sqrt(V_a² − W²)

Отношение:

T_вдоль / T_поперёк = V_a / sqrt(V_a² − W²) = 1 / sqrt(1 − (W/V_a)²)  > 1

Галсы поперёк ветра всегда быстрее. Причина — попутный участок не компенсирует встречный: выигрыш на попутном линеен, а проигрыш на встречном растёт гиперболически (среднее гармоническое меньше среднего арифметического).

Конкретные числа:

W / V_a Проигрыш галсов вдоль ветра
0,2 +2 %
0,4 +9 %
0,53 (Gemini: 8 м/с при 15 м/с) +18 %
0,6 +25 %
0,8 +67 %

Это прямое численное подтверждение правила из руководства Planner — и готовый аргумент на защиту.

Итоговая целевая функция по углу — сумма обоих факторов:

T(θ) = Σ_галсы L_i(θ) / V_g(θ, ветер)  +  N_turns(θ) · t_turn(θ)

Одномерная задача: перебрать θ от 0° до 179° с шагом 1° и взять минимум. 180 вычислений геометрии полигона — доли секунды. Никакой эвристики не нужно, решается точно перебором. При этом мы автоматически делаем то, что в Planner делается руками, и можем показать выигрыш числом.

3. Генерация галсов

Внутри каждого выпуклого куска — параллельные отрезки с шагом By под выбранным углом. Краевые эффекты: первый и последний галс сдвигаются внутрь на By/2, чтобы края области попали в покрытие. Это классический источник «дырки по краю», её ловит метрика покрытия в валидаторе.

4. Стоимость разворота — то, что превращает оценку из оптимистичной в честную

Наивная формула «время = длина / скорость» игнорирует развороты. Для самолёта это ошибка в десятки процентов.

Минимальный радиус разворота при координированном вираже с креном φ:

R = V² / (g · tan φ)

Для Геоскан 201 на крейсере 27,8 м/с (100 км/ч) с креном 30°:

R = 27,8² / (9,81 · 0,577) = 772,8 / 5,66 ≈ 137 м

То есть диаметр разворота ~273 м, а типичный шаг галсов — 70–120 м. Полукруглым разворотом на следующий галс не перейти: он «перелетает» цель в 2–4 раза.

Отсюда и берётся тот самый «разворот с выходом на ЛЗП» с петлёй из руководства Planner:

БВС полностью пролетит галс, а затем зайдет на следующий галс с дополнительным маневром («петлей»). Этот вариант гарантирует съемку территории под маршрутом в полном объеме, и он предпочтителен в случае резких разворотов.

Против:

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

Это физический компромисс «полнота покрытия ↔ время», и его надо смоделировать явно, а не выбрать молча. В UI — переключатель, в отчёте валидатора — обе метрики (покрытие и время) для обоих вариантов.

Оценки времени разворота:

Аппарат Модель Время 180°
Самолёт (201, V = 27,8, R = 137) полукруг πR, но при By < 2R нужна петля πR / V ≈ 15,5 с минимум; с петлёй 20–30 с
Мультиротор (Gemini, 801, V = 15) торможение → разворот на месте → разгон, a ≈ 3 м/с² 2·(15/3) = 10 с плюс сам разворот

Дополнительно у QGC есть TurnAroundDistance — вылет за границу полигона на разворот (дефолт 10 м). Его тоже надо учитывать: он добавляет и время, и требование, чтобы разворотная зона не попадала в бесполётную.

Для строгого расчёта берутся кривые Дубинса (минимальная траектория для аппарата с ограниченным радиусом разворота, без реверса) — их считает Fields2Cover.

5. Порядок обхода галсов

Внутри одного куска обычный бустрофедон (туда-обратно) почти оптимален. Когда кусков несколько или галсы неоднородны, порядок — это задача маршрутизации, и Fields2Cover умеет решать её через OR-Tools вместо фиксированного паттерна.

Важно: на этом этапе порядок определяется в пределах одного борта. Глобальное распределение галсов между бортами — следующий слой.

Что берём готовым

Fields2Cover

github.com/Fields2Cover/Fields2Cover — лицензия BSD-3, C++17 с Python-биндингами через SWIG, есть интеграция с ROS 2.

Модульный пайплайн ровно по нашим шагам: генерация краевых полос (headlands) → генерация галсов (swaths) → планирование маршрута (route planning) → построение траектории с выполнимыми разворотами (path planning). Либо один вызов planCovPath.

Что конкретно закрывает:

  • невыпуклые области с препятствиями;
  • трапецоидальная и бустрофедонная декомпозиция;
  • генерация галсов под заданным или оптимизируемым углом;
  • развороты по кривым Дубинса и Ридса-Шеппа, с непрерывной кривизной и без;
  • упорядочивание галсов через OR-Tools.

Практическое замечание: библиотека официально собирается и тестируется под Ubuntu, pip install fields2cover тянет системные зависимости. Заложить Docker-образ сразу, иначе полдня уйдёт на сборку под macOS. Это единственный реальный риск по этой зависимости.

Альтернатива — писать самим

Генерация параллельных галсов в выпуклом полигоне — это 100 строк на Shapely: повернуть полигон на −θ, нарезать горизонтальными линиями с шагом By, пересечь, повернуть обратно. Если Fields2Cover не соберётся или его модель не ляжет на наши типы съёмки, собственная реализация покрывает шаги 1–3 за день. Развороты по Дубинсу — ещё полдня, формулы известные.

Рекомендация: начать со своей реализации на Shapely (полный контроль, ноль проблем со сборкой), Fields2Cover держать как ускоритель для сложных невыпуклых случаев и как сильный аргумент «используем отраслевую библиотеку» на защите. Решение принимать по факту, когда будет валидатор и будет чем мерить.

Метрики, которые считает валидатор на этом слое

Метрика Как считается Зачем
Доля покрытия площадь объединения полос захвата ∩ полигон / площадь полигона главный критерий корректности
Число галсов — косвенно показывает качество выбора угла
Число разворотов — то, что минимизируем
Доля времени на разворотах N_turns · t_turn / T_total показывает, насколько наивная оценка врёт
Нарушения NFZ длина траектории внутри бесполётных зон должно быть строго 0
Выход за границу ВП длина траектории вне inclusion-зоны должно быть строго 0

Источники