Methods and systems for distributing tasks among robotic devices

• US 8,428,777 B1
• Filed: 08/01/2012
• Issued: 04/23/2013
• Est. Priority Date: 02/07/2012
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Poursohi, Arshan, Hickman, Ryan, Francis, Anthony, Kuffner, James
• Primary Examiner(s): Tran, Khoi
• Assistant Examiner(s): Nguyen, Bao Long T
• Application Number:
  US13/564,135
• Time in Patent Office: 265 Days
• Field of Search: None
• US Class Current: 700/248
• CPC Class Codes: G05B 19/41865 characterised by job scheduling, process planning, material flow
• CPC Class Codes: Y02P 90/02 Total factory control, e.g. smart factories, flexible manufacturing systems [FMS] or integrated manufacturing systems [IMS]

Abstract

Methods and systems for distributing tasks among robotic devices are described. A server may receive from a first device, information associated with an assigned task of the first device. The server may determine whether the assigned task can be executed more efficiently with assistance from additional devices, and may further determine available devices that can assist in executing the assigned task. The determined available devices may be ranked according to an amount of usage of the devices over time, and a second device may be selected from the available devices based on the ranking. A subtask of the assigned task may then be determined from a plurality of subtasks of the assigned task based on capabilities of the selected second device. An instruction may then be sent to the second device, instructing the second device to execute the determined subtask.

Claims

1. A method performed by a device, the method comprising:

receiving from a first device information associated with an assigned task of the first device, wherein the assigned task involves an interaction with an environment and comprises a plurality of subtasks;

determining whether the assigned task can be executed in less time with assistance from one or more additional devices;

determining one or more available devices that can assist in executing the assigned task by executing at least one of the plurality of subtasks, wherein the one or more available devices include a device that is idle and that is configured to execute at least one of the plurality of subtasks;

ranking devices from the one or more available devices based on an amount of usage over time of the one or more available devices;

selecting a second device from among the one or more available devices based on the ranking of the one or more available devices;

determining a first subtask from the plurality of subtasks for the second device to execute based on capabilities of the second device;

sending to the second device instructions to execute the determined first subtask;

storing the information associated with the assigned task of the first device;

determining a pattern of assigned tasks based on the stored information and previously stored information associated with previously assigned tasks of a pool of devices; and

determining a task prediction based on the pattern of assigned tasks, the task prediction estimating a future task and a future time at which the future task is to be executed.

2. The method of claim 1, wherein the amount of usage includes an amount of mechanical component usage, and wherein determining the first subtask from the plurality of subtasks for the second device to execute based on capabilities of the second device further comprises:

selecting a subtask from the plurality of subtasks for the second device to execute that has a degree of mechanical difficulty inversely proportional to the amount of mechanical component usage of the second device.

3. The method of claim 1, further comprising:

ranking devices from among the one or more available devices based on geographical proximities of the one or more available devices to the first device;

selecting the second device from among the one or more available devices based on the ranking of the geographical proximities.

4. The method of claim 1, wherein determining one or more available devices that can assist in executing the assigned task by executing at least one of the plurality of subtasks further comprises:

determining a status of mechanical actuators or processing components of devices in a pool of devices; and

selecting as the one or more available devices any device of the pool of devices that has one of the mechanical actuators or the processing components in an idle status.

5. The method of claim 1, wherein determining the one or more available devices that can assist in executing the assigned task by executing at least one of the plurality of subtasks further comprises:

determining respective levels of reserve power of devices in a pool of devices; and

selecting as the one or more available devices any device of the pool of devices that has a reserve power level above a predetermined threshold amount.

6. The method of claim 1, wherein determining the one or more available devices that can assist in executing the assigned task by executing at least one of the plurality of subtasks further comprises:

determining respective geographical locations of devices in a pool of devices; and

selecting as the one or more available devices any device of the pool of devices capable of relocating to a subtask location where at least one of the plurality of subtasks is to be executed.

7. The method of claim 1, wherein determining the one or more available devices that can assist in executing the assigned task by executing at least one of the plurality of subtasks further comprises:

determining respective processing capabilities of devices in a pool of devices; and

selecting as the one or more available devices any device of the pool of devices that is idle and is configured to execute at least one of the plurality of subtasks.

8. The method of claim 7, wherein determining the first subtask from the plurality of subtasks for the second device to execute based on capabilities of the second device further comprises:

selecting a subtask from the plurality of subtasks, wherein the selected subtask has a processing requirement met by the processing capabilities of the second device.

9. The method of claim 1, wherein determining the one or more available devices that can assist in executing the assigned task by executing at least one of the plurality of subtasks further comprises:

determining respective mechanical capabilities of devices in a pool of devices; and

selecting as the one or more available devices any device of the pool of devices that has a given mechanical capability needed to perform the first subtask.

10. The method of claim 9, wherein determining the first subtask from the plurality of subtasks for the second device to execute based on capabilities of the second device further comprises:

selecting a subtask from the plurality of subtasks that has a mechanical requirement met by the respective mechanical capability of the second device.

11. The method of claim 1, wherein determining the first subtask from the plurality of subtasks for the second device to execute based on capabilities of the second device further comprises:

determining one or more previous experiences of the second device, the one or more previous experiences indicating one or more subtasks the second device has previously executed; and

selecting a subtask from the plurality of subtasks for the second device to execute that is the same or similar as a given subtask that the second device has previously executed.

12. The method of claim 1, further comprising receiving from the second device one or more of information associated with whether the first subtask can be executed by the second device and information associated with whether the first subtask can be executed at all.

