Method for automatically generating waypoints for imaging shelves within a store

• US 10,399,230 B2
• Filed: 05/19/2017
• Issued: 09/03/2019
• Est. Priority Date: 05/19/2016
• Status: Expired due to Fees

• Current Assignee: Simbe Robotics, Inc.
• Original Assignee: Simbe Robotics, Inc.
• Inventors: Shah, Mirza Akbar, Bogolea, Bradley, Gee, Jeffrey, Safi, Jariullah, Fraser, Luke
• Primary Examiner(s): Tran, Dalena
• Application Number:
  US15/600,556
• Publication Number:
  US 20180001481A1
• Time in Patent Office: 837 Days
• Field of Search: 700245, 700259, 705 28, 345427, 382103, 382212
• CPC Class Codes: B25J 11/008 Manipulators for service tasks
• CPC Class Codes: B25J 13/089 Determining the position of the robot with reference to its environment
• CPC Class Codes: B25J 19/023 including video camera means
• CPC Class Codes: B25J 9/1664 characterised by motion, path, trajectory planning
• CPC Class Codes: B25J 9/1697 Vision controlled systems
• CPC Class Codes: B64U 2101/30 for imaging, photography or videography
• CPC Class Codes: B64U 2201/20 Remote controls
• CPC Class Codes: G06Q 10/087 Inventory or stock management, e.g. order filling, procurement or balancing against orders
• CPC Class Codes: G06Q 20/00 Payment architectures, schemes or protocols apparatus for performing or posting payment transactions G07F7/08, G07F19/00; electronic cash registers G07G1/12
• CPC Class Codes: G06Q 30/0201 Market modelling; Market analysis; Collecting market data
• CPC Class Codes: G06T 5/80 Geometric correction
• CPC Class Codes: G06T 7/0008 checking presence/absence
• CPC Class Codes: G06V 20/20 in augmented reality scenes

Abstract

One variation of a method for automatically generating waypoints for imaging shelves within a store includes: dispatching a robotic system to autonomously generating a map of a floor space within the store; accessing an architectural metaspace defining target locations and addresses of the set of shelving structures within the store; distorting the architectural metaspace into alignment with the map to generate a normalized metaspace representing real locations and addresses of the set of shelving structures in the store; defining a set of waypoints distributed longitudinally along and offset laterally from a first shelving structure represented in the normalized metaspace based on a known position of an optical sensor in the robotic system; and dispatching the robotic system to record optical data while occupying the set of waypoints during an imaging routine.

Claims

1. A method for automatically generating waypoints for imaging shelves within a store comprises:

dispatching a robotic system to autonomously collect map data of a floor space within the store during a mapping routine;

generating a map of the floor space from map data collected by the robotic system during the mapping routine;

accessing an architectural metaspace defining target locations and addresses of the set of shelving structures within the store;

distorting features in the architectural metaspace into alignment with like features in the map to generate a normalized metaspace representing real locations and addresses of the set of shelving structures in the store;

defining a coordinate system within the normalized metaspace;

defining a set of waypoints within the normalized metaspace relative to the coordinate system, the set of waypoints comprising a first subset of waypoints distributed longitudinally along and offset laterally from a real location of a first shelving structure, in the set of shelving structures, represented in the normalized metaspace, each waypoint in the first subset of waypoints defining an orientation relative to the coordinate system based on a known position of an optical sensor in the robotic system and the real location of the first shelving structure in the normalized metaspace; and

dispatching the robotic system to record optical data while occupying each waypoint in the first subset of waypoints during an imaging routine.

2. The method of claim 1:

further comprising;

accessing, from a planogram of the store, a first elevation map associated with a first address of the first shelving structure, the first elevation map specifying locations of product facings assigned to a first side of the first shelving structure;

extracting locations of a first set of shelving segments in the first shelving structure from the first elevation map; and

projecting locations of the first set of shelving segments onto the location of the first shelving structure in the normalized metaspace to locate shelving segments in the first shelving structure in the normalized metaspace;

wherein defining the set of waypoints within the normalized metaspace comprises;

defining waypoints longitudinally centered between each shelving segment in the first shelving structure represented in the normalized metaspace; and

