CA-3190171-C - A SELECTOR FOR ROBOT-RETRIEVABLE ITEMS

CA3190171CCA 3190171 CCA3190171 CCA 3190171CCA-3190171-C

Abstract

The present invention provides a retrieval controller for identifying an item to be retrieved from a flat storage surface by a robot so as to solve the problem of identifying one item, amongst a collection of items stored on a common surface that can be retrieved by a robot equipped with a lateral-motion gripper. To achieve this, the present invention provides a retrieval controller comprising a depth map computing unit arranged to establish a global coordinate system, establish an orthonormal set of basis vectors u, v and w defined in the global coordinate system, where w is approximately orthogonal to the surface that the items are stored on, receiving a depth map from a depth sensor, converting the received depth map into a 3D Point Cloud defined in the global coordinate system, computing a representation of a partitioning into segments of the 3D Points of the 3D Point Cloud such that a segment contains a pair of 3D Points only if the 3D points should be considered to be part of the surface of the same item and a prism calculating unit arranged to compute a right, enclosing prism for each segment. The retrieval controller further comprises a vector determination unit arranged to compute each of: a) outwards-pointing normal of each w-aligned face of each computed right, enclosing prism, b) outwards-pointing normal of each w-aligned edge of each computed right, enclosing prism and c) which w-aligned edges of each computed right, enclosing prism correspond to grasp points that should be precluded from an item selection process. Moreover, the retrieval controller comprises an item selection unit arranged to iterate over the w-aligned edges of each right, enclosing prism, that do not correspond to grasp points that should be precluded from the item selection process, computing a pair of quadrilateral-based, right prisms for each such a w-aligned edge, checking whether or not the interior of either of the two quadrilateral-based, right prisms associated with a w-aligned edge intersects any of the right, enclosing prisms and a robot instructing unit arranged to instruct the robot to retrieve the item based on uv coordinates of one or more w-aligned edges whose associated quadrilateral-based, right prisms do not have interiors that intersect any of the right, enclosing prisms as selected by the item selection unit.

Inventors

Osemwaro Jeremiah Oghenetega PEDRO

Assignees

OCADO INNOVATION LIMITED

Dates

Publication Date: 20260505
Application Date: 20210809
Priority Date: 20200811

Claims (1)

