Sage Journals: Discover world-class research

Abstract

Advancements in robotics and autonomous systems are being deployed nowadays in many application domains such as search and rescue, industrial automation, domestic services and healthcare. These systems are developed to tackle tasks in some of the most challenging, labour intensive and dangerous environments. Inspecting structures (e.g. bridges, buildings, ships, wind turbines and aircrafts) is considered a hard task for humans to perform and of critical importance since missing any details could affect the structure’s performance and integrity. Additionally, structure inspection is time and resource intensive and should be performed as efficiently and accurately as possible. Inspecting various structures has been reported in the literature using different robotic platforms to: inspect difficult to reach areas and detect various types of faults and anomalies. Typically, inspection missions involve performing three main tasks: coverage path planning, shape, model or surface reconstruction and the actual inspection of the structure. Coverage path planning ensures the generation of an optimized path that guarantees the complete coverage of the structure of interest in order to gather highly accurate information to be used for shape/model reconstruction. This article aims to provide an overview of the recent work and breakthroughs in the field of coverage path planning and model reconstruction, with focus on 3D reconstruction, for the purpose of robotic inspection.

Keywords

Robotic inspection coverage path planning 3D reconstruction anomaly detection

Introduction

The ongoing developments in the field of autonomous robots have witnessed a growth in utilizing different robotic platforms in real life applications. The interesting application of robotic inspection involves many robotic application domains employing different kinds of robotic systems such as unmanned arial vehicles (UAVs), unmanned ground vehicles (UGVs) and marine robots. Inspecting large structures is particularly important in applications that require maintenance, fault traceability, anomaly and defects detection and model digitizing.

Technically, inspecting structures requires various robotic capabilities such as localization in the environment where the structure exists, path planning and navigation in order to compute a set of achievable routes, sensing and perception in order to gather information about the structure from different viewpoints along the route. As such, it is important to equip the robot with intelligent sensing capabilities that enhance the quality of the information gathered in order to reconstruct and inspect the structure of interest accurately. While utilizing robotic systems in inspection applications, majority of existing approaches attempt to reduce the computational cost (time need to compute and execute the inspection mission), avoid collision with the structure of interest and gather information with sufficient resolution for anomaly detection.

Initial attempts that involve robots inspecting structures in real-life scenarios were done in different environments and for different applications. For instance, Nokia started recently using SecuTronic INSPIRE drones for tower inspection, line of sight testing and radio site planning in order to optimize telecomm networks.¹ San Diego Gas and Electric Company is using drones for inspecting power lines, pipelines and other remote infrastructures.² Roads and Maritime Services in Australia is using grit blasting robots for cleaning bridges by scanning areas, creating 3D maps and calculating the sand blasting force.³ Boeing, the largest aerospace company in the world, started to use a UAV platform for inspecting aircraft for lightning scratches and burns.⁴ Performing inspection missions with robotic platforms reduces the cost and time and increases the accuracy in comparison to conventional inspection processes.

The two main challenging research topics related to inspection are coverage path planning (CPP) and workspace 3D reconstruction. CPP is the process of computing a feasible path encapsulating a set of viewpoints through which the robot must pass in order to completely scan the structure of interest. The set of generated viewpoints affects CPP since it defines the positions and orientations of the sensor from which the data will be perceived affecting the overall coverage. The efficiency of the CPP algorithm is measured by the planning completeness and convergence speed. On the other hand, workspace 3D reconstruction is a task during which the set of high-quality data, gathered during the coverage path execution, is fused in a mapping procedure to provide the complete and accurate model to be used for inspection. The accuracy of the reconstructed model is an important inspection performance metric, which is evaluated by the resolution of the gathered information and how close the reconstructed model is to reality. The method of information gathering, whether it is continuous or discrete, and the 3D mapping or reconstruction methods (online or offline) are all considered contributing factors that will affect the model quality and the inspection performance.

The inspection process usually starts by generating a set of viewpoints, together with the optimized path to follow to visit those view points, followed by a data gathering step, during which the robot uses the onboard sensors to collect data about the structure. Next, the data gathered will be used to construct a 3D model of the structure that will be used for inspection. This inspection sequence is depicted in Figure 1. Coverage completeness is used to quantify and evaluate the quality of the 3D reconstruction models and to determine whether all the critical areas have been covered during the inspection. The overall robotic inspection process could be performed manually or autonomously, with or without a reference model, online or offline (coverage path generation) and continuous or discrete (viewpoints generation along the path) based on the application scenario, the nature of the structure of interest and the source of the defects.

Figure 1.

The main components of the robotic inspection system.

In this survey article, the main components of the robotic inspection process are defined and reviewed in separate sections. Section ‘CPP’ focuses on CPP and its components. Coverage exploration and viewpoint generation strategies will be reviewed in section ‘Coverage exploration and viewpoint generation’ and coverage completeness in section ‘Coverage completeness’. In section ‘Workspace 3D reconstruction’, different 3D reconstruction methods are discussed including 3D environment mapping in section ‘3D environment mapping’ and 3D structures reconstruction in section ‘3D structures reconstruction’. An overview discussion of the main aspects of robotic inspection is presented in section ‘Discussion’. Finally, conclusions are drawn in section ‘Conclusion’.

CPP

CPP is a task during which a robot must explore in details a workspace, whether it was an environment or a structure of interest,^5
–7 and determine in the process the set of locations to pass through avoiding all possible obstacles. CPP is important in applications where the complete coverage of an area has to be performed, similar to robots used for floor cleaning, lawn mowing, agricultural surveying, surveillance, structure painting, bridge grit blasting, geo-spatial mapping and object reconstruction. Generally in CPP, either a reference model of the structure or the environment is provided in advance or the model is reconstructed using the sensing capabilities of the robot in real time.^5,7

Galceran and Carreras⁵ provided an extensive review of the most successful CPP methods discussing their functionalities and the applications using these methods. CPP can be performed either offline using a model encapsulating the static information of a known environment or online where real-time sensor measurements are used to cover the workspace.^5,6 The classical exact cellular decomposition category in the study by Galceran and Carreras⁵ describes mainly offline algorithms, while the online algorithms are described under morse-based cellular decomposition, landmark-based topological coverage, contact sensor-based coverage of rectilinear environments and graph-based coverage categories. In addition, grid-based coverage, 3D coverage, optimal coverage, coverage under uncertainty and multi-robot coverage categories include both online and offline algorithms.⁵

The main components of CPP include defining the exploration method, generating viewpoints and planning an optimized path, and quantifying the coverage completeness. The viewpoints generation and path planning components depend directly on the exploration method used to cover the structure of interest. Viewpoint generation and coverage exploration will be surveyed in detail in section ‘Coverage exploration and viewpoint generation’. CPP can be divided into discrete path planning and continuous path planning. Discrete CPP attempts to find a discrete set of viewpoints covering the workspace or structure, followed by finding an admissible route passing through the viewpoint set in an optimal manner.^8,9 Continuous CPP includes performing continuous sensing along the trajectory to be followed.⁹

Discrete coverage path planning

Discrete CPP algorithms divide the planning problem into two steps: viewpoints generation to generate a discrete set of viewpoints and optimal path generation using multi-goal planning to connect the viewpoints. Discrete CPP algorithms provide sequenced waypoints for the robot to follow. The robot has to stabilize and perceive views at each waypoint in order to avoid missing sensory observations.

The work presented in the study by Englot and Hover,⁷ Bircher et al.⁸ and Hover et al.¹⁰ uses an offline discrete sampling-based CPP algorithm to provide full sensory coverage of a 3D structure. Bircher et al.⁸ inspected different 3D structures like the Big Ben and other structures using a UAV platform equipped with a visual-inertial (VI) camera utilizing the previous mentioned two steps: solving an art gallery problem (AGP) to find well configured viewpoints in space and then computing the optimal path with the lowest computational cost by solving a travelling salesman problem (TSP). Lin-Kirighan heuristic (LKH) TSP solver described in the study by Helsgaun¹¹ produces high-quality solutions in short time and it was used for solving the TSP in the study by Bircher et al.⁸ This TSP solver includes a modified LKH heuristic rules in order to direct and restrict the search and achieve optimality effectively. The search strategy is modified and restricted to select small but large enough candidate sets based on a sensitive analysis of spanning trees. The research conducted in the study by Englot and Hover⁷ and Hover et al.¹⁰ inspected a ship hull to detect mines using an underwater robot by solving a coverage sampling problem using watchman route and redundant roadmap algorithms (first step) and then finding the coverage path shown in Figure 2 by solving a multi-goal planning problem using probabilistic road map (PRM)¹² and rapidly exploring random trees (RRT)¹³ algorithms (second step). The approaches described in the study by Englot and Hover,⁷ Bircher et al.⁸ and Hover et al.¹⁰ are iterative approaches used to achieve optimal or asymptotically optimal solutions.

