Route planning for multi-unmanned aerial vehicle-based package delivery

• US 10,170,006 B2
• Filed: 09/27/2016
• Issued: 01/01/2019
• Est. Priority Date: 09/27/2016
• Status: Active Grant

• Current Assignee: Maplebear Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Kline, Eric V., Rakshit, Sarbajit K.
• Primary Examiner(s): Tissot, Adam D
• Application Number:
  US15/277,078
• Publication Number:
  US 20180090014A1
• Time in Patent Office: 826 Days
• Field of Search: None
• CPC Class Codes: B64U 10/13 Flying platforms
• CPC Class Codes: B64U 2101/64 for parcel delivery or retrieval
• CPC Class Codes: G05D 1/102 specially adapted for vertical take-off of aircraft
• CPC Class Codes: G05D 1/104 involving a plurality of aircrafts, e.g. formation flying traffic control systems for aircraft G08G5/00
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem
• CPC Class Codes: G06Q 10/06311 Scheduling, planning or task assignment for a person or group
• CPC Class Codes: G06Q 10/06312 Adjustment or analysis of established resource schedule, e.g. resource or task levelling, or dynamic rescheduling
• CPC Class Codes: G06Q 10/083 Shipping
• CPC Class Codes: G06Q 10/08355 Routing methods
• CPC Class Codes: G08G 5/0013 with a ground station
• CPC Class Codes: G08G 5/0026 located on the ground
• CPC Class Codes: G08G 5/0034 Assembly of a flight plan
• CPC Class Codes: G08G 5/0039 Modification of a flight plan
• CPC Class Codes: G08G 5/0043 Traffic management of multiple aircrafts from the ground G08G5/003 takes precedence; data processing specially designed for resource management, e.g. scheduling or allocating time, human or machine resources G06Q10/06
• CPC Class Codes: G08G 5/0069 specially adapted for an unmanned aircraft
• CPC Class Codes: G08G 5/0091 for monitoring atmospheric conditions radar or analogous systems specially adapted for meteorological use G01S13/95; meteorology G01W

Abstract

An aspect includes receiving data for each of a plurality of unmanned aerial vehicles (UAVs) that includes a current location and final destination of each UAV. An aspect also includes calculating permutations of travel routes for each of the UAVs, which permutations are calculated as a function of the current locations of the UAVs and final destinations of each UAV. An aspect also includes applying a selected variable to the calculated permutations to produce proposed travel routes for the UAVs. An aspect further includes generating a routing plan from the proposed travel routes.

Claims

1. A method, comprising:

receiving, at a computer processor, data for each of a plurality of unmanned aerial vehicles (UAVs), the data including a UAV identifier, current geographic location, and final destination of each UAV;

calculating a plurality of permutations of travel routes for each of the UAVs, the proposed travel routes calculated as a function of the current geographic location of each of the plurality of UAVs and the final destinations of the plurality of UAVs;

applying a selected variable to the plurality of calculated permutations to produce proposed travel routes for the plurality of UAVs, wherein the selected variable is configured to minimize an idle time for the plurality of UAVs, wherein the idle time is time that each of the plurality of UAVs are not actively engaged in a package delivery or pick-up service; and

generating a routing plan from the proposed travel routes, wherein at least one of the proposed travel routes includes an interchange location at which a first UAV of the plurality of UAVs exchanges a package with a second UAV of the plurality of UAVs.

2. The method of claim 1, further comprising transmitting instructions to the plurality of UAVs, the instructions conveying routing information corresponding to the routing plan, wherein each of the instructions is addressed to a corresponding UAV based on the UAV identifier.

3. The method of claim 1, further comprising:

monitoring deployment data associated with the plurality of UAVs;

periodically receiving current location data from the plurality of UAVs; and

dynamically reconfiguring the routing plan based on an increase or decrease in an estimated aggregate idle time.

4. The method of claim 1, wherein the plurality of UAVs spans multiple network carriers, and the data includes a carrier identifier.

5. The method of claim 1, wherein at least one of the plurality of UAVs is out of network with respect to others of the plurality of UAVs, the others of the plurality of UAVs comprising in-network UAVs, the method further comprising:

receiving a mode of pick up request from a user of the out of network UAV;

receiving an identifier of the out of network UAV;

upon determining a package subject to a transaction by the user of the out of network UAV is available for delivery;

