💻 computer science

A Complete-Coverage Path-Planning Algorithm Based on Local Path Cost

This paper proposes CCPP-LPC, a complete-coverage path-planning algorithm that utilizes a local path cost evaluation model and an adaptive dual-guided perturbation strategy to overcome the limitations of existing heuristic methods, thereby achieving superior computational efficiency and path optimization in complex environments.

Original authors: Xia Wang, Yuhang Zhu, Jianing Tang, Zhongbin Dai, Chenjia Li

Published 2026-07-02

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Xia Wang, Yuhang Zhu, Jianing Tang, Zhongbin Dai, Chenjia Li

Original paper licensed under CC BY 4.0 (https://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

The Big Picture: The "Mow-All-the-Grass" Problem

Imagine you have a robot vacuum or a lawn-mowing drone. Its job is to clean or mow every single inch of a room or a field without missing a spot. This is called "Complete Coverage Path Planning."

The challenge isn't just getting from Point A to Point B; it's visiting every single square inch of a complex space (with furniture, trees, or rocks in the way) while doing three things:

Don't waste time: Keep the total distance short.
Don't waste energy: Avoid turning the robot around too many times (turning is slow and uses extra battery).
Don't go over the same spot twice: If you vacuum the same rug twice, you're wasting time.

The Problem with Old Methods

The authors explain that existing robot planners are a bit like a person trying to solve a maze by randomly guessing. They might get stuck in a "local trap"—a path that looks okay but isn't the best. They also tend to wander aimlessly, making the robot turn too much or re-traverse areas it already cleaned.

The authors' previous method (called CCPP-TPLP) was better, but it still had a flaw: when it tried to fix a bad path, it was a bit "blind." It would pick random parts of the path to change, hoping for the best, rather than knowing exactly which part was the problem.

The New Solution: CCPP-LPC

The new algorithm, CCPP-LPC, acts like a smart foreman who knows exactly where the mistakes are. Here is how it works, broken down into three simple steps:

1. The "Cost Calculator" (Local Path Cost)

Imagine you are walking through a garden. If you have to take a giant, awkward step to get from one flower to the next, that step is "expensive" in terms of energy and time.

What the paper does: The algorithm looks at every single step in the robot's planned route. It calculates a "cost" for each step. If a step forces the robot to travel a long distance or make a weird turn, that step gets a high cost score.
The Analogy: It's like a GPS that doesn't just show the route, but highlights the specific traffic jams or potholes so you know exactly where to reroute.

2. The "Double-Strategy" Selection (Adaptive Dual-Guided Perturbation)

Once the algorithm finds the "expensive" steps (the high-cost nodes), it needs to fix them. But if it only fixes the worst parts, it might get stuck in a loop. If it fixes random parts, it wastes time.

The Solution: The algorithm uses two different "strategies" to pick which parts of the path to change:
- Strategy A (The Fixer): This strategy looks at the "high cost" steps and says, "Let's definitely change these!" It focuses on the worst parts of the path to make them shorter.
- Strategy B (The Explorer): This strategy picks a random step, even a "good" one. Why? To keep the robot's options open and prevent it from getting stuck in a rut.
The Analogy: Imagine you are editing a messy essay.
- Strategy A is like a strict editor who only fixes the paragraphs with the most grammar errors.
- Strategy B is like a creative writer who randomly rewrites a sentence just to see if a new idea pops up.
- CCPP-LPC does both at the same time, ensuring the essay gets better and stays fresh.

3. The "Talent Show" (Elitist Selection)

After the robot tries out these new, slightly changed paths, the algorithm acts like a talent show judge.

It takes the old path and the new "improved" path.
It keeps the one that is shorter, has fewer turns, and covers the area better.
It throws away the worse one.
The Result: Over time, the robot's path gets better and better, like a runner training to shave seconds off their time.

What the Experiments Showed

The authors tested this new "smart foreman" against five other popular robot planners (like Ant Colony Optimization and others) in four different scenarios:

Simple Grids: Small rooms with few obstacles.
Complex Grids: Large areas with many obstacles.
Real-World Lakes: Using satellite maps of actual lakes (Yuhua Lake, Wisdom Lake, Qiulian River) where a boat needs to clean the water.
Real-World Fields: A tractor driving over a field with hills.

The Results:

Shorter Paths: The new algorithm consistently found shorter routes than the others.
Fewer Turns: The robot didn't have to spin around as much, saving energy.
Less Overlap: It didn't clean the same spot twice as often as the other methods.
Stability: It didn't just get lucky once; it performed well every single time it was tested, even in very messy, complex environments.

Summary

In short, this paper introduces a smarter way for robots to plan their cleaning or mowing routes. Instead of guessing randomly, the new algorithm identifies the specific "bad steps" in a path, fixes them with a targeted strategy, and keeps a little bit of randomness to stay creative. The result is a robot that works faster, uses less battery, and gets the job done more efficiently, whether it's vacuuming a living room or mowing a farm field.

Technical Summary: A Complete-Coverage Path-Planning Algorithm Based on Local Path Cost (CCPP-LPC)

Problem Statement
Complete Coverage Path Planning (CCPP) is a critical technology for autonomous mobile robots and unmanned surface vehicles (USVs), tasked with generating collision-free trajectories that traverse all reachable grid cells in a workspace. While existing metaheuristic and swarm-intelligence-based planners (e.g., Ant Colony Optimization, Genetic Algorithms) have advanced the field, they often struggle in large-scale, complex environments. Specific limitations include slow convergence rates, a tendency to become trapped in local optima due to a lack of directional guidance in population evolution, and the generation of paths with excessive turning maneuvers. These inefficiencies lead to suboptimal path lengths, increased energy consumption, and reduced operational efficiency.

Methodology
The paper proposes the CCPP-LPC algorithm, which builds upon a previous framework (CCPP-TPLP) but introduces a novel mechanism to guide the evolutionary search process. The core methodology involves three primary components:

Local Path Cost Evaluation Model:
Instead of relying on population stratification based on global fitness, CCPP-LPC constructs a local evaluation model. For every node in a path sequence, the algorithm calculates a "local path cost" ( $c_k$ ). This metric represents the average distance cost of the two-hop subpath formed by the node and its immediate predecessor and successor.
- Mathematically, $c_k$ quantifies the marginal negative contribution of a specific node to the total path length.
- Nodes with higher local costs indicate poor local connectivity and are identified as having high optimization potential.
Adaptive Dual-Guided Perturbation Node Selection Strategy:
To overcome the blindness of traditional mutation operators, the algorithm derives two distinct probability distributions from the local path costs to select perturbation nodes:
- Optimization-Oriented Distribution: This distribution assigns higher selection probabilities to nodes with high local costs (specifically, weights are calculated as $(c_k - 1 + \epsilon)^\beta$ ). This steers the evolutionary operators to prioritize refining segments that significantly inflate the total path length.
- Diversity-Oriented Distribution: This distribution assigns baseline exploration probabilities to all nodes (weights calculated as $c_k^\beta$ ). By not subtracting the baseline value of 1, it ensures that even nodes with low local costs retain a non-negligible chance of selection, thereby preserving population diversity and preventing premature convergence.
- The algorithm uses roulette-wheel selection based on these distributions to choose two perturbation nodes ( $I$ and $J$ ) for each individual.
Individual Update and Elitist Selection:
Once nodes $I$ and $J$ are selected, one of three variation operators (Swap, Reversal, or Insertion) is applied stochastically to generate offspring. The algorithm employs an elitist selection strategy, merging the parent and offspring populations and retaining the top $N$ individuals based on fitness. This eliminates the need for manually set population hierarchical division ratios, simplifying parameter tuning.

Key Contributions
The paper identifies two main contributions:

Construction of a Local Path Cost Evaluation Model: This model adaptively quantifies the optimization urgency of each waypoint by measuring its two-hop subpath cost. This allows for the precise identification of "low-quality" segments without the need for population tiering or manual parameter settings regarding hierarchical division.
Design of an Adaptive Dual-Guided Perturbation Strategy: By combining optimization-oriented and diversity-oriented probability distributions, the algorithm achieves a balance between local refinement (targeting high-cost segments) and global search (maintaining genetic diversity). This provides explicit directionality to the evolutionary process, addressing the randomness inherent in previous mutation operators.

Experimental Results
The performance of CCPP-LPC was evaluated against five state-of-the-art algorithms (ACO, ALNS, CCPP-TPLP, DTSA, DJAYA) across four simulated grid maps of varying scales and complexity, as well as three real-world physical application scenarios (Yuhua Lake, Wisdom Lake/Qiulian River, and a tractor operating environment).

Simulation Performance: CCPP-LPC consistently outperformed comparison algorithms across all metrics: total path length, number of turns, repeated coverage ratio, and computational efficiency. The performance gap widened as environmental complexity increased. Notably, CCPP-LPC demonstrated the smallest standard deviations in path length and repeated coverage ratio, indicating superior solution stability.
Real-World Validation: In practical scenarios, including irregular lake environments and a 2.5-D tractor environment with elevation constraints, CCPP-LPC achieved shorter path lengths, fewer turns, and lower repeated coverage ratios compared to existing methods. In the tractor scenario, it also achieved a higher fitness value (indicating lower energy consumption).
Ablation Studies: Sensitivity analysis on the parameter $\beta$ determined that a value of 0.5 offered the best balance for computation time, while the proposed population update strategy was verified to be superior to both ACO and the previous CCPP-TPLP framework.

Significance and Claims
The paper claims that CCPP-LPC offers a practically valuable approach for complete-coverage optimization in multi-constrained, complex environments. By shifting from blind search to a guided evolution based on local path costs, the algorithm significantly improves computational efficiency and path quality. The authors emphasize that the method effectively reduces the number of turns and redundant coverage, which are critical for minimizing energy consumption and motion control complexity in real-world deployments. While the current work focuses on single-agent planning, the authors acknowledge that future work will address cooperative multi-agent planning to further enhance system efficiency in large-scale operations.