Navigable path networks for autonomous vehicles

• US 10,248,120 B1
• Filed: 09/16/2016
• Issued: 04/02/2019
• 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:
  US15/268,202
• Time in Patent Office: 928 Days
• Field of Search: 701 22
• 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 herein are defined based on attributes of tasks to be performed by autonomous vehicles traveling thereon, based on 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 computer-implemented method comprising:

receiving, over a communications network, an order for a purchase of an item from a customer, wherein the order specifies a destination for a delivery of the item;

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 and the mass of the item;

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

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

receiving, over the communications network, third information captured by at least one sensor provided on the selected autonomous vehicle while the selected autonomous vehicle is traveling on at least one of the first path or the second path,

wherein the third information comprises at least one of a course, a speed, a position or an altitude of the selected autonomous vehicle.

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

a frame having a height, a width and a length;

an electric motor; and

a storage compartment having a predetermined carrying capacity, and

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

the width of the frame of the one of the autonomous vehicles;

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

or

the predetermined carrying capacity of the one of the autonomous vehicles.

3. The computer-implemented method of claim 2, wherein the at least one sensor provided on the selected autonomous vehicle further comprises an imaging device, and

wherein the method further comprises:

receiving, over the communications network, imaging data captured by the imaging device while traveling from the facility to the destination along the optimal path;

identifying at least one proposed path within the environment based at least in part on the imaging data, wherein the at least one proposed 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 return route for the selected autonomous vehicle from the destination to the facility, wherein the return route comprises the at least one proposed 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 at least one proposed path at a third speed.

4. The computer-implemented method of claim 1, wherein determining the optimal route for the selected autonomous vehicle from the facility to the destination comprises:

selecting at least one of the first path or the second path according to one of Dijkstra'"'"'s Algorithm, Bellman-Ford Algorithm, Floyd-Warshall Algorithm, Johnson'"'"'s Algorithm or a hub labeling technique.

5. The computer-implemented method of claim 1, wherein determining the optimal 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 the selected autonomous vehicle 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; 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.

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;

identifying third information regarding a plurality of autonomous vehicles by the at least one computer server, wherein each of the autonomous vehicles is configured for travel on at least one of the plurality of paths;

selecting one of the autonomous vehicles for performing the mission based at least in part on the first information, the second information and the third 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, the second information and the third 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, fourth information regarding the selected route to the selected autonomous vehicle,

wherein the fourth 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 an 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 first information identifies at least one of a height of the item, a width of the item, a length of the item, a volume of the item or a mass of the item.

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 is at least a portion of a street, a road, a sidewalk, a bridge, a bicycle path, a walking path or a trail, and

wherein at least one of the plurality of paths 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 pair of wheels joined to at least one axle;

a motor disposed within the frame, wherein the motor is configured to cause the at least one pair of wheels to rotate at a speed within a predetermined speed range;

at least one storage compartment disposed within the frame, wherein the at least one storage compartment comprises at least one door pivotably joined to an outer surface of the frame by at least one hinge, and wherein the at least one door is configured to pivot between an open position and a closed position;

at least one power module for powering the motor;

at least one computer processor; and

at least one memory component.

11. The method of claim 10, wherein the third information identifies, for each of the plurality of autonomous vehicles, at least one of:

a height of the frame;

a width of the frame;

a length of the frame;

a number of the at least one pair of wheels;

a diameter of at least one of the at least one pair of wheels;

an estimated range;

a power rating or a speed rating of the motor;

the predetermined speed range of the motor;

or

an electric charge associated with the at least one power module, wherein the at least one power module comprises at least one battery.

12. The method of claim 10, wherein the third information identifies, for each of the plurality of autonomous vehicles, at least one of:

a depth of the at least one storage compartment;

a width of the at least one storage compartment;

a length of the at least one storage compartment;

a volume of the at least one storage compartment;

or

a weight capacity of the at least one storage compartment.

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 fifth 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 fifth 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 fifth 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, fifth information captured by the selected autonomous vehicle using at least one sensor, wherein the fifth 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 fifth 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 fifth information;

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

or

modifying a third path of the plurality of paths based at least in part on the fifth 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, fifth information captured by at least one of the plurality of autonomous vehicles using at least one sensor, wherein the fifth information is captured while the selected autonomous vehicle is traveling along the selected route; and

modifying the selected route based at least in part on the fifth 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 fifth information;

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

or

modifying a third path of the selected route based at least in part on the fifth 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 fourth 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 16, wherein at least one of the first path or the second path is selected 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 first time stamp associated with a departure of one of the autonomous vehicles from the first location;

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

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

at least one of a height, a width or a length of the one of the autonomous vehicles;

at least one of a mass or a volume of an item delivered from the first location to the second location by way of the at least one third location;

a first speed of the one of the autonomous vehicles between the first location and the at least one third location; and

a second speed of the one of the autonomous vehicles between the at least one third location and the second 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 a request for a delivery of a first item, wherein the request identifies an origin for the delivery of the first item and a destination for the delivery of the first item;

determining at least one of a mass or a volume of the first item;

identifying a point of the navigable path network corresponding to the origin;

identifying a point of the navigable path network corresponding to the destination;

selecting a route from the point of the navigable path network corresponding to the origin to the point of the navigable path network corresponding to the destination, wherein the selected route comprises at least one path of the navigable path network;

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

transmitting, over a communications network, a plurality of instructions for delivering the first item from the origin to the destination to the selected 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, wherein the plurality of instructions further comprises a second instruction to capture information by at least one sensor while the selected autonomous vehicle is en route from the origin to the destination on the at least one path, and

wherein the method further comprises:

receiving, over the communications network, the information from the selected autonomous vehicle; and

revising the navigable path network associated with the area based at least in part on the information received from the selected autonomous vehicle, wherein revising the navigable path network comprises at least one of;

adding a first path extending between two of the plurality of points to the navigable path network;

removing a second path from the navigable path network;

or

revising a third path of the navigable path network.

20. The method of claim 18, wherein each of the plurality of autonomous vehicles comprises:

a frame;

at least one pair of wheels;

a motor disposed within the frame, wherein the motor is configured to cause the at least one pair of wheels to rotate at a speed within a predetermined speed range;

at least one storage compartment disposed within the frame, wherein the at least one storage compartment comprises at least one door pivotably joined to an outer surface of the frame by at least one hinge, and wherein the at least one door is configured to pivot between an open position and a closed position;

at least one power module for powering the motor;

at least one computer processor; and

at least one memory component, and

wherein the route is selected based at least in part on at least one of;

a height of the frame;

a width of the frame;

a length of the frame;

a number of the at least one pair of wheels;

a diameter of at least one of the at least one pair of wheels;

an estimated range;

a power rating of the motor;

the predetermined speed range of the motor;

or

an electric charge associated with the at least one power module, wherein the at least one power module comprises at least one battery.