# US 2021/0278857 A1 · Method and system for obstacle avoidance in robot path planning using depth sensors

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

- Number: US 2021/0278857 A1
- Document ID: US20210278857A1
- Status: Published application
- Kind: A1
- Application number: 17/193,557
- Filed: 2021-03-05
- Published: 2021-09-09
- Earliest claimed: 2020-03-06
- Assignees: Edda Technology, Inc.
- Applicants: Edda Technology, Inc.
- Inventors: Guo-Qing WEI; Yuanfeng MAO; Li FAN; Xiaolan ZENG; Jianzhong QIAN
- Web page: https://patentgrep.com/patent/US20210278857A1

## CPC

- B25J 19/021: {Optical sensing devices}
- G05D 1/0238: {using obstacle or wall sensors (G05D1/0246 and G05D1/0289 take precedence; lidar systems designed for anti-collision purposes G01S17/93)}
- B25J 9/1666: {Avoiding collision or forbidden zones}
- G05B 2219/40442: Voxel map, 3-D grid map
- G05B 2219/40455: Proximity of obstacles
- G05B 2219/40476: Collision, planning for collision free path
- 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})
- G05D: SYSTEMS FOR CONTROLLING OR REGULATING NON-ELECTRIC VARIABLES
- 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

The present teaching relates to method, system, medium, and implementations for robot path planning. Depth data of obstacles, acquired by depth sensors deployed in a 3D robot workspace and represented with respect to a sensor coordinate system, is transformed into depth data with respect to a robot coordinate system. The 3D robot workspace is discretized to generate 3D grid points representing a discretized 3D robot workspace. Based on the depth data with respect to the robot coordinate system, binarized values are assigned to at least some of 3D grid points to generate a binarized representation for the obstacles present in the 3D robot workspace. With respect to one or more sensing points associated with a part of a robot, it is determined whether the part is to collide with any obstacle. Based on the determining, a path is planned for the robot to move along while avoiding any obstacle.

## Claims

### Claim 1

A method implemented on at least one processor, memory, and communication platform capable of connecting to a network for robot path planning, the method comprising:
transforming depth data of obstacles, acquired by one or more depth sensors deployed in a 3D robot workspace and represented with respect to a sensor coordinate system, into depth data with respect to a robot coordinate system;
discretizing the 3D robot workspace to generate a set of 3D grid points representing a discretized 3D robot workspace;
assigning, based on the depth data with respect to the robot coordinate system, binarized values to at least some of the set of 3D grid points to generate a binarized representation for the obstacles present in the 3D robot workspace;
determining, with respect to one or more sensing points associated with a part of a robot, whether the part is to collide with any of the obstacles in the 3D robot workspace; and
planning, based on a result of the determining, a path for the robot to move along while avoiding any of the obstacles.

### Claim 2 (depends on 1)

The method of claim 1, wherein the step of assigning comprises:
for each 3D grid point of the set of 3D grid points,
assigning, when it is determined that at least some of the depth data with respect to the robot coordinate system coincide with the 3D grid point, a first value to the 3D grid point representing presence of an obstacle;
assigning, when it is determined that no depth data with respect to the robot coordinate system coincides with the 3D grid point, a second value to the 3D grid point indicating no presence of an obstacle; and
assigning the second value to the 3D grid point, when a projection of the 3D grid point onto a base-plane of the robot coordinate system overlaps a projection of the robot on the base-plane.

### Claim 3 (depends on 2)

The method of claim 2, wherein the one or more sensing points are along a central line of the part and the step of determining comprises:
generating, based on the binarized representation for the obstacles, a distance map with respect to an allowable obstacle distance to represent, with respect to each 3D grid point of the set of 3D grid points with the second value, a distance to a closest one of the set of 3D grid points with the first value; and
for each sensing point,
reading, from the distance map, a distance value associated with the sensing point,
obtaining a sum of the distance value and a radius of the part, and
evaluating whether the part is to collide with any of the obstacles by comparing the sum against the allowable obstacle distance.

