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

Leave a Comment