Google Earth Augmented for Earthwork Construction Planning

Abstract

This chapter introduces GoogleEarthWork which is an augmented geographic information system (GIS) based on Google Earth to manage and visualize heterogeneous site information, especially 3D models, aerial and ground images, panoramas, and GIS data of the site environment. The concept is to realize a highly automated end-to-end earthwork construction planning system that is able to generate project management deliverables from heterogeneous information and enhance the usefulness and intelligence of GIS for better project planning and control in earthwork construction. With identified constraints from the augmented Google Earth, the earthwork planning problem is formulated, and an optimized executable plan can be automatically generated, including work breakdown structure and project network model. Demonstration cases are provided to prove concepts of and illustrate functionalities of GoogleEarthWork in support of earthwork construction planning in realistic settings.

1. Introduction

Construction project planning and control requires an integral and comprehensive understanding of the construction site. During the planning process, a large volume of data are collected and created to identify potential problems on the construction site and select proper construction methods and procedures in order to ensure safety and on-time delivery of the project. Such data include (1) as-planned information that describes the design and the scope of the project, (2) as-built information that describes the actual situation on the construction site, and (3) environmental information that can be used to evaluate the impact of the environment on the project and the impact of the project on the environment. At present, engineers and project managers can be overwhelmed with various information coming from different sources (as listed in Table 1); however, maintaining large-volume heterogeneous datasets would become a big burden unless they can be linked and managed together to enable efficient information retrieval and facilitate problem identification [1].

Data	Usage
2D drawings (as-designed)	Design
3D models (as-designed)	Design/construction prototyping [2, 3]; Site layout planning [4]; Crane path and lift planning [5]
Images/videos (as-built)	Site inspection and reporting; As-built modeling [6, 7]; Progress monitoring [8]
Laser scanning (as-built)	As-built modeling [9, 10, 11]; Progress monitoring [8]
Satellite images, topographic data, et al. in GIS (environmental)	Site layout planning [12, 13, 14, 15, 16, 17]; Route planning [15]; Data management and visualization [1, 18, 19]

Table 1.

Typical datasets available on a construction project.

The adoption of advanced sensing and information management technologies in construction is greatly hindered by (1) high expenses on system development yet unclear benefits of implementation [20, 21, 22], (2) inefficient visualization and oversimplified site modeling methods for coping with complicated site environment [20], (3) insufficient integration and interoperability [23, 24], and (4) technology barriers and organizational difficulties in information sharing and distribution [20, 25].

Several technologies have been applied on project information management and visualization, including building information modeling (BIM) [2], augmented reality (AR) [26, 27, 28], the integration of BIM and AR, the integration of GIS and BIM, and Google Earth, as listed in Table 2.

Technology	Information
BIM	3D models
AR	3D models + images
BIM + AR	3D models + images
GIS + BIM	3D models + satellite images + topographic
Google Earth	3D models + images + satellite images + topographic

Table 2.

Site information management methods.

BIM demonstrates great potential to model rich geometric and semantic information of a building object but lacks the capability to incorporate as-built and environmental information. AR has gained substantial attention lately due to its capability to combine site photos and as-planned 3D models. However, the absence of an accurate model of the surrounding environment, for example, those 3D site models generally provided by 3D GIS systems, makes AR less instrumental in construction engineering applications that demand the representation of frequent, intensive interactions and relationships between the facilities being built and the site environment, especially where the project is situated in crowded cities or environmentally fragile areas. Researchers have also leveraged on the benefits of integrating BIM and AR [29, 30, 31, 32]. Nonetheless, incorporating AR into BIM software is still practically infeasible due to inherent limitations of BIM software in handling large external datasets for real-time rendering [31].

GIS has achieved significant success in managing large-scale heterogeneous spatial information. Considerable attention has been placed on the integration of BIM models and GIS so as to integrate the indoor as-built information and the outdoor environmental information [33, 34]. To tackle unstructured data, researchers utilized variants of Extensible Markup Language (XML) to develop shared project information models thanks to its extensibility and interoperability on the web schemas [35, 36, 37]. Both the open source BIM standard of industrial foundation class (IFC) [38, 39, 40] and Web GIS formats (including LandXML [39, 41], City Geography Markup Language (CityGML) [42, 43, 44, 45], and Keyhole Markup Language (KML) [1]) are based on XML. LandXML is mainly intended for enhancing interoperability of data utilization in the land development industry. The integration between IFC and CityGML is the most investigated approach for integrated information modeling of buildings [43]. Majority of the works have attempted to covert semantically rich IFC models to CityGML models by taking advantage of the capability of GIS to handle huge datasets with a server-based approach [34, 43]. Earlier works [43, 44, 46] in this area focused on the conversion of geometric models. Ensuing research endeavors were intended to improve the conversion of semantic information [45, 47] using semantic mapping [42, 47, 48, 49] and ontology [42, 48].

