Drop-off location planning for delivery vehicle

Patent metadata

Field	Value
Publication number	US-10353388-B2
Application number	US-201615295995-A
Country	US
Kind code	B2
Filing date	Oct 17, 2016
Priority date	Oct 17, 2016
Publication date	Jul 16, 2019
Grant date	Jul 16, 2019

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.

First claim

What is claimed is:

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.

Assignees

• X Dev Llc

Inventors

• Schubert Martin
• Grundmann Michael
• Biffle Clifford
• Watson Philip

Classifications

• G06N7/01

  Probabilistic graphical models, e.g. probabilistic networks · CPC title

• B64U2201/20

  Remote controls · CPC title

• G01C21/20

  Instruments for performing navigational calculations (G01C21/24, G01C21/26 take precedence) · CPC title

• G01C21/005 Primary

  with correlation of navigation data from several sources, e.g. map or contour matching (G01C21/30 takes precedence) · CPC title

• G08G5/0021

  Physics · mapped topic