Complete Coverage Path Planning(CCPP)算法总结
本文参考一下论文
On Complete Coverage Path Planning Algorithms for Non-holonomic Mobile Robots: Survey and Challenges.” Journal of Information Science & Engineering, 2017
CCPP can be achieved by using single-robot(单个机器人) or multi-robot(多个机器人) coverage according to the size of the environments.
- Single-robot coverage is suitable for the coverage task in small environments such as homes, workplaces, and restaurants because of the simplicity of its design.
- Multi-robot coverage is appropriate for large environments because the coverage task is performed by dividing the large environment into small sub-regions and covering those sub-regions simultaneously. If one of the robots fails, other robots can easily cover the remaining environment.
Coverage efficiency of a CCPP algorithm is determined by
- total coverage ratio
- total time required for complete coverage
- total path length
- total energy consumption required to cover the path
A CCPP algorithm is
- complete if the robot sweeps the workplace such that union of all the sub-trajectories completely covers the workplace in a finite time.
- robust if it is complete and at least one active robot performs the coverage task.
- non-overlapping if the robot does not cover the already covered area.
一般来说，CCPP algorithms主要分为两类
- offline algorithms: use fixed information and environment is known in advance
- 例子：genetic algorithms, neural networks, cellular decomposition, spanning trees, spiral filling paths, and ant colony method
- online algorithms: use real-time measurements and decisions to sweep the entire target area.
Usually, CCPP algorithms generate a linear, piecewise path that composed of only straight lines and sharp turns. To make these paths applicable for real-time applications in such robots, smoothness must be incorporated in the paths.
A CCPP algorithm我们主要看三个子算法是如何做：
- the environment decomposition technique
- the sweep direction (for reducing the total number of turns)
- the optimal backtracking mechanism
Environment decomposition approach
- Random Coverage Path Planning: In random CPP, the robot in an arbitrary direction in a straight line until it collides with an obstacle. After the collision, the robot turns at a random angle and repeats the straight-line motion.
- Cell-Based Decomposition Techniques: Decompose free space within the environment into non-overlapping regions called ‘cells’ to perform the coverage. The decomposed environment is represented as an adjacency graph