Method and apparatus for anti-collision and collision protection for multiple robot system
First Claim
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 Assignments
0 Petitions
Accused Products
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.
-
Citations
41 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27)
-
-
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. - View Dependent Claims (29, 30)
-
-
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. - View Dependent Claims (32, 33, 34, 35, 36, 37, 38, 39, 40, 41)
-
Specification