The integration of BIM and CityGML provides an effective means to manage indoor building information and outdoor environmental information. However, it lacks the functionality to support AR modeling based on site photos or videos. In contrast, KML—which represents a markup language specialized for data modeling in Google Earth—focuses on data integration and visualization. It provides various data models to support advanced visualization techniques including AR. In [50], KML was used to visualize building energy simulation results integrated with BIM. Another related endeavor [1] proposed the use of KML and Google Earth to generate a cost-effective site information management platform which integrated site photos, 3D models, and the building environment.

In this chapter, we introduce an augmented GIS system called GoogleEarthWork—which is conceptualized from an academia-industry joint research endeavor and prototyped by taking advantage of KML and Google Earth for managing and visualizing heterogeneous site information in support of proactive project planning and control in the particular application context of rough grading earthwork construction. GoogleEarthWork focuses on the integration of 3D models, aerial and ground images, panoramas, and GIS data of the site environment that are commonly used for earthwork construction planning. Such datasets are seamlessly synthesized to facilitate the identification of quantitative and qualitative constraints in earthwork construction planning through applying computer vision techniques. Further, GoogleEarthWork runs on an automated earthwork planner engine program, leading to the generation of an optimized earthwork execution plan.

2. GIS-based site information management and visualization

Google Earth has been widely used by scientists and relevant stakeholders in addressing environmental and construction planning issues thanks to its ubiquity and rich geographic information. Diversified geographical information is presented to the user through a combination of digital elevation models, satellite imagery, 3D building models, street views, and user-uploaded images. Features such as tiling and level of detail (LOD) for images and 3D models enable Google Earth to manage large datasets with ease and efficiency, eclipsing majority of BIM software. Besides, KML enriches the extensibility of Google Earth significantly by providing users a standardized language to add data and customize analyses. With temporal and spatial information associated with each object, Google Earth enables efficient information retrieval through content navigation, 3D exploration, and time window filtering.

The GoogleEarthWork—which is prototyped based on Google Earth using KML—seamlessly integrates information contained in unordered images, geometric models, and 3D GIS system. As presented in Figure 1, the system encompasses data collection, data processing, data management, and information visualization and distribution. Aerial and ground imageries of the construction site captured with unmanned aerial vehicles (UAVs) and mobile devices are selected as major data sources for actual site monitoring and modeling. As-planned models and project schedules provide main data sources to build a virtual construction process. In addition, the 3D environment construction environment is reproduced in the visualization system. Subsequent to data acquisition, images and models need to be processed such that they are compatible with KML. Models are divided into parts in order to denote distinct construction stages in line with construction schedule.

Figure 1.

GoogleEarthWork for earthwork construction planning.

Photogrammetry algorithms are also used in order to align unordered images within the WGS84 coordinate system adopted in Google Earth. Panoramic views and 3D reconstruction of the construction site are produced to facilitate a better comprehension of the construction environment. The resulting 3D point cloud captures the geometry of the construction site and is thereby used for cut/fill volume takeoff, as well as measuring the hauling distance between two areas. As-planned models are converted in the KML format and time-stamped in order to visualize the construction progress. The system provides stakeholders with a visually intuitive platform to perceive the construction site and identify potential problems such as spatial limits in connection with site accesses and site layouts through integrated information visualization. By storing data on the cloud, KML enables efficient management of large volumes of data in images and models. Sharing KML documents of limited size instead of original datasets also streamlines information distribution and improves computing efficiency performances.

2.1 Data collection and preprocessing

Google Earth provides project managers with free high-resolution satellite images and topographic information of the environment around a construction site. Such information is essential to plan for site accesses, site layouts, and traffic flows. As-planned information in 2D/3D drawings is crucial for scope definition, quantity takeoff, and progress monitoring. For earthwork projects specifically, the as-designed surface is required to take off cut/fill volumes. Besides, the structures being built also affect site accessibility and traffic flows.

