Method and apparatus for anti-collision and collision protection for multiple robot system

• US 5,150,452 A
• Filed: 07/28/1989
• Issued: 09/22/1992
• Est. Priority Date: 07/28/1989
• Status: Expired due to Fees

• Current Assignee: Rankin Corporation
• Original Assignee: Megamation Incorporated
• Inventors: Hoffman, Brian D., Pollack, Steven H.
• Primary Examiner(s): Herndon, Heather R.
• Application Number:
  US07/387,222
• Time in Patent Office: 1,152 Days
• Field of Search: 364/518, 364/521, 364/522, 364/513, 364/461, 364/462, 395/90, 395/135
• US Class Current: 700/255
• CPC Class Codes: B25J 9/1676 Avoiding collision or forbidden zones

Abstract

Collision detection in a multi-robot system. A "map" of the "world" is stored in memory. A collision map containing a desired robot move is created. The initial position of the desired robot is removed from the "world" map by combining the robot map and the "world" map in a logical exclusive-OR operation and thereafter combining the collision map and the "world" map in a logical exclusive-OR operation followed by combining the collision map and the "world" map in a logical "inclusive-OR" operation in a byte-by-byte manner. A collision is indicated by a difference in any bit position of the inclusive and exclusive-OR combinations. The lack of any difference indicates that the move may be made. Similar logic operations are performed to partially and ultimately totally deallocate an allocated path and for considering alternative moves or partial moves responsive to the presence of a "collision". The method is performed using a computer which may be no more sophisticated than a conventional personal computer (i.e. PC) in which calculations are capable of being performed within a millisecond, which operating speed favorably compares with the movement of a robot which requires of the order of one second.

Claims

1. A collision detection met robot system having at least two robots movable about a common surface of a predetermined size

(a) providing a world map and a plurality of robot maps each divided into an xy grid of uniform sized squares, each map being the same size as said common surface for receiving two-dimensional representations, of robots projected onto said common surface;

(b) associating each of said squares of each maps with a predetermined memory cell in an associated memory;

(c) installing the initial location of each robot in its associated map by setting each memory cell associated with a square in the associated robot map having at least a portion thereof occupied by said robot to a first binary state;

(d) installing the initial location of each robot in the world map by combining the binary bit of each robot map memory cell with the binary bit of the associated memory cell of the world map;

(e) removing the initial location of a predetermined robot from the world map by a logical combination of the memory cells of the robot map of said predetermined robot with the associated memory cells of the world map responsive to a move request for said predetermined robot;

(f) installing the swept area representing movement from the initial position to a desired final position of said predetermined robot upon a swept area robot map by setting all of the memory cells occupied by the swept area to said predetermined state;

combining the binary states of associated memory cells of said swept area robot map and said world map using a first type of logical OR operation;

(h) combining the binary states of associated memory cells of said swept area map and said world map using a second type of logical OR operation different from said first type of logical OR operation;

(i) indicating a collision if the binary states of any one of the associated memory cells of the logical combinations resulting from said first and second types of logical OR operations are unequal.

2. The method of claim 1 wherein said first type of logical OR operation is an exclusive-OR operation.

3. The method of claim 2 wherein said first type of logical OR operation is an inclusive-OR operation.

4. The method of claim 1 wherein said first type of logical OR operation is an inclusive-OR operation.

5. The method of claim 1 wherein steps (g) and (h) further comprise the step of sequentially combining groups of memory cells each having a predetermined number of memory cells and further comprising the step of installing the result of step (g) into the world map memory cells when the binary states of the combined groups resulting from steps (g) and (h) are equal.

6. The method of claim 1 wherein said first predetermined state is the binary "ONE" state.

7. The method of claim 1 further comprising the step of providing an allocation condition when all of the associated memory cells of the combined maps created in steps (g) and (h) are equal.

8. The method of claim 7 further including sequentially combining groups of memory cells each having a predetermined number of memory cells and further comprising the step of installing the result of step (g) into the world map memory cells when the binary states of the combined groups resulting from steps (g) and (h) are equal.

9. The method of claim 1 wherein the memory cells of each map are arranged in bytes each having a uniform number of memory cell "bits", each byte of each map being associated with a byte of every other map.

10. The method of claim 9 wherein steps (g) and (h) each further comprise the steps of:

extracting associated bytes of the robot and world maps from their memory cells;

combining the associated bits of the extracted bytes in a sequential fashion.

