Link level wind factor computation for efficient drone routing using 3D city map data

Patent metadata

Field	Value
Publication number	US-10698422-B2
Application number	US-201715724974-A
Country	US
Kind code	B2
Filing date	Oct 4, 2017
Priority date	Oct 4, 2017
Publication date	Jun 30, 2020
Grant date	Jun 30, 2020

Abstract

Embodiments include apparatus and methods for determining link level wind factors and providing routes for drones based on the wind factors. At least a portion of the route corresponds to airspace above a road network. Wind factor values are assigned to a range of altitudes of drone air space above a road link of the road network based on a wind model and stored in a database. The wind model is applied to a location based on wind condition data and three-dimensional (3D) features from 3D map data associated with the location. The route is optimized based on the determined wind factors.

First claim

We claim:

1. A method of determining link level wind factors for unmanned aerial vehicle (UAV) routing, the method comprising:
accessing, by a processor, three-dimensional (3D) features from 3D map data for a location and road link data for a road link network associated with the location;
accessing, by the processor, wind condition data for the location;
applying, by the processor, a wind model for the location based on the 3D features and the wind condition data;
assigning, by the processor, wind factor values for a plurality of altitudes of UAV air space above a link of the road link network based on the wind model;
associating, by the processor, the wind factor values and the road link data for the link of the road link network; and
storing the wind factor values in a database.

2. The method of claim 1 , wherein applying the wind model comprises:
performing a computational fluid dynamics simulation over the 3D map data associated with the location.

3. The method of claim 1 , wherein applying the wind model comprises:
receiving real time wind data from sensors at the location, wherein at least one wind factor value is refined based on real time wind data received from sensors at the location.

4. The method of claim 1 , wherein storing the wind factor values in the database further comprises:
storing the wind factor values such that said wind factor values are queryable using a prevailing wind condition, a link identifier for the road link, or a combination thereof, as query parameters.

5. The method of claim 1 , wherein the wind factor values comprise a measure of wind speed relative to a direction of the road link.

6. The method of claim 5 , wherein the wind factor values further comprise a measure of volatility of a respective wind speed.

7. The method of claim 1 , wherein the wind factor values correspond to an altitude in the air space above the road link.

8. A method for providing a route for a drone, the method comprising:
providing in response to a routing request, with a processor, a route from a starting location to a destination, wherein at least a portion of the route corresponds to airspace above a road network in a geographic region;
for the portion of the route that corresponds to airspace above a road network, using a wind factor value database, wherein the wind factor value database includes factors for wind speed, wind direction and altitude above the road network, wherein the factors in the wind factor value database are based on a wind model; and
optimizing the route for a selected criterion.

9. The method of claim 8 , wherein the wind factor value database further comprises wind speed volatility factors.

10. The method of claim 8 , wherein the selected criterion is minimal time to traverse the route or minimal energy consumption.

11. The method of claim 8 , wherein the routing request includes drone-specific information, the drone-specific information being used for determining at least one operational threshold of the drone.

12. The method of claim 8 , wherein the selected criterion is least likelihood of crashing.

13. The method of claim 8 , wherein for at least a portion of the route corresponding to airspace that is not above a road network in the geographic region, and wherein the wind factor value database further comprises values for airspace that is not above a road network, wherein the wind factor value database includes factors for wind speed, wind direction and altitude across the airspace that is not above a road network.

14. The method of claim 13 , wherein the optimizing further includes selecting portions for the route that include airspace above the road network and airspace not above the road network based on use of the wind factor value database.

15. The method of claim 8 , wherein the selected criterion is shortest path if a prevailing wind condition is below a predetermined threshold.

16. The method of claim 8 , wherein calculating the route for a drone further comprises:
identifying existing drone flight paths associated with the starting location; and
calculating the drone route based on the existing drone flight paths.

17. The method of claim 8 , further comprising:
in response to receiving a real-time wind condition update for a location along the route, recalculating the route based on said update; and
providing the recalculated route to the drone.

18. An apparatus for determining link level wind factors for unmanned aerial vehicle (UAV) routing, the apparatus comprising:
a database configured to store three-dimensional (3D) features and map data for a location, the map data including road link data for a road link network associated with the location; and
a controller configured to apply a wind model for the location based on the 3D features and wind condition data for the location and associate wind factor values with the road link data for a link of the road link network, wherein the wind factor values are for a plurality of altitudes of UAV air space above the link of the road link network based on the wind model.

19. The apparatus of claim 18 , wherein the controller, to apply the wind model, is configured to perform a computational fluid dynamics simulation over the map data associated with the location.

20. The apparatus of claim 18 , wherein at least one wind factor value is refined based on real time wind data received from sensors associated with the location.

21. The apparatus of claim 18 , wherein the wind factor values comprise a measure of wind speed relative to a direction of the road link, the wind factor values further comprise a measure of volatility of the wind speed relative to the direction of the road link, or an altitude in the air space above the road link.

22. An apparatus for providing a route for a drone, the apparatus comprising:
a wind factor value database configured to store factors for wind speed, wind direction and altitude above a road network, wherein the factors in the wind factor value database are based on a wind model and associated with road link data for the road network;
a communication interface configured to receive a routing request; and
a processor configured to calculate, in response to the routing request, a route from a starting location to a destination, wherein at least a portion of the route corresponds to airspace above the road network in a geographic region selected based on the factors from the wind factor value database and a selected criterion.

23. The apparatus of claim 22 , wherein the selected criterion is minimal time to traverse the route, minimal energy consumption, or least likelihood of crashing.

24. The apparatus of claim 22 , wherein the selected criterion is shortest path if a prevailing wind condition is below a predetermined threshold.

25. The apparatus of claim 22 , wherein the communication interface is configured to send the route to the drone.

26. The apparatus of claim 25 , wherein, in response to receiving a real-time wind condition update along the route, the processor is configured to recalculate the route based on said update and the communication interface is configured to provide the recalculated route to the drone.

Assignees

• Here Global Bv

Inventors

• Tuukkanen Marko
• Beaurepaire Jerome

Classifications

• B64U2201/00

  UAVs characterised by their flight controls · CPC title

• B64U2201/104

  using satellite radio beacon positioning systems, e.g. GPS · CPC title

• G06Q10/047 Primary

  Optimisation of routes or paths, e.g. travelling salesman problem · CPC title

• B64U2101/00

  UAVs specially adapted for particular uses or applications · CPC title

• G05D1/101

  specially adapted for aircraft · CPC title