- Email: [email protected]

Contents lists available at ScienceDirect

Mechatronics journal homepage: www.elsevier.com/locate/mechatronics

Path planning for autonomous bulldozers Masami Hirayama a,b,∗, Jose Guivant a, Jayantha Katupitiya a, Mark Whitty a a b

School of Mechanical and Manufacturing Engineering, University of New South Wales, Sydney, NSW 2052, Australia Komatsu Limited, 2-3-6, Akasaka, Minato-ku, Tokyo 107-8414, Japan

a r t i c l e

i n f o

Keywords: Path planning Autonomous bulldozers

a b s t r a c t Komatsu Ltd. is reinforcing the R&D of automation technology for our earth-movers. Based on this trend, a path planning methodology for autonomous bulldozers is proposed and developed. This methodology autonomously plans an eﬃcient path depending on a given material proﬁle. Conventionally, existing path planning algorithms are versatile so they can be applied to any application, typically by using a grid-based map. However, in reality, a substantial eﬀort is still required when applying to speciﬁc industry products. In contrast to this trend, the aim of this work is to develop a path planning algorithm speciﬁcally suitable for bulldozers, from the theory development phase. The novel planning methodology was developed by incorporating industry feedback, and has successfully resolved the issues which occurred when attempting to apply the existing planning methodologies. As a result of this work, the developed methodology provides an eﬃcient path that lets bulldozers complete given tasks with minimal operation time, without a human operator on-board, and can be applied to commercial machines immediately.

1. Introduction 1.1. Background and scope As demand and awareness from industries for safety improvement, higher productivity, and more eﬃcient vehicle utilization are increasing, coupled with a labor shortage issue, the signiﬁcance of automating mining vehicles is rapidly advancing. Among diﬀerent types of operations carried out at mining sites, one of the most important processes is the dumping area operation. This type of operation is exercised to restore the site to a certain required state after the main operation of mineral extraction [1–4]. In fact, the cost related to dumping area operation is one of the largest components of the mining operation, that can account for up to 50% of the total operational costs [5]. Due to this reason, when automating mining vehicles, dumping area operation is one of the most important key elements that requires a substantial research eﬀort. Focusing on this fact, the aim of this paper is to develop a system that enables bulldozers to autonomously complete the tasks required for dumping area operations. A typical dumping area operation, edge dumping, is shown in Fig. 1. Dump trucks transport waste material from other parts of the site over the edge of the dumping area [6–8]. The purpose of the dumping area operation is to backﬁll the mined area to restore the site to a certain required state. This is done by increasing the width of dumping area as shown in Fig. 1. In particular, waste material needs to be pushed past

∗

the edge of the dumping area, and bulldozers are typically used for this purpose. Hence, this paper focuses on automating such an operation. Fig. 2 shows the speciﬁc scenario to be achieved in this paper. The task given to the bulldozer in this scenario is to remove the waste material autonomously. Most of the time, the material volume exceeds the bulldozers’ blade capacity, therefore an eﬃcient path that lets bulldozers cut and move the material eﬃciently using multiple pushes needs to be planned. The blue lines in Fig. 2 represents a conceptual example of an eﬃcient path for autonomous bulldozers. Automating bulldozers means there are no operators on-board who could manually steer to remove the waste material, hence this sort of path needs to be planned autonomously based on the perceived location and volume of terrain. This paper will predominantly deal with the development itself of such path planning, and will not deal with a comparison between an optimized path and a path exercised in the current manual operation. This is based on two reasons. One reason is that, as will be mentioned in Section 1.3 as an identiﬁed problem, there is currently no path planning methodology which can be immediately applied to bulldozers, therefore developing such planning methodology itself is novel. Another reason is the limitation of obtaining reliable path data from the current industrial scenario. In actual scenarios at mining sites, the terrain is basically constantly changing, hence it is not quite feasible to obtain data that the can be used to do such comparisons. For these reasons, this paper will not discuss the improvement of a path derived from the proposed methodology, compared to a manual operation path, but predominantly focuses

Corresponding author at: School of Mechanical and Manufacturing Engineering, University of New South Wales, Sydney, NSW 2052, Australia. E-mail address: [email protected] (M. Hirayama).

https://doi.org/10.1016/j.mechatronics.2019.01.001 Received 21 March 2018; Received in revised form 18 December 2018; Accepted 4 January 2019 0957-4158/© 2019 Elsevier Ltd. All rights reserved.

M. Hirayama, J. Guivant and J. Katupitiya et al.

Mechatronics 58 (2019) 20–38

Fig. 3. Case 1. This is the scope of this paper.

Fig. 1. Top view of dumping area. Bulldozer’s operation involves pushing the material dumped by trucks past the dumping area edge. This paper focuses on automating this operation.

Fig. 4. Case 2. This is NOT the scope.

Fig. 5. Case 3. This is NOT the scope.

the scenario which can be often seen at actual mining sites is predominantly Case 1. From the perspective of bulldozers, Cases 2 and 3 are not preferable as they require complex operations, which result in a significant increase of the operation time. For this reason, since the dumping area itself at mining sites is large enough to avoid a Case 2 or 3 situation, with a suﬃcient deployment of dump trucks and bulldozers, Cases 2 and 3 rarely happen in real-life situations. Therefore, Case 1 scenario is the scope for this paper, which means no blade motion discussion is necessary, and what is required for autonomy implementation to bulldozers is predominantly path planning only. One of the most important elements in autonomy design is localization, however localization is not within the scope of this paper. This is because in the scenarios typically seen with mining bulldozers” operation, the localization problem is solved by using GPS in RTK mode. RTK (Real Time Kinematic) is a navigation technique to compensate the deﬁciency of conventional GPS technology. RTK not only enhances the precision of position data, but also provides the precision in a real-time fashion [10,11]. Taghia et al. demonstrated a high accuracy path tracking performance of an agricultural tractor using RTK-GPS [12]. RTK-GPS is actually an existing feature of some of the commercialized bulldozers, therefore localization itself will not be an issue for the bulldozers’ operation scenario. A highly beneﬁcial autonomous system should enable bulldozers to autonomously plan an eﬃcient path to push material based on any given material proﬁle, by only specifying the area which includes the material that needs to be removed. As opposed to the conventional operation where operators have to manually plan a path and control steering, the

Fig. 2. Autonomous bulldozers’ operation to be achieved at dumping area. Based on a given material proﬁle, bulldozers need to autonomously plan an efﬁcient path (blue lines) to remove waste material with minimal operation time. (For interpretation of the references to color in this ﬁgure legend, the reader is referred to the web version of this article.)

on the methodology development itself. However, this paper deals with a comparison of the two diﬀerent operation patterns, ‘Type1 - Side attack’ and ‘Type2 - Middle attack’. The details of these two operation patterns are presented in Section 2.2 “Two operation types’. In general, three diﬀerent cases can be considered for the A-A crosssectional diagram as in Fig. 2. Fig. 3 through 5 show those three cases. Case 1 shown in Fig. 3 shows the situation where the mound is small enough to be removed by one push of the bulldozer. Case 2 as in Fig. 4, shows the situation where the mound depth is substantial and can not be removed by one push, hence it requires a depth reduction path. Typically, in this case, the material is cut from the side closer to the dumping area edge towards the other side, one push after another. Case 3 in Fig. 5 shows the situation where, in addition to the condition in Case 2, the mound has a substantial height, hence it requires a height reduction path as well as a depth reduction path. Among these three cases, 21

M. Hirayama, J. Guivant and J. Katupitiya et al.

Mechatronics 58 (2019) 20–38

processing is primarily a volume and shape estimation of the piles of material, segmentation, and distribution of the segmented material. It is already known that terrain can be adequately represented by polygonal approximations [21–25]. Once a set of point cloud data that represents the material proﬁle is constructed, existing methodologies such as alpha shapes [26–29], or Delaunay triangulation [30–34] coupled with the convex hull [35,36] can be simply used to create an approximated polygon which immediately provides the volume value. However, a problem in applying these methodologies is, there is no formulation that best suits with the scenario considered in this paper. Therefore, a formulation to construct a set of point cloud data which can be eﬃciently used for bulldozers’ path planning is essentially a key element for terrain polygonal approximation in this case. 1.2.2. Path planning Although there is already a substantial number of diﬀerent path planning techniques developed in existing works, which will be presented in this subsection, none of them are straightforwardly capable of completing the bulldozers’ task. The typical scenario which can be often seen in existing works is basically an obstacle avoidance with pre-given start and goal points. Therefore, the major diﬀerences of bulldozers’ operation from those in the existing works can be identiﬁed as a necessity of dealing with the following two items:

Fig. 6. Autonomous system framework comprised of four modules (derived from [9]). The highlighted sections are dealt with in this paper.

• Material handling • Non-given start and goal points