calculating an angular orientation normal to a longitudinal face of the first shelving structure, relative to the coordinate system, in the normalized metaspace; and

writing the angular orientation to each waypoint in the first subset of waypoints.

3. The method of claim 2, further comprising:

for each shelving segment in each shelving structure represented in the normalized metaspace, calculating a linear combination of values of products assigned to the shelving segment by the planogram;

for each waypoint in the set of waypoints, assigning a value to the waypoint based on a linear combination of values of products assigned to a shelving segment adjacent the waypoint;

defining an order for the set of waypoints based on values assigned to the set of waypoints; and

serving the order for the set of waypoints to the robotic system for execution during the imaging routine.

4. The method of claim 3, wherein defining the order for the set of waypoints comprises calculating the order for the set of waypoints that minimizes total distance traversed by the robotic system from a docking station within the store, to a first waypoint adjacent a first shelving segment associated with a greatest linear combination of values of assigned products, to a second waypoint adjacent a second shelving segment associated with a lowest linear combination of values of assigned products, and back to the docking location.

5. The method of claim 2, wherein generating the normalized metaspace comprises generating the normalized metaspace representing real gaps between shelving structures, misalignment of adjacent shelving structures, shelving structures in the store omitted from the architectural plan, shelving structures in the store added over the architectural plan, and positions of shelving segments within the store.

6. The method of claim 2:

further comprising extracting a height of the first shelving structure from the first elevation map; and

wherein defining the set of waypoints within the normalized metaspace comprises;

calculating a target lateral offset distance from the first shelving structure based on the height of the first shelving structure and optical capabilities of a camera integrated into the robotic system; and

defining the first subset of waypoints offset laterally from the longitudinal face of the first shelving structure by the target lateral offset distance.

7. The method of claim 2, further comprising:

for each waypoint in the set of waypoints, labeling the waypoint with an address of a particular shelving structure and a particular shelving segment predicted to fall within a field of view of the optical sensor when the robotic system occupies a location and an orientation defined by the waypoint;

during the imaging routine, receiving a first image recorded by the robotic system while occupying a first waypoint, in the set of waypoints, adjacent a first shelving segment in the first shelving structure;

accessing a first list of identifiers of products assigned to the first shelving segment based on a first address of the first shelving segment stored with the first waypoint;

retrieving a first set of template images, from a database of template images, representing products in the first list of products stored with the first waypoint; and

identifying products on shelves in the first shelving segment based on similarities between features detected in the first image and template images in the first set of template images.

8. The method of claim 2, further comprising:

during the imaging routine, receiving a first image recorded by a first camera in the robotic system while occupying a first waypoint adjacent a first shelving segment in the first shelving structure;

projecting heights of a first set of shelves assigned to the first shelving segment by the first elevation map onto the first image based on a known position of the first camera on the robotic system;

identifying a first region in the image corresponding to a first shelf in the first shelving segment;

extracting a first list of identifiers of products assigned to the first shelf by the first elevation map;

retrieving a first set of template images, from a database of template images, representing products in the first list of products; and

identifying products on the first shelf based on similarities between features detected in the first region of the first image and template images in the first set of template images.

9. The method of claim 1, wherein generating the normalized metaspace comprises:

detecting shelving structures represented in the map;

detecting shelving structures represented in the architectural metaspace;

calculating a transform that approximately centers shelving structures detected in the map onto shelving structures detected in the architectural metaspace; and

applying the transform to shelving structures and to locations of shelving structure addresses in the architectural metaspace to generate the normalized metaspace.

10. The method of claim 9,

wherein accessing the architectural metaspace comprises accessing a standardized store layout for a retail brand associated with the store, the standardized store layout defining generic target locations of shelving structures in stores associated with the retail brand;

wherein detecting shelving structures represented in the architectural metaspace comprises detecting shelving structures represented in the standardized store layout;

wherein calculating the transform comprises calculating the transform that approximately centers a first subset of shelving structures detected in the map to a first subset of shelving structures detected in the standardized store layout;

wherein applying the transform to shelving structures and to locations of shelving structure addresses in the architectural metaspace comprises initializing the normalized metaspace with locations and addresses of the first subset of shelving structures; and

