An optimized approach for automatic material distribution operations of bulldozers

Abstract

Komatsu Ltd. is reinforcing the research and development of automation technology for our bulldozers. Based on this trend, a methodology for optimized distribution of materials is proposed and developed for dumping area operations using bulldozers in this article. The aim of this work is to develop a robust methodology to contribute to the development of an autonomous system as possible so that it can be applied to our commercial machines immediately. The identified problem is that no formulation has yet been produced which can be applied to achieve such objectives. To develop the methodology, firstly, problem formulation of a specific scenario at the dumping area is presented. Secondly, integer linear programming is applied to solve the distribution problem. A hybrid method combining heuristics techniques and local branching is utilized to make this methodology capable of providing fast and reasonable solutions. Lastly, simulation results with specific different distribution requirements are presented to show that the developed methodology can derive optimized solutions for different requirements with a stable computational performance.

Introduction

With increasing demands and awareness from industries for enhanced safety, higher productivity, and better vehicle utilization, coupled with a labor shortage, automating outdoor ground vehicles is becoming more important. Among different types of work carried out at construction and mining sites, one of the most important processes that can be found at any kind of site is a dumping area operation because the site needs to be restored to a certain required state after the conclusion of the construction work or the main operation of mineral extraction. ^{1 –4} In addition, the cost related to waste dump management is one of the largest components of the operation which can account for 25–50% of the total operational costs. ⁵ For this reason, when attempting to automate construction and mining vehicles, dumping area operation is always a key element that requires substantial research effort. Focusing on this fact, the aim of this article is to develop a system that assists automation and optimization of dumping area operations.

A typical dumping area operation, edge dumping, is shown in Figure 1. Dump trucks transport waste material from other parts of the site over the edge of a dumping area. ^{6 –8} Once they are at the dumping area, they simply reverse closer to the dumping area edge and dispose the waste material near the edge. Some of the material self-falls over, while the rest still remains on the top of the dumping area. ⁸ One of the safety measurements is to restrict the distance that dump trucks can approach in relation to the edge, to prevent them from falling over. In such cases, the amount of remaining waste material on the top of the dumping area is more pronounced as the unloading position of dump trucks becomes further from the edge. The remaining waste material needs to be eventually pushed past the edge of the dumping area. Bulldozers are typically used for this purpose. It is this “dumping area operation” that is the focus of this article. It is apparent that, at sites where the dump trucks are automated or semi-automated, the distance between the unloading position and the edge is substantial and there is no self-falling over the material. As the majority of mining sites have yet to be equipped with autonomous products, in reality, common scenarios often seen are those with self-falling over the materials. However, as we aim to develop a methodology to contribute to a full autonomous system, this article assumes the scenario with no self-falling material, where there is a certain distance between unloaded material and the dumping area edge.

Figure 1.

Dumping area operation.

Figure 2 shows a top-down view of the dumping area. A circumstance that needs to be considered in this scenario is that, firstly, there is a gap between the location of material and the dumping area edge. Also, the profile of the edge is not homogeneous; hence, the closest distance varies along the edge. This fact, at the same time, creates another constraint where different locations along the edge profile may require different amount of the material, in relation to the requirement of having to form a certain specified terrain eventually. Thus, a certain pattern of material distribution along the edge profile and requirement for the final terrain shape needs to be considered. Another aspect to take into account is that, in most cases, the total volume of the remaining material typically exceeds the maximum capacity of the amount of material that a bulldozer can handle; therefore, a segmentation of the material is essential.

Figure 2.

Top view of dumping area. Bulldozers’ operation involves pushing the materials dumped by trucks past the dumping area edge. This article focuses on automating this operation.