28 Claims 1. A retrieval controller for identifying an item to be retrieved from a flat storage surface by a robot, the retrieval controller comprising: a depth map computing unit 5 arranged to establish a global coordinate system, establish an orthonormal set of basis vectors u, v and w defined in the global coordinate system, where w is approximately orthogonal to the surface that the items are stored on, receiving a depth map from a depth sensor, converting the received depth map into a 3D Point Cloud defined in the global coordinate system, computing a representation of a partitioning into segments of the 3D 10 Points of the 3D Point Cloud such that a segment contains a pair of 3D Points only if the 3D points are considered to be part of the surface of the same item; a prism calculating unit arranged to compute a right, enclosing prism for each segment; a vector determination unit arranged to compute each of: a. outwards‐pointing normal of each w‐aligned face of each computed right, 15 enclosing prism, b. outwards‐pointing normal of each w‐aligned edge of each computed right, enclosing prism, c. which w‐aligned edges of each computed right, enclosing prism correspond to grasp points that are precluded from an item selection process; 20 an item selection unit arranged to iterate over the w‐aligned edges of each right, enclosing prism, that do not correspond to grasp points that are precluded from the item selection process, computing a pair of quadrilateral‐based, right prisms for each such a w‐aligned edge, checking whether or not the interior of either of the two quadrilateral‐based, right prisms associated with a w‐aligned edge intersects any of the right, enclosing prisms; 25 a robot instructing unit arranged to instruct the robot to retrieve the item based on uv coordinates of one or more w‐aligned edges whose associated quadrilateral‐based, right prisms do not have interiors that intersect any of the right, enclosing prisms as selected by the item selection unit. 30 2. The retrieval controller according to Claim 1, wherein the base of each right, enclosing prism is a simple polygon that is orthogonal to w. 3. The retrieval controller according to any one of Claims 1 ‐ 2, wherein each right, enclosing prism contains all of the 3D Points that constitute its associated segment. 29 CAN_DMS: \1007418587\1 4. The retrieval controller according to any one of Claims 1 ‐ 3, wherein each right, enclosing prism has minimal volume. 5. The retrieval controller according to any one of Claims 1 ‐ 4, wherein the pair of quadrilateral‐based, right prisms associated with 5 any given w‐aligned edge are adjacent to that edge’s two neighbouring w‐aligned faces. 6. The retrieval controller according to any one of Claims 1 ‐ 5, wherein the bases of each quadrilateral‐based, right prism associated with any given w‐aligned edge are parallel to the uv 10 plane. 7. The retrieval controller according to any one of Claims 1 ‐ 6, wherein each quadrilateralbased, right prism associated with any given w‐aligned edge has four edges that are parallel to that w‐aligned edge, and wherein one of these four edges lies in the plane containing that w15 aligned edge and that w‐aligned edge’s normal. 8. The retrieval controller according to any one of Claims 1 ‐ 7, wherein for each quadrilateral‐based, right prism associated with any given w‐aligned edge, the minimal and maximal projections of the quadrilateral‐based, right prism’s vertices onto the w axis are equal 20 to the minimal and maximal projections of the w‐aligned edge onto the w axis. 9. The retrieval controller according to any one of Claims 1 ‐ 8, wherein the vector determination unit is further arranged to identify which w‐aligned edges of a computed right, enclosing prism correspond to grasp points that are precluded from the item selection process 25 by: a. computing the uv coordinates of the centroid of the flat storage surface; b. computing the centroid of the uv coordinates of the right, enclosing prism’s vertices; c. identifying the one or more w‐aligned edges whose normals are closest in 30 orientation to the vector that runs from the former centroid to the latter centroid. 10. The retrieval controller according to any one of Claims 1 ‐ 9, wherein the vector determination unit is further arranged to identify which w‐aligned edges of a computed right, enclosing prism correspond to grasp points that are precluded from the item selection process 35 by: CAN_DMS: \1007418587\1 a. computing a minimal area convex polygon K that encloses the storage surface’s projection onto the uv plane; b. computing the uv coordinates of the vertices of the right, enclosing prism; c. excluding a given w‐aligned edge’s grasp points from the item selection process 5 only if one of the following conditions holds: i. the minimal area convex polygon K encloses a projected edge of the right, enclosing prism, and translating that projected edge a predetermined distance in the opposite direction of the w‐aligned edge’s normal would cause the projected edge to cross an edge of the minimal area convex polygon K; or 10 ii. part of a projected edge of the right, enclosing prism lies outside the minimal area convex polygon K, and translating that projected edge a userspecified distance in the opposite direction of the w‐ aligned edge’s normal would move the projected edge further from the closest edge of the minimal area convex polygon K. 11. A system comprising: a depth sensor for generating a depth map of an item stored on one or more stacked surfaces; a robot for grasping the item; and 20 a retrieval controller according to any one of Claims 1 ‐ 10arranged to control the robot to grasp the item. 12. A storage system comprising: a first set of parallel rails or tracks extending in an X‐direction, and a second set of parallel 25 rails or tracks extending in a Y‐direction transverse to the first set in a substantially horizontal plane to form a grid pattern comprising a plurality of grid spaces; a plurality of stacks of containers located beneath the rails, and arranged such that each stack is located within a footprint of a single grid space; at least one transporting device, the at least one transporting device being arranged to 30 selectively move in the X and/or Y directions, above the stacks on the rails and arranged to transport a container; a picking station arranged to receive a container transported by the at least one transporting device; and a system according to Claim 11, wherein the system is arranged to grasp an item and place 35 it in a container at the picking station. 31 CAN_DMS: \1007418587\1 13. The storage system according to Claim 12, wherein the at least one transporting device has a footprint that occupies only a single grid space in the storage system, such that a transporting device occupying one grid space does not obstruct a transporting device occupying or traversing the 5 adjacent grid spaces in the X and/or Y directions. 14. A method of identifying an item to be retrieved from a flat storage surface by a robot, the method comprising the steps of: a. establishing a global coordinate system; 10 b. establishing an orthonormal set of basis vectors u, v and w defined in the global coordinate system, where w is approximately orthogonal to the surface that the items are stored on; c. receiving a depth map from a depth sensor; d. converting the received depth map into a 3D Point Cloud defined in the global 15 coordinate system; e. computing a representation of a partitioning into segments of the 3D Points of the 3D Point Cloud that were observed to be lying on the surfaces of the items that are to be retrieved, such that a segment contains a pair of 3D Points only if the 3D points are considered to be part of the surface of the same item; 20 f. computing a right, enclosing prism for each segment; g. computing the outwards‐pointing normal of each w‐aligned face of each right, enclosing prism; h. computing the outwards‐pointing normal of each w‐aligned edge of each right, enclosing prism; 25 i. computing which w‐aligned edges of each right, enclosing prism correspond to grasp points that are precluded from an item selection process; j. iterating over the w‐aligned edges of each right, enclosing prism, that do not correspond to grasp points that are precluded from the item selection process; k. computing a pair of quadrilateral‐based, right prisms for each such a w‐aligned 30 edge; l. checking whether or not the interior of either of the two quadrilateral‐based, right prisms associated with a w‐aligned edge intersects any of the right, enclosing prisms; m. instructing the robot to retrieve the item based on the uv coordinates of one or more w‐aligned edges whose associated quadrilateral‐based, right prisms do not have 35 interiors that intersect any of the right, enclosing prisms. 32 CAN_DMS: \1007418587\1 15) The method according to Claim 14, wherein the base of each right, enclosing prism is a simple polygon that is orthogonal to w. 16) The method according to any one of Claims 14 to 15, wherein 5 each right, enclosing prism contains all of the 3D Points that constitute its associated segment. 17) The method according to any one of Claims 14 to 16, wherein each right, enclosing prism has minimal volume. 18) The method according to any one of Claims 14 to 17, wherein the pair of quadrilateralbased, right prisms associated with any given w-aligned edge are adjacent to that edge’s two neighbouring w-aligned faces. 15 19) The method according to any one of Claims 14 to 18, wherein the bases of each quadrilateral-based, right prism associated with any given w-aligned edge are parallel to the uv plane. 20) The method according to any one of Claims 14 to 19, wherein each quadrilateral-based, 20 right prism associated with any given w-aligned edge has four edges that are parallel to that waligned edge, and wherein one of these four edges lies in the plane containing that w-aligned edge and that w-aligned edge’s normal. 21) The method according to any one of Claims 14 to 20, wherein for each quadrilateral25 based, right prism associated with any given w-aligned edge, the minimal and maximal projections of the quadrilateral-based, right prism’s vertices onto the w axis are equal to the minimal and maximal projections of the w-aligned edge onto the w axis. 22) The method according to any one of Claims 14 to 21, wherein the step of computing which 30 w-aligned edges of each right, enclosing prism correspond to grasp points are precluded from an item selection process comprises: a. computing the uv coordinates of the centroid of the flat storage surface; b. computing the centroid of the uv coordinates of the right, enclosing prism’s vertices; 33 CAN_DMS: \1007418587\1 c. identifying the one or more w‐aligned edges whose normals are closest in orientation to the vector that runs from the former centroid to the latter centroid. 23. The method according to any one of Claims 14 to 22, wherein the step of computing which w‐aligned edges of each right, enclosing 5 prism correspond to grasp points are precluded from an item selection process comprises: a. computing a minimal area convex polygon K that encloses the storage surface’s projection onto the uv plane; b. computing the uv coordinates of the vertices of the right, enclosing prism; 10 c. excluding a given w‐aligned edge’s grasp points from the item selection process only if one of the following conditions holds: i. the minimal area convex polygon K encloses a projected edge of the right, enclosing prism, and translating that projected edge a predetermined distance in the opposite direction of the w‐aligned edge’s normal would cause the projected 15 edge to cross an edge of the minimal area convex polygon K; or ii. part of a projected edge of the right, enclosing prism lies outside the minimal area convex polygon K, and translating that projected edge a userspecified distance in the opposite direction of the w‐ aligned edge’s normal would move the projected edge further from the closest edge of the minimal area convex 20 polygon K.

