← Past problems · 2017 set

2017 · Problem A — Drone Clusters as Sky Light Displays

Read the official PDF →

The prompt, restated

A city is considering replacing its traditional Fourth-of-July fireworks display with a choreographed flight of illuminated quad-copter drones — the same idea Intel/Disney/Shenzhen have since made famous with shows of 500–2,000 drones. Each drone carries a multi-color LED, flies under coordinated GPS control, and must take off, form a sequence of aerial images, and land safely. The team is asked to address several questions.

(1) Suppose the city wants to recreate a specific Fourth-of-July fireworks display using illuminated drones. Determine the minimum number of drones required for each image — the problem gives several reference targets such as an American flag, the Statue of Liberty, and a written message — and design the choreography that gets the fleet from one target to the next without collisions. (2) Address how a fleet of, say, 500 drones could be repurposed across a wider program: holiday displays, advertising, search-and-rescue, fire-spotting. (3) Recommend to a hypothetical "Florida-based theme park" how many drones to buy, where to base them, and how to staff the program, given safety, cost, and FAA constraints. (4) Write a one-page non-technical proposal to a city or park decision-maker.

Key modeling idea

Two layered problems. First, given a target image, find the smallest set of 3D points $\{p_i\}$ whose illuminated drones visually reproduce the image at the audience's viewing distance — essentially a covering / sampling problem on a 2D silhouette with a human-perception spacing constraint. Second, given two consecutive target sets $A$ and $B$ with $|A|=|B|=n$, find an assignment $\pi: A \to B$ that minimizes total travel distance subject to collision avoidance — this is the classical linear assignment problem with deconfliction.

Suggested approach

• Step 1 — Pixelize the target. Rasterize each image (flag, Statue of Liberty silhouette, text) to a binary mask, then sample drone positions at a spacing $d$ chosen from a perception model: at viewing distance $R$, the human eye resolves about 1 arcminute, so $d \approx R \cdot \tan(1') \approx R/3438$. For $R = 300$ m this gives $d \approx 0.09$ m, but a real show uses far coarser spacing (1–2 m) so the swarm reads as distinct points of light. Iterate on $d$ until the image is recognizable.
• Step 2 — Solve the inter-image assignment. Use the Hungarian algorithm (technique 5) on the $n \times n$ cost matrix $c_{ij} = \|p_i^A - p_j^B\|$ — optimal in $O(n^3)$, fine for $n \le 1000$.
• Step 3 — Deconflict trajectories. Straight-line assignments will produce crossings. Add a small altitude offset per drone (e.g., assign each drone a unique layer in a 0.5 m vertical band) or run velocity-obstacle / ORCA-style local avoidance. For HiMCM scope, layered altitudes are enough.
• Step 4 — Scale up. Estimate fleet size: a moderately detailed flag is roughly 200–400 drones; a Statue of Liberty silhouette around 500–800 [illustrative]. Compare to real shows — Intel's 2018 Olympics show used 1,218 drones; Shenzhen 2020 hit 3,051.
• Step 5 — Cost & safety memo. Per-drone capex roughly \$1,000–\$1,500 [illustrative]; add software, ground station, pilot-in-command staffing (FAA Part 107 waiver for swarm operations). Compare against a single fireworks show (~\$40k–\$80k).

Data sources to consider

Common pitfalls

• No perception model. Teams pick a drone spacing out of thin air. Anchor it to viewing distance and visual acuity, then defend the choice.
• Straight-line trajectories without deconfliction. Two drones swapping positions on a straight line collide at the midpoint. Either layer altitudes or solve a proper time-parameterized path-planning problem.
• Ignoring battery endurance. Show drones get 15–25 minutes of flight on a charge. A 30-minute show requires hot-swap batteries or two fleets.
• Skipping wind / GPS error. Real swarms hold position to ±0.3–1.0 m; station-keeping noise determines the minimum safe spacing.
• No failure analysis. What happens if 1% of drones drop out mid-show? Top papers include a graceful-degradation mode (resparsify the target on the fly).

Python sketch

Pixelize a target image, then solve the linear assignment between two consecutive frames.

import numpy as np
from scipy.optimize import linear_sum_assignment
from PIL import Image

# --- Step 1: rasterize a target into drone positions ---
def sample_positions(path, spacing_m=1.0, scale_m_per_px=0.5):
    img = np.array(Image.open(path).convert("L"))
    ys, xs = np.where(img < 128)               # dark pixels = "lit drone"
    pts = np.column_stack([xs, -ys]) * scale_m_per_px
    # subsample to enforce spacing
    keep = []
    for p in pts:
        if all(np.linalg.norm(p - q) >= spacing_m for q in keep):
            keep.append(p)
    return np.array(keep)

# --- Step 2: assignment between frame A and frame B ---
A = sample_positions("flag.png",    spacing_m=1.5)
B = sample_positions("liberty.png", spacing_m=1.5)
n = min(len(A), len(B))                          # pad/trim for square cost
A, B = A[:n], B[:n]
cost = np.linalg.norm(A[:, None, :] - B[None, :, :], axis=-1)
row, col = linear_sum_assignment(cost)           # Hungarian, O(n^3)

# --- Step 3: layered altitudes for collision avoidance ---
altitudes = np.linspace(80, 100, n)              # each drone gets a unique z-band, metres AGL
trajectories = [(A[i], altitudes[i], B[col[i]], altitudes[i]) for i in row]

travel_total = cost[row, col].sum()
print(f"n = {n} drones, total travel = {travel_total:.1f} m")
print(f"avg travel per drone = {travel_total/n:.2f} m")

Sensitivity & validation checklist

• Vary perceptual spacing $d$ from 0.5 m to 3 m — at what point does the image stop being recognizable? Use a small human-rater study or downsample-and-blur as a proxy.
• Vary fleet size: can a 300-drone fleet still render the flag at lower fidelity?
• Inject 1%, 5%, 10% random drone failures during a transition and report the reassignment cost.
• Stress with a 10 m/s crosswind — does the safe spacing need to grow?
• Validate trajectories: minimum pairwise distance during transition should never drop below twice the GPS error band.

Related pages

• Techniques — Optimization & assignment
• Techniques — Monte Carlo (for failure injection)
• Anatomy of a winning paper