Determining delivery areas for aerial vehicles

• US 10,219,112 B1
• Filed: 08/16/2017
• Issued: 02/26/2019
• Est. Priority Date: 09/30/2015
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Mishra, Pragyana K.
• Primary Examiner(s): Nguyen, Khai M
• Application Number:
  US15/678,972
• Time in Patent Office: 559 Days
• CPC Class Codes: G06Q 10/083 Shipping
• CPC Class Codes: H04W 4/021 Services related to particular areas, e.g. point of interest [POI] services, venue services or geofences
• CPC Class Codes: H04W 4/023 using mutual or relative location information between multiple location based services [LBS] targets or of distance thresholds

Abstract

Preferred points or regions in space for performing a task at a location, e.g., the delivery of an item to the location, may be defined based on sensed positions obtained during the prior performance of tasks at the location. The sensed positions may be identified using a GPS sensor or like system. Vectors including coordinates of the sensed position, and uncertainties of such coordinates, may be clustered into groups at the location. Subsequently identified vectors including coordinates and uncertainties may further refine a cluster, or be used to generate a new cluster. A preferred point or region in space may be identified based on such location hypotheses and utilized in the performance of tasks. Some preferred points or regions may be used for routing vehicles to the location, while others may correspond to delivery points for items at the location.

Claims

1. A delivery system comprising:

a plurality of unmanned aerial vehicles, wherein the plurality of unmanned aerial vehicles comprises a first unmanned aerial vehicle and a second unmanned aerial vehicle;

at least one memory component; and

at least one computer processor,

wherein the at least one computer processor is configured to at least;

receive, from the first unmanned aerial vehicle, a first set of coordinates of the first unmanned aerial vehicle during a first delivery of at least a first item to a location at a first time;

identify a geolocation corresponding to the location;

determine a first level of uncertainty associated with at least one of the first unmanned aerial vehicle at the first time or the first set of coordinates;

determine a first geoscan comprising a first Gaussian distribution having a first mean location at the first set of coordinates and the first level of uncertainty;

define a first region at the location based at least in part on the first geoscan and the geolocation, wherein the first region comprises a second Gaussian distribution having the first mean location at the first set of coordinates and the first level of uncertainty;

store information regarding the first region in at least one data store;

receive a request for a second delivery of at least a second item to the location;

identify at least one attribute of at least one of the second delivery or the second item based at least in part on the request;

determine that the first region is suitable for the second delivery based at least in part on the at least one attribute;

determine a path from an origin to the first region; and

transmit, to a second unmanned aerial vehicle, an instruction to deliver at least the second item from the origin to the first region along the path.

2. The delivery system of claim 1, wherein the at least one computer processor is further configured to at least:

receive, from the second unmanned aerial vehicle, a second set of coordinates of the second unmanned aerial vehicle during the second delivery at a second time;

determine a second level of uncertainty associated with at least one of the second unmanned aerial vehicle at the second time or the second set of coordinates;

define a second geoscan comprising a third Gaussian distribution centered at the second set of coordinates and having the second level of uncertainty;

determine that the second geoscan corresponds to the first region;

modify the second Gaussian distribution based at least in part on the second geoscan; and

update the information regarding the first region in the at least one data store based at least in part on the modified second Gaussian distribution.

3. The delivery system of claim 1, wherein the at least one computer processor is further configured to at least:

receive, from the second unmanned aerial vehicle, a second set of coordinates of the second unmanned aerial vehicle during the second delivery at a second time;

determine a second level of uncertainty associated with at least one of the second unmanned aerial vehicle at the second time or the second set of coordinates;

define a second geoscan comprising a third Gaussian distribution having a second mean location at the second set of coordinates and the second level of uncertainty;

determine that the second geoscan does not correspond to the first region;

in response to determining that the second geoscan does not correspond to the first region,

define a second region at the location based at least in part on the second geoscan and the geolocation, wherein the second region comprises a fourth Gaussian distribution having the second mean location and the second level of uncertainty; and

store information regarding the second region in the at least one data store.

4. The delivery system of claim 1, wherein the first set of coordinates are defined in three-dimensions, and

wherein the first set of coordinates comprise a latitude and a longitude for the first mean location and an altitude at the first mean location.

5. A method comprising:

after a first delivery of at least a first item to a location,

identifying a first sensed position associated with the first delivery using at least one computer processor;

determining a first level of uncertainty associated with at least the first sensed position using the at least one computer processor;

