Methods and systems for decomposing fleet planning optimizations via spatial partitions

• US 8,874,356 B1
• Filed: 01/24/2013
• Issued: 10/28/2014
• Est. Priority Date: 01/24/2013
• Status: Active Grant

• Current Assignee: Loon, LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Bonawitz, Keith Allen
• Primary Examiner(s): Cheung, Mary
• Assistant Examiner(s): WONG, YUEN H
• Application Number:
  US13/748,708
• Time in Patent Office: 642 Days
• Field of Search: 701/120, 709/201
• US Class Current: 701/120
• 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: G08G 5/0008 with other aircraft
• CPC Class Codes: G08G 5/0013 with a ground station
• CPC Class Codes: G08G 5/0034 Assembly 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

Abstract

Example methods and systems for decomposing fleet planning optimizations via spatial partitions are described. An example method includes receiving information indicating a sequence of coverage requirements for a region over a period of time. The region is characterized by a plurality of landmarks and the period of time is divided into a plurality of phases. An individual coverage requirement indicates a desired number of vehicles of a plurality of vehicles for respective landmarks at a given phase. The method also includes dividing the region into a plurality of sub-regions, and determining sub-region fleet plans for the plurality of sub-regions based on estimates of one or more vehicles entering respective sub-regions and estimates of one or more vehicles leaving respective sub-regions. The method also includes combining the sub-region fleet plans to produce a fleet plan responsive to the sequence of coverage requirements for the region.

Claims

1. A method comprising:

receiving information from a control system indicative of a sequence of coverage requirements for a data network for a region over a 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 a given coverage requirement of the sequence of coverage requirements is indicative of a desired number of vehicles of a plurality of vehicles for respective landmarks at a given phase;

dividing the region into a plurality of sub-regions;

determining, by a processor of the control system, sub-region fleet plans for the plurality of sub-regions based on both estimates of one or more vehicles entering respective sub-regions and estimates of one or more vehicles leaving the respective sub-regions, wherein a given sub-region fleet plan of the determined sub-region fleet plans is indicative of one or more landmarks for the one or more vehicles to travel to during one or more phases of the plurality of phases, and indicates both a first number value of vehicles entering the given sub-region and a second number value of vehicles leaving the given sub-region during respective phases, and wherein the first number value of vehicles is different than the second number value of vehicles;

combining, by the processor of the control system, the determined sub-region fleet plans to produce a fleet plan responsive to the sequence of coverage requirements for the region; and

providing, by the processor of the control system, instructions to the one or more vehicles to travel according to the fleet plan.

2. The method of claim 1, further comprising:

for the plurality of sub-regions, determining for one or more respective landmarks of the plurality of landmarks estimated landmarks of the plurality of landmarks that can be reached by a vehicle starting from the one or more respective landmarks; and

based on the sequence of coverage requirements, determining which landmarks of the estimated landmarks for the vehicle to travel to during a respective phase to generate the sub-region fleet plans.

3. The method of claim 1, wherein combining the sub-region fleet plans to produce the fleet plan comprises:

for sub-region fleet plans corresponding to a first sub-region and a second sub-region of the plurality of sub-regions that are adjacent regions, at a boundary of the adjacent regions resolving a number of vehicles traversing the boundary to be a given number of vehicles that are estimated to be leaving the first sub-region at the boundary.

4. The method of claim 1, wherein a first sub-region and a second sub-region of the plurality of regions are adjacent regions, and wherein vehicles traverse from the first sub-region to the second sub-region, and wherein combining the sub-region fleet plans to produce the fleet plan responsive to the sequence of coverage requirements for the region comprises:

at a boundary of the adjacent regions, resolving a number of vehicles traversing the boundary to be a smaller of a number of vehicles leaving the first sub-region at the boundary and a number of vehicles entering the second sub-region at the boundary.

5. The method of claim 1, wherein combining the sub-region fleet plans to produce the fleet plan comprises:

providing the sub-region fleet plans to a linear solver as inputs for an initial configuration of vehicles of the plurality of vehicles; and

performing one or more iterations using the linear solver to produce the fleet plan for the region.

6. The method of claim 1, wherein the region includes Earth, and wherein dividing the region into a plurality of sub-regions comprises dividing the Earth into regions comprising continents.

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

8. The method of claim 7, further comprising:

for the plurality of sub-regions, determining for one or more respective landmarks of the plurality of landmarks estimated landmarks of the plurality of landmarks that can be reached by the balloon starting from the one or more respective landmarks and by following one or more estimated winds at one or more altitudes.