Figure 2.

Coverage path improvement: (a) initial generated coverage path and (b) the improved path. Source: Reused from the studies by Englot and Hover⁷ and Hover et al.¹⁰

Sampling-based path planning is often used in conjunction with discrete CPP to find a collision free path that passes through the viewpoints optimally. The two main properties that should be analysed for any sampling-based path planning algorithm include the probabilistic completeness and convergence. The most popular sampling-based algorithms that guarantee probabilistic completeness are PRM and RRT.¹⁴ Karaman and Frazzoli¹⁴ introduced the optimal version of the previously mentioned popular algorithms (PRM* and RRT*) by analysing their cost and optimality. RRT* introduced in the study by Karaman and Frazzoli¹⁴ was used in the work of Bircher et al.⁸ as a local planner in the case of obstacle existence. Research presented in the study by Papadopoulos et al.¹⁵ proposed a new sampling-based path planning algorithm called random inspection tree algorithm (RITA), used particularly for inspection, and it guarantees both probabilistic completeness and optimal global path convergence. This algorithm deals with the visibility and control problems simultaneously instead of dividing the planning problem into two subproblems. Elizabeth et al.¹⁶ also proposed a new sampling-based planning algorithm that is based on both RRT* and rapidly exploring random graphs (RRG),¹⁷ and it guarantees both optimality and probabilistic completeness. It generates optimal trajectories based on large task specifications represented as deterministic mu calculus.

Continuous CPP

Continuous CPP is mainly focused on following a trajectory while perceiving sensed information continuously. Classical path planning algorithms are the most related algorithms to continuous CPP including cell decomposition, generalized Voronoi diagram and grid-based planning. These algorithms are adapted to satisfy coverage constraints.⁵

A grid-based method was used in the study by Valente et al.,⁶ where a prior known map was decomposed into cells that should be covered by a UAV in an optimal path minimizing: the number of turns, turning angle and coverage completion time, in order to insure the continuity of the path. The grid-based method is easily converted to a grid graph consisting of nodes (representing the centre of the cells) and edges. An optimal solution of this grid graph represents a continuous smooth coverage trajectory that facilitates the continuous sensing of the environment of interest. This trajectory is found in the work of Valente et al.⁶ using three solution options including tree-based search, heuristic-based search using wavefront planner and backtracking method and the pedestrian pocket algorithm that divides the grid cells into smaller cells to improve the computational cost. Another example of continuous coverage is illustrated in the studies of Atkar et al.,^18,19 where an auto body painting planning method was developed to segment complex 3D models like a car into simple topological pieces (cells) and plan contiguous coverage paths over these segments minimizing geodesic curvature and providing uniform painting. The segmentation part of the algorithm is a cell decomposition performed using a slicing function that depends on surface geometry and topology to generate simple cells. In the study by Cheng et al.,²⁰ a UAV platform was used to cover different urban buildings using planar looping trajectories that minimizes the coverage time considering the dynamics of the UAV. These trajectories are designed by developing simplified coverage models converting the problem to coverage of non-planar surfaces instead of complex 3D structures. Also, they are designed such that the data captured by the sensors mounted on the UAV platform will cover the urban buildings of interest continuously.

Coverage exploration and viewpoint generation

In the majority of the surveyed literature, coverage exploration algorithms are classified into model-based exploration and non-model-based exploration. The model-based exploration methods depend on the existence of a model of the workspace or the structure, while the non-model-based exploration is performed by exploring and planning paths without a prior knowledge of the structure.^21,22

Viewpoints generation and path planning are considered critical in the robotic inspection process since it aims to output an optimized path based on the generation of admissible set of viewpoints that covers the structure or environment of interest. It is performed in the literature using various techniques based on the inspection application and the coverage exploration method used.

Model-based viewpoint generation

The main aim of model-based methods is to provide a set of viewpoints that explores a structure or an environment in such a way that every area of the structure is visible.²¹ Many of these approaches consider properties such as sensor specifications that determine frustum field of view (FOV) and shadow effects, object shapes and material properties and image overlapping properties used during image integration.^21,22 Model-based view planning methods are further divided into three categories based on the information embedded in the model of the structure including set theory methods, graph theory methods and computational geometry methods.^21,22

The set theory methods depend on two significant matrices: visibility matrix and measurability matrix.^21,22 The visibility matrix stores the visibility information of each object surface point in the view point space, while the measurability matrix stores measurement quality information based on sensor frustum shape, sensor shadow effects and measurement variations along the frustum.^21,22

The graph theory methods depend on graph data structures that consist of nodes and arcs.^21,22 The nodes represent object aspects that are the viewpoint space regions with equivalent visibility, while the arcs represent the aspects’ adjacency.²¹ These aspect graphs introduce computational issues and difficulties, which make them not suitable for representing a view planning problem.²¹

The computational geometry methods mainly deal with solving an AGP to generate the set of viewpoints for structure coverage.²² AGP deals with polygonal areas in order to determine the minimum number of viewpoints that covers a structure or environment.²²

Set theory and computational geometry methods are the two most commonly used categories in the literature to generate an admissible set of viewpoints for coverage planning. Scott²¹ presented a multi stage model-based view planning approach using a set theory method and improved the concept of the measurability matrix to reconstruct different object shapes using different laser scanning range cameras with different capabilities. This approach starts with an exploration phase during which a rough model of an object is constructed. The model is then used to scan precisely the object during a measurement phase resulting in a high-quality reconstructed model. In the studies by Englot and Hover,^7,9 Hover et al.¹⁰ and Englot and Hover,²³ a set of stationary views providing full coverage of a ship hull was obtained using a polygonal mesh of the ship hull and solving a set cover problem that generates a redundant roadmap consisting of the viewpoints. In the study by Dornhege et al.,²⁴ different search-based algorithms were used utilizing a known map in order to generate a set of sequenced viewpoints that provide full coverage. It was found that using set cover method with TSP provides the best set of viewpoints in terms of computation time and path cost.²⁴ Another model-based view planning method related to computational geometry methods was used in the study by Bircher et al.⁸ This method uses a triangular mesh of the desired structure to determine the set of viewpoints with the best configurations by solving it as an AGP problem. Moreover, Janousek and Faigl²⁵ presented another model-based coverage method that uses triangular meshes of the objects of interest, together with the free space tetrahedral divisions in order to generate the motion planning roadmap and the coverage spaces, and finally find the inspection path as shown in Figure 3.

Figure 3.

Coverage path generation using self organizing maps: (a) coverage planned path across the objects of interest labeled with red and (b) tetrahedral covering spaces. Source: Reused from the study by Janousek and Faigl.²⁵

Exploratory-based viewpoint generation

When a robotics system encounters an unknown environment or object, it needs to perform exploratory view planning concurrently with the reconstruction of the environment or the object. The sequence of iterative steps involved in solving this problem include robot localization, scanning, registration and integration and planning the next viewpoint.²⁶ Next best view (NBV) strategies are popular iterative algorithms used as exploratory-based view planning algorithms to cover and model structures in indoor environments. NBV strategy performs real-time exploratory sensing and decision-making to acquire a suitable sensor view that will be used with all the other previously obtained views to decide on the best location of the next view.^26
–28 In general, exploratory view planning algorithms like NBV are divided into three categories volumetric methods, surface-based methods and global-based methods.

Volumetric methods model the workspace as a grid of voxels and select the viewpoints based on the volume occupied by the structure. Surface-based methods, on the other hand, use the structure’s surface geometry to select the next views. Surface-based methods include three techniques based on the used surface geometry occluded edges, contour following and parametric surfaces. The occluded edges technique detects the geometric jump edges in the range images, indicating surfaces that are not yet sampled based on the premise that occluded edges infer not sampled surfaces.^21,22 The contour following technique involves covering a portion of the object of interest by a sensor while keeping it in close proximity to the surface. This technique works well for simple shapes but struggles with geometrically complex structures due to the complexity of collision avoidance in these structures. The parametric surface representations of super-quadric models are commonly used for simple objects or segmented complex objects since they are known to be flexible and compact in representation.

