# US 2021/0172740 A1 · Method and apparatus for providing aerial route calculation in a three-dimensional space

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

- Number: US 2021/0172740 A1
- Document ID: US20210172740A1
- Status: Published application
- Kind: A1
- Application number: 16/709,556
- Filed: 2019-12-10
- Published: 2021-06-10
- Earliest claimed: 2019-12-10
- Assignees: HERE Global B.V.
- Applicants: HERE Global B.V.
- Inventors: Raul CAJIAS; Daniel ROLF
- Web page: https://patentgrep.com/patent/US20210172740A1

## CPC

- G08G 5/26: Transmission of traffic-related information between aircraft and ground stations
- G08G 5/32: for flight plan preparation
- G01C 21/20: Instruments for performing navigational calculations (G01C21/24, G01C21/26 take precedence)
- G01C 21/3867: {Geometry of map features, e.g. shape points, polygons or for simplified maps}
- G08G 5/22: located on the ground
- G08G 5/55: for a single aircraft
- G08G 5/57: for unmanned aircraft
- G08G 5/80: Anti-collision systems
- B64U 10/00: Type of UAV
- B64U 2201/10: autonomous, i.e. by navigating independently from ground or air stations, e.g. by using inertial navigation systems [INS]
- B64U 2201/20: Remote controls
- G08G: TRAFFIC CONTROL SYSTEMS (guiding railway traffic, ensuring the safety of railway traffic B61L; arrangement of road signs or traffic signals E01F9/00; radar or analogous systems, sonar systems, lidar systems specially adapted for traffic control G01S13/91, G01S15/88, G01S17/88; {radar or analogous systems, sonar systems, lidar systems specially adapted for anti-collision purposes G01S13/93, G01S15/93, G01S17/93})
- G01C: MEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY (measuring liquid level G01F; radio navigation, determining distance or velocity by use of propagation effects, e.g. Doppler effects, propagation time, of radio waves, analogous arrangements using other waves G01S)
- B64U: UNMANNED AERIAL VEHICLES [UAV]; EQUIPMENT THEREFOR

## Abstract

An approach is provided for aerial route calculation in a three-dimensional (3D) space. The approach, for example, involves receiving a request to route an aerial vehicle through the 3D space from a start location to a target location. The 3D is represented as 3D shapes (e.g., cubes). The approach also involves matching the start location and the target location respectively to a start shape and a target shape in the 3D space. The approach further involves computing a route through the 3D shapes from the start shape to the target shape based on a collision probability determined based on a first probability of survival due to volume-related factors, a second probability of survival due to aerial-vehicle-related factors, or a combination.

## Claims

### Claim 1

A method for routing an aerial vehicle through a three-dimensional space comprising:
receiving a request to route the aerial vehicle through the three-dimensional space from a start location to a target location, wherein the three-dimensional space is represented as a plurality of three-dimensional shapes;
matching the start location and the target location respectively to a start shape and a target shape of the plurality of three-dimensional shapes; and
computing a route through the plurality of three-dimensional shapes from the start shape to the target shape based on a collision probability determined based on a first probability of survival due to volume-related factors, a second probability of survival due to aerial-vehicle-related factors, or a combination thereof for the plurality of three-dimensional shapes from the start shape to the target shape,
wherein the path includes a set of three-dimensional shapes between the start shape and the target shape.

### Claim 2 (depends on 1)

The method of claim 1, wherein the plurality of three-dimensional shapes is a plurality of cubes.

### Claim 3 (depends on 1)

The method of claim 1, wherein the first probability of survival is based on a collision probability computed from map data of the three-dimensional space.

### Claim 4 (depends on 1)

The method of claim 1, wherein the second probability of survival is based on a one or more intrinsic factors of the aerial vehicle.

### Claim 5 (depends on 4)

The method of claim 4, further comprising:
computing the second probability of survival as a function of a number of the plurality of three-dimensional shapes that the aerial vehicle is predicted to traverse before a predicted failure due to the one or more intrinsic factors.

### Claim 6 (depends on 1)

The method of claim 1, further comprising:
selecting a resolution for the plurality of three-dimensional shapes, wherein the resolution determines an amount of the three-dimensional space represented by a volume of the plurality of three-dimensional shapes,
wherein the route is computed based on the resolution.

### Claim 7 (depends on 6)

