Chinese

2020,  2 (2):   87 - 103   Published Date：2020-4-20

DOI: 10.1016/j.vrih.2020.04.003

Abstract

Background
This paper presents an intelligent path planner for lifting tasks by tower cranes in highly complex environments, such as old industrial plants that were built many decades ago and sites used as tentative storage spaces. Generally, these environments do not have workable digital models and 3D representations are impractical.
Methods
The current investigation introduces the use of cutting-edge laser scanning technology to convert real environments into virtualized versions of the construction sites or plants in the form of point clouds. The challenge is in dealing with the large point cloud datasets from the multiple scans needed to produce a complete virtualized model. The tower crane is also virtualized for the purpose of path planning. A parallelized genetic algorithm is employed to achieve intelligent path planning for the lifting task performed by tower cranes in complicated environments taking advantage of graphics processing unit technology, which has high computing performance yet low cost.
Results
Optimal lifting paths are generated in several seconds.

Content

2096-5796/©Copyright 2020 Beijing Zhongke Journal Publishing Co. Ltd., Publishing services by Elsevier B.V. on behalf of KeAi Communication Co. Ltd. This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/by/4.0/).
1 Introduction
1.1　Background
Tower crane lifting is a common operational practice in areas such as the building and petrochemical industries. Safety is a pertinent issue in such tasks, particularly when lifting heavy and large precast materials or equipment in complicated construction sites or plants. Generally, to improve productivity and prevent safety hazards, several planning practices must be done before conducting the lifting task. The planning is normally carried out manually, which is error-prone and time-consuming. To improve the lift planning process, many computer-aided planning approaches have been proposed. The development of safety monitoring and simulation systems have been presented in previous papers[1‒6], while other papers[7‒11] have explored automatic planning for lifting paths. These works have been based on digital models that were developed using Building Information Modeling (BIM), SmartPlant, or Plant Design Management System (PDMS) software. This study investigates the intelligent planning for lifting path in complicated and real environments that do not have workable digital models or where 3D representations using BIM, SmartPlant, or PDMS software would be impractical. Such environments include old buildings that were constructed several decades ago and constantly changing environments such as working sites that act as temporary storage spaces for construction materials. In the current literature, it is a challenging problem that needs to be addressed. Rather than employing computer-aided design (CAD) applications to construct digital models of the environment, the real environment is digitized into point cloud data, which can realistically and accurately represent complex construction sites or plants. By taking advantage of digital geometry processing technology, the acquired point cloud data is processed and used for the intelligent planning of lifting paths.
1.2　Objectives and scope
The objective of this research is to develop an intelligent path planning system for environments of any complexity to improve the productivity and safety of tower crane lifting. In near real-time, optimized and safe lifting paths are automatically produced for tower crane lifting in highly complex environments that were virtualized to point cloud data. Point cloud data processing techniques, such as registration and resampling, are also explored in this paper.
1.3　State-of-the-art
1.3.1 　 Virtual environments
CAD tools are commonly employed in the modelling and visualization of construction sites and industrial plants (e.g., water treatment and chemical plants) during the design and construction phases. There are some commercially available solutions for this purpose. The plant design suite developed by AutoDesk [12] provides a useful tool for plant design and review. PDMS, from AVEVA[13], is a comprehensive system for interactive plant design that is used by both contractors and plant owners. SmartPlant, which was developed by InterGraph[14], is an integrated system that employs rule-based methods for the design and management of plant models. In the field of construction, BIM is increasingly being employed. It offers insights that aid in the scheme, design, construction, and management of infrastructure and buildings throughout their entire lifespan.
Point cloud technology has become a popular and powerful tool for the virtualization of real buildings and plants. With the rapid development of 3D scanning techniques, point clouds are being used to produce virtualized 3D models for applications such as reverse engineering, rendering, and visualization. Employing laser scanning and point cloud technologies to create virtualized 3D models can reduce substantially the computational time compared to conventional CAD modelling techniques while maintaining the fine details needed for real, complex environments. Thus, point cloud technology is suitable for the virtualization of real construction sites or plants that do not have existing 3D models in BIM, SmartPlant, or PDMS.
Point clouds are commonly used in robotics. For robotic navigation in indoor environments, Kinects[15,16] is used to capture depth images of small-scale areas, and point clouds are constructed based on captured RGB-D images. The 3D maps constructed from the point cloud data are used robotics navigation systems. For large-scale environments, laser scanners are generally used. Octomap, which was proposed by Hornung et al., uses a 3D volumetric representation of the space in addition to the point cloud data captured from the laser scans of outdoor environments or the depth images of for indoor environments from Kinect[17].
1.3.2 　 Computer-aided crane lifting
Extensive research has used computed technology to improve the productivity and safety of crane lifting. Some works have explored the use of simulation systems to aid in the planning of lift paths. Haas et al. develop the HeLPS simulation system, which carries out the planning for setting up cranes[1]. Varghese et al. furthered the research by using the HeLPS system to monitor safety hazards during the interactions [2]. Al-Hussein et al. proposed an integrated system that uses simulation tools to help construction managers with decision-making during the construction planning process[3]. Kang et al. presented a system that provides 3D animations and simulations of the construction processes[4]. Chadalavada et al. proposed the CLPS simulation system, which works as a plugin for the Autodesk Inventor, for safety monitoring and interactive manipulation[5]. Wang et al. presented a simulation system that would be used to train tower crane operator using virtual reality technology[6]. Some other works have focused on issues relevant to lift planning, such as crane selection[18,19] and the layout of the crane[20‒22]. In addition to the work done on lifting by a single crane, multi-crane lifting has also been studied, and it is considered robot system suspended [23‒26].
Different algorithms have been explored to address intelligent planning for lifting paths. Initial efforts used simple CAD models to depict the crane and its surrounding environment[7‒10]. Heuristic searches and serial genetic algorithms were exploited in these studies to address the path planning issue. In these works, genetic algorithms (GAs) were able to obtain highly optimized solutions. However, their applications are limited due to the intensive computational requirements[8]. Other algorithms involving bidirectional rapidly-exploring random trees (RRTs)[11], bi-directional expanding trees[27], and probabilistic road maps (PRMs)[28] have been employed to quickly produce lifting paths for cranes. A comparison of these algorithms with the GA-based approach in the paper[8] is carried out in the work[28]. The results show that GA can offer better quality solution, but a larger amount of time is needed for the algorithm to converge. In previously published papers[29‒31], Cai et al. explored graphics processing unit (GPU) parallelization to improve the computational time of the GA calculations, and reproduction operators were used to enhance the search capacity of the GA.
1.4　Problem statement
Figure 1 shows an example of a highly complex environment where tower crane lifting tasks will be performed. The environment includes working sites used as temporary storage space for precast materials and old buildings that were constructed decades ago. This environment has no exist-ing digital modeling document. The target (shown in the white blocks) will be moved by the tower crane (in yellow) from the start position to the end position. A method of generating a safe and optimal lifting path in such a situation needs to be explored.
1.5　Proposed solution
Recent research[30] was conducted on intelligent path planning for heavy lifting in plants using mobile cranes. These plants had existing digital 3D models in SmartPlant or PDMS. This research paper expands on the previous work by exploring novel technology for the intelligent planning of lifting paths conducted by tower cranes in complex environments that do not have existing digital models.
There are two major problems that are addressed in this paper. The first is the handling of complex environments that do not have existing digital models. These highly complex environments can be old plants that were built several decades ago or temporary spaces used to store precast and other building materials. The second problem is that tower crane and mobile crane are quite different in terms of structure and lifting procedure. The details of such tasks are investigated by looking at the kinematics of tower cranes, which serves as the base for optimal lifting path planning.
In this work, a new approach to intelligent path planning for the lifting tasks conducted by tower cranes is proposed. Environments of any complexity are virtualized using laser scanning technology, point cloud-based digital geometry processing, and a master-slave parallel genetic algorithm (MSPGA). In general, the goal is to develop an innovative search method to achieve optimal lifting path planning for tower cranes.
The digitization of the environments is achieved using point clouds. New collision detection methods need to be explored for the tower cranes and the virtualized environments. Moreover, point-cloud-based multi-level depth maps, the kinematics of tower cranes, continuous collision detection (CCD), and hybrid C-space are explored.
2 Environment virtualization using laser scanning technology
In the following sections, virtualized environments are used to depict plants, buildings, construction sites and terrains. In this section, environment digitization using laser scanning and point cloud-based digital geometry processing is introduced.
2.1　Laser scanning
A 3D scanner is a device that collects and analyzes the shape and appearance data of any real-world environment. Commercial products (hardware and software) from FARO, Leica, Zoller Fröhlich, and RIEGL provide high-precision laser scanning. The FARO Focus 3D X330 was used in this work. It is a professional 3D laser scanner that can used for both indoor and outdoor measurements. The Focus 3D X330 offers a distance accuracy up to ±2mm, and an extra-long range of 0.6 to 330m with integrated GPS. The measurement speed and resolution are up to 976000 points per second and 70 megapixels, respectively.
2.2　Point cloud processing
For each scan, the laser scanner generates a point cloud within its valid range. In most cases, a single scan is not sufficient due to obstacles in the scanner’s field of view. Therefore, multiple scans and the stitching of the multiple scans together are necessary. In Figure 2, the workflow of processing multiple scans is illustrated. The captured point cloud data are processed through registration, segmentation, de-noising and resampling before the final virtualized result is obtained.
2.2.1 　 Multiple point clouds registration
Point cloud registration determines a rigid transformation that needs to be applied to align two different scans. This registration has two distinct steps: global registration and local registration. Initially, arbitrary input poses of the same environment are approximately aligned via global registration. Local registration then optimizes the transformation between the two globally registered scans by refining the correspondences between the two. The details of this two-phase registration are described in the paper[32].
2.2.2 　 Intelligent segmentation
In certain cases, there may be disparities in terms of object location and the addition or removal of objects in the scans to be aligned. It is necessary to identify these differences before alignment is performed. In this work, a segmentation algorithm[33] is utilized to distinguish the desired objects and shapes in the point cloud environment, and it is applied either during or after registration. The method begins with the interactive selection of certain points on the objects of interest, which are called seeds. The points in the immediate neighborhood of the seeds are then merged to the object cluster according to the smoothness constraint and color similarity. In following iterations, the cluster size is increased, and termination occurs when a segmented object has been formed. Min-cut-based segmentation[33] can also be employed to distinguish the foreground and background portions of the point cloud environment.
2.2.3 　 Resampling
The aligned scans generally result in a large size, which grows as more scans are added due to the large number of duplicate and redundant points. Moreover, rendering and subsequent processing is computationally expensive due to the large size of the dataset. Thus, resampling is employed to eliminate redundancy and reduce the file size. A practical solution is to downsample the point cloud data, which would reduce the resolution. A set of 3D voxel grids can be generated by partitioning the bounding box of the point cloud. The size of the individual grids, defined by the users, determines the resolution of the downsampling. In each grid, the points can be approximated or resampled with their centroid, which is controlled by the downsampling rate that was defined by the user.
A noise threshold can be predefined and grids that contain less points than the threshold value would be considered as noise. De-noising can be achieved by applying a statistical outlier removal method that is based on the distribution of the distances from a point to its neighbors.
3 Tower crane virtualization and point-cloud-based collision avoidance
Intelligent planning for lifting paths relies on the detection of collisions between objects in the virtual environment and the components (including load) of the digitalized crane. The fitness evaluation step of the MSPGA takes collision detection into account.
The computational efficiency of the collision detection module can be improved by incorporating the hybrid C-space strategy proposed in [30]. There is a tradeoff between the pre-processing time and the planning time in this strategy. The crane has four degrees of freedom (4-DOF), which will be discussed further in Section 3.2. The collision information for two DOFs of the crane are computed prior to running the GA and the information is stored in the 2D C-space. The collision information for the other two DOFs are computed during the GA iterations. The hybrid C-space strategy can obtain the computationally simple 2D C-space in a short time, thereby reducing the time expended in the planning phase.
A schematic diagram of the collision detection engine is presented in Figure 3. To detect collisions between the tower crane and objects in the environment, a depth map of the environment is generated, and the components of the crane in all possible configurations are compared to the points in the depth map. Section 3.1 presents the process used to generate the depth map of the environment. Section 3.2 illustrates the kinematics of tower cranes, which is essential in determining the positions of the tower crane components (including target). The hybrid C-Space and swept volumes are discussed in Section 3.3 and Section 3.4, respectively. Boolean values from the collision detection are an important factor in the fitness function of the MSPGA.
3.1　Rasterization of point cloud environments
The point cloud data of the environment must be discretized into a histogram-shaped depth map[34]. GPU parallelization can be used with multi-level depth maps[35] to achieved 3D collision detection of large environments.
Quick depth map generation from the point cloud environment is realized using a GPU depth map generator, which was developed based on OpenGL’s concept of rasterization[34]. A large environment (up to several square kilometers) produce a large number of points in the model (more than hundreds of millions). A CPU must invest a substantial amount of time to deal with such a huge dataset for rasterization. The significant computational capacity of GPU parallelization allows this process to be significantly sped up.
In the depth map generator, parallel GPU threads are mapped onto the x-y ranges of the plant model. Each GPU thread considers one pixel value in the x-y plane, searches for the corresponding points in the point cloud model, and records the z values of those points. In this way, thousands of GPU threads run concurrently to generate the depth map quickly.
Generally, the components of the tower crane, including the lifting target, operate above the plant structures at all stages of the lifting task. Therefore, the tallest portions of structures in the environment restrict the tower crane’s contact with the environment objects. Thus, in this research, for efficiency and the practicality, only the maximum z value for each pixel in the point cloud environment is considered during collision avoidance.
Section 5.2 describes the time requirements and the results of the generated depth map.
3.2　Tower crane virtualization
Tower cranes are important tools used for lifting tasks in industrial plants and construction sites. In this work, a hammerhead tower crane is used, as shown in Figure 4a. Figure 4b illustrates the degrees of freedom (DOFs) and the kinematics information of the tower crane.
As indicated in Figure 4b, the tower crane has 4-DOF, which are described as follows:
(1) Swinging―Rotation of the counter-jib and jib around the z-axis, which is oriented along the tower height, and point B is the rotation center; the angle of rotation is expressed as
$α S W$
.
(2) Hoisting―raising or lowering of the target; the hoisting distance is denoted as
$l H S$
.
(3) Trolley Movement―Trolley moves in or out along the jib; the movement distance is indicated as
$l M V$
.
(4) Target rotation―Target (or load) rotates about the z axis; the angle of rotation is expressed as
$α B D$
.
There are five critical points on the tower crane, as labelled on Figure 4b. Point A is the center of the tower crane’s base. It is a fixed point that is determined during the setup of the crane on the ground. Point B is the cockpit rotation pivot (CRP) point, around which the jib and counter-jib rotate. The position of point B is extrapolated from the height of the tower and the location of the base (point A). Points C and D are the tips of counter jib and the jib, respectively, and point E is the load center. Points C, D, and E can be extrapolated based on points A and B through vector operations. The following formulas (Equations 1-3) show the calculation of these three critical points. The definitions of the parameters used is shown in Table 1.
$C = A + R z ( α B D ) ( A B ⃗ + R z ( α S W ) B C ⃗ )$
$D = A + R z ( α B D ) ( A B ⃗ + R z ( α S W ) B D ⃗ )$
$= A + R z ( α B D ) ( T y ( l M V ) T z ( - l H S ) A B ⃗ )$
The parameters used in the kinematics calculations of the tower crane
Parameter Definitions
$α B D$
The rotation angle of the tower body around the
$z$
axis, which is fixed once the tower crane is set up
$R z ( α B D )$
The rotation matrix around the
$z$
axis for a rotation angle of
$α B D$
$R z ( α S W )$
The rotation matrix around the
$z$
axis for a rotation angle of
$α S W$
$T y ( l M V )$
The translation matrix along the
$y$
axis for a moving length of
$l M V$
$T z ( - l H S )$
The translation matrix along the
$- z$
axis for a moving length of
$l H S$
$A B ⃗$
The vector from point A to point B
$B C ⃗$
The vector from point B to point C, its length is the counter-jib’s length
$B D ⃗$
The vector from point B to point D, its length is the jib’s length
3.3　Hybrid C-space
The hybrid C-space for the two DOFs of the crane, i.e., the trolley movement and the swinging of the jibs, are calculated before the initiation of the MSPGA. For each combination of the trolley movement distance
$l M V$
and the swinging angle
$α S W$
, the positions of the jib and counter-jib are deduced and checked against points in the environment depth map. The collision information is then used to generate the hybrid C-space.
Figures 5a and 5b illustrates the tower crane in the point cloud environment and the tower crane’s hybrid C-space (the purple concentric circles), respectively. Each point in the concentric circles indicates that there is no collision between the environment and the jib/counter-jib in the stipulated configuration with trolley movement distance of
$l M V$
and swinging angle of
$α S W$
. For example, there are no points shown in sector A in Figure 5b, indicating that a collision would occur between the jibs and the oil tank in this area.
3.4　Continuous collision detection
Continuous collision detection (CCD) is a method of detecting overlapping regions between the swept spaces defined by the movement of the crane components and the environment objects during the continuous steps of the lifting operation[10]. In the current work, CCD is implemented to check for collisions with the swept spaces constructed from the paths that the crane components move through as the crane transitions between independent configurations during the lifting task.
In the hybrid C-space strategy, collision checks are done by considering the movements of the crane components and the lifting target separately. First, the collision results of the swept spaces established by the jib and counter-job movements are obtained from the hybrid C-space. The swept frontier method is then used to detect collisions within the swept space constructed by the motion of the target.
Swept frontiers are the surfaces of a swept volume, which is the volume of space that the load moves through during a lifting task, that have the highest risk of collision with objects in the plant. As cranes are generally only operated above the maximum height of the plant structures, only the bottom surfaces of the load’s swept volumes are considered as swept frontiers. A unique swept frontier can be designed by strategizing the movement between two independent crane configurations. Figure 6 demonstrates the swept frontiers of the moving target in 2D. In this case, the tower crane’s jibs (and counter-jibs) swings a certain angle in the counter-clockwise direction, the target is rotated, and then the trolley moves the target outwards to arrive at the destination position.
During the path planning process, the algorithm performs searches in the hybrid C-space and the swept frontiers to check for collision between the operational crane components and the depth map of the environment. The fitness evaluation function of the MSPGA relies on the CCD results, which are computed as Boolean values.
4 Path planning for tower crane lifting in point-cloud-based VR environments
GA, as a general optimization algorithm, is well-suited for finding global optimality in mathematical problems such as lifting path planning. A simple GA, constituting of four functional modules (selection, mutation, crossover, and fitness evaluation), is well-suited for GPU parallelization. The highly parallel computing structure of GPUs enables various types of data processing to be conducted quickly. By embedding the components of the GA, which normally require intensive computational power, into the GPU platform, it is possible to achieve significant performance improvement.
Cai et al. developed a master-slave parallel genetic algorithm that was well-suited for massive parallelization[30]. As a result, the computational complexity of the GA was simplified using parallel GPU threads. They investigated automatic path planning for mobile cranes in complex model-based environments in SmartPlant and PDMS. In this paper, the MSPGA is briefly introduced and the application of point clouds to digitize complex environments for automatic planning of lifting paths is presented.
The MSPGA framework is depicted in Figure 7. The CPU is used as the master processor for the MSPGA, while the GPU acts as the slave processors and handles the four functional components of the GA. In each GA iteration, GPU kernels for the four components are executed in sequence. At the end of each iteration, the CPU evaluates the fitness of the final population and checks it against the termination fitness value. Upon meeting the termination fitness requirement, the GA search is terminated and the optimum chromosome (solution) from the GPU memory is collected by the CPU. As MSPGA retains the probabilistic completeness of the simple GA, a sufficient increase in the number of iterations ensure a 100% success rate of finding a solution.
5 Experiment and result
All the experiments are conducted on a PC with an NVIDIA GeForce GTX660 GPU and a 3.60GHz Intel Core i7-4790 CPU.
5.1　Registration of point clouds
To demonstrate the point cloud processing method, a real 300m
$×$
150m plant was scanned and modeled. During the scanning of the plant shown in Figure 1, the resolution of the scanner (FARO Focus X330) was set to 8192 pt per 360° and 2mm. The scan size is 8120
$×$
3414pt.
In the experiment, the FARO scanner was placed in nine different locations in the plant to capture the entire environment. The first six scans listed in Table 2 were taken on days 1 and the remaining three scans were conducted on day 2 to replenish some of the details that were missing from the day 1 scans. Each scan resulted in raw data with file sizes of nearly 0.5GB. The number of points, file size, and scanning time of the nine scans are listed in Table 2. As shown in Figure 8, the six scans and three scans captured in two days were globally registered respectively using FARO SCENE software. The crane was retracted on day 1 and extended on day 2. To increase the registration accuracy and to obtain a pure plant point cloud, the blue crane was segmented and removed from each point cloud. The total nine scans were then aligned together using Super4PCS, and local registration based on sparse ICP[36] using
$L p$
norm (
$p$
=0.4) was used to refine the registration and minimize the distance errors among the point clouds. The complete virtualized environment of the scanned plant was obtained. Based on Figure 8, it is evident that the point clouds of the captured scans were well aligned after global and local registration.
Details of nine scans conducted in the experiment.
Scan ID Number of Points File Size (MB) Scanning Time (Min:Sec)
1 11483663 261.950 10:18
2 11850648 270.319 10:37
3 12614167 287.732 11:20
4 16271827 371.147 10:27
5 20469452 466.876 13:56
6 12995088 296.419 12:38
7 12451583 284.024 10:10
8 12112391 276.289 10:16
9 12592680 287.242 10:41
There are two issues that need to be addressed here. The purpose of using point clouds is to achieve an automatic process. However, human interaction is needed during the segmentation step. The second issue is that pair-wise local registration can be time consuming. The experiments were performed on a PC with 16.0GB memory and a 3.60GHz Intel Core i7-4790 CPU. Generally, about one hour was needed to run one pair-wise local registration. However, as point cloud processing for the environment is an offline process, this running time is acceptable and human-computer interaction is allowed. In comparison, the modelling and virtualization of plant using PDMS and BIM generally requires weeks and several professional engineers. The total time and labor cost of the proposed virtualization method is small in comparison.
The number of points in the fully virtualized plant obtained from the nine merged scans is 120144032. The file size and number of points after downsampling with different resolutions and sampling rates is listed in Table 3. Based on the results, it is clear that downsampling can greatly reduce the file size. In Figure 9, the sampled point clouds are rendered at 1/9, 1/16, and 1/25 of the full sampling rate, and a good rendering effect is still achieved at 1/25 rate.
Details of different resampling result for the point cloud data
Rate Resolution (mm) Number of points File size (MB)
Full 2 120144032 2740.473
1/2 2 60090038 1716.858
1/4 3 30027171 885.045
1/9 4 13341982 471.086
1/16 5 7513351 265.288
1/25 6 4804782 169.653
5.2　Point cloud rasterization for collision detection
5.2.1 　 Depth map image
Figure 10 shows the rasterization of the point cloud environment. The input, shown in Figure 10a, is the point cloud environment, and the output, shown in Figure 10b, is the depth map generated.
5.2.2 　 Points in the depth map
Table 4 illustrates the reduction in complexity achieved by converting the point cloud file (input) into the depth map (output). The number of points in the depth map are significantly reduced compared to the point cloud file. As the depth map is used for collision detection, this helps to greatly shorten the time expended on collision detection. Table 5 shows that the number of points in the depth map also decreases as the resolution of the depth map is lower from 10cm to 100cm.
Rasterization of the point cloud environment at different sampling rates for a depth map resolution of 40cm
Sampling rate File size (MB) Number of points in the point cloud file Number of points in the generated depth map Rasterization time (ms)
1/9 471.086 1334982 22602 828
1/16 265.288 7513351 20342 459
1/25 169.653 4804782 20455 295
Rasterization of the point cloud environment for various depth map resolutions at a sampling rate of 1/9
Depth map Resolution (cm)