There has been many recent developments on NBV algorithms to enhance view planning and to make it more efficient. Vasquez-Gomez et al.²⁶ presented a NBV algorithm that enhances the scanning quality and reduces the navigation distance by following a search-based paradigm where the NBV is selected by evaluating a set of candidate views using a utility function. The utility function evaluates each view against different constraints such as information gain, positioning constraints (view reachability), sensing constraints (sensor FOV) and registration constraints (scans overlapping area). Krainin et al.²⁷ proposed a NBV method that gathers views by grasping the object of interest and moving it in the camera FOV in order to collect higher quality views, thus increases the dimensionality of the view planning problem. The gathered views incorporate the manipulator motion cost, which tends to increase based on the quality of the views. High-quality poses are selected based on the trade-off between the actuation cost and the view quality.

Another NBV method was proposed in the study by Vásquez and Sucar²⁸ which also follows the search-based paradigm but plans for good views in the presence of positioning errors in two phases: the first phase evaluates the candidate views, and the second phase preforms another re-evaluation. These views are re-evaluated using the convolution of two functions: the utility function and a Gaussian function that accounts for the positioning errors. A new exploration algorithm called nearest neighbour NBV (NN-NBV) was presented in the study by Quin et al.,²⁹ which reduces the number of evaluated viewpoints considering the closest viewpoints in the configuration space. It also reduces the number of gain calculations, overall computations and the time required to perform the exploration.

Coverage completeness

The completeness of CPP is assessed by quantifying the percentage of the covered part of the structure compared to the original structure model. This component was presented in the literature as a critical part of the planning algorithm iterations and as a significant performance criteria.

The coverage completeness of model-based algorithms can be computed directly based on the baseline used in the planning procedure. Wallar³⁰ proposed a model-based coverage planner called planner for autonomous risk-sensitive coverage, used by a team of quadcopters to maximize area coverage in the xy plane of a previously known environment. The area coverage was quantified using a Monte-Carlo process where a large number of randomly generated points were sampled inside the xy bounding box of the scene.³⁰ The percentage of the total area covered was computed using the ratio of the number of sampled points that belongs to any of the sensed areas to the total number of sampled points.³⁰ In addition, the coverage planning algorithm described previously in the study by Cheng et al.²⁰ performed complete coverage for urban features by generating spiral trajectories based on the sensor position and footprint area. The coverage completeness was guaranteed by calculating the conical FOV sensor footprint surface area and the number of generated footprints along the coverage path followed around the simplified features (hemispherical and cylindrical shapes).²⁰

The non-model-based coverage planning completeness is calculated by evaluating the NBV and computing the termination condition. A coverage and exploration algorithm is proposed in the study by Heng et al,³¹ a micro ariel vehicle (MAV) platform equipped with a RGB-Depth (RGBD) sensor to operate in an unknown environment. The coverage is measured by the number of visible voxel faces contained in the viewing frustum given a state position and a discrete yaw angle. The visible faces are found using a similar approach to z-buffering in which the pixels stored in the buffer correspond to the closest voxels with respect to the camera.³¹ The algorithm tends to maximize the coverage by enforcing constant changes in the yaw angle as the MAV is moving towards the goal position that is chosen at each iteration according to its information gain (number of unexplored voxels).³¹ The work presented in the studies by Vasquez-Gomez et al.²⁶ and Vásquez and Sucar²⁸ preformed complete model reconstruction under positioning error by computing NBVs that provide new information or scans, which could be registered and combined with the previous scans using iterative closest point (ICP). The views generated at each iteration are evaluated using a utility function that assesses the view according to the overlapping percentage, the scan quality and the distance travelled from the previous view. All of these comparisons are performed with respect to a voxel map that represents the reconstructed model.^26,28 In this work, the coverage percentage was quantified indirectly utilizing the overlapping percentage at each step. In addition to this, Lee and Lee³² proposed a hyprid terrain coverage framework (HTCF) that includes a hyprid decision module, which considers the sloped surface conditions and differentiate between gradual and steep terrain in order to apply one of the following techniques: planar terrain coverage algorithm and a spiral path terrain coverage algorithm. The hybrid decision module checks the terrain coverage completeness at each step before deciding the suitable coverage technique until the terrain is completely covered.

Workspace 3D reconstruction

Detailed 3D models are increasingly being required for different kinds of applications such as structure inspection, urban planning, terrain surveillance, indoor mapping and navigation. In general, a workspace 3D reconstruction process involves four steps: viewpoint planning, scanning, registering and integration.²² The 3D reconstruction depends on localization that is done as part of simultaneous localization and mapping (SLAM), an approach used in most reconstruction and mapping applications. Workspace 3D reconstruction is represented in the literature as a 3D mapping application of an environment or as a 3D reconstruction for a structure or object of interest.¹⁰ We will survey each of these fields separately in the following sections.

3D environment mapping

3D mapping techniques are used in different robotic application scenarios such as search and rescue and surveillance scenarios. In some scenarios, fixed trajectories are followed in order to map an environment, while in others, CPP methods are used to ensure coverage of certain areas. Faessler et al.³³ proposed a system that can perform two significant operations autonomously, executing a given trajectory and providing a live dense 3D map using a UAV platform equipped with a camera. The main aspect of the system is the semi-direct visual odometry (SVO) that consists of two main threads: motion estimation thread that determines the camera position with respect to the map and mapping thread that extends the map while exploring the area. The real-time dense 3D map reconstruction was performed using an algorithm called regularized monocular depth algorithm. This algorithm is used to build dense depth maps in two steps: depth filter formulation and smoothness step utilizing the images and the poses generated by SVO.³³ Similarly, a real-time dense mapping was obtained in the study by Weiss et al.³⁴ using a single camera mounted on a MAV employing a visual SLAM algorithm. The proposed approach generates a 3D mesh from the extracted point cloud, which is then textured and used during obstacle avoidance and exploration.

Other 3D mapping frameworks are presented in the studies by Hornung et al.³⁵ (OctoMap) and Khan et al.³⁶ (RMAP). The OctoMap approach presented in the study by Hornung et al.³⁵ is based on octree data structure in which volumetric 3D environment models including free and unknown areas are generated using probabilistic occupancy estimation. The RMAP approach presented in the study by Khan et al.³⁶ is based on Rtrees data structure composed of rectangular cuboids (RCs) hierarchy. In this approach, an occupancy grid and axis aligned RC approximation are used to provide a 3D probabilistic representation of the environment with multi resolution capability. The approach in the study by Khan et al.³⁶ demonstrated better memory efficiency than³⁵ due to the fact that RMAP preforms implicit free space modelling. Another more space efficient data structure is represented in the study by Morris et al.³⁷ based on a multi volume occupancy grid (MVOG). MVOG groups the observations of a 2D laser scanner as vertical volumes to represent free and occupied spaces of 3D rectilinear indoor spaces.

Furthermore, octree-based maps were generated in the studies by Omari et al.,³⁸ Schadler et al.³⁹ and Fossel et al.⁴⁰ using and extending the OctoMap 3D mapping framework presented previously in the study by Hornung et al.³⁵ Omari et al.³⁸ proposed a navigation system for a UAV platform equipped with a VI sensor that estimates the UAV pose and generates real-time environment 3D maps for industrial inspection. The obtained depth images are converted into a 3D point cloud stored in an octree-based data structure that is updated whenever a new depth image is obtained by raytracing the new point cloud in the octomap. Schadler et al.³⁹ also proposed an octree-based 3D mapping method in addition to a real time pose tracking method utilizing two rotating laser scanners. The octree-based map representing the environment is a multi-resolution surfel (surface element) map in which the surfels store both shape parameters and reflectance distribution of the surface. The two main steps in registering the local multi resolution surfel maps generated by the 3D laser scans are surface association and pose estimation. An OctoSLAM algorithm was presented in the study by Fossel et al.⁴⁰ where an extended version of the octree representation was combined with an online occupancy grid map learning algorithm (scan registration) called Hector SLAM. Different data perceived by various sensors mounted on a UAV platform were fused by the OctoSLAM algorithm to generate the map including 2D laser range finder scans and the altitude and attitude sensor data. In the study by Saarinen et al.,⁴¹ a novel 3D spatial online mapping approach was proposed and it is represented as the normal distributions transforms occupancy grid map. It showed a high performance in the number of updates and multi resolution support in comparison to the Octomap approach. The proposed approach provides exact recursive updates and supports multi resolution maps and mapping dynamic areas. Moreover, a pipeline for 3D mapping using a laser range finder mounted on a MAV was presented in the study by Holz and Behnke,⁴² where the pipeline consists of two algorithmic components: a pairwise registration algorithm and a global alignment algorithm.

