Розподіл завдань (task allocation) — вирішення питання «хто що робить» у рої БПЛА. Для людини-планувальника навіть 10 БПЛА з 10 потенційними цілями — вже складна комбінаторна задача (10! = 3,6 млн варіантів). При 20 БПЛА і 20 цілях розрахунок вручну стає неможливим → потрібні алгоритми.
Ключові підходи: централізоване оптимальне призначення (угорський алгоритм, лінійне програмування) — оптимальне але вимагає центрального планувальника; і децентралізовані аукціонні методи (CBBA, market-based) — субоптимальні але стійкі до відмов, масштабовані і не потребують глобального знання.
Для бойових роїв БПЛА ЗСУ критично щоб алгоритм розподілу завдань враховував: поточний заряд батареї, тип корисного навантаження, позицію кожного агента відносно цілі, і пріоритизацію загроз — все це в режимі реального часу при постійно змінній обстановці.
Матриця призначення: БПЛА × Завдання
Приклад оптимального призначення 5 БПЛА на 5 завдань. Зелені клітинки — призначені ролі; сині — БПЛА здатний але не призначений; червонуваті — БПЛА недоступний (низький заряд / неправильний тип навантаження).
Основні алгоритми розподілу
Часті запитання
Що таке задача розподілу завдань рою БПЛА і чому вона NP-hard?
Multi-UAV Task Allocation (MUTA) — формалізована постановка задачі: Дано: N БПЛА з різними можливостями (ISR, Strike, Relay, EW). M завдань з різними вимогами (потрібен ISR-тип, мінімальна дальність X км, дедлайн T). Завдання: призначити БПЛА до завдань так щоб: максимізувати загальний profit (priority × success_rate). мінімізувати completion time. виконати всі hard constraints (тип, ресурс, temporal dependency). Чому NP-hard: якщо додати temporal constraints (завдання A має бути виконане ДО завдання B) → задача стає Travelling Salesman-like. з multi-robot routing → Multiple Depot Vehicle Routing (MDVRP), NP-hard навіть для апроксимації. Практичні масштаби: 20 БПЛА, 30 завдань → точне рішення вимагає ~minuti-hours обчислення на звичайному CPU. Тому → евристики: CBBA дає ~85–95% оптимального результату за секунди. Типові обмеження в MUTA: Battery constraint: БПЛА з <20% заряду не призначається на далекі завдання. Capability constraint: ISR-дрон не може виконати удар (немає боєголовки). Temporal precedence: розвідка цілі → ДО → удару. Coordinated attack: 3 БПЛА мають атакувати одночасно (синхронізація). Load balancing: рівномірне використання ресурсів рою.
Як працює алгоритм CBBA і чим він кращий від централізованого планувальника для бойових роїв?
CBBA (Consensus-Based Bundle Algorithm) — розроблений MIT LIDS, де-факто стандарт для decentralized task allocation: Принцип роботи CBBA (2 фази): Фаза 1 — Bundle Building (кожен агент незалежно): Агент i розглядає всі завдання j. Обчислює свій score(i, j) = очікувана вартість + (позиція → відстань → витрати ресурсів). Greedy: додає завдання до свого bundle поки benefit > cost. Виставляє bids (ставки) на вибрані завдання. Фаза 2 — Consensus (через gossip обмін): Агенти обмінюються ставками з сусідами. Правило консенсусу: завдання отримує агент з найвищою ставкою (після k-раундів Gossip → вся мережа знає winner). Conflict resolution: при «нічиї» → детермінована tiebreak (менший agent_id). Convergence: за O(diameter мережі) раундів → всі агенти мають узгоджене призначення. Переваги над централізованим: Відмовостійкість: якщо 5 агентів збиті → CBBA re-runs на решті. Немає single point of failure. Scalability: кожен агент обчислює тільки свій bundle, не глобальну матрицю. Bandwidth: обмін тільки ставками, не повним станом. Privacy: кожен агент зберігає тільки локальне знання. Обмеження CBBA: suboptimality (~10–20% від оптимуму). Не гарантує optimum при non-submodular reward functions. Convergence time O(diameter) → повільно при sparse network. Розширення CBBA: CBBA-П (pairwise): враховує синергію між завданнями. CBBA-D (dynamic): re-allocation при зміні обстановки в реальному часі. Практичне застосування: DARPA OFFSET рої, commerial drone delivery systems (Zipline), дослідні програми ЗСУ.
Як враховуються батарейні обмеження при розподілі завдань і що таке dynamic re-allocation?
Resource-aware task allocation з батарейними constraints — критичний аспект бойових роїв: Battery constraint modeling: кожен агент має State of Charge (SoC): 0–100%. Завдання j вимагає мінімум E_j енергії для виконання. Constraint: SoC_i ≥ E_j + RTB_margin (заряд на повернення до бази). Агент з SoC < threshold → не eligible для нових завдань. Battery-aware bid scoring: score(i,j) = quality(i,j) × energy_feasibility_factor. quality = геометрична прив'язка + capability match. energy_feasibility = (SoC_i - E_j - RTB) / SoC_max → 0 якщо feasibility < 0 (not eligible). Dynamic re-allocation запускається при: Агент збитий або відмова → його завдання → back to unassigned pool → CBBA re-runs. Нова ціль виявлена → нове завдання додається → re-allocation. Агент досягає SoC threshold → його незавершені завдання → re-assigned. Нова інформація про ціль (переміщення) → update scores → potential re-assignment. Online CBBA (incremental updates): базова CBBA статична (один раз перед місією). Online CBBA: при кожній зміні → тільки affected assignments перераховуються. Re-allocation overhead: ~50–200 мс для рою з 20 агентів (практична оцінка). Практична реалізація ЗСУ: mission_priority × capability_score - range_penalty - battery_penalty = bid. При SoC < 25% → примусовий RTB flag → GCS автоматично виключає зі списку eligible агентів. Це дозволяє оператору фокусуватись на стратегії замість мікро-менеджменту кожного БПЛА.
Як рій автоматично перерозподіляє завдання при знищенні частини агентів?
Fault-tolerant re-allocation при бойових втратах — ключова функція живучого рою: Виявлення втрати агента: heartbeat timeout: відсутність heartbeat протягом T_timeout (типово 1–3 с) → агент вважається «втраченим». Cluster-head або alive agents оголошують агента i «failed». Задокументовані невиконані завдання агента i → перенесені до unassigned pool. Re-allocation procedure: Triggered CBBA: surviving agents запускають скорочену CBBA тільки для unassigned tasks. Кожен живий агент перераховує свої scores для осиротілих завдань. Priority boost: завданням загиблого агента надається вищий priority_multiplier щоб швидше переназначити. Сценарій 20 → 14 агентів (30% втрат): якщо вижилі агенти мають ресурчи → CBBA відновлює ~85–90% місії coverage. деякі низько-пріоритетні завдання можуть бути dropped (mission pruning). Виконання temporal constraints після втрат: якщо агент що мав виконати завдання A (prerequisite до B) загинув → завдання B (dependent) також деactivated до виконання A. Новий агент призначається на A → після виконання A → B знову eligible. Latency re-allocation практична: 5 агентів, 3 осиротіли завдання → CBBA convergence ~100–300 мс. 20 агентів, 5 осиротілих → ~500 мс–1 с. 50+ агентів → ~2–5 секунд (acceptable якщо завдання не time-critical). Реальне значення: рій БПЛА що зазнав 40% втрат але продовжує ефективно виконувати місію — значна тактична перевага над системами що «ламаються» при перших втратах.
Як синхронізувати скоординований одночасний удар кількох БПЛА по одній цілі?
Coordinated simultaneous strike (time-synchronized attack) — технічна реалізація: Навіщо синхронний удар: одночасна атака з різних напрямків → overwhelm point defense. PK (probability of kill) значно вища ніж sequential single attacks (кожен наступний БПЛА атакує вже «готову» до відбиття ПВО). Saturation approach: якщо ПВО може відбити k ударів одночасно → рій з k+1 атакуючих агентів → гарантований прорив. Task allocation для синхронного удару: завдання типу «coordinated attack» розбивається на: sub-task для кожного agent_i: «прибути до point_i з bearing_i ДО T_strike». Temporal constraint: всі N агентів мають T_arrive ≤ T_strike ± Δ (де Δ = tolerance window, типово ±2–5 с). Time-of-Arrival (TOA) синхронізація: при CBBA bid агент обчислює ETA до цілі. Bid враховує ETA: агент що прибуде занадто пізно → excluded. Після assignment: кожен агент обчислює power profile щоб прибути точно до T_strike (throttle down if early / throttle up if late). Технічна точність: при GPS з точністю ±5 м → ETA помилка ~±1–2 с. Для Δ = 3 с → feasible для 5–10 агентів. При більших роях і меншому Δ → потрібна sub-second time sync (PPS from GPS). Практичний приклад: мультивекторна атака на РЛС: 3 БПЛА-ударники з N/W/E + 1 БПЛА-ISR (target designation overhead) + 1 БПЛА-jammer (EW глушіння РЛС під час атаки). Вся координація через CBBA з temporal constraints → без ручної мікро-координації оператором.
Які обмеження існуючих алгоритмів і які дослідження ведуться для вдосконалення task allocation?
Поточні обмеження алгоритмів task allocation і відкриті дослідні питання: Обмеження CBBA: suboptimality при non-submodular reward functions: CBBA гарантує <=2× від optimal тільки при submodular rewards. Для реальних бойових reward functions (complex interdependencies) → гарантії слабші. Convergence залежить від зв'язності мережі: sparse graph (рій у scatter formation) → повільна convergence. Не враховує uncertainty: класична CBBA assumes детермінований результат. Реально: «успіх удару на ціль T = 70%» → потрібен probabilistic CBBA. Відкриті дослідні питання: Multi-objective CBBA: одночасна оптимізація кількох факторів (mission success + friendly losses minimization + time). Deep RL для task allocation: навчання нейронної мережі розподіляти завдання в складних середовищах (POMDP). Meta-learning: рій «навчається» з попередніх місій → покращений scoring for similar future scenarios. Adversarial robustness: task allocation за наявності «брехливих» агентів (Byzantine) що маніпулюють ставками. Real-world progress 2024–2025: MIT Lincoln Laboratory: distributed task allocation для реальних 50-БПЛА тестів. Google Brain / DeepMind: transformer-based task allocation (attention між агентами і завданнями). ETH Zurich: swarm intelligence для 100-UAV outdoor experiments. Практичне значення для ЗСУ: поточні виробничі системи БПЛА-роїв переважно використовують CBBA або simple market-based auction. Deep RL task allocation → переважно лабораторний стан, до бойового розгортання потрібна верифікація надійності.