For as-built information, site photos have been widely used on a construction site for updating construction progress and reporting safety issues or other problems. However, images collected by different personnel are barely reused due to lack of efficient image management tools. It is desirable to automatically organize images with locations in a GIS system, but the positioning accuracy of mobile devices is inadequate for two main reasons, namely, (1) low-end localization sensors embedded in mobile devices and (2) multipath effect of radio frequency signals. In general, the camera pose obtained from a consumer-grade mobile device does not satisfy the need for geo-referencing and AR applications. Higher positioning accuracy can be obtained from aerial images taken by UAV due to high-grade localization sensors embedded and lessened multipath effects. After bundle adjustment [51], the camera pose can be further improved. By taking the optimized geo-location of aerial images as references, ground imageries can also be precisely aligned in the physical coordinate system. In addition, 3D reconstruction from images is instrumental in quantifying cut/fill volumes of earthmoving jobs and fixing distances and slopes of haul roads in earthwork construction planning. Most recent research endeavors [52] have demonstrated the cost-effectiveness of UAV photogrammetry for earthwork volume estimation.

Structure from motion (SfM) [53] has been well studied in photogrammetry and computer vision domains to reconstruct the 3D structure of the scene from image collections and to recover the pose of these images. Taking unordered images as inputs, SfM outputs the precise image position and orientation, plus 3D reconstruction of the site as point cloud or model. Besides, high-resolution panoramas stitched from aerial photos are cost-effective substitutes for outdated low-resolution satellite images. As an incremental approach, SfM is suitable for processing construction site photos collected on an irregular basis along the time line. However, it requires redundant images in order to ensure “realism” of the scene. This is usually not assured when ground photos are taken by different personnel on a construction site. Therefore aerial images taken by UAV are used to materialize connecting and aligning scattered ground images. With a sequence of imageries taken on the construction site, the system implements the SfM procedure, starting from the first aerial imagery and taking it as the reference in subsequent processing of images taken by cell phones on the ground.

The direct output of SfM includes the camera pose and a 3D point cloud of the object. A much denser 3D reconstruction of the object can be achieved using stereo matching subject to coplanar constraints [54]. To visualize the 3D reconstruction in GoogleEarthWork, a mesh model of the object is also produced. Further, panoramic images are generated by projecting original aerial photos onto the mesh model. An example is given in the subsequent section.

2.2 Information integration with KML

Based on XML, KML uses a tag-based structure with nested elements to manage data and information associated with an object in a hierarchical manner. Different from CityGML which is designed to represent geometric objects, the strength of KML lies in visualization on a web-based GIS platform. It defines basic elements to represent geometric objects, raster images, as well as their visual effects. Elements predefined in KML are divided into several categories according to their functionality: Feature for vector and raster geo-data, Geometry for 3D objects, AbstractView for navigation, TimePrimitive for date and time, and others for visualization style, LOD, and so on. As for GIS, geo-referencing elements are the most important for defining one object. Each object needs to be geo-referenced by <Location > and < Orientation > elements. A < Scaling > element is also available if scaling is necessary. The detailed information can be found through the KML reference; those elements intensively used in this research are listed in Table 3.

Element	Function	Objects
<Model>	3D model representation and visualization	3D models
<GroundOverlay>	Raster data alignment and overlay on Google Earth terrain	Panoramic mosaics
<PhotoOverlay>	Image placement and orientation for AR visualization	Original images
<Camera>	Camera position and orientation for AR and navigation	Image pose
<TimeStamp>; <TimeSpan>	Associate date/time for 4D exploration of objects and activities	Schedule
<ExtendedData>	Customized data organization and visualization	Documents, webs, et al.

Table 3.

Intensively used KML elements in GoogleEarthWork.

Objects defined with elements in the Feature category are listed on the navigation panel of the Google Earth interface for interactive selection. These elements include <GroundOverlay> and <PhotoOverlay> for images, as well as <Placemark>, <NetworkLink> for geometries and models. <GroundOverlay> elements are used to align satellite images or panoramic images over the 3D terrain model. <PhotoOverlay> elements are capable to align normal images with the 3D environment for AR visualization. A 3D model can be placed under <Placemark> or <NetworkLink> elements. Geometric objects can be represented either with primary basic shapes predefined in KML or hyperlinks of models in KML files or XML-based COLLADA files [55]. <Folder> and <Document> are elements that can be used repetitively to efficiently organize hierarchical contents.

