Drop-off location planning for delivery vehicle

• US 10,353,388 B2
• Filed: 10/17/2016
• Issued: 07/16/2019
• Est. Priority Date: 10/17/2016
• Status: Active Grant

• Current Assignee: X Development LLC (Alphabet Inc.)
• Original Assignee: X Development LLC (Alphabet Inc.)
• Inventors: Schubert, Martin, Grundmann, Michael, Biffle, Clifford, Watson, Philip
• Primary Examiner(s): Shudy, Angelina
• Application Number:
  US15/295,995
• Publication Number:
  US 20180107211A1
• Time in Patent Office: 1,002 Days
• Field of Search: 701 3, 701 4, 701 23, 701425
• CPC Class Codes: B64C 39/024 of the remote controlled vehicle type, i.e. RPV
• CPC Class Codes: B64U 10/14 with four distinct rotor axes, e.g. quadcopters
• CPC Class Codes: B64U 10/25 Fixed-wing aircraft VTOL aircraft B64U10/20
• CPC Class Codes: B64U 2101/60 for transporting passengers; for transporting goods other than weapons
• CPC Class Codes: B64U 2101/64 for parcel delivery or retrieval
• CPC Class Codes: B64U 2201/20 Remote controls
• CPC Class Codes: G01C 21/005 with correlation of navigation data from several sources, e.g. map or contour matching G01C21/30 takes precedence
• CPC Class Codes: G01C 21/20 Instruments for performing navigational calculations G01C21/24, G01C21/26 take precedence
• CPC Class Codes: G05D 1/0044 by providing the operator with a computer generated representation of the environment of the vehicle, e.g. virtual reality, maps maps used for automatic navigation G05D1/0274; flight directors G01C23/005
• CPC Class Codes: G05D 1/0676 specially adapted for landing
• CPC Class Codes: G05D 1/106 Change initiated in response to external conditions, e.g. avoidance of elevated terrain or of no-fly zones
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks
• CPC Class Codes: G08G 5/0013 with a ground station
• CPC Class Codes: G08G 5/0021 located in the aircraft
• CPC Class Codes: G08G 5/0026 located on the ground
• CPC Class Codes: G08G 5/0069 specially adapted for an unmanned aircraft
• CPC Class Codes: G08G 5/025 Navigation or guidance aids radar or analogous systems specially adapted for landing purposes G01S13/913

Abstract

An example method may include receiving, from a client computing device, an indication of a target drop-off spot for an object within a first virtual model of a first region of a delivery destination. A second virtual model of a second region of the delivery destination may be determined based on sensor data received from one or more sensors on a delivery vehicle. A mapping may be determined between physical features represented in the first virtual model and physical features represented in the second virtual model to determine an overlapping region between the first and second virtual models. A position of the target drop-off spot within the second virtual model may be determined based on the overlapping region. Based on the position of the target drop-off spot within the second virtual model, the delivery vehicle may be navigated to the target drop-off spot to drop off the object.

Claims

1. A method comprising:

receiving, from a client computing device, an indication of a target drop-off spot for an object within a first virtual model of a first region of a delivery destination, the first virtual model indicating first physical features including three-dimensional relationships between objects in the first region of the delivery destination, the first virtual model being determined from multiple images captured by the client computing device and first sensor data corresponding to the multiple images;

receiving, from one or more sensors on a delivery vehicle, second sensor data indicative of a second region of the delivery destination;

determining, based on the second sensor data, a second virtual model of the second region of the delivery destination, the second virtual model indicating second physical features including three-dimensional relationships between objects in the second region of the delivery destination, the second virtual model being determined from the second sensor data captured by the delivery vehicle;

determining a mapping between one or more of the first physical features and one or more of the second physical features to determine an overlapping region between the first virtual model and the second virtual model;

based on the overlapping region, determining a position of the target drop-off spot within the second virtual model; and

based on the position of the target drop-off spot within the second virtual model, providing instructions that cause the delivery vehicle to navigate to the target drop-off spot to place the object at the target drop-off spot.

2. The method of claim 1, further comprising:

providing instruction to display, by way of a user interface of the client computing device, the first virtual model;