defining a first vector based at least in part on the first sensed position and the first level of uncertainty using the at least one computer processor;

determining a first geolocation associated with the location;

establishing a first preferred area for landing unmanned aerial vehicles at the location based at least in part on the first vector and the first geolocation using the at least one computer processor; and

storing information regarding the first preferred area in association with the location in at least one data store,

wherein the information regarding the first preferred area comprises a first probability distribution function for the first preferred area.

6. The method of claim 5, further comprising:

receiving a request for a second delivery of a second item to the location;

determining information regarding at least one of the second delivery, the second item or the location;

selecting the first preferred area based at least in part on the information regarding the at least one of the second delivery, the second item or the location using the at least one computer processor; and

transmitting information comprising a first instruction to proceed to the first preferred area to a first unmanned aerial vehicle over a network.

7. The method of claim 6, further comprising:

identifying an origin of the second item using the at least one computer processor; and

determining an optimal path from the origin to the first preferred area using the at least one computer processor,

wherein the first instruction to proceed to the first preferred area identifies at least a portion of the optimal path.

8. The method of claim 6, further comprising:

receiving, from the first unmanned aerial vehicle over the network, a second sensed position associated with the request for the second delivery of the second item to the location;

determining a second level of uncertainty associated with the second sensed position;

defining a second vector based at least in part on the second sensed position and the second level of uncertainty using the at least one computer processor;

determining whether the second vector corresponds to the first preferred area for the location using the at least one computer processor;

in response to determining that the second vector corresponds to the first preferred area,

modifying the first probability distribution function of the first preferred area based at least in part on the second vector; and

updating the information regarding the first preferred area in association with the location in the at least one data store,

wherein the updated information regarding the first preferred area comprises the modified first probability distribution function.

9. The method of claim 8, wherein the first probability distribution function for the first preferred area comprises a mean location for the first preferred area, at least one measure of uncertainty of the mean location, and an angle of orientation of the first preferred area, and

wherein modifying the first probability distribution function of the first preferred area based at least in part on the second vector further comprises:

generating a covariance matrix for the second vector using the at least one computer processor;

generating a covariance matrix for the first probability distribution function for the first preferred area using the at least one computer processor;

determining a first product of the covariance matrix for the second vector and the covariance matrix for the first probability distribution function; and

modifying at least one of the mean location for the first preferred area, the at least one measure of uncertainty or the angle of orientation based at least in part on the first product.

10. The method of claim 9, wherein the first preferred area is one of a plurality of preferred areas for the location,

wherein generating a covariance matrix for the first probability distribution function for the first preferred area further comprises:

generating a plurality of covariance matrices, wherein each of the plurality of covariance matrices is generated for a respective one of a plurality of probability distribution functions for one of the plurality of preferred areas, and wherein the first probability distribution function is one of the plurality of probability distribution functions,

wherein determining the first product of the covariance matrix for the second vector and the covariance matrix for the first probability distribution function further comprises;

determining products of the covariance matrix for the second vector and each of the plurality of covariance matrices, wherein the first product is one of the products, and wherein the method further comprises;

identifying one of the products of the covariance matrix corresponding to a reduction in a measure of uncertainty of a mean location of one of the plurality of preferred areas,

wherein the first preferred area is the one of the plurality of preferred areas.

11. The method of claim 6, further comprising:

receiving, from the first unmanned aerial vehicle over the network, a second sensed position associated with the request for the second delivery of the second item to the location;

determining a second level of uncertainty associated with the second sensed position;

defining a second vector based at least in part on the second sensed position and the second level of uncertainty using the at least one computer processor;

determining whether the second vector corresponds to the first preferred area for the location using the at least one computer processor;

in response to determining that the second vector does not correspond to the first preferred area,

establishing a second preferred area for the location based at least in part on the second vector and the first geolocation using the at least one computer processor; and

storing information regarding the second preferred area in association with the location in at least one data store,

wherein the information regarding the second preferred area comprises a second probability distribution function for the second preferred area.

12. The method of claim 11, further comprising:

determining at least one consideration associated with the second delivery, wherein the at least one consideration is at least one of;

a date of the second delivery;

a time of the second delivery;

a season of the second delivery;

a prevailing weather condition during the second delivery;

a legal restriction in effect during the second delivery; and

a regulatory restriction in effect during the second delivery,

wherein the information regarding the second preferred area comprises an association between the second preferred area and the at least one consideration.

13. The method of claim 6, further comprising:

receiving, from the first unmanned aerial vehicle over the network, a second sensed position associated with the request for the second delivery of the second item to the location;

determining a second level of uncertainty associated with the second sensed position;

defining a second vector based at least in part on the second sensed position and the second level of uncertainty using the at least one computer processor;

determining whether the second vector corresponds to the first preferred area for the location using the at least one computer processor;

in response to determining that the second vector does not correspond to the first preferred area,

disregarding the second sensed position as an outlier with respect to the first preferred area.

14. The method of claim 6, further comprising:

determining information regarding at least a portion of a surface of the first preferred area, wherein the information comprises at least one latitude, at least one longitude and at least one altitude of the surface,

wherein the information comprising the first instruction further comprises the information regarding at least the portion of the surface of the first preferred area.

15. The method of claim 14, wherein determining the information regarding at least the portion of the surface of the preferred area comprises:

identifying at least one surface feature associated with the first preferred area; and

determining that the first preferred area comprises a delivery point for the second delivery based at least in part on the at least one surface feature; and

wherein the information comprising the first instruction further comprises a second instruction to deposit the second item at the delivery point, and

wherein the at least one surface feature comprises at least one of a portion of a ramp;

a curb;

a road;

a driveway;

a walkway;

a sloped surface;

or a substantially flat surface.

16. The method of claim 5, wherein identifying the first sensed position associated with the first delivery comprises:

receiving information regarding the first sensed position over a network, wherein the information is received from at least one of;

a handheld device;

a ground-based vehicle;

or

an aerial vehicle, and

wherein the first sensed position comprises a latitude, a longitude and an altitude associated with the location.

17. The method of claim 5, wherein identifying the first sensed position associated with the first delivery comprises:

identifying a plurality of sensed positions associated with prior deliveries of items to the location using the at least one computer processor, wherein the first sensed position is one of the plurality of sensed positions, and wherein the first delivery is one of the plurality of prior deliveries; and

determining levels of uncertainty associated with at least some of the sensed positions using the at least one computer processor, wherein the vector is defined based at least in part on the at least some of the sensed positions and the levels of uncertainty.

18. A computer-implemented method comprising:

receiving a first geoscan from a first unmanned aerial vehicle over a network, wherein the first geoscan is received from the first unmanned aerial vehicle during a first delivery of at least a first item to a location by the first unmanned aerial vehicle;

defining a location hypothesis by at least one computer processor, wherein the location hypothesis is defined based at least in part on the first geoscan, and wherein the location hypothesis comprises a mean location, a major axis and a minor axis;

receiving a request for a second delivery of at least a second item to the location over the network;

transmitting information regarding the second delivery to a second unmanned aerial vehicle over the network, wherein the information regarding the second delivery comprises at least a first instruction to travel to the location with the second item and a second instruction to deposit the second item on a surface within the location hypothesis;

receiving a second geoscan from the second unmanned aerial vehicle over the network, wherein the second geoscan is received from the second unmanned aerial vehicle during the second delivery; and

refining the location hypothesis by the at least one computer processor, wherein the location hypothesis is refined based at least in part on the second geoscan,

wherein refining the location hypothesis comprises at least one of;

relocating the mean location;

modifying the major axis;

or

modifying the minor axis.

19. The computer-implemented method of claim 18, wherein the first geoscan is received from a first position sensor associated with the first unmanned aerial vehicle,

wherein defining the location hypothesis comprises:

determining a first level of uncertainty associated with the first position sensor or the first geoscan; and

selecting at least one of the major axis or the minor axis based at least in part on the first level of uncertainty,

wherein the second geoscan is received from a second position sensor associated with the second unmanned aerial vehicle, and

wherein refining the location hypothesis comprises;

determining a second level of uncertainty associated with the second position sensor or the second geoscan; and

modifying at least one of the major axis or the minor axis based at least in part on the second level of uncertainty.

20. The computer-implemented method of claim 18, wherein receiving the first geoscan from the first unmanned aerial vehicles over the network comprises:

receiving geoscans from each of a plurality of unmanned aerial vehicles over the network, wherein the geoscans are received from the plurality of unmanned aerial vehicles during deliveries of at least one item to the location by the plurality of unmanned aerial vehicles;

defining a cluster of at least some of the geoscans, and

wherein defining the location hypothesis comprises;

selecting at least one of the mean location, the major axis or the minor axis based at least in part on the cluster of the at least some of the geoscans.