Our review of literature suggests that linear programming is appropriate for distribution optimization. Figure 3 also shows the scope of this article focused on an optimal material distribution, as opposed to path planning. In the area of distribution problem, linear programming is commonly used. The following papers have shown novel problem formulation for specific industrial applications. Ouedraogo and Oki ⁹ have formulated a minimization problem of capacity requirements of traffic backup networks, under uncertainty, using linear programming. By rerouting the traffic in the case of a link failure in an existing network, their simulation results show up to 70% reduction in the spare capacity required for the backup networks. Aurora et al. ¹⁰ have developed an optimization solver that can be integrated with an industrial plate cut scheduling automation system. The solver is based on a mixed-integer linear programming (MILP). Another example of MILP was done by Rueda-Medina et al. ¹¹ by formulating the problem of optimal type, size, and allocation of distributed generators. On the other hand, if the variables are known to take only integer values, the problem can be specifically treated as ILP. ^{12 –14} Work done by Wang and Yang ¹⁴ is about the optimization of carriage for meeting the transport requirements to maximize the total profit of container shipping. Rezvani et al. ¹³ modeled the problem of resource allocation in the infrastructure as service clouds. Rahulamathavan et al. ¹² proposed an algorithm that optimally allocates adaptive radio resources to maximize the total data rates under interference power constraints. The distribution solvers of these three works ^{12 –14} are all based on ILP, and they are related to the problem in this article.

Figure 3.

Autonomous system framework. The highlighted section is dealt with in this article.

As can be seen, although different variations of linear programming can be considered depending on the problem, linear programming is very flexible and can be adapted to any sort of distribution problems. However, a formulation that best represents the problem is essentially necessary to apply the method and that is the most challenging part when applying linear programming.

This article introduces a novel formulation of material distribution for bulldozers to contribute to the development of an autonomous system for dumping area operations. In particular, this article presents a methodology to transport each split material segment to an optimized dumping point. The novelty lies in its simplicity and flexibility with different requirements, so that it can be immediately applied to commercial products. In the section, “System architecture,” a framework for developing an autonomous system for dumping area operations is proposed. Based on the system architecture presented, in the section “Problem statement and objective,” both the specific problem in scope to discuss in this article and the objectives are described. In the section, “ILP,” the general ILP problem which is used for the distribution optimization is recalled. In the section, “Formulation,” the material distribution problem is formulated in mathematical form, and ILP is used to achieve different distribution requirements. In the section “Simulation results and discussion,” simulation results involving three examples of optimization aims, based on bulldozer operators’ feedback and the performance of the developed distribution solver, are shown. Conclusions are presented in the last section.

System architecture

A highly beneficial autonomous system, for a dumping area application, should enable bulldozers to autonomously remove materials by only specifying the area which includes materials that need to be removed. As opposed to the conventional operation where operators manually determine material distribution, the 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 by terrain mapping, path planning, and navigation. ^{15 –17} An overall framework for developing an optimized autonomous system, for the scenario considered in this article, is shown in Figure 3.

The modeled terrain requires post-processing before being fed to path planning process. The post-processing is basically volume and shape estimation of the piles of material, segmentation, and distribution of the segmented materials. Terrain and material shapes can be adequately represented by polygonal approximations. ^{18 –22} One of the most common methodologies is Delaunay triangulation. ^{23 –27} An idea for this methodology is to maximize the minimum angle of all the triangles in the triangulation by ensuring the circumcircle associated with each triangle contains no other points in its interior. Once this is done, the material volume itself can be easily found using existing computational function to calculate the volume bounded by the convex hull. ^28,29 Therefore, material segmentation and distribution are the main focus, and the details are discussed in the section “Formulation.”

Problem statement and objective

As highlighted in Figure 3, the problem to discuss in this article is that no formulation has yet been produced which can be applied to the autonomous material distribution at a dumping area operation. Therefore, the objective of this article is primarily on developing the model and formulation for the optimization regarding such a scenario.

When automating a certain operation that has been done manually, the first thing to consider is what can be the objective function which best represents the scenario—in other words, what needs to be maximized or minimized. A formulation is achieved by understanding what a human operator is thinking while operating the machine. This is to be reflected in the objective function such as minimizing the travel distance, the processing time, the number of pushes, and so on. Also, the cost of moving materials needs to be represented in some way in conjunction with the formulation. However, what is prioritized to minimize or maximize typically depends on the person. For this reason, the formulation discussed in this article is developed in such way it can be flexibly applied to different given requirements. Those requirements are based on feedback from different operators who regularly operate bulldozers.

