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

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.

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.

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.

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.