Number of points in

the point cloud file

Number of points in the

generated depth map

Rasterization time (ms)
10 13341982 117898 848
20 54214 836
40 22602 828
100 6569 822
5.2.3 　 Rasterization time
Table 4 lists the rasterization times of the point cloud files at different sampling rates for a depth map resolution of 40cm, and Table 5 lists the rasterization time for different depth map resolutions at a sampling rate of 1/9. Both tables show that in all cases the depth maps are generated quickly from the point cloud environment (less than 1 second), while the depth map resolution has little effect on the rasterization time. Furthermore, the rasterization time increases with increasing number of points in the point cloud file.
5.3　Performance of the path planner
Three different groups of experiments were carried out to test the effects of depth map resolution and sampling rate on the performance of the path planner. The sampling rates were 1/9, 1/16, and 1/25 of the full sampling rate for groups 1, 2, and 3, respectively. Table 6 lists the input values set for all the experimental groups. The start and end configuration are defined in terms of the DOFs of the tower crane (refer to Figure 4b). Using the complex environment that was shown in Figure 1, the path planning algorithm was executed 50 times for each depth map resolution of each experimental group. The results are shown in Tables 7,8 and 9.
The inputs used in all the experimental groups used to evaluate the performance of the path planner
Input Value
Tower crane model Terex SK415-20
Size of population 100
Length of string 6
Crossover rate 0.75
Mutation rate 0.25

