FIELD OF THE INVENTION

The present invention relates to a method of estimating parameters of a medium to be moved by a digging apparatus, to a computer program product, to a digging apparatus and to a method of excavating a site.

BACKGROUND OF THE INVENTION

Excavation and digging apparatus is traditionally controlled entirely by humans and sometimes assisted by computer or other feedback controls. An operator sits in a cab and controls the excavator to move earth, aggregates and other materials. The job is repetitive, yet requires a high degree of skill by the operator if it is to be performed efficiently. The human operator can rely on a variety of stimuli including visual, tactile and sound combined with experience to excavate efficiently. The operator effectively infers the nature of the earth from the stimuli and may adjust excavation tactics accordingly. However, over time the operator may become fatigued and efficiency may drop. Also training operators to high experience levels is slow and expensive. Furthermore resources e.g. fuel may be used needlessly in applying more force with the apparatus than is actually needed to excavate or move the earth or other medium.

Autonomous excavation represents huge potential for virtually all earth- moving operations including construction, mining, agricultural, forestry, and military applications. Particular advantage is offered by autonomous excavation for clearing hazardous and/or toxic sites where human presence would be dangerous. The goal of autonomous excavation research is for excavation and digging apparatus to be self- controlled i.e. without human intervention.

Nevertheless, automation of the earthmoving process is a challenge for engineers and scientists due to the complexity of the real environment and replicating the control of an experienced human operator is difficult. The interaction between the soil and the bucket is of considerable importance and has been difficult to control effectively in autonomous applications due to the heterogeneity of the soil. Therefore the ability to model and validate the soil-tool interaction in real-time represents desirable goal for the automated excavation system. A real-time validation or estimate of the soil properties such as strength and resistance of the soil would allow a real-time determination of the forces acting on the bucket and this is essential for automated digging applications to establish a suitable control strategy.

Finite element analysis of the soil-tool interaction has been proposed. Whilst this would allow more accurate modelling, it does not permit real-time application due to its high computational overhead.

The Parameter Space Intersection Method (PSIM) is a graphical technique that has been proposed by Hong (W. J. Hong "Modelling, Estimation and Control of Robot-Soil Interactions", Ph.D. Thesis, Department of Mechanical Engineering, MIT, September 2001.) for the purpose of the robot-based Mars exploration. It uses tabular data of the predicted failure force using a single soil model. The PSIM is used to extract soil parameters from the soil model. However, the method is only capable of estimating two independent soil parameters at most due to the problem of dimensional complexity. Estimating more than two parameters will exponentially increase the memory usage and the estimation time due to the excessive computation requirements of tabular data. It will be appreciated that this method is of limited use for applications requiring more than two parameters in real-time.

In two papers (C. P. Tan, Y. H. Zweiri, K. Althoefer and L. D. Seneviratne, "Autonomous Excavation based on Soil Parameter Estimation", Proc. International Conference on Mechatronics, pp 557-562, June 2003; and C. P. Tan, Y. H. Zweiri, K. Althoefer and L. D. Seneviratne, "On-line Soil Property Estimation for Autonomous Excavator Vehicles", IEEE International Conference Robotics and Automation, Taipei, Taiwan, September 2003) we describe a method for estimating two of three unknown soil parameters (soil density γ, soil-tool friction angle δ, and soil-soil friction angle φ) using the Newton-Raphson method. In this method we extract the soil parameters from a soil model by minimising the difference between experimental data and the modelled failure force. The method has proved to be useable in real-time and provides accurate results. However, the method only estimated two soil parameters, whereas in reality (on an autonomous excavator for example) it is necessary to estimate all three (or more) unknowns. We have now devised further improvements with aim of enhancing our earlier estimation method, and in particular we have devised a method for determining all three unknown soil parameters. In doing so we have encountered and overcome problems that were not foreseen.

SUMMARY OF THE PRESENT INVENTION

Preferred embodiments of the present invention are based on the insight that it is possible to estimate three or more soil parameters, but that in some circumstances more than one model is necessary to accurately estimate this number of parameters.

According to the present invention there is provided a method of estimating parameters of a medium to be moved by a digging apparatus, which method comprises the steps of: - (1) receiving an electronic signal representing a failure force of the medium; (2) using said failure force to estimate with an electronic-processing means at least three parameters of said medium by numerical solution of a function dependent on said at least three parameters, which function provides a model of predicted failure forces of the medium under different actions of the digging apparatus; (3) comparing a predicted failure force obtained with that estimate of said parameters to said failure force; and (4) electronically controlling or assisting digging by said digging apparatus in response to said comparison to take advantage of the properties of the medium. Preferably, two specific functions are used one of which provides a model of the medium that assumes a substantially linear or planar failure surface, and the other of which assumes a substantially non-linear failure surface. The starting conditions of the failure force can be used to determine which function should be used for the estimation. In a particular embodiment two specific functions are used: the Mohr-Coulomb soil model (that assumes substantially linear or planar soil failure) and the Chen and Liu Upper Bound soil model (that assumes substantially non-linear soil failure). Advantageously, the method chooses one of the soil models to increase accuracy of results. However, the method of the invention is not limited to soils and may be applied to any medium to be moved in bulk including coal, aggregates, grain, sand, etc. One advantage of the method is that it may be applied substantially in real-time whereby the digging operation may be controlled in response to changing soil properties and to reduce energy consumption for example.

