US6108949A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for determining an excavation strategy
Assignee: Carnegie Mellon University
•
Filing: 1998-10-14
•
Granted: 2000-08-29
•
Expires: 2018-10-14
Abstract
Abstract In one embodiment of the present invention, a planning system and method for earthmoving operations such as digging a foundation or leveling a mound of soil is disclosed including three different levels of processing for planning the excavation. One of the processing levels is a coarse-level planner that uses geometry of the site and the goal configuration of the terrain to divide the excavation area into a grid-like pattern of smaller excavation regions and to determine the boundaries and sequence of excavation for each region. The next level is a refined planner wherein each excavation region is, in order of the excavation sequence provided by the coarse planner, searched for the optimum excavation that can be executed. This is accomplished by choosing candidate excavations that meet geometric constraints of the machine and that are approximately within the boundaries of the region being excavated. The refined planner evaluates the candidate excavations using a simulated model of a closed loop controller and by optimizing a cost function based on performance criteria such as volume of material excavated, energy expended, and time, to determine the optimal location and orientation of a bucket of an excavator to begin excavating the region. The third level of the excavation planner is a control scheme wherein the selected excavation is executed by a closed loop controller that controls execution of a commanded excavation trajectory by monitoring forces exerted on a bucket, stick, and boom on an excavating machine.
Inventors
- 👤 Sanjiv Singh
- 👤 Howard Cannon
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-03 14:40
CPC Classifications
E; E02; E02F; E02F9/00; E02F9/20; E02F9/2025; E02F9/2045; E02F3/00; E02F3/04; E02F3/28; E02F3/36; E02F3/42; E02F3/43; E02F3/435; E02F3/437; E02F9/26; E02F9/261; E02F9/262
Claims Analysis
Total Claims: 33
Claim 1
Independent Claim
122 words
A method for planning earthmoving operations using a terrain map of an excavation area, and an excavator having a work implement comprised of a bucket, stick, and boom linked together in sequence and movably actuated by hydraulic cylinders, the method comprising the steps of: (a) dividing the excavation area into a plurality of excavation regions using expert heuristics; (b) determining at least one candidate location of the bucket for starting an excavation for each excavation region; (c) predicting an excavation result of each candidate location; (d) determining a level of quality of the predicted excavation results by evaluating at least one performance parameter; and (e) selecting a starting location as a function of the level of quality of the predicted excavation results.
Claim 2
Independent Claim
122 words
A method for planning earthmoving operations using a terrain map of an excavation area, and an excavator having a work implement comprised of a bucket, stick, and boom linked together in sequence and movably actuated by hydraulic cylinders, the method comprising the steps of: (a) dividing the excavation area into a plurality of excavation regions using expert heuristics; (b) determining at least one candidate location of the bucket for starting an excavation for each excavation region; (c) predicting an excavation result of each candidate location; (d) determining a level of quality of the predicted excavation results by evaluating at least one performance parameter; and (e) selecting a starting location as a function of the level of quality of the predicted excavation results.
Claim 3
Dependent Claim
43 words
The method as set forth in claim 1 wherein step (a) further comprises dividing the excavation area into a plurality of excavation regions within a cylindrical coordinate frame, and determining radial extents of the excavation regions based on kinematic constraints of the excavator.
Claim 4
Dependent Claim
33 words
The method as set forth in claim 1 wherein step (a) further comprises assigning a sequence number to each excavation region corresponding to the order in which the region is to be excavated.
Claim 5
Dependent Claim
29 words
The method as set forth in claim 1 wherein step (b) further comprises determining a candidate location of the bucket to clean up the floor of the excavation region.
Claim 6
Dependent Claim
26 words
The method as set forth in claim 4 wherein step (c) further comprises using a feed-forward model of the excavation process to predict the excavation result.
Claim 7
Dependent Claim
28 words
The method as set forth in claim 1 wherein step (b) further comprises determining a new position for the excavator before selecting a candidate location of the bucket.
Claim 8
Dependent Claim
35 words
The method as set forth in claim 6 wherein step (d) further comprises determining the level of quality of the predicted excavation results by evaluating the amount of time required to complete the predicted trajectory.
Claim 9
Dependent Claim
23 words
The method as set forth in claim 1 wherein step (b) further comprises determining an orientation of the leading edge of the bucket.
Claim 10
Dependent Claim
49 words
The method as set forth in claim 8 wherein step (c) further comprises using a simulated model of a closed loop controller to predict the trajectory of the work implement during excavation based on the starting location and orientation of the bucket and characteristics of the material being excavated.
Claim 11
Dependent Claim
32 words
The method as set forth in claim 1 wherein step (d) further comprises determining the level of quality of the predicted excavation results by evaluating the energy expended in completing the excavation.
Claim 12
Dependent Claim
36 words
The method as set forth in claim 1 wherein step (d) further comprises determining the level of quality of the predicted excavation results by evaluating the volume of material captured in the bucket during the excavation.
Claim 13
Dependent Claim
52 words
The method, as set forth in claim 1, wherein step (d) further comprises determining the number of sweeping actions required to clean up the floor of the excavation area and computing the distance required to reposition the excavator to reach material on the floor and on the bench of the excavation area.
Claim 14
Independent Claim
127 words
A method for planning earthmoving operations using a terrain map of an excavation area, and an excavator having a work implement comprised of a bucket, stick, and boom linked together in sequence and movably actuated by hydraulic cylinders, the method comprising the steps of: (a) dividing the excavation area into a plurality of excavation regions; (b) determining at least one candidate location of the bucket for starting an excavation for each excavation region; (c) predicting an excavation result of each candidate location; (d) determining a level of quality of the predicted excavation results by evaluating at least one performance parameter including the energy expended in performing the excavation; and (e) selecting a starting location as a function of the level of quality of the predicted excavation results.
Claim 15
Independent Claim
127 words
A method for planning earthmoving operations using a terrain map of an excavation area, and an excavator having a work implement comprised of a bucket, stick, and boom linked together in sequence and movably actuated by hydraulic cylinders, the method comprising the steps of: (a) dividing the excavation area into a plurality of excavation regions; (b) determining at least one candidate location of the bucket for starting an excavation for each excavation region; (c) predicting an excavation result of each candidate location; (d) determining a level of quality of the predicted excavation results by evaluating at least one performance parameter including the energy expended in performing the excavation; and (e) selecting a starting location as a function of the level of quality of the predicted excavation results.
Claim 16
Independent Claim
155 words
A method for planning earthmoving operations using a terrain map of an excavation area, and an excavator having a work implement comprised of a bucket, stick, and boom linked together in sequence and movably actuated by hydraulic cylinders, the method comprising the steps of: (a) dividing the excavation area into a plurality of excavation regions; (b) determining at least one candidate location of the bucket for starting an excavation for each excavation region; (c) predicting an excavation result of each candidate location using a simulated model of a closed loop controller to predict the trajectory of the work implement during excavation based on the starting location and orientation of the bucket and characteristics of the material being excavated; (d) determining a level of quality of the predicted excavation results by evaluating at least one performance parameter; and (e) selecting a starting location as a function of the level of quality of the predicted excavation results.
Claim 17
Independent Claim
155 words
A method for planning earthmoving operations using a terrain map of an excavation area, and an excavator having a work implement comprised of a bucket, stick, and boom linked together in sequence and movably actuated by hydraulic cylinders, the method comprising the steps of: (a) dividing the excavation area into a plurality of excavation regions; (b) determining at least one candidate location of the bucket for starting an excavation for each excavation region; (c) predicting an excavation result of each candidate location using a simulated model of a closed loop controller to predict the trajectory of the work implement during excavation based on the starting location and orientation of the bucket and characteristics of the material being excavated; (d) determining a level of quality of the predicted excavation results by evaluating at least one performance parameter; and (e) selecting a starting location as a function of the level of quality of the predicted excavation results.
Claim 18
Independent Claim
131 words
An apparatus for planning earthmoving operations using a work implement of an excavating machine, the work implement including a boom, stick, and bucket, the boom, stick, and bucket being controllably actuated by at least one respective hydraulic cylinder, the planning apparatus comprising: a terrain map of an excavation site represented in numerical form; and a data processor operable to access information in the terrain map, divide the excavation area into a plurality of excavation regions using expert heuristics, determine at least one candidate location for starting an excavation for each excavation region, predict the excavation results of each candidate location, determine the quality of the predicted excavation results by evaluating at least one performance parameter, and select a starting location as a function of the quality of the predicted excavation results.
Claim 19
Independent Claim
131 words
An apparatus for planning earthmoving operations using a work implement of an excavating machine, the work implement including a boom, stick, and bucket, the boom, stick, and bucket being controllably actuated by at least one respective hydraulic cylinder, the planning apparatus comprising: a terrain map of an excavation site represented in numerical form; and a data processor operable to access information in the terrain map, divide the excavation area into a plurality of excavation regions using expert heuristics, determine at least one candidate location for starting an excavation for each excavation region, predict the excavation results of each candidate location, determine the quality of the predicted excavation results by evaluating at least one performance parameter, and select a starting location as a function of the quality of the predicted excavation results.
Claim 20
Dependent Claim
48 words
The apparatus as set forth in claim 15 wherein the data processor is further operable to divide the excavation area into a plurality of excavation regions within a cylindrical coordinate frame, and to determine radial extents of the excavation regions based on kinematic constraints of the excavating machine.
Claim 21
Dependent Claim
36 words
The apparatus as set forth in claim 15 wherein the data processor is further operable to assign a sequence number to each excavation region corresponding to the order in which each region is to be excavated.
Claim 22
Dependent Claim
33 words
The apparatus as set forth in claim 15 wherein the data processor is further operable to determine a candidate starting location of the bucket to clean up the floor of the excavation region.
Claim 23
Dependent Claim
32 words
The apparatus as set forth in claim 15 wherein the data processor is further operable to determine a new position for the excavator before selecting a candidate starting location of the bucket.
Claim 24
Dependent Claim
26 words
The apparatus as set forth in claim 15 wherein the data processor is further operable to determine the orientation of the leading edge of the bucket.
Claim 25
Dependent Claim
52 words
The apparatus as set forth in claim 20 wherein the data processor is further operable to predict the trajectory of the work implement during the excavation based on the starting location and orientation of the bucket and characteristics of the material being excavated using a simulated model of a closed loop controller.
Claim 26
Dependent Claim
35 words
The apparatus as set forth in claim 15 wherein the data processor is further operable to determine the level of quality of the predicted excavation results by evaluating the energy expended in completing the excavation.
Claim 27
Dependent Claim
39 words
The apparatus as set forth in claim 15 wherein the data processor is further operable to determine the level of quality of the predicted excavation results by evaluating the volume of material captured in the bucket during the excavation.
Claim 28
Dependent Claim
38 words
The apparatus as set forth in claim 15 wherein the data processor is further operable to determine the level of quality of the predicted excavation results by evaluating the amount of time required to complete the predicted trajectory.
Claim 29
Dependent Claim
56 words
The apparatus as set forth in claim 15, wherein the data processor is further operable to determine the number of sweeping actions required to clean up the floor of the excavation area and to compute the distance required to reposition the excavator to reach material on the floor and on the bench of the excavation area.
Claim 30
Independent Claim
154 words
An apparatus for planning earthmoving operations using a work implement of an excavating machine, the work implement including a boom, stick, and bucket, the boom, stick, and bucket being controllably actuated by at least one respective hydraulic cylinder, the planning apparatus comprising: a terrain map of an excavation site represented in numerical form; and a data processor operable to access information in the terrain map, divide the excavation area into a plurality of excavation regions, determine at least one candidate location for starting an excavation for each excavation region, predict the excavation results of each candidate location based on the starting location and orientation of the bucket and characteristics of the material being excavated using a simulated model of a closed loop controller, determine the quality of the predicted excavation results by evaluating at least one performance parameter, and select a starting location as a function of the quality of the predicted excavation results.
Claim 31
Independent Claim
154 words
An apparatus for planning earthmoving operations using a work implement of an excavating machine, the work implement including a boom, stick, and bucket, the boom, stick, and bucket being controllably actuated by at least one respective hydraulic cylinder, the planning apparatus comprising: a terrain map of an excavation site represented in numerical form; and a data processor operable to access information in the terrain map, divide the excavation area into a plurality of excavation regions, determine at least one candidate location for starting an excavation for each excavation region, predict the excavation results of each candidate location based on the starting location and orientation of the bucket and characteristics of the material being excavated using a simulated model of a closed loop controller, determine the quality of the predicted excavation results by evaluating at least one performance parameter, and select a starting location as a function of the quality of the predicted excavation results.
Claim 32
Independent Claim
146 words
An apparatus for planning earthmoving operations using a work implement of an excavating machine, the work implement including a boom, stick, and bucket, the boom, stick, and bucket being controllably actuated by at least one respective hydraulic cylinder, the planning apparatus comprising: a terrain map of an excavation site represented in numerical form; and a data processor operable to access information in the terrain map, divide the excavation area into a plurality of excavation regions, determine at least one candidate location for starting an excavation for each excavation region, predict the excavation results of each candidate location based on the starting location and orientation of the bucket, determine the quality of the predicted excavation results by evaluating at least one performance parameter including the energy expended in performing the excavation, and select a starting location as a function of the quality of the predicted excavation results.
Claim 33
Independent Claim
146 words
An apparatus for planning earthmoving operations using a work implement of an excavating machine, the work implement including a boom, stick, and bucket, the boom, stick, and bucket being controllably actuated by at least one respective hydraulic cylinder, the planning apparatus comprising: a terrain map of an excavation site represented in numerical form; and a data processor operable to access information in the terrain map, divide the excavation area into a plurality of excavation regions, determine at least one candidate location for starting an excavation for each excavation region, predict the excavation results of each candidate location based on the starting location and orientation of the bucket, determine the quality of the predicted excavation results by evaluating at least one performance parameter including the energy expended in performing the excavation, and select a starting location as a function of the quality of the predicted excavation results.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-08-29 | 2004-02-28 | 2004-08-29 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-08-29 | 2008-02-28 | 2008-08-29 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-08-29 | 2012-02-28 | 2012-08-29 | $7700.00 | Window Closed / Lapsed |