proposed framework minimizes the manual input needed from operators to only designating the area of interest. In general, an autonomous navigation system should be composed of terrain mapping, path planning, and navigation [13–15]. An overall framework comprised of four modules for developing an optimized autonomous system, for the scenario considered in this paper, is shown in Fig. 6. As the sections dealt with in this paper are highlighted, this paper mainly focuses on terrain mapping, including post-processing, and path planning. Note that other modules have already been tested and the usefulness has been demonstrated by using a real bulldozer [16].

Firstly, as for material handling, assuming an obstacle avoidance scenario only, results in a planning methodology for the agent motion only. On the other hand in this paper, in addition to the motion of the agent (in this case, the agent is a bulldozer), material handling also needs to be considered for the bulldozers’ operation. What is meant by material handling is planning a path for bulldozers, using an eﬃcient order to cut the material. Simultaneously, the planner needs to consider many difference factors such as, the material volume to be cut by bulldozers each time, the eﬀect of the bulldozers’ velocity reduction due to the material volume, and the length of the path to take. The path in which bulldozers remove speciﬁed material with a minimal operation time needs to be derived taking into account all these factors. Secondly, as for start and goal points, pre-given points are a typical assumption in the existing works. However when planning a path for bulldozers’ operation, start and goal points are not given at the start of the operation, as those points depend on which path to take to cut the material. Creating start and goal points needs to be incorporated as a part of the planning process. Therefore, the major diﬀerences of this paper from other existing research is that material handling needs to be planned in addition to the agent motion, and start/goal point creation needs to be incorporated as a part of the planning. Among the many diﬀerent path planning techniques, three techniques are chosen to consider the path planning methodology for this research - metric path planning, sampling-based path planning, and topological path planning. The conceptual comparative overview is presented in Fig. 7. As a result of the literature review, it has been identiﬁed that there is no existing path planning methodology that can be straightforwardly applied to the scenario that is considered in this research. This fact is therefore the motivation for this research topic, and the literature review is followed by Section 1.3, describing this identiﬁed problem. As can be seen in Fig. 7, the major advantage of topological planning is a signiﬁcantly low computational cost. Compared to the other two types of planning (metric path planning, and sampling-based path planning) which have typical methods to be used for planning, it seems topological path planning does not have any speciﬁc methods typical for this type of planning. Alternatively, methods used for other types of planning such as A∗ or RRT are adjusted to be used [37,38]. Although the path that can be obtained from this methodology is not as eﬃcient

1.2. Literature review This section describes what aspects of terrain mapping and path planning are distinct from existing relevant works, and why research eﬀort is required for the aim of this paper, respectively. 1.2.1. Terrain mapping Terrain mapping itself is a suﬃciently developed domain from existing works, however a conversion of raw data, as post-processing, is essential in order for the terrain information to be eﬃciently fed to the path planning process. This section ﬁrstly describes existing mapping approaches, and secondly describes a key element of post-processing in the case of the scenario considered in this paper. Firstly, as for terrain mapping sensing, 3D imagery needs to be obtained in some way, and there are predominantly two main options for this purpose - LIDAR [17,18], or RGB-D [19]. LIDAR is especially suitable for a harsh outdoor environment. This sensing approach coupled with SLAM was performed using a mining haul truck by Nebot et al. [20]. They demonstrated that LIDAR technology can survive in a harsh environment at a mining site where rain and dust cause unpredictable changes to the sensing environment. RGB-D is, in general, suitable for an indoor environment, and the cost of the sensor itself is relatively cheap. For this context, when applying the methodology developed in this paper to a real mining bulldozer in the future, LIDAR looks to be an appropriate sensing option. However, the environment of the experiment we consider speciﬁcally for this paper is an indoor laboratory, hence a RGB-D camera is used for convenience’s sake. Secondly, as for post-processing, the modeled terrain requires postprocessing before being fed to the path planning process. The post22

M. Hirayama, J. Guivant and J. Katupitiya et al.

Mechatronics 58 (2019) 20–38

Fig. 7. Conceptual comparative overview of existing path planning techniques. Parts shown in blue represent the map in each type, and an example solution path is shown with a red line. Topological path planning has an advantage with computational cost, however does not have particular typical methods (the highlighted section). Hence there are some attempts to extend existing search methods used for other planning types to topological planning, and this paper deals with the case for bulldozers’ operation in particular based on topological planning. (For interpretation of the references to color in this ﬁgure legend, the reader is referred to the web version of this article.)

as the other two types of planning (metric path planning, and samplingbased path planning) as can be seen in the conceptual graph shown in Fig. 7, the requirements and fundamental assumption which lie in this methodology suit suﬃciently with bulldozer operations. One example of applying path planning methodology to a mining vehicle can be seen in a work done by Alshaer et al. [39], and their methodology is based on topological planning. They focused on wheel loaders. The typical wheel loader operation is the repetition of a cycle of the vehicle taking material from the stockpile, and transporting it to a truck. Typically the amount of material at the stockpile is fairly large, and is not thought of as a moving object, considering the amount of material the machine can take each time with respect to the whole amount of material at the stockpile. Also, while the wheel loader is operating, the truck is usually stopped. Therefore, since the stockpile and the location of the truck are stationary, their scenario is a completely static environment with a given start and goal point. What should be learned from this literature is that the methodology applied in that paper can be classiﬁed as topological path planning. Again, topological planning has a signiﬁcant advantage in the computational cost, and this is very critical when including the prospect of applying it to actual commercial products. As mentioned in Fig. 7, the topological path consists of nodes and edges. In this case, the nodes are set to two static points, which are the stockpile and the location of the truck. The edges are created by using an existing curve algorithm such as the Reeds-Shepp curve [40,41], or Bezier curve [42]. When considering topological planning for the scenario supposed in this paper, a formulation for nodes and edges has to be a part of the methodology development. This is dealt with in more detail in Section 2.4.2. Automation has actually already been applied to some commercial wheel loaders [43]. The scenario where those commercial autonomous wheel loaders work is identical to the one in the work done by Alshaer et al. [39]. Thus, it can be adequately assumed that the planning methodology used for those commercial products is based on topologi-

cal planning. Another perspective to support this assumption is the advantage of computational cost, which is very critical when applying to a commercial level product. Therefore, with the perspective of an immediate implementation to commercial products, the approach taken in this existing work should be considered as a benchmark, and the path planning methodology for bulldozers should be developed based on topological planning. 1.3. Problem statement As a result of the literature review, the most signiﬁcant problem to discuss in this paper is that no path-planning methodology has yet been produced which achieves bulldozer operation. In particular, it is a path planning methodology to deal with non-given start and goal points, and material handling, along with the agent motion. 1.4. Objective and novel contributions The objective of this paper is to develop a path planning methodology particularly suitable for bulldozers. Unlike other path planning research, we will not aim to develop a generalized methodology that can be applied to any kind of application. The methodology to be developed in this paper will plan a path (blue lines in Fig. 2) to remove the waste material on the dumping area based on recognized variable terrain location and volume, with the aim of minimizing operation time. The optimization aim lies in a minimal operation time. As a result of completing this objective, below are novel contributions created from this paper. • Terrain mapping – An introduction of transition points to allow estimation of total operation time (Section 2.3.2) 23

M. Hirayama, J. Guivant and J. Katupitiya et al.

Mechatronics 58 (2019) 20–38

Fig. 8. Experimental scale dumping area operation. (For interpretation of the references to color in this ﬁgure, the reader is referred to the web version of this article.)

• Path planning – A method to topologically model the environment by incorporating key ideas about how to push material with bulldozers, which enables autonomous creation of subgoal points, and an eﬃcient path with low computational cost. (Section 2.4.2) – A method to derive a path from the material handling pattern planning (rather than direct planning of agent motion), which enables material handling pattern planning in addition to the agent motion. (Section 2.4.2) – A method to formulate the true cost and heuristic of A∗ based evaluation function, which enables autonomous efﬁcient path planning for pushing a maximized amount of material per push in the shortest time. (Section 2.4.2) – A comparison of two operation patterns that demonstrates how ‘Side attack’ is faster than ‘Middle attack’ from the perspective of operation time. (Section 4 - This is an empirical contribution.)

in Fig. 2, hence an eﬃcient path to remove the material needs to be autonomously created based on the perceived information about it. 2.2. Two operation types According to feedback from professional bulldozer operators, there are two diﬀerent operation patterns exercised in industry. Those two operation patterns are shown in Fig. 10. With Type 1, the material is simply taken from one side to the other without leaving windrows. On the other hand, with Type 2, ﬁrstly the bulldozer aims to take the material from the middle, so it has windrows to maximize the productivity [44,45], then clean the windrows at the end. As for the volume to be taken by the bulldozer, Type 1 allows the bulldozer to move a certain percentage under the blade capacity constantly, as it has to ensure there is no material spillage on the opposite side of the mound. Typically, professional bulldozer operators aim to take material up to 60% of the blade capacity. If bulldozers attempt to contain more than 60%, the material starts to spill out from the blade. Compared to that, Type 2 allows the bulldozer to take a lot more volume for the ﬁrst half of the operation, then very small amounts for the last half. The more material the bulldozer pushes, the slower the bulldozer’s velocity becomes. With this complicated science, the path planning methodology developed in this paper provides an eﬃcient path for bulldozers to remove a required amount of material in a faster operation time, based on these two basic operation types.

