1. Introduction
Complete coverage path planning (CCPP) aims to determine a path that visits all points within a region or workspace while avoiding obstacles.
Choset classifies CCPP algorithms by whether the environment map is known a priori into two categories: offline and online. Offline CCPP algorithms rely only on static environment information and assume the environment is known in advance. In many cases, this assumption is unrealistic. Online CCPP algorithms do not assume full prior knowledge of the environment to be covered, and instead use sensor data to scan the workspace in real time. These later algorithms are therefore also called sensor-based coverage algorithms.
Based on their operating principles, CCPP algorithms can be grouped into random collision methods, cell decomposition methods, biologically inspired methods, template methods, and intelligent algorithms. CCPP solutions should generally satisfy the following requirements:
- The robot must visit all points in the target region excluding obstacles, achieving full coverage of the workspace.
- The robot should minimize path repetition during coverage.
- For ease of control, the motion trajectory should be as simple as possible (for example, straight lines or circles).
- When possible, obtain an "optimal" path under given criteria (for example, minimum total length or minimum energy consumption).
2. Random Collision Method
The random collision method is essentially a time-for-space strategy. The robot selects an initial direction and drives straight to cover the area along that line. When an obstacle is detected, the robot turns a fixed angle clockwise and repeats the process. The resulting coverage is highly random. In theory, given sufficient time, the robot can cover a large portion of the workspace, but the method is inefficient.
Advantages: it does not require complex localization sensors and typically only needs simple sensors such as infrared, while demanding little computational resource.
Disadvantages: it generates many local repeat paths and fits poorly to structured environments. When the environment contains multiple subregions connected by narrow corridors, random collision methods may spend a large amount of time moving between regions.
In practice, consumer vacuum robots often become trapped by dynamic obstacles; invoking a random coverage strategy to escape such situations is a common tactic.
3. Cell Decomposition Methods
Cell decomposition divides the free space into simple, nonoverlapping subregions called cells. The union of these cells exactly fills the free workspace. The robot covers each cell using simple motion patterns (for example, back-and-forth or spiral motion). Covering every cell results in full coverage of the entire area.
For example, trapezoidal decomposition is a basic exact cell decomposition method. The robot first traverses the workspace boundary to build a map, then scans the area from left to right with a vertical cutting line. When the cutting line meets a polygonal obstacle vertex, a new cell is formed, so the free space is decomposed into trapezoidal cells. The robot covers each trapezoid by back-and-forth motion.
Other representative methods include boustrophedon decomposition, Morse decomposition, and line-sweep partitioning. Interested readers can consult the cited references for details.
4. Biologically Inspired Methods
Yang and Luo applied a neural network model inspired by biological systems to coverage planning for cleaning robots. They model the environment using a grid map, where each grid cell corresponds to a neuron. They proposed a diffusion equation to compute excitation or inhibition from neighboring neurons. The diffusion equation is as follows.
The variable xi denotes the state of neuron i; A is a nonnegative constant representing the decay rate of neuron activity; B and D represent upper and lower bounds on neuron states; Ii denotes external input; ωij is the connection weight between neuron i and neuron j, typically computed from the distance between the two neurons. The activity landscape for neuron i is shown below.
When the robot is at a grid cell, it computes the activity values of neighboring neurons and selects the neighbor with the highest activity as the next position. Biologically inspired methods are adaptable and perform well for obstacle avoidance and real-time response, but they may produce higher rates of path repetition.
5. Template Methods
Template methods define a set of fixed motion templates based on a known 2D environment map. The approach can handle unexpected obstacles not represented on the map. The robot's motion behavior is predetermined as a small set of templates that cover typical situations encountered in the map; the robot follows the templates to achieve full map coverage.
Template methods are simple and computationally light, and they can handle dynamic obstacles. Their drawbacks include the need for prior map knowledge, limited applicability, and relatively low autonomy.
6. Intelligent Algorithms
Wang combined genetic algorithms with boustrophedon cell decomposition. After decomposing the free space into cells, genetic encoding represents each cell and the base points between cells. A genetic algorithm then searches for an optimal coverage sequence, while coverage within each cell uses back-and-forth motion. This converts the CCPP problem into a traveling salesman problem (TSP).
Zhang introduced ant colony optimization into cell decomposition. They define a distance matrix based on connectivity between cells and use the ant colony algorithm to optimize the coverage order. Their experiments show that the combined method ensures full workspace coverage while producing shorter paths, lower overlap, and higher planning efficiency. However, in complex environments it is still difficult to avoid recovery regions near obstacles.
References cited in the original text provide further technical details.