Start configuration

(

$α S W$
,
$l M V$
,
$l H S$
,
$α L D$
)

(21°, 2714cm, 2113cm, 355°)

End configuration

(

$α S W$
,
$l M V$
,
$l H S$
,
$α L D$
)

(113°, 6488cm, 2113cm, 113°)
Termination iteration 200
Group 1: Performance of the GA for various depth map resolutions at a sampling rate of 1/9
Depth map resolution (cm) GA runtime (ms) Nth Iteration (when convergence begins) Average success fitness value Success rate (%)
10 90358 44 511.46 100%
20 43289 40 513.79 100%
40 20312 48 515.15 100%
100 9941 61 518.90 96%
Group 2: Performance of the GA for various depth map resolutions at a sampling rate of 1/16
Depth map resolution (cm) GA runtime (ms) Nth Iteration (when convergence begins) Average success fitness value Success rate (%)
10 78991 32 523.38 100
20 36186 43 521.56 100
40 18610 43 521.49 100
100 8742 42 522.96 100
Figure 11 presents an example of the fitness value for each iteration during the GA search. The fitness value will start to converge at Nth iteration if the GA search is successful.
5.3.1 　 Convergence speed and success rate
Tables 7,8 and 9 list the GA success rates, which are nearly 100% for all depth map resolutions and point cloud datasampling ratesstudied. Further-more, convergence occursfast enough, since Nth iteration was found to be between 22 and 64.
Group 3: Performance of the GA for various depth map resolutions at a sampling rate of 1/25
Resolution of depth map (cm) GA runtime (ms) Nth Iteration (when convergence begins) Average success fitness value Success rate (%)
10 70431 22 528.52 100
20 31353 43 529.35 100
40 16592 48 528.84 100
100 8664 64 529.89 98
5.3.2 　 Execution time
Tables 7,8 and 9 show that the GA runtime slowly increases as the sampling rate increases from 1/25 to 1/9, while a sharp increase in runtime is observed as the depth map resolution becomes finer from 100cm to 10cm. This indicates the that depth map resolution has a greater effect on the GA runtime than the sampling rate.
5.3.3 　 Scalability of the path planner
The three groups of experiments resulted in success rates close to 100% and GA runtimes less than 100 seconds for different combinations of point cloud sampling rates and depth map resolutions. Thus, the proposed MSPGA is scalable in terms of depth map resolution and point cloud file size.
5.3.4 　 The produced lifting path
Figure 12 presents one of the lifting paths produced. Firstly, the load is lifted (the blue dotted line) from the start position, the trolley then moved out (the green dotted line), and the jibs swing (the yellow circle) in the counter-clockwise direction. The trolley was then moved in (the green dot line), the load was moved down (the blue dotted line), and rotated (the orange fan area) to arrive at the end position.
6 Conclusions and future work
This paper explores the intelligent planning of lifting paths for tower cranes in complicated environments. Laser scanning technology was utilized to create point cloud data of working sites or old plants. By doing this, the time-consuming and onerous task of modeling the environments can be avoided. After stitching together multiple scans, the complete point cloud environment is rasterized into a depth map, which is then used in processes such as collision avoidance and GA-based searching to determine optimal lifting paths. The depth map approach allows the relevant processes to be applied to environments of any complexity. Moreover, the developed genetic algorithm is highly parallelized, and can therefore substantially accelerate the process of intelligent path planning for lifting tasks conducted by tower cranes.
Laser scanning can only capture the surface geometry of objects. Thus, it is impossible to digitize the internal structures of the objects in the environment. Additionally, the location and orientation of certain objects could be changed in the multiple-scan stitching process. These objects need to be removed to achieve high accurate alignment of the multiple scans. Currently, the segmentation technique is still fairly primary, and implementation of semantic level segmentation will be considered in future works. Moreover, this paper only explores the lifting task of a single crane. The intelligent path planning of lifting tasks performed by dual- or multi-cranes will also be considered in future research.