2. Developed method 2.1. Experimental scenario Fig. 8 shows a speciﬁc scenario to consider in an experimental scale, based on the scope described in Fig. 2. Terrain mapping is done by using the 3D scanning sensor mounted on-board of the scaled-down bulldozer. The area shown in blue in Fig. 8 is the range that can be perceived by the 3D scanning sensor. The following section includes how the material mound is represented with 3D point cloud data in Fig. 12, and how this raw data is approximated to polygon in Fig. 13. As already mentioned in Section 1.2.1, a RGB-D camera was used for convenience’s sake in this paper. As can be seen, the total volume of material exceeds the blade capacity, so the bulldozer has to plan a multiple number of pushes to move the material. A sequence of ﬁgures showing the bulldozer pushing material push by push, are also shown in Fig. 9. In this case, three pushes are required to remove the whole material volume, and the bulldozer pushes the material over the dumping area edge, by using a repetitive forward and backward motion. Given real-life practices exercised at mining sites, a dumping area edge is created at the equivalent of 3(m) past the material to make this lab environment test as similar to real mining scenarios as possible. At real mining sites, this distance is advised with respect to production eﬃciency and safety measurement. The following subsections describe developed methodology for terrain mapping and path planning, respectively, for this speciﬁc scenario (Fig. 8). As a result of these pushes, the material is moved past the dumping area edge from the original position. This is the desired scenario described

2.3. Terrain polygonal approximation The reason terrain polygonal approximation is essential is primarily for material volume calculation and shape estimation, as mentioned in Section 1.2.1. 2.3.1. Proposed procedure of terrain polygonal approximation Fig. 11 shows the proposed ﬂow chart of the polygonal approximation, and Fig. 12 shows a cross-sectional diagram of terrain data, illustrating how each process in Fig. 11 is applied to raw terrain data. The whole idea of the polygonal approximation proposed here, is to create 4 representative points per cross-section, with a set of cross-sections that cover the mound area as shown at View Z in Fig. 12. In this subsection, the step number in parenthesis indicates the corresponding step in the ﬂow chart shown in Fig. 11. Firstly, a line ﬁtting is applied to the ground level (Step 1). Once the line information is obtained within the region where the line ﬁtting is applied, the point which deviates the most from the line and its deviation distance is calculated as xf (Step 2). This deviation distance is used to identify the ramp start point. The system investigates the existence of any point of which the 24

M. Hirayama, J. Guivant and J. Katupitiya et al.

Mechatronics 58 (2019) 20–38

Fig. 9. A sequential snapshot of pushing material.

Table 1 Mound measurement assessment. Measurement

True

Accuracy

0.0138(m3 )

0.0125(m3 )

90.6 (%)

that an external mapping system such as an UAV is not necessary with this proposed methodology, and the planning is feasible with bulldozers having their own devices on-board. However, it is obvious that more accurate mound representation and volume calculation is possible if this system involves any external mapping system, which would eliminate the concern of blind spots. The point is, the proposed system in this paper suﬃciently works independently from an external mapping system, and discussion about optimal mapping system is not a focus of this paper. Note that, in the experiment performed in this paper, the terrain approximation was performed only at the start of the process. However, we recognize that a time-step approximation is essential when it comes to implementation to a real bulldozer. In this case, the planning process is performed periodically and repeatedly at a low frequency. Each time it is performed, it uses the most recently updated 3D mapping description, and the approximation is based on this newest 3D model to feed into the planner.

vertical position is larger than kxf (k can be an arbitrary number to adjust the threshold). If there is such a point, the existence of the ramp is valid in the cross-section (Step 3). In other words, any mound height lower than kxf is classiﬁed as a ﬂat plane. By using the ramp start point, another line ﬁtting is applied to the other point cloud which exists in the ramp region (Step 4). Once the line is created, the line is used with the ground line to identify the intersection point (Step 5). A transition point idea shown in part of Fig. 11, is introduced here, and this intersection is labeled as transition point T1. The details of this transition point idea are described in the following subsection. A ramp end point is created by ﬁnding a point which has the largest value for vertical position (Step 6). After the intersection and the ramp end point are identiﬁed, a symmetric point from the intersection is created, and this is labeled as transition point T2 (Step 7). This needs to be done only because the scanning sensor is assumed to be mounted on-board the bulldozers, and before planning a path, the bulldozers perceive one side of the mound. An idea to compensate this disadvantage is that the other side of the mound is assumed to be symmetric around a line that vertically descends straight down from the ramp end point. This process of creating 4 representative points is employed to each cross-section. This case is shown in View Z in Fig. 12. After that, when there are no more cross-sections regarding this process, the 4 representative points become representative points to approximate the mound. In this work, Alpha shapes are used to construct an approximated polygon [26–29], and the volume of this polygon is also provided by this methodology. Table 1 shows the comparison between the measurement and the true volume. In this case, the proposed methodology shows more than 90% accuracy. As the assumption of symmetric cross-section is employed, this means simultaneously

2.3.2. An introduction of transition point The point of introducing a transition point is to estimate the total operation time, as the optimization aim is to plan a path that allows bulldozers to remove the waste material in the shortest time. While the details of a theoretical modeling of operation time are presented in Section 3, this section primarily describes the transition point, which also ultimately supports the theoretical modeling of the total operation time. One beneﬁt of introducing the transition point is to know, what state of pushes the bulldozer is in at which place. When a bulldozer pushes material on a dumping area, there are basically 4 diﬀerent states, and the 4 diﬀerent discrete states are shown in Fig. 14. The reason the scenario is discretized is simply because the bulldozer’s velocity depends on which state the bulldozer is in. In State 1 (Approaching the material), the bulldozer travels towards the mound with a constant velocity. In State 2 (Engaged in pushing), the bulldozer starts to push the material, and the material’s volume increases as the bulldozer travels, hence the velocity changes accordingly. After State 2, in State 3 (Moving material to the edge), the bulldozer keeps pushing the material, however the 25

M. Hirayama, J. Guivant and J. Katupitiya et al.

Mechatronics 58 (2019) 20–38

Fig. 10. Two operation patterns. Table 2 Area and state correspondence. Area

State

P1-P2 P2-P3 P3-P4 P4-P5

State 1 (Const. velocity) State 2 (Variable velocity) State 3 (Const. velocity) State 4 (Const. velocity)

Fig. 11. Proposed ﬂow chart of polygonal approximation.

Approaching the material Engaged in pushing Moving to edge Reversing

• Push material in a straight line As soon as bulldozers start engaging in pushing material, it is most preferred not to steer while pushing. This is to prevent material spillage from the blade, as rehandling time increases if there is a spillage. • Traverse towards the edge in a perpendicular direction This is to ensure both tracks of bulldozers have full contact with the ground when dumping material over the dumping are edge (See Fig. 2). A slight angle tolerance can be allowed as long as bulldozers’ tracks stay on the ground.

volume is constant past transition point T2, hence the velocity is constant. At the end of State 3, the material is pushed past the dumping area edge. In State 4 (Reversing), the bulldozer reverses back to the start point for the next push. Note that a path for State 4 includes two way-points to turn, so that the bulldozer does not collide with the remaining material. In order to estimate the operation time, which is discussed in more detail in Section 3, the clariﬁcation of the velocity is essential. As mentioned, the velocity depends on which state the bulldozer is in, and by comparing the bulldozer’s position and the position of the 2 points labeled as ‘transition point’, this transition point idea helps us to understand what velocity the bulldozer is traveling with, and this will be used to calculate the total operation time eventually. Table 2 shows which state the bulldozer is in at which place, and its corresponding velocity types.

Fig. 15 shows how bulldozers should push material based on these two key ideas. Fig. 16 illustrates the problems expected to happen if the operation does not follow these two key ideas. The path shown in Fig. 16 shows one example of not following these two key ideas. Firstly, if the bulldozer steers while pushing, the material simply spills from the blade. This situation is shown in the middle diagram in Fig. 16. Secondly, if the bulldozer does not traverse in a perpendicular direction towards the dumping area edge, one of the tracks looses partial contact with the ground. The right hand side diagram in Fig. 16 illustrates this scenario. This leads to a reduction of traction power, hence it is preferred to avoid this scenario.

2.4. Path planning 2.4.1. Two key ideas to push material with bulldozers Regardless of whether manually-driven or autonomous, based on feedback from professional bulldozer operators, below shows two key ideas to be ensured when pushing material with bulldozers, for eﬃcient machine utilization. The two key ideas are incorporated into a part of the developed modeling, which the result of is presented in Section 4, so that a path will be optimized in accordance with this eﬃcient vehicle utilization manner.