transmitting a schedule delivery message to the user, the schedule delivery message including a package drop off location and date; and

transmitting a routing message to one of the in-network UAVs, the routing message including the identifier of the out of network UAV and the drop off location.

6. The method of claim 5, further comprising:

transmitting authentication data to the in-network UAV, the authentication data configured to validate the out-of-network UAV prior to hand off of the package.

7. The method of claim 1, wherein the interchange locations include at least one of a rooftop and in-flight transfer location.

8. The method of claim 1, wherein the variable is at least one of minimized idle time, package delivery commitment time, perishability of the package, and available power reserve of a UAV.

9. A system, comprising:

a memory having computer readable instructions; and

a processing unit for executing the computer readable instructions, the computer readable instructions including;

receiving data for each of a plurality of unmanned aerial vehicles (UAVs), the data including a UAV identifier, current geographic location, and final destination of each UAV;

calculating a plurality of permutations of travel routes for each of the UAVs, the proposed travel routes calculated as a function of the current geographic location of each of the plurality of UAVs and the final destinations of the plurality of UAVs;

applying a selected variable to the plurality of calculated permutations to produce proposed travel routes for the plurality of UAVs, wherein the selected variable is configured to minimize an idle time for the plurality of UAVs, wherein the idle time is time that each of the plurality of UAVs are not actively engaged in a package delivery or pick-up service; and

generating a routing plan from the proposed travel routes, wherein at least one of the proposed travel routes includes an interchange location at which a first UAV of the plurality of UAVs exchanges a package with a second UAV of the plurality of UAVs.

10. The system of claim 9, wherein the computer readable instructions further comprise transmitting instructions to the plurality of UAVs, the instructions conveying routing information corresponding to the routing plan, wherein each of the electronic instructions is addressed to a corresponding UAV based on the UAV identifier.

11. The system of claim 9, wherein the computer readable instructions further comprise:

monitoring deployment data associated with the plurality of UAVs;

periodically receiving current location data from the plurality of UAVs; and

dynamically reconfiguring the routing plan based on an increase or decrease in an estimated aggregate idle time.

12. The system of claim 9, wherein the plurality of UAVs spans multiple network carriers, and the data includes a carrier identifier.

13. The system of claim 9, wherein at least one of the plurality of UAVs is out of network with respect to others of the plurality of UAVs, the others of the plurality of UAVs comprising in-network UAVs, the computer readable instructions further comprising:

receiving a mode of pick up request from a user of the out of network UAV;

receiving an identifier of the out of network UAV;

upon determining a package subject to a transaction by the user of the out of network UAV is available for delivery;

transmitting a schedule delivery message to the user, the schedule delivery message including a package drop off location and date; and

transmitting a routing message to one of the in-network UAVs, the routing message including the identifier of the out of network UAV and the drop off location.

14. The system of claim 13, wherein the computer readable instructions further comprise:

transmitting authentication data to the in-network UAV, the authentication data configured to validate the out-of-network UAV prior to hand off of the package.

15. A computer program product comprising a computer readable storage medium having program instructions embodied therewith, wherein the computer readable storage medium is not a transitory signal per se, the program instructions executable by a computer processor to cause the computer processor to perform a method comprising:

receiving data for each of a plurality of unmanned aerial vehicles (UAVs), the data including a UAV identifier, current geographic location, and final destination of each UAV;

calculating a plurality of permutations of travel routes for each of the UAVs, the proposed travel routes calculated as a function of the current geographic location of each of the plurality of UAVs and the final destinations of the plurality of UAVs;

applying a selected variable to the calculated a-plurality of permutations to produce proposed travel routes for the plurality of UAVs, wherein the selected variable is configured to minimize an idle time for the plurality of UAVs, wherein the idle time is time that each of the plurality of UAVs are not actively engaged in a package delivery or pick-up service; and

generating a routing plan from the proposed travel routes, wherein at least one of the proposed travel routes includes an interchange location at which a first UAV of the plurality of UAVs exchanges a package with a second UAV of the plurality of UAVs.

16. The computer program product of claim 15, wherein the program instructions further comprise transmitting instructions to the plurality of UAVs, the instructions conveying routing information corresponding to the routing plan, wherein each of the electronic instructions is addressed to a corresponding UAV based on the UAV identifier.