Patent Publication Number: US-9404239-B2

Title: Sub-bin refinement for autonomous machines

Description:
TECHNICAL FIELD 
     The present disclosure relates generally to planning cut locations for machines, and more particularly, to methods and systems for determining cut locations for autonomous machines based on sub-bin cut volume analysis. 
     BACKGROUND 
     Machines such as, for example, track-type tractors, dozers, motor graders, wheel loaders, and the like, are used to perform a variety of tasks. For example, these machines may be used to move material and/or alter work surfaces at a worksite. The machines may be manned machines, but may also be autonomous or semi-autonomous vehicles that perform these tasks in response to commands remotely or locally generated as part of a work plan for the machines. The machines may receive instructions in accordance with the work plan to perform operations, including digging, loosening, carrying, and any other manipulation of materials at the worksite. 
     It may be desirable to ensure that the machines perform these operations such that the materials are moved in an efficient manner. More particularly, in repetitive operations, it may be especially desirable to ensure that the locations at which the machines begin to alter the work surface and/or the profiles along which the machines alter the work surface are chosen such that the machines function efficiently. Some conventional systems plan cut locations based on predetermined cut volume estimations. Such systems often employ algorithms which digitalize a worksite into discrete bins or grids to facilitate any necessary computations. 
     While such algorithms greatly assist in the planning process, there is still room for improvement. For instance, due to the discrete nature of the calculations, precision can be somewhat compromised. One solution for improving precision is to increase the resolution or the number of bins or grids per area of a worksite. By reducing the area or size per bin or grid, a cut location can be more precisely and accurately determined. However, increasing the resolution also significantly increases the number of calculations required per cut location. The increase in computational load would either burden existing control systems, or demand substantial costs for implementing hardware suited to support the added computations. 
     In view of the foregoing inefficiencies and disadvantages associated with conventional autonomous machines and control systems therefor, a need exists for control systems capable of providing improved precision without substantially increasing computational load. 
     SUMMARY OF THE DISCLOSURE 
     In one aspect of the present disclosure, a computer-implemented method for determining a cut location for a machine implement is provided. The method may include comparing a target cut volume to a projected cut volume associated with each boundary of a selected bin, designating the cut location as the boundary most closely approximating the target cut volume if both of the projected cut volumes at the boundaries are either greater than or less than the target cut volume, and designating the cut location as an average of the boundaries if the projected cut volumes at the boundaries are greater than and less than the target cut volume. 
     In another aspect of the present disclosure, a control system for determining a cut location for a machine implement is provided. The control system may include at least a memory and a controller in communication with the memory. The memory may be configured to retrievably store one or more algorithms. Based on the one or more algorithms, the controller may be configured to at least test each boundary of a selected bin and corresponding projected cut volumes in relation to a target cut volume, designate the cut location as the boundary most closely approximating the target cut volume if both of the projected cut volumes at the boundaries are either greater than or less than the target cut volume, and designate the cut location as an average of the boundaries if the projected cut volumes at the boundaries are greater than and less than the target cut volume. 
     In yet another aspect of the present disclosure, a controller for determining a cut location for a machine implement is provided. The controller may include at least a boundary test module, a boundary selection module, and a boundary average calculation module. The boundary test module may be configured to compare a target cut volume to a projected cut volume associated with each boundary of a selected bin. The boundary selection module may be configured to designate the cut location as the boundary most closely approximating the target cut volume if the boundary test module indicates both of the projected cut volumes at the boundaries to be either greater than or less than the target cut volume. The boundary average calculation module may be configured to designate the cut location as an average of the boundaries if the boundary test module indicates the projected cut volumes at the boundaries to be greater than and less than the target cut volume. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  is a pictorial illustration of an exemplary disclosed worksite; 
         FIG. 2  is a diagrammatic illustration of an exemplary control system that may be used at a worksite; 
         FIG. 3  is a diagrammatic illustration of an exemplary controller that may be used at a worksite; 
         FIG. 4  is a pictorial illustration of a simulation of a potential cut at a worksite that may be generated by a control system of the present disclosure; and 
         FIG. 5  is a flowchart depicting an exemplary disclosed method that may be performed by a control system of the present disclosure. 
     
    
    
     DETAILED DESCRIPTION 
     Although the following sets forth a detailed description of numerous different embodiments, it should be understood that the legal scope of protection is defined by the words of the claims set forth at the end of this patent. The detailed description is to be construed as exemplary only and does not describe every possible embodiment since describing every possible embodiment would be impractical, if not impossible. Numerous alternative embodiments could be implemented, using either current technology or technology developed after the filing date of this patent, which would still fall within the scope of the claims defining the scope of protection. 
     It should also be understood that, unless a term is expressly defined herein, there is no intent to limit the meaning of that term, either expressly or by implication, beyond its plain or ordinary meaning, and such term should not be interpreted to be limited in scope based on any statement made in any section of this patent (other than the language of the claims). To the extent that any term recited in the claims at the end of this patent is referred to herein in a manner consistent with a single meaning, that is done for sake of clarity only so as to not confuse the reader, and it is not intended that such claim term be limited, by implication or otherwise, to that single meaning. 
     Referring now to  FIG. 1 , one exemplary worksite  100  is illustrated with one or more machines  102  performing predetermined tasks. The worksite  100  may include, for example, a mine site, a landfill, a quarry, a construction site, or any other type of worksite. The predetermined task may be associated with altering the geography at the worksite  100 , such as a dozing operation, a grading operation, a leveling operation, a bulk material removal operation, or any other type of operation that results in geographical modifications within the worksite  100 . The machines  102  may be mobile machines configured to perform operations associated with industries related to mining, construction, farming, or any other industry known in the art. The machines  102  depicted in  FIG. 1 , for example, may embody earth moving machines, such as dozers having blades or other work tools or implements  104  movable by way of one or more actuators  106 . The machines  102  may also include manned machines or any type of autonomous or semi-autonomous machines. 
     The overall operations of the machines  102  and the machine implements  104  within the worksite  100  may be managed by a control system  108  that is at least partially in communication with the machines  102 . Moreover, each of the machines  102  may include any one or more of a variety of feedback devices  110  capable of signaling, tracking, monitoring, or otherwise communicating relevant machine information to the control system  108 . For example, each machine  102  may include a locating device  112  configured to communicate with one or more satellites  114 , which in turn, may communicate to the control system  108  various information pertaining to the position and/or orientation of the machines  102  relative to the worksite  100 . Each machine  102  may additionally include one or more implement sensors  116  configured to track and communicate position and/or orientation information of the implements  104  to the control system  108 . 
     The control system  108  may be implemented in any number of different arrangements. For example, the control system  108  may be at least partially implemented at a command center  118  situated locally or remotely relative to the worksite  100  with sufficient means for communicating with the machines  102 , for example, via satellites  114 , or the like. Additionally or alternatively, the control system  108  may be implemented using one or more computing devices  120  with means for communicating with one or more of the machines  102  or one or more command centers  118  that may be locally and/or remotely situated relative to the worksite  100 . In still further alternatives, the control system  108  may be implemented on-board any one or more of the machines  102  that are also provided within the worksite  100 . Other suitable modes of implementing the control system  108  are possible and will be understood by those of ordinary skill in the art. 
     Using any of the foregoing arrangements, the control system  108  may generally be configured to monitor the positions of the machines  102  and/or machine implements  104  relative to the worksite  100  and a predetermined target operation, and provide instructions for controlling the machines  102  and/or machine implements  104  in an efficient manner in executing the target operation. In certain embodiments, the machines  102  may be configured to excavate areas of a worksite  100  according to one or more predefined excavation plans. For example, the excavation plans may include, among other things, determining a location, size, and shape of a plurality of cuts into an intended work surface or action space  122  at the worksite  100  along a plurality of spaced apart locations known as slots  124 . In such embodiments, the control system  108  may function as a means for planning the excavation, for instance, to determine a location, size, and shape of the cuts into the action space  122  within the slots  124 . While described in connection with slot-based excavation planning, the control system  108  may similarly be employed in conjunction with other types of action spaces  122 . 
     Turning to  FIG. 2 , one exemplary embodiment of a control system  108  that may be used in conjunction with the worksite  100  of  FIG. 1  is diagrammatically provided. As shown, the control system  108  may generally include, among other things, a controller  126 , a memory  128 , and a communications device  130 . More specifically, the controller  126  may be configured to operate according to one or more algorithms that are retrievably stored within the memory  128 . The memory  128  may be provided on-board the controller  126 , external to the controller  126 , or otherwise in communication therewith. The communications device  130  may be configured to enable the controller  126  to communicate with one or more of the machines  102 , and provide information pertaining to the position and/or orientation of the machines  102  and the machine implements  104 , for example, via satellites  114 , or any other suitable means of communication. Moreover, the controller  126  may be implemented using any one or more of a processor, a microprocessor, a microcontroller, or any other suitable means for executing instructions stored within the memory  128 . Additionally, the memory  128  may include non-transitory computer-readable medium or memory, such as a disc drive, flash drive, optical memory, read-only memory (ROM), or the like. 
     As further shown in  FIG. 3 , the controller  126  may be configured to determine a cut location in an action space  122  according to a sub-bin refinement approach, or one or more algorithms which may generally be categorized into, for example, a digitalization module  132 , a bin selection module  134 , a boundary test module  136 , a boundary selection module  138 , and a boundary average calculation module  140 . With reference to exemplary diagram of  FIG. 4 , the digitalization module  132  may configure the controller  126  to digitalize an action space  122  into a plurality of grids or bins  142 , where each bin  142  is equal in size and increment, such as in units of length, and encompasses a range of potential cut locations, and where each cut location is associated with a projected cut volume. Among the bins  142  digitalized by the digitalization module  132 , the bin selection module  134  may configure the controller  126  to initially select the bin  142  having projected cut volumes that would best approximate the target cut volume. The boundary test module  136  may further refine the cut location analyses by configuring the controller  126  to perform boundary tests on each boundary  144  of the selected bin  142 . 
     In particular, the boundary test module  136  may configure the controller  126  to compare the projected cut volume at each of the boundaries  144  of the selected bin  142  to the target cut volume. If the boundary test module  136  indicates that the projected cut volumes at the boundaries  144  are both greater than the target cut volume or both less than the target cut volume, the boundary selection module  138  may configure the controller  126  to designate the final cut location as the boundary  144  with the projected cut volume most closely approximating the target cut volume. If, however, the boundary test module  136  indicates that the projected cut volume at one boundary  144  is greater than the target cut volume, and that the projected cut volume at the other boundary  144  is less than the target cut volume, the boundary average calculation module  140  may configure the controller  126  to designate the final cut location as the average of the boundaries  144 . More particularly, the boundary average calculation module  140  may perform an interpolation of at least the two boundary points  144 , assign weights to each of the boundaries  144  based on the interpolation, and calculate an average of the weighted boundaries  144  to be designated as the final cut location, for example, at final cut location  146  as shown in  FIG. 4 . 
     Additionally or optionally, the control system  108  and/or the controller  126  may further be configured to track the position and/or orientation of the machines  102  and/or the machine implements  104 , track previously engaged cut locations, communicate instructions to the machines  102  and/or machine implements  104  for engaging cut locations, such as via an additional communications module  130 , and the like. Moreover, previously tracked information may be at least temporarily stored within memory  128 . Furthermore, to further simplify calculations, the control system  108  may convert a target cut volume into one or more predefined criteria or thresholds against which the boundary cut locations of the bins  142  may be directly compared, for instance, without having to calculate or assess the projected cut volume per iteration of the above processes. Other variations and modifications to the algorithms or methods will be apparent to those of ordinary skill in the art. One exemplary algorithm or method by which the controller  126  may be operated to determine a cut location based on the sub-bin refinement approach is discussed in more detail below. 
     INDUSTRIAL APPLICABILITY 
     In general terms, the present disclosure sets forth methods, devices and systems for volume-based cut planning and material moving operations where there are motivations to improve productivity and efficiency. Although applicable to any type of machine, the present disclosure may be particularly applicable to autonomously or semi-autonomously controlled dozing machines where the dozing machines are controlled along particular travel routes within a worksite to excavate materials. Moreover, the present disclosure may provide excavation or cut planning with improved precision by enabling sub-bin refinement without adding a significant computational load or burden on the control system. By providing more refined control without adding complexity, cut locations may be determined and volume-based excavation work may be carried out with improved productivity and efficiency. 
     One exemplary algorithm or computer-implemented method  148  for determining a cut location is diagrammatically provided in  FIG. 5 , according to which, for example, the control system  108  and the controller  126  may be configured to operate. With reference to  FIG. 4  and as shown in block  148 - 1  of  FIG. 5 , the controller  126  may initially digitalize a given action space  122  into a plurality of grids or bins  142  such that each bin  142  is equal in size or length, and such that each bin  142  encompasses a range of potential cut locations. In addition, each cut location may be associated with a projected cut volume, which may be calculated by the controller  126  and/or retrieved from predetermined data or maps stored within memory  128  associated with the controller  126 . Based on the bins  142  digitalized in block  148 - 1 , the controller  126  in block  148 - 2  may be configured to select the bin  142  with corresponding projected cut volumes best suited to approximate a desired or target cut volume. More particularly, the controller  126  may perform comparisons between the projected cut volumes of the bins  142  and the target cut volume to determine the most efficient bin  142  to begin with. 
     Once a starting bin  142  is selected, the controller  126  in block  148 - 3  may be configured to perform a boundary test on each boundary  144  of the selected bin  142 . In particular, the controller  126  may determine a first projected cut volume corresponding to a first cut location at a first boundary  144 - 1  of the selected bin  142 , as well as a second projected cut volume corresponding to a second cut location at a second boundary  144 - 2  of the selected bin  142 . The controller  126  may additionally compare each of the first and second projected cut volumes against the target cut volume to determine whether the respective projected cut volume is greater than or less than the target cut volume. If both of the first and second projected cut volumes are greater than the target cut volume, or if both of the first and second projected cut volumes are less than the target cut volume, the controller  126  may proceed to operate according to block  148 - 4 . In block  148 - 4 , the controller  126  may be configured to compare the first projected cut volume to the second projected cut volume, and determine which of the two projected cut volumes more closely approximates the target cut volume. Based on the comparison in block  148 - 4 , the controller  126  in block  148 - 5  may designate one of the boundaries  144  as the final cut location. For example, if the first projected cut volume is a better approximation of the target cut volume than the second projected cut volume, the first boundary  144 - 1  may be designated as the final cut location. Alternatively, if the second projected cut volume is a better approximation, the second boundary  144 - 2  may be designated as the final cut location. 
     If, however, one of the first and second projected cut volumes is greater than the target cut volume, while the remaining one of the first and second projected cut volumes is less than the target cut volume, the controller  126  may be configured to designate the final cut location based on a calculated average, such as a weighted average, of the boundaries or boundary points  144 . For example, according to block  148 - 6 , the controller  126  may be configured to perform an interpolation between at least the two boundary points  144 , or across other bins  142 , and in block  148 - 7 , the controller  126  may be configured to assign weights to the boundary points  144  based on that interpolation. More particularly, the interpolation and weighting schemes may be computed based at least partially on the size or length of the bins  142 , the relative cut locations, the corresponding cut volumes, and the like. In block  148 - 8 , the controller  126  may be configured to compute an average of those weighted boundary points  144 , and in block  148 - 9 , the controller  126  may be configured to designate the weighted average of the boundary points  144  as the final cut location, for example, at final cut location  146  as shown in  FIG. 4 . 
     Additionally or optionally, the method  148  may further configure the control system  108  and the controller  126  to track the position and/or orientation of the machines  102  and/or the machine implements  104 , track previously engaged cut locations, communicate instructions to the machines  102  and/or machine implements  104  for engaging cut locations, and the like. Moreover, previously tracked information may be at least temporarily stored within memory  128 . Furthermore, to further simplify calculations, the control system  108  may convert a target cut volume into one or more predefined criteria or thresholds against which the boundary cut locations of the bins  142  may be directly compared, for instance, without having to calculate or assess the projected cut volume per iteration of the above processes. 
     From the foregoing, it will be appreciated that while only certain embodiments have been set forth for the purposes of illustration, alternatives and modifications will be apparent from the above description to those skilled in the art. These and other alternatives are considered equivalents and within the spirit and scope of this disclosure and the appended claims.