11. The method of claim 10 further comprising the step of installing the result of step (g) into the memory cells of the world map when the results of steps (g) and (h) are equal.

12. The method of claim 11 wherein step (i) further comprises the steps of:

(j) comparing associated bytes in fashion; and

(k) halting the comparison when the associated bytes being compared are unequal.

13. The method of claim 12 further comprising the step of removing the binary data of those bytes installed into the memory cells of the world map previous the occurrence of the inequality condition occurring at step (k).

14. The method of claim 1 further comprising the steps of:

(j) combining the binary states of the associated memory cells of the swept area robot map and the world map in a logical OR operation to erase the swept area from the world map;

(k) installing the binary states representing the present position of the robot whose swept area has been removed from the world map into the memory cells of a robot map;

(l) installing the robot map of the robot'"'"'s present position by combining the binary states of the associated memory cells of the last-mentioned robot map and the world map.

15. The method of claim 14 wherein step (j) employs a logical exclusive-OR operation.

16. The method of claim 14 wherein step (k) employs a logical OR operation.

17. The method of claim 1 wherein step (c) further comprises the step of:

installing two-dimensional representations of fixed objects in the work space into the world map by inserting said predetermined binary state in each memory cell associated with the squares containing any portion of the fixed objects.

18. The method of claim 1 further comprising the steps of:

(j) removing the original swept area from the world map memory cells by reversing the binary state of the world map memory cells representing the swept area;

(k) installing a swept area of a robot moving between its initial position and a safe position located between the initial position and the desired final position into the associated memory cells of a swept area map by inserting the predetermined binary state into those memory cells representing squares touched by the swept area;

(l) repeating steps (g), (h) and (i) employing the world map and the swept area map created during step (k).

19. The method of claim 18 further comprising the steps of:

repeating steps (j), (k) and (1) employing a swept area having a second safe position different from said first safe position and said desired final position responsive to a collision condition.

20. The method of claim 18 further comprising the steps of:

repeating steps (j), (k) and (l) employing a swept area having a second incremental distance into said known safe region different from said first safe position and said desired final position responsive to a collision condition.

21. The method of claim 18 further comprising the steps of:

preventing movement of the robot requesting the allocation for a predetermined delay responsive to a collision indication.

22. The method of claim 1 further comprising the steps of:

(j) removing the original swept area from the world map memory cells;

(k) installing a swept area of a robot moving between its initial position and a incremental position located a small predetermined distance away from said initial position into a known free space region of the common surface by inserting said predetermined binary states into those memory cells representing square a touched by said swept area; and

(l) repeating steps (g), (h) and (i) employing the world map and the swept area map created during step (k).

23. The method of claim 22 further comprising the step of:

preventing movement of the robot requesting the allocation for a predetermined delay responsive to a collision indication.

24. The method of claim 1 further comprising the step of:

preventing movement of the robot requesting the allocation for a predetermined delay responsive to a collision indication.

25. The method of claim 24 wherein said delay period is about one (1) second.

26. The method of claim 1 wherein each robot is coupled to a controller by an umbilical cord, said method steps (c) through (h) further comprising the steps of:

installing the two-dimensional representation of the umbilical cord into the robot maps and the world map and installing the two dimensional representation of the swept area of the umbilical cord into the swept area robot map.

27. The method of claim 1 wherein each robot is coupled to a controller by an umbilical cord, said method steps (c) through (f) further comprising the steps of:

installing the two-dimensional representation of the desired final position of the umbilical cord into the swept area robot map.

28. A method for detecting collisions in a robot system in which at least two robots are movable to any position along a common surface comprising the steps of:

(a) providing in a memory storing device a world map and a plurality of robot maps each being divided into an xy grid of uniform sized squares, each map being the same size as said common surface for receiving two-dimensional representations of robots and other objects projected onto said common surface, the memory storage device having a plurality of memory locations, each memory location being assigned to store the condition of an associated square of said world map and said robot maps;

(b) installing a two-dimensional representation of a robot into an associated robot map representing the two-dimensional projection of the initial position of the robot upon the common surface by inserting a mark in those memory locations presenting squares in which at least a part of the robot is projected;

(c) combining each robot map with the world map by combining the data stored in the memory storage device world map and robot maps to install the robots into the world map;

(d) removing the robot of a robot map from said world map by removing the robot data from the world map data in the memory storage device responsive to a requested move for the robot which is being removed;