providing instructions to prompt, by way of the user interface, for designation of the target drop-off spot for the object within the first virtual model; and

receiving, by way of the user interface, the designation of the target drop-off spot.

3. The method of claim 1, wherein the first sensor data is received at a first time and wherein the second sensor data is received at a second time later than the first time, wherein the second sensor data is captured from the one or more sensors of the delivery vehicle in response to the delivery vehicle being within a threshold distance of the delivery destination.

4. The method of claim 1, further comprising:

providing instruction to prompt, by way of a user interface of the client computing device, for selection of the delivery destination from a plurality of candidate delivery destinations for the object; and

providing instructions to prompt, by way of the user interface, for selection of the target drop-off spot from a plurality of user-designated candidate target drop-off spots for the object within the selected delivery destination.

5. The method of claim 1, wherein determining the second virtual model comprises:

determining, based on the second sensor data, an orientation of the second virtual model within the delivery destination.

6. The method of claim 1, wherein determining the second virtual model comprises:

determining, based on the second sensor data, a first portion of the second virtual model, the first portion indicating physical features of a first sub-region of the second region of the delivery destination;

determining that a confidence level of a mapping between the physical features indicated in the first portion of the second virtual model and the first physical features is below a threshold confidence value;

in response to determining that the confidence level of the mapping is below the threshold confidence value, receiving, from the one or more sensors on the delivery vehicle, additional sensor data indicative of a second sub-region of the second region of the delivery destination; and

determining, based on the additional sensor data, a second portion of the second virtual model, the second portion indicating physical features of the second sub-region of the second region of the delivery destination.

7. The method of claim 6, wherein determining a mapping between one or more of the first physical features and one or more of the second physical features comprises:

aligning the first virtual model with the second virtual model based on location of common objects identified in the first virtual model and the second virtual model;

determining a mapping between one or more of the first physical features and one or more of the physical features of the second sub-region to determine the overlapping region between the first virtual model and the second portion of the second virtual model; and

determining that a confidence level of the mapping between the one or more of the first physical features and the one or more of the physical features of the second sub-region is greater than the threshold confidence value.

8. The method of claim 1, wherein:

determining the mapping comprises;

determining a geometric transformation between representations of the one or more of the first physical features and representations of the one or more of the second physical features; and

determining a position of the target drop-off spot within the second virtual model comprises;

applying the determined geometric transformation to coordinates of the target drop-off spot within the first virtual model to determine coordinates of the target drop-off spot within the second virtual model.

9. The method of claim 1, wherein the overlapping region between the first virtual model and the second virtual model comprises a geometric intersection between a portion of the second virtual model and a corresponding portion of the first virtual model.

10. The method of claim 1, wherein the first virtual model is associated with global positioning system (GPS) coordinates, the method further comprising:

providing instructions to transport the object to the delivery destination by navigating the delivery vehicle from a facility storing the object to the delivery destination based on the GPS coordinates; and

after the delivery vehicle navigates to the delivery destination, receiving the second sensor data indicative of the second region of the delivery destination to locate the target drop-off spot within the delivery destination.

11. The method of claim 1, wherein the overlapping region does not contain the target drop-off spot, and wherein determining the position of the target drop-off spot within the second virtual model comprises:

based on the overlapping region, determining a path through which to move the delivery vehicle to collect additional sensor data indicative of a region of the delivery destination containing the target drop-off spot; and

providing instructions to navigate the delivery vehicle along the determined path and collect the additional sensor data while navigating along the determined path.

12. The method of claim 11, wherein determining the position of the target drop-off spot within the second virtual model additionally comprises:

updating the second virtual model based on the additional sensor data to represent the target drop-off spot and physical features of the region of the delivery destination containing the target drop-off spot.

13. The method of claim 1, further comprising:

receiving, from the one or more sensors on the delivery vehicle, image data representing the object disposed at the target drop-off spot; and

transmitting, to the client computing device, a delivery confirmation including the image data representing the object disposed at the target drop-off spot.

14. The system of claim 13, wherein the one or more sensors comprise one or more of (i) global positioning system (GPS) module, (ii) a camera, or (iii) a magnetometer.