Reference

1.

Lin K L, Haas C T. An interactive planning environment for critical operations. Journal of Construction Engineering and Management, 1996, 122(3): 212‒222 DOI:10.1061/(asce)0733-9364(1996)122:3(212)

2.

Varghese K, Dharwadkar P, Wolfhope J, O'Connor J T. A heavy lift planning system for crane lifts. Computer-Aided Civil and Infrastructure Engineering, 1997, 12(1): 31‒42 DOI:10.1111/0885-9507.00044

3.

Al-Hussein M, Athar Niaz M, Yu H T, Kim H. Integrating 3D visualization and simulation for tower crane operations on construction sites. Automation in Construction, 2006, 15(5): 554‒562 DOI:10.1016/j.autcon.2005.07.007

4.

Kang S C, Chi H L, Miranda E. Three-dimensional simulation and visualization of crane assisted construction erection processes. Journal of Computing in Civil Engineering, 2009, 23(6): 363‒371 DOI:10.1061/(asce)0887-3801(2009)23:6(363)

5.

Chadalavada S, Madras G, Varghese K. Development of a computer aided critical lift planning system using parametric modeling software. In: Proceedings of the 2010 (1st) International Conference on Engineering, Project, and Production Management, Association of Engineering, Project, and Production Management, 2010, 1–12 DOI:10.32738/ceppm.201010.0001