Advantageously, the method further comprises repeating steps (2) and (3) if said comparison indicates that a difference between said predicted failure force and said failure force exceeds a predetermined threshold, hi this way the accuracy of the estimate may be improved.

In one embodiment, steps (2) and (3) are repeated until the difference between said predicted failure force and the failure force is substantially minimised.

Preferably, step (2) comprises the step of substantially solving said function with said electronic-processing means.

Advantageously, said numerical solution is obtained by application of the Newton-Raphson method. This is particularly useful as the estimates are reached quickly, enabling employment of the method substantially in real-time. Furthermore the estimates are accurate within acceptable error (typically ±10% of the actual values of the parameters).

Preferably, the method further comprises the step of electronically guessing said at least three parameters to provide starting point values for said numerical solution, wherein said guess for each parameter lies within an upper limit and a lower limit based on values realised in practice. The applicant has found that this improves the accuracy and speed of the method.

Advantageously, the method further comprises the step of measuring the failure force of the medium with said digging apparatus and transmitting said failure force to said electronic-processing means. The failure force may be measured with a suitable force measuring means position on or adjacent a digging part of the digging apparatus. Preferably, the method further comprising the steps of inserting part of a bucket of the digging apparatus into the medium, applying increasing force to the medium with the bucket until the medium fails, and outputting electronic signals to said electronic processing means that represent a resistance applied to the bucket by said medium.

Advantageously, the method further comprises the step of obtaining the failure force from an electronic memory containing electronic data representing failure forces of media measured previously. Such data may be in the form of failure forces obtained experimentally on different media, or may be measurements taken within the previous few seconds, minutes or digs, on the medium on which the digging apparatus is working.

Preferably, step (1) comprises the step of receiving electronic signals representing at least three failure forces. This enables establishment of at least three independent equations to estimate the at least three parameters.

In one embodiment a number of failure forces received is equal in number to the number of parameters to be estimated. This enables establishment of the same number of independent equations to estimate the number of parameters.

Advantageously, each failure force was measured from different starting conditions.

Preferably, said different starting conditions are in terms of an angle between a digging part of the digging apparatus and said medium.

Advantageously, the method further comprises the step of adjusting a digging strategy with said electronic-processing means in response to said comparison. Such adjustment may be by digging faster or slower for example.

Preferably, the method further comprising the steps of applying said estimated parameters to said function to electronically estimate a substantially minimum failure force for said medium, estimating from said function parameters representing a starting position of said digging apparatus to dig the medium with said substantially minimum failure force, and digging said medium using said starting position to fail the medium with each dig.

Advantageously, said electronic-processing means stores at least two functions, each providing a model of predicted failure forces of the medium under different actions of the digging apparatus, which method further comprises the step of using said at least two functions to estimate said at least three parameters. In this way a hybrid soil model is effectively used to estimate the soil parameters whereby accuracy of the estimates is improved.

Preferably, the method further comprises the step of selecting one of said functions to estimate said at least three parameters, which selection is performed on the basis of a starting condition used to obtain said failure force. This may be done at the upper or lower limits of each function where accuracy is reduced and where another function provides more accurate estimates.

Advantageously, one function is used to estimate the parameters when said starting condition exceeds a threshold and another function is used to estimate the parameters when said starting condition is below said threshold.

Preferably, said starting condition is a position measurement of a digging apparatus relative to said medium.

Advantageously, said position measurement is an angle of a part of a digging apparatus whilst force is applied to fail said medium.

Preferably, the method further comprises the steps of outputting an electronic signal representative of the weight of a payload of the medium dug by the digging apparatus, using said parameters to determine with said electronic-processing means a volume of the payload, and storing a volume of the payload in an electronic memory. This has particular advantage for moving substantially homogeneous media (e.g. coal, grain aggregates) where it may be important to keep records of how much of the media has been sold for example. Advantageously, the or each function represents soil model that is stored in an electronic memory accessible by said electronic-processing means.

Preferably, the or each function is or is based on the Mohr-Coulomb soil model and/or the Chen and Liu Upper Bound soil model.

Advantageously, said at least three parameters include the soil-soil friction angle φ, soil-tool friction angle δ and soil density γ or other parameters representative thereof.

According to another aspect of the present invention there is provided a computer program product storing computer executable instructions in accordance with a method as aforesaid. The program may be embodied in a record medium, in a computer memory, in a read-only memory, or on an electrical carrier signal.

According to another aspect of the present invention there is provided a digging apparatus comprising or adapted for use with a computer program product as aforesaid. The digging apparatus may be a loader, a front-end loader, a track loader, a wheel loader, a multi-terrain loader, a backhoe, an excavator, an hydraulic excavator, or any other earth moving, mining or quarrying apparatus having a digging function.

According to another aspect of the present invention there is provided a method of excavating a site, which method comprises the steps of: (1) excavating the site with one or more digging apparatus; and (2) performing a method as set out above with at least one of the digging apparatus to assist in excavating the site. In one embodiment step (1) is carried out autonomously.

According to another aspect of the present invention there is provided a method of electronically controlling or assisting control of a digging apparatus, which method comprises the steps of estimating a parameter of the medium using a plurality of failure force data of the medium measured by the digging apparatus and a function modelling the physical properties of said medium by applying the Newton- Raphson method to substantially solve said function, and controlling the digging apparatus using said estimated parameter. This method may be combined with any of the aforementioned steps.

