Navigation using planned robot travel paths

• US 9,864,377 B2
• Filed: 04/01/2016
• Issued: 01/09/2018
• Est. Priority Date: 04/01/2016
• Status: Active Grant

• Current Assignee: Locus Robotics Corporation
• Original Assignee: Locus Robotics Corporation
• Inventors: Welty, Bruce, Powers, Bradley, Tappan, Eric
• Primary Examiner(s): YEH, EUENG NAN
• Application Number:
  US15/088,474
• Publication Number:
  US 20170285648A1
• Time in Patent Office: 648 Days
• CPC Class Codes: B25J 11/008 Manipulators for service tasks
• CPC Class Codes: B25J 5/007 mounted on wheels
• CPC Class Codes: G05D 1/0236 in combination with a laser lasers per se H01S
• CPC Class Codes: G05D 1/0246 using a video camera in combination with image processing means
• CPC Class Codes: G05D 1/0248 in combination with a laser lasers per se H01S
• CPC Class Codes: G05D 1/0274 using mapping information stored in a memory device navigation using map-matching G01C21/30
• CPC Class Codes: G06Q 10/087 Inventory or stock management, e.g. order filling, procurement or balancing against orders
• CPC Class Codes: G06V 20/10 Terrestrial scenes scenes under surveillance with static cameras G06V20/52; scenes perceived from the exterior of a vehicle G06V20/56; scenes perceived from the interior of a vehicle G06V20/59
• CPC Class Codes: Y10S 901/01 Mobile robot

Abstract

A method for generating a navigation map of an environment in which a plurality of robots will navigate, includes obtaining an image of the environment defined by a plurality of pixels, each having a cost value. The environment includes an image of a fixed object having a set of pixels corresponding to its location and having a first defined cost value. The method includes obtaining a planned path image for the robots, which include a first set of pixels corresponding to the location of each robot in the environment and a second set of pixels adjacent to the first set of pixels and extending along a planned path of travel toward a destination. The first set of pixels of each robot having the first defined cost value and the second set of pixels having a second defined cost value. The second defined cost value is less than the first defined cost value.

Claims

1. A method for generating a navigation map of an environment in which a plurality of robots will navigate, the method comprising:

Obtaining an image of the environment, the image defined by a plurality of pixels, each pixel having a cost value associated with it;

wherein the image of the environment includes an image of at least one fixed object comprising a set of pixels corresponding to the location of the at least one fixed object in the environment, the set of pixels corresponding to the location of the at least one fixed object having a first defined cost value; and

Obtaining a planned path image for each of the plurality of robots in the environment, the planned path image including for each robot a first set of pixels corresponding to the location of each robot in the environment and a second set of pixels adjacent to the first set of pixels and extending along a planned path of travel of each robot toward a destination;

the pixels in the first set of pixels of each robot having the first defined cost value and the second set of pixels of each robot comprising pixels having cost values which are less than the first defined cost value;

wherein the image of the environment including the image of at least one fixed object is stored locally with each of the plurality of robots;

wherein each of the plurality of robots produces its own planned path and communicates its own planned path to the other of the plurality of robots;

wherein each robot combines the image of the environment including the image of at least one fixed object with images representing the planned paths received from other of the plurality of robots to form a navigation map; and

wherein each robot uses the navigation map to plan a path from its current location to its destination.

2. The method of claim 1, wherein each of the plurality of robots produces its own updated planned path at regular time intervals as each robot traverses its path to its destination and communicates its own updated planned path to the other of the plurality of robots at such regular intervals;

and wherein each robot uses the updated planned path of the other of the plurality of robots to produce an updated navigation map and updates its planned path to its destination using the updated navigation map.

3. The method of claim 1 wherein the second set of pixels of each robot comprises pixels having plurality of cost values less than the first cost value, and wherein the cost values of the pixels decrease proportionally in value as they extend from adjacent to the first set of pixels out along the planned path of travel of each robot toward a destination.

4. The method of claim 3 wherein the second set of pixels of each robot is formed by producing a plurality of regions along the planned path of travel of each robot toward a destination and wherein each region successively comprises pixels having cost values less than the preceding region.

5. The method of claim 4 wherein the plurality of regions are circular in shape and the regions have a radius corresponding to the size of at least one of the robots.

6. The method of claim 1 wherein the environment is a warehouse.

7. A method for navigating a robot in an environment from a current location to a destination, the environment including at least one fixed object and at least one other robot, the method comprising:

Obtaining an image of the environment, the image defined by a plurality of pixels, each pixel having a cost value associated with it;

wherein the image of the environment includes an image of the at least one fixed object comprising a set of pixels corresponding to the location of the at least one fixed object in the environment, the set of pixels corresponding to the location of the at least one fixed object having a first defined cost value;