A different approach for 3D mapping was presented in the study by Sehestedt et al.⁴³ utilizing a depth sensor mounted on a grit-blasting assistive device consisting of a robotic manipulator and a Xion RGBD camera. The mapping was preformed by starting with a workspace fundamental element, such as a roof point cloud, to identify other regions and narrowed down until the map matches a template, thus enhancing the geometrical accuracy of the map. The accuracy of 3D maps was the focus of,⁴⁴ where a fusion technique called invariant extended Kalman filter (IEKF) was used to combine RGBD images with motion sensor data to improve localization in order to provide accurate 3D maps. ICP was used for analysing localization error and performing localization using depth images.

3D structures reconstruction

In inspection applications, a 3D model of the structure is usually required. The previously mentioned ship hull inspection performed in the study by Hover et al.¹⁰ reconstructed the vessels stern in order to detect mines. The reconstruction was performed using the data frames coming from a sonar range sensor, filtered and assembled into a point cloud. The point cloud is then subsampled using Poisson disk sampling and used to estimate the normals and determine the orientation of the point cloud. Maurer et al.⁴⁵ proposed an image-based 3D reconstruction pipeline that fuses images captured by a MAV with geospatial information in order to create georeferenced semi dense 3D models. The models created are considered an approximation of a digital surface model (DSM). Haala and Kada⁴⁶ focused on describing the use of elevation data originated from Light Detection and Ranging (LiDAR) or image matching to preform building roof reconstruction, assuming footprints were extracted before using the data. The described approach in the study by Haala and Kada⁴⁶ preformed reconstruction with parametric shapes, segmentation and DSM simplification.

A hybrid novel image-based modelling with a surface parametrization system was described in the study by Nguyen et al.⁴⁷ This method generates 3D models using a collection of unconstrained images employing two main approaches: structure from motion (SfM) and bundle adjustments. The stages of the reconstruction according to the literature⁴⁷ include camera parameter estimation using bundle adjustments, scene geometry refinement, surface reconstruction using Poisson surface reconstruction algorithm and finally texture reconstruction using surface parametrization. Remondino et al.⁴⁸ discussed 3D reconstruction using camera-based images taken during a UAV flight path planned for data acquisition. The camera calibration and image triangulation were performed using bundle adjustments and automatic arial triangulation techniques. The surface reconstruction was performed using automated dense image matching techniques or interactive methods. Different reconstruction projects using Pix4D, a tool that utilizes bundle adjustments approach, were able to reconstruct complex structures using UAV platforms such as mapping Chillon Castle and modelling Matterhorn Mountain in Switzerland.^49
–51 In addition to this, a live dense 3D reconstruction was presented in the study by Wendel et al.,⁵² where a proposed distributed reconstruction pipeline was used exploiting visual SLAM and depth map fusion methods.

Additional examples of 3D structure reconstruction using depth data perceived by RGBD sensors are presented in the studies by Sehestedt et al.,⁴⁴, Silva et al.⁵³ and Dong et al.⁵⁴ Silva et al.⁵³ proposed an improvement to an existing reconstruction pipeline using noisy RGBD images of an object to provide high-quality real-time reconstructions. This pipeline includes an improvement on the acquisition stage by creating a visual feedback represented by real-time 3D model update using the acquired images fused by KinectFusion implementation. The other improvements include applying a noise reduction technique that uses an edge preserving filter to improve the quality of images and performing offline reconstruction using the resolved data textured using digital camera images. In the study by Dong et al.,⁵⁴ a visual odometry-based reconstruction method was proposed for generating consistent indoor spaces reconstructions. The proposed method combines the visual odometry data with high-quality RGBD data using KinectFusion.

Discussion

Inspecting structures usually involves navigating through an efficient route to explore the structure of interest, mapping or 3D reconstructing the structure utilizing the information gathered through the viewpoints encapsulated in the route, and analysing the model for anomalies and defects according to the application parameters. Two approaches could be followed based on the analysed literature, and these are summarized in Figure 4.

Figure 4.

Literature analysis diagram.

The first approach involves using a priori model to generate a route offline and then execute the route for data gathering to be used in model reconstruction. The second approach involves performing an online route generation, data gathering and model reconstruction all together. In both approaches, a set of viewpoints will be generated either based on a model or an initial model view. Full model coverage and high resolution scans should be guaranteed in order to reconstruct an accurate model for inspection purposes. In both approaches, the reconstructed model is assessed and the coverage percentage is quantified based on the used coverage exploration method. The viewpoints generation and path planning components are critical for the inspection process, since different constraints could affect the generation of viewpoints and coverage paths. These constraints include sensor limitations, localization errors, scan footprint and the standoff distance from the model. Most of the work in the literature performed the path generation by addressing some of these constraints, which affected both the efficiency of the planning algorithm and the resolution of the collected scans.

The quality of the scans should be high enough to facilitate the inspection in a particular application. In the studies by Valente et al.,⁶ Englot and Hover⁷ and Bircher et al.,⁸ a constant resolution was maintained by executing a route at a fixed distance, without focusing on the quality of the scans. In the study by Cheng et al.,²⁰ a high resolution reconstruction is maintained by simplifying the models of the buildings and utilizing the sensor footprint area, sensor uniform angular resolution and sensor orientation, in order to reconstruct these buildings. The resolution in the study by Cheng et al.²⁰ is constrained also by the radius of the circular trajectory that was bounded in the experiment by a safety distance of 80 m and a sensor capture area less than 8777.14 pixels. This simplification is not useful while inspecting complex structures, since it could remove critical features that are important for finding anomalies, unlike urban features reconstruction.

Additionally, Galceran et al.⁵⁵ performed redundant fixed distance coverages of the same area in order to maintain high resolution. The redundant coverages increase the computational cost and affect the efficiency of the process. Similarly, in the literature,²¹ a fine modelling method was proposed to enhance the deficiencies of a model by improving the resolution of the computed view plan. The fine modelling method starts with decimating or segmenting a rough model of the structure, then generating the view points and the view plan and finally executing the plan. After executing the plan, the collected data is evaluated according to the specific scanning objectives, then the low level scanning areas are identified and upgraded with additional targeted scans. For object reconstruction, this method was applied once but in inspection tasks, it was repeated multiple times, thus affecting the computational cost of the process.

CPP completeness is also considered a critical requirement, specially while inspecting complex structures. The complexity of the structure will affect the complexity of the planning procedure, the computational cost, the coverage completeness and the coverage convergence speed. The coverage path of such complex structures should be efficient enough to cover all the generated viewpoints in a short time consuming less resources. The average quadcopter fly time is limited to around 20 min and this should be taken into consideration when preforming real coverage experimentations using UAVs.⁵⁶ The method presented in the study Scott²¹ took 1 h to reconstruct a complex structure while it took from 3.6 min to 28.1 min to reconstruct different shapes in simulation. In the studies by Englot and Hover⁷ and Hover et al.,¹⁰ the coverage path distance was reduced using an improvement of RRT* method. Generating the initial path takes around 20 min, while the entire procedure of generating the initial path and preforming the improvements on the path takes around 2 h. The work presented in the study by Papadopoulos et al.¹⁵ proved that the RITA algorithm converges to the optimal path, with completeness performance equivalent to that of RRG. In this method, the convergence gets closer to the optimal path when the algorithm is repeated for around 1 h. From these references, it is noticeable that enhancing the path comes at the expense of computational cost and experimental duration. This is particularly evident when online planning and execution is performed, while performing offline planning will not affect the experiment duration.

In addition to this, the work performed in the study by Dornhege et al.²⁴ detailed the duration of viewpoints generation and CPP for different location sizes such as a lab, arena and campus. It presented the cost and the timing for these locations using different coverage search algorithms showing that NBV methods take much longer time than using other model-based algorithms. The work presented in the study by Janousek and Faigl²⁵ showed that increasing the number of epochs shortens the resulting inspection path using self-organizing maps. Moreover, structure segmentation was performed in the studies by Atkar et al.,¹⁸ Cheng et al.²⁰ and Scott²¹ to generate coverage plans for each segment, but this will take a long time for complex structures since they contain a lot of critical and small parts.