further comprising;

identifying a second subset of shelving structures in the map that deviate from locations of nearest shelving structures in the standardized store layout by more than a threshold distance; and

prompting a user to manually link the second subset of shelving structures in the map to a second subset of shelving structures in the standardized store layout;

inserting the second subset of shelving structures in the map into the normalized metaspace; and

writing addresses from the second subset of shelving structures in the architectural metaspace onto the second subset of shelving structures in the normalized metaspace based on manual links provided by the user.

11. method of claim 1:

wherein dispatching the robotic system to autonomously collect map data of the floor space within the store comprises dispatching the robotic system to autonomously collect map data of the floor space within the store in response to indication of a change to the store layout entered through an operator portal at a computing device;

wherein generating the normalized metaspace comprises generating the normalized metaspace representing the change to the store layout; and

wherein defining the set of waypoints comprises defining the set of waypoints according to the change to the store layout represented in the normalized metaspace.

12. The method of claim 1, further comprising:

receiving a first image recorded by the robotic system while occupying a first location during the mapping routine;

scanning the first image for a first aisle address;

projecting the first aisle address onto the map based on the first location of the robotic system and a known position of a camera integrated into the robotic system; and

confirming alignment of the architectural metaspace to the map based on alignment between the first aisle address and addresses imported from the architectural metaspace into the normalized metaspace.

13. The method of claim 1, further comprising:

accessing a first image comprising visual data recorded by the robotic system when occupying a first waypoint in the set of waypoints during the imaging routine;

detecting a first shelf in the first image;

determining an address of the first shelf based on a first address of a first shelving structure associated with the first waypoint and a vertical position of the first shelf within the first image;

based on the address of the first shelf, retrieving a first list of products assigned to the first shelf by a planogram of the store;

retrieving a first set of template images from a database of template images, each template image in the first set of template images comprising visual features of a product specified in the first list of products;

extracting a first set of features from a first region of the first image adjacent the first shelf;

confirming presence of a unit of a first product, in the first list of products, on the first shelf in response to correlation between features in the first set of features and features in a first template image, in the first set of template images, representing the first product;

determining that a unit of the first product is improperly stocked on the first shelf in response to deviation between features in the first set of features and features in the first template image; and

in response to determining that the unit of the first product is improperly stocked on the first shelf, generating a first restocking prompt for the first product on the first shelf.

14. The method of claim 1, further comprising:

at the robotic system, during the imaging routine;

detecting a matrix barcode in a field of view of a second optical sensor in the robotic system;

calculating a temporary waypoint based on a position and an orientation of the matrix barcode in the field of view of the second optical sensor, the temporary waypoint defining a first location and a first orientation that aligns a field of view of the optical sensor to a temporary shelving structure coupled to the matrix barcode;

recording a first image through the optical sensor while occupying the temporary waypoint;

determining an identity of the temporary shelving structure based on the matrix barcode;

based on the identity of the temporary shelving structure, retrieving a first list of products assigned to the temporary shelving structure by a planogram of the store;

retrieving a first set of template images from a database of template images, each template image in the first set of template images comprising visual features of a product specified in the first list of products;

confirming presence of a unit of a first product, in the first list of products, on the temporary shelving structure in response to correlation between features in the first image and features in a first template image, in the first set of template images, representing the first product;

determining that a unit of a second product is improperly stocked on the temporary shelving structure in response to deviation between features in the first image and features in a second template image, in the first set of template images, representing the second product; and

in response to determining that the unit of the second product is improperly stocked on the temporary shelving structure, generating a first restocking prompt for the second product on the temporary shelving structure.

15. The method of claim 14, wherein calculating the temporary waypoint comprises:

calculating a position and an orientation of a front face of the temporary shelving structure relative to the coordinate system based on the position and the orientation of the matrix barcode in the field of view of the second optical sensor and a position and an orientation of the robotic system relative to the coordinate system;

applying a target imaging distance, for the optical sensor, from the front face of the temporary shelving structure to calculate the temporary waypoint.

16. A method for automatically generating waypoints for imaging shelves within a store comprises:

dispatching a robotic system to autonomously map a floor space within the store;