Obtaining an image of the at least one other robot in the environment, the image of the at least one other robot including a first set of pixels corresponding to the location of the at least one other robot in the environment and a second set of pixels adjacent to the first set of pixels and extending along a planned path of travel of the at least one other robot toward a destination;

the pixels in the first set of pixels of the at least one other robot having the first defined cost value and the second set of pixels of the at least one other robot comprising pixels having cost values which are less than the first defined cost value; and

Planning a path from the current location of the robot to the destination of the robot based on the image of the at least one fixed object and the image of the at least one other robot.

8. The method of claim 7, wherein the image of the environment including the image of at least one fixed object is stored locally within the robot.

9. The method of claim 8, wherein the at least one other robot produces its own planned path from a current location to a destination and communicates its own planned path to the robot.

10. The method of claim 9, wherein the robot combines the image of the environment including the image of at least one fixed object with an image of the planned path received from the at least one other robot to form a navigation map.

11. The method of claim 10, wherein the robot uses the navigation map to plan a path from its current location to its destination.

12. The method of claim 11, wherein the at least one other robot produces its own updated planned path at regular time intervals as it traverses its path to its destination and communicates its own updated planned path to the robot at such regular intervals;

and wherein the robot uses the updated planned path of the at least one other robot to produce an updated navigation map and updates its planned path to its destination using the updated navigation map.

13. The method of claim 7, wherein the second set of pixels of the at least one other robot comprises pixels having plurality of cost values less than the first cost value, and wherein the cost values of the pixels decrease proportionally in value as they extend from adjacent to the first set of pixels out along the planned path of travel of the at least one other robot toward its destination.

14. The method of claim 13, wherein the second set of pixels of the at least one other robot is formed by producing a plurality of regions along the planned path of travel of the at least one other robot toward its destination and wherein each region successively comprises pixels having cost values less than the preceding region.

15. The method of claim 14, wherein the plurality of regions are circular in shape and the plurality of regions have a radius corresponding to the size of the robot or the at least one other robot.

16. The method of claim 7, wherein the environment is a warehouse.

17. A robot configured to navigate an environment, the environment including at least one fixed object and a plurality of other robots, the robot comprising:

A mobile base for propelling the robot throughout the environment;

A communication device enabling communication between the robot and the plurality of other robots; and

A processor, in communication with the communication device, configured to;

Obtain an image of the environment, the image defined by a plurality of pixels, each pixel having a cost value associated with it;

wherein the image of the environment includes an image of the at least one fixed object comprising a set of pixels corresponding to the location of the at least one fixed object in the environment, the set of pixels corresponding to the location of the at least one fixed object having a first defined cost value;

Obtaining an image of the plurality of other robots in the environment, the image including for each robot a first set of pixels corresponding to the location of each robot in the environment and a second set of pixels adjacent to the first set of pixels and extending along a planned path of travel of each other robot toward a destination;

the pixels in the first set of pixels of each other robot having the first defined cost value and the second set of pixels of each other robot comprising pixels having a cost values which are less than the first defined cost value, and

Planning a path from the current location of the robot to the destination of the robot based on the image of the at least one fixed object and the images of the plurality of other robots.

18. The robot of claim 17, wherein the image of the environment including the image of at least one fixed object is stored locally with each of the plurality of robots.

19. The robot of claim 18, wherein each of the plurality of other robots is configured to produce its own planned path and communicate its own planned path using its communications device to the robot and to the plurality of other robots.

20. The robot of claim 19, wherein the processor is configured to combine the image of the environment including the image of at least one fixed object with images of the planned paths received from the other of the plurality of robots to form a navigation map.

21. The robot of claim 20, wherein the processor is configured to use the navigation map to plan a path from its current location to its destination.

22. The robot of claim 21, wherein the processor is configured to receive from each of the plurality of other robots an updated planned path at regular time intervals as each other robot traverses its path to its destination;

and wherein the processor is configured to use the updated planned path of the other of the plurality of robots to produce an updated navigation map and update its planned path to its destination using the updated navigation map.

23. The robot of claim 17 wherein the second set of pixels of each of the plurality of other robots comprises pixels having a plurality of cost values less than the first cost value, and wherein the cost values of the pixels decrease proportionally in value as they extend from adjacent to the first set of pixels out along the planned path of travel of each robot toward a destination.

24. The robot of claim 23 wherein the second set of pixels of each of the plurality of other robots is formed by producing a plurality of regions along the planned path of travel of each robot toward a destination and wherein each region successively comprises pixels having cost values less than the preceding region.

25. The robot of claim 24 wherein the regions are circular in shape and the regions have a radius corresponding to the size of at least one of the plurality of other robots.

26. The robot of claim 17 wherein the environment is a warehouse.