Another important aspect affecting the duration of path execution is the sensing technique, whether it is performed continuously along the path or discretely at each viewpoint. Most of the analysed literature used discrete sensing, since it allows the robot to stabilize before scanning and avoid missing observations, but following this approach increases the inspection duration as described earlier.

The second important aspect in robotic inspection applications is the 3D reconstruction process, during which the data gathered are combined to create an accurate 3D model of the object or structure of interest. 3D reconstruction could be handled offline, after the coverage path execution and data gathering processes, or online where CPP and data gathering are being performed consequently as described in the diagram shown in Figure 4.

3D reconstruction and mapping algorithms deal with point clouds, 2D images data and other forms of data that are considered complex data, which requires an efficient memory representation to encapsulate the generated model. The literature presented in the studies by Hornung et al.,³⁵ Omari et al.³⁸ and Fossel et al.⁴⁰ used an octree data structure for representing the 3D environment maps. One of the advantages of octree is that the initialization of the map volumes is delayed until the map integration process, unlike fixed grid structures. Another data structure representation illustrated in the work of Khan et al.³⁶ is the Rtree that consists of RCs instead of voxels. The approach described in the work of Khan et al.³⁶ generates variable-sized cuboids that reduce the memory complexity and make the memory efficient for axis aligned surfaces. Another efficient data structure discussed earlier is the MVOG presented in the study by Morris et al.³⁷ for representing rectilinear indoor environments.

Another important part of the 3D reconstruction and mapping procedure is the camera localization, usually preformed by different methods in the surveyed literature. In some of the literature,^34,52 the localization is preformed as part of a visual SLAM algorithm, while searching for corresponding features in the collected scenes. In the literarure,^45,47 SfM was used to determine the camera position and orientation. Another method for localization and motion estimation is the SVO proposed in the study by Faessler et al.³³ for MAV localization in environments containing highly repetitive texture.

The components of the CPP process used in the surveyed work in this article are summarized in Tables 1 and 2. Table 1 summarizes the surveyed research on the model-based approaches, while Table 2 summarizes the surveyed research on the non-model-based approaches. In these tables, each article is summarized in a row, where the columns list the viewpoints generation method, the coverage path generation method, the evaluations of the coverage method and the application performed. Different evaluations are performed in terms of path planning completeness, coverage completeness and convergence and the quality of the scans. The 3D reconstruction work surveyed is summarized in Table 3. In this tables, each article is presented in a row, where the columns list the sensors used, the algorithms developed and additional properties described in that article.

Table 1.

Summary of model-based coverage path planning approach references.

Reference model is available
Reference	Viewpoints generation/sampling method	Coverage path generation	Evaluation (convergence, completeness and resolution)	Application
⁶	- Grid based (cellular decomposition) - Center of each cell is a waypoint	- Tree-based search - Heuristic-based search - Pedestrian pocket algorithm	- Maintained constant resolution - Cells dimension constrained by sensor FOV	- Inspection, monitoring, perimeter surveillance, or image sampling
⁷	- Triangular mesh (using ranges to triangles) - Set cover method	CSP algorithm based: - Watchman route - Redundant roadmap	- Short coverage distance - Probabilistic completeness	- Ship hull Inspection (non-planar part; related to Hover et al.¹⁰ and Englot and Hover⁹)
⁸	- Triangular mesh (using visibility of triangles) - Computational geometry method (AGP)	- TSP algorithm (LKH solver)	- Viewpoints position and heading optimization - Various mesh resolution impact - Computation time - Viewpoints number and path distance	- Structural inspection (inspection paths for 3D reconstruction)
¹⁰	- Mesh division into planar (simple) and non planar part (complex) - Contour following (planar part) and sampling based algorithm (complex part)	- Feature-relative navigation and pose graph SLAM (back and forth sweep paths for planar part) - CSP algorithm as⁷ for the non-planar part	- Low cost configurations replacing high-cost ones (using improvement of RRT*) - Tour length reduction	- Ship hull inspection (planar and non-planar parts; related to Englot and Hover^7,9)
¹⁵	- Simplified model (polyhedral structures and obstacles) - Randomized Kino dynamics sampling-based motion planner	- RITA algorithm	- Probabilistic completeness - Convergence to optimal trajectory - Continuous and discrete sensing (discrete is used)	- Structural Inspection (trajectory generation and 3D reconstruction)
²¹	- Rough model (decimated triangular mesh) - A set theory method is used for viewpoints generation	- TSP algorithm or view plans merging if model segmentation is used	- Scanning precession density and coverage - View plan quality and efficiency - Resolution and pose error prevention and correction	- Object inspection/3D reconstruction (using closed loop simulation of the environment)
³⁰	- Grid-based decomposition - Sensed grids store the time of coverage - Candidate orientations generated using random sampling	- The area is segmented based on the candidate orientations - Coverage planning is based on the sensed area and the large average waiting time	- PARCov efficiency and scalability - Coverage completeness - High-sensor data quality - Reduced detection risk between the UAVs	- Surveillance of sensitive areas (simulation)
¹⁹	- A start curve with lowest geodesic curvature is selected using the model - Offsetting procedure is done on both sideways of the start curve	- Coverage path generated by offsetting passes on both start curve sideways - Iterative plane slice intersection with the surface generates a group of 1D paths	- Speed optimization along the paths - The spacing between the 1D paths is optimized to be wide reducing the cycle time	- Coverage for auto body painting (focus on paint deposition uniformity)
¹⁸	- Model hierarchal segmentation (surface topological and path geometry) into simple cells of same curvature	- Individual optimal paint deposition coverage paths in each cell are generated using¹⁹ approach	- Similar evaluations as¹⁹	- Complex automotive surfaces painting
²⁰	- Simplified models of buildings (cylinders and hemispheres) - Sensor model is considered (sensor footprint and distance)	- For hemispherical model, horizontal circles at different altitudes with a shared center and larger radius than the model are used - For cylindrical model, circular flights (sides) and hemispherical flights are used (cap)	- Plan is generated to obtain maximum resolution always (the resolution of the camera was 307200 pixels and FOV was 35°) - The sensor points to the center axis of the cylinder for cylindrical flights and to the model center for hemispherical flight	- 3D coverage for urban environments with 2.5D features
⁴³	- Prior knowledge (digital models or templates) - Number of viewpoints is restricted	- The sensor data (point cloud) are segmented into ROI then narrowed down - These regions are matched with the templates to map unobserved regions	- Convergence, in panel detection and ROI size - Restricted time (restricted number of viewpoints) - Accuracy and robustness (in positioning error presence)	- 3D mapping for steel bridge maintenance
³⁹	- Multi-resolution surfel maps generated using laser scans are associated and pose optimized - A* used for planning	- Drivable cells found are used in planning - Euclidean distance is the heuristic - Waypoints are derived from the plan and local plan is updated based on real time depth data	- Distances between scans of laser tracking and SLAM were compared	- 3D mapping and navigation for search and rescue
²⁵	- Triangular mesh - The free space is divided into tetrahedrons - Viewpoints are generated simultaneously with the path optimization	- Motion PRM - Coverage space construction (set of tetrahedral) - Determining inspection path using self-organizing maps (WRP)	- Feasible and cost effective path - Computational complexity in terms of tetrahedral mesh covering space algorithms and number of triangles and timing	- Inspection coverage planning for a set of objects in a city-like environment
⁵⁵	- Prior bathymetric map of the target structure is used - Contour following is used at an offset distance and uniformly spaced depths	- The offline coverage path consist of contours where the data is collected - Replanning using stochastic trajectory optimization is done to cope positioning error	- Nominal coverage paths - 3D objects reconstruction	- Inspection of complex structures on the ocean floor (such as seamounts or coral reefs)
⁹	- Hierarchal face clustering is used to segment a model triangular mesh to isolate planar areas - Individual configurations are computed solving set cover problem (AGP)	Two phase path planning strategy (planar and non-planar): - Hybrid sampling-sweep-based planning for the full coverage path consisting of discrete waypoints - The occluded areas are covered using randomized paths	- Low-cost configurations - Tour length reduction - Probabilistic complete	- Ship hull inspection (ship motors; related to Englot and Hover⁷ and Hover et al.¹⁰)
²³	- Triangular mesh (discrete structure models) - Dense graph of feasible structure configurations (nodes) and paths are constructed	- Iterative edge computation is done using the nodes to fully cover the area - The unattached closed walks in the graph are merged to form one continuous tour	- Coverage time, inspection path length - Structure nodes and triangles - Graph nodes and edges	- Ship hull inspection of complex structures underneath a ship hull
²⁴	- A prior known 3D environment - Set cover problem is used to generate the viewpoints	- TSP (TFD/LKH solvers) generates a sequenced viewpoints - Variants of searching problems and greedy cost provided solutions but set cover/TSP performed the best	- Computation time and the costs of the paths and execution time were compared for the variants of the algorithm	- Covering complex 3D environments for searching applications