15. The method of claim 1, wherein the delivery vehicle is an autonomous delivery vehicle that navigates itself to the target drop-off spot in response to receiving the instructions.

16. The method of claim 1, wherein:

the first virtual model comprises a first three-dimensional model that indicates the three-dimensional relationships between the objects in the first region of the delivery destination;

the second virtual model comprises a second three-dimensional model that indicates the three-dimensional relationships between the objects in the second region of the delivery destination; and

the first three-dimensional model and the second three-dimensional model each comprise one of (i) a point cloud, (ii) a wireframe model, (iii) a surface model, or (iv) a solid model.

17. The method of claim 1, further comprising determining the first virtual model from the multiple images and the first sensor data, including generating, in the first virtual model, a virtual representation of objects in the first region of the delivery destination using images of the objects and motion sensor data for each image of the object, the motion sensor data comprising at least one of global positioning system (GPS) data obtained from a GPS sensor of the client computing device when the image was captured or accelerometer data received from an accelerometer of the client computing device when the image was captured;

wherein generating the second virtual model comprises generating, in the second virtual model, a virtual representation of objects in the second region of the delivery destination using images of the objects captured by the delivery vehicle and motion sensor data for each image of the object, the motion sensor data comprising at least one of GPS data obtained from a GPS sensor of the delivery vehicle when the image was captured or accelerometer data received from an accelerometer of the delivery vehicle when the image was captured.

18. The method of claim 1, further comprising:

receiving, from the client computing device, global positioning system (GPS) coordinates of the client device;

determining, based on the GPS coordinates, second instructions that cause the delivery vehicle to navigate to within a threshold distance of the delivery destination;

providing the second instructions to the delivery vehicle; and

determining that the delivery vehicle is within the threshold distance of the delivery destination, wherein the second virtual model is determined in response to determining that the delivery vehicle is within the threshold distance of the delivery destination.

19. A system comprising:

a delivery vehicle;

one or more sensors connected to the delivery vehicle; and

a control system configured to;

receive, from a client computing device, an indication of a target drop-off spot for an object within a first virtual model of a first region of a delivery destination, the first virtual model indicating first physical features including three-dimensional relationships between objects in the first region of the delivery destination, the first virtual model being determined from multiple images captured by the client computing device and first sensor data corresponding to the multiple images;

receive, from the one or more sensors, second sensor data indicative of a second region of the delivery destination;

determine, based on the second sensor data, a second virtual model of the second region of the delivery destination, the second virtual model indicating second physical features including three-dimensional relationships between objects in the second region of the delivery destination, the second virtual model being determined from the second sensor data captured by the delivery vehicle;

determine a mapping between one or more of the first physical features and one or more of the second physical features to determine an overlapping region between the first virtual model and the second virtual model;

based on the overlapping region, determine a position of the target drop-off spot within the second virtual model; and

based on the position of the target drop-off spot within the second virtual model, provide instructions that cause the delivery vehicle to navigate to the target drop-off spot to place the object at the target drop-off spot.

20. A non-transitory computer readable storage medium having stored thereon instructions that, when executed by a computing device, cause the computing device to perform operations comprising:

receiving, from a client computing device, an indication of a target drop-off spot for an object within a first virtual model of a first region of a delivery destination, the first virtual model indicating first physical features including three-dimensional relationships between objects in the first region of the delivery destination, the first virtual model being determined from multiple images captured by the client computing device and first sensor data corresponding to the multiple images;

receiving, from one or more sensors on a delivery vehicle, second sensor data indicative of a second region of the delivery destination;

determining, based on the second sensor data, a second virtual model of the second region of the delivery destination, the second virtual model indicating second physical features including three-dimensional relationships between objects in the second region of the delivery destination, the second virtual model being determined from the second sensor data captured by the delivery vehicle;

determining a mapping between one or more of the first physical features and one or more of the second physical features to determine an overlapping region between the first virtual model and the second virtual model;

based on the overlapping region, determining a position of the target drop-off spot within the second virtual model; and

based on the position of the target drop-off spot within the second virtual model, providing instructions that cause the delivery vehicle to navigate to the target drop-off spot to place the object at the target drop-off spot.