Method and system for automatically preventing deadlock in multi-robot systems

• US 9,144,904 B2
• Filed: 05/02/2012
• Issued: 09/29/2015
• Est. Priority Date: 05/21/2008
• Status: Active Grant

• Current Assignee: Fanuc Robotics America Corp (Fanuc Corporation)
• Original Assignee: Fanuc Robotics America Corp (Fanuc Corporation)
• Inventors: McGee, H. Dean, Chang, Tien L., Swanson, Peter, Tao, Jianming, Xiao, Di, Wong, Ho Cheung, Cheng, Sai-Kai, Tsai, Jason
• Primary Examiner(s): Nguyen, John Q
• Assistant Examiner(s): Fei, Jordan S
• Application Number:
  US13/462,234
• Publication Number:
  US 20120215351A1
• Time in Patent Office: 1,245 Days
• Field of Search: 700248-255
• US Class Current: 1/1
• CPC Class Codes: B25J 9/1666 Avoiding collision or forbidden zones
• CPC Class Codes: B25J 9/1676 Avoiding collision or forbidden zones
• CPC Class Codes: G05B 2219/39135 For multiple manipulators operating at same time, avoid collision
• CPC Class Codes: G05B 2219/40442 Voxel map, 3-D grid map
• CPC Class Codes: G05B 2219/40477 Plan path independent from obstacles, then correction for obstacles
• CPC Class Codes: G05B 2219/40492 Model manipulator by spheres for collision avoidance

Abstract

A system and method for controlling avoiding collisions and deadlocks in a workcell containing multiple robots automatically determines the potential deadlock conditions and identifies a way to avoid these conditions. Deadlock conditions are eliminated by determining the deadlock-free motion statements prior to execution of the motions that have potential deadlock conditions. This determination of deadlock-free motion statements can be done offline, outside normal execution, or it can be done during normal production execution. If there is sufficient CPU processing time available, the determination during normal production execution provides the most flexibility to respond to dynamic conditions such as changes in I/O timing or the timing of external events or sequences. For minimal CPU impact the determination is done offline where many permutations of programming sequences can be analyzed and an optimized sequence of execution may be found.

Claims

1. A method for preventing deadlock of a pair of robots which have a common workspace, each of the robots being controlled by an associated program wherein when the programs are executed concurrently to generate normal program motion each of the robots occupies at least a portion of the common workspace during a portion of execution of the associated program, said method comprising the steps of:

prior to the normal program motion, determining portions of the common workspace occupied by the robots by initial operation in a lockdown mode or an offline run according to the programs including representing the occupied portions of the common workspace with voxel models;

determining at least one interference region wherein the portions of the common workspace occupied by the robots overlap by comparing the voxel models to determine the at least one interference region;

analyzing the at least one interference region and determining where at least one deadlock condition of the two robots can occur; and

avoiding the at least one deadlock condition during execution of the programs in the normal program motion by automatically determining a mechanism to avoid the at least one deadlock condition and associating the mechanism with at least one of the programs before execution of the programs in the normal program motion.

2. The method according to claim 1 wherein the mechanism is at least one deadlock-free motion statement.

3. The method according to claim 2 wherein the at least one deadlock-free motion statement is associated by adding to at least one of the programs.

4. The method according to claim 2 wherein the at least one deadlock-free motion statement is associated by modifying at least one instruction in at least one of the programs.

5. The method according to claim 2 wherein the at least one deadlock-free motion statement is associated by re-sequencing instructions in at least one of the programs.

6. The method according to claim 2 wherein the at least one deadlock-free motion statement is associated by adding a wait command to at least one of the programs.

7. A non-transitory computer readable media containing instructions executable by a computer to perform a method for preventing deadlock of a pair of robots which have a common workspace, each of the robots being controlled by an associated program wherein when the programs are executed concurrently to generate normal program motion each of the robots occupies at least a portion of the common workspace during a portion of execution of the associated program, the method comprising:

prior to the normal program motion, the instructions determining portions of the common workspace occupied by the robots by initial operation in a lockdown mode or an offline run according to the programs wherein the instructions represent the occupied portions of the common workspace with voxel models;

the instructions determining at least one interference region wherein the portions of the common workspace overlap by comparing the voxel models to determine the at least one interference region;

the instructions analyzing the at least one interference region and determining where at least one deadlock condition of the two robots can occur; and

the instructions avoiding the at least one deadlock condition during execution of the programs in the normal program motion by automatically determining a mechanism to avoid the at least one deadlock condition and associating the mechanism with at least one of the programs before execution of the programs in the normal program motion.

8. The method according to claim 7 wherein the mechanism includes at least one deadlock-free motion statement.

9. The method according to claim 8 wherein the at least one deadlock-free motion statement is associated by adding to at least one of the programs.

10. The method according to claim 8 wherein the at least one deadlock-free motion statement is associated by modifying at least one instruction in at least one of the programs.

11. The method according to claim 8 wherein the at least one deadlock-free motion statement is associated by re-sequencing instructions in at least one of the programs.

12. The method according to claim 8 wherein the at least one deadlock-free motion statement is associated by adding a wait command to at least one of the programs.

13. A method for preventing deadlock of a plurality of robots which have a common workspace, each of the robots being controlled by an associated program wherein when the programs are executed concurrently to generate normal program motion each of the robots occupies at least a portion of the common workspace during a portion of execution of the associated program, said method comprising the steps of:

prior to the normal program motion, determining portions of the common workspace occupied by the robots by initial operation in a lockdown mode or an offline run according to the programs including representing the occupied portions of the common workspace with voxel models;

determining at least one interference region wherein the portions of the common workspace overlap for at least two of the robots by comparing the voxel models to determine the at least one interference region;

analyzing the at least one interference region and determining where at least one deadlock condition of the at least two robots can occur; and

avoiding the at least one deadlock condition during execution of the programs in the normal program motion by automatically determining at least one deadlock-free motion statement and associating the statement with at least one of the programs before execution of the programs in the normal program motion.