AGP: art gallery problem; TSP: travelling salesman problem; LKH: Lin-Kirighan heuristic; PARCov: planner for autonomous risk-sensitive coverage; UAV: unmanned arial vehicle; FOV: field of view; ROI: regions of interest; SLAM: simultaneous localization and mapping; PRM: probabilistic road map; NBV: next best view; SfM: structure from motion; CSP: Coverage Sampling Problem; WRP: Watchman Route Problem.

Table 2.

Summary of non-model based coverage path planning approach references.

No reference model available
Reference	Viewpoints generation/sampling method	Coverage path generation	Evaluation (convergence, completeness and resolution)	Application
²⁹	- Initial view based on the sensor limitations	- The nearest poses to the current pose are chosen using a specific step size and checking their validity - The valid poses are selected based on the information gain and effort	- Evaluated viewpoints number, information gain and computational time reduction - Another NBV (AXBAM NBV) is used to check the area exploration completeness	- Exploration of complex 3D environments
³¹	- 3D Workspace discretization and yaw non uniform discretization - A set of candidate goals on the frontiers	- Pre-computations of the swath and view frustum Two planning problem: - Choosing next best goal based on maximizing utility function (shortest path and information gain) - Path planning to the goal maximizing coverage gain (number of voxel faces)	- Maximize the size of the reconstructed model - Maximize the coverage completeness	- Automated 3D reconstruction of an environment (simulation)
²⁸	- An initial position and view is available - NBV follows four steps: positioning, scanning, registering and NBV planning	- Two evaluations for the generated views based on a utility function: - Evaluating (information gain (80%) and overlapping scans (20%) - Evaluating positioning error	- Reconstruction efficiency using two evaluations - Robustness against positioning error - The reduction of views	- Object 3D reconstruction (simulation)
²⁶	- An initial position and view is available - The approximated object dimensions are known - NBV follows four steps: positioning, scanning, registering and NBV	Two evaluations for the generated views based on both raytracing resolution and a utility function: - Evaluating Information gain, overlapping scans, navigation distance, and scans’ quality. - Evaluating positioning error	- Scan’s quality enhancement - Accelerated NBV and reduced number of views to be evaluated at each iteration (multi resolution strategy)	- Object 3D reconstruction (simulation)
²⁷	- Initial view based on the depth sensor limitations - The object is grasped and moved based on NBV in front of the camera	- Volumetric variant of NBV	- Different grasps are generated based on an information gain threshold to provide complete model	- 3D surface model reconstruction

DSM: digital surface model; NBV: next best view; AXBAM: Autonomous exploration to Build a Map.

Table 3.

Summary of the 3D reconstruction approaches references.

Reference	Sensors	Algorithms	Properties
⁴⁵	- Panasonic Lumix LX3 digital camera - GPS and IMU	- SfM to determine the camera orientation - Bundle adjustments (refine reconstructed features points) - Alignment of a semi dense reconstruction with a DSM	- Patch-based semi-dense approach to densify the sparse model
³³	- Monocular camera – IMU	- The depth at new 2D feature positions is found using FAST corners (depth filter) - The depth filter is updated in a recursive Bayesian fashion	- Depth filter is described by a parametric model - Depth map smoothing step using Huber norm
³⁴	- Monocular camera (uEye camera with WVGA resolution and global shutter)	- Camera position is determined searching for corresponding features (FAST corners) - Adaptation of visual SLAM algorithm of Klein and Murray (use a more conservative key frame selecting heuristic) - Delaunay triangulation is used to reveal the real topology of the scene to build 3D-textured mesh map	- SLAM algorithm is robust against partial camera occlusions - 3D point features are projected to 2D image plane to extract the desired texture for the map - Using bundle adjustments to minimize the error between the projected map points and the corresponding observations
³⁵	- Stereo camera - Laser (deals with point cloud)	- Volumetric 3D environment models including free and unknown areas are generated by using probabilistic occupancy estimation	- Octrees data structure is used - Bounded per-volume confidence is used to substantially reduce memory usage
³⁶	- Laser (deals with point cloud)	- An occupancy grid and axis-aligned RC approximation were used to provide a 3D probabilistic representation of the environment with multi-resolution capability	- SLAM algorithm is robust against partial camera occlusions - 3D point features are projected to 2D image plane to extract the desired texture for the map - Using bundle adjustments to minimize the error between the projected map points and the corresponding observations
³⁷	- Altimet–r -IMU - Hokuyo laser range finder - Swiss Ranger 4000 depth camera	- 3D MVOG mapping similar to 2D occupancy grid approach - The steps of updating the MVOG: rasterization, insert and creating volumes and apply constraints - Scan matching approach with depth images	- MVOG data structure groups the observations of a 2D laser scanner as vertical volumes to represent free and occupied spaces of 3D rectilinear indoor spaces
⁴⁶	- Airborne images - Laser scans	- Reconstruction based on segmentation - Footprint decomposition and parametric shapes - Reconstruction by DSM simplification - Building facades	- Terrestrial data collection for providing detailed information on building facades while modeling cities
⁴⁷	- Digital camera	- SfM and bundle adjustment for defining camera parameters and a 3D scene geometry - Hybrid multi-view image-based modeling approach coupled with a surface parameterization technique for 3D-textured mapping	- Point cloud density is enhanced exploiting silhouette information of the scene - Segmentation and charting approach are used to create high quality texture - Using graph cut technique to fuse the projected best fitted images on each surface segment over each chart to create textured map
⁴⁸	- Digital camera	- Automated dense image matching techniques or interactive methods for features and vector information extraction	- Automated methods generate DSM - Interactive approaches deliver sparse point clouds that need structuring
⁵²	- Single industrial camera (IDS UI-1240SE; a maximum resolution of 1280 × 1024 pixels, global shutter and an 8 mm lens)	- Visual SLAM of Klein and Murray with variations on the distributed operation is used - New points are add by triangulation with neighboring views - Quasi-dense depth maps are computed based on the collected key frames using multi-view version of the plane sweep algorithm	- Live dense volumetric reconstructions - Bundle adjustment is used for refinement - Depth map fusion is based on truncated signed distance function
³⁸	- VI sensor (The sensor dimensions are 144 × 40 × 57 mm³ with a weight of 130 g and a power consumption of less than 7 W.)	- OctoMap mapping framework is used - The depth images are estimated using the area correlation-based block-matching algorithm	- Integrating GPS measurements makes the point cloud geo-referenced
³⁹	- 2D laser scanner	- Surfels are associated between maps from the finest resolution to coarser resolutions until associations have been determined for the entire map - 3D scans are represented by local multi-resolution surfel maps - 3D scans are efficiently registered and aligned in a global map using graph optimization	- Multi-resolution surfel representations allow for compact maps and efficient registration of local maps
⁴⁰	- 2D laser range finder - Altitude sensor – IMU	- A planar based SLAM algorithm that operates on a 3D representation of environments - Scan registration algorithm is derived from Hector SLAM	- 3D environment are represented by an octree based map
⁴²	- A developed lightweight 3D laser scanner (rotating 2D laser range finder)	3D mapping pipeline: - Scans pairwise registration that include topological information from approximate surface reconstructions - Global alignment of scans using graph-based approach	- 3D laser sensor provides omnidirectional sensing at high frame rates (2 Hz)
⁴³	- Depth camera (Xtion camera)	- Mapping procedure is done by segmenting available digital models to regions and applying template matching using ICP	- Digital models of particular structural elements are used - RANSAC is used to remove remaining outliers
⁵³	- Depth sensor (Kinect) - Digital camera	3D reconstruction pipeline: - An implementation of KinectFusion used to create a real-time updating 3D model used only for visual feedback - A spatio-temporal resolution method to improve the depth images - Mesh integration using VRIP and Consensus Surfaces and the IVIA	- Texture is applied using digital camera images - Pre-aligning the resolved data using SURF followed by two phase of ICP offers maximum precession
⁴⁴	- Kinect sensor - Three-axis gyroscope (IMU Crossbow VG600)	- Fusion of depth images with motion data is done using of invariant EKF and is directly based on the estimated covariance of the ICP	- The accuracy of the localization is improved
⁵⁴	- RGBD sensor	- A 6D RGBD odometry approach is followed to find the relative camera pose between consecutive RGBD frames - KinectFusion algorithm fine tunes frame to frame relative poses and fuses depth data to global implicit surface using ICP	- Camera relative pose is found be key points extraction and feature matching on the RGB and depth image planes
^49,50	- Canon 6D with Sigma fisheye 8 mm - Sony alpha7r with fisheye - DJI Phantom 2 Vision - Tachymeter - GoPro Hero3	- Pix4DMapper (based on bundle adjustments) - Individual reconstructions were done for each sensor then a global reconstruction was obtained combining the individual ones	- Geo-referenced and very accurate model of complex architecture are obtained using consumer grade cameras

DSM: digital surface model; RC: rectangular cuboid; MVOG: multi volume occupancy grid; ICP: iterative closest point; VRIP: volumetric range image processing; IVIA: IMAGO volumetric integration algorithm; SLAM: simultaneous localization and mapping; SfM: structure from motion; EKF: extended Kalman filter; RANSAC: Radom Sample Consensus.

Conclusion

In this article, we have surveyed the literature related to the inspection of structures using robotic systems. The major components of inspection are identified and discussed. The CPP problem has been addressed using different approaches in the literature based on a reference model of the object. The model-based CPP research work reviewed in this article dominates the non model-based research work performed in the application of inspection. The model-based approach utilizes the existence of the priori static knowledge of the structure of interest in order to generate a coverage path that passes through an admissible set of viewpoints and provide maximum coverage for reconstruction and inspection. The non-model based approach evaluates next best candidate views to provide the maximum coverage based on the coverage and information gain using different utility functions. The model-based approach performs the CPP offline, while the non-model based approach performs a cycle of online iterative steps including candidate views generation, evaluation and path planning, scanning and reconstruction. The reconstruction process is performed using different approaches that range from simple structure reconstruction to complex environments mapping and reconstruction. In general, the two main methods for performing inspection using robotics involve finding an optimized short path passing through a set of viewpoints that provide full coverage and high quality scans, and reconstructing an accurate model utilizing the collected scans in order to detect or trace anomalies and faults in the constructed model.

In real-life inspection applications, accuracy and coverage completeness are considered two major concerns. Although several research work preformed CPP and 3D reconstruction in different inspection applications, little attention has been given to incorporating sensor accuracy and coverage completion in CPP methods. In addition to this, most of the reviewed literature either preformed coverage on simple geometrical structures or performed model simplification before applying CPP using the structure model, which in both cases affect the reconstructed model accuracy and coverage completeness. Therefore, incorporating sensors accuracy during coverage planning, and extensively evaluating coverage completeness are still considered open research areas in this field that require further investigation.

Footnotes

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) received no financial support for the research, authorship, and/or publication of this article.

