# US 2024/0198524 A1 · Deep collision avoidance

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2024/0198524 A1
- Document ID: US20240198524A1
- Status: Published application
- Kind: A1
- Application number: 18/067,157
- Filed: 2022-12-16
- Published: 2024-06-20
- Earliest claimed: 2022-12-16
- Assignees: Fanuc Corporation
- Applicants: Fanuc Corporation
- Inventors: Yongxiang Fan
- Web page: https://patentgrep.com/patent/US20240198524A1

## CPC

- B25J 9/1666: {Avoiding collision or forbidden zones}
- B25J 9/1612: {characterised by the hand, wrist, grip control}
- G05B 2219/40492: Model manipulator by spheres for collision avoidance
- B25J: MANIPULATORS; CHAMBERS PROVIDED WITH MANIPULATION DEVICES ({manipulators specially adapted for use in surgery A61B34/70; manipulators used in cleaning hollow articles B08B9/04}; manipulators associated with rolling mills B21B39/20; manipulators associated with forging machines B21J13/10; {manipulators associated with picking-up and placing mechanisms B23P19/007}; means for holding wheels or parts thereof B60B30/00; {vehicles with ground-engaging propulsion means, e.g. walking members B62D57/02, B62D57/032; devices for picking-up and depositing articles or materials between conveyors B65G47/90, B65G47/91; manipulators with gripping or holding means for transferring packages B65H67/065}; cranes B66C; {manipulators used in the protection or supervision of pipe-line installations F17D5/00; walking equipment adapted for nuclear steam-generators F22B37/006}; manipulators specially adapted for, or associated with, nuclear reactors G21C; {apparatus used for handling wafers during manufacture or treatment of semiconductor H10P72/50})
- G05B: CONTROL OR REGULATING SYSTEMS IN GENERAL; FUNCTIONAL ELEMENTS OF SUCH SYSTEMS; MONITORING OR TESTING ARRANGEMENTS FOR SUCH SYSTEMS OR ELEMENTS (systems for controlling or regulating non-electric variables G05D; systems for regulating electric or magnetic variables G05F; control devices or systems insofar as characterised by mechanical features only G05G)

## Abstract

A system and method for providing deep collision avoidance between objects in a robotic system. For a collision between a part and an object, the method decomposes the part into a union of part balls having a known radius and center location and decomposes the object into a union of object balls having a known radius and center location. The method obtains a Minkowski difference between each pair of the part balls and the object balls, converts each Minkowski difference into a Minkowski ball having a known center location and radius, and combines the Minkowski balls into a union of overlapping Minkowski balls. The method determines an outer boundary of the union of the overlapping Minkowski balls, extracts boundary points on the boundary as escape vectors, and maps each of the escape vectors into collision-free part pose.

## Claims

### Claim 1

A system for preventing a collision between a part and an object, said system comprising:
a computer including at least one processor and a memory device storing data and executable code that, when executed, causes the at least one processor to:
decompose the part into a union of part balls having a known radius and center location and decompose the object into a union of object balls having a known radius and center location;
obtain a Minkowski difference between each pair of the part balls and the object balls;
convert each Minkowski difference into a Minkowski ball having a known center location and radius;
combine the Minkowski balls into a union of overlapping Minkowski balls;
determine an outer boundary of the union of the overlapping Minkowski balls;
extract boundary points on the boundary as escape vectors; and
map each of the escape vectors into collision-free part pose.

### Claim 2 (depends on 1)

The system according to claim 1 wherein the at least one processor decomposes the part and the object off-line.

### Claim 3 (depends on 1)

The system according to claim 1 wherein the at least one processor decomposes the part and the object into balls having the same radius.

### Claim 4 (depends on 1)

The system according to claim 1 wherein the at least one processor decomposes the part and the object into balls having varying radii.

### Claim 5 (depends on 1)

The system according to claim 1 wherein the at least one processor identifies the center location of the Minkowski ball by subtracting the center location of the part ball in the pair from the center location of the object ball in the pair, and determines the radius of the Minkowski ball by adding the radius of the part ball in the pair and the radius of the object ball in the pair.

### Claim 6 (depends on 1)

The system according to claim 1 wherein the at least one processor associates the union of the overlapping Minkowski balls with a grid structure having cells and assigning each cell an identifier depending on where the cell is relative to the Minkowski balls.

### Claim 7 (depends on 6)

The system according to claim 6 wherein cells internal to a Minkowski ball are given an internal identifier, cells on a boundary of a Minkowski ball are given a boundary identifier and cells in unoccupied space are given an unoccupied identifier.

### Claim 8 (depends on 7)

The system according to claim 7 wherein the cells for each Minkowski ball are assigned an identifier independent of other Minkowski balls and wherein overlapping boundary cells between Minkowski balls are given the internal identifier.

### Claim 9 (depends on 7)

The system according to claim 7 wherein a template for cell identifiers for Minkowski cells of known sizes is pre-computed.

### Claim 10 (depends on 1)

The system according to claim 1 wherein the part is a robot gripper.

### Claim 11

A method for preventing a collision between a part and an object, said method comprising:
decomposing the part into a union of part balls having a known radius and center location and decomposing the object into a union of object balls having a known radius and center location;
obtaining a Minkowski difference between each pair of the part balls and the object balls;
converting each Minkowski difference into a Minkowski ball having a known center location and radius;
combining the Minkowski balls into a union of overlapping Minkowski balls;
determining an outer boundary of the union of the overlapping Minkowski balls;
extracting boundary points on the boundary as escape vectors; and
mapping each of the escape vectors into collision-free part pose.

### Claim 12 (depends on 11)

The method according to claim 11 wherein decomposing the part and the object includes decomposing the part and the object off-line.

### Claim 13 (depends on 11)

The method according to claim 11 wherein decomposing the part and the object includes decomposing the part and the object into balls having the same radius.

### Claim 14 (depends on 11)

The method according to claim 11 wherein decomposing the part and the object includes decomposing the part and the object into balls having varying radii.

### Claim 15 (depends on 11)

The method according to claim 11 wherein obtaining a Minkowski difference and converting each Minkowski difference into a Minkowski ball includes identifying the center location of the Minkowski ball by subtracting the center location of the part ball in the pair from the center location of the object ball in the pair, and determining the radius of the Minkowski ball by adding the radius of the part ball in the pair and the radius of the object ball in the pair.

### Claim 16 (depends on 11)

The method according to claim 11 wherein determining an outer boundary of the union of the overlapping Minkowski balls includes associating the union of the overlapping Minkowski balls with a grid structure having cells and assigning each cell an identifier depending on where the cell is relative to the Minkowski balls.

### Claim 17 (depends on 16)

The method according to claim 16 wherein cells internal to a Minkowski ball are given an internal identifier, cells on a boundary of a Minkowski ball are given a boundary identifier and cells in unoccupied space are given an unoccupied identifier.

### Claim 18 (depends on 17)

The method according to claim 17 wherein the cells for each Minkowski ball are assigned an identifier independent of other Minkowski balls and wherein overlapping boundary cells between Minkowski balls are given the internal identifier.

### Claim 19 (depends on 17)

The method according to claim 17 wherein a template for cell identifiers for Minkowski cells of known sizes is pre-computed.

### Claim 20 (depends on 1)

The method according to claim 1 wherein the part is a robot gripper.
