Abstract:
A method for the automatic palletizing of stable package stacks includes the steps of virtual generation of multiple follow-up configurations by adding packages to at least one initial configuration, assessment of these follow-up configurations, and pursuit of follow-up configurations that are assessed as good as initial configurations. These steps are repeated until a termination criterion is satisfied. The follow-up configurations are assessed on the basis of different partial stack heights, towers and/or overbuildings. Another version of the method includes the steps of virtual generation of a package stack, and determination of a characteristic stability value of a package of a layer of a virtual package stack on the basis of the characteristic stability value of packages on which the package rests.

Description:
BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     The invention concerns a method and a device for automated generation of stable or more stable package stacks, in particular by means of a manipulator. 
     2. Description of the Prior Art 
     In manufacturing, for storage, for transport and for consignment, individual goods or goods bundles (that are uniformly designated as packages in the following) are frequently stacked atop one another on loading or transport means such as storage spaces, pallets, shelf boards, continuous transporters or the like in order to save packing space, for example. This is generally designated in the following as palletizing packages into a package stack. 
     It is desirable for the generated package stack to have a higher stability since such stacks can be handled better, for example can be moved dynamically. The stability of provided (partial) package stacks should therefore be assessed or already be taken into account in the planning of a package stack to be generated, i.e. the generation of a palletizing or loading pattern. 
     For this purpose, DE 10 2007 001 263 A1 discloses determining characteristic values for the stability, to consider the weight, size center of gravity position, the ratio of footprint to bearing surface, and the position of packages relative to one another. E. E. Bischoff examines and assesses known heuristic methods in “Stability aspects of pallet loading”, OR Spektrum (1991) 13:189-197. 
     SUMMARY OF THE INVENTION 
     An object of the present invention is to improve the automated palletizing of stable package stacks. 
     A method according to the invention is particularly suitable for the palletizing of mixed package stacks that contain varying packages with different dimensions. It can advantageously be used to check provided package stacks or to plan package stacks to be generated, and is based on the principle to increase the stability by overbuilding. The supporting of a package on two or more underlying packages is thereby generally designated as overbuilding. In contrast to this, packages that are supported on only a single package are defined as what are known as towers. If all packages of a tower are supported on only the respective underlying package, this is designated as a free tower (in contrast to towers whose uppermost package is supported on adjacent packages). 
     According to a first aspect of the present invention, a heuristic method is proposed for the automatic palletizing of stable package stacks according to which one or more packages that are still to be palletized are virtually added to an initial configuration, for example a loading means such as a pallet or a partial package stack from a preceding step. In that the package or, respectively, packages are added at different points and/or in different orientations, and/or in that different packages are added to the initial configuration, two or more follow-up configurations are generated. 
     In contrast to a mere “brute force” method, the follow-up configurations that are generated in this way are evaluated, and only those that are assessed as good are pursued as new initial configuration(s) in following method steps. For example, this can be realized via corresponding evaluation of the fitness of these configurations in an evolutionary optimizer, by excluding from further method steps configurations whose assessment falls below a predetermined, fixed or variable limit value, or by taking the evaluation into account in a quality criterion of an optimizer. 
     These steps are repeated until a termination criterion is satisfied, for example all packages to be palletized are used, all follow-up configurations are assessed as poor or the like. The variant tree of the follow-up configurations that are pursued as a new initial configuration can advantageously be reduced if necessary during the workflow of the heuristic method, for example in that a subset (in particular the best assessed follow-up configurations that have resulted from all pursued initial configurations) is pursued as a new initial configuration in the order of their assessment. 
     It is noted that an evaluation, for example, can be discretized by overrunning predetermined quality limit values, in particular a binary classification into good and poor classifications, but can also be made uniform or continuous, in particular with blurring by fuzzification, wherein the positive treatment of a good criterion (for example the pursuit of a good configuration) can also be implemented uniformly by the negative treatment of a complementary poor criterion, for example the non-pursuit of a poor configuration. 
     According to the invention, the follow-up configurations are evaluated on the basis of different partial stack heights, of towers and/or of overbuildings. 
     In particular a configuration can be assessed better, for example in that a corresponding characteristic quality value is assigned to it or its existing characteristic quality value is correspondingly increased if it exhibits lower partial stack height differences. For this, the differences between the levels of the uppermost packages of the configuration can be assessed with different standards, for example via absolute or quadratic averaging, a maximum standard or the like. The height differences can advantageously also be mapped in a histogram whose characteristic values can then serve for the assessment as a good or poor configuration. 
     Additionally or alternatively, a configuration can be evaluated as better if it exhibits lower and/or fewer (in particular free) towers since such towers form potential seeds or sources of instability in the package stack. 
     Furthermore, a configuration can additionally or alternatively be assessed as better if it exhibits a higher number of overbuildings. An overbuilding can thereby be evaluated on the basis of an (in particular predeterminable) minimum contact area (footprint). For example, an overbuilding is preferably only classified as a development to be considered in the evaluation when the ratio of the area supported on underlying packages to the maximum possible contact area of the resting package exceeds a predetermined, fixed or variable value, for example 15%. All overbuildings can be enumerated as integers, meaning that every overbuilding can be weighted the same, or the overbuildings can be weighted uniformly in the determination of the number, for example corresponding to the relationship explained above. 
     In order to generate a configuration from an initial layer (for example an empty pallet or a partial stack from a preceding step), it can be advantageous that the preferred or, respectively, higher-priority packages of such a configuration whose height difference falls below a similarity limit value (that thus are advantageously essentially equal in height) are added in parallel (next to one another) since this facilitates the formation of overbuildings in the next step. In particular if such a parallel arrangement is not possible due to the available packages or other boundary conditions (inasmuch lower-priority packages relative to essentially equally high packages), such packages whose height difference exceeds a perturbation limit value can then be arranged in parallel with high priority. The possibility increases to achieve partial stacks of the same height again by the addition of an additional short package to the shorter of the packages arranged in parallel, by the parallel arrangement of packages with significantly different heights. 
     According to a second aspect of the present invention, in a method for automated palletizing of stable package stacks, a characteristic stability value of a package of a layer of a virtual package stack is determined on the basis of the characteristic stability of values of packages on which the package rests. This characteristic stability value can be used in the heuristic generation (explained in the preceding) of a virtual package stack for the evaluation of follow-up configurations. However, an independent application is also similarly possible in which stability values are propagated from bottom to top through an (in particular virtual) package stack. 
     This second aspect enables the determination of a characteristic stability value for packages in a simple manner that can be computationally handled well, even in complex, mixed package stacks. For this a stabilization of underlying packages via overlying packages is intentionally disregarded. In a preferred embodiment, this can be iteratively taken into account as well by a subsequent backward propagation from top to bottom, possibly even a repeat forwards-backwards recursion. 
     The characteristic stability value of a package is preferably determined on the basis of a contact area with packages on which the package rests. This is based on the principle that packages that are supported with more contact area on underlying packages are more stable, such that the stability of the underlying package is propagated to a correspondingly greater degree to the overlying package. 
     The characteristic stability value of a package can also be comparably determined on the basis of the number of packages on which the package rests, and/or the number of corners with which the packet is seated. This is based on the principle that packages that are supported on multiple underlying packages, just like packages that are seated on more corners, are more stable, such that the stability of the underlying package is propagated to a correspondingly greater degree to the overlying package. In particular, a minimum limit value for underlying packages or supported corners can be provided as of which the characteristic stability value of the underlying packages is propagated identically to the overlying package. This minimum limit value can, for example, correspond to the number of lower corners of the seated package (thus 4 given packages with rectangular footprint). 
     The characteristic stability value of a package is preferably determined as a weighted sum of the characteristic stability values of packages on which the package rests. This is based on the principle that underlying packages on which a package is supported contribute to different degrees to the stability of the overlying package, such that the stability of the underlying packages is correspondingly propagated differently to the overlying package. 
     In an advantageous embodiment that is simple to implement, to determine the characteristic stability value of a package of a layer of a virtual package stack the characteristic stability values of the packages on which the package rests can be assigned a constant value (for example “1”) so that the characteristic stability value of an overlying package results on the basis of its contact areas with packages on which this package rests. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  shows an initial configuration in a step of a method according to one embodiment of the present invention. 
         FIG. 2  shows two follow-up configurations in a step of the method. 
         FIG. 3  shows height histograms and tower heights of the follow-up configurations of  FIG. 2 . 
         FIGS. 4A ,  4 B are side and plan views of a metastable package stack. 
         FIGS. 5A ,  5 B are side and plan views of a more stable package stack. 
         FIGS. 6A ,  6 B are side and plan views of an even more stable package stack. 
         FIG. 7  shows the workflow of a method according to a further embodiment of the present invention. 
     
    
    
     DESCRIPTION OF THE PREFERRED EMBODIMENTS 
     The sequence of FIG.  1 →FIG.  2 → FIG. 3  shows a loop of a heuristic method according to the first aspect of the present invention for the successive generation of a virtual stable package stack. 
     In an initial Step S 10 , one or more initial configurations are selected. In  FIG. 1  an initial configuration in the form of two packages  1 ,  2  of different heights standing next to one another is provided that, for example, resulted from a preceding loop or was provided by the user. 
     The packages  3 ,  4 ,  5  that are still to be palletized are added to this initial configuration in Step S 20 . In that the packages are added in different arrangements and/or orientations, multiple follow-up configurations are thus generated, of which two are shown in  FIG. 2 . It is recognizable in the very schematic example that the lower configuration in  FIG. 2  (in which the packages  5 ,  2  are overbuilt by the package  4 ) is markedly more stable than the upper configuration with the high free tower composed of packages  1 ,  3  and  4 . 
     The generated follow-up configurations are now evaluated in Step S 30 . For this the height T of the highest free tower ( 1 + 3 + 4  at the top in  FIG. 2 ; or  5  at the bottom in  FIG. 2 ) of the respective configuration is considered, which is drawn with a dash-dot line in  FIG. 3  for the respective adjacent configuration. 
     Moreover, the partial stack heights h that are mapped in the histograms of  FIG. 3  over the stack contact area F are considered. In these it is shown in particular that a larger maximum difference Δh_max between partial heights (namely between the height of the stack  1 + 3 + 4  and the package  2 ) occurs in the upper configuration in  FIG. 2 . 
     It is also taken into account that an overbuilding (a package overlapping multiple stacks) above the entire contact area of the package  4  is present in the lower configuration in  FIG. 2 , while no overbuilding is present in the upper configuration. 
     Under suitable quantification of these three criteria Δh_max, T and overbuilding, the configuration below in  FIG. 2  is assessed as good, the configuration above in  FIG. 2  as not good or, respectively, poor. Therefore only the lower configuration that is assessed as good is pursued and forms the basis of a new initial configuration if the loop FIG.  1 →FIG.  2 → FIG. 3  is run through again analogously to generate additional layers on the package stack  1 + 2 + 3 + 4 + 5 ; in contrast, the configuration above in  FIG. 2  is discarded. 
       FIG. 4A  shows in side view a package stack made up of two packages  1 . 1 ,  2  stacked one atop the other. In particular in the plan view from above in  FIG. 4B , the footprint or contact area (drawn there with hatching) between two packages is well recognizable; it amounts to 50% of the maximum contact area or underside area of the package  2 . This stair-like construction is metastable since, given a homogeneous mass distribution of the package  2 , its center of gravity lies directly over the edge of the package  1 . 1  supporting it. 
       FIGS. 5A ,  5 B show (in a presentation corresponding to  FIG. 4A ,  4 B) a more advantageous, more stable configuration in which the upper package  2  is supported with 40% of its underside on a package  1 . 3  and a respective eighth on the packages  1 . 1 ,  1 . 2 . 
     Finally,  FIGS. 6A ,  6 B show in the same depiction an even more advantageous, even more stable configuration in which the upper package  2  is supported at each of its four corners with a respective eighth of its underside on the packages  1 . 1 , . . . ,  1 . 4 . 
       FIG. 7  shows the workflow of a method according to the second aspect of the present invention in order to map this simply (in terms of calculation) in the evaluation of the stability of the package stack, and thus for example to be able to evaluate a package stack or a configuration. 
     For this a limit value for the assessment of the stability is initially established in Step S 100  that is advantageously greater than 0.5 and, in the exemplary embodiment, is 0.65. A characteristic stability value S 1  for the packages of a lowermost layer that, for example, can be defined by a pallet on which the packages are stacked or by the underlying packages  1 . 1 , . . . ,  1 . 4  shown in  FIG. 4 through 6  can then be provided in Step S 110 . In the exemplary embodiment, this value is equal to 1 and represents maximum stability of a package. 
     In the virtual package stack, a characteristic stability value S i  for the packages of the stack is now propagated from bottom to top. For this a counter i that designates the package to be assessed is incremented in Step S 120 , and this package is arranged in Step S 130  at a predetermined point of the virtual package stack. If the package stack is predetermined, such that only its stability should be assessed, Step  130  degenerates into the establishment of where and how the package i is arranged in the package stack. If the virtual package stack should only be generated under consideration of the stability, an optimizer can arrange the package at various points for testing in Step S 130 . 
     In Step S 140  the characteristic stability value S i  for the package i is now determined according to 
                     S   i     =     Max   (         ∑     u   i               ⁢           ⁢       k   ij     ·     S   j         ,   1     )             (   1   )               