References

Nokia puts “telco drones” to work inspecting cell towers. http://www.zdnet.com/article/nokia-puts-telco-drones-to-work-inspecting-cell-towers/ (accessed 13 Sepember 2015).

Smith

. Utilities turn to drones to inspect power lines and pipelines. http://www.wsj.com/articles/utilities-turn-to-drones-to-inspect-power-lines-and-pipelines-1430881491 (accessed 5 September 2015).

Mercer

Phil

. Grit-blasting robots clean Sydney Harbour Bridge. BBC News, http://www.bbc.com/news/world-asia-23352958 (accessed 13 september 2015).

Boeing uses drones for inspection. http://www.rocketmine.com/boeing-uses-drones-for-inspection/ (accessed 23 August 2015).

Galceran

Carreras

. A survey on coverage path planning for robotics. Robot Autom Syst 2013; 61(12): 1258–1276.

Valente

Barrientos

Cerro

. Coverage path planning to survey large outdoor areas with aerial robots: a comprehensive analysis. Introduction to Modern Robotics 2011, http://iconceptpress.com/download/paper/101108074033.pdf (accessed 20 July 2015).

Englot

Hover

. Sampling-based coverage path planning for inspection of complex structures. In: Icaps 2012, pp. 29–37. Available from: http://www.aaai.org/ocs/index.php/icaps/icaps12/paper/download/4728/4711 (accessed 1 August 2015).

Bircher

Alexis

Burri

. Structural inspection path planning via iterative viewpoint resampling with application to aerial robotics. In: IEEE international conference on robotics and automation (ICRA), Seattle, WA, 2015, pp. 6423–6430. DOI: 10.1109/ICRA.2015.7140101.

Englot

Hover

. Sampling-based sweep planning to exploit local planarity in the inspection of complex 3D structures. In: IEEE/RSJ international conference on intelligent robots and systems, Vilamoura, 2012, pp. 4456–4463. DOI: 10.1109/IROS.2012.6386126.

10.

Hover

Eustice

Kim

. Advanced perception, navigation and planning for autonomous in-water ship hull inspection. Int J Robot Res 2012; 31(12): 1445–1464.

11.

Helsgaun

. Effective implementation of the Lin-Kernighan traveling salesman heuristic. Eur J Oper Res 2000; 126(1): 106–130.

12.

Kavraki

Svestka

. Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Trans Robot Autom 1996; 12(4): 566–580.

13.

LaValle

Kuffner

. Randomized kinodynamic planning. In: Proceedings 1999 IEEE international conference on, Detroit, MI, 1999, vol. 1, pp. 473–479. Doi: 10.1109/ROBOT.1999.770022.

14.

Karaman

Frazzoli

. Sampling-based algorithms for optimal motion planning. Int J Robot Res 2011; 30(7): 846–894.

15.

Papadopoulos

Kurniawati

Patrikalakis

. Asymptotically optimal inspection planning using systems with differential constraints. In: IEEE international conference on robotics and automation (ICRA), Karlsruhe, 2013, pp. 4126–4133. Doi: 10.1109/ICRA.2013.6631159.

16.

Karaman

Frazzoli

. Sampling-based algorithms for optimal motion planning with deterministic μ-calculus specifications. In: 2012 american control conference (ACC), Montreal, QC, 2012, pp. 735–742. DOI: 10.1109/ACC.2012.6315419.

17.

Karaman

Frazzoli

. Incremental sampling-based algorithms for optimal motion planning. Proc. Robotics: Science and Systems (RSS), 2010.

18.

Atkar

Conner

Greenfield

. Hierarchical segmentation of surfaces embedded in R3 for auto-body painting. In: Proceedings of the 2005 IEEE international conference on robotics and automation, 2005, pp. 572–577. DOI: 10.1109/ROBOT.2005.1570179.

19.

Atkar

Conner

Greenfield

. Uniform coverage of simple surfaces embedded in R 3 for auto-body painting. Workshop on algorithmic foundations of robotics, 2004, pp. 383–398.

20.

Cheng

Keller

Kumar

. Time-optimal UAV trajectory planning for 3D urban structure coverage. In: 2008 IEEE/RSJ international conference on intelligent robots and systems, Nice, 2008, pp. 2750–2757. DOI: 10.1109/IROS.2008.4650988.

21.

Scott

. Model-based view planning. Mach Vis Appl 2009; 20(1): 47–69.

22.

Scott

Roth

Rivest

. View planning for automated three-dimensional object reconstruction and inspection. ACM Comput Survey 2003; 35(1): 64–96.

23.

Englot

Hover

. Inspection planning for sensor coverage of 3D marine structures. In: Intelligent robots and systems (IROS), 2010 IEEE/RSJ international conference on, Taipei, 2010, pp. 4412–4417. DOI: 10.1109/IROS.2010.5648908.

24.

Dornhege

Kleiner

Kolling

. Coverage search in 3D. In: 2013 IEEE international symposium on safety, security, and rescue robotics (SSRR), Linkoping, 2013, pp. 1–8. DOI: 10.1109/SSRR.2013.6719340.

25.

Janoušek

Faigl