Aerial images (which are taken by UAV) provide a unique view angle of the construction site with fewer obstacles. Besides, these images can be taken on a periodical basis to capture updates and progress on site. The stitched panoramic image has much higher resolution than satellite images available in Google Earth. The <GroundOverlay> element can be applied to replace the outdated lower resolution satellite image with high-resolution mosaics made of most recent images. To support real-time visualization, large panoramic images are preprocessed and managed with special elements designated for visualization in different levels of detail.

On a construction site, ground imageries are usually taken at “random” locations and angles. Consequently, they are fragmented in nature and only used as evidence shown in documents in practice. However, by aligning the image at the exact location and orientation in relation to 3D models and the site environment, fragmented information provided by individual images can be well organized and seamlessly integrated. Different from real-time AR technologies which demand considerable computing resources and remain too expensive to implement on site, the <PhotoOverlay> element in KML affords a pragmatic approach for realizing cost-effective AR experiences and efficient site photo management. Each <PhotoOverlay> object is defined by (1) a <Camera> element specifying the position and orientation of the image, (2) a <ViewVolume> specifying the field of view (FOV) of the image, (3) a <Icon> element to store the link to the image, and (4) an optional <TimeStamp> element stating the date when the image is captured. Given the rotation angles of the camera (omega, phi, and kappa) obtained from photogrammetry software, the heading, tilt, and roll can be derived with equations presented in [1]. The view volume of the image can also be derived from the estimated focal length and the image size. The image capturing date and time can be readily extracted from the header of the image file; thereby, a time stamp can be added to each image to show actual progress. This also enables retrieval and viewing of images only relevant to a particular time frame.

An example of information integration in GoogleEarthWork through using KML is presented in Figure 2; ground images captured with cell phones and digital cameras, aerial images collected using UAVs, and 3D models are embedded in the Google Earth platform so that the surrounding environment of the construction site is also rendered in a cost-effective fashion.

Figure 2.

Integrated project data management and visualization.

2.3 Constraints identification in earthwork planning

Analytical simulation or optimization for construction operations planning requires knowledge of practical constraints on the construction site so as to make a sufficient problem definition. In rough grading, a certain volume of earth needs to be excavated at one area and filled at another. Accessibility issues during project execution become the primary concern for earthwork construction planners, especially when only limited accesses between site areas are available at the very beginning of the project. Moreover, earthmoving operations need to be executed in a safe, efficient manner, accommodating many concurring construction activities on site.

These site constraints can be categorized into quantitative constraints and qualitative constraints, as listed in Table 4. A quantitative constraint can be defined with a number; by contrast, qualitative constraints cannot be quantitatively represented in GoogleEarthWork. The two basic constraints in earthwork construction planning are (1) cut/fill volume takeoff and assignment and (2) site accessibility and haul path planning. Besides, in order to improve project performance in terms of cost and duration, a solid plan needs to consider more factors. For instance, swell/shrinkage factors account for earth volume changes during excavation and compaction. These factors have a direct impact on quantity takeoff. The haul distance, road surface condition, and slope impact earthmoving productivity. Site layout design and concurring construction activities also potentially introduce spatial constraints. For example, certain areas on site are reserved for trenching and utility installation, hence remain temporarily unpassable to trucks in earthmoving.

Quantitative constraints	Qualitative constraints
Cut/fill volume for each area Soil swell/shrinkage factors Traveling distance/time between areas Unit cost	Access to/on the site Site layout from the design Other construction activities Road condition

Table 4.

Typical quantitative and qualitative constraints for earthwork projects.