Integer linear programming

Linear programming is an optimization method that can be applied to problems where objective function and the constraints are formulated as linear functions. ³⁰ When all the variables are set to take only integer values in the optimization problem, it is called an ILP. A standard form of a linear programming problem is represented by

$\text{min}f(\mathit{X})={\mathit{C}}^T\mathit{X}$

1

subject to the constraints

$\mathit{a}\mathit{X}\le \mathit{b}$

2

$\mathit{X}\ge 0$

3

where C represents the cost matrix, X represents unknown decision variables to be solved via optimization, and a and b are constant matrices to represent constraints related to the decision variables X . Matrix dimensions, in this article, based on the formulation which will be discussed in the section “Formulation,” are shown in equation (4). m and n are denoted in Table 1. p is the number of constraints

$\begin{array}{ll}\mathit{X}\in \hfill & {ℝ}^{(m\cdot n)\times 1}\hfill \\ \mathit{C}\in \hfill & {ℝ}^{(m\cdot n)\times 1}\hfill \\ \mathit{a}\in \hfill & {ℝ}^{p\times (m\cdot n)\times 1}\hfill \\ \mathit{b}\in \hfill & {ℝ}^{p\times 1}\hfill \end{array}$

4

Table 1.

Symbols used in the formulation.

Symbol	Description
m	Number of edge points
n	Number of segments
cki	Cost from kth segment to ith edge point
xki	Decision value from kth segment to ith point
yi	Number of segments that the ith point can accept
V	Total volume of material

Typically, linear programming is solved using the Simplex method. However, the solution that can be obtained includes non-integer values; therefore, in the case of ILP, an additional step is required to ensure that the solutions are all integer. This is usually done using heuristics. This technique enables the solver to search the neighborhood of the current best integer feasible solution point to find a new and better solution, according to Danna et al. ³¹ Their work also shows that a hybrid method combining this technique and local branching effectively gives fast and reasonable solutions in many practical applications. Hence, the hybrid method is employed in this article.

Formulation

Formulation aim

The aim of formulating the problem is to assign each material segment to the best position along the cliff edge profile to meet the given requirements. The formulation for the distribution problem starts with discretizing the scenario. Figure 4 shows a schematic representation of the discretization of the scenario considered in Figure 2. Note that, in this simulation, the dumping area edge is assumed to be a smooth continuous curve that can be found in a real-life situation at mining sites. It is also assumed that the dumping area edge and material locations are given parameters. However, this proposed method is general and applicable to different edge profiles. In fact, in a real implementation, the estimation of the dumping area boundary is performed by another module, which processes 3-D mapping data. This is done prior to the planning process. ^{32 –35}

Figure 4.

Discretization of the dumping area operation.

The edge points are created on the cliff edge profile with an appropriate interval starting from edge point 1. What is meant by an appropriate interval is that the interval needs to be small enough to meet requirements. The requirements vary depending on customers; therefore, a detailed discussion with regard to particular values is not dealt with in this article. However, one example can be that the interval needs to be small enough to cover where the materials should be taken to and so on. Edge point 1 is set close to the first material segment along the profile. The material segments are numbered in increasing order from the bottom to the top. One assumption made here is that, as can be seen in Figure 2, as trucks dispose material near the edge, the material is assumed to be pushed toward one direction. Hence, a scenario such as a bulldozer starts pushing the material from somewhere between the edge and the material is not considered, as that kind of scenario is hardly seen at actual sites. The number of the material segments and the edge points are to be n and m, respectively.

In this section, the material segmentation is discussed in the subsection of “Material segmentation.” Also, the objective function that needs to be used in different cases is represented in the subsection of “Objective function.” Using the common objective function, three different requirements to seek optimization are considered for the formulation. The subsection of “Shortest distance constraint” shows constraints for simply the shortest distance. Uniform distribution and targeted distribution are also studied in the subsection of “Uniform distribution constraint” and “Targeted distribution constraint,” respectively. The symbols in Table 1 are used to present the problem formulation.