(e) creating a robot map in which the total swept area of the move is installed by inserting a mark in those memory device locations representing each square of the robot map touched by said swept area, said swept area representing the total area of movement of the robot from the initial position to a desired final position;

(f) combining stored data representing the swept area of the robot map with the world map by storing data in each square of the world map where whenever a mark is present in the corresponding square of either the world map or the robot map but not both; and

(g) indicating a possible collision if any stored data representing corresponding squares in the world map and the swept area robot map both contain a mark.

29. The method of claim 28 further comprising the steps of:

(h) removing stored data from the memory storage means representing the marks from the world map representing the swept area of a robot responsive to a collision indication;

(i) creating a robot map according to step (e) for a swept area extending between the initial position and a desired final position different from the desired final position employed in step (e) when originally performed; and

(j) combining data in the memory locations representing the swept area robot map created during step (i) with the world map.

30. The method of claim 28 further comprising the step of providing a non-collision indication when none of the locations representing associated squares in the world map and the swept area robot map created in step (i) each contain data representing a mark.

31. In a robot system incorporating a plurality of robots movable along a common platen surface, each robot including means for moving the robot along said platen in mutually perpendicular directions, collision detection apparatus comprising:

memory means for storing two-dimensional representations of said robot projected onto the surface of said platen and comprised of memory sections having memory cells for storing binary data, the memory cells being of a number sufficient to represent an xy grid of uniform sized squares each representing a predetermined area along said platen surface;

said memory being divided into a world map memory section and a plurality of robot map sections each memory section being representative of the surface area of said platen;

means for installing a two-dimensional representation of the initial position of each robot in its associated robot map by inserting a binary bit of a predetermined binary state into those memory cells representing square areas touched by the two-dimensional representation of the associated robot;

means for combining the robot maps with the world map by installing the binary states of the memory cells in each robot map into the memory cells representing the world map;

means responsive to a request for movement of a predetermined robot for removing the representation of the initial position of said predetermined robot from the world map by combining the binary data in the associated memory cells of the predetermined robot map and the world map in a logical operation;

means for creating a robot swept area map representative of the two-dimensional region occupied by the said predetermined robot and moving from its initial position to a desired final position by inserting binary bits of said predetermined binary state into those memory cells touched by the swept area;

first means for combining the robot swept area into the world map by combining the binary data of the associated memory cells of the swept area robot map and world map in a first type of logical ORing operation;

second means for combining the binary data in the memory cells of the swept area robot map with the binary data in the associated memory cells of the world map employing a second type of logical ORing operation;

means for comparing the binary data of associated memory cells resulting from the two last-mentioned logical ORing operations, including means for indicating a collision in the event that the binary states of associated memory locations are unequal.

32. The apparatus of claim 31 further comprising means for providing an allocation signal when the data compared by said comparison means is equal.

33. The apparatus of claim 32 further comprising:

means for inserting the binary data generated by said second combining means responsive to said allocation signal.

34. The apparatus of claim 31 wherein said robot system comprises a conductive platen and each of said robots comprises xy forcer means for generating electro-magnetic fields in mutually perpendicular directions to propel the robot along said platen.

35. The apparatus of claim 34 further comprising means for driving said robots including an umbilical cord for coupling drive signals to said xy forcer means.

36. The apparatus of claim 35 wherein said means for generating said robot swept area map further includes means for installing a two-dimensional representation of the robot means umbilical cord in said robot swept area map by inserting binary bits of said predetermined binary state into those memory cells representing squares touched by the two-dimensional projection of the umbilical cord upon the platen surface.

37. The apparatus of claim 31 further comprising:

means for generating a collision signal when the data compared by said comparison means is unequal;

means for removing a swept area two-dimensional representation of a robot from said world map by combining the binary data of the memory cells associated with said robot swept area map with the binary data contained in the memory cells representing said world map employing a predetermined logical ORing operation;

means for installing the two-dimensional representation of the initial position of the robot whose swept area has indicated a collision condition by combining the binary data in the memory cells representing the robot initial position with the binary data in the memory cells representing said world map, employing a predetermined type of logical OR operation.

38. The apparatus of claim 31 wherein one of said logical OR operations comprises an exclusive OR operation.

39. The apparatus of claim 31 wherein one of said logical OR operations comprises an inclusive-OR operation.

40. The apparatus of claim 31 wherein one of said logical OR operations comprises an exclusive-OR operation and the other one of said logical OR operations comprises an inclusive-OR operation.

41. The apparatus of claim 31 wherein said predetermined binary state comprises a binary one state.