Description

1 A Selector for Robot‐Retrievable Items Technical Field The present invention relates generally to the field 5 of vision‐guided robotics and the use of visually‐guided robots as retrieval systems in, for example, warehouses. Background 10 A common practice, when preparing items of a given type for warehouse storage, is to pack the items onto flat surfaces, and to stack these layers of items on top of each other (on pallets), to save space. Automating the process of retrieving items stored in this manner often proves to be more cost‐effective than using manual labourers. In highly‐controlled environments in which the items are always kept in known locations (or in which the items can always be manoeuvred into 15 known locations), and in which the destinations that the items must be moved to are fixed and in a known state (e.g. free of obstruction), such automation can be achieved by “blind” material handling equipment that does not rely on sensors to locate either the items or their destinations. However, in environments in which it is not practical, feasible or desirable to impose strict constraints on the locations of the items or on the location or state of their destinations, the 20 information about the locations and destinations of the items must come from sensor readings, and the machines used to retrieve and move the items must be flexible enough to be able to cope with any variations that may arise in their locations and destinations. In order to satisfy the latter requirement, it will typically be necessary to use some form of programmable industrial robot. Over the past few years, an ever‐growing range of Depth Sensors have become commercially available that are capable of producing real‐time Depth Maps or 3D Point Clouds that can be used to determine the locations of objects up to 2m away to sub centimetre accuracy. The low cost of some of these sensors, together with their satisfactory level of accuracy, makes them an 30 attractive option for a sensor‐based retrieval system. Given a Depth Sensor that is in a known position relative to a robot and that is observing the items that are to be retrieved, it will be necessary at some point for the retrieval system to select which item or items to retrieve next. The question of which items can be retrieved depends on 35 what kind of gripper the robot is equipped with, as this determines the directions that the gripper 2 CAN_DMS: \1007417284\1 can move in when approaching the items. A gripper that approaches the items from above, and that only needs to make contact with the uppermost surface of each item, can always grasp every item, if the items do not overlap each other. But a gripper that must approach the items with a motion that has a horizontal component, or that needs to make contact with the sides of each item, cannot grasp an item if the space that it 5 must move through en‐route to that item's grasp points is occupied by any other items. Thus, when using such a gripper, the process of selecting which item to retrieve next must be based on an assessment of which items appear to have sufficient clearance in the 3D Point Cloud data acquired from the Depth Sensor. Henceforth such grippers will be referred to as “lateral‐motion grippers”. Summary In view of the problems of identifying one item amongst a collection of items stored on a common surface that can be retrieved by a robot equipped with a lateral‐motion gripper, the present 15 invention aims to provide an apparatus and method for retrieval of such items by way of automated means. According to the present invention there is provided a retrieval controller for identifying an item to be retrieved from a flat storage surface by a robot. The retrieval controller comprises a depth 20 map computing unit arranged to establish a global coordinate system, establish an orthonormal set of basis vectors u, v and w defined in the global coordinate system, where w is approximately orthogonal to the surface that the items are stored on, receiving a depth map from a depth sensor, converting the received depth map into a 3D Point Cloud defined in the global coordinate system, computing a representation of a partitioning into segments of the 3D Points of the 3D 25 Point Cloud such that a segment contains a pair of 3D Points only if the 3D points should be considered to be part of the surface of the same item and a prism calculating unit arranged to compute a right, enclosing prism for each segment. The retrieval controller further comprises a vector determination unit arranged to compute each of: a) outwards‐pointing normal of each waligned face of each computed right, enclosing prism, b) outwards‐pointing normal of each w30 aligned edge of each computed right, enclosing prism and c) which w‐aligned edges of each computed right, enclosing prism correspond to grasp points that should be precluded from an item selection process. Moreover, the retrieval controller comprises an item selection unit arranged to i