[Review] Coverage Path Planning with Realtime Replanning for 3D underwater structures

February 11, 2019 ยท 5 minute read

Conference Paper Review 11-02-2019

Coverage Path Planning with Realtime Re-planning for Inspection of 3D Underwater Structures

E. Galceran et al., ICRA 2014, Hong Kong, DOI: 10.1109/ICRA.2014.6907831

The Problem

Coverage Path Planning (CPP) Is a task to find the optimal path for a given surface or shape for an agent to follow such that the agent covers the surface. This could be physical traversal, or in this case the coverage of a camera on an autonomous underwater vehicle (AUV). This paper presents a technique for online dynamic adjustments to a path as a result of sensor measurements while using a a-priori planned path as a prior.

Aims of the Paper

Introduces a novel replanning algorithm based on stochastic trajectory optimisation that reshapes a pre-computed path on the fly based on sensor data of a target structure. They demonstrate this method on autonomous underwater vehicles in conjunction with an offline coverage path planning method on 2.5D Bathymetric maps of the sea floor.

Paper Summary

The method they have proposed is composed of two parts:

  1. Off-Line Coverage Path Planning
  2. Real-Time Replanning

The focus of this paper is explaining the real-time replanning portion of the method. The off-line coverage path planning method essentially takes a Bathymetric map of the contours of the target region (i.e. a depth map) and uses that to plan a coverage path. This is done by discretising the depths at which the robot can operate based on the vertical sensor range and a Boustrophondonic like path is planned in 3 dimensions around the depths at a desired distance from the target surface. This coverage path is then used as a prior or nominal path for the AUV to follow in its inspection task.

The purpose of the real-time replanning is then to incorporate fine grained details of the surface which may have been missed by the high level planner by using live sensor data to ensure that the desired distance is kept constant. This allows robustness to uncertainties in movement and surface. The methodology consists of two steps which are repeated on segments on the path until the coverage is complete:

  1. A segment of path is selected and the nominal path is drawn from memory.
  2. The STOMP (Stochastic Trajectory Optimisation for Motion Planning) algorithm is used to adapt the nominal path to the actual surface structure.

STOMP works by first generating several noisy trajectories based on the nominal trajectory. The linear combination of the noises at each timestep is then used to modify the trajectory where the weights are determined by the smoothness (linear acceleration) of the generated trajectory. This is repeated until the trajectory cost converges to a minima. The trajectory cost is determined by a combination of trajectory smoothness, and position error with respect to the desired distance from the surface. A parameter R determines the length of the trajectories which are passed to STOMP. This optimisation in this work only takes place on the flat 2D plane.

2 experiments of this method working on a real AUV - The Girona 500 - are then presented. The AUV in this instance was equipped with side-looking multibeam sonar and stereo cameras, hence a passing trajectory is all that is required for inspection. Results of inspections of a concrete breakwater and a large underwater boulder known as L’Amarrador are presented. In both we see that the replanning makes a significant difference to the AUV trajectory when compared to the nominal path. and almost enough data is collected in both instances to produce 3D models of the inspected subjects.

Paper Review

The author’s of this paper clearly convey and demonstrate a method which does indeed provide a solution to coverage path planning in uncertain environments. A short and succinct related work section suggests that previous work was used as inspiration for the random sampling method used in this work. This paper is a “part 2” to a previous paper on the off-line coverage path planning with which they provide an overview for. The explanation into the real-time replanning is well thought and and appears fairly complete with few questions raised by myself in reading.

The approach itself appears to be fairly intuitive and harks back to the plan/correct loop that is used in applications such as SLAM which is interesting. This is most apparent in the images of the planned route vs the actual replanned routes which appear to be rather different, although it is difficult to determine from their images which is better as no quantitative results are provided in the paper (percentage coverage, time taken, etc). Another observable effect is the jerkiness of the transition between optimised paths as can be seen by the white lines in figure 4. It appears that this is due to the requirement that at the end of a STOMP’d segment, a linear trajectory is added between the end of the segment and the start of the next one. Such a lumpy trajectory (which may be down to error in the case of the concrete block demonstrations with errors +/-2m) will be inefficient in terms of energy consumption and difficult in terms of manoeuvrability. Perhaps optimising overlapping trajectories to ensure smoothness at overlap points may be a solution.

Overall a relatively interesting paper that provides one method of solving the 3D coverage path planning under uncertainty solution. The ideas behind the paper are worth considering and I am surprised there are not more citations. The paper was well laid out and the method well explained. The experimentation could have done with more quantitative results either in simulation or reality which could prove the importance of the dynamic replanning. I would perhaps recommend that people interested in the CPP problem skim this paper for historical context and for the baseline ideas.