Methods and systems for determining a cyclical fleet plan satisfying a recurring set of coverage requirements

• US 8,880,326 B1
• Filed: 02/20/2013
• Issued: 11/04/2014
• Est. Priority Date: 02/20/2013
• Status: Expired due to Fees

• Current Assignee: Loon, LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Bonawitz, Keith Allen, Piponi, Dan, Treuille, Adrien, Rhodes, Bradley James
• Primary Examiner(s): MARC-COLEMAN, MARTHE Y
• Application Number:
  US13/771,361
• Time in Patent Office: 622 Days
• Field of Search: 701/120, 701/13, 701/3, 701/4, 455/343.1, 455/78, 320134-136
• US Class Current: 701/120
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem
• CPC Class Codes: G06Q 50/40 Business processes related to the transportation industry shipping G06Q10/083
• CPC Class Codes: G08G 5/00 Traffic control systems for aircraft , e.g. air-traffic control [ATC]
• CPC Class Codes: G08G 5/0034 Assembly of a flight plan
• CPC Class Codes: G08G 9/00 Traffic control systems for craft where the kind of craft is irrelevant or unspecified

Abstract

Methods and systems for determining a cyclical pattern of trajectories for a fleet of vehicles are provided. In one example, a method comprises receiving a sequence of coverage requirements for a region and an associated period of time. For each of one or more phases of the period of time, possible routes that a vehicle located at one or more respective landmarks at a beginning of the phase could follow to reach one or more additional landmarks by an end of the phase are determined. Further, a cyclical pattern of trajectories for vehicles of a fleet of vehicles that minimizes a difference between a distribution of the fleet at a beginning of the period of time and a distribution of the fleet at an end of the period of time is determined.

Claims

1. A method comprising:

receiving a sequence of coverage requirements for a region and an associated period of time, wherein the region is characterized by a plurality of landmarks and the period of time is divided into a plurality of phases, and wherein individual coverage requirements of the sequence of coverage requirements are indicative of a desired number of vehicles of a fleet of vehicles for one or more of the plurality of landmarks at an end of a given phase of the plurality of phases;

determining, by a processor, for each of one or more phases of the plurality of phases, possible routes that a vehicle of the fleet of vehicles located at one or more respective landmarks of the plurality of landmarks at a beginning of the phase could follow to reach one or more additional landmarks of the plurality of landmarks by an end of the phase; and

based on the sequence of coverage requirements and the determined possible routes, determining, by the processor, a cyclical pattern of trajectories for vehicles of the fleet of vehicles that minimizes a difference between a distribution of vehicles in the fleet of vehicles at a beginning of the period of time and a distribution of vehicles in the fleet of vehicles at an end of the period of time.

2. The method of claim 1, wherein vehicles of the fleet of vehicles include a balloon within a data network that is operable to provide data communication via optical or radio-frequency (RF) links.

3. The method of claim 2, further comprising determining the possible routes based on one or more estimated winds at one or more altitudes.

4. The method of claim 1, wherein the cyclical pattern of trajectories indicates which route of the determined possible routes for a given vehicle starting at an individual landmark of the plurality of landmarks to follow during a given respective phase.

5. The method of claim 1, further comprising determining the cyclical pattern of trajectories by minimizing a linear objective function, wherein the linear objective function includes a deficit term that is indicative of a number of vehicles by which one or more of the coverage requirements are under-satisfied.

6. The method of claim 1, further comprising transmitting, using one or more optical or radio-frequency (RF) links, instructions to the fleet of vehicles to cause the fleet of vehicles to follow the cyclical pattern of trajectories.

7. The method of claim 1, wherein determining, for each of the one or more phases, the possible routes that a vehicle located at the one or more respective landmarks could follow comprises:

determining, for each of the one or more phases and each of the one or more respective landmarks of the plurality of landmarks, a minimum distance from each additional landmark of the plurality of landmarks that a vehicle starting from the respective landmark could reach during the phase; and

determining the possible routes for the phase and the respective landmark based on a comparison between minimum distances associated with the additional landmarks and a threshold distance.

8. The method of claim 1, wherein determining, for each of the one or more phases, the possible routes that a vehicle located at the one or more respective landmarks could follow comprises:

determining, for each of the one or more phases and each of the one or more respective landmarks of the plurality of landmarks, confidence measures that are indicative of whether a vehicle starting from the respective landmark could reach each additional landmark of the plurality of landmarks during the phase; and