Material segmentation

Figure 5 shows one example of a material mound. Based on Figure 5, a simulated material mound is created as shown in Figure 6. One assumption made to create the simulated material mound is that the material will be split into a uniform direction. Considering the material needs to be segmented in the following process (Figure 3), it is efficient to take representative points forming the simulated mound profile where the segmentation plates will be. In that way, segmentation can be done simply by combining a certain number of small elements. As can be seen in Figure 6, the total mound consists of a set of small elements accumulated next each other in a uniform direction.

Figure 5.

Material mound.

Figure 6.

Simulated mound.

The pseudocode of algorithm 1 represents the segmentation approach. The basic idea is that while continuing to integrate the small element volumes, the segmenting position is determined at the point where it reaches the bulldozer’s blade capacity (V_c), taking into account the efficiency (α). Figure 7 shows the position of the segmentation plane in the example case from Figure 6. As can be seen, the distance between each plane becomes shorter for the larger depth portion of the mound and longer for the smaller depth portion of the mound.

Figure 7.

Material segmentation.

Algorithm 1.

Material segmentation pseudocode.

1:  Ni:= number of small element 2:  Vs:= summation of small element volume 3:  ve,i:= volume of ith small element 4:  Vc:= bulldozer’s blade capacity 5:  α:= bulldozer’s efficiency 6:  for i = 1 to Ni do        ⊲ // for all small elements 7:     $V_s:=V_s+v_{e,i}$ 8:    if $V_s>V_c\cdot \alpha$ then 9:       $V_s:=0$ 10:     segmenting position := i 11:   end if 12: end for

Objective function

In order to formulate the distribution problem, the cost matrix C from equation (1) is defined as follows. In equation 6, the value in the matrix $c_{ki}(k=1,\mathrm{2...}n)(i=1,2,\mathrm{...}m)$ represents a cost from kth material segment to ith edge point. Although any numerical value can be a value for a cost, traveling distance is set to be a cost for the sake of argument in this article. The value is calculated by Euclidean distance ^36,37

$\mathit{C}=\left[\begin{array}{ccccc}{\mathit{c}}_1& {\mathit{c}}_2& {\mathit{c}}_3& \dots & {\mathit{c}}_{\mathit{n}}\end{array}\right]$

5

where

$c_k=\underset{(k=1,2,\dots n)}{\left[\begin{array}{ccccc}{c}_{k1}& c_{k2}& c_{k3}& \dots & c_{km}\end{array}\right]}$

6

Also, the decision variable matrix X from equation (1) is defined as binary matrix as follows. The aim to use a binary vector is to derive decision solutions with the value 1, meaning being selected for the path between the designated set of a material segment and the edge point, or the value 0, meaning not being selected. Therefore, an inequality constraint is introduced to X

$X=\left[\begin{array}{ccccc}{x}_1& x_2& x_3& \dots & x_n\end{array}\right]$

7

$\begin{array}{ll}0\hfill & \le x_k\le 1\hfill \\ \hfill & (k=1,2,\dots n)\hfill \end{array}$

8

where

$\begin{array}{l}{x}_k=\left[\begin{array}{ccccc}{x}_{k1}& x_{k2}& x_{k3}& \dots & x_{km}\end{array}\right]\\ (k=1,2,\dots n)\end{array}$

9

$x_{ki}(k=1,\mathrm{2...}n)(i=1,2,\mathrm{...}m)$ represents the decision value for a path from kth material segment to ith edge point. If only the condition described in equation 8 is considered, $x_{ki}(k=1,\mathrm{2...}n)(i=1,2,\mathrm{...}m)$ can take a non-integer value; however, ILP is the methodology employed in this problem, and therefore, the values in the matrix $x_{ki}(k=1,\mathrm{2...}n)(i=1,2,\mathrm{...}m)$ are essentially either 0 or 1. If the value of x_ki is 1, that means the path between kth material segment and ith edge point is selected, and other values of x_ki for all the other k should be 0 unless it is specified to take one material segment to multiple edge points.