. Speeding up coverage queries in 3D multi-goal path planning. In: Robotics and automation (ICRA), 2013 IEEE international conference on, Karlsruhe, 2013, pp. 5082–5087. DOI: 10.1109/ICRA.2013.6631303.

26.

Vasquez-Gomez

Sucar

Murrieta-Cid

. Volumetric next best view planning for 3D object reconstruction with positioning error. Int J Adv Robot Syst 2014; 11: 159. http://www.intechopen.com/journals/international_journal_of_advanced_robotic_systems/volumetric-next-best-view-planning-for-3d-object-reconstruction-with-positioning-error (accessed 8 august 2015).

27.

Krainin

Curless

Fox

. Autonomous generation of complete 3D object models using next best view manipulation planning. In: Robotics and automation (ICRA), 2011 IEEE international conference on, Shanghai, 2011, pp. 5031–5037. DOI: 10.1109/ICRA.2011.5980429.

28.

Vásquez

Sucar

. Next-best-view planning for 3D object reconstruction under positioning error. In: Batyrshin

Sidorov

(eds) Advances in Artificial Intelligence. Berlin Heidelberg: Springer, 2011, pp. 429–442.

29.

Quin

Paul

Alempijevic

. Efficient neighbourhood-based information gain approach for exploration of complex 3D environments. In: Robotics and automation (ICRA), 2013 IEEE international conference on, Karlsruhe, 2013, pp. 1343–1348. DOI: 10.1109/ICRA.2013.6630745.

30.

Wallar

Plaku

Sofge

. A Planner for autonomous risk-sensitive coverage (PARCOV) by a team of unmanned aerial vehicles. In: Swarm intelligence (SIS), 2014 IEEE symposium on, Orlando, FL, 2014, pp. 1–7. DOI: 10.1109/SIS.2014.7011807.

31.

Heng

Gotovos

Krause

. Efficient visual exploration and coverage with a micro aerial vehicle in unknown environments. In: 2015 IEEE international conference on robotics and automation (ICRA), Seattle, WA, 2015, pp. 1071–1078. DOI: 10.1109/ICRA.2015.7139309.

32.

Lee

. A new hybrid terrain coverage method for underwater robotic exploration. J Marine Sci Technol (Japan) 2014; 19(1): 75–89.

33.

Faessler

Fontana

Forster

. Autonomous, vision-based flight and live dense 3D mapping with a quadrotor micro aerial vehicle. J Field Robot 2014; 7(PART 1): 1–20.

34.

Weiss

Achtelik

Kneip

. Intuitive 3D maps for MAV terrain exploration and obstacle avoidance. J Intell Robot Syst Theor Appl 2011; 61(1–4): 473–493.

35.

Hornung

Wurm

Bennewitz

. OctoMap: an efficient probabilistic 3D mapping framework based on octrees. Auton Robot 2013; 34(3): 189–206.

36.

Khan

Dometios

Verginis

. RMAP: a rectangular cuboid approximation framework for 3D environment mapping. Auton Robot 2014; 37(3): 261–277.

37.

Morris

Dryanovski

Xiao

. 3D indoor mapping for micro-uavs using hybrid range finders and multi-volume occupancy grids. In: RSS 2010 workshop on RGBD advanced reasoning with depth cameras, Zaragoza, Spain. 2010, pp. 743–747.

38.

Omari

Gohl

Burri

. Industrial inspection using aerial robots. In: International conference on applied robotics for the power industry (CARPI), Vol. 1, 2014.

39.

Schadler

Stückler

Behnke

. Rough terrain 3D mapping and navigation using a continuously rotating 2D laser scanner. KI – Künstliche Intelligenz 2014; 28(2): 93–99.

40.

Fossel

Hennes

Claes

. OctoSLAM: a 3D mapping approach to situational awareness of unmanned aerial vehicles. In: Unmanned aircraft systems (ICUAS), 2013 International conference on, Atlanta, GA, 2013, pp. 179–188. DOI: 10.1109/ICUAS.2013.6564688.

41.

Saarinen

Stoyanov

Andreasson

. 3D normal distributions transform occupancy maps: an efficient representation for mapping in dynamic environments. Int J Robot Res 2013; 0(0): 1–18.

42.

Holz

Behnke

. Mapping with micro aerial vehicles by registration of sparse 3D laser scans. In: Proc. of the int. conf. on intelligent autonomous systems, IAS, Padova, Italy, 2014.

43.

Sehestedt

Paul

Rushton-smith

. Prior-knowledge assisted fast 3D map building of structured environments for steel bridge maintenance. IEEE international conference on automation science and engineering (CASE), Madison, WI, 2013, pp. 1040–1046. DOI: 10.1109/CoASE.2013.6653892.

44.

Hervier

Bonnabel

Goulette

. Accurate 3D maps from depth images and motion sensors via nonlinear Kalman filtering. In: 2012 IEEE/RSJ international conference on intelligent robots and systems, Vilamoura, 2012, pp. 5291–5297. DOI: 10.1109/IROS.2012.6385597.

45.

Maurer

Rumpler

Wendel

. Geo-referenced 3D reconstruction: fusing public geographic data and aerial imagery. In: Robotics and automation (ICRA), 2012 IEEE international conference on, Saint Paul, MN, 2012, pp. 3557–3558. DOI: 10.1109/ICRA.2012.6225247.

46.

Haala

Kada

. An update on automatic 3D building reconstruction. ISPRS J Photogramm Remote Sens 2010; 65(6): 570–580.

47.

Nguyen

Wunsche

Delmas

. High resolution 3D content creation using unconstrained and uncalibrated cameras. In: 2013 6th international conference on human system interactions (HSI), Sopot, 2013, pp. 637–644. DOI: 10.1109/HSI.2013.6577892.

48.

Remondino

Barazzetti

Nex

. UAV photgrammetry for mapping and 3D modeling – current status and future perspectives. In: International archives of the photogrammetry, remote sensing and spatial information sciences, Zurich Switzerland, September 2011, Vol. XXXVIII, pp. 14–16.

49.

Krull

Betschart

. The chillon project: Aerial/terrestrial and indoor integration. 2014. https://support.pix4d.com/hc/en-usarticles/202557199-Scientific-WhitePaper-The-Chillon-Project-AerialTerrestrialand-Indoor-Integration (accessed 20 September 2015).

50.

Strecha

Zoller

Rutishauser

Brot

. Terrestrial 3D mapping using Fisheye and perspective sensors. http://www.pix4d.com (accessed 23 November 2015).

51.

Modelling the Matterhorn. https://pix4d.com/modelling-matterhorn/ (accessed 23 November 2015).

52.

Wendel

Maurer

Graber

. Dense reconstruction on-the-fly. In: Computer vision and pattern recognition (CVPR), 2012 IEEE conference on, Providence, RI, 2012, pp. 1450–1457. DOI: 10.1109/CVPR.2012.6247833.

53.

Silva

Gomes

Agüero

. Real-time acquisition and super-resolution techniques on 3D reconstruction. In: 2013 IEEE international conference on image processing, Melbourne, VIC, 2013, pp. 2135–2139. DOI: 10.1109/ICIP.2013.6738440.

54.

Dong

Figueroa

Saddik

. Towards consistent reconstructions of indoor spaces based on 6D RGB-D odometry and kinectfusion. In: 2014 IEEE/RSJ international conference on intelligent robots and systems, Chicago, IL, 2014, pp. 1796–1803. DOI: 10.1109/IROS.2014.6942798.

55.

Galceran

Campos

Palomeras

. Coverage path planning with realtime replanning for inspection of 3D underwater structures. In: 2014 IEEE international conference on robotics and automation (ICRA), Hong Kong, 2014, pp. 6586–6591. DOI: 10.1109/ICRA.2014.6907831.

56.

How to choose battery for Quadcopter, Tricopter and Hexacopter. http://blog.oscarliang.net/how-to-choose-battery-for-quadcopter-multicopter/ (accessed 23 July 2015).

A survey on inspecting structures using robotic systems

Abstract

Keywords

Introduction

CPP

Discrete coverage path planning

Continuous CPP

Coverage exploration and viewpoint generation

Model-based viewpoint generation

Exploratory-based viewpoint generation

Coverage completeness

Workspace 3D reconstruction

3D environment mapping

3D structures reconstruction

Discussion

Conclusion

Footnotes

Declaration of conflicting interests

Funding

References