6.

Wang X, Lv Y L, Wu D. Development of tower crane simulation system with flexible wire rope. In: Proceedings of the 2015 International Symposium on Computers and Informatics. Beijing, China, Paris, France, Atlantis Press, 2015, 2416–2423 DOI:10.2991/isci-15.2015.314

7.

Sivakumar P, Varghese K, Babu N R. Path planning of construction manipulators using genetic algorithms. In: Proceedings of the 16th IAARC/IFAC/IEEE International Symposium on Automation and Robotics in Construction. Madrid, Spain. International Association for Automation and Robotics in Construction (IAARC), 1999, 555–560 DOI:10.22260/isarc1999/0086

8.

Ali M S A D, Babu N R, Varghese K. Collision free path planning of cooperative crane manipulators using genetic algorithm. Journal of Computing in Civil Engineering, 2005, 19(2): 182–193 DOI:10.1061/(asce)0887-3801(2005)19:2(182)

9.

Reddy H R, Varghese K. Automated path planning for mobile crane lifts. Computer-Aided Civil and Infrastructure Engineering, 2002, 17(6): 439–448 DOI:10.1111/0885-9507.00005

10.

Olearczyk J, Bouferguène A, Al-Hussein M, Hermann U R. Automating motion trajectory of crane-lifted loads. Automation in Construction, 2014, 45: 178–186 DOI:10.1016/j.autcon.2014.06.001