GoogleEarthWork assists project planners in identifying abovementioned constraints more efficiently through information integration and visualization. Among them, cut/fill volumes can be readily acquired from a dense 3D reconstruction of the construction site. The slope of the terrain can be evaluated based on the 3D reconstruction if necessary. For instance, in Figure 3, the volume of the stockpiles can be precisely estimated from 3D reconstruction using Pix4D as presented in Figure 3(a). The relative positioning accuracy is evaluated using the width of the paved road in front of the house. The average width out of 20 measurements is 8.008 m. Detailed measurements can be found in Figure 3(b). Compared with the actual width 8 m, the average error is about 8 mm, and the standard deviation is around 29 mm. Note, the absolute positioning accuracy was not evaluated in this research due to unavailability of ground truth references. Nonetheless, the visualization effect of GoogleEarthWork proves that positioning accuracy is sufficient and acceptable for construction planning and monitoring purposes.

Figure 3.

GoogleEarthWork features demonstration: (a) earth volume survey from automated 3D reconstruction and (b) relative positioning accuracy evaluation.

Obviously, site photos provide valuable information to identify qualitative constraints. The accessibility issues, site layout constraints, and road conditions can also be assessed with high-resolution panoramic images and/or ground photos on computer. As these images are geo-located, GoogleEarthWork enables rapid identification of constraints at a particular spot. From Figure 4, it is straightforward to define one access road (pattern fill), four storage areas (solid lines), and three stockpiles (dashed lines) on the construction site directly from high-resolution panoramic image overlay.

Figure 4.

Qualitative constraints identification in GoogleEarthWork: geo-relationship between accesses, stockpiles, storage area, and the building identified from high-resolution panoramic images stitched from aerial photos.

3. Earthwork optimization and planning

Given identified quantitative and qualitative constraints, the analytical method presented in [56, 57] will be introduced for automated earthwork construction planning. This method provides an analytical approach to plan rough grading operations while making problem formulation and modeling more intuitive and simplified by the use of material flow networks. To a certain extent, it can potentially eliminate temporal-spatial conflicts (such as trucks are not allowed to haul on ungraded areas) in generation of an optimized yet more practically feasible work plan. The two-phase approach splits earthwork optimization and earthwork planning into two distinct, logically connected problems. The two problems were commonly combined in previous methods; thus representing time-dependent constraints such as temporal-spatial conflicts in field operations would result in overcomplicated mathematical models which had reduced application values of the developed models in reality.

The architecture of the two-phase approach is illustrated in Figure 5. At the bottom, an earthwork optimizer based on a material flow network is developed to optimize earthwork operations subject to identified quantitative and qualitative constraints. The optimization result is then taken as the primary input for ensuing analysis by the earthwork planner, which generates haul jobs, defines inter-job relationships, and produces the project network model for project scheduling and control.

Figure 5.

Scheme for embedding automated earthwork planning system in GoogleEarthWork.

3.1 Earthwork optimizer

The earthwork optimizer in GoogleEarthWork (Figure 6) models site constraints and earthwork operations with a flow network model. Those quantitative constraints are defined as attributes associated with nodes, while qualitative constraints are represented in the network structure as follow: To establish such a model, the construction site is first divided into cells. For simplicity, the site can be divided into regular square cells. The links between cells can be derived directly by connecting a cell with its neighbor cells sharing four common edges. The division of the site into cells needs to consider the design, the site layout, elevation changes, and accesses. For example, defining separate cells at a specific position is preferred if abrupt elevation change occurs, thus resulting in definition of irregular cells. Occasionally, treating a particular site area as one node is preferable if it has limited access. In short, the identification of these problems requires integration of information on design, actual construction site, and the surrounding environment. Once the site has been digitized into a cell model, the next step is to establish the flow network model incorporating various quantitative and qualitative constraints.

Figure 6.

Flow network model for earthwork optimization and state presentation in GoogleEarthWork. (a) Typical constraints on a construction site, (b) quantitative constraints and qualitative constraints modeled as attributes and network structure, respectively, and (c) optimized earth flow network used to represent the state of the system.

Prior to delving into the core of the earthwork optimizer in GoogleEarthWork, several important concepts need to be clarified. A graph model $G=\left(V,E\right)$ is made of a set of vertices V and a set of edges E which defines the connectivity between the vertices. Given a list of vertices $V=\left\{v_1,v_2,\cdots ,v_i,\cdots ,v_j,\cdots ,v_n\right\}$ , an edge between vertex $u\in V$ and vertex $v\in V$ is defined as $\left(u,v\right)$ . For a directed graph, edge $\left(u,v\right)$ and edge $\left(v,u\right)$ represent reversed directions. A flow network is defined as follows based on the directed graph:

A flow network is a directed graph, where each vertex is assigned with a demand $d\left(v\right)$ and each edge $\left(u,v\right)$ is assigned with a capacity $c_{\mathit{uv}}>0$ , a unit cost $a_{\mathit{uv}}$ , and a flow $x_{\mathit{uv}}$ .

The demand is the amount of flow that is required by this vertex. If $d>0$ , the vertex is demanding material to flow in. It is also called a sink node. On the contrary, it is a supplying vertex also named as source node if $d<0$ . Otherwise, the vertex will be a transshipment node with $d=0$ . The capacity $c_{\mathit{uv}}$ indicates the maximum flow allowed on each edge. The cost $a_{\mathit{uv}}$ is the unit cost to transport each flow unit through individual edges, respectively. The flow $x_{\mathit{uv}}$ specifies the amount of flow on each edge.

The total cost of a flow network is defined as:

$$h\left(\mathbf{x}\right)=\sum _{\left(u,v\right)\in E}{a}_{\mathit{uv}}{x}_{\mathit{uv}}$$ E1

where $\mathbf{x}=\left\{x_{\mathit{uv}}|\left(u,v\right)\in E\right\}$ represents the flow variables indicating the amount of flow on an edge. The optimal flow ${\mathbf{x}}_{\min }$ can be found by applying the minimum-cost flow algorithms [58] which minimize the cost function defined in Eq. (2) subject to capacity constraints and balance constraints defined in Eq. (3) and Eq. (4), respectively:

$$0\le x_{\mathit{uv}}\le c_{\mathit{uv}}\text{for}\mathrm{all}\left(u,v\right)\in E$$ E2

$$\sum _{\left(u,v\right)\in E}{x}_{\mathit{uv}}-\sum _{\left(v,w\right)\in E}{x}_{\mathit{vw}}=d_v\text{for}\mathrm{all}v\in N$$ E3

Traditional methods model haul jobs directly by adding links only between cut and fill cells. These methods require predefined hauling paths which may not be explicitly specified in earthwork planning, as hauling paths can be included as variables to be optimized in addition to earth volume assignment variables between cut and fill cells. In [56], a new method is introduced to deal with the issue without increasing the complexity of problem formulation. In contrast to linking cut cells to fill cells directly, this method links neighbor cells irrespective of whether they are cut or fill cells, while the exact hauling path for each haul job will be fixed by optimization along with the source cell (cut), the destination cell (fill), and the volume to handle for each haul job.

The quantitative constraints such as cut/fill volumes and the traveling speed are directly modeled as the demand $d_v$ for each node and the unit cost $a_{\mathit{uv}}$ for each edge, respectively. The capacity of flow on an edge is typically unlimited unless there is a special need, for example, to limit the total amount moved to a storage area. The qualitative constraints are modeled implicitly in the network structure. They are embedded by adding or removing specific arcs at specific directions. In the following subsections, we will elaborate typical site constraints for earthwork including accessibility, reserved areas, and haul road conditions.

Accessibility constraints: Site accessibility constraints are the most common on a construction site. The access between cells may be blocked by waterways, ponds, other facilities, and so on. Prohibiting moving material from one cell to another may be justified in certain areas in order to ensure traffic safety and provide adequate space for other construction activities. This can be imposed by removing certain directional arcs between cells in the site grid model in order to moderate earth flows.

Reserved area constraints: Reserved areas for temporary facilities, such as fuel stations, parking yards, and rest areas, require grading as well, but trucks generally are not allowed to pass through these areas once the temporary facilities are established. They can be treated as special cases of accessibility constraints. Taking the example presented in Figure 8, the site is divided into regular cells. Among them, cell 3 and cell 5 cover the area where a structure is being built. After the excavation in this area, there will be a substantial elevation change. Passing through this area is thus not allowed. Considering this area is a net cut area (the total demand is negative); only material flows leaving this area (red dash rectangle) are permitted. Similarly, only material flows entering an area are allowed if this area is a net fill area.

Haul road condition constraints: It is noteworthy that the truck hauling speed on rough ground and treated ground varies significantly. In the flow network model, haul road conditions can be modeled by adjusting the unit cost $a_{\mathit{uv}}$ of particular edges which represent haul road sections in the flow network. Shortening total project duration is the objective in construction planning in general. Thus, the traveling time can be used to directly model the cost.