13. The method of claim 1, further comprising:

determining that the second device is unable to execute the first subtask when the second device has not executed the first subtask after a predetermined time;

querying a pool of devices for instructions informing how to execute the first subtask; and

providing to the second device instructions informing the second device how to execute the first subtask.

14. The method of claim 1, further comprising:

determining that the second device is unable to execute the first subtask when the second device has not executed the first subtask after a predetermined time;

providing a control interface to a human operator, the control interface configured to receive input from the human operator to control the second device; and

providing to the second device the input from the human operator instructing the second device to execute the first subtask.

15. The method of claim 1, further comprising:

determining mechanical and processing requirements of the future task;

selecting a third device from among the one or more available devices to execute the future task based on capabilities of the third device, wherein the capabilities of the third device meet the mechanical and computational requirements of the future task;

determining a future task location where the future task is to be executed;

sending instructions to the third device to move to the future task location prior to the future time.

16. The method of claim 1, wherein determining a first subtask from the plurality of subtasks for the second device to execute based on capabilities of the second device further comprises:

transmitting data indicating the capabilities of the second device to the first device;

causing the first device to determine the first subtask from the plurality of subtasks based on capabilities of the second device; and

receiving data indicating the first subtask from the plurality of subtasks for the second device to execute.

17. A computer readable memory having stored thereon instructions executable by a computing device to cause the computing device to execute functions comprising:

receiving from a first device information associated with an assigned task of the first device, wherein the assigned task involves an interaction with an environment and comprises a plurality of subtasks;

determining whether the assigned task can be executed in less time with assistance from one or more additional devices;

determining one or more available devices that can assist in executing the assigned task by executing at least one of the plurality of subtasks, wherein the one or more available devices include a device that is idle and that is configured to execute at least one of the plurality of subtasks;

ranking devices from the one or more available devices based on an amount of usage over time of the one or more available devices;

selecting a second device from among the one or more available devices based on the ranking of the one or more available devices;

determining a first subtask from the plurality of subtasks for the second device to execute based on capabilities of the second device; and

sending to the second device instructions to execute the determined first subtask;

storing the information associated with the assigned task of the first device;

determining a pattern of assigned tasks based on the stored information and previously stored information associated with previously assigned tasks of a pool of devices; and

determining a task prediction based on the pattern of assigned tasks, the task prediction estimating a future task and a future time at which the future task is to be executed.

18. The computer readable memory of claim 17, wherein the instructions are further executable by the computing device to cause the computing device to execute functions comprising:

determining that the second device is unable to execute the first subtask when the second device has not executed the first subtask after a predetermined time;

providing a control interface to a human operator, the control interface configured to receive input from the human operator to control the second device; and

providing to the second device the input from the human operator instructing the second device to execute the first subtask.

19. A device comprising:

a processor; and

memory including instructions stored therein executable by the processor to perform functions comprising;

receiving from a first device information associated with an assigned task of the first device, wherein the assigned task involves an interaction with an environment and comprises a plurality of subtasks;

determining whether the assigned task can be executed in less time with assistance from one or more additional devices;

determining one or more available devices that can assist in executing the assigned task by executing at least one of the plurality of subtasks, wherein the one or more available devices include a device that is idle and that is configured to execute at least one of the plurality of subtasks;

ranking devices from the one or more available devices based on an amount of usage over time of the one or more available devices;

selecting a second device from among the one or more available devices based on the ranking of the one or more available devices;

determining a first subtask from the plurality of subtasks for the second device to execute based on capabilities of the second device;

sending to the second device instructions to execute the determined first subtask;

storing the information associated with the assigned task of the first device;

determining a pattern of assigned tasks based on the stored information and previously stored information associated with previously assigned tasks of a pool of devices; and

determining a task prediction based on the pattern of assigned tasks, the task prediction estimating a future task and a future time at which the future task is to be executed.

20. The device of claim 19, further comprising instructions stored in the memory executable by the processor to perform functions comprising:

determining mechanical and computational requirements of the future task;

selecting a third device from among the one or more available devices to execute the future task based on capabilities of the third device, wherein the capabilities of the third device meet the mechanical and computational requirements of the future task;

determining a future task location where the future task is to be executed;

sending instructions to the third device to move to the future task location prior to the future time.

21. A system comprising:

a first device; and

a second device configured to;

receive from the first device information associated with an assigned task of the first device, wherein the assigned task involves an interaction with an environment and comprises a plurality of subtasks;

determine whether the assigned task can be executed in less time with assistance from one or more additional devices;

determine one or more available devices that can assist in executing the assigned task by executing at least one of the plurality of subtasks, wherein the one or more available devices include a device that is idle and that is configured to execute at least one of the plurality of subtasks;

rank devices from the one or more available devices based on an amount of usage over time of the one or more available devices;

select a third device from among the one or more available devices based on the ranking of the one or more available devices;

determine a first subtask from the plurality of subtasks for the third device to execute based on capabilities of the third device;

cause the first device to send to the third device instructions to execute the determined first subtask;

storing the information associated with the assigned task of the first device;

determining a pattern of assigned tasks based on the stored information and previously stored information associated with previously assigned tasks of a pool of devices; and

determining a task prediction based on the pattern of assigned tasks, the task prediction estimating a future task and a future time at which the future task is to be executed.

22. The system of claim 21, wherein the second device is further configured to:

determine a second subtask from the plurality of subtasks based on capabilities of the second device; and

execute the second subtask from the plurality of subtasks.