11.

Lin Y S, Wu D, Wang X, Wang X K, Gao S D. Lift path planning for a nonholonomic crawler crane. Automation in Construction, 2014, 44: 12–24 DOI:10.1016/j.autcon.2014.03.007

12.

AUTODESK. Plant Design Suite. http://www.autodesk.com/suites/plant-design-suite/overview. 2016-1-4

13.

AVEVA. Solutions for the plant industries. http://www.aveva.com/en/Products_and_Services/AVEVA_for_Plant.aspx. 2016-1-4

14.

INTERGRAPH. SmartPlant® Enterprise. http://www.intergraph.com/products/ppm/smartplant/. 2016-1-4

15.

Izadi S, Kim D, Hilliges O, Molyneaux D, Newcombe R, Kohli P, Shotton J, Hodges S, Freeman D, Davison A, Fitzgibbon A. KinectFusion: Real-time 3D reconstruction and interaction using a moving depth camera. ACM, New York, USA, 2011, 559–568

16.

Henry P, Krainin M, Herbst E, Ren X F, Fox D. RGB-D mapping: Using Kinect-style depth cameras for dense 3D modeling of indoor environments. The International Journal of Robotics Research, 2012, 31(5): 647–663 DOI:10.1177/0278364911434148

17.

Hornung A, Wurm K M, Bennewitz M, Stachniss C, Burgard W. OctoMap: an efficient probabilistic 3D mapping framework based on octrees. Autonomous Robots, 2013, 34(3): 189–206 DOI:10.1007/s10514-012-9321-0