receiving a map of the floor space from the robotic system;

accessing an architectural metaspace defining locations of shelving structures and addresses of shelving structures within the store;

generating a normalized metaspace by aligning features in the architectural metaspace to features in the map;

defining a coordinate system for the store within the normalized metaspace;

defining a set of waypoints within the normalized metaspace based on positions of shelving structures within the normalized metaspace and imaging capabilities of the robotic system, each waypoint comprising a location and orientation relative to the coordinate system;

labeling each waypoint in the set of waypoints with an address of a shelving structure proximal the waypoint;

uploading the set of waypoints to the robotic system for execution in a subsequent imaging routine;

accessing a first image comprising visual data recorded by the robotic system when occupying a first waypoint in the set of waypoints during the imaging routine;

detecting a first shelf in the first image;

determining an address of the first shelf based on a first address of a first shelving structure associated with the first waypoint and a vertical position of the first shelf within the first image;

based on the address of the first shelf, retrieving a first list of products assigned to the first shelf by a planogram of the store;

retrieving a first set of template images from a database of template images, each template image in the first set of template images comprising visual features of a product specified in the first list of products;

extracting a first set of features from a first region of the first image adjacent the first shelf; and

confirming presence of a unit of a first product, in the first list of products, on the first shelf in response to correlation between features in the first set of features and features in a first template image, in the first set of template images, representing the first product.

17. The method of claim 16, further comprising:

determining that a unit of the first product is improperly stocked on the first shelf in response to deviation between features in the first set of features and features in the first template image; and

in response to determining that the unit of the first product is improperly stocked on the first shelf, generating a first restocking prompt for the first product on the first shelf.

18. method of claim 16:

further comprising;

accessing, from a planogram of the store, a first elevation map associated with a first address of the first shelving structure, the first elevation map specifying locations of product facings assigned to a first side of the first shelving structure;

extracting locations of a first set of shelving segments in the first shelving structure from the first elevation map; and

projecting locations of the first set of shelving segments onto the location of the first shelving structure in the normalized metaspace to locate shelving segments in the first shelving structure in the normalized metaspace;

wherein defining the set of waypoints within the normalized metaspace comprises;

defining waypoints longitudinally centered between each shelving segment in the first shelving structure represented in the normalized metaspace;

calculating an angular orientation normal to a longitudinal face of the first shelving structure, relative to the coordinate system, in the normalized metaspace; and

writing the angular orientation to each waypoint in the first subset of waypoints.

19. The method of claim 16, further comprising:

at the robotic system, during the imaging routine;

detecting a matrix barcode in a field of view of a second optical sensor in the robotic system;

calculating a temporary waypoint based on a position and an orientation of the matrix barcode in the field of view of the second optical sensor, the temporary waypoint defining a first location and a first orientation that aligns a field of view of the optical sensor to a temporary shelving structure coupled to the matrix barcode;

recording a second image through the optical sensor while occupying the temporary waypoint;

determining an identity of the temporary shelving structure based on the matrix barcode;

based on the identify of the temporary shelving structure, retrieving a first list of products assigned to the temporary shelving structure by a second planogram associated with the temporary shelving structure;

retrieving a first set of template images from a database of template images, each template image in the first set of template images comprising visual features of a product specified in the first list of products;

confirming presence of a unit of a second product, in the first list of products, on the temporary shelving structure in response to correlation between features in the second image and features in a first template image, in the first set of template images, representing the second product;

determining that a unit of the second product is improperly stocked on the temporary shelving structure in response to deviation between features in the second image and features in the second template image; and

in response to determining that the unit of the second product is improperly stocked on the temporary shelving structure, generating a second restocking prompt for the second product on the temporary shelving structure.

20. The method of claim 19, further comprising:

detecting units of products on shelving structures in the store based on images collected by the robotic system during the imaging routine;

generating a global restocking list based on deviations between units of products detected on shelving structures in the store and the planogram of the store;

serving the global restocking list to an associate of the store;

generating a temporary restocking list based on deviations between units of products detected on the temporary shelving structure and the planogram associated with the temporary shelving structure;

serving the temporary restocking list to an affiliate of the temporary shelving structure outside of the store.