### Claim 4 (depends on 3)

The method of claim 3, wherein the step of generating the distance map comprises:
sub-sampling the set of 3D grid points at a plurality of scales;
at each scale of the plurality of scales:
assigning a corresponding maximum-to-compute distance, and
generating, based on the maximum-to-compute distance, a distance sub-map with respect to the scale; and
merging distance sub-maps with respect to the plurality of scales.

### Claim 5 (depends on 4)

The method of claim 4, wherein the maximum-to-compute distance is determined based on the allowable obstacle distance and an adjustment factor, wherein
the adjustment factor is determined based on a level of the plurality of scales.

### Claim 6 (depends on 2)

The method of claim 2, wherein the one or more sensing points are along a plurality of sensing lines emanating from the part, and the step of determining comprises:
for each sensing line of the plurality of sensing lines,
identifying, with respect to at least one of the one or more sensing points on the sensing line, a closest 3D grid point, and
evaluating whether the part is to collide with any of the obstacles based on whether the closest 3D grid point has the first value or the second value.

### Claim 7 (depends on 1)

The method of claim 1, further comprising:
computing, via calibration, a sensor-robot transformation between the sensor coordinate system and the robot coordinate system, wherein the step of transforming is performed based on the sensor-robot transformation.

### Claim 8

Machine readable and non-transitory medium having information recorded thereon, where the information, when read by a machine, causes the machine to perform:
transforming depth data of obstacles, acquired by one or more depth sensors deployed in a 3D robot workspace and represented with respect to a sensor coordinate system, into depth data with respect to a robot coordinate system;
discretizing the 3D robot workspace to generate a set of 3D grid points representing a discretized 3D robot workspace;
assigning, based on the depth data with respect to the robot coordinate system, binarized values to at least some of the set of 3D grid points to generate a binarized representation for the obstacles present in the 3D robot workspace;
determining, with respect to one or more sensing points associated with a part of a robot, whether the part is to collide with any of the obstacles in the 3D robot workspace; and
planning, based on a result of the determining, a path for the robot to move along while avoiding any of the obstacles.

### Claim 9 (depends on 8)

The medium of claim 8, wherein the step of assigning comprises:
for each 3D grid point of the set of 3D grid points,
assigning, when it is determined that at least some of the depth data with respect to the robot coordinate system coincide with the 3D grid point, a first value to the 3D grid point representing presence of an obstacle;
assigning, when it is determined that no depth data with respect to the robot coordinate system coincides with the 3D grid point, a second value to the 3D grid point indicating no presence of an obstacle, and
assigning the second value to the 3D grid point, when a projection of the 3D grid point onto a base-plane of the robot coordinate system overlaps a projection of the robot on the base-plane.

### Claim 10 (depends on 9)

The medium of claim 9, wherein the one or more sensing points are along a central line of the part and the step of determining comprises:
generating, based on the binarized representation for the obstacles, a distance map with respect to an allowable obstacle distance, to represent, with respect to each of the set of 3D grid points with the second value, a distance to a closest one of the set of 3D grid points with the first value; and
for each sensing point,
reading, from the distance map, a distance value associated with the sensing point,
obtaining a sum of the distance value and a radius of the part, and
evaluating whether the part is to collide with any of the obstacles by comparing the sum against the allowable obstacle distance.

### Claim 11 (depends on 10)

The medium of claim 10, wherein the step of generating the distance map comprises:
sub-sampling the set of 3D grid points at a plurality of scales;
at each scale of the plurality of scales:
assigning a corresponding maximum-to-compute distance, and
generating, based on the maximum-to-compute distance, a distance sub-map with respect to the scale; and
merging distance sub-maps with respect to the plurality of scales.

### Claim 12 (depends on 11)