18.

Olearczyk J, Al-Hussein M, Bouferguène A. Evolution of the crane selection and on-site utilization process for modular construction multilifts. Automation in Construction, 2014, 43: 59–72 DOI:10.1016/j.autcon.2014.03.015

19.

Marzouk M, Abubakr A. Decision support for tower crane selection with building information models and genetic algorithms. Automation in Construction, 2016, 61: 1–15 DOI:10.1016/j.autcon.2015.09.008

20.

Huang C, Wong C K, Tam C M. Optimization of tower crane and material supply locations in a high-rise building site by mixed-integer linear programming. Automation in Construction, 2011, 20(5): 571–580 DOI:10.1016/j.autcon.2010.11.023

21.

Lien L C, Cheng M Y. Particle bee algorithm for tower crane layout with material quantity supply and demand optimization. Automation in Construction, 2014, 45: 25–32 DOI:10.1016/j.autcon.2014.05.002

22.

Wang J, Zhang X D, Shou W C, Wang X Y, Xu B, Kim M J, Wu P. A BIM-based approach for automated tower crane layout planning. Automation in Construction, 2015, 59: 168–178 DOI:10.1016/j.autcon.2015.05.006

23.

Carricato M, Merlet J P. Stability analysis of underconstrained cable-driven parallel robots. IEEE Transactions on Robotics, 2013, 29(1): 288–296 DOI:10.1109/tro.2012.2217795