2.4.2. Core concept of path planning for autonomous bulldozers As mentioned in Sections 1.2.2 and 1.3, the problems in applying typical path planning methodology in bulldozers’ operation are, goal points are not given, and material handling needs to be planned along with the agent motion. Goal points dominantly control a path for bulldozers to follow. Hence, when goal points are not given, basically, they can not 26

M. Hirayama, J. Guivant and J. Katupitiya et al.

Mechatronics 58 (2019) 20–38

Fig. 12. Cross-sectional diagram of terrain data. The numbers in the diagram correspond to the process numbers shown in the proposed ﬂow chart in Fig. 11.

Fig. 18 shows the topological modeling comparison between the proposed methodology and typical case. As mentioned in Fig. 7, when formulating with topological path planning, what need to be deﬁned are nodes and edges. In this proposed methodology, nodes are deﬁned as points along the dumping area edge, and edges are deﬁned as perpendicular lines from those nodes. A certain angle tolerance can also be considered for the edge line. In all the simulations in this paper, the angle tolerance is ± 15 degrees, and nodes are created every 0.5 m. This particular value was determined from the size of the material and the bulldozer’s blade width. Unlike typical cases where only one start point and one goal point are speciﬁed, in bulldozers’ operation, a set of way-points to tell the timing to switch between forward and reverse, also needs to be planned. This is because bulldozers need to repeat forward and backward motion to remove the waste material. Therefore some of the nodes deﬁned become the set of waypoints, and the others become start and goal points. Fig. 27 shows an example result of this point generation. As shown in Fig. 7, edges in typical topological path planning usually hold information about the route itself. However, in this proposed methodology, by incorporating the two key ideas of bulldozers’ operation, in addition to that information about the route itself, the proposed methodology also allows the edges to contain material amount information. The material amount can be calculated using simple geometry as an overlapping area, as shown in Fig. 18. Fig. 17 shows an example of a topologically discretized model for bulldozers’ operation. The second reason as previously mentioned, is simply a computational cost advantage, which is critically important when considering applying to a commercial level product, as mentioned in Section 1.2.2. By using the topologically discretized model, the search algorithm is developed based on A∗ algorithm. The standard A ∗ algorithm is one of the most widely-known planning algorithms, and is an informed search algorithm [46]. This means a solution path is searched out, provided that a start and a goal point are given. The algorithm is typically used in a grid-base maps with an occupancy grid [47] in metric path planning fashion (See also Fig. 7). However, the proposed methodology is

Fig. 13. Approximated polygon.

even be manually speciﬁed, as they have to be created as a part of path planning. In particular, with Fig. 2, the start and goal points simply can not be speciﬁed before planning a path. To address these two issues, this section presents the proposed methodology, and the novel formulation of the total cost, which are claimed as a novelty in Section 1.4. The proposed methodology is shown below. (See also Table 3) • Step 1: Model the scenario topologically (c.f. In a typical case, the model is a grid-base map.) • Step 2: Plan material handling pattern (c.f. In a typical case, the agent motion is planned) • Step 3: Derive path for bulldozers from material handling pattern The proposed methodology is based on topological planning for two main reasons - formulation suitability and computational cost. The importance of the computational cost was already mentioned as a part of the literature review (See Section 1.2.2), hence below describes formulation suitability. Formulation suitability is how easily the two key ideas of bulldozer operations (See Section 2.4.1) can be incorporated. 27

M. Hirayama, J. Guivant and J. Katupitiya et al.

Mechatronics 58 (2019) 20–38

Table 3 Comprehensive comparison between conventional and proposed methodology. This comparison shows what approaches are usually taken for typical cases, and what problems arise when applying the typical convention to bulldozer operation. To address the issues, approaches and corresponding aims taken in this proposed methodology are presented. Typical case

Problems in applying typical convention

Model

Grid-based model

Environment

- Grid space - Obstacle location - Goal is given

Goal is not given

Agent

Robot (Agent-motion oriented planning) Traveled distance from start to current position

Need to plan material handling along with agent motion

Cost g(n)

Cost h(n)

This paper Approach

Aim

Topologically modeled scenario

- Comp. cost reduction - Additional info. to path - Incorporating two key ideas of bulldozers’ operation - To plan material handling pattern along with agent motion

Plan material handling pattern

Normalized traveling time

Heuristic to goal

- Enable addition - To plan material handling pattern along with agent motion

Normalized remaining volume

Table 4 Variables to formulate cost function.

The complete methodology is shown in the form of a pseudocode in Algorithm 1. This pseudocode also presents the part which needs to

Symbol

Meaning

TS-C TNom VRest VIni

Elapsed time that bulldozers operate in from the start to the current point Nominal total operation time Remaining volume of material Initial volume of material

Algorithm 1 Bulldozers’ path planning pseudocode. Input: Material proﬁle; Dumping area edge; Output: A path for bulldozers to remove the material if

Type1: Side attack 𝑂𝑝𝑒𝑛 ← ∀𝑀𝑥 such that 𝑉capacity ); 3: else if Type2: Middle attack 𝑂𝑝𝑒𝑛 ← ∀𝑀𝑥 such that 𝑤remain 4:

1:

Table 5 Variables for pseudocode.

2:

Symbol

Meaning

Mx V (Mx ) v Vcapacity klb kub wremain 𝑤min

Path line from node x The amount of material that a bulldozer pushes when following line Mx Remaining amount of material Blade capacity Lower bound ratio of material to be pushed Upper bound ratio of material to be pushed Width of remaining mound Minimal threshold for windrows

5: 6:

7: 8: 9: 10:

based on topological planning, and a start and goal point are not given, therefore a modiﬁed version of A∗ needs to be sought. Searching in the standard A∗ algorithm proceeds based on minimizing the total cost at each iteration. The total cost f(n) can be expressed as Eq. (1) [46].

13:

𝑓 (𝑛) = 𝑔(𝑛) + ℎ(𝑛)

15:

11: 12:

where g(n) is the actual cost of a path from the start to the current position, h(n) is a heuristic to estimate the cost from the current position to the goal, and n represents the current node. Table 3 shows a comprehensive comparison between the proposed formulation and a typical case. The major problem in applying the typical convention is, again, in bulldozers’ operation, start and goal points are not given, and material handling needs to be planned along with an agent motion. To address these issues, approaches taken in terms of model, environment, agent, and cost formulation in this paper are shown in Table 3. Simultaneously a part of this table results in providing the 3-step procedure, which was already presented in this subsection. The actual cost g(n) and a heuristic h(n) are deﬁned in Eqs. (2) and (3), respectively, as well as shown in Table 3. As opposed to a typical case where the same metric is used for g(n) and h(n), normalization is necessary for this proposed methodology, as diﬀerent metrics are used. (2)

ℎ(𝑛) = 𝑉Rest ∕𝑉Ini

(3)

then ≥ 𝑤min ;

endif; 𝐶𝑙𝑜𝑠𝑒 ← 0; repeat Select 𝑀best from 𝑂𝑝𝑒𝑛 such that 𝑓 (𝑀best ) ≤ 𝑓 (𝑛), ∀𝑛 ∈ 𝑂𝑝𝑒𝑛; Remove 𝑀best from 𝑂𝑝𝑒𝑛 and add to 𝐶𝑙𝑜𝑠𝑒; Update material proﬁle; if 𝑣 = 0 then Exit endif; Initialize 𝑉 (𝑀𝑥 );

Type1: Side attack then Expand 𝑀best for ∀𝑀𝑥 that are not in 𝑂𝑝𝑒𝑛 such that (𝑘lb × 𝑉capacity ) ≤ 𝑉 (𝑀𝑥 ) ≤ (𝑘ub × 𝑉capacity ); else if Type2: Middle attack then 16: Expand 𝑀best for ∀𝑀𝑥 that are not in 𝑂𝑝𝑒𝑛 such that 𝑤remain ≥ 17: 𝑤min ; 14:

(1)

𝑔(𝑛) = 𝑇S−C ∕𝑇Nom

