Analysis of the working principle of the Comprehensive Coverage Path Planning Algorithm (CCPP)

1 Introduction

The task of complete coverage path planning (CCPP) problem is to determine a path that passes through all points in an area or a certain spatial range while avoiding obstacles.

Choset divides full coverage path planning algorithms into two categories: "online" and "offline", depending on whether the environment map is known a priori. The offline CCPP algorithm relies only on static environmental information and assumes that the environment is known a priori. However, in many cases, it may be unrealistic to assume sufficient prior knowledge of the environment. The online CCPP algorithm does not assume sufficient prior knowledge of the environment to be covered, but uses sensor data to scan the target space in real time. Therefore, these later algorithms are also called sensor-based coverage algorithms. Here I also recommend the new course "3D Vision Workshop" "In-depth Analysis of Spatial Synchronization (Calibration) of On-Vehicle Sensors for Autonomous Driving".

According to the different working principles of CCPP algorithms, they can be divided into random collision method, unit decomposition method, biological incentive method, template method, intelligent algorithm, etc. However, CCPP algorithms should meet the requirements that must be met for coverage, mainly:

The robot must pass through all points in the target area except obstacles and completely cover the target area;

The robot should try to avoid path duplication during the coverage process;

For ease of control, simple motion trajectories (e.g., straight lines or circles) should be used as much as possible;

Under the permitted conditions, obtain an "optimal" path (with the shortest total route length or the least energy consumption);

2 Random Collision Method

The random collision method is essentially an algorithm that uses time to exchange for space. Its idea is that the robot chooses any initial direction, drives the robot to walk in a straight line in the environment, covers the area within the straight line, and when the robot detects an obstacle, turns clockwise for a certain angle and repeats the above process. The coverage area of ​​this strategy is extremely random. Theoretically, given enough time, the robot can cover a sufficient space range, but this method is very inefficient. The advantages of this method are: no complex positioning sensors are required, usually only infrared sensors are required, and huge computing resources are not required; the disadvantages of this method are: there are a large number of repeated paths in the local range, and the environmental applicability is poor. When there are multiple sub-scenes in the environment, especially when two sub-scenes are connected by a narrow corridor, the random collision method may consume a lot of useless time to walk from one area to another.

In actual use, sweeping robots often get into trouble due to dynamic obstacles and other information. Calling random path coverage to escape from this dilemma is also a common method.

3 Unit decomposition method

The unit decomposition method is to divide the free area in the entire space into simple sub-areas with no overlapping areas by some method. Each sub-area is called a cell, and the union of these cells just fills the entire free space. The robot uses a simple covering method (such as reciprocating motion or spiral motion) to cover each sub-area. When the coverage of each sub-area is completed, the full coverage of the entire area is achieved.

Take the trapezoidal decomposition method as an example. It is the simplest precise cell decomposition method. This method first makes the robot walk along the edge of the space to build a map of the entire area, and then uses a vertical cutting line to scan the entire area from left to right. When the cutting line meets the vertex of the polygonal obstacle, a sub-area will be decomposed. In this way, the entire free space is decomposed into many sub-areas, each of which is a trapezoid. The robot reciprocates in each sub-area to cover the sub-area. The trapezoidal decomposition method is shown in the figure.

Other representative methods include: ox-plowing unit decomposition method [1,2], Morse decomposition method [3,4], line scan segmentation method, etc. I will not describe them in detail here. If you are interested, you can read the references.

4 Biostimulation

Yang and Luo applied the bio-inspired neural network model to the full coverage path planning of the cleaning robot. They first modeled the environment and represented it using a grid map. Each grid point corresponds to a neuron cell, and proposed a shunt equation to calculate the degree of excitation or inhibition of the surrounding neurons on the current neuron. The shunt equation is shown below.

Where xi represents the state of the i-th neuron; A is a non-negative constant, indicating the decay rate of neuron activity; B and D represent the upper and lower limits of the neuron state; Ii represents external input, and ωij represents the connection weight between the i-th neuron and the j-th neuron, which is generally calculated from the distance between the two neurons. The activity value connection diagram of the i-th neuron is shown in the figure.

When the robot is in a certain grid, it will calculate the activity values ​​of the surrounding neurons and select the grid with the largest activity value as the next step. The advantages of the biological incentive method are good applicability, good performance in obstacle avoidance and real-time performance, and the disadvantage is that it may lead to a high path repetition rate.

5 Template method

The template method was proposed by Neumann de Carvalho R et al. It relies on the prior knowledge of the two-dimensional environment map and can handle unexpected obstacles that are not represented on the map. They predefine the robot's movement behavior as seven fixed templates, as shown in the figure below. These templates contain all the situations that the robot may encounter in the map. The robot moves in the map according to the templates, and finally achieves full coverage of the map.

The advantages of the template method are simple principles, low computational consumption, and the ability to handle dynamic obstacles; the disadvantages are that it requires prior knowledge of maps, poor applicability, and low intelligence. Here we also recommend the new course "In-depth Analysis of Spatial Synchronization (Calibration) of On-board Sensors for Autonomous Driving" from the "3D Vision Workshop".

6 Intelligent Algorithms

Wang[5] combined genetic algorithm with the ox-plowing unit decomposition method. After using the dividing line to divide the entire free space into sub-regions, each sub-region was encoded by genetic algorithm, and the base point information between sub-regions was restored. The optimal covering sequence was obtained by genetic algorithm, and coverage was achieved in each sub-region in the form of reciprocating motion, thus converting the CCPP problem into the traveling salesman problem (TSP).

Zhang[6] introduced the ant colony algorithm into the unit decomposition method, defined the distance matrix according to the connectivity information between two sub-regions, and used the ant colony algorithm to optimize the coverage order according to the distance matrix. Their experimental results show that the combined algorithm can not only ensure the coverage of all workspaces, but also plan shorter paths, smaller path overlap rate, and higher planning efficiency. However, for complex environments, it is difficult to avoid the recovery area near obstacles.