24.

Gouttefarde M, Collard J F, Riehl N, Baradat C. Geometry selection of a redundantly actuated cable-suspended parallel robot. IEEE Transactions on Robotics, 2015, 31(2): 501–510 DOI:10.1109/tro.2015.2400253

25.

Park J, Chung W K, Moon W. Wire-suspended dynamical system: stability analysis by tension-closure. IEEE Transactions on Robotics, 2005, 21(3): 298–308 DOI:10.1109/tro.2004.840888

26.

Oh S R, Agrawal S K. Cable suspended planar robots with redundant cables: controllers with positive tensions. IEEE Transactions on Robotics, 2005, 21(3): 457–465 DOI:10.1109/tro.2004.838029

27.

Kang S, Miranda E. Planning and visualization for automated robotic crane erection processes in construction. Automation in Construction, 2006, 15(4): 398–414 DOI:10.1016/j.autcon.2005.06.008

28.

Chang Y C, Hung W H, Kang S C. A fast path planning method for single and dual crane erections. Automation in Construction, 2012, 22: 468–480 DOI:10.1016/j.autcon.2011.11.006

29.

Cai P P, Cai Y Y, Chandrasekaran I, Zheng J M. A GPU-enabled parallel genetic algorithm for path planning of robotic operators//GPU Computing and Applications. Singapore: Springer Singapore, 2014, 1–13 DOI:10.1007/978-981-287-134-3_1

30.

Cai P P, Cai Y Y, Chandrasekaran I, Zheng J M. Parallel genetic algorithm based automatic path planning for crane lifting in complex environments. Automation in Construction, 2016, 62: 133–147 DOI:10.1016/j.autcon.2015.09.007

31.

Huang L H, Zhang Y Z, Zheng J M, Cai P P, Dutta S, Yue Y F, Thalmann N, Cai Y Y. Point cloud based path planning for tower crane lifting. In: Proceedings of Computer Graphics International. Bintan, Island, Indonesia, ACM Press, 2018, 211–215 DOI:10.1145/3208159.3208186

32.

Cai Y Y, Zheng J M, Zhang Y Z, Wu X Q, Chen Y, Tan B Q, Yang B Y, Liu T R, Thalmann N. Madam snake white: a case study on virtual reality continuum applications for Singaporean culture and heritage at haw par villa. Presence: Teleoperators and Virtual Environments, 2018, 26(4): 378–388 DOI:10.1162/pres_a_00303

33.

Golovinskiy A, Funk T. Min-cut based segmentation of point clouds. In: 2009 IEEE 12th International Conference on Computer Vision Workshops. Kyoto, Japan, IEEE, 2009 DOI:10.1109/iccvw.2009.5457721

34.

Rost RJ, Licea-Kane B. Chapter 1. Review of OpenGL Basics. In: OpenGL Shading Language, 3rd edn. Boston, MA, Addison-Wesley, 2009, 1–34

35.

NVIDIA. CUDA C Programming Guide. http://docs.nvidia.com/cuda/cuda-c-programming-guide/#axzz3wRH77NnU. 2015-10-3

36.

Bouaziz S, Tagliasacchi A, Pauly M. Sparse iterative closest point. In: SGP'13 Proceedings of the Eleventh Eurographics/ACMSIGGRAPH Symposium on Geometry Processing. 2013, 113–123