Method and apparatus for determining an excavation strategy
First Claim
1. 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.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
27 Claims
-
1. 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
-
-
13. 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.
-
-
14. 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.
-
-
15. 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. - View Dependent Claims (16, 17, 18, 19, 20, 21, 22, 23, 24, 25)
-
-
26. 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.
-
-
27. 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.
-
Specification