Learning system and method for optimizing control of autonomous earthmoving machinery

• US 6,076,030 A
• Filed: 10/14/1998
• Issued: 06/13/2000
• Est. Priority Date: 10/14/1998
• Status: Expired due to Term

• Current Assignee: Carnegie Mellon University
• Original Assignee: Carnegie Mellon University
• Inventors: Rowe, Patrick S.
• Primary Examiner(s): Cuchlinski, Jr., William A.
• Assistant Examiner(s): Donnelly, Arthur D.
• Application Number:
  US09/173,074
• Time in Patent Office: 608 Days
• Field of Search: 701/50, 701/207, 37/348, 37/414, 172/4.5
• US Class Current: 701/50
• CPC Class Codes: E02F 3/435 for dipper-arms, backhoes or the like
• CPC Class Codes: E02F 3/438 Memorising movements for repetition, e.g. play-back capability
• CPC Class Codes: E02F 9/2033 Limiting the movement of frames or implements, e.g. to avoid collision between implements and the cabin sub-groups of E02F3/431 of E02F3/435 take precedence; for turntables E02F9/123
• CPC Class Codes: E02F 9/2045 Guiding machines along a predetermined path for graders E02F3/841; machines for construction of roads E01C19/004
• CPC Class Codes: E02F 9/245 for preventing damage to underground objects during excavation, e.g. indicating buried pipes or the like detection of pipes in the ground F16L1/11
• CPC Class Codes: G05B 13/0265 the criterion being a learning criterion
• CPC Class Codes: G05B 19/19 characterised by positioning or contouring control systems, e.g. to control position from one programmed point to another or to control movement along a programmed continuous path
• CPC Class Codes: G05B 2219/33032 Learn by changing input weights as function of position error

Abstract

In one embodiment of the present invention, a motion planning algorithm is used to control an autonomous machine. The motion planning algorithm consists of a template or script which captures the general trends of the motion, while parameters in the script are filled in with the kinematic details for a specific machine and set of movements. A learning algorithm computes the script parameters by using feedback of how the machine performed during the preceding cycle with the current parameter set, and adjusting the parameters to improve the machine'"'"'s performance during succeeding work cycles. The new parameters are evaluated by the learning algorithm using a predictive function approximator to test various performance criteria such as the time required to perform a task and the accuracy with which the task was performed. The performance criteria are weighted using local regression techniques so that the prediction of the outcome of alternate motions places emphasis on the performance criteria that is considered most important. As data from repeated motions accumulates, the algorithm uses the history of the results of various motions to recompute and refine the parameters to improve performance.

Claims

1. A method for controlling automated movement of an earthmoving machine having a plurality of links connected at joints that are operable to move concurrently based on commands generated using at least one script, each script including at least one variable parameter defining a movement of the machine, the method comprising the steps of:

determining at least one desired outcome from a number of desired outcomes;

measuring conditions in the machine'"'"'s environment pertaining to each desired outcome;

determining a candidate value for at least one variable parameter from a number of potential candidate values using a learning algorithm before executing the script in which the variable parameter is used; and

predicting the desired outcome of the candidate value prior to executing the script in which the variable parameter is used with the candidate value being selected based upon the determined desired outcome.

2. The method as set forth in claim 1 wherein the candidate value for each variable parameter is a predetermined value that is used during initial execution of at least one script, the method further comprising the steps of:

storing the measured conditions during at least one execution cycle; and

storing the candidate value used for each variable parameter during at least one execution cycle.

3. The method as set forth in claim 2 wherein the learning algorithm comprises the step of:

executing a function approximator to evaluate each candidate value by predicting the outcome using at least one stored value for each variable parameter and at least one of the stored measured conditions from at least one execution cycle.

4. A method as set forth in claim 3 wherein the learning algorithm further comprises the step of:

optimizing a cost function that is dependent on at least one variable representing the desired outcome and at least one corresponding data value from the actual measured conditions.

5. The method as set forth in claim 4 wherein executing the function approximator further comprises the step of:

predicting the outcome of the machine action using a weighted regression algorithm, the weights being computed using an exponential function that is dependent on the difference between at least one stored variable parameter and the candidate value.

6. The method as set forth in claim 5 wherein the step of executing the function approximator includes using a locally linear function to approximate a segment of the response.

7. The method as set forth in claim 5 wherein the step of executing the function approximator includes using a locally quadratic function to approximate a segment of the response.

8. A system for controlling automated movement of a machine comprising:

a machine having a plurality of links connected at joints that are operable to move concurrently based on commands;

a processing system for executing at least one script, each script including at least one variable parameter defining a movement of the machine; and

a learning algorithm operable to modify values of at least one variable parameter based on a desired outcome of the machine'"'"'s action and conditions measured in the machine'"'"'s environment pertaining to the desired outcome and predicting the desired outcome of the machine'"'"'s action prior to executing movement of the machine with the desired outcome being selected based upon a number of desired outcomes.

9. The system as set forth in claim 8 wherein at least one candidate value for each variable parameter is a predetermined value that is used during initial execution of at least one script, the system further comprising:

data storage means for storing the measured conditions during at least one execution cycle and for storing the value used for each variable parameter during at least one execution cycle.

10. The system as set forth in claim 9 wherein the learning algorithm comprises:

a function approximator to evaluate the at least one candidate value for modifying at least one variable parameter by predicting the outcome using at least one stored value for each variable parameter and at least one of the stored measured conditions from at least one execution cycle.

11. The system as set forth in claim 10 wherein the learning algorithm further comprises:

a cost function that is dependent on at least one variable representing the desired outcome and at least one corresponding data value from the actual measured conditions.

12. The system as set forth in claim 11 wherein the function approximator further comprises:

a weighted regression algorithm for predicting the outcome of the machine action, the weights being computed using an exponential function that is dependent on the difference between at least one stored variable parameter and the candidate value.

13. The system as set forth in claim 12 wherein the function approximator further includes using a locally linear function to approximate a segment of the machine'"'"'s response.

14. The system as set forth in claim 12 wherein the function approximator further includes using a locally quadratic function to approximate a segment of the machine'"'"'s response.

15. The system as set forth in claim 8 further comprising at least one fixed instruction for controlling the movement of the machine.