Stability prediction for three dimensional robotic bin packing

1 . A method comprising:

picking, by a robotic arm, a first item for placement in a first bin, the first bin containing at least one other item;

determining, for a first candidate placement position in the first bin, a first set of contact points in an x-y plane, where the first item is projected to contact at least one of the first bin or the at least one other item when placed in the first candidate placement position, wherein the x-y plane is parallel to a bottom of the first bin;

determining a first contact point of the first set of contact points with a minimum x-coordinate value among the first set of contact points;

determining a second contact point of the first set of contact points with a maximum x-coordinate value among the first set of contact points;

determining a first line between the first contact point and the second contact point;

determining a third contact point that is a farthest contact point from the first line from among the first set of contact points;

determining a centroid of the first item;

determining that the centroid is located outside of a first triangle with vertices comprising the first contact point, the second contact point, and the third contact point; and

placing, by the robotic arm, the first item at a second candidate placement position in the first bin.

2 . The method of claim 1 , further comprising:

determining a second line between the first contact point and the third contact point;

determining a fourth contact point that is a farthest contact point from the second line;

determining that the centroid is located inside of a second triangle with vertices of the first contact point, the third contact point, and the fourth contact point; and

determining that the first candidate placement position is a stable candidate placement position based on the centroid being located inside of the second triangle.

3 . The method of claim 1 , further comprising:

determining a first area of the first set of contact points;

determining a second area of the first item in the x-y plane;

determining a ratio of the first area to the second area;

determining that the ratio is below a threshold ratio; and

placing, by the robotic arm, the first item at the second candidate placement position in the first bin based at least in part on the ratio being below the threshold ratio.

4 . A method comprising:

picking, by a robotic manipulator, a first item for placement;

determining, for a first candidate placement position, a first set of contact points for the first item placed at the first candidate placement position by the robotic manipulator;

determining a first contact point among the first set of contact points having a minimum coordinate value along a first coordinate dimension;

determining a second contact point among the first set of contact points having a maximum coordinate value along the first coordinate dimension;

determining a first line between the first contact point and the second contact point;

determining a third contact point that is a farthest contact point from the first line from among the first set of contact points;

determining a centroid of the first item;

determining that the centroid is located outside of a first triangle with vertices comprising the first contact point, the second contact point, and the third contact point; and

placing, by the robotic manipulator, the first item at a second candidate placement position.

5 . The method of claim 4 , further comprising:

determining, based at least in part on the centroid of the first item being located outside of the first triangle, that the first candidate placement position represents an unstable placement position for the first item.

6 . The method of claim 4 , further comprising:

determining a second line between the first contact point and the third contact point;

determining a fourth contact point that is a farthest contact point from the second line;

determining that the centroid is located inside of a second triangle with vertices comprising the first contact point, the third contact point, and the fourth contact point; and

determining that the first candidate placement position is a stable candidate placement position based on the centroid being located inside of the second triangle.

7 . The method of claim 4 , further comprising:

determining a first area of the first set of contact points;

determining a second area of the first item in a first plane;

determining a ratio of the first area to the second area;

determining that the ratio is below a threshold ratio; and

placing, by the robotic manipulator, the first item at the second candidate placement position in the first bin based at least in part on the ratio being below the threshold ratio.

8 . The method of claim 4 , further comprising:

determining a second line between the first contact point and the third contact point; and

determining a second triangle, different from the first triangle, wherein one side of the second triangle comprises the second line.

9 . The method of claim 8 , further comprising:

determining that the centroid is located within the second triangle; and

determining that the first candidate placement position is a stable candidate placement position.

10 . The method of claim 9 , further comprising:

determining a degree of stability of the first candidate placement position based at least in part on an area of the first set of contact points and an area of the first item.

11 . The method of claim 10 , further comprising:

selecting the second candidate placement position over the first candidate placement position based on the degree of stability.

12 . The method of claim 4 , wherein the third contact point is the farthest contact point from the first line among a set of points in a first hyperplane on a first side of the first line, the method further comprising:

determining a fourth contact point that is a farthest contact point from the first line among a set of points in a second hyperplane on a second side of the first line, wherein the determining the fourth contact point is performed in parallel with the determining the third contact point; and

determining that the centroid is located outside of a second triangle with vertices comprising the first contact point, the second contact point, and the fourth contact point, wherein the determining that the centroid is located outside of the second triangle is performed in parallel with the determining that the centroid is located outside of the first triangle.

13 . A system comprising:

at least one processor; and

non-transitory computer-readable memory storing instructions that, when executed by the at least one processor, are configured to:

pick, by a robotic manipulator, a first item for placement;

determine, for a first candidate placement position, a first set of contact points for the first item placed at the first candidate placement position by the robotic manipulator;

determine a first contact point among the first set of contact points having a minimum coordinate value along a first coordinate dimension;

determine a second contact point among the first set of contact points having a maximum coordinate value along the first coordinate dimension;

determine a first line between the first contact point and the second contact point;

determine a third contact point that is a farthest contact point from the first line from among the first set of contact points;

determine a centroid of the first item;

determine that the centroid is located outside of a first triangle with vertices comprising the first contact point, the second contact point, and the third contact point; and

place, by the robotic manipulator, the first item at a second candidate placement position.

14 . The system of claim 13 , the non-transitory computer-readable memory storing further instructions that, when executed by the at least one processor, are further effective to:

determine, based at least in part on the centroid of the first item being located outside of the first triangle, that the first candidate placement position represents an unstable placement position for the first item.

15 . The system of claim 13 , the non-transitory computer-readable memory storing further instructions that, when executed by the at least one processor, are further effective to:

determine a second line between the first contact point and the third contact point;

determine a fourth contact point that is a farthest contact point from the second line;

determine that the centroid is located inside of a second triangle with vertices comprising the first contact point, the third contact point, and the fourth contact point; and

determine that the first candidate placement position is a stable candidate placement position based on the centroid being located inside of the second triangle.

16 . The system of claim 13 , the non-transitory computer-readable memory storing further instructions that, when executed by the at least one processor, are further effective to:

determine a first area of the first set of contact points;

determine a second area of the first item in a first plane;

determine a ratio of the first area to the second area;

determine that the ratio is below a threshold ratio; and

place, by the robotic manipulator, the first item at the second candidate placement position in the first bin based at least in part on the ratio being below the threshold ratio.

17 . The system of claim 13 , the non-transitory computer-readable memory storing further instructions that, when executed by the at least one processor, are further effective to:

determine a second line between the first contact point and the third contact point; and

determine a second triangle, different from the first triangle, wherein one side of the second triangle comprises the second line.

18 . The system of claim 17 , the non-transitory computer-readable memory storing further instructions that, when executed by the at least one processor, are further effective to:

determine that the centroid is located within the second triangle; and

determine that the first candidate placement position is a stable candidate placement position.

19 . The system of claim 18 , the non-transitory computer-readable memory storing further instructions that, when executed by the at least one processor, are further effective to:

determine a degree of stability of the first candidate placement position based at least in part on an area of the first set of contact points and an area of the first item.

20 . The system of claim 19 , the non-transitory computer-readable memory storing further instructions that, when executed by the at least one processor, are further effective to:

select the second candidate placement position over the first candidate placement position based on the degree of stability.