Once the model is established, it is optimized with established minimum-cost flow algorithms [59]. As a result, the earthwork optimizer produces a flow network that defines the amount of flows (defined by $\mathbf{x}$ ) between adjacent cells. Because it does not model haul jobs directly, the result cannot produce the final execution plan which defines each haul job in terms of source, destination, volume, and haul path. Next, the earthwork planner is introduced which generates the final execution plan based on the optimized earth flow network.

3.2 Earthwork planner

The optimized earth flow network specifies quantity and direction to move material along inter-cell edges (haul roads) in the site system. However, temporal or spatial constraints arising from sequencing earthmoving jobs can be missed in this representation. At the beginning of earthwork operations, only limited accessibility is available. Access to an area is enabled in the middle of the earthmoving process once its neighbor areas are graded. Thus an additional network is required to define the accessibility between areas considering the progress of the project over time. In the remainder of this chapter, the optimized earth flow network is denoted as $G_{\mathit{op}}$ , and the network to represent the accessibility is named as $G_{\mathit{ac}}$ .

In this step, the classical planning model in automated planning theory is adopted for earthwork project planning in GoogleEarthWork. The state transition system for the earthwork planner is defined with a triple $\sum =\left(\mathbf{S},\mathbf{{\rm A}},\mathbf{\gamma }\right)$ , where.

$\mathbf{S}$ is defined with a tuple of two directed graphs $\left(G_{\mathit{ac}},G_{\mathit{op}}\right)$ , where $G_{\mathit{op}}$ is the optimal earth flow network and $G_{\mathit{ac}}$ is a directed graph representing the accessibility between cells.

$\mathbf{{\rm A}}$ is the action space defined as haul jobs. Each haul job can be represented with $\left(\mathit{WF}=\left(\mathit{Cut},\mathit{\text{Fill}}\right),P,V\right)$ which specifies the cut and fill cells, together with the volume V and the hauling path P. For example, a haul job $\left(\mathit{WF}=\left(\mathit{Cut},\mathit{\text{Fill}}\right),P,V\right)$ indicates 20 units of material which are transported from Cell 1 to Cell 2 passing through Cell 3 and Cell 4.

$y$ is a map from $S\times A$ to $S$ where the optimal earth flow network and the accessibility are updated after performing an action (i.e., completing a haul job.) This includes the following:

1. Updating the volumes of each cell on $G_{\mathit{op}}$

2. Updating the flow between adjacent cells on $G_{\mathit{ac}}$

3. Updating accessibility on $G_{\mathit{ac}}$ after some cells are graded

In the classical planning model, actions are sequentially taken by selecting an action and updating the state as presented in Figure 7. The procedure consists of four steps with the first three steps corresponding to deliberation functions and the fourth step corresponding to state transition functions. Because actions are required to satisfy all material flow constraints (flow direction and flow quantity on each edge), which are already determined in the optimized flow network, the final plan is extracted from a searching space that is already optimized. The detailed explanation of the planner can be found in [56, 57].

Figure 7.

The procedure of the earthwork planner. The deliberation functions include a cut/fill cell selection module and a haul job generation model.

4. Case study

In this section a campground grading project located in Northern Alberta, Canada, is used to demonstrate the application of earthwork optimization and automated planner functions. The size of the campground is around 2000 m long and 650 m wide. The total volume of material to be handled is 584,308 bank cubic meters ( $\mathit{bcm}$ ). The site layout is presented in Figure 8 with color bands denoting deep excavation (>3 m), medium height excavation (1.5–3 m), shallow excavation (<1.5 m), shallow fill (<1.5 m), and medium-depth fill (1.5–3 m). On the west side and east side, respectively, there are two storm water storage ponds, which also provide the two primary sources for fill material in site grading. Note during construction, only limited access to the two ponds is allowed. Pond 1 has one access point on its east side; Pond 2 has two access points on its north and west sides, respectively.

Figure 8.

Rough grading construction site: drawing and layouts.

