MRCPP

Efficient Multi-Robot Coverage Path Planning of Non-Convex Regions of Interests

Minimum-Turn Swaths VG-based Connectivity mTSP Allocation

Authors: <Add authors & affiliations>

Abstract

This letter presents an energy-efficient multi-robot coverage path planning (MRCPP) framework for large, nonconvex Regions of Interest (ROI) containing obstacles and no-fly zones (NFZ). Existing minimum-energy coverage planning algorithms utilize meta-heuristic boustrophedon workspace decomposition. Therefore, even with minimum energy objectives and energy consumption constraints, they cannot achieve optimal energy efficiency. Moreover, most existing frameworks support only a single type of robotic platform. MRCPP overcomes these limitations by: generating globally-informed swath generation, creating parallel sweeping paths with minimal turns, calculating safety buffers to ensure safe turning clearance, using an efficient mTSP solver to balance workloads and minimize mission time, and connecting disjoint segments via a modified visibility graph that tracks heading angles while maintaining transitions within safe regions. The efficacy of the proposed MRCPP framework is demonstrated through real-world experiments involving autonomous aerial vehicles (AAVs) and autonomous surface vehicles (ASVs). Evaluations demonstrate that the proposed MRCPP consistently outperforms state-of-the-art planners, reducing average total energy consumption by 3% to 40% for a team of 3 robots and computation time by an order of magnitude, while maintaining balanced workload distribution and strong scalability across increasing fleet sizes. The MRCPP framework is released as an open-source package and videos of real-world and simulated experiments are available at https://mrc-pp.github.io/.

Overview & Contributions

MRCPP integrates analytic geometry, graph-based connectivity, and optimization-based allocation to produce efficient coverage paths for non-convex ROIs with obstacles and no-fly zones.

Key Ideas

Minimum-area sweep orientation: rotating calipers compute the minimum-area enclosing rectangle to set a globally consistent sweep direction.
Minimum-turn swath generation: parallel swaths aligned with the sweep direction, clipped to the ROI, ordered along the minor axis.
Headland buffers: buffering the ROI boundary and exclusion zones yields a safe operable region for turns.
VG connectivity: a visibility graph connects disjoint swaths with collision-free transitions.
Workload-balanced allocation: a modified mTSP assigns swaths to minimize the maximum robot path length.

Rotating Calipers Headland Buffering Visibility Graph mTSP (LKH)

MRCPP Pipeline

MRCPP follows a geometry-to-optimization workflow: (i) compute a global sweep orientation, (ii) generate parallel swaths in the buffered free space, (iii) connect disjoint swaths using VG-based transitions, and (iv) allocate swaths to robots via a workload-balanced mTSP formulation.

Benchmark Results

We evaluate MRCPP on seven benchmark environments: Cape, Complex-12, Complex-22, Wetland, Island, Rect, and Simple. These range from simple convex regions to large non-convex ROIs with internal no-fly zones (Complex-12, Complex-22, Wetland). Performance is reported in terms of computation time, path length, and energy consumption. Scalability is further assessed by increasing fleet size in the Complex-22 and Cape environments.

Benchmark environments and MRCPP coverage paths. — **Fig. 2.** Representative benchmark environments with MRCPP-generated coverage paths for three AAVs (yellow, violet, blue). No-fly zones are shown as shaded red polygons.

Table I. Three-AAV Comparison Across Environments

Metrics: computation time, total fleet energy including depot round-trips (E_t [Wh]), resulting path length (ℓ [km]), coverage-only fleet energy (Ē_t [Wh]), and coverage-only path length (ℓ̄ [km]). Best value per scenario highlighted in bold. A dash (—) indicates no valid solution.

