Drop-off Location Planning for Delivery Vehicle

• US 20180107211A1
• Filed: 10/17/2016
• Published: 04/19/2018
• 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
• Granted Patent: US 10,353,388 B2
• Time in Patent Office: Days
• 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 representing first physical features of the first region of the delivery destination;

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

determining, based on the sensor data, a second virtual model of the second region of the delivery destination, the second virtual model representing second physical features of the second region on the delivery destination;

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 to navigate the delivery vehicle to the target drop-off spot to place the object at the target drop-off spot.

2. The method of claim 1, wherein the sensor data is a second sensor data, the method further comprising:

receiving, from one or more sensors on the client computing device, first sensor data indicative of the first region of the delivery destination; and

determining, based on the first sensor data, the first virtual model.

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

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

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

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

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

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

determining, based on the sensor data, a first portion of the second virtual model, the first portion representing 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 represented 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 representing physical features of the second sub-region of the second region of the delivery destination.

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

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.

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

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

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

12. 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 sensor data indicative of the second region of the delivery destination to locate the target drop-off spot within the delivery destination.

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

14. The method of claim 13, 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.

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

17. The system of claim 15, wherein the control system comprises a computing device on the delivery vehicle, and wherein the control system is configured to receive the indication of the target drop-off spot from a server device.

18. The system of claim 15, wherein the control system comprises a server device remote to the delivery vehicle, and wherein the control system is configured to receive the indication of the target drop-off spot from a client computing device.

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

16. A system comprising:

a delivery vehicle;

one or more sensors connected to the delivery vehicle; and

a control system configured to;

receive 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 representing first physical features of the first region of the delivery destination;

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

determine, based on the sensor data, a second virtual model of the second region of the delivery destination, the second virtual model representing second physical features of the second region on the delivery destination;

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 to navigate the delivery vehicle 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 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 representing first physical features of the first region of the delivery destination;

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

determining, based on the sensor data, a second virtual model of the second region of the delivery destination, the second virtual model representing second physical features of the second region on the delivery destination;

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 to navigate the delivery vehicle to the target drop-off spot to place the object at the target drop-off spot.