Why Grid Search
Search and rescue probability theory is built on a simple foundation: the probability of detecting a target in an area is a function of the fraction of that area you actually observe. A random flight path through the search area will cover some of it, miss some of it, and over-observe some of it. Systematic coverage — a planned sweep that visits every point exactly once — maximises detection probability for a given amount of flight time.
The boustrophedon pattern is the standard approach. The word comes from ancient Greek, meaning "as the ox turns" — referring to the way an ox-drawn plough works back and forth across a field. In computational geometry, boustrophedon decomposition is a well-studied method for covering a 2D region with parallel sweep lines. It is used in robotic vacuum cleaners, CNC milling, agricultural spraying, and, relevantly, aerial survey.
The pattern is simple in concept: fly a straight line across the search area, turn, offset by a fixed distance, fly back the other way, turn, offset, repeat. The result is a series of parallel passes that cover the entire area. The engineering questions are: how far apart should the passes be, what orientation should they have, and how do you handle a search area that is not rectangular?
Computing Sweep Spacing
The spacing between sweep lines is determined by the camera's ground footprint at the chosen altitude. If the camera can see a strip of ground W metres wide, and you want P percent overlap between adjacent strips, the spacing is:
spacing = W × (1 − P/100)
The camera footprint width W is a function of the altitude h and the horizontal field of view angle θ:
W = 2 × h × tan(θ/2)
For the Parrot ANAFI UKR's main camera, the horizontal FOV is approximately 69 degrees. At 30m altitude:
W = 2 × 30 × tan(34.5°) = 60 × 0.6882 ≈ 41.3m
With 20% overlap (the default in our planner):
spacing = 41.3 × 0.80 ≈ 33.0m
This means sweep lines should be 33m apart. Each pass covers 41.3m of ground width, and adjacent passes overlap by approximately 8.3m. This overlap serves two purposes: it compensates for position estimation error (the drone might not be exactly where it thinks it is), and it ensures targets near the edge of the frame — where lens distortion and oblique viewing angle reduce detection quality — are also observed from the adjacent pass.
The relationship between altitude and spacing is direct. Fly higher and each pass covers more ground, so you need fewer passes. But flying higher reduces the ground sample distance — the size of each pixel on the ground — which reduces detection capability for small targets. For SAR with visible-spectrum human detection, 30m is a practical compromise: the ground footprint is wide enough for efficient coverage, and the pixel resolution is sufficient for a neural network to identify a person-shaped object.
Principal Axis Alignment
For a rectangular search area aligned with the cardinal directions, the sweep pattern is trivial: fly east-west passes offset north-south (or vice versa). But SAR search areas are rarely rectangular and rarely aligned to cardinal directions. An operator draws an arbitrary polygon on a map based on where the missing person might be.
For any convex polygon, sweeping parallel to the longest edge minimises the number of turns. This is because the longest edge represents the direction in which the polygon has the greatest extent relative to its width. Sweeping perpendicular to the short axis means longer, fewer passes with fewer turns. Turns are expensive — the drone decelerates, rotates, re-accelerates — and during turns the camera is not pointed straight down, so turn time is wasted time from a coverage perspective.
The algorithm works in three steps. First, compute the angle of the longest edge of the polygon. This is straightforward: iterate through all edges, compute each edge's length and angle, and select the longest. Second, rotate the entire polygon so that this edge aligns with the x-axis. This is a 2D rotation matrix applied to all vertices. Third, generate the sweep lines as horizontal scanlines at the computed spacing across the rotated polygon's y-extent. Fourth, rotate the resulting sweep lines back to the original coordinate frame.
The rotation step simplifies the sweep generation: after rotation, all sweep lines are horizontal, and the clipping problem (described next) reduces to finding where horizontal lines intersect polygon edges — a much simpler computation than finding intersections at arbitrary angles.
Clipping to Arbitrary Polygons
Given a set of horizontal sweep lines (in the rotated coordinate frame) and a polygon boundary, each sweep line needs to be clipped to the polygon. Only the segments that lie inside the polygon are valid flight paths.
The algorithm is a standard scanline intersection approach. For each sweep line at height y:
- Walk all edges of the polygon. For each edge, test whether the sweep line's y-value falls between the edge's two endpoint y-values. If it does, compute the x-coordinate of the intersection using linear interpolation along the edge.
- Collect all intersection x-coordinates and sort them left to right.
- Pair intersections: the first and second form an entry-exit pair (a segment inside the polygon), the third and fourth form another pair, and so on. This works because a straight line crossing a simple polygon alternates between inside and outside.
For convex polygons, there are always exactly two intersections per sweep line (one entry, one exit), producing one segment per line. For concave polygons, a sweep line might intersect the boundary more than twice, producing multiple disjoint segments on a single sweep line. The pairing approach handles both cases naturally.
The result is a set of line segments, each representing one pass of the sweep pattern. Adjacent segments are connected by turns: the drone flies to the end of one segment, turns, flies to the start of the next segment. The turn direction alternates — right turn, left turn, right turn — producing the characteristic boustrophedon zigzag.
From Grid Points to Waypoints
The sweep pattern produces a set of geographic coordinates in the original (unrotated) coordinate frame. These are the turning points of the zigzag. But for GPS-resilient flight, we do not store these as absolute GPS coordinates. We convert them to relative vectors.
Each waypoint in the flight plan is expressed as a displacement from the previous waypoint:
{dx, dy, dz, dpsi}
Where dx is the eastward displacement in metres, dy is the northward displacement in metres, dz is the altitude change in metres, and dpsi is the heading change in degrees. For the sweep pattern, dz is zero during the grid (constant altitude) and dpsi corresponds to the 180-degree turns at the end of each sweep line.
The complete mission sequence is:
- Takeoff. Ascend to the target altitude. This is a single waypoint:
{dx: 0, dy: 0, dz: altitude, dpsi: 0}. - Transit to grid start. Fly from the takeoff position to the first corner of the grid. One or more waypoints with appropriate dx, dy values.
- Grid sweep. The sequence of sweep waypoints computed from the boustrophedon pattern. Each straight segment is one waypoint. Each turn is a transition to the next segment.
- Return to home. Fly from the last grid point back to the takeoff position. Descend and land.
An important property of this representation: the sum of all dx values across the entire mission should be approximately zero, and likewise for dy and dz. The drone takes off, flies a pattern, and returns to the takeoff point. If the vector sum is non-zero, there is a bug in the generation code — this serves as a built-in sanity check.
The practical advantage of relative vectors is resilience. As we described in our GPS-denied navigation post, a mission stored as relative displacements can execute using any position estimation system: GPS, VIO, or a combination. The drone tracks "how far have I moved since the last waypoint" rather than "what is my absolute position" — and that distinction is what keeps the mission running when satellites go dark.