💻 computer science

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

This paper proposes an energy-efficient multi-robot coverage path planning (MRCPP) framework that optimizes coverage for large, non-convex regions by utilizing globally-informed swath generation and an efficient mTSP solver, significantly reducing energy consumption and computation time across heterogeneous robotic platforms.

Original authors: Sourav Raxit, Jose Fuentes, Paulo Padrao, Abdullah Al Redwan Newaz, Md Tamjidul Hoque, Mark Kulp, Leonardo Bobadilla

Published 2026-04-27

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Sourav Raxit, Jose Fuentes, Paulo Padrao, Abdullah Al Redwan Newaz, Md Tamjidul Hoque, Mark Kulp, Leonardo Bobadilla

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are in charge of a massive, irregularly shaped lawn that is filled with flower beds you aren't allowed to step on, a swimming pool in the middle, and a few large boulders. You have a team of three robotic lawnmowers to get the job done.

If you just tell the mowers, "Go mow the grass," one mower might end up doing 90% of the work while the others sit idle, or they might spend all their battery life zig-zagging wildly and turning around every two seconds.

This paper introduces a new "brain" (a software framework called MRCPP) that acts like a master conductor for these robots, making sure they work together perfectly to save energy and time.

Here is how the "brain" works, broken down into three simple steps:

1. Finding the "Perfect Angle" (The Striping Strategy)

Think about when you mow a lawn or vacuum a rug. If you move diagonally or in random directions, you waste a lot of energy turning the machine around.

The researchers realized that most robots waste energy because they don't pick the best direction to start. Their system uses a clever math trick (called "rotating calipers") to look at the entire shape of the yard and find the single best direction to lay down long, straight "stripes." By aligning the robot's path with the longest side of the yard, the robot can go long distances in a straight line and only turn when absolutely necessary. It’s the difference between driving a car in long highway stretches versus constantly driving through a series of tight city intersections.

2. Dividing the Labor (The Fair Boss)

Once the system knows where the "stripes" should go, it has to decide which robot gets which stripe.

If you just give the first robot everything on the left and the second robot everything on the right, one might get a huge area while the other gets a tiny corner. The MRCPP acts like a fair boss in a warehouse. It uses a specialized math solver to hand out tasks so that every robot has roughly the same amount of work. This ensures that the whole job finishes as fast as possible, rather than everyone waiting around for one exhausted robot to finish its massive pile of work.

3. Navigating the Obstacles (The Smart Detour)

Now, what happens if a "stripe" hits a flower bed or a no-fly zone? The robot can't just stop or crash.

The researchers created a "smart detour" system. Instead of the robot getting confused or taking a massive, looping detour that wastes battery, the system creates a "safety buffer" (like a virtual lane) around obstacles. It then uses a "Visibility Graph"—think of this as a GPS that only looks at the clear paths between corners—to find the shortest, smoothest way to get from one stripe to the next without hitting anything.

Does it actually work?

The researchers didn't just test this on computers; they put it to work in the real world with drones (AAVs) in the air and boats (ASVs) on the water.

The Results:

Huge Energy Savings: It used 3% to 40% less energy than the current best methods. In the world of robotics, that is the difference between a drone finishing its mission or falling out of the sky mid-way.
Lightning Fast: It calculates the entire plan in seconds, whereas older methods could take much longer.
Scalable: Whether you have 3 robots or 10, the system stays organized and efficient.

In short: This paper provides a smarter, fairer, and more "straight-line" way for groups of robots to clean, monitor, or scan large areas without running out of juice.

Technical Summary: Energy-Efficient Multi-Robot Coverage Path Planning (MRCPP)

1. Problem Statement

The paper addresses the challenge of Multi-Robot Coverage Path Planning (MRCPP) in large, non-convex Regions of Interest (ROI) that contain obstacles and No-Fly Zones (NFZ). The primary objective is to minimize energy consumption while ensuring complete coverage, obstacle avoidance, and balanced workloads among a fleet of robots.