According to another aspect of the present invention there is provided a method of estimating parameters of a medium to be moved by a digging apparatus, which method comprises the steps of: - (1) receiving failure force data of the medium from the digging apparatus; (2) using said failure force data to estimate with an electronic-processing means a parameter of said medium by numerical solution of a function dependent on said parameter, which function provides a model of predicted failure forces of the medium; (3) comparing a predicted failure force obtained with that estimate of said parameter to said failure force; and (4) electronically controlling or assisting digging by said digging apparatus in response to said comparison to take advantage of the properties of the medium. Preferably the method is iterated repeatedly to provide a feedback loop for substantially real-time control of the digging apparatus. In this way the digging apparatus can adjust digging to meet changing soil properties for example. In one embodiment the numerical solution is by application of the Newton-Raphson method. Preferably at least two parameters are estimated, and preferably at least three parameters are estimated substantially simultaneously. This aspect of the invention may be combined with any of the aforementioned steps of the first aspect of the invention.

BRIEF DESCRIPTION OF THE FIGURES

For a better understanding of how the present invention may be carried out in practice, reference will now be made by way of example only, to the accompanying drawings in which: - Fig. 1 is a schematic side view of an earth moving apparatus in accordance with the present invention; Fig. 2 is a schematic representation of a control system for controlling the earth moving apparatus of Fig. 1; Fig. 3 is a schematic representation of the Mohr-Coulomb soil model; Fig. 4 is a schematic representation of the Chen and Liu Upper Bound soil model; Fig. 5 is a flow chart of a method according to the present invention; Fig. 6 is a schematic representation of a system according to the present invention; Fig. 7 shows graphs of the convergence of the estimation of three parameters of interest when applying a method according to the present invention; and Figs. 8 and 9 show five tables of results of various comparisons of experimental data and other estimation methodologies with the results obtained by a method in accordance with the present invention.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT

Referring to Fig. 1 a mechanical digger (or hydraulic excavator as it is sometimes known in the art) generally identified by reference numeral 10 comprises caterpillar tracks 12 (only one shown) and an upper part 14. In use, the upper part 14 is pivotable about a substantially vertical axis relative to the tracks 12. The upper part 14 comprises an engine (not shown), a cab 16 and a digging apparatus 18. If the digger 10 is autonomous the cab 16 maybe omitted.

The digging apparatus 18 is pivotally mounted to the upper part 14 of the digger 10 so as to enable movement of the digging apparatus in a substantially vertical plane. The digging apparatus 18 comprises a first arm 20 a proximal end 22 of which is pivotally mounted on the upper part 14 as mentioned. The first arm comprises two substantially straight parts disposed at approximately 120° to one another. A first end 26 of a substantially straight second arm 28 is pivotally mounted to a distal end 24 of the first arm 20. A bucket 32 is pivotally mounted to a second end 30 of the second arm 28. The digging apparatus 18 further comprises a number of electro-hydraulic actuators 34 for moving and holding the digging apparatus in position. The digging apparatus 18 is also provided with a number of position encoders (not shown) at each of its joints whereby the position of the bucket 32 may be known and monitored at all times by a control system.

In use, the electro-hydraulic actuators 34 may be controlled to move the digging apparatus 18 to perform an excavation operation for example. Movement of the bucket 32 is provided in two planes, a substantially vertical plane and a substantially horizontal plane. Referring to Fig. 2 the digger 10 further comprises computer-processing apparatus 36 in the form of a laptop (or notebook) computer or PC. For the purposes of the present invention it is not essential that the computer processing apparatus 36 comprise or be in communication with a display apparatus. The computer-processing apparatus 36 comprises a processor 38 that communicates with a RAM memory 40 under control of a clock 42. A port (not shown) on the computer-processing apparatus 36 enables electronic control signals and data to be sent between the processor 38 and an electronic control system 44 of the digger 10. The electronic control system 44 may be a separate computer processing apparatus that is built into or otherwise provided with the digger 10. Alternatively it may part of the computer- processing apparatus 36, for example in the form of software stored in the memory 40.

The electronic control system 44 communicates electronically with the electro-hydraulic actuation system 46 to control the digging apparatus 18. In use, the electro-hydraulic actuation system 46 sends command signals to the actuators 34 for controlling the digging apparatus 18. The command signals may be generated in response to operator commands from a control panel (not shown) in the cab 16 and/or from commands from the computer-processing apparatus 36. In a preferred aspect of the invention, the computer-processing apparatus 36 receives commands from an operator and controls the digging apparatus 18 in response thereto. In this way the operator is assisted by computer to enhance productivity and reduce consumption of energy for example. However, the invention will be applicable in autonomous digging apparatus where an excavation operation may be controlled almost entirely or entirely by computer.

As mentioned above, the digging apparatus 18 comprises a number of position encoders at its joints. The position encoders transmit electronic signals representative of the positions of the parts of the apparatus back to the electro- hydraulic actuation system 46 that in turn forwards the signals on to the electronic control system 44. The electronic control system 44 can then determine the position of the bucket 32 relative to the digger 10, and in particular can determine how far the bucket 32 has been inserted into the ground. Commercially available shaft encoders at the linkage joints of the digging apparatus 18 can be used for this purpose. The joint between the bucket 32 and second arm 28 is also provided with a one degree of freedom force (or pressure) sensor (not shown) that can measure the resistance of earth against the bucket. The force sensor generates an electronic signal representative of the force against the bucket during a digging operation that is sent back to the electronic control system 44. From here the signal is sent to the computer- processing apparatus 36 for use in the method of the invention. Such force sensors are commercially available. Alternatively the force may be measured through pressure sensors in the hydraulic actuators of the digging apparatus 18.

