Navigable path networks for autonomous vehicles

• US 10,698,409 B1
• Filed: 03/27/2019
• Issued: 06/30/2020
• Est. Priority Date: 09/16/2016
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Siegel, Hilliard Bruce, Mishra, Pragyana K.
• Primary Examiner(s): Marc, McDieunel
• Application Number:
  US16/367,180
• Time in Patent Office: 461 Days
• CPC Class Codes: G01C 21/3407 specially adapted for specific applications
• CPC Class Codes: G01C 21/3602 Input other than that of destination using image analysis, e.g. detection of road signs, lanes, buildings, real preceding vehicles using a camera
• CPC Class Codes: G05D 1/0022 characterised by the communication link data switching networks in general H04L12/00
• CPC Class Codes: G05D 1/0088 characterized by the autonomous decision making process, e.g. artificial intelligence, predefined behaviours using knowledge based models G06N5/00
• CPC Class Codes: G05D 1/0223 involving speed control of the vehicle vehicle fittings for automatically controlling, i.e. preventing speed from exceeding an arbitrarily established velocity or maintaining speed at a particular velocity, as selected by the vehicle operator B60K31/00
• CPC Class Codes: G05D 1/0246 using a video camera in combination with image processing means
• CPC Class Codes: G05D 1/0274 using mapping information stored in a memory device navigation using map-matching G01C21/30
• CPC Class Codes: G05D 1/0297 by controlling means in a control room
• CPC Class Codes: G06Q 10/0834 Choice of carriers

Abstract

Navigable path networks are generated or modified based on attributes of tasks to be performed by autonomous vehicles traveling thereon, attributes of such vehicles, or attributes of the environments in which such networks are provided. The networks include traditional and non-traditional transportation features, and are defined based on prior travel within the environments, including information gathered by such vehicles during such prior travel. The autonomous vehicles are robotic, self-powered units having storage compartments for carrying objects between points of the networks. An optimal route within a navigable path network is selected based on attributes of an autonomous vehicle, a task to be performed by the autonomous vehicle, or the various paths within the network. A navigable path network is updated based on information subsequently learned regarding the environment, including information captured by autonomous vehicles traveling on paths of the network.

Claims

1. A method comprising:

receiving, over a communications network, an order for a purchase of an item from a customers,

identifying, by at least one server, a facility where the item is located;

determining, by the at least one server, a plurality of attributes of the item, wherein the plurality of attributes comprises a volume of the item and a mass of the item;

identifying, by the least one server, first information regarding a navigable path network within an environment, wherein the navigable path network comprises a plurality of points and a plurality of paths between the plurality of points, and wherein the facility corresponds to a first one of the plurality of points, and wherein the destination corresponds to a second one of the plurality of points;

identifying, by the at least one server, second information regarding a plurality of autonomous vehicles configurable for travel on at least a portion of the navigable path network;

selecting, by the at least one server, one of the plurality of autonomous vehicles for the delivery of the item from the facility to the destination, wherein the one of the autonomous vehicles is selected based at least in part on the volume of the item or the mass of the item;

determining, by the at least one server, a first route on the navigable path network for the selected autonomous vehicle, wherein the first route comprises a first path originating at the facility and a second path terminating at the destination; and

sending, over the communications network, a first plurality of computer instructions for causing the selected autonomous vehicle to travel from the facility to the destination, wherein the first plurality of computer instructions comprises at least a first computer instruction for causing the selected autonomous vehicle to travel along the first path at a first speed and at least a second computer instruction for causing the selected autonomous vehicle to travel along the second path at a second speed.

2. The method of claim 1, wherein each of the autonomous vehicles comprises:

a frame;

a motor; and

a storage compartment, and

wherein the one of the plurality of autonomous vehicles is selected based at least in part on at least one of;

at least one dimension of the frame of the one of the autonomous vehicles;

a speed rating of the motor of the one of the autonomous vehicles;

or

a carrying capacity of the storage compartment of the one of the autonomous vehicles.

3. The method of claim 2, further comprising:

receiving, over the communications network, third information captured by at least one sensor provided aboard the selected autonomous vehicle, wherein the third information was captured while the selected autonomous vehicle traveled from the facility to the destination along at least a portion of the first route;

identifying at least a third path within the environment based at least in part on the third information, wherein the third path extends from a first one of the plurality of points to a second one of the plurality of points through at least one of a park, a field, a forest, a lot or a clearing within the environment;

determining, by the at least one server, a second route for the selected autonomous vehicle from the destination to the facility, wherein the second route comprises the third path; and

sending, over the communications network, a second plurality of computer instructions for causing the selected autonomous vehicle to travel from the destination to the facility, wherein the second plurality of computer instructions comprises a third computer instruction for causing the selected autonomous vehicle to travel along the third path at a third speed.

4. The method of claim 3, further comprising:

modifying the navigable path network based at least in part on the third information, wherein modifying the navigable path network comprises at least one of;

