Automated lane and route network discovery for robotic actors

• US 9,945,677 B1
• Filed: 07/23/2015
• Issued: 04/17/2018
• Est. Priority Date: 07/23/2015
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: X Development LLC (Alphabet Inc.)
• Inventors: Watts, Kevin William
• Primary Examiner(s): Black, Thomas G
• Assistant Examiner(s): Smith-Stewart, Demetra R
• Application Number:
  US14/807,797
• Time in Patent Office: 999 Days
• Field of Search: None
• CPC Class Codes: B25J 9/1664 characterised by motion, path, trajectory planning
• CPC Class Codes: G01C 21/206 specially adapted for indoor navigation
• CPC Class Codes: G01C 21/3492 employing speed data or traffic data, e.g. real-time or historical traffic control systems for road vehicles involving transmission of navigation instructions to the vehicle G08G1/0968
• CPC Class Codes: G05B 19/4189 characterised by the transport system
• CPC Class Codes: G05D 1/0276 using signals provided by a source external to the vehicle involving a plurality of vehicles G05D1/0287; automatically controlling vehicle speed responsive to externally generated signals B60K31/0058
• CPC Class Codes: G05D 1/0289 with means for avoiding collisions between vehicles vehicle fittings for automatically controlling speed including means for detecting potential obstacles B60K31/0008; avoiding obstacles by action on the steering system B62D; radar, sonar, lidar systems designed for anti-collision purposes G01S13/93, G01S15/93, G01S17/93
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem
• CPC Class Codes: G06Q 10/08 Logistics, e.g. warehousing, loading or distribution; Inventory or stock management
• CPC Class Codes: Y02P 90/02 Total factory control, e.g. smart factories, flexible manufacturing systems [FMS] or integrated manufacturing systems [IMS]
• CPC Class Codes: Y10S 901/01 Mobile robot

Abstract

Systems and methods are provided for automated route discovery. A computing device can receive location data for designated actor(s) of a plurality of actors operating within an environment. The plurality of actors can also include a robotic device. The computing device can determine a route network of paths taken by the designated actor(s) within the environment, where the route network includes information about frequencies of paths taken by the designated actor(s) based on the location data. The computing device can receive a starting location and a destination location for the robotic device. The computing device can select a selected path from the starting location to the destination location based on the route network taken by the designated actor(s). The computing device can provide an instruction to the robotic device to use the selected path to travel from the starting location to the destination location.

Claims

1. A method, comprising:

receiving, at a computing device, location data for one or more designated actors of a plurality of actors operating within an environment, wherein the plurality of actors further comprise a robotic device;

determining, by the computing device, a route network of paths taken by the one or more designated actors within the environment, wherein the route network of paths comprises information about frequencies of paths taken by the one or more designated actors based on the location data for the one or more designated actors;

receiving, at the computing device, a starting location and a destination location for the robotic device;

selecting, by the computing device, a selected path from the starting location to the destination location based on the route network of paths taken by the one or more designated actors; and

providing, from the computing device, an instruction to the robotic device to use the selected path to travel from the starting location to the destination location.

2. The method of claim 1, wherein selecting the selected path from the starting location to the destination location based on the route network of paths taken by the one or more designated actors comprises selecting at least a portion of the selected path that follows at least one path in the route network of paths.

3. The method of claim 2, wherein selecting the at least the portion of the selected path that follows at least one path comprises selecting the at least the portion of the selected path that follows the at least one path based on a role of the robotic device.

4. The method of claim 2, wherein selecting the at least the portion of the selected path that follows at least one path comprises selecting the at least the portion of the selected path that follows the at least one path based on a time of day.

5. The method of claim 2, wherein selecting the at least the portion of the selected path that follows at least one path comprises selecting the at least the portion of the selected path that follows the at least one path based on a type of a designated actor, wherein the type of the designated actor is selected from a robotic-actor type, a human-actor type, and a human-controlled-actor type.

6. The method of claim 1, wherein selecting the path from the starting location to the destination location based on the route network of paths taken by the one or more designated actors comprises selecting at least a portion of the selected path that avoids at least one path in the route network of paths.

7. The method of claim 6, selecting the at least the portion of the selected path that avoids at least one path comprises selecting the at least the portion of the selected path that avoids the at least one path based on a role of the robotic device.

8. The method of claim 6, selecting the at least the portion of the selected path that avoids the at least one path comprises selecting the at least the portion of the selected path that avoids the at least one path based on a time of day.

9. The method of claim 6, selecting at least a portion of the selected path that avoids the at least one path comprises selecting the at least the portion of the selected path that avoids the at least one path based on a type of a designated actor, wherein the type of the designated actor is selected from a robotic-actor type, a human-actor type, and a human-controlled-actor type.

10. The method of claim 1, further comprising:

receiving additional location data for the one or more designated actors while they continue to operate within the environment; and

updating the route network of paths based on the additional location data.

11. A computing device, comprising:

one or more processors; and

data storage including at least computer-executable instructions stored thereon that, when executed by the one or more processors, cause the computing device to perform functions comprising;

receiving location data for one or more designated actors of a plurality of actors operating within an environment, wherein the plurality of actors further comprise a robotic device;

determining a route network of paths taken by the one or more designated actors within the environment based on the location data for the one or more designated actors, wherein the route network of paths comprises information about frequencies of paths taken by the one or more designated actors based on the location data for the one or more designated actors;

receiving a starting location and a destination location for the robotic device;

selecting a selected path from the starting location to the destination location based on the route network of paths taken by the one or more designated actors; and

providing an instruction to the robotic device to use the selected path to travel from the starting location to the destination location.

12. The computing device of claim 11, wherein selecting the selected path from the starting location to the destination location based on the route network of paths taken by the one or more designated actors comprises selecting at least a portion of the selected path that follows at least one path in the route network of paths.

13. The computing device of claim 12, wherein selecting the at least the portion of the selected path that follows at least one path comprises selecting the at least the portion of the selected path that follows the at least one path based on a role of the robotic device.

14. The computing device of claim 12, wherein selecting the at least the portion of the selected path that follows at least one path comprises selecting the at least the portion of the selected path that follows the at least one path based on a time of day.

15. The computing device of claim 12, wherein selecting the at least the portion of the selected path that follows at least one path comprises selecting the at least the portion of the selected path that follows the at least one path based on a type of a designated actor, wherein the type of the designated actor is selected from a robotic-actor type, a human-actor type, and a human-controlled-actor type.

16. The computing device of claim 11, wherein selecting the path from the starting location to the destination location based on the route network of paths taken by the one or more designated actors comprises selecting at least a portion of the selected path that avoids at least one path in the route network of paths.

17. The computing device of claim 11, wherein the environment comprises a warehouse, and wherein the computing device is configured to be permanently located within the warehouse.

18. The computing device of claim 11, wherein the computing device is configured to be a component of the robotic device.

19. The computing device of claim 11, wherein the computing device is configured to be at least part of a mobile device associated with an actor of the plurality of actors.

20. A non-transitory computer readable medium having stored thereon instructions, that when executed by one or more processors of a computing device, cause the computing device to perform functions comprising:

receiving location data for one or more designated actors of a plurality of actors operating within an environment, wherein the plurality of actors further comprise a robotic device;

determining a route network of paths taken by the one or more designated actors within the environment, wherein the route network of paths comprises information about frequencies of paths taken by the one or more designated actors based on the location data for the one or more designated actors;

receiving a starting location and a destination location for the robotic device;

selecting a selected path from the starting location to the destination location based on the route network of paths taken by the one or more designated actors; and

providing an instruction to the robotic device to use the selected path to travel from the starting location to the destination location.