Referring now to Figs. 3 and 4 two soil models are used for estimating parameters of soil being excavated by digger 10 based on a soil failure force measured by the force sensor at the bucket 32. The two soil models are the Mohr- Coulomb model and the Chen and Liu Upper Bound model (CLUB). Both models are two-dimensional and assume that no soil escapes from the sides of the bucket 32 whilst digging. Furthermore the soil is assumed as homogeneous and isotropic and that a perfect plastic deformation of the soil occurs at failure.

The failure force of a soil can be defined as the maximum force required to "fail" a particular soil. Fig. 3 shows diagrammatically the Mohr-Coulomb soil model generally identified by reference numeral 50. A soil surface 52 is disposed at an angle β to the horizontal and the bucket 32 is assumed to be a plate in the model. The bucket 32 has been inserted a depth H into the soil at an angle a to the horizontal. Once in the soil, force is applied to the bucket in a horizontal direction (from left to right in Fig. 3). The force is gradually increased until the soil fails. In the Mohr- Coulomb model soil failure is assumed to take place in a plane containing and along the line be.

The soil model estimates the failure force based on the active soil force and passive soil force. These are the forces applied to the back of the bucket (e.g. by soil falling from the exposed face of the soil tending to push the bucket in the direction trying to fail the soil) and the force applied by the soil on the front of the bucket (generally in the opposite direction to the bucket), respectively. The failure force F of the soil may be expressed as F = FP - FΛ = ^γH2 {KP(a,β,φ,δ) - KΛ (a,β,φ,δ))

where Fp and FA are the passive and active force, γ is the density of the soil, H is the vertical insertion depth of the bucket, Kp and KA are the passive and active force coefficients, a is the bucket angle, β is the soil surface angle, φ the internal soil-soil friction angle, and S is the soil-bucket friction angle.

Equilibrium analysis of a wedge of soil 54 (identified by abc) reveals three main forces acting on it when the soil fails: weight W, the soil-soil friction force, and the soil-tool friction force. The passive and active forces, Fp and FA,, are derived using principles of static equilibrium. Fp is given by: -

where Kp is

FA, is given by: -

where KA is

with aA = π - a and βA = —β .

The second soil model (CLUB) is generally identified by reference numeral 60. The model employs a more complex and precise failure mechanism where the failure force is computed based on three individual regions 62, 64, and 66. The soil failure is force is determined by equating the external rate of work to the internal rate of energy dissipation. More details of CLUB can be found in W. F. Chen and X. L. Liu, "Limit Analysis in Soil Mechanics", Elsevier, Amsterdam, 1990. Region 62 is modelled as a triangular region with failure occurring along a straight line. This region is not affected by the interface friction between regions 64 and 66. Region 64 is also triangular. However, it is influenced by the interface friction at the wall of the bucket 32. Region 66 is a mixed or transition zone with a curved line of failure.

From analysis of the three regions the passive failure coefficient Kp is given by:-

where c stands for cos, s for sin, t for tan, b=3tan φ , angles p and ψ define the size

of regions 64 and 66 respectively.

The passive failure coefficient K^ is given by:-

with aA = π — a and βA = — β .

In order to find KA and Kp, optimization is conducted by the electronic processing apparatus on the variables p and ψ until the minimum value of KA and

Kp is determined. This is so that the model will predict the smallest failure force required to fail the soil under the model. The Nelder-Mead Simplex method is applied to find the values of p and ψ that minimise KA and Kp. Details of the Nelder-Mead Simplex method can be found in J. A. Nelder and R. Mead, "A Simplex Method for Function Minimization", Computer Journal, Vol. 7 pp308-313, 1965.

For both models, H and a can be determined from measurement by the position encoders on the digging apparatus 18 and bucket 32 as described above, β is measured using an inclinometer sensor on the digger 10. Once the properties of the soil γ , δ , φ axe known it is possible to determine Kp and KA and thereafter to predict from both models the minimum force to be applied by the bucket 32 to fail the soil. This information is useful as it would allow the digger to operate more efficiently for example.

However, in practice when excavating a site with the digger 10 the parameters γ , δ , φ cannot readily be determined. The parameters that can be measured on site by the digger are the failure force F of the soil, the depth of insertion of the bucket H, the angle of that insertion α, and β the angle of the slope.

Thus although both the Mohr-Coulomb and CLUB models can in theory predict of the failure force F of a particular soil, crucial soil parameters (relating to soil strength and resistance) are missing that are needed to enable such prediction to be carried out in practice. The method of the invention enables soil parameters to be estimated based on measured or experimental failure force data.

Referring to Fig. 5 a method according to the present invention generally identified by reference numeral 70 is stored in the memory 40 in the form of computer executable instructions. Prior to initiating the method the digger 10 is manoeuvred to a position ready for excavation. The digging apparatus 18 is operated (either by an operator or by the computer-processing apparatus 36) to bring a tip of the bucket 32 up to the earth surface. The tip of the bucket 32 (that typically comprises a substantially flat portion at its forward end) is inserted into the earth and brought to rest. At step Sl the position encoders on the digging apparatus 18 determine the angle α that the flat tip of the bucket makes with the horizontal, and the depth H that the tip has be inserted. Any angle β that the surface of the earth makes to the horizontal is also measured as described above. The values of α, β and H are sent electronically to the computer-processing apparatus 36 where they are stored in the memory 40.

