Determining routing points and delivery points

• US 9,743,239 B1
• Filed: 09/30/2015
• Issued: 08/22/2017
• 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:
  US14/871,080
• Time in Patent Office: 692 Days
• Field of Search: 4554561, 4554563, 455457, 4555501
• 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 method comprising:

identifying a first sensed position associated with a first delivery of a first item to a location using at least one computer processor;

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

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 the location based at least in part on the first vector and the first geolocation using the at least one computer processor;

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;

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;

identifying 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 computer device over a network.

2. The method of claim 1, further comprising:

receiving, from the computer device 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;

upon 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.

3. The method of claim 2, 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;

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.

4. The method of claim 3, 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.

5. The method of claim 2, further comprising:

upon 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.

6. The method of claim 1, wherein the information regarding the at least one of the second delivery, the second item or the location comprises at least one of:

an attribute of a person, a vehicle or a machine associated with the second delivery;

a size of the second item;

a shape of the second item;

a mass of the second item;

a volume of the second item;

a date or a time of the second delivery;

an actual or predicted weather condition at the location at the date or the time of the second delivery;

an actual or predicted traffic condition at the location at the date or the time of the second delivery;

or

a legal constraint in effect at the location at the date or the time of the second delivery.

7. The method of claim 1, further comprising:

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 structure;

a stair;

a ramp;

a curb;

a hill;

a road;

a driveway;

a walkway;

a sloped surface;

or a substantially flat surface.

8. The method of claim 1, further comprising:

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

determining that the first preferred area comprises a routing 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 proceed to the routing point in a vehicle with the second item, and

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

a stair;

a ramp;

a curb;

a hill;

a road;

a driveway;

a walkway;

a sloped surface;

or a substantially flat surface.

9. The method of claim 1, 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.

10. The method of claim 1, wherein the first preferred area comprises a delivery point for the second delivery, and

wherein the method further comprises:

selecting a routing point at the location for the second delivery using the at least one computer processor;

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

determining a first optimal path from the origin to the routing point using the at least one computer processor; and

determining a second optimal path from the routing point to the delivery point using the at least one computer processor,

wherein the information comprising the first instruction further comprises a second instruction to proceed from the origin to the routing point in a vehicle via the first optimal path, a third instruction to proceed from the routing point to the delivery point on foot and a fourth instruction to deposit the second item at the delivery point.

11. A networked computer system comprising

at least one memory component;

and

at least one computer processor,

wherein the at least one computer processor is configured to execute a plurality of computer-executable instructions for causing the networked computer system to perform a method comprising;

identifying a first sensed position of a first handheld device during a performance of a first task at a location at a first time;

determining a first level of uncertainty associated with at least one of the first handheld device at the first time or the first sensed position;

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

determining a first geolocation associated with the location;

establishing a first preferred area for the location based at least in part on the first vector and the first geolocation;

storing information regarding the first preferred area in association with the location in the at least one memory component;

receiving a request for a performance of a second task at the location at a second time;

determining information regarding at least one of the second task, the location or the second time;

identifying the first preferred area based at least in part on the information regarding the at least one of the second task, the second time or the location; and

transmitting information comprising a first instruction to proceed to the first preferred area at the second time to a second handheld device over a network.

12. The networked system of claim 11, wherein identifying the first sensed position comprises:

receiving, from the first handheld device, a first set of coordinates of the first handheld device during the performance of the first task at the location at the first time,

 

wherein the first set of coordinates corresponds to the first sensed position,

 

wherein the first vector is 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;

 

wherein establishing the first preferred area for the location based at least in part on the first vector and the first geolocation comprises;

defining the first preferred area based at least in part on the first geoscan and the first geolocation, and

 

wherein the method further comprises;

receiving, from the second handheld device over the network, a second set of coordinates of the second handheld device during the performance of the second task at the location at the second time;

determining a second level of uncertainty associated with at least one of the second handheld device at the second time or the second set of coordinates;

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

determining that the second geoscan corresponds to the first preferred area;

modifying the first preferred area based at least in part on the second geoscan; and

updating the information regarding the first preferred area in the at least one data store.

13. The networked computer system of claim 11, wherein identifying the first sensed position comprises:

receiving, from the first handheld device, a first set of coordinates of the first handheld device during the performance of the first task at the location at the first time,

 

wherein the first set of coordinates corresponds to the first sensed position,

 

wherein the first vector is 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;

 

wherein establishing the first preferred area for the location based at least in part on the first vector and the first geolocation comprises;

defining the first preferred area based at least in part on the first geoscan and the first geolocation, and

 

wherein the method further comprises;

receiving, from the second handheld device over the network, a second set of coordinates of the second handheld device during the performance of the second task at the location at a second time;

determining a second level of uncertainty associated with at least one of the second handheld device at the second time or the second set of coordinates;

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

determining that the second geoscan does not correspond to the first preferred area;

defining a second preferred area at the location based at least in part on the second geoscan and the geolocation; and

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

14. The networked computer system of claim 11, wherein the second task is a delivery of an item to the location, and

wherein the method further comprises:

identifying at least one surface feature associated with the location;

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

transmitting, to the second handheld device over the network, an instruction to deposit the item at the first region,

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

a stair;

a ramp;

a curb;

a hill;

a road;

a driveway;

a walkway;

a sloped surface;

or a substantially flat surface.

15. A non-transitory computer-readable medium having instructions stored thereon, wherein the instructions, when executed by at least one computer processor, cause the at least one computer processor to execute a method comprising:

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

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

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 the location based at least in part on the first vector and the first geolocation using the at least one computer processor;

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;

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;

identifying 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 computer device over a network.

16. The non-transitory computer-readable medium of claim 15, wherein identifying the first sensed position comprises:

receiving, from a second computer device over the network, coordinates of a first point associated with the location, wherein the level of uncertainty is determined based at least in part on the coordinates of the first point, and

wherein the method further comprises;

defining the first probability distribution function based at least in part on the coordinates of the first point and the first level of uncertainty.

17. The non-transitory computer-readable medium of claim 16, wherein identifying the first preferred area comprises:

selecting a region corresponding to the first probability distribution using the at least one computer processor, wherein the information transmitted to the first computer device identifies the selected region.

18. The non-transitory computer-readable medium of claim 16, wherein the method further comprises:

receiving, from the first computer device, coordinates of a second point associated with the location;

determining a second level of uncertainty associated with the coordinates of the second point using the at least one computer processor;

determining that the second point or the second level of uncertainty corresponds to at least a first portion of the first probability distribution function using the at least one computer processor; and

updating the first probability distribution function based at least in part on the coordinates of the second point and the second level of uncertainty using the at least one computer processor.

19. The non-transitory computer-readable medium of claim 15, wherein the method further comprises:

transmitting a second instruction to the second computer device associated with the first delivery of the first item to the location, wherein the second instruction comprises a first geocode corresponding to a geolocation associated with the location, and

wherein the first instruction comprises a second geocode corresponding to a mean of the first probability distribution function.