The problem: covering a real area with a real team, fairly
A team of UAVs assigned to jointly survey an area — for search and rescue, environmental monitoring, or agricultural inspection — needs more than just “a path for each robot.” It needs a coverage plan: a division of the area across the team such that every point gets visited, the plans respect real-world constraints like no-fly zones, and critically, the workload is balanced — no single robot ends up flying a route dramatically longer than its teammates while the rest sit idle.
Most coverage path-planning work assumes convex, obstacle-free regions. Real areas of interest are rarely that clean: they’re irregular, non-convex, and often have discontinuities — no-fly zones, obstacles, restricted airspace — carved out of them. A method that only works on a clean convex polygon isn’t one that survives contact with an actual mission area.
The approach: SCoPP
This paper’s method, SCoPP (Scalable Coverage Path Planning), breaks the problem into stages:
- Area discretization — the user-specified area of interest, non-convex boundary and no-fly zones included, is discretized into a grid of cells.
- Load-balanced partitioning — the cells are clustered into partitions sized for balanced workload across the team, rather than simply divided evenly by area.
- Auctioning of boundary cells — cells that sit on the boundary between partitions are auctioned off to resolve conflicts and further even out each robot’s assigned workload.
- Path planning — a fast nearest-neighbor algorithm generates an ordered list of waypoints for each robot to visit within its assigned cells.
The result is a coverage plan that’s explicit about handling non-convexity and no-fly zones from the start, rather than assuming them away, with load balancing built into the partitioning step rather than bolted on afterward.
Results: balanced workload, and it scales
SCoPP is shown to produce better-balanced workloads than baseline coverage-planning methods, with comparable overall mission completion efficiency — the point isn’t just “cover the area fast,” it’s “cover the area fast and don’t leave one robot doing most of the work.” Just as important for practical deployment, the method scales: computing time stays within a few minutes even for team sizes up to 150 robots, well past where a lot of coverage-planning approaches start to break down computationally.
The paper backs this up with an outdoor field experiment using a team of 3 UAVs, demonstrating the plan holds up outside simulation, not just on paper.
Why this matters
Coverage missions — search and rescue over a disaster area, environmental surveys, agricultural monitoring — are exactly the applications where both non-convex terrain and fair workload distribution are non-negotiable in practice: a plan that quietly assumes a clean rectangular field, or that runs one drone’s battery down while others barely fly, doesn’t survive first contact with a real deployment. SCoPP’s combination of load-balanced partitioning and demonstrated scalability to large teams is aimed directly at that gap between coverage-planning research and coverage-planning deployment.
- What is SCoPP?
- SCoPP (Scalable Coverage Path Planning) is a method for planning multi-UAV area coverage that discretizes the area into cells, load-balances the workload across the team through partitioning and boundary-cell auctioning, then plans each robot's path with a fast nearest-neighbor algorithm.