At step S2 the digging apparatus 18 is operated to gradually increase the force applied by the bucket 32 to the soil. The force sensor outputs the measured force and this is recorded against time in the memory 40 by the computer-processing apparatus 36. Once the soil has failed the computer-processing apparatus 36 examines the data in the memory 40 to determine the peak force applied by the bucket 32 to the soil. This peak force represents the failure force of the soil under the starting conditions of the bucket 32. The peak force is stored electronically in the memory 40. Step S2 is repeated two more times with the angle of the bucket different on each occasion i.e. with different starting conditions. The result is three failure force readings for three bucket angles a stored in the memory 40.

At step S3 the angles a are examined. If all three a values are each less than or equal to 80° the Mohr-Coulomb model will be used to estimate the soil parameters. If all three a values are each greater than 80° tibe CLUB model will be used to estimate the soil parameters. This is because the applicant has realised that for estimation of three or more soil parameters, single soil models fail to estimate the soil parameters accurately over the practical range of a. Thus, selecting the soil model to estimate the soil parameters as a function of a the applicant has found that accuracy of results is increased as well as permitting three or more parameters of be estimated. In particular the applicant has realised that when attempting to estimate more than two soil parameters using their earlier approach, the strategy based on a single soil model failed to estimate the parameters accurately. The Mohr-Coulomb lost its accuracy when the tool (i.e. bucket) angle is too high (near or over about 80°). The applicant realised that this is because in the Mohr-Coulomb model, a planar failure surface extending from the tip of the tool towards the surface is assumed and this assumption is inaccurate at high tool angles.

Whilst three measurements of failure force with the bucket at different angles are sufficient for the two-model estimation approach of the invention whatever the angle of the bucket at which they were measured, it is preferred that three measurements are made in the range of angles where a particular model is most accurate. Thus if there are less than three a. values above or below 80° respectively then steps S2 and S3 are repeated until there are at least three values in either range. Once there are at least three a values in either range, the soil model to be used for estimating the soil parameters is chosen as described above. Li this way the method can be seen as a hybrid of two models that are switched based on the input data in order to generate more accurate estimates. In practical applications the typical range of angle a of the bucket 32 varies. For example backhoe excavators have 20°<α<120o for bulldozers a is approximately 90°; and front-end excavators have 300<α<800. Thus measurements of the failure force may be made at differing angles a according to the digging apparatus used.

Once steps Sl to S5 have been completed the method 70 proceeds to estimate the soil parameters γ , δ , φ . For the benefit of understanding, the theory behind the estimation process is presented below. As mentioned above the failure force for a particular soil can be expressed as:

F = FP - FΛ = ±γH2 {KP {a,β,φ,δ) - KΛ(a,β,φ,δ))

For a particular measurement of the failure force Fi by the digger 10, this equation can be expressed as:

For practical applications this may expressed as: ^ (φ.δ^, U1 )^ Q In other words the difference between a measured failure force Fj and the failure force predicted by the chosen soil model should be minimised. For n measurements of the failure force the problem to be solved is:

Each function /}.... fn can be approximated by a Taylor Series expansion as follows (for the first function only): Aγ

+ [Higher - order terms]. Similar expressions for functions /2 and /j can be obtained. In the method the higher order terms are neglected. The method will iterate to find the solution to each function and therefore it is desirable that the equation is linear in the delta terms. Note that the partial derivatives are evaluated at the estimates of γ ,δ ,φ and are therefore computable to a numerical value by the electronic-processing means 36. The matrix representation of the approximated functions is:

The Newton-Raphson method estimates roots of functions by estimating a solution and incrementally improving the estimate until the error falls below a given threshold. In terms of the soil parameters γ , δ , φ , to be estimated, the Newton- Raphson method says that a (k+l)th estimate of the solution is given by the Jcth estimate of the solution plus a small correction factor of the Mh estimate as follows:-

δ^D = δk + Aδk

Re-arranging the estimates and substituting for in the equation above

we can express the iteration to estimate γ , δ , φ as follows:

(2)

where k is the iteration index ranging from A= 1 , 2, 3 n.

To estimate the three soil parameters it is necessary to have at least three measurements of the failure force at different bucket angles 32 to generate three independent equations.

Referring again to Fig. 5, it will be recalled that the computer-processing apparatus 36 determined which soil model will be used to estimate the soil parameters based on the measurement of failure force by the bucket 32. Once the model has been chosen, initial values of the γ ,δ ,φ must be selected at step S6 to start the iteration process. These assumptions are based on practical, rather than theoretical experience. In particular, the applicant believes the range of possible soil density γ of any soil is between 500kg/m3 and 3000kg/m3. The soil-soil friction angle φ lies in the range ~10° and ~70° which is to be found in most soils. The soil- tool friction angle δ is in the range -10° and ~60° and should not exceed the soil- soil friction angle due to invalidity of the model. The applicant has found that, providing the estimates lie in the ranges to begin with, the iterations very quickly converge to the solution.

The iteration begins at step S7 when k is set equal to one i.e. the first approximation. At step S 8 the first estimated numerical values of Y1 , S1 , φx are input

