Computer system and method for automated mapping by robots

• US 9,939,814 B1
• Filed: 05/01/2017
• Issued: 04/10/2018
• Est. Priority Date: 05/01/2017
• Status: Expired due to Fees

• Current Assignee: Savioke, Inc.
• Original Assignee: Savioke, Inc.
• Inventors: Bauer, Robert S., Minier, Alain, Wirth, Stephan, Chiesa, Lucas, Fritz, Christian, Canoso, Adrian
• Primary Examiner(s): Zanelli, Michael J
• Application Number:
  US15/584,012
• Time in Patent Office: 344 Days
• CPC Class Codes: G01C 21/206 specially adapted for indoor navigation
• CPC Class Codes: G01C 21/3848 Data obtained from both position sensors and additional sensors
• CPC Class Codes: G05D 1/0088 characterized by the autonomous decision making process, e.g. artificial intelligence, predefined behaviours using knowledge based models G06N5/00
• CPC Class Codes: G05D 1/0246 using a video camera in combination with image processing means
• CPC Class Codes: G05D 1/0274 using mapping information stored in a memory device navigation using map-matching G01C21/30
• CPC Class Codes: G05D 1/0285 using signals transmitted via a public communication network, e.g. GSM network
• CPC Class Codes: G09B 29/00 Maps; Plans; Charts; Diagrams, e.g. route diagram star maps G09B27/04; devices for holding or supporting maps A47B97/02; for computing purposes G06G1/14, G09B1/16; display boards G09F

Abstract

A method for autonomous map generation by a robot comprising: instructing the robot to traverse a route within an environment in which the robot is deployed; while following the route, causing the robot to collect sensor data to identify features in the environment and to generate an initial map of areas in environment that have been traversed; upon completion of the route, autonomously generating a map of valid areas of the environment by moving throughout the environment while collecting sensor data; while autonomously generating the map, determining that a particular area is potentially invalid by detecting features that are previously unknown to the robot; generating and providing an electronic message to an operator of the robot comprising sensor data of the particular area and a prompt requesting information indicating whether the particular area is valid or invalid; upon receiving a response from the operator, continuing autonomously generating the map according to the response wherein if the particular area is valid, collecting sensor data from the particular area and, if the particular area is invalid, proceeding to an unmapped, valid area of the environment; determining that there are no remaining unmapped, valid areas of the environment, ending autonomously generating the map.

Claims

1. A method for a robot to autonomously generate a digitally stored map of an environment, the method comprising:

receiving, via an input signal to a stored program executing in the robot, an instruction to physically traverse a route within the environment, the route comprising a path through the environment, and in response to the input signal, initiating physical traversal of the robot of the route;

while traversing the route, collecting digital data from one or more sensors of the robot and digitally transforming the collected digital data to result in identifying one or more features of the environment and to generate a digitally stored initial map representing the environment that has been traversed;

in response to detecting completion of traversal of the route, initiating traversal of the environment using other than the route, and;

concurrently generating and digitally storing a digital map of valid areas of the environment;

while generating the digital map, determining that a particular area is potentially invalid based on detecting features of the environment that are not represented in stored environment data, and in response, generating and transmitting an electronic message comprising collected sensor data for the particular area and a prompt requesting information indicating whether the particular area is valid;

in response to input indicating that the particular area is valid, traversing the particular area and continuing generating the digital map, and in response to input indicating that the particular area is invalid, avoiding traversing the particular area and moving to an unmapped valid area of the environment;

repeating the preceding steps relating to generating the digital map until all valid areas of the environment have been traversed.

2. The method of claim 1, further comprising, in response to detecting completion of traversal of the route, determining that the sensor data collecting during the route is insufficient to begin autonomously generating the map and requesting a second route comprising a second path through the environment.

3. The method of claim 1, wherein the route comprises traveling between separated areas of the environment using a transportation mechanism and at least one separated area of the environment is an invalid area.

4. The method of claim 1, further comprising identifying an elevator of a plurality of elevators using sensor data, and executing a machine vision algorithm using a computer in the robot to determine that the elevator is associated with a particular elevator number.

5. The method of claim 1, wherein autonomously generating the map comprises moving between two or more separated areas of the environment.

6. The method of claim 1, wherein autonomously generating the map comprises the robot programmatically communicating with a facilities access computer to utilize a transportation mechanism or to open an automatic door.