with:
         the quantity u i  of the packages underlying the package i, i.e. the packages on which the package i is seated,   the function       

               Max   ⁡     (     a   ,   1     )       =     {             a   ⇔     a   ≤   1       ;                 1   ⇔     a   &gt;   1       ;                   
and
         the weighting factor k ij . This corresponds to the ratio of the contact area between the package i and the underlying package j to the maximum footprint of the package i insofar as the package i does not rest on at least four packages and/or with at least 4 corners on packages, meaning that the stability of the underlying packages is propagated to the overlying package proportional to the contact area. In contrast to this, in the event that the package i rests on at least four packages or, respectively, with at least 4 corners on packages, the factor k ij =1, meaning that the stability of the underlying packages is propagated entirely to the overlying package.       

     For simplification, in (1) the same uniformly constant value (for example “1”) can also always be used for the characteristic stability value S j  of the underlying package j, independent of a characteristic stability value calculated in a previous method step. The weighting factor k ij  can also always correspond to the ratio of the contact area between the package i and the underlying package j to the maximum footprint of the package i, independent of the number of packages and/or corners on or, respectively, with which it is supported. 
     In Step S 150  the characteristic stability value S i  of the package is now compared with the limit value G predetermined in Step S 100 : if the characteristic stability value falls below the limit value (S 150 : “N”), the package stack is discarded or the package i is arranged at another point and/or in another orientation and is reassessed. Contrarily, if the characteristic stability value exceeds the limit value (S 150 : “Y”), the method continues with the next package i+1 in order to thus propagate the characteristic stability value upward, starting from the predetermined characteristic stability value S 1  for the pallet or the lowermost layer  1 . 1 , . . . ,  1 . 4 . 
     In the examples of  FIG. 4 through 6 , an insufficient characteristic stability value consequently results for the configuration of  FIG. 4  with 
                       S     2   ,     Fig   ⁢   .4         =       Max   (             0   ,   5     ︸       k     21   ,   1         ·       1   ︸       S   1.1         ,   1     )     =   0       ,     5   &lt;           0   ,   65     ︸     G     ⁢     (   a   )                 (   a   )               
a quite sufficient characteristic stability value results with
 
                       S     2   ,     Fig   ⁢   .5         =       Max   (               0   ,   125     ︸       k     21   ,   1         ·       1   ︸       S   1.1         +           0   ,   125     ︸       k     21   ,   2         ·       1   ︸       S   12         +           0   ,   4     ︸       k     21   ,   3         ·       1   ︸       S   1.3           ,   1     )     =   0       ,     65   =   G             (   b   )               
for the configuration of  FIG. 5 , and the best characteristic stability value results for the configuration of  FIG. 6  (in which the package  2  is supported with its four corners on the four packages  1 . 1 , . . . ,  1 . 4 ) with
 
                       N     underlying   ⁢           ⁢   packages       =       N     supported   ⁢           ⁢   corners       =       4   ⇒     k   1.1       =       k   1.2     =       k   1.3     =       k   1.4     →   1               ⁢     
     ⁢       S     2   ,     Fig   ⁢   .6         =       Max   ⁡     (         ∑     j   =   1     4     ⁢           ⁢       1   ︸       k     21   ,   i           ,       1   ︸       S     1   ,   i         ,   1     )       =       Max   ⁡     (     4   ,   1     )       =     1   &gt;   G                   (   c   )               
in spite of its lower contact area
 
     
       
         
           
             
               
                 
                   ∑ 
                   
                     j 
                     = 
                     1 
                   
                   4 
                 
                 ⁢ 
                 
                     
                 
                 ⁢ 
                 
                   
                     
                       0 
                       , 
                       125 
                     
                     ︸ 
                   
                   
                     k 
                     
                       21 
                       , 
                       i 
                     
                   
                 
               
               = 
               0 
             
             , 
             5. 
           
         
       
     
     Although modifications and changes may be suggested by those skilled in the art, it is the intention of the inventor to embody within the patent warranted hereon all changes and modifications as reasonably and properly come within the scope of his contribution to the art.