determining the possible routes for the phase and the respective landmark based on a comparison between confidence measures associated with the additional landmarks and a confidence threshold.

9. The method of claim 1, wherein determining, for each of the one or more phases, the possible routes that a vehicle located at the one or more respective landmarks could follow comprises:

determining, for each of the one or more phases and each of the one or more respective landmarks of the plurality of landmarks, cost values associated with a vehicle traveling to each additional landmark of the plurality of landmarks during the phase; and

determining the possible routes for the phase and the respective landmark based on a comparison between cost values associated with the additional landmarks and a cost threshold.

10. The method of claim 1, wherein determining the cyclical pattern of trajectories for vehicles of the fleet of vehicles further comprises determining an initial distribution for vehicles in the fleet of vehicles at the beginning of the period of time.

11. The method of claim 10, further comprising:

determining a current distribution of vehicles of the fleet of vehicles at a current time period prior to the period of time; and

determining trajectories for vehicles of the fleet of vehicles to follow between the current time and the period of time to cause the vehicles of the fleet of vehicles to be arranged in the initial distribution at the beginning of the period of time.

15. The non-transitory computer-readable storage medium of claim 10, wherein the cyclical pattern of trajectories indicates which route of the determined possible routes for a given vehicle starting at an individual landmark of the plurality of landmarks to follow during a given respective phase.

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

receiving a sequence of coverage requirements for a region and an associated period of time, wherein the region is characterized by a plurality of landmarks and the period of time is divided into a plurality of phases, and wherein individual coverage requirements of the sequence of coverage requirements are indicative of a desired number of vehicles of a fleet of vehicles for one or more of the plurality of landmarks at an end of a given phase of the plurality of phases;

determining for each of one or more phases of the plurality of phases possible routes that a vehicle of the fleet of vehicles located at one or more respective landmarks of the plurality of landmarks at a beginning of the phase could follow to reach one or more additional landmarks of the plurality of landmarks by an end of the phase; and

based on the sequence of coverage requirements and the determined possible routes, determining a cyclical pattern of trajectories for vehicles of the fleet of vehicles that minimizes a difference between a distribution of vehicles in the fleet of vehicles at a beginning of the period of time and a distribution of vehicles in the fleet of vehicles at an end of the period of time.

13. The non-transitory computer-readable storage medium of claim 12, wherein vehicles of the fleet of vehicles include a balloon within a data network that is operable to provide data communication via optical or radio-frequency (RF) links.

14. The non-transitory computer-readable storage medium of claim 13, wherein the functions further comprise determining the possible routes based on one or more estimated winds at one or more altitudes.

16. A system, comprising:

at least one processor;

data storage comprising program instructions executable by the at least one processor to cause the system to perform functions comprising;

receiving a sequence of coverage requirements for a region and an associated period of time, wherein the region is characterized by a plurality of landmarks and the period of time is divided into a plurality of phases, and wherein individual coverage requirements of the sequence of coverage requirements are indicative of a desired number of vehicles of a fleet of vehicles for one or more of the plurality of landmarks at an end of a given phase of the plurality of phases;

determining for each of one or more phases of the plurality of phases possible routes that a vehicle of the fleet of vehicles located at one or more respective landmarks of the plurality of landmarks at a beginning of the phase could follow to reach one or more additional landmark of the plurality of landmarks by an end of the phase; and

based on the sequence of coverage requirements and the determined possible routes, determining a cyclical pattern of trajectories for vehicles of the fleet of vehicles that minimizes a difference between a distribution of vehicles in the fleet of vehicles at a beginning of the period of time and a distribution of vehicles in the fleet of vehicles at an end of the period of time.

17. The system of claim 16, wherein vehicles of the fleet of vehicles include a balloon within a data network that is operable to provide data communication via optical or radio-frequency (RF) links.

18. The system of claim 17, wherein the functions further comprise determining the possible routes based on one or more estimated winds at one or more altitudes.

19. The system of claim 16, wherein the cyclical pattern of trajectories indicates which route of the determined possible routes for a given vehicle starting at an individual landmark of the plurality of landmarks to follow during a given respective phase.

20. The system of claim 16, wherein the functions further comprise instructing the fleet of vehicles to follow the cyclical pattern of trajectories.