Existing methods suffer from several critical limitations:

Suboptimal Energy Efficiency: Many algorithms rely on meta-heuristic "boustrophedon" decomposition, which leads to fragmented swaths, excessive turns, and redundant overlaps.
Poor Path Continuity: Partition-based or cell-based methods often ignore sweep orientation, resulting in inconsistent headings and frequent, energy-intensive direction reversals.
Scalability and Complexity: Existing solvers often struggle with the NP-hard complexity of large, cluttered, non-convex domains or fail to provide valid solutions when obstacles are present.

2. Methodology

The authors propose a multi-stage framework designed to optimize the geometric and operational aspects of coverage:

Orientation-Optimized Swath Generation: Instead of using fixed grids, the framework uses a rotating-calipers algorithm to find the Minimum-Area Rectangle (MAR) enclosing the ROI. This determines a globally informed sweep orientation that aligns with the ROI's principal axis, thereby minimizing the total number of turns.
Safety Buffering (Headland Concept): To ensure safe turning clearance and obstacle avoidance, the framework applies Minkowski operations. It dilates exclusion zones (Minkowski sum) and shrinks the ROI boundary (Minkowski difference) to create a "buffered" feasible space ( $F'$ ).
Workload-Balanced Task Allocation: The problem is formulated as a multiple Traveling Salesman Problem (mTSP). The framework uses the LKH solver with a MINSUM objective to assign swaths to robots. A minimum tour size constraint is applied to ensure that the workload is distributed approximately equally across the fleet, preventing a single robot from being overburdened.
Contiguous Path Generation via Modified Visibility Graph (VG): To connect disjoint swath segments, the authors use a modified VG algorithm. Unlike standard VGs that only use obstacle corners, this version samples additional points along obstacle edges to ensure that detours remain close to the original swath trajectory, minimizing deviation and energy loss. It also employs a heading-driven traversal rule to maintain a boustrophedon (back-and-forth) pattern.

3. Key Contributions

Orientation-Optimized Algorithm: A method to minimize turns by aligning coverage with the ROI’s principal axis while respecting safety buffers.
Balanced mTSP Formulation: An efficient approach to multi-robot swath allocation that balances individual workloads and minimizes total mission time.
Obstacle-Aware Path Refinement: A modified Visibility Graph algorithm that uses sampled boundary points and heading-driven selection to ensure collision-free, continuous, and energy-efficient transitions.

4. Experimental Results

The framework was validated through extensive simulations and real-world experiments using Autonomous Aerial Vehicles (AAVs) and Autonomous Surface Vehicles (ASVs).

Simulation Performance:
- Energy Efficiency: MRCPP reduced average total energy consumption by 3% to 40% compared to state-of-the-art planners (e.g., EAMCMP and DARP+MST).
- Computational Speed: The framework was an order of magnitude faster, often solving complex scenarios in under 4 seconds, whereas competitors took significantly longer or failed entirely in obstacle-rich environments.
- Scalability: As the fleet size increased (from 4 to 10 robots), MRCPP maintained low computation times and efficient energy scaling, whereas existing methods failed to produce valid solutions for larger fleets.
Real-World Validation:
- Aerial (AAVs): Two DJI Mavic Air drones successfully covered a polygonal ROI with an NFZ, demonstrating the ability to execute complex, coordinated paths.
- Surface (ASVs): Two surface vehicles successfully covered an aquatic region while avoiding polygonal obstacles, verified via real-time satellite imagery and sensor feeds.

5. Significance

This research provides a robust, scalable, and computationally efficient solution for autonomous fleet coordination in complex environments. By shifting the focus from simple path length to turn-minimization and orientation-optimization, the framework directly addresses the physical energy constraints of real-world robots. The release of the framework as an open-source package makes it a valuable tool for applications in precision agriculture, environmental monitoring, and search-and-rescue operations.