One constraint that needs to be applied in any case is to simply constrain one material segment to go to one edge point. This means one edge point can still accept multiple material segments; however, one material segment cannot be physically sent to multiple edge points. The constraint can be expressed as the following equation

${\displaystyle \sum _{i=1}^m}{x}_{ki}=1(k=1,2,\dots n)$

10

Three different constraints are identified and presented in this article. Those three constraints were defined based on a discussion with industry. This does not mean that the proposed methodology is applicable to only those three constraints; the three constraints are dealt with in this article only to demonstrate how the proposed methodology works. The proposed methodology is still applicable to other formulated constraints.

Shortest distance constraint

As in equation (1), the objective function already possesses a functionality to minimize the cost; hence, this case only requires constraint conditions to make the solver work. One condition to ensure the shortest distance is to simply constrain one material segment to go to one edge point. This constraint is already stated in equation (10).

Uniform distribution constraint

Provided that the dumping area face is already shaped to the required profile, one of the constraints to keep the face profile is a uniform distribution. If only the constraint expressed in equation (10) is considered, each material segment can go to any of the edge points; therefore, an additional constraint needs to be incorporated. The additional constraint for this case is to limit the number of material segments that each edge point is able to accept to 1

${\displaystyle \sum _{k=1}^n}{x}_{ki}\le 1(i=1,2,\dots m)$

11

Note that one condition that needs to be assumed in this case is that the number of edge points is more than that of material segments to ensure that the group of the edge points is capable of accepting all the material segments

$n\le m$

12

Targeted distribution constraint

Another scenario that frequently happens at an actual mining dumping area is that, the face is not uniformly shaped, because of occurrence of a slump, a sudden erosion, or flow slide after uniform shaping. ³⁸ In this case, variable distribution needs to be taken into account to specify a different amount of material to be sent to different location. As explained in the subsection of “Objective function,” the constraint as in equation (10) is still applied in this case. An additional constraint to realize a targeted distribution is to specify the number of material segments that each edge point can accept

${\displaystyle \sum _{k=1}^n}{x}_{ki}=y_i(i=1,2,\dots m)$

13

${\displaystyle \sum _{i=1}^m}{y}_i=n$

14

where y_i represents the number of material segments that the ith edge point can accept. Since each edge point can accept a multiple number of material segments, conditions that have to be assumed in the case as in the subsection of “Uniform distribution constraint” can be negated.

Simulation results and discussion

The credibility of the proposed formulation including the objective function and the constraint conditions was evaluated with simulation work. Primarily for the simulation, 10 edge points (m = 10) and 10 material segments (n = 10) are considered. First of all, as can be seen in Figure 8 to Figure 10, the distribution solver developed provides the solution that meets the different given requirements.

Figure 8.

Numerical solution: Shortest distance optimization. The target formulated by equation (10) is for a summation of each row to be all 1. The table in this figure shows that the actual solutions provided by the developed solver meet the required target.

Figure 9.

Numerical solution: Uniform distribution optimization. In addition to the same target as shortest distance (Figure 8), another target formulated by equation (11) is for a summation of each column to be all 1. The table in this figure shows that the actual solutions provided by the developed solver meet the required target.

Figure 10.

Numerical solution: Targeted distribution optimization. In addition to the same target as shortest distance (Figure 8), another target formulated by equation (13) is for a summation of each column to be as specified in the table. The table in this figure shows that the actual solutions provided by the developed solver meet the required target.

Figure 8 shows the distribution result in the case of shortest distance. The optimization aim in this case is to move each material segment to the closest edge point using the functionality of the objective function (equation (1)). The result shows that a feasible solution was obtained from this solver and it distributes each material segment as aimed; therefore, the constraint proposed in equation (10) is sufficiently plausible for the shortest distance case.