into the equation (2) above to determine a second estimate Y2 ,δ2,φ2 . It is to be noted that the various functions representing the two models and their partial derivatives are stored in the memory and are readily numerically determined by the processor 38 at the estimated values of Y, δ ,φ . At step S9 the second estimate is used in the chosen soil model (Mohr-Coulomb or CLUB) to determine the theoretical failure force FEST of the soil for the parameters Y2 , δ2 , φ2 at each angle CC1 , (X2 , CC3 of the actual failure force measurements. At step SlO each estimated failure force is subtracted from the corresponding measured failure force to determine how close to zero the difference is. At step SIl the three differences are examined and each is below a threshold (which can be 1x10" and 1x10" in practical applications) the computer-processing apparatus 36 determines that the soil parameters have been estimated within an acceptable tolerance at step S12. If the differences are not below the threshold the iteration is repeated by setting k=k+l at step S 13 and using the estimates T2,δ2,φ2 to generate a third estimate. This loop repeats until the differences between predicted and measured values fall below the threshold as described above.

Fig. 6 is a schematic representation of the method of Fig. 5.

One particular advantage of this method is speed of results. Referring to Fig. 7 graphs of the estimates of γ , δ , φ against number of iterations are generally identified by reference numerals 80, 90 and 100. It is readily apparent how quickly the estimates converge on the solution, even by the first iteration. By the sixth iteration all three parameters were within the specified error threshold of 1 x 10"10.

Referring to Fig. 8 three tables of results of comparisons of the present invention with actual measurements are identified by reference numerals 110, 120 and 130. Table 1 110 shows a comparison between the estimated soil parameters and measured soil parameters of Ticino soil. It is apparent that the estimated soil parameters are either within the measured range or are very close to the measured range.

Table II 120 shows a comparison between the estimated failure force and the measured failure force for tool angles in the range 70° to 90°. The table shows that the estimated results are in very good agreement with the measured results.

Table III 130 shows a comparison of the method of the present invention with the Least Square Method. The soil had actual parameters of φ=40°, γ=1600kg/m3, (5=28°. Both the method of the invention (referred to as the "Hybrid Soil Model") and the Least Square Method were started at differing initial guesses of the parameters to see how quickly and if they converged on the correct solution. The method of the invention converged in each case, whereas the Least Square Method converged only when the initial guess is near to the solution. Thus the method of the invention is robust and has the advantage that no particular attention needs to be paid to the initial guess. The parameters as estimated by a method in accordance with the invention were φ=40.09°, f=1598.4kg/m3, δ=27.57° i.e. very close to the actual values. The average time taken for the Hybrid Soil Model to converge on a solution was 1.7s, which is a factor of 140 times faster than some earlier estimation methods that took 4 minutes. Thus the Hybrid Soil Model and method of implementation have real-time capability.

In order to evaluate the method of the invention, the estimation for three soil parameter using a single soil model (both the Mohr-Coulomb and CLUB) over all bucket angles was compared with the present methodology. Fig. 9 shows two tables 140 and 150. Table IV 140 shows a comparison of the estimation using a single soil model and the Hybrid Soil Model to estimate three soil parameters. In both single soil model cases, there was no convergence on a solution. The applicant believes that this is because the Mohr-Coulomb soil model predicts failure incorrectly at high tool angles (greater than approximately 80°). As a result the difference between the experimental failure force and the predicted failure force could not be minimised to zero. However, Table IV 140 shows that employment of the Hybrid Soil model in combination with the Newton Raphson method permits the soil parameters to be estimated across the practical range of tool angles (about 30° to about 85°), and the estimation to be performed quickly and accurately.

The Hybrid Soil Model was also evaluated using the single soil models, estimating two soil parameters in this case δ and γ at a bucket angle of 70° and 90° respectively. Table V 150 shows the results. The Mohr-Coulomb model is fast, reaching a result in 0.15 s. However, the results are inaccurate. The CLUB model has good accuracy, but the method is too computationally expensive, taking 6.85s. The Hybrid Soil Model is both fast and accurate making it suitable for real-time application.

Once the soil parameters /,δ ,φ have been estimated to an acceptable tolerance they can be used in either or both soil models to determine the bucket angle OC at which the failure force is minimum for that particular soil, for example. This can then be used to ensure that the digger 10 operates more efficiently (e.g. by applying force at best tool angle so that the soil fails at minimum or low force) and there is less wear on the parts of the digger 10. In this way the cost of the excavation can be reduced. The method is very robust compared to other known methods (e.g. Least Square) and would be of great assistance in autonomous excavation applications with unpredictable soil conditions. Furthermore the method allows the digger 10 to continue the digging process without having to pause while soil parameters are identified. As employed above, the Newton Raphson method is not computationally expensive, does not have difficulty with saddle-point solutions and non-optimal local minima and is not sensitive to measurement noise.

As an alternative step in the method shown in Fig. 7, the soil parameter estimation may be applied carried out simultaneously or in turn on both models, rather than choosing a particular model by bucket angle. To add further robustness the actual failure force could be measured at numerous tool angles so that the parameters could be estimated by both soil models in parallel and the results compared and/or combined.

The invention is not limited to the Mohr-Coulomb and CLUB models. Estimation of three or more parameters may be carried out by selection of any suitable and any number of soil models used in combination to generate a hybrid model. In particular other soil models presently available are:- (1) Ohde's Logarithmic spiral method (see K. Terzaghi, "Theoretical Soil Mechanics", John Wiley and Sons Inc., New York, 1943); (2) Caquot and Kerisel's Earth Pressure Table (see A. Caquot and, J. Kerisel, "Table for the Calculation of Passive Pressure, Active Pressures, and Bearing Capacity of Foundations", Paris-Imprimerie Gauthier-Villars, 1948); and (3) Numerical Limit Analysis (finite element analysis) (see B. Ukritchon, A. J. Whittle, and S. W. Sloan, "Undrained limit analysis for combined strip footing in clay", Journal of Geo technical and Geoenvironmental Engineering, 124(3): 265- 276, March 1998).

Any of these models could be used with either the Mohr-Coulomb model or the CLUB model. However, the combination of Mohr-Coulomb and CLUB is preferred because Mohr-Coulomb has less computation time and is accurate enough at low tool angles. CLUB is the most accurate at high tool angles and is not prohibitively expensive in terms of processing time. For tool angles lower than 80°, the Mohr-Coulomb soil model and Ohde's Logarithmic spiral method compute the results close to the experimental data. However, Ohde's Logarithmic Spiral method is not ideal because it requires optimization in the soil model equation to compute failure force that takes more computation time compared to Mohr-Coulomb soil model. Caquot and Kerisel's Earth pressure table (3) and Chen and Liu Upper Bound soil model (4) provide a more accurate result compared to Ohde's Logarithmic spiral method and Mohr-Coulomb soil model at high tool angles (more than 80°). Numerical Limit Analysis (Finite Element Analysis) (5) is not suitable as it needs excessive computation power to compute the failure force.

The methodology of the invention may be employed to assist human-operated machinery or may be employed in autonomous applications. It may also be applied to assist movement of aggregates, coal, grain and any other material that is handled in bulk by backhoes and the like. Furthermore, in such an application, once the parameters of the medium have been estimated it is possible to determine the volume of medium that has been captured by the bucket that can be important for record keeping purposes.

The present invention has application in excavation operations from the smallest to the largest scale in construction, agriculture, military, toxic disposal, and space exploration.

The computer-processing apparatus 36 may be built into the digging apparatus.

As used in the appended claims the term "medium" is intended to include any bulk solid that may be excavated and/or moved by the type of machinery mentioned herein and "soil" is intended to include any part of the earth's surface that may be excavated, mined, moved, etc. The term "bucket" (generally a term of art) may mean the device carried by the digging apparatus for the purposes of digging and moving the medium. Usually such a bucket comprises a substantially planar portion for penetrating the medium and a container portion thereadjacent for holding part of the medium that has been "scooped" up. A fUrther embodiment of the invention will now be described, which provides for four soil parameters to be estimated. In this estimation scheme, the given geometrical properties are the height of the bucket, H, the angle of the bucket with respect to the horizontal axis, ce, and the angle of the soil surface, β. The soil parameters to be identified are the soil density, γ, the soil-tool friction angle, δ, the soil-soil friction angle, φ, and the soil cohesion, c.

Independent equations are required in order to extract the unknown parameters effectively. These equations are generated by measuring the failure forces at discrete tool angles. Here, four equations are generated based on the experiments at four different tool angles (a , a a and a ) for four unknown soil parameters (φ, δ, γ and

c).

The estimation method of this further embodiment then works by incrementally improving the guess until the difference between the measured failure force and the modeled failure force is minimized and hence the soil parameters are identified, and hence is substantially the same as the three-parameter estimation scheme described previously, but with differences in the equations used for the parameters, and the estimation method, as described below. Generally, however, the estimation method follows the processing steps described previously and shown in Figure 6.

Generally, the Newton Raphson method is an iterative method used to solve nonlinear algebraic equations. To obtain a solution, an initial guess, which is based on a-priori knowledge of the problem, is used to start the estimation process. The solution is reached by incrementally improving on the initial guess until a predefined performance measure (here, the difference between the measured failure force and the modeled failure force) falls below a given threshold. The function to solve the soil parameter estimation problem is expressed as follows:

where φ, δ, γ and c are the unknown soil parameters to be estimated. The function of the failure force is computed by the soil model which is expressed applying different tool angles, a\, o2, o3 and aA. Then the unknown soil parameters are expressed in terms of an estimation of the solution and a small correction factor:

where A: is the iteration index ranging from 1, 2, ..., n. The Taylor Series expansion is used to approximate the nonlinear equations of the functions. The expression for the soil parameters with the estimation can be written as follows:

As described above, when estimating three parameters the Newton Raphson method was used. However, in the presently described embodiment when attempting to estimate four unknown soil parameters (adding cohesion, c) using the same approach, the previously described Newton Raphson estimation strategy, although possible to be used, is not as accurate at estimating four soil parameters, and in some cases, depending on the starting values chosen, may not converge to a suitable estimation.To overcome this, a Modified Newton Raphson Method is proposed where the conventional Newton Raphson method is improved to estimate more unknown soil parameter accurately.

In the Modified Newton Raphson method, the iteration of the method is divided into two sections. In a first section estimation of two soil parameters, (δ and γ) is carried out. The estimated parameters (δ and γ ) then become the initial conditions of another parameter estimation scheme (second section) where the third and fourth parameter (φ, c) are estimated. The estimated parameters from the second section then become the initial conditions for the first section. The first and second sections are then subsequently iterated in turn with new estimates of parameter being performed using the estimated parameters from the previous iteration of the alternate section. The parameters are estimated ultimately when the errors of functions from both sections are minimized.

The estimation of two parameters has a higher success rate of convergence than estimating four parameters. This strategy therefore improves the convergence of the estimation method where four parameters estimation is divided into two sections. Although the speed of convergence is decreased compared to the previously described Newton Raphson method (due to more iterations needed to identify the parameters), the results show that the Modified method is able to estimate the parameter accurately with high speed.

In the present embodiment, in view of the fourth cohesion parameter added over what was described previously, a different soil failure force model is preferably used, which makes use of the c parameter. Here, the soil failure force is computed as:- F = Fr -Fx

where F A and F A are the resulting passive force and the active force respectively, K Jr and K A are the passive and active force coefficients respectively, with other parameters being as defined previously. In this respect, , K Ir and K A derive from the particular soil model (CLUB, or Mohr-Coulomb) used, and are the same as described previously for the three parameter estimation. With such changes to use the Modified Newton-Raphson method and the above equation for soil failure force, the execution process to find the soil parameters is substantially the same as described previously with respect to Figure 5, and in particular in the use of the Hybrid soil model to choose between the CLUB or Mohr- Coulomb models. It will be recalled from the previous discussion, however, that it is necessary to seed the estimation with parameter values derived from a priori knowledge of likely soil conditions. Likely ranges of soil density, soil-soil friction angle and soil-tool friction angle were given previously, and which can still be used in the four parameter estimation. Likely ranges of the soil cohesion parameter c range from OkPa to 5kPa for wet sand, up to 2OkPa for clay. With such extra information, the execution process is the same as that described previously with respect to Figure 5, but with a change to step 56 to also guess soil cohesion within the a priori range, and a change to step 58 to apply the Modified Newton Raphson method as discussed above to estimate the four parameters. Test results for the four parameter estimation model using the Modified Newton Raphson estimation will be discussed later.

It was mentioned previously that instead of applying the hybrid execution model which selected the soil model to be used in dependence on bucket angle (referred to above as the hybrid soil model) the two available soil models may also be used in other ways, and in particular may be applied in parallel or in turn. Next we describe two further execution models which may be used to apply the two available soil models (being the CLUB and the Mohr-Coulomb models) to the estimation. A first alternative execution model is the parallel execution model (PEM). In the Parallel Execution Model, the measured failure force obtained from the sensor at a certain geometrical state (bucket insertion depth, H, soil surface angle, β, and bucket angle, a), is compared to the failure force computed by two soil models using a similar geometrical state. The soil model that computes the lesser force difference between the modeled and measured results is then selected to compute the failure force in the estimation scheme. This can ensure the selected soil model computes the forces at higher accuracy and the soil parameters can be estimated using the soil model that can better approximate the environment

One implementation of such a parallel execution model is to run both models in the first iteration, and calculate the estimated failure force from the parameters generated by both models. The model whose failure force estimation is then closest to the measured failure force is then selected for use in the subsequent iterations to find the estimations within the required thresholds.

A second execution model is a flexible parallel execution model. The principle of the Flexible Parallel Execution Model (FPEM) is similar to the PEM but higher accuracy approximation of the environment soil is achieved. This strategy selects the soil model that computes the lowest force difference between the measured and modeled one in each of the estimation iterations. Hence, the amount of times a soil model is selected is directly proportional to the number of iterations required to identify the soil parameters. This strategy provides better environment approximation at each of the iteration in the estimation process and ensures the unknown parameters to be estimated more accurately.

An implementation of the flexible parallel execution model is to run both soil models in the first iteration, and then compare the resulting failure force estimation from each model with the measured failure force. The output estimates from the model whose estimate is closest to the measured failure force are then chosen as the input estimates to the next iteration. In the next iteration both models are then run again with the output estimates from the previously chosen model as input estimates, and further output estimates are obtained from both models. Respective failure force estimates are then obtained, and the set of estimates that gave the closest failure force estimate to the measured failure force estimate is chosen as input for the next iteration. The process is iteratively repeated with both models being run each time, and one set of parameter estimates being selected as input to the next iteration, until the estimates converge to the desired thresholds.

It should be noted that any of the Hybrid execution model (HEM), PEM, or FPEM may be used with either of the three or four parameter estimation schemes described herein. Below we present test results of the four parameter estimation scheme, when run according to each of the HEM, PEM, or FPEM.

The different execution models were tested on wet Leighton Buzzard soil having the measured characteristics shown in the Table (Table VI) below:-

THEMEASOEEDFALCUSEFORCES Ai» MEASURED SO-LEAItAMEIERS FOR WET LEIGHTOH BuZZAKD SOIL

The initial conditions for φ, δ and γ, based on a-priori knowledge of the soil were provided before the estimation procedure is started. In this test, the a priori values were set in the ranges as follows: soil-soil friction angle, φ, should be in the range between 10° and 50°; soil-tool friction angle, δ, is between 10° and 40° and should not exceed the soil- soil friction angle, since otherwise the model becomes invalid; 3 3 soil density, % is in the possible range between 500kg/m and 3000kg/m ; and soil cohesion, c, ranged from OkPa to 5kPa for wet sand and up to 2OkPa for clay. With these a priori inputs, the estimation results of the MNRM (i.e. the four

parameter model) using the PEM, FPEM and HEM are shown in Table VII below.

The initial conditions used in the estimation are φ = 30°, γ= 2000kg/m , δ = 20°, c =

3kPa.

THE ESmaTH>am.PAR.4MEIEES ϋSMG-MODMED MEWIOS SAEBSON METHOD

The results show that the estimation using the MNRM with the FPEM and HEM

estimate the parameters with higher accuracy compared to the PEM. Lesser time is

needed for the HEM to estimate the parameters compared to the other model

selection strategies. Hence, the HEM proved to be a better technique to select the soil

model in the estimation scheme with its fast and accurate estimation.