9. 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 information from a control system indicative of a sequence of coverage requirements for a data network for a region over a 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 a given coverage requirement of the sequence of coverage requirements is indicative of a desired number of vehicles of a plurality of vehicles for respective landmarks at a given phase;

dividing the region into a plurality of sub-regions;

determining sub-region fleet plans for the plurality of sub-regions based on both estimates of one or more vehicles entering respective sub-regions and estimates of one or more vehicles leaving the respective sub-regions, wherein a given sub-region fleet plan of the determined sub-region fleet plans is indicative of one or more landmarks for the one or more vehicles to travel to during one or more phases of the plurality of phases, and indicates both a first number value of vehicles entering the given sub-region and a second number value of vehicles leaving the given sub-region during respective phases, and wherein the first number value of vehicles is different than the second number value of vehicles;

combining the determined sub-region fleet plans to produce a fleet plan responsive to the sequence of coverage requirements for the region; and

providing instructions to the one or more vehicles to travel according to the fleet plan.

10. The non-transitory computer readable storage medium of claim 9, wherein the functions further comprise:

for the plurality of sub-regions, determining for one or more respective landmarks of the plurality of landmarks estimated landmarks of the plurality of landmarks that can be reached by a vehicle starting from the one or more respective landmarks; and

based on the sequence of coverage requirements, determining which landmarks of the estimated landmarks for the vehicle to travel to during a respective phase to generate the sub-region fleet plans.

11. The non-transitory computer readable storage medium of claim 9, wherein combining the sub-region fleet plans to produce the fleet plan comprises:

for sub-region fleet plans corresponding to a first sub-region and a second sub-region of the plurality of sub-regions that are adjacent regions, at a boundary of the adjacent regions resolving a number of vehicles traversing the boundary to be a given number of vehicles that are estimated to be leaving the first sub-region at the boundary.

12. The non-transitory computer readable storage medium of claim 9, wherein a first sub-region and a second sub-region of the plurality of regions are adjacent regions, and wherein vehicles traverse from the first sub-region to the second sub-region, and wherein combining the sub-region fleet plans to produce the fleet plan responsive to the sequence of coverage requirements for the region comprises:

at a boundary of the adjacent regions, resolving a number of vehicles traversing the boundary to be a smaller of a number of vehicles leaving the first sub-region at the boundary and a number of vehicles entering the second sub-region at the boundary.

13. The non-transitory computer readable storage medium of claim 9, wherein combining the sub-region fleet plans to produce the fleet plan comprises:

providing the sub-region fleet plans to a linear solver as inputs for an initial configuration of vehicles of the plurality of vehicles; and

performing one or more iterations using the linear solver to produce the fleet plan for the region.

14. The non-transitory computer readable storage medium of claim 9, wherein the region includes Earth, and wherein dividing the region into a plurality of sub-regions comprises dividing the Earth into regions comprising continents.

15. A system, comprising:

at least one processor; and

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

receiving information from a control system indicative of a sequence of coverage requirements for a data network for a region over a 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 a given coverage requirement of the sequence of coverage requirements is indicative of a desired number of vehicles of a plurality of vehicles for respective landmarks at a given phase;

dividing the region into a plurality of sub-regions;

determining sub-region fleet plans for the plurality of sub-regions based on both estimates of one or more vehicles entering respective sub-regions and estimates of one or more vehicles leaving the respective sub-regions, wherein a given sub-region fleet plan of the determined sub-region fleet plans is indicative of one or more landmarks for the one or more vehicles to travel to during one or more phases of the plurality of phases, and indicates both a first number value of vehicles entering the given sub-region and a second number value of vehicles leaving the given sub-region during respective phases, and wherein the first number value of vehicles is different than the second number value of vehicles;

combining the determined sub-region fleet plans to produce a fleet plan responsive to the sequence of coverage requirements for the region; and

providing instructions to the one or more vehicles to travel according to the fleet plan.

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

17. The system of claim 16, wherein the functions further comprise:

for the plurality of sub-regions, determining for one or more respective landmarks of the plurality of landmarks estimated landmarks of the plurality of landmarks that can be reached by the balloon starting from the one or more respective landmarks and by following one or more estimated winds at one or more altitudes.

18. The system of claim 15, wherein combining the sub-region fleet plans to produce the fleet plan comprises:

providing the sub-region fleet plans to a linear solver as inputs for an initial configuration of vehicles of the plurality of vehicles; and

performing one or more iterations using the linear solver to produce the fleet plan for the region.