7. The method of claim 1, wherein autonomously generating the map comprises automatically labelling rooms and corridors in the digital map.

8. The method of claim 1, wherein the route is a demonstration route comprising a pre-defined path through the environment.

9. The method of claim 1, wherein the route comprises one or more hints indicating at least one or more of:

a starting location, a direction of travel, a distance of travel, an area to avoid, an area to traverse, an environment feature to follow, and a turn direction.

10. The method of claim 1 wherein the digital map comprises a plurality of pixels that are associated with the valid areas, wherein each pixel of the digital map is associated with a cost value representing a relative cost of the robot navigating one of the valid areas that is associated with the pixel.

11. The method of claim 10 wherein a first pixel corresponding to an impassable location in the environment has a higher cost value than a second pixel corresponding to a passable location in the environment.

12. The method of claim 1 wherein the digital map comprises graph data indicating a plurality of nodes and a plurality of edges, wherein each node of the plurality of nodes represents a valid area, and each edge of the plurality of edges represents an ability to navigate between two valid areas.

13. A robot programmed to execute a method to autonomously generate a digitally stored map of an environment, the robot comprising:

one or more computers;

one or more digital sensors that are coupled to the one or more computers and operable under program control of the one or more computers to collect signals based upon sensing the environment of the robot;

a non-transitory computer-readable storage medium coupled to the one or more computers and storing instructions which when executed by the one or more computers cause performing;

receiving, via an input signal to a stored program executing in the robot, an instruction to physically traverse a route within the environment, the route comprising a path through the environment, and in response to the input signal, initiating physical traversal of the robot of the route;

while traversing the route, collecting digital data from one or more sensors of the robot and digitally transforming the collected digital data to result in identifying one or more features of the environment and to generate a digitally stored initial map representing the environment that has been traversed;

in response to detecting completion of traversal of the route, initiating traversal of the environment using other than the route, and;

concurrently generating and digitally storing a digital map of valid areas of the environment;

while generating the digital map, determining that a particular area is potentially invalid based on detecting features of the environment that are not represented in stored environment data of the robot, and in response, generating and transmitting an electronic message comprising collected sensor data for the particular area and a prompt requesting information indicating whether the particular area is valid;

in response to input indicating that the particular area is valid, traversing the particular area and continuing generating the digital map, and in response to input indicating that the particular area is invalid, avoiding traversing the particular area and moving to an unmapped valid area of the environment;

repeating the preceding steps relating to generating the digital map until all valid areas of the environment have been traversed.

14. The robot of claim 13, further comprising instructions which when executed by the one or more computers cause, in response to detecting completion of traversal of the route, determining that the sensor data collecting during the route is insufficient to begin autonomously generating the map and requesting a second route comprising a second path through the environment.

15. The robot of claim 13, wherein the route comprises traveling between separated areas of the environment using a transportation mechanism and at least one separated area of the environment is an invalid area.

16. The robot of claim 13, further comprising instructions which when executed by the one or more computers cause identifying an elevator of a plurality of elevators using sensor data, and executing a machine vision algorithm using a computer in the robot to determine that the elevator is associated with a particular elevator number.

17. The robot of claim 13, wherein autonomously generating the map comprises moving between two or more separated areas of the environment.

18. The robot of claim 13, wherein autonomously generating the map comprises the robot programmatically communicating with a facilities access computer to utilize a transportation mechanism or to open an automatic door.

19. The robot of claim 13, wherein autonomously generating the map comprises automatically labelling rooms and corridors in the digital map.

20. The robot of claim 13, wherein the route is a demonstration route comprising a pre-defined path through the environment.

21. The robot of claim 13, wherein the route comprises one or more hints indicating at least one or more of:

a starting location, a direction of travel, a distance of travel, an area to avoid, an area to traverse, an environment feature to follow, and a turn direction.

22. The robot of claim 13 wherein the digital map comprises a plurality of pixels that are associated with the valid areas, wherein each pixel of the digital map is associated with a cost value representing a relative cost of the robot navigating one of the valid areas that is associated with the pixel.

23. The robot of claim 22 wherein a first pixel corresponding to an impassable location in the environment has a higher cost value than a second pixel corresponding to a passable location in the environment.

24. The robot of claim 13 wherein the digital map comprises graph data indicating a plurality of nodes and a plurality of edges, wherein each node of the plurality of nodes represents a valid area, and each edge of the plurality of edges represents an ability to navigate between two valid areas.