Smooth Complete Coverage Trajectory Planning Algorithm for a Nonholonomic Robot

Abstract

The complete coverage path planning is a process of finding a path which ensures that a mobile robot completely covers the entire environment while following the planned path. In this paper, we propose a complete coverage path planning algorithm that generates smooth complete coverage paths based on clothoids that allow a nonholonomic mobile robot to move in optimal time while following the path. This algorithm greatly reduces coverage time, the path length, and overlap area, and increases the coverage rate compared to the state-of-the-art complete coverage algorithms, which is verified by simulation. Furthermore, the proposed algorithm is suitable for real-time operation due to its computational simplicity and allows path replanning in case the robot encounters unknown obstacles. The efficiency of the proposed algorithm is validated by experimental results on the Pioneer 3DX mobile robot.

Keywords: complete coverage; mobile robot; path planning; path smoothing; velocity profile optimization.

Figure 1

Solution examples of different methods for the TSP problem. (a) The RSTC algorithm, (b) The PT algorithm, (c) The ACO algorithm, (d) The HNN algorithm.

Figure 2

The pipeline of the smooth complete coverage path planning algorithm.

Figure 3

Example of the complete coverage path planning for the known environment step-by-step. The real obstacles collected by SLAM algorithm are presented with green dots. (a) Low resolution occupancy grid map, (b) Subdividing of grid cells, (c) The spanning tree (blue line), (d) Complete coverage path (black line).

Figure 4

Illustration of the sharp turn smoothing by two clothoids.

Figure 5

The enlarged part of the coverage path with two positions of the robot: (1) the robot’s starting position and (2) the robot’s position at the obstacle corner. The obstacle cell is shown in gray, the robot’s positions in dashed circles, the robot’s orientation in green, the spanning tree in blue, the RSTC path in black, and the smoothed path in red.

Figure 6

The smoothed path from Figure 4 (red line) and the tracked trajectory (green diamonds).

Figure 7

The calculated linear and angular velocities (blue line) and real linear and angular velocities (magenta diamonds) at which the robot tracked the trajectory.

Figure 8

The comparison of the CCPP and SCCPP algorithms in the Lab scenario with the presented RSTC spanning tree (blue line), the RSTC path (black line), the smoothed path by the SCCPP algorithm (red line), the executed path by the CCPP and SCCPP algorithm (green line), the reference velocity profile (blue line), and the actual velocity profile (red line). (a) The CCPP path in the Lab scenario. (b) The SCCPP path in the Lab scenario. (c) The CCPP velocity profile in the Lab scenario. (d) The SCCPP velocity profile in the Lab scenario.

Figure 9

The RSTC algorithm in the Lab scenario with the presented RSTC spanning tree (blue line), the RSTC path (black line), the smoothed path by the SCCPP algorithm (red line), and the executed path by the smoothed RSTC algorithm (green line). Red points are the robots’ position where the replanning algorithm is executed. (a) The smoothed RSTC path in the Lab scenario before replanning. (b) The smoothed RSTC path in the Lab scenario after replanning.

Figure 10

The SCCPP algorithm in the Aula scenario, which presents the smoothed path with red line and the executed path with green line.

Figure 11

The SCCPP algorithm in the Gallery scenario: the RSTC spanning tree (blue line), the smoothed path (red line), and the executed path (green line).

Figure 12

The complete coverage of the CCD* algorithm with the path and noted redundant numbers of cell visits (from 1 to 9).

Figure 13

The complete coverage of the HDCP algorithm with hexagonal cell grid.

Figure 14

The wall following algorithm after SCCPP: driven trajectory (red line), and robot’s footprint in every point on the trajectory is presented degraded from black to gray.

Figure 15

The calculated SCCPP path (red line) and trajectory tracked by the Pioneer 3DX robot (green line).

Figure 16

Calculated linear and angular velocities (blue line) and linear and angular velocities, while the Pioneer 3DX robot is tracking the trajectory (magenta line).

Figure 17

Real linear velocity, while the robot Pioneer 3DX is following the trajectory (magenta line), deviates from the applied linear velocity (blue line).