Scenario	MRCPP (Ours)					EAMCMP					DARP+MST					POPCORN+SALT
Scenario	Time [s]	E_t	ℓ	Ē_t	ℓ̄	Time [s]	E_t	ℓ	Ē_t	ℓ̄	Time [s]	E_t	ℓ	Ē_t	ℓ̄	Time [s]	E_t	ℓ	Ē_t	ℓ̄
Cape	1.28	586.37	36.68	470.08	29.28	4.93	601.68	35.66	496.56	28.90	33.82	600.85	34.92	503.98	28.68	55.87	818.99	39.16	708.18	32.06
Complex-12	3.60	478.14	27.40	455.74	26.12	—	—	—	—	—	45.31	482.23	24.73	479.58	24.62	—	—	—	—	—
Complex-22	1.23	256.92	14.49	241.55	13.66	1.25	419.69	23.55	404.95	22.67	18.22	270.75	13.69	265.88	13.46	—	—	—	—	—
Wetland	2.10	293.52	17.06	274.17	15.82	0.52	309.67	17.23	285.93	15.78	44.39	325.10	15.61	309.93	14.68	—	—	—	—	—
Island	0.47	37.82	1.60	29.77	1.25	0.53	36.80	1.60	30.25	1.29	5.21	37.61	1.37	33.85	1.18	—	—	—	—	—
Rect	0.44	68.21	3.66	55.16	2.99	0.02	85.25	4.35	73.83	3.75	4.75	89.18	3.81	87.37	3.74	20.71	137.06	3.99	131.99	3.75
Simple	0.63	117.90	6.67	104.46	5.97	0.02	185.09	10.41	169.56	9.57	5.70	140.25	6.33	138.14	6.26	32.28	242.59	7.18	235.47	6.83

Table II. Scalability in the Complex & Cape Environments (4–10 AAVs)

Metrics: computation time (t_c [s]), total fleet energy including depot round-trips (E_t [Wh]), and total coverage path length (ℓ [km]). A dash (—) indicates no valid solution. Bold marks the best value per row.

Scenario	MRCPP (Ours)			EAMCMP
Scenario	t_c	E_t	ℓ	t_c	E_t	ℓ
Complex (4 AAVs)	1.41	294.40	16.40	1.45	303.28	16.83
Complex (6 AAVs)	1.81	291.28	16.56	1.67	311.80	17.36
Complex (8 AAVs)	2.51	316.95	17.94	1.89	321.90	18.39
Complex (10 AAVs)	2.90	334.74	18.91	—	—	—
Cape (4 AAVs)	1.96	684.63	43.06	479.20	783.14	47.64
Cape (6 AAVs)	2.50	711.88	44.71	—	—	—
Cape (8 AAVs)	3.15	809.37	50.95	—	—	—
Cape (10 AAVs)	3.70	923.47	58.28	—	—	—

Scalability results for MRCPP vs baselines as number of robots increases. — **Fig. 3.** Scalability in fixed NFZ-constrained environments with varying fleet sizes (4–10 AAVs). MRCPP scales gracefully across all configurations; EAMCMP fails for larger fleets in the Cape environment.

EAMCMP Baseline Comparison

EAMCMP relies on boustrophedon decomposition without explicit sweep orientation optimization, resulting in suboptimal turn sequences and higher energy consumption across most benchmark environments. MRCPP outperforms EAMCMP in both total fleet energy (E_t) and coverage-only energy (Ē_t) in six of seven scenarios — the exception being Island, where EAMCMP achieves a marginally lower E_t (36.80 Wh vs. 37.82 Wh) due to its sensitivity to initial vehicle positions. Furthermore, EAMCMP fails to produce a valid solution in the Complex-12 environment, whereas MRCPP successfully solves all seven scenarios.

EAMCMP Rectangle — **Rectangle** (EAMCMP)

Ablation Study

We evaluate four sweep orientation strategies and assess the sensitivity of the buffer parameter, then compare MRCPP and EAMCMP head-to-head in an obstacle-rich environment across different fleet sizes.

Table III. Orientation Ablation — Fleet Energy Across Scenarios

Four sweep orientation strategies evaluated across seven benchmark scenarios. Metrics: total fleet energy including depot round-trips (E_t [Wh]) and coverage-only fleet energy (Ē_t [Wh]). Bold marks the lowest E_t per scenario.

Scenario	MAR		Angle Search		PCA		Min-Width
Scenario	E_t	Ē_t	E_t	Ē_t	E_t	Ē_t	E_t	Ē_t
Cape	589.21	464.64	662.84	537.14	586.37	470.08	652.80	540.78
Complex-12	533.65	506.20	486.15	457.19	507.58	470.05	478.14	455.74
Complex-22	275.91	253.37	278.34	260.82	256.92	241.55	276.91	257.23
Island	39.00	32.43	40.67	33.13	39.60	31.57	37.82	29.77
Rect	72.09	59.45	72.76	61.70	74.71	62.27	68.21	55.16
Simple	161.45	143.66	119.85	104.45	117.90	104.46	123.98	108.65
Wetland	161.45	143.66	119.85	104.45	117.90	104.46	123.98	108.65