The method of claim 6, further comprising:
determining that the collision probability for the route is below a survival threshold;
selecting another resolution for the plurality of three-dimensional shapes; and
re-computing the route based on the another resolution.

### Claim 8 (depends on 1)

The method of claim 1, further comprising:
determining that the collision probability for the route is below a survival threshold; and
selecting another aerial vehicle to fly the route based on the another aerial vehicle having a higher probability of survival due to aerial-vehicle related factors than the aerial vehicle.

### Claim 9 (depends on 1)

The method of claim 1, further comprising:
determining an insurance cost, a delivery cost, or a combination thereof for the aerial vehicle to fly the route based on the collision probability for the route.

### Claim 10 (depends on 1)

The method of claim 1, wherein the request specifies a threshold value for the collision probability, and wherein the route is further computed based on the threshold value.

### Claim 11 (depends on 1)

The method of claim 1, further comprising:
encoding the route, the collision probability for one or more of the plurality of three-dimensional shapes from the start shape to the target shape, or a combination there in an output; and
transmitting the output the aerial vehicle.

### Claim 12

An apparatus for routing an aerial vehicle through a three-dimensional space comprising:
at least one processor; and
at least one memory including computer program code for one or more programs,
the at least one memory and the computer program code configured to, with the at least one processor, cause the apparatus to:
transmit a request for a route through the three-dimensional space from a start location to a target location;
in response to the request, receive a route that is generated based on representing the three-dimensional space as a plurality of three-dimensional shapes,
wherein the route matches the start location and the target location respectively to a start shape and a target shape of the plurality of three-dimensional shapes; and
wherein the route comprises the start shape, the target shape, and a set of the plurality of three-dimensional shapes traversing from the start shape to the target shape;
receive collision probability data for the plurality of three-dimensional shapes in the route; and
determine to reject or to accept the route based on the collision probability.

### Claim 13 (depends on 12)

The apparatus of claim 12, wherein the apparatus is further caused to:
transmit another request for the route, the another request specifying a collision probability threshold; and
in response to the another request, receive another route based on the collision probability threshold.

### Claim 14 (depends on 12)

The apparatus of claim 12, wherein the plurality of three-dimensional shapes is a plurality of cubes, and wherein the apparatus is further caused to:
determine a trajectory for a current position of the aerial vehicle to a closest point on a face of a next cube on the route; and
navigate the aerial vehicle along the trajectory.

### Claim 15 (depends on 14)

The apparatus of claim 14, wherein the apparatus is further caused to:
process sensor data of the aerial vehicle to determine a presence of an obstacle along the trajectory; and
select another point on the face of the cube to determine the trajectory to avoid the obstacle.

### Claim 16 (depends on 14)

The apparatus of claim 14, wherein the apparatus is further caused to:
determine that the collision probability data for a cube to be traversed by the trajectory is above a threshold value; and
navigate the aerial vehicle along the trajectory at a speed determined based on a response time of an onboard sensor of the aerial vehicle.

### Claim 17 (depends on 14)

The apparatus of claim 14, wherein the apparatus is further caused to:
determine that the collision probability data for a cube traversed by the trajectory is below a threshold value; and
navigate the aerial vehicle along the trajectory with an onboard sensor the aerial configured in a low power mode.

### Claim 18

A non-transitory computer-readable storage medium for routing an aerial vehicle through a three-dimensional space, carrying one or more sequences of one or more instructions which, when executed by one or more processors, cause an apparatus to perform:
receiving a request to route the aerial vehicle through the three-dimensional space from a start location to a target location, wherein the three-dimensional space is represented as a plurality of three-dimensional shapes;
matching the start location and the target location respectively to a start shape and a target shape of the plurality of three-dimensional shapes; and
computing a route through the plurality of three-dimensional shapes from the start shape to the target shape based on a collision probability determined based a first probability of survival due to volume-related factors, a second probability of survival due to aerial-vehicle-related factors, or a combination thereof for the plurality of three-dimensional shapes from the start shape to the target shape,
wherein the path includes a set of three-dimensional shapes between the start shape and the target shape.

### Claim 19 (depends on 18)

The non-transitory computer-readable storage medium of claim 18, wherein the first probability of survival is based on a collision probability computed from map data of the three-dimensional space.

### Claim 20 (depends on 18)

The non-transitory computer-readable storage medium of claim 18, wherein the second probability of survival is based on a one or more intrinsic factors of the aerial vehicle.
