Efficient packing of objects

Patent metadata

Field	Value
Publication number	US-10452789-B2
Application number	US-201514954959-A
Country	US
Kind code	B2
Filing date	Nov 30, 2015
Priority date	Nov 30, 2015
Publication date	Oct 22, 2019
Grant date	Oct 22, 2019

Abstract

Systems, apparatuses and/or methods may provide for generating a packing order of items within a container that consolidates the items into a reduced space. Items may be scanned with a three-dimensional (3D) imager, and models may be generated of the items based on the data from the 3D imager. The items may be located within minimal-volume enclosing bounding boxes, which may be analyzed to determine whether they may be merged together in one of their bounding boxes, or into a new bounding box that is spatially advantageous in terms of packing. If a combination of items is realizable and is determined to take up less space in a bounding box than the bounding boxes of the items considered separately, then they may be merged into a single bounding box. Thus, a spatially efficient packing sequence for a plurality of real objects may be generated to maximize packing efficiency.

First claim

We claim:

1. A system comprising:
at least one sensor to provide sensor to an object modeler that is to generate a digital three-dimensional (3D) model of each of a plurality of real objects;
an object boxer communicatively coupled with the at least one sensor to generate a bounding box for each of the plurality of real objects; and
a packing plan generator communicatively coupled with the object boxer to determine a spatially efficient packing sequence for the plurality of real objects, wherein at least one of the plurality of real objects contains at least one other of the plurality of real objects.

2. The system of claim 1 , further including an object voxelizer to approximate a size and a shape for each of the plurality of real objects in voxels.

3. The system of claim 1 , wherein one or more of the plurality of real objects is an item, and wherein the apparatus further includes:
an item voxelizer to approximate a size and a shape for each item;
an item boxer to generate a minimal enclosing bounding box for each item; and
an item combiner to:
determine if any two or more items are mergeable into a bounding box that occupies less volume than a sum of volumes for each minimal enclosing bounding box for each of the two or more items; and
merge the two or more items together in the bounding box if the two or more items are mergeable.

4. The system of claim 3 , wherein the item combiner is to:
compute a free space (FS) value of each item with respect to each minimal enclosing bounding box for each item; and
merge the two or more items into one bounding box if a merger criterion is met.

5. The system of claim 1 , wherein the at least one sensor includes a 3D sensor, and wherein the system further includes an object identifier to identify each of the plurality of real objects and acquire non-3D image data corresponding to each of the plurality of the real objects.

6. The system of claim 1 , further including a hierarchy generator to generate a hierarchical volumetric representation of each of the plurality of real objects to detect an empty part of each of the plurality of real objects.

7. The system of claim 3 , wherein one of the plurality of real objects is a storage space, and wherein the system further includes a storage space boxer to generate a maximum enclosed bounded box for the storage space.

8. An apparatus comprising:
a processor;
memory communicatively coupled to the processor; and
logic communicatively coupled to the processor to:
generate, via an object modeler, a three-dimensional (3D) digital model of a plurality of real objects based on sensor data for each of the plurality of real objects;
generate, via an object boxer communicatively coupled with the object modeler, a bounding box for each of the plurality of real objects; and
determine, via a packing plan generator communicatively coupled with the object boxer, a spatially efficient packing sequence for the plurality of real objects, wherein at least one of the plurality of real objects contains at least one other of the plurality of real objects.

9. The apparatus of claim 8 , wherein one or more of the plurality of real objects is an item, and wherein the logic is further to:
approximate, via an item voxelizer, a size and a shape for each item;
generate, via an item boxer, a minimal enclosing bounding box for each item;
determine, via an item combiner, if any two or more items are mergeable into a bounding box that occupies less volume than a sum of volumes for each individual minimal enclosing bounding box for each of the two or more items; and
merge, via the item combiner, the two or more items together in the bounding box if it is determined that the two or more items are mergeable.

10. The apparatus of claim 9 , wherein the logic is further to:
compute, via the item combiner, a free space value (FS) of each item with respect to each minimal enclosing bounding box for each item; and
merge, via the item combiner, the two or more items into one bounding box if it is determined that a merger criterion is met.

11. The apparatus of claim 8 , wherein the logic is further to: identify, via an object identifier, each of the plurality of real objects and acquire non-3D image data corresponding to each of the plurality of the real objects.

12. The apparatus of claim 8 , wherein the logic is further to: generate, via a hierarchy generator, a hierarchical volumetric representation of each of the plurality of real objects to detect an empty part of each of the plurality of real objects.

13. The apparatus of claim 8 , wherein one or more of the plurality of real objects is a storage space, wherein the logic is further to: generate, via a storage space boxer, a maximum enclosed bounded box for the storage space.

14. A method comprising:
generating, by at least one sensor, a three-dimensional (3D) digital model of a plurality of real objects based on sensor data for each of the plurality of real objects;
generating, by an object boxer, a bounding box for each of the plurality of real objects; and
determining, by a packing plan generator, a spatially efficient packing sequence for the plurality of real objects, wherein at least one of the plurality of real objects contains at least one other of the plurality of real objects.

15. The method of claim 14 , wherein one or more of the plurality of real objects is an item, and wherein the method further includes:
approximating a size and a shape for each item in voxels;
generating a minimal enclosing bounding box for each item;
determining if any two or more items are mergeable into a bounding box that occupies less volume than a sum of volumes for each individual minimal enclosing bounding box for each of the two or more items; and
merging the two or more items together in the bounding box if it is determined that the two or more items are mergeable.

16. The method of claim 15 , further including:
computing a free space value (FS) of each item with respect to each minimal enclosing bounding box for each item; and
merging the two or more items into one bounding box if it is determined that a merger criterion is met.

17. The method of claim 14 , further including identifying each of the plurality of real objects and acquiring non-3D image data corresponding to each of the plurality of the real objects.

18. The method of claim 14 , further including generating a hierarchical volumetric representation of each of the plurality of real objects to detect an empty part of each of the plurality of real objects.

19. The method of claim 15 , wherein one of the plurality of real objects is a storage space, the method further including generating a maximum enclosed bounded box for the storage space.

20. At least one non-transitory computer readable storage medium comprising a set of instructions, which when executed by an apparatus, cause the apparatus to:
generate a three-dimensional (3D) digital model of a plurality of real objects based on sensor data for each of the plurality of real objects;
generate a bounding box for each of the plurality of real objects; and
determine a spatially efficient packing sequence for the plurality of real objects, wherein at least one of the plurality of real objects contains at least one other of the plurality of real objects.

21. The at least one non-transitory computer readable storage medium of claim 20 , wherein one or more of the plurality of real objects is an item, and wherein the instructions, when executed, cause a

Assignees

• Madmony Maoz
• Fleishman Shahar
• Kliger Mark
• Kutliroff Gershom
• Intel Corp

Inventors

• Madmony Maoz
• Fleishman Shahar
• Kliger Mark
• Kutliroff Gershom

Classifications

• G06F2113/20

  Packaging, e.g. boxes or containers · CPC title

• G06F30/00 Primary

  Computer-aided design [CAD] · CPC title

• G06F16/5854

  using shape and object relationship · CPC title

• G06F17/50 Primary

  Physics · mapped topic

• G06F2217/38

  Physics · mapped topic