Min-Width achieves the lowest E_t in three of seven scenarios (Complex-12, Island, Rect), while PCA is best in three others (Cape, Complex-22, Simple). MAR and Angle Search are never the top performers. The spread between best and worst orientation can exceed 35% (Simple), confirming sweep direction is a significant design parameter.

Effect of Headland Buffer on Energy Consumption

Effect of buffer scale w on total fleet energy consumption across environments. — **Fig. 4.** Effect of headland buffer scale w on total fleet energy consumption E_t across different environments. Lower values indicate better energy efficiency. Non-convex environments (e.g., Complex-12, Cape) show greater sensitivity to the buffer parameter than simpler ones (Island, Rect, Simple, Wetland).

Table IV. MRCPP vs EAMCMP — Obstacle-Rich Environment (3 / 6 / 10 AAVs)

Performance comparison in an environment with 10 convex and non-convex obstacles. Metrics: worst-case per-robot energy (E_{o_max} [Wh]), total fleet coverage-only energy (Ē_t [Wh]), and computation time (T_c [s]). Bold indicates the best value per fleet size.

# Robots	Method	E_{o_max} [Wh]	Ē_t [Wh]	T_c [s]
3	MRCPP (Ours)	41.81	111.17	9.65
3	EAMCMP	44.49	132.25	68.87
6	MRCPP (Ours)	21.81	104.58	3.22
6	EAMCMP	23.11	135.51	58.06
10	MRCPP (Ours)	13.92	96.73	3.11
10	EAMCMP	14.73	139.77	68.95

MRCPP is roughly 12× faster on average (5.33 s vs 65.29 s). Its total fleet energy decreases by ~13% as the fleet grows from 3 to 10 AAVs, reflecting effective workload distribution. EAMCMP's energy increases by ~5.7% over the same range due to sensitivity to initial positions rather than geometric structure.

EAMCMP coverage paths with 10 convex and non-convex obstacles. — **Fig. 5a.** EAMCMP — 10 AAVs, 10 obstacles. Paths occasionally violate NFZ and obstacle constraints near hazards.

MRCPP coverage paths with 10 convex and non-convex obstacles. — **Fig. 5b.** MRCPP — 10 AAVs, 10 obstacles. Buffer-zone constraints and VG detouring enforce strict separation from all boundaries.

Real-World Field Experiments

We validate MRCPP with two real-world deployments: (i) aerial coverage using two DJI Mavic Air AAVs (paths uploaded and executed via Litchi), and (ii) aquatic coverage using two ASVs equipped with YSI EXO2 sondes for in situ sensing. The executed coverage paths and the no-fly zone are visualized in the experiment interface and overlaid on satellite imagery.

AAV coverage experiment with two DJI Mavic Air. — **Fig. 4a.** AAV coverage experiment: the ROI (white polygon) is covered by two DJI Mavic Air AAVs with paths shown in orange and blue; the no-fly zone is highlighted in red.

ASV coverage experiment with two surface vehicles. — **Fig. 4b.** ASV coverage experiment: two ASVs execute coverage paths shown in red and green and obstacles (yellow) over satellite imagery of an aquatic environment.

Videos

Note: For best viewing quality, please watch the videos in full-screen mode.

AAV Experiment

Description (Fig. 1a): Two DJI Mavic Air AAVs execute MRCPP-generated coverage paths over a polygonal Region of Interest (ROI). The planned trajectories (orange and blue) are uploaded to the Litchi mission-planning software and flown concurrently. The circular red region denotes a no-fly zone enforced during path generation.

Tip: Click the icon in the video player to view in full screen.

ASV Experiment

Description (Fig. 1b): Two autonomous surface vehicles (ASVs), each equipped with YSI EXO2 sondes, execute MRCPP-planned coverage paths in a coastal aquatic environment. The executed trajectories (red and green) and obstacle (yellow) are overlaid on satellite imagery, enabling real-time monitoring and verification of coverage performance.

Tip: Full-screen playback is recommended for improved spatial clarity.

BibTeX

@article{mrcpp2025,
  title   = {Efficient Multi-Robot Coverage Path Planning of Non-Convex Regions of Interests},
  author  = {<authors>},
  journal = {},
  year    = {2025},
  url     = {https://mrc-pp.github.io/}
}