adding the third path to the plurality of paths based at least in part on the third information;

removing a fourth path from the plurality of paths based at least in part on the third information;

or

modifying a fifth path of the plurality of paths based at least in part on the third information.

5. The method of claim 1, wherein determining the first route of the navigable path network for the selected autonomous vehicle for the delivery of the item from the facility to the destination comprises:

identifying a plurality of routes of the navigable path network from the facility to the destination for each of the plurality of autonomous vehicles for the delivery of the item from the facility to the destination, wherein each of the plurality of routes comprises at least two of the plurality of paths;

determining, for each of the plurality of routes, at least one of a cost of the delivery or a time of the delivery by each of the plurality of autonomous vehicles, wherein the one of the autonomous vehicles is selected based at least in part on the costs of the delivery by each of the plurality of autonomous vehicles or the times of the delivery by each of the autonomous vehicles; and

selecting the one of the plurality of routes having at least one of a lowest cost of the delivery or a shortest time of the delivery by the selected autonomous vehicle.

6. A method comprising:

receiving, over a communications network, first information regarding a mission requiring travel from an origin to a destination;

identifying second information regarding a plurality of paths of a navigable path network having a plurality of points and a plurality of paths by at least one computer server, wherein each of the paths extends between two of the points, wherein one of the points corresponds to the origin and wherein one of the points corresponds to the destination;

selecting one of the autonomous vehicles for performing the mission based at least in part on the first information and the second information by the at least one computer server;

selecting a route for the selected autonomous vehicle from the origin to the destination by the at least one computer server based at least in part on the first information and the second information by the at least one computer server, wherein the selected route is defined by at least some of the plurality of paths of the navigable path network extending between the origin and the destination; and

sending, over the communications network, third information regarding the selected route to the selected autonomous vehicle,

wherein the third information comprises at least one instruction for causing the selected autonomous vehicle to perform the mission while traveling along the selected route from the origin to the destination.

7. The method of claim 6, wherein the mission comprises a delivery of at least one item from the origin to the destination via the navigable path network,

wherein the first information is received over the communications network via at least one of a browser or a shopping application operating on a client computer device, and

wherein the method further comprises:

identifying third information regarding the at least one item based at least in part on the first information, wherein the third information identifies at least one of a height of the at least one item, a width of the at least one item, a length of the at least one item, a volume of the at least one item or a mass of the at least one item, and

wherein the one of the autonomous vehicles is selected based at least in part on the first information, the second information and the third information.

8. The method of claim 6, wherein the second information identifies, for each of the plurality of paths, at least one of:

a length of the path;

a width of the path;

whether the path is covered;

a surface feature of the path;

a predicted weather condition of the path;

or

a predicted traffic condition of the path.

9. The method of claim 6, wherein at least one of the plurality of paths of the navigable path network extends through at least one of a park, a field, a forest, a lot or a clearing.

10. The method of claim 6, wherein each of the autonomous vehicles comprises:

a frame;

at least one wheel;

a motor configured to cause the at least one wheel to rotate at a speed within a speed range;

at least one storage compartment associated with the frame;

at least one power module;

at least one computer processor; and

at least one memory component.

11. The method of claim 10, wherein the one of the autonomous vehicles is selected based at least in part on at least one of:

at least one dimension of the frame of the one of the autonomous vehicles;

a number of the at least one wheel of the one of the autonomous vehicles;

a diameter of at least one wheel of the one of the autonomous vehicles;

an estimated range of the one of the autonomous vehicles;

a power rating or a speed rating of the motor of the one of the autonomous vehicles;

the speed range of the motor of the one of the autonomous vehicles;

or

a capacity associated with the at least one power module of the one of the autonomous vehicles.

12. The method of claim 10, wherein the one of the autonomous vehicles is selected based at least in part on at least one of:

a depth of the at least one storage compartment of the one of the autonomous vehicles;

a width of the at least one storage compartment of the one of the autonomous vehicles;

a length of the at least one storage compartment of the one of the autonomous vehicles;

a volume of the at least one storage compartment of the one of the autonomous vehicles;

or

a weight capacity of the at least one storage compartment of the one of the autonomous vehicles.

13. The method of claim 6, further comprising:

prior to receiving the first information regarding the mission requiring travel from the origin to the destination,

identifying fourth information regarding a plurality of prior missions requiring travel between at least two of the points of the navigable path network by at least one of the plurality of autonomous vehicles, wherein the fourth information comprises, for each of the prior missions, at least one of;

a date or a time of a departure from one of the points of the navigable path network;

a date or a time of an arrival at one of the points of the navigable path network;

an elapsed time of the mission;

a volume or a payload carried during the mission;

a route traveled during the mission, wherein the route comprises at least one of the paths of the navigable path network;

a weather condition on one of the paths of the navigable path network during the mission;

or

a level of traffic on one of the paths of the navigable path network during the mission; and