A temporary haul road aligned with a future permanent road is established to facilitate the earthmoving process. Average truck speed differs when a truck hauls on the temporary road or the rough-graded ground. A fleet consisting of a 40 T excavator with a production rate of 190 $\mathit{bcm}$ per day and CAT 740B trucks with 20 $\mathit{bcm}$ volume capacity are employed on this project. The combined loading, dumping, and waiting time is assumed to be 20 minutes. The truck hauling speed limit, irrespective of truck haul (full) and truck return (empty), is averaged at 27 km/h on temporary haul road and $18\mathrm{km}/\mathrm{h}$ on rough ground, respectively. Besides, hourly rates of the excavator and the truck are $140/\mathit{hr}$ and $135/\mathit{hr}$ . The hourly rate for an equipment operator is around $60/\mathit{hr}$ regardless of the type of the equipment.

The construction site is divided into cells (100 m × 100 m) for material flow network optimization and AON network development. The cell size is defined by the user after assessing site topology and application need. Mathematically, the smaller the cell size, the more accurate the result would be. However, too small cell size is not suitable for current application of earthwork planning and construction management. Four times the truck width is recommended as cell dimension for planning mining haul road, which was used for earthwork planning in GoogleEarthWork due to safety concerns [60]. To incorporate the two ponds in the flow network model, irregular shaped cells instead of squared cells are used for representing the ponds, their neighboring areas, and the boundaries. In this case, Pond 1 is treated as one cell node, and Pond 2 is divided into two cell nodes. Single-directional arcs flowing out of pond cells are defined so to avoid trucks passing through the ponds. The traveling time per truckload between adjacent cells is defined as the unit cost of hauling in optimization analysis. The final flow network definition is presented in Figure 9.

Figure 9.

Flow network model for the case study. Two ponds are split into irregular cells.

The earthwork Optimizer and the earthwork Planner in connection with GoogleEarthWork were implemented based on the open source Library for Efficient Modeling and Optimization in Networks (LEMON) graph algorithm library with its LGF file format denoting flow network definition [61]. Taking the flow network model as input, an optimized earth flow network was obtained as the result of minimum-cost flow optimization. Next, eight sub-flows were identified from the optimized earth flow network based on weakly connected component analysis. In the end, a total of 129 jobs were generated. The proposed system not only enables automated project planning but also automated project network analysis and resource-loaded scheduling simulation analysis. Once the work breakdown structure and the project network are produced, they can be readily used to perform scheduling and cost analysis with existing tools. Based on the automated planner, the cost and duration were estimated to be $3,491,632 and 149 work days, respectively.

5. Conclusion

In this chapter, we conceptualize an augmented GIS system called GoogleEarthWork for earthwork planning based on Google Earth and demonstrate great potential in site information management and visualization, especially the integration of site photos, 3D models, and 3D surrounding environment of the construction site. The system is capable of facilitating the identification of (1) quantitative constraints by image-based 3D reconstruction and (2) qualitative constraints through interactive VR and AR visual inspection within Google Earth. Coupled with an automated earthwork planning system, GoogleEarthWork holds the potential to provide an integrated project planning solution that assists project managers in information collection, data analysis, and construction planning. It also enables higher-level project management analyses such as scheduling and simulation by automatically generating project execution plans (e.g., AON network model). The results provide project managers with a sufficient basis for the development of a practical, dynamic plan. As construction unfolds and the site evolves over time, additional constraints can be further imposed in order to keep the plan up to date.

At present, application of GoogleEarthWork is confined to rough grading earthwork construction. In the future, the system along with its underlying methodology can be customized for other application domains. More importantly, a formal definition of the GoogleEarthWork application framework allows the representation of domain knowledge and facilitates the implementation of advanced planning techniques (such as resource-constrained scheduling optimization or operations simulation) in the specific application domain. This will ultimately result in optimized construction plans for performance improvement in field productivity and safety. Though automated tools have been proposed for site information processing, human interactions still remain crucial in site constraint identification and planning problem definition in reality. A comprehensive information system that assists project managers in updating site constraints through site information integration and visualization is thus indispensable to refining problem definitions and identifying practical constraints. In the near future, GoogleEarthWork will be further augmented with advanced quantitative methods and emerging AI techniques.

Acknowledgments

This research was substantially funded by Mitacs Canada and Ledcor Canada through a Mitacs Accelerate Internship grant (Project ID: IT06594). The authors sincerely acknowledge Sam Johnson, Senior Construction Manager of Graham Construction Canada, for sharing information and insight on earthwork planning and Dr. Eric Loo, the Director of Business Development of Mitacs for facilitating the research.