Multiple UAS

Example 1 Exhaustive search versus greedy

import math
from itertools import permutations

drones = [(0, 0), (0, 30), (60, 0), (60, 30)]
tasks = [(10, 25), (35, 15), (30, 5), (50, 25)]
cost = [[math.dist(d, t) for t in tasks] for d in drones]

best = min(permutations(range(4)), key=lambda p: sum(cost[i][p[i]] for i in range(4)))
used, greedy = set(), []
for i in range(4):
    j = min((j for j in range(4) if j not in used), key=lambda j: cost[i][j])
    used.add(j)
    greedy.append(j)

for name, plan in (("optimal", best), ("greedy", greedy)):
    total = sum(cost[i][plan[i]] for i in range(4))
    pairs = ", ".join(f"D{i + 1}->T{plan[i] + 1}" for i in range(4))
    print(f"{name:<8} {total:6.1f} m  {pairs}")

optimal    81.9 m  D1->T3, D2->T1, D3->T2, D4->T4
greedy    131.0 m  D1->T1, D2->T2, D3->T4, D4->T3

D1 takes its nearest task T1 first, which forces D2, close to T1, to travel far. The total is much worse than the optimum. For dozens of drones, use the Hungarian method, which finds the optimum without trying every permutation.

Example 2 Closest approach between two path segments

Assume both drones move in straight lines at constant rates over the same interval.

def closest(a0, a1, b0, b1, t0=0.0, dt=2.0):
    r0 = [a - b for a, b in zip(a0, b0)]
    dr = [(a1i - b1i) - r for a1i, b1i, r in zip(a1, b1, r0)]
    dd = sum(v * v for v in dr)
    u = 0.0 if dd == 0 else min(1.0, max(0.0, -sum(r * d for r, d in zip(r0, dr)) / dd))
    d = sum((r + u * v) ** 2 for r, v in zip(r0, dr)) ** 0.5
    return d, t0 + u * dt

cases = {
    "swap on the same line": ((-1, 0, 2), (1, 0, 2), (1, 0, 2), (-1, 0, 2)),
    "swap 0.5 m apart sideways": ((-1, 0, 2), (1, 0, 2), (1, 0.5, 2), (-1, 0.5, 2)),
    "one above the other": ((0, 0, 2.0), (2, 0, 2.0), (0, 0, 2.4), (2, 0, 2.4)),
}
for name, (a0, a1, b0, b1) in cases.items():
    d, t = closest(a0, a1, b0, b1)
    print(f"{name:<26} ends {sum((a - b) ** 2 for a, b in zip(a0, b0)) ** 0.5:.1f} m apart -> "
          f"min {d:.2f} m at t {t:.1f} s")

swap on the same line      ends 2.0 m apart -> min 0.00 m at t 1.0 s
swap 0.5 m apart sideways  ends 2.1 m apart -> min 0.50 m at t 1.0 s
one above the other        ends 0.4 m apart -> min 0.40 m at t 0.0 s

In the third case the drones stay 0.4 m apart vertically the whole way, which looks safe, but the lower drone sits in the downwash of the upper one. Hönig et al. (2018) therefore model each drone as an ellipsoid that is longer vertically than horizontally, so the vertical separation threshold must be larger than the horizontal one. The actual values must come from testing the drone model in use.

Example 3 Swarm bandwidth

MSG_BYTES, RATE_HZ, OVERHEAD = 60, 30, 1.3          # position message, rate, protocol overhead
for n in (3, 10, 50):
    kbps = n * RATE_HZ * MSG_BYTES * 8 * OVERHEAD / 1000
    print(f"{n:>2} drones: {kbps:6.1f} kbit/s for position updates only")

 3 drones:   56.2 kbit/s for position updates only
10 drones:  187.2 kbit/s for position updates only
50 drones:  936.0 kbit/s for position updates only

These figures exclude camera video. If every drone streamed video, bandwidth would rise by hundreds of times. Processing on board and sending only results matters a great deal in multi-drone work.