Figures 9 and 10 show the cases of uniform distribution and targeted distribution, respectively. The results show that optimized distribution solutions in these cases can also be retrieved according to a distribution specification. While the solutions meet the distribution requirements, the proposed solver provides the solution that still minimizes the distance between material segments and edge points, as the dominant objective function is based on equation (1). With the targeted distribution case shown in Figure 10, two material segments are specified to the edge points 1, 3, 4, 5, and 10 as a requirement for distribution (the number of the total material segments is 10). This is a typical case in a dumping area scenario. The requirement for reshaping the dumping area is to fill up the area which has less material compared to other areas. With this example, the area around edge points 6 through 9 already has surplus; hence, the material should be directed to another area. The simulation result clearly demonstrates that each material segment is distributed while minimizing the travel cost. Firstly, the two material segments at each end were sent to furthest edge points (the edge points 2 and 10). Secondly, the remaining problem is how to distribute six material segments (three through eight) to three edge points, and those six segments are evenly distributed to the three points with minimum travel cost, as can be seen in Figure 10. In order to clearly show the minimum cost has been obtained, Figures 11 and 12 show the cost optimization for “shortest distance” and “targeted distribution,” respectively. For each scenario, 10 random solutions were created including the optimal solution to compute the total cost. With the scenario of “uniform distribution,” there is no cost minimization, as there is only one solution which meets the required constraints. For this reason, the cost minimization is unable to be shown. Figures 11 and 12 show that the cost of the obtained optimal solution is minimal among all the cases; therefore, these results show that the minimum cost was obtained as a result of using the proposed methodology. The minimized values in Figures 11 and 12 correspond to those in Table 2. Moreover, solving times for each case are shown in Table 2. The result shows a stable computational performance. Although a different path is required for each case, and as opposed to the increment level of requirement complexity and path length, the variation of solving time difference is stable.

Figure 11.

Total cost optimization: Shortest distance. Case 10 is the optimal case. The remaining cases are solutions created taking into account randomness. Data are sorted in decreasing order.

Figure 12.

Total cost optimization: Targeted distribution. Case 10 is the optimal case. The remaining cases are solutions created taking into account randomness. Data are sorted in decreasing order.

Table 2.

Comparison of computational time results from different requirements (#: values are normalized by the values from constraint 1).

	Optimized path length minf( X )	Normalized path length (#)	Relative solving time (#)
Constraint 1: Shortest distance	415 (m)	1.00	1.00
Constraint 2: Uniform distribution	423 (m)	1.02	1.01
Constraint 3: Targeted distribution	498 (m)	1.20	1.02

Conclusions

In this article, the material distribution optimization problem for dumping area operations has been formulated and solved successfully using ILP. The formulation idea is based on minimizing the cost between material segments and edge points. The cost typically represents the distance between them. The simulation results demonstrate satisfactory performance to meet different requirements. By incorporating additional constraints, it is also validated that the proposed method provides a solution that satisfies the different specifications of distribution requirements as imposed by bulldozer operators. The cost for removing the material is minimized while meeting the different requirements; thus, the machine utilization is improved.

The future work will focus on planning a detailed path between material segments and the dumping area edges to move material segments, based on the distributed position provided by solutions from this proposed method. A path assumed in this article is a simple Euclidean path; therefore, the detailed path to be created may affect the distribution solution. However, it will be simply reflected to the values in the cost matrix; hence, the formulation developed in this article is still viable. Although a particular approach to plan a detailed path needs to be discussed, one leading candidate is trajectory optimization. In particular, a direct method is preferred with this type of scenario, as the path needs to be created using search algorithm. Also, accuracy is not as critical as other types of application, such as aerospace. Another factor that needs to be considered for path planning is material spillage. Typically, when bulldozers handle materials, a spillage is an unavoidable problem. Therefore, when discussing path planning, the algorithm to create a path that minimizes the material spillage is essential. The logic developed in this article assumes that the segmenting positions are known before planning a path. However, if segmentation planes may depend on the path to be planned, a novel hierarchical structure to best incorporate both the distribution algorithm and path planning will be sought.