Autonomous coordination of resources amongst robots

Patent metadata

Field	Value
Publication number	US-9513627-B1
Application number	US-201615137463-A
Country	US
Kind code	B1
Filing date	Apr 25, 2016
Priority date	Apr 25, 2016
Publication date	Dec 6, 2016
Grant date	Dec 6, 2016

Abstract

A synchronization primitive provides robots with locks, monitors, semaphores, or other mechanisms for reserving temporary access to a shared limited set of resources required by the robots in performing different tasks. Through non-conflicting establishment of the synchronization primitives across the set of resources, robots can prioritize the order with which assigned tasks are completed and minimize wait times for resources needed to complete each of the assigned tasks, thereby maximizing the number of tasks simultaneously executed by the robots and optimizing task completion. The synchronization primitives and resulting resource allocation can be implemented with a centralized coordinator or with peer-to-peer robotic messaging, whereby private keys and blockchains secure the precedence and establishment of synchronization primitives by different robots. Moreover, synchronization primitives can be established with queues to further optimize the immediate and future allocation of resources to different robots.

First claim

We claim:

1. A method comprising:
providing a plurality of robots and a plurality of resources, wherein the plurality of resources are shared amongst the plurality of robots in execution of a plurality of tasks;
assigning a task to a particular robot of the plurality of robots;
determining at least a first resource from the plurality of resources required by the particular robot for completion of said task;
determining a path from a current position of the particular robot to a destination associated with the task;
establishing by the particular robot, a first synchronization primitive on the first resource prior to the particular robot accessing the first resource, wherein said establishing provides the particular robot exclusive access to the first resource and prevents other robots from the plurality of robots from accessing the first resource while said first synchronization primitive of the particular robot is established, wherein establishing the synchronization primitive comprises associating a unique identifier of the particular robot to the first resource; and
accessing the first resource with the particular robot in execution of the task by the particular robot, wherein accessing the first resource comprises moving the particular robot from the current position to a first distance from a point of reference based on said path involving moving the particular robot in a first direction to reach the destination, and moving the particular robot from the current position to a second distance from the point of reference based on said path involving moving the particular robot in a second direction that is opposite to the first direction, wherein the particular robot determines the first and second distances based on visual sensors of the particular robot.

2. The method of claim 1 , wherein establishing the first synchronization primitive further comprises the particular robot wirelessly requesting access to the first resource and wirelessly receiving confirmation that the first resource is available.

3. The method of claim 2 , wherein said wirelessly requesting and wirelessly receiving confirmation is performed with peer-to-peer communications between the particular robot and other robots of the plurality of robots.

4. The method of claim 2 , wherein said wirelessly requesting and wirelessly receiving confirmation is performed between the particular robot and a coordinator, wherein the coordinator manages resource allocation across the plurality of robots, and the method further comprising receiving from the coordinator at the particular robot (i) synchronization primitive establishment confirmation providing the particular robot precedence over other robots of the plurality of robots to access the first resource or (ii) synchronization primitive establishment rejection providing a second robot from the plurality of robots precedence over the particular robot to access the first resource because of an earlier established synchronization primitive by the second robot.

5. The method of claim 1 further comprising releasing the synchronization primitive by operation of the particular robot after said accessing, wherein said releasing renders the first resource accessible by other robots of the plurality of robots, and wherein said releasing comprises disassociating the unique identifier of the particular robot from the first resource.

6. The method of claim 1 further comprising establishing a second synchronization primitive on a second resource of the plurality of resources further required by the particular robot for completion of said task, wherein establishing the second synchronization primitive provides the particular robot with simultaneous exclusive access to the first resource and the second resource, and wherein the first resource and the second resource comprise any two of a computing asset, an authorization privilege, and a physical asset.

7. The method of claim 1 further comprising queuing by the particular robot, a second synchronization primitive on a second resource of the plurality of resources, wherein said queuing comprises placing the unique identifier of the particular robot after a different unique identifier of a second robot in a queue of the second resource, establishing the second synchronization primitive on the second resource after the different unique identifier of the second robot is removed from said queue, and providing the particular robot exclusive access to the second resource an amount of time after said accessing the first resource.

8. The method of claim 1 , wherein the first resource comprises space, and wherein accessing the first resource comprises moving the particular robot into said space.

9. The method of claim 8 further comprising establishing by the particular robot, a plurality of synchronization primitives on a set of resources comprising a set of continuous spaces along said path.

10. The method of claim 8 further comprising establishing by the particular robot, a plurality of synchronization primitives on a set of resources comprising space surrounding the robot, wherein said set of resources provide the particular robot with space to adjust course without other robots deadlocking the particular robot movements.

11. The method of claim 1 , wherein establishing the synchronization primitive further comprises the particular robot (i) generating the unique identifier using a private key of the particular robot and (ii) writing said unique identifier to a blockchain associated with the first resource.

12. The method of claim 1 further comprising halting or reordering task execution of a second robot from the plurality of robots in response to said establishing the first synchronization primitive by the particular robot and the second robot requiring access to the first resource.

13. The method of claim 1 further comprising changing the particular robot movement direction, wherein said changing comprises (i) moving the particular robot from the first distance to the second distance and (ii) moving the robot in the opposite second direction while maintaining the second distance from a plurality of points of reference running parallel to the second direction of movement by the robot.

14. The method of claim 1 further comprising receiving at the particular robot, a plurality of synchronization primitives established by other robots from the plurality of robots, each synchronization primitive of the plurality of synchronization primitive identifying a different resource reserved by a robot other than the particular robot.

15. A method comprising:
providing a plurality of item retrieval robots and a plurality of resources, wherein the plurality of item retrieval robots access different sets of the plurality of resources in retrieving a plurality of items from a plurality of shelves within a distribution site;
computing an optimal allocation of the plurality of resources minimizing total retrieval time of the plurality of items by the plurality of item retrieval robots;
determining based on said optimal allocation, paths from current positions of the plurality of item retrieval robots to different shelves of the plurality of shelves;
moving a first set of the plurality of item retrieval robots to a first distance from a point of reference based on said paths involving moving the first set of item retrieval robots in a first direction;
moving a different second set of the plurality of item retrieval robots to a second distance from a point of reference based on said paths involving moving the second set of item retrieval robots in a second direction that is opposite to the first

Assignees

• Invia Robotics Inc
• Invia Robotics Llc

Inventors

• Elazary Lior
• Voorhies Randolph Charles
• Parks Ii Daniel Frank

Classifications

• G05B2219/39166

  Coordinate activity by sending pheromone messages between robots, no central control · CPC title

• G05B2219/39167

  Resources scheduling and balancing · CPC title

• G05B2219/39146

  Swarm, multiagent, distributed multitask fusion, cooperation multi robots · CPC title

• G05B19/41895 Primary

  using automatic guided vehicles [AGV] (control of position or course of AGV's G05D1/00) · CPC title

• G05B19/41865 Primary

  characterised by job scheduling, process planning, material flow · CPC title