then (𝑘lb × 𝑉capacity ) ≤ 𝑉 (𝑀𝑥 ) ≤ (𝑘ub ×

18:

19: 20:

if

endif; Add ∀𝑀𝑥 to 𝑂𝑝𝑒𝑛 until 𝑂𝑝𝑒𝑛 is empty

be changed depending on Type 1; Side attack or Type 2: Middle attack. As shown in Algorithm 1, motion assumption is deﬁned by using the blade capacity as a state expansion rule. The following equation is an example of the bulldozers’ state expansion rule. Descriptions about the variables used in Eq. (4) are shown in Table 6. By using the deﬁned state expansion rule, the states to be expanded to at the next iteration are chosen if the amount of material V satisﬁes Eq. (4). Fig. 19 shows a very simpliﬁed example intuitively illustrating how this new algorithm autonomously plans a path for bulldozers (Tables 4, 5 and 8). 28

M. Hirayama, J. Guivant and J. Katupitiya et al.

Mechatronics 58 (2019) 20–38

Table 7 Variables to formulate way-points. Symbol

Meaning

dturn dswitch

Oﬀset distance from the material to get in line with the next push Oﬀset distance from the material to reverse to

Table 8 Symbols used in the formulation. Symbol

Meaning

Ttotal N 𝑡𝑖,𝑃 𝑗−𝑃 𝑘 𝑙𝑖,𝑃 𝑗−𝑃 𝑘 vF vR vp (t) 𝜇 N m g 𝛾 dw dh dd Ca , Cb

Total operation time Number of pushes Time for the bulldozer to move from Pj to Pk at ith push Path length from Pj to Pk at ith push Forward velocity Reverse velocity Variable velocity Friction coeﬃcient Material’s normal force Material’s weight Gravity acceleration Material’s speciﬁc weight Bulldozer’s contact width with the material Bulldozer’s contact height with the material Bulldozer’s contact depth with the material Coeﬃcients for ﬁtting

State expansion rule (𝑘lb × 𝑉capacity )

Table 6 Variables to formulate state expansion rule. Meaning

V Vcapacity klb kub

The amount of material that a bulldozer pushes Blade capacity Lower bound ratio Upper bound ratio

(𝑘ub × 𝑉capacity )

(4)

As mentioned in Section 1.2.2, a lower computational cost is also aimed for in the development of this methodology. The bottom row in Table 3 shows the conceptual diﬀerence of the computational cost. The number of arrows is equal to the number of iterations, which directly represents the computational cost. The iteration in this case refers to expansions in the search tree. With a grid-based model, which is often used in typical cases, no matter whether the path is a curve or a straight line, the iterations are applied for the number of grid squares unconditionally. This can result in unnecessary numbers of iterations especially when only a straight line is necessary for the path. This aspect is also improved with the developed methodology. As can be seen in Table 3, since the environment model is based on topological formulation, only one iteration is needed for a straight line. This eﬀect was realized by introducing the two key ideas of the bulldozers’ operation, and simultaneously contributes to the signiﬁcant computational cost reduction. Fig. 20 shows the proposed path creation procedure. A key point is that the planning algorithm only has to plan forward paths. This is because reverse paths can be created by using simple geometry with respect to the material’s position and the planned forward paths. Therefore, at the end of the search process, the proposed search algorithm essentially provides only forward paths. However, in calculating a value of g(n), the time from the start to the current position also includes the reverse traveling time to ensure the minimum total cost path can be derived considering the back-up motion. Table 7 shows necessary variables to determine way-points. The point of introducing dswitch and dturn is to determine how far the bulldozer should reverse back after it pushes, and to avoid collision between the bulldozers and the material, respectively. If the bulldozer simply travels from the end of the push to the start of the next push, the path overlaps with still-existing material, hence this situation needs to be avoided. In order to do so, turning points are created at the distance from dturn so that the bulldozer simply reverses on the same path as the forward push, then starts to move onto the next push path. In that way, the material in the area the bulldozer travels is already removed by previous pushes, thus the bulldozers do not collide with the existing material. Since the bulldozer makes turns while reversing, dswitch needs to be long enough so that the bulldozer’s orientation is in line with the next forward path, in such a way the bulldozer only has

Fig. 14. Illustration of the discrete operation status.

Symbol

≤𝑉 ≤

29

M. Hirayama, J. Guivant and J. Katupitiya et al.

Mechatronics 58 (2019) 20–38

Fig. 15. This is how bulldozers push material based on the two key ideas.

Fig. 16. Problems expected to happen if the two key ideas are not exercised.

to move straight forward on the planned path to move the next material. The actual value for dswitch could be any number as long as it complies with the conditions described above. For example, 𝑑switch = 15(m) was used in our case. This value was arbitrarily determined by observing professional bulldozer operators’ practice. After creating these way-points, a reverse path can be created simply by connecting these points. This process is shown in Sub-ﬁgure(3) in Fig. 20. As such, the path including forward and reverse paths is the ﬁnal solution path for the bulldozers to follow. As illustrated with this speciﬁc example, the proposed procedure ﬁrst plans the material handling pattern, rather than planning the agent’s motion in the ﬁrst place, then derives a path for the agent from the material handling pattern. One important criterion for A∗ algorithm is that heuristic h(n) needs to satisfy the following equation, to ensure admissibility. When h(n) is admissible, the A∗ search is guaranteed to be optimal and complete [46,48]. ∀𝑛 ℎ (𝑛) ≥ ℎ(𝑛) ∗

Fig. 17. Topological modeling.

the completeness is still guaranteed. Fig. 21 illustrates this comparison in detail. This is the beneﬁt of this proposed formulation, by introducing a material handling pattern to the planner in addition to the agent motion. From an industry perspective, completeness is considerably more signiﬁcant than optimality. Without completeness, the existence of a solution path is unknown before running the path planner, and the bulldozers can not know what path to follow if there is no solution path, which would result in critical system failure. For this reason, the proposed methodology can be considered to be suﬃcient for this paper’s purpose.

(5)

where h∗ (n) represents the true cost from n to the goal. As a result of adjusting A∗ algorithm to bulldozers’ operation, the optimality of a solution is no longer guaranteed, nevertheless the proposed methodology still holds completeness. This still agrees with the minimal acceptable requirements from an industry perspective. The reason the property of optimality is lost is, in the formulation presented in Table 3, the admissibility criterion as in Eq. (5) is satisﬁed only at the last iteration, and for the remaining range of n, the condition bounded by Eq. (5) is not always guaranteed. However, unlike a typical case where an agent explores a maze environment with any chance of being stuck at cul de sac, in the scenario considered in this paper, material will be removed eventually no matter what order or volume the bulldozers move per push, therefore

2.4.3. Constraints for path solution completeness Constraints to ensure the completeness of the path solution are presented in this section. Fig. 22 illustrates a general case scenario of a dumping area operation. Note that the dumping area edge proﬁle is 30

M. Hirayama, J. Guivant and J. Katupitiya et al.

Mechatronics 58 (2019) 20–38

tion operates as an MPC (Model Predictive Control) approach [49–52], in which only the ﬁrst part of the nominal plan is used, because a new plan is generated for the rest, based on updated information (last estimated 3D terrain). That new plan may not be exactly coincident with the previous nominal plan (as usually occurs in MPC). This approach should be implemented at a high level loop, and is necessary due to the fact that material behavior prediction is not included in the developed methodology. However this drawback can be compensated by the idea of a constant update of terrain information and replanning of a path. By doing this, the planned path is ensured to be in line with the actual terrain speciﬁcation in real time, and there would be no redundancy in regards to the material removal. Note that in the context of recent mining operations, real-time full access to terrain information is available, it is extensively feasible to obtain the measurement of the remaining material in real time (Figs. 23 and 24). 3. Theoretical model for operation time This section presents a theoretical derivation of the total operation time for bulldozers to remove the required amount of material. The equation to calculate the total operation time is presented in Eq. (7). A part of the path segments requires variable velocity formulation to derive the operation time calculation, which is presented in Section 3.2.

Fig. 18. Topological modeling comparison between this paper and a typical case. Parts shown in blue represent the map in each case. Incorporating the two key ideas of bulldozers operation ﬁts with the deﬁnition of nodes and edges. By incorporating the two key ideas, the edges can contain the material amount information. (For interpretation of the references to color in this ﬁgure legend, the reader is referred to the web version of this article.)

3.1. Total operation time For the dumping area operation scenario, from the perspective of bulldozers’ traveling time, the path can be split into 4 segments. Those 4 segments are identical to the segmentation already shown in Table 2 and Fig. 14. Hence, a formulation for the total operation time Ttotal can be expressed as the following equation. Note that an acceleration proﬁle is not taken into account for the modeling, considering bulldozers are relatively slow velocity machines, hence the inﬂuence of including acceleration/deceleration can be considered to be small, and can be negated.

assumed to be approximated in a certain appropriate way. This approximation may be chains of straight line segments, curved line segments, or any other suitable geometric methods. Note that, in this paper, only normal scenarios for bulldozers’ dumping area operation are assumed for practical purposes, therefore unusual situations such as obstacles, are not considered for the formulation. As all the area from Edge point Pi which bulldozers can travel ⋃ through can be expressed as ∀𝑗 𝐴𝑖,𝑗 by using the deﬁned variables, all the area for the speciﬁed region ) which bulldozers can travel through can ⋃ (⋃ . The constraint to ensure the completebe expressed as ∀𝑖 𝐴 𝑖,𝑗 ∀𝑗

𝑇total =

𝑖=1

∀𝑖∈Specif ied region

(𝑡𝑖,𝑃 1−𝑃 2 + 𝑡𝑖,𝑃 2−𝑃 3 + 𝑡𝑖,𝑃 3−𝑃 4 + 𝑡𝑖,𝑃 4−𝑃 5 )

+(𝑡𝑁,𝑃 1−𝑃 2 + 𝑡𝑁,𝑃 2−𝑃 3 + 𝑡𝑁,𝑃 3−𝑃 4 )

ness is that the area which can be traveled through by bulldozers needs to cover the area of the material segments. Hence the constraint can be mathematically expressed as the following equation. In other words, the region for bulldozers to take material to, needs to be speciﬁed in such way it satisﬁes the constraint expressed in Eq. (6). (⋃ ) ⋃ ⋃ (6) 𝑆𝑘 ⊂ 𝐴𝑖,𝑗 ∀𝑘

𝑁−1 ∑

(7)

As shown in Fig. 14, since all the velocity segments except for the P2 to P3 region are constant velocities, the bulldozer’s traveling time can be expressed as the following equations. 𝑡𝑖,𝑃 1−𝑃 2 =

𝑙𝑖,𝑃 1−𝑃 2

𝑡𝑖,𝑃 3−𝑃 4 =

2.4.4. Implementation with path tracking involved Once a path is planned, the bulldozer needs to be moved along the path using path tracking as shown in the framework presented in Fig. 6. While this paper’s predominant focus is on path planning, path tracking is based on a standard PID control. The major limitation of the developed methodology in implementing it in a real life situation, is that there is a discrepancy in regards to the path between reality and that of planned. Hence, although the methodology is capable of planning a path for the entire given material amount, if bulldozers simply follow all the paths, there would be a redundancy in terms of both excess and deﬁciency of the material. This means that the bulldozer could potentially run on the empty area where the material has been already removed, or some material would be left behind on the dumping area as bulldozers continue operation. This issue can be solved by using adaptive replanning. Hence adaptive replanning is essential when it comes to implementing this developed algorithm to a real commercialized product. The idea is to simply update the terrain information and replan a path every time a bulldozer pushes material. The updated 3D description is periodically used for updating the plan. The plan considers a certain horizon, but the real ac-

𝑡𝑖,𝑃 4−𝑃 5 =

(8)

𝑣𝐹

∀𝑗

𝑙𝑖,𝑃 1−𝑃 2 𝑣𝑝 (𝑡)∕Bulldozer

(9)

is at 𝑃 3

𝑙𝑖,𝑃 4−𝑃 5

(10)

𝑣𝑅

3.2. Variable velocity formulation The velocity for the bulldozer to travel from P2 to P3 varies over the traveling time, as the material volume the bulldozer pushes changes in the region. Therefore, the bulldozer’s traveling time can be obtained by solving the following equation for 𝑡𝑖,𝑃 2−𝑃 3 . 𝑙𝑖,𝑃 2−𝑃 3 =

𝑡𝑖,𝑃 2−𝑃 3

∫0

𝑣𝑝 (𝑡)𝑑𝑡

(11)

To solve Eq. (11), the variable velocity vp (t) needs to be explicitly expressed as a function of t. In order to do this, the drawbar pull curve for the bulldozer needs to be considered, and the resistance force acting on the bulldozer has to be formulated accordingly. Firstly, to formulate the resistance force, the scenario of the bulldozer pushing material is shown in Fig. 25. This resistance force solely 31

M. Hirayama, J. Guivant and J. Katupitiya et al.

Mechatronics 58 (2019) 20–38

Fig. 19. A simpliﬁed example of path planning by using the developed methodology.

depends on the weight of the material pushed by the bulldozers, therefore the resistance force FR can be expressed as the following equation, based on the standard friction equation [53]. Note that a ﬂat surface is assumed on the dumping area, just as can be often seen in a real mining site. Hence, an inclination of the ground does not have to be taken into account. It is also assumed that the material pushed by the bulldozers is a rectangular cube for the purpose of simplifying the computation. 𝐹𝑅 = 𝜇𝑁 = 𝜇𝑚𝑔 = 𝜇 × (𝛾𝑑𝑤 𝑑ℎ 𝑑𝑑 ) × 𝑔 = 𝜇 × (𝛾𝑑𝑤 𝑑ℎ 𝑣𝑝 (𝑡)𝑡) × 𝑔

resistance force indicates the balancing point between the bulldozers’ pushing force and the resistance force from the material, therefore this point indicates the current velocity. Hence, it makes sense with Fig. 26 that, as the bulldozers push material, the material amount increases, and the bulldozers’ velocity decreases accordingly. Commercial bulldozers possesses the function of automatic gearshift mode, which smoothly changes the trasmission gears automatically, based on the variable resistance force. An approximation of the automatic gear shift mode curve throughout the whole speed range was attempted in the work done by Klanfar et al. [54]. Their derived formula matches well with the genuine drawbar pull curve in the higher speed range, but not in the lower speed range. This is due to seeking an approximation for all speed ranges. However, when bulldozers push material, they typically use only Forward 1st gear. Therefore, as opposed to the approximation intention of Klanfar et al., considering a lower speed region is more essential, predominantly when looking at bulldozers’ dynamics of pushing material. In this proposed methodology, only

(12)

Secondly, to obtain an explicit function for vp (t), the drawbar pull curve is introduced. Fig. 26 shows the typical drawbar pull curve of bulldozers. The curve (green dotted line) is superposed with the resistance force from Eq. (12) (blue line). As can be seen in Eq. (12), as time passes, the amount of material the bulldozer pushes increases, and the resistance increases accordingly. This corresponds to the line inclination increase of the resistance force (blue line) as shown in Fig. 26. The intersection (blue dot) of the drawbar pull curve and the 32

M. Hirayama, J. Guivant and J. Katupitiya et al.

Mechatronics 58 (2019) 20–38

Fig. 20. Path creation procedure.

Fig. 21. Completeness comparison.

33

M. Hirayama, J. Guivant and J. Katupitiya et al.

Mechatronics 58 (2019) 20–38

Fig. 22. General case scenario of dumping area operation - Denotation for constraint formulation.

Fig. 23. Block diagram of path tracking.

the Forward 1st gear curve is approximated. For simpliﬁcation purposes, a line ﬁtting can be presumed to be suﬃcient, and the equation is shown below: 𝐹𝑅 = 𝐶𝑎 𝑣𝑝 (𝑡) + 𝐶𝑏

(13)

From Eqs. (12) and (13), vp (t) can be solved as the following equation: 𝐶𝑏 𝑣𝑝 (𝑡) = (14) 𝜇𝑔𝛾𝑎𝑤 𝑎ℎ 𝑡 − 𝐶𝑎 By inserting this derived function to Eq. (11), 𝑡𝑖,𝑃 2−𝑃 3 can be obtained as the following equation: ( ( ) ) 𝜇𝑔𝛾𝑎𝑤 𝑎ℎ 𝑙𝑖,𝑃 2−𝑃 3 −𝐶𝑎 𝑡𝑖,𝑃 2−𝑃 3 = × exp −1 (15) 𝜇𝑔𝛾𝑎𝑤 𝑎ℎ 𝐶𝑏 Eqs. (8)–(10), and (15) are all the necessary time segments to calculate the total operation time Eq. (7), and these time segments are now derived in such way of being dependent solely on the path length. This means, once a path for bulldozers is planned, the operation time can be immediately predicted. 4. Simulation results and discussion This section presents path planning simulation results with Type 1 and Type 2 operations (See Section 2.2) for the same amount and proﬁle of material. The purpose of the comparison is to identify which operation type enables the bulldozers to remove the required amount of material in a faster time. The simulation was run with two diﬀerent blade-width conditions to observe the result consistency, provided that the main body of the bulldozer is identical, hence the drawbar pull performance is identical accordingly. This scenario in a real life situation would assume only the blade is changed to larger capacity options. The blade width ratio means the ratio between the blade width and the material width, and can be expressed as the following equation. 𝑤 𝛽= 𝑏 (16) 𝑤𝑚

Fig. 24. Adaptive replanning for this paper’s algorithm.

where wb represents the blade width, and wm represents the material width. For the sake of argument in this simulation, two blade widths (𝛽 = 0.3, 0.4) are chosen based on available commercial models, considering the realistic size of the bulldozer to use for the presumed size of the material. Table 9 shows the total operation time comparison with these 34

M. Hirayama, J. Guivant and J. Katupitiya et al.

Mechatronics 58 (2019) 20–38

Table 9 Path planning simulation results showing the corresponding total operation times with the same amount and proﬁle of material. The results show that operation type 1 provides a faster operation time for two diﬀerent cases of the blade width. The operation time in Type 1 is up to 19% faster, compared to Type 2.

Case 1 Standard blade 𝛽=0.3 Case 2 Wider blade 𝛽=0.4

Operation type 1 Side attack

Operation type 2 Middle attack

Comparison result

100 (s) 83 (s)

109 (s) 103 (s)

Type 1 ‘Side attack’ is 8% (9s) faster Type 1 ‘Side attack’ is 19% (20s) faster

Fig. 25. Resistance force acting on bulldozer.

Fig. 27. Autonomous way-point generation. Start, goal, and subgoal points are autonomously generated only from the terrain data, by using the developed methodology.

diﬀerent conditions. The simulation results suggest the following two items predominantly. Note that the scale is based on a real commercial bulldozer. • Result 1: Path planning methodology for autonomous bulldozers is developed Firstly, a methodology which autonomously plans a path for bulldozers to remove waste material with a multiple number of pushes on a dumping area is developed. As mentioned in Section 1.2.2, the major diﬀerence from existing methodology is the necessity of material handling, and non-given start and goal points. Fig. 27 shows that those necessary points are autonomously generated, only from the given terrain data. The developed methodology successfully provides a path for bulldozers to remove waste material within a minimal time. • Result 2: Operation type 1 is faster Table 9 also shows that Operation type 1 is faster than type 2, regardless of the blade width. This is subject to the condition already mentioned in Section 2.2 - bulldozers in Operation type 1 are presumed to take up to 60% of the blade capacity to avoid material spillage. To analyze the total operation time diﬀerence, as a representative example, Fig. 28 shows a time history of the bulldozer’s velocity, and the material volume change, for ‘Case1’ blade width ratio. The reason this case was chosen is that both

Fig. 26. Drawbar pull curve superposed with the resistance force line. According to Eq. (12), the resistance increases as time passes and the material amount increases. The intersection indicates the current velocity. The velocity decreases as the bulldozer pushes material through. (For interpretation of the references to color in this ﬁgure, the reader is referred to the web version of this article). 35

M. Hirayama, J. Guivant and J. Katupitiya et al.

Mechatronics 58 (2019) 20–38

Fig. 28. Time history of bulldozer’s velocity and material volume change from Case 1 blade width ratio. With Type 2, an extended time to transport material from P3 to P4 makes the total operation time longer. This makes Type 1 operation faster.

operation types have the same number of pushes. Type 1 allows the bulldozer to move around 20–30% of the total material volume constantly, while Type 2 allows the bulldozer to take a more pronounced volume for the ﬁrst push where material is taken from the middle, then small amounts for the rest of the time. As mentioned, the more material the bulldozer pushes, the slower the bulldozer’s velocity becomes. The simulation results show that, as in the plot of ‘Volume the dozer pushes’, the bulldozer moves more material per push in Type 2 while pushing material from the middle, however after that process, it takes a longer time to clean windrows, and at the last push of Type 1, the bulldozer ﬁnishes removing all the material and eventually provides a faster operation time. Therefore, for this type of operation, which can be often seen at dumping area operations, it can be said that it is faster to move a constant amount of material throughout the whole process, rather than attempting to move more material at ﬁrst and smaller leftover amounts at

the end. This is due to the drastically decreasing velocity of the bulldozer if holding more material. This extended time is especially pronounced with the time to transport the material from P3 to P4 at Push 1, 𝑡1,𝑃 3−𝑃 4 with Type 2 operation, as can be seen in Fig. 28. This has a major inﬂuence on the total operation time.

5. Conclusions This work presented a novel and practical path planning methodology for autonomous bulldozers. A novel post-processing methodology of terrain mapping conversion, which can be fed to the developed path planning in an eﬃcient way, was also presented. The path planning development idea is based on topological modeling of the environment, material handling pattern planning to derive a path for bulldozers, and a novel formulation of true cost and heuristic. This approach addressed the issues occurring when attempting to apply the existing 36

M. Hirayama, J. Guivant and J. Katupitiya et al.

Mechatronics 58 (2019) 20–38

planning methodology to bulldozers’ scenario, namely, in particular, the necessity of dealing with the material handling, and non-given start and goal points. Simultaneously, the developed methodology ensures the completeness, hence a path for bulldozers to remove waste material is always guaranteed to be provided. In the process of this methodology development, the key ideas of bulldozer’s operation based on industry perspectives, are incorporated to ensure the solution path is in line with eﬃcient machine utilization. The developed methodology was applied to two operation types in the planning simulation. The simulation results show that Operation type 1, Side attack, enables the bulldozers to remove the required amount of the material in a faster time. It also shows that this result is consistent with diﬀerent blade widths.

[8] Lucas R. Optimisation of waste-Dump lift heights for pre-strip operations. In: Proceedings of the fourteenth coal operator’s conference. Wollongong; 2014. p. 427–36. [9] Hirayama M, Whitty M, Katupitiya J, Guivant J. An optimized approach for automatic material distribution operations of bulldozers. Int J Adv Rob Syst 2018;15(2):361–70. 1729881418764716 [10] Wang LH, Wang J. Application of GPS RTK technology in mountain planting location lofting in world garden exposition of Qingdao in 2014. Adv Mater Res 2014;933:794–8. Trans Tech Publ. [11] Lenain R, Thuilot B, Cariou C, Martinet P. Adaptive control for car like vehicles guidance relying on RTK GPS: rejection of sliding eﬀects in agricultural applications. In: Proceedings of the 2003 IEEE International Conference on Robotics and Automation, 1; 2003. p. 115–20. (Cat. No.03CH37422). [12] Taghia J, Wang X, Lam S, Katupitiya J. A sliding mode controller with a nonlinear disturbance observer for a farm vehicle operating in the presence of wheel slip. Auton Robots 2017;41(1):71–88. [13] Durst P, Gray W. Levels of autonomy and autonomous system performance assessment for intelligent unmanned systems, 1. The US Army Engineer Research and Development Center; 2014. [14] Milella A, Cicirelli G, Distante A. RFID-Assisted mobile robot system for mapping and surveillance of indoor environments. Ind Robot (UK) 2008;35(2):143–52. [15] Wettergreen D, Moreland S, Skonieczny K, Jonak D, Kohanbash D, Teza J. Design and ﬁeld experimentation of a prototype lunar prospector. Int J Robot Res (USA) 2010;29(12):1550–64. [16] Miura S, Hamamoto K, Kuronuma I. Next generation construction production system: on automated construction machinery. In: Proceedings of the seventh civil engineering conference in the Asian region; 2016. [17] Guivant JE. Real time synthesis of 3D images based on low cost laser scanner on a moving vehicle. V Jornadas Argentinas de Robotica 2008. [18] Katz R, Melkumyan N, Guivant J, Bailey T, Nieto J, Nebot E. Integrated sensing framework for 3D mapping in outdoor navigation. In: Proceedings of the IEEE international conference on intelligent robots and systems. Beijing, China; 2006. p. 2264–9. [19] Robledo A, Cossell S, Guivant J. Outdoor ride: Data fusion of a 3d kinect camera installed in a bicycle. In: Proceedings of the Australasian conference on robotics and automation. Melbourne, Australia; 2011. [20] Nebot E, Guivant J, Worrall S. Haul truck alignment monitoring and operator warning system. J Field Rob 2006;23(2):141–61. [21] Ben-Moshe B, Carmi P, Katz MJ. Approximating the visible region of a point on a terrain. Geoinformatica 2008;12(1):21–36. doi:10.1007/s10707-006-0017-5. [22] Coll N, Guerrieri M, Rivara MC, Sellarès JA. Terrain approximation from grid data points. In: Actas XIII Encuentros de Geometria Computacional. Zaragoza, Spain; 2009. p. 101–8. [23] Garland M, Heckbert P. Fast polygonal approximation of terrains and height ﬁelds. Technical Report. CS Department, Carnegie Mellon U.; 1995. [24] Herbert M, Caillas C, Krotkov E, Kweon IS, Kanade T. Terrain mapping for a roving planetary explorer. In: Proceedings of the IEEE international conference on robotics and automation. Scottsdale, AZ, USA; 1989. p. 997–1002. [25] Segu WP. Terrain approximation by ﬁxed grid polynomial. Photogramm Rec (UK) 1985;11(65):581–91. [26] Edelsbrunner H, Kirkpatrick DG, Seidel R. On the shape of a set of points in the plane. IEEE Trans Inf Theory (USA) 1983;29(4):551–9. [27] Edelsbrunner H, Mucke EP. Three-dimensional alpha shapes. ACM Trans Graph (USA) 1994;13(1):43–72. [28] Guo B, Menoo J, Willette B. Surface reconstruction using alpha shapes. Comput Graph Forum (UK) 1997;16(4):177–90. [29] Wilson JA, Bender A, Kaya T, Clemons PA. Alpha shapes applied to molecular shape characterization exhibit novel properties compared to established shape descriptors. J Chem Inf Model (USA) 2009;49(10):2231–41. [30] Kim S-S, Park J-H. Space-eﬃcient terrain rendering using constrained Delaunay triangulation. In: Proceedings of the international geoscience and remote sensing symposium (IGARSS), 4. Toronto, Ont., Canada; 2002. p. 2441–3. [31] Liu X, Rokne JG, Gavrilova ML. A novel terrain rendering algorithm based on quasi Delaunay triangulation. Vis Comput (Germany) 2010;26(6–8):697–706. [32] Lo SH. Parallel delaunay triangulation in three dimensions. Comput Methods Appl Mech Eng 2012;237:88–106. [33] Nieto A, Peng SL. Proximity warning and terrain modelling system based on Delaunay triangulation and surface spline interpolation. Trans Inst Mining Metall Sec A Mining Technol 2010;119(1):1–7. [34] Rognant L, Chassery JM, Goze S, Planes JG. The Delaunay constrained triangulation: the Delaunay stable algorithms. In: Proceedings of the IEEE international conference on information visualization. Los Alamitos, CA, USA; 1999. p. 147–52. Cat. No. PR00210. [35] Auat Cheein FA, Guivant J. SLAM-Based incremental convex hull processing approach for treetop volume estimation. Comput Electron Agric (Netherlands) 2014;102:19–30. [36] Barber CB, Dobkin DP, Huhdanpaa H. The quickhull algorithm for convex hulls. ACM Trans Math Softw (USA) 1996;22(4):469–83. [37] Guo L, Yang Q, Yan W. Intelligent path planning for automated guided vehicles system based on topological map. In: Proceedings of the 2012 IEEE conference on control, systems & industrial informatics (ICCSII). Piscataway, NJ, USA; 2012. p. 69–74. [38] Yi D, Goodrich MA, Seppi KD. Homotopy-aware RRT∗ : toward human-robot topological path-planning. In: Proceedings of the eleventh ACM/IEEE international conference on human-robot interaction (HRI). Piscataway, NJ, USA; 2016. p. 279–86. [39] Alshaer BJ, Darabseh TT, Alhanouti MA. Path planning, modeling and simulation of an autonomous articulated heavy construction machine performing a loading cycle. Appl Math Model (USA) 2013;37(7):5315–25.

6. Future work The next steps for further improvement were identiﬁed either for terrain mapping and path planning, which are the two domains predominantly dealt with in this paper. Firstly, the future work for terrain mapping is to improve the robustness of the applicability. The proposed methodology in this paper assumes that the cross section, as in Fig. 12, contains only one mound, and is not capable of handling a multiple number of mounds in a single cross section. Resolving this limitation will contribute to the range of scenarios where this methodology can be applied. Secondly, the future work for path planning is to secure optimality, and conﬁrmation of the faster operation type consistency in various environmental conditions. As mentioned, as a result of adjusting the standard A∗ algorithm, optimality had to be sacriﬁced at the formulation stage, although this is not a critical issue from the perspective of implementation to commercial products. Therefore, an improvement of the formulation to ensure optimality will contribute to the derivation of path which provides an even shorter operation time. Optimality can also be approached from the perspective of spillage management. In the presented work, the spillage prevention was dealt with by predeﬁning the blade-ﬁll ratio for the bulldozer. This adaptive ﬁlling ratio will contribute to the improvement of path optimality. Mathematical proof in regards to the completeness is another related future work. Additional future work is to conﬁrm the consistency of the faster operation type. In this paper, only one mound proﬁle was used to assess the operation time diﬀerence, to obtain Result 2. In order to conﬁrm the generality of this result, various environmental conditions including the mound width, the mound depth, or distance between the mound and the dumping area edge should be considered for the operation time assessment. Lastly, implementation to a real bulldozer at a mining site is another future work. Along with this, a study in regards to what cost fraction of the dumping area operation is related to bulldozers, and how much can be reduced by using the proposed methodology also has to be done. This will assess the eﬀectiveness of this research aim, and assist us to have an even more eﬀective aim when extending this work to other themes. References [1] Hamanaka A, Inoue N, Shimada H, Sasaoka T, Matsui K. An evaluation on mixture materials using overburden and Flyash as cover layer for acid mine drainage prevention and underlying materials of seedbed in indonesian coal mine. Res J Environ Earth Sci 2014;6(10):486–92. [2] Maheshi D, Steven VP, Karel VA. Environmental and economic assessment of ‘open waste dump’ mining in Sri Lanka. Resour Conserv Recycl (Netherlands) 2015;102:67–79. [3] Scott B, Ranjith PG, Choi SK, Khandelwal M. A review on existing opencast coal mining methods within Australia. J Min Sci 2010;46(3):280–97. [4] Xie Z, Luan T, He N. Safety evaluation technology for waste dump landslide of open-pit mine based on fuzzy mathematics. Appl Mech Mater (Switzerland) 2013;353–356:2245–50. [5] Adam RA, Bertinshaw RG. Waste dumps - the new frontier. In: Proceedings of the third large open pit mining conference. Mackay, Australia: (The Australasian Institute of Mining and Metallurgy); 1992. p. 255–9. [6] Ercelebi SG, Bascetin A. Optimization of shovel-truck system for surface mining. J South Afr Inst Min Metall 2009;109(7):433–9. [7] Kennedy BA. SME surface mining. second ed. United States: Society for Mining, Metallurgy, and Exploration; 1990. 37

M. Hirayama, J. Guivant and J. Katupitiya et al.

Mechatronics 58 (2019) 20–38 Jose E. Guivant received the B.E. degree in Electrical Engineering from the Universidad Nacional del Sur (UNS), Bahia Blanca, Argentina, and his Ph.D. degree in Robotics, from The University of Sydney (ACFR/USYD), Australia. He is currently Sr. Lecturer in Mechatronics, at the School of Mechanical Engineering, UNSW, Australia.

[40] Enright JJ, Frazzoli E. The traveling salesman problem for the Reeds-Shepp car and the diﬀerential drive robot. In: Proceedings of the IEEE conference on decision and control. San Diego, CA, United states; 2006. p. 3058–64. [41] Kim JM, Lim KI, Kim JH. Auto parking path planning system using modiﬁed Reeds-Shepp curve algorithm. In: Proceedings of the eleventh international conference on ubiquitous robots and ambient intelligence (URAI). Piscataway, NJ, USA; 2014. p. 311–15. [42] Dai P, Katupitiya J. Path planning and tracking of a 4WD4WS vehicle to be driven under force control. In: Proceedings of the IEEE international conference on mechatronics and automation (ICMA). Piscataway, NJ, USA; 2014. p. 1709–15. [43] Bjelkeﬂo L. Volvo outlook on vehicle automation. Technical Report; 2013. [44] Hayes TG. Using dozers to remove coal overburden. Min Eng 1997;49(10):35–8. [45] Uren Z, Nehring M. Development of dozer push optimisation software for commodore coal mine. Trans Inst Mining Metall Sec A Mining Technol 2015;124(4):231–8. [46] Hart PE, Nilsson NJ, Raphael B. A formal basis for the heuristic determination of minimum cost paths. IEEE Trans Syst Sci Cybernet 1967;SSC-4(2):100–7. [47] Elfes A. Using occupancy grids for mobile robot perception and navigation. Computer (USA) 1989;22(6):46–57. [48] Dechter R, Pearl J. Generalized best-ﬁrst search strategies and the optimality of a∗ . J Assoc Comput Mach (USA) 1985;32(3):505–36. [49] Tan Q, Wang X, Taghia J, Katupitiya J. Force control of two-wheel-steer four-wheel– drive vehicles using model predictive control and sequential quadratic programming for improved path tracking. Int J Adv Rob Syst 2017;14(6):522–36. [50] Shen C, Shi Y, Buckham B. Integrated path planning and tracking control of an AUV: a uniﬁed receding horizon optimization approach. IEEE/ASME Trans Mechatron (USA) 2017;22(3):1163–73. [51] Klancar G, Rkrjanc I. Inﬂuence of sample period variation to MPC trajectory tracking of mobile robot. IFAC, Pap Online (Netherlands) 48 (1) 669–670. [52] Wang X, Taghia J, Katupitiya J. Robust model predictive control for path tracking of a tracked vehicle with a steerable trailer in the presence of slip. IFAC-PapersOnLine 2016;49(16):469–74. [53] Ruina A, Pratap R. Introduction to static and dynamics. Oxford University Press; 2002. [54] Klanfar M, Kujundzic T, Vrkljan D. Analiza proracuna ucinka dozera pri gravitacijskom transportu na povrinskim kopovima. Tehnicki Vjesnik 2014;21(3):517–23.

Jayantha Katupitiya has a bachelor’s degree in production engineering from the University of Peradeniya, Sri Lanka, and a Ph.D. degree from the Katholieke Universiteit Leuven, Belgium. He is currently an associate professor and the head of the mechatronic engineering program at the University of New South Wales in Sydney, Australia. His main research interest is the development of sophisticated control methodologies for the precision guidance of ﬁeld vehicles on rough terrain at high speeds.

Mark Whitty is a Senior Lecturer in the Mechatronics discipline within the School of Mechanical and Manufacturing Engineering at UNSW Sydney, Australia. His research interest is focused around the development of tools for digital agriculture including yield estimation, data mining and the development of autonomous vehicles for use in unknown environments. He received his Ph.D. degree in Mechatronic Engineering in 2012 from the University of New South Wales.

Masami Hirayama is a design engineer from the bulldozer development division of Komatsu Ltd. His research interest is in automation for mining vehicles. He is also currently pursuing a Ph.D. in the School of Mechanical and Manufacturing Engineering at the University of New South Wales, Australia. He has a Bachelor’s and Master’s degrees in Mechanical Engineering from Nagoya University, Japan.

38