defining the navigable path network for at least one of the plurality of autonomous vehicles based on the fourth information.

14. The method of claim 6, further comprising:

determining that the selected autonomous vehicle is traveling along at least one of the plurality of paths of the selected route;

receiving, over the communications network, fourth information captured by the selected autonomous vehicle using at least one sensor, wherein the fourth information is captured while the selected autonomous vehicle is traveling along the selected route; and

modifying the navigable path network based at least in part on the fourth information, wherein modifying the navigable path network comprises at least one of;

adding a first path to the plurality of paths based at least in part on the fourth information;

removing a second path from the plurality of paths based at least in part on the fourth information;

or

modifying a third path of the plurality of paths based at least in part on the fourth information.

15. The method of claim 6, further comprising:

determining that the selected autonomous vehicle is traveling along at least one of the plurality of paths of the selected route;

receiving, over the communications network, fourth information captured by at least one of the plurality of autonomous vehicles using at least one sensor, wherein the fourth information is captured while the selected autonomous vehicle is traveling along the selected route, and wherein the at least one of the plurality of autonomous vehicles does not include the selected autonomous vehicle; and

modifying the selected route based at least in part on the fourth information, wherein modifying the navigable path network comprises at least one of;

adding a first path to the selected route based at least in part on the fourth information;

removing a second path from the selected route based at least in part on the fourth information;

or

modifying a third path of the selected route based at least in part on the fourth information.

16. The method of claim 6,

wherein the selected route comprises:

a first path extending from a first point of the navigable path network corresponding to the origin to at least a second point of the navigable path network, wherein the first point corresponds to the origin; and

a second path extending from at least the second point of the navigable path network to a third point of the navigable path network, wherein the third point corresponds to the destination; and

wherein the third information comprises;

a first instruction to travel along the first path of the navigable path network on a first course and at a first speed; and

a second instruction to travel along the second path of the navigable path network on a second course and at a second speed.

17. The method of claim 6, wherein at least a portion of the selected route is determined using at least one of Dijkstra'"'"'s Algorithm, Bellman-Ford Algorithm, Floyd-Warshall Algorithm, Johnson'"'"'s Algorithm or a hub labeling technique.

18. A method comprising:

identifying information regarding a plurality of deliveries of items within an area, wherein each of the deliveries of items is from a first location to a second location by way of at least a third location using one of a plurality of autonomous vehicles, and wherein the information regarding the plurality of deliveries comprises, for each of the deliveries of items, at least one of;

a time of a departure of one of the autonomous vehicles from the first location;

a time of an arrival of the one of the autonomous vehicles at the second location;

a time of an arrival of the one of the autonomous vehicles at the at least one third location;

at least one dimension of the one of the autonomous vehicles;

or

at least one attribute of at least one item delivered from the first location to the second location by way of the at least one third location;

defining a navigable path network associated with the area based at least in part on the information regarding the plurality of deliveries, wherein the navigable path network comprises a plurality of paths and a plurality of points, wherein each of the plurality of points corresponds to a location within the area, and wherein each of the paths extends between two of the plurality of points;

receiving, over a communications network, a request for a delivery of a first item at a first time, wherein the request identifies an origin for the delivery of the first item and a destination for the delivery of the first item, and wherein each of the origin and the destination is within the area;

determining at least one attribute of the first item;

selecting a first autonomous vehicle of the plurality of autonomous vehicles for delivery of the first item along the selected route based at least in part on the at least one attribute of the first item;

determining at least one attribute of the area at the first time, wherein the at least one attribute of the area is at least one of;

a ground surface condition of at least a portion of the area at the first time;

a traffic condition in at least the portion of the area at the first time;

or

an environmental condition in at least the portion of the area at the first time;

selecting a route from a point of the navigable path network corresponding to the origin to a point of the navigable path network corresponding to the destination based at least in part on the at least one attribute of the area at the first time, wherein the selected route comprises at least a first path of the navigable path network; and

transmitting, over the communications network, a plurality of instructions for delivering at least the first item from the origin to the destination to the first autonomous vehicle, wherein the plurality of instructions comprises a first instruction to travel on at least a first course and at least a first speed on the at least one path of the navigable path network.

19. The method of claim 18, further comprising:

receiving, over the communications network, information regarding at least one attribute of the area at a second time, wherein the second time follows the first time, and wherein the information regarding the at least one attribute of the area at the second time comprises at least one of;

a ground surface condition of at least a portion of the area at the second time;

a traffic condition in at least the portion of the area at the second time;

or

an environmental condition in at least the portion of the area at the second time;

identifying a second path of the navigable path network based at least in part on the information regarding the at least one attribute of the area at the second time; and

modifying the route to include the second path.

20. The method of claim 19, wherein the information regarding the at least one attribute of the area at the second time is received from at least one of:

the first autonomous vehicle;

or

a second autonomous vehicle of the plurality of autonomous vehicles.