The medium of claim 11, wherein the maximum-to-compute distance is determined based on the allowable obstacle distance and an adjustment factor, wherein
the adjustment factor is determined based on a level of the plurality of scales.

### Claim 13 (depends on 9)

The medium of claim 9, wherein the one or more sensing points are along a plurality of sensing lines emanating from the part, and the step of determining comprises:
for each sensing line of the plurality of sensing lines,
identifying, with respect to at least one of the one or more sensing points on the sensing line, a closest 3D grid point, and
evaluating whether the part is to collide with any of the obstacles based on whether the closest 3D grid point has the first value or the second value.

### Claim 14 (depends on 8)

The medium of claim 8, further comprising:
computing, via calibration, a sensor-robot transformation between the sensor coordinate system and the robot coordinate system, wherein the step of transforming is performed based on the sensor-robot transformation.

### Claim 15

A system for robot path planning, comprising:
a coordinate transformer configured for transforming depth data of obstacles, acquired by one or more depth sensors deployed in a 3D robot workspace and represented with respect to a sensor coordinate system, into depth data with respect to a robot coordinate system;
a workspace discretizing unit configured for discretizing the 3D robot workspace to generate a set of 3D grid points representing a discretized 3D robot workspace;
a workspace binarizing unit configured for assigning, based on the depth data with respect to the robot coordinate system, binarized values to at least some of the set of 3D grid points to generate a binarized representation for the obstacles present in the 3D robot workspace;
a collision determining unit configured for determining, with respect to one or more sensing points associated with a part of a robot, whether the part is to collide with any of the obstacles in the 3D robot workspace; and
a path planning unit configured for planning, based on a result of the determining, a path for the robot to move along while avoiding any of the obstacles.

### Claim 16 (depends on 15)

The system of claim 15, wherein the workspace binarizing unit performs, for each 3D grid point of the set of 3D grid points, the following steps:
assigning, when it is determined that at least some of the depth data with respect to the robot coordinate system coincide with the 3D grid point, a first value to the 3D grid point representing presence of an obstacle;
assigning, when it is determined that no depth data with respect to the robot coordinate system coincides with the 3D grid point, a second value to the 3D grid point indicating no presence of an obstacle; and
assigning the second value to the 3D grid point, when a projection of the 3D grid point onto a base-plane of the robot coordinate system overlaps a projection of the robot on the base-plane.

### Claim 17 (depends on 16)

The system of claim 16, wherein the one or more sensing points are along a central line of the part, and the collision determining unit performs:
generating, based on the binarized representation for the obstacles, a distance map with respect to an allowable obstacle distance, to represent, with respect to each 3D grid point of the set of 3D grid points with the second value, a distance to a closest one of the set of 3D grid points with the first value; and
for each sensing point,
reading, from the distance map, a distance value associated with the sensing point,
obtaining a sum of the distance value and a radius of the part, and
evaluating whether the part is to collide with any of the obstacles by comparing the sum against the allowable obstacle distance.

### Claim 18 (depends on 17)

The system of claim 17, wherein the distance map is generated by:
sub-sampling the set of 3D grid points at a plurality of scales;
at each scale of the plurality of scales:
assigning a corresponding maximum-to-compute distance, and
generating, based on the maximum-to-compute distance, a distance sub-map with respect to the scale; and
merging distance sub-maps with respect to the plurality of scales.

### Claim 19 (depends on 18)

The system of claim 18, wherein the maximum-to-compute distance is determined based on the allowable obstacle distance and an adjustment factor, wherein
the adjustment factor is determined based on a level of the plurality of scales.

### Claim 20 (depends on 16)

The system of claim 16, wherein the one or more sensing points are along a plurality of sensing lines emanating from the part, and the collision determining unit performs,
for each sensing line of the plurality of sensing lines,
identifying, with respect to at least one of the one or more sensing points on the sensing line, a closest 3D grid point, and
evaluating whether the part is to collide with any of the obstacles based on whether the closest 3D grid point has the first value or the second value.
