Methods and systems for performing fleet planning based on coarse estimates of regions

• US 9,424,752 B1
• Filed: 12/26/2012
• Issued: 08/23/2016
• Est. Priority Date: 12/26/2012
• Status: Active Grant

• Current Assignee: Loon, LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Bonawitz, Keith
• Primary Examiner(s): Olszewski, John R
• Assistant Examiner(s): CASS, JEAN PAUL
• Application Number:
  US13/727,071
• Time in Patent Office: 1,336 Days
• US Class Current: 1/1
• CPC Class Codes: B64C 39/024 of the remote controlled vehicle type, i.e. RPV
• CPC Class Codes: B64U 10/30 Lighter-than-air aircraft, e.g. aerostatic aircraft
• CPC Class Codes: G01C 21/20 Instruments for performing navigational calculations G01C21/24, G01C21/26 take precedence
• 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 1/202 Dispatching vehicles on the basis of a location, e.g. taxi dispatching
• 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
• CPC Class Codes: H04B 7/18504 Aircraft used as relay or high altitude atmospheric platform

Abstract

Example methods and systems for performing fleet planning based on coarse estimates of regions is provided. A method may include receiving information indicative of a sequence of coverage requirements for a region over a period of time. For one or more time intervals of the period of time, the method may include dividing the region over which vehicles of the plurality of vehicles may traverse into a plurality of sub-regions such that for each subsequent time interval a size of a given sub-region increases. The method includes at each of the one or more time intervals of the period of time, determining vehicles of the plurality of vehicles that can reach a given landmark in a given sub-region by an end of the one or more time intervals, and based on the sequence of coverage requirements, generating a fleet plan for the time intervals based on the determined vehicles.

Claims

1. A method comprising:

receiving, at one or more processors, a sequence of coverage requirements 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 time intervals, and wherein an individual coverage requirement of the sequence of coverage requirements identifies a desired number of vehicles of a plurality of vehicles for each of the plurality of landmarks at a given time interval;

for one or more time intervals of the period of time, dividing, by the one or more processors, the region into a plurality of sub-regions such that for a first interval of the period of time, a given landmark of the plurality of landmarks is located in a first sub-region having a first size, and for a second interval of the period of time subsequent to the first interval, the given landmark is located in a second sub-region encompassing the first sub-region but having a second size that is larger than the first size;

for the first interval of the period of time, determining by the one or more processors a set of one or more vehicles of the plurality of vehicles that are able to reach the given landmark in the first sub-region by an end of the first interval of the period of time;

for the second interval of the period of time, determining by the one or more processors a set of one or more vehicles of the plurality of vehicles that are able to reach the given landmark in the second sub-region by an end of the second interval of the period of time, and

based on the sequence of coverage requirements, generating, by the one or more processors, a fleet plan for the time intervals based on the determined set of one or more vehicles, wherein the generating occurs before any vehicle of the determined set of one or more vehicles travels to the given landmark, and wherein the fleet plan comprises instructions that cause at least one vehicle of the set of one or more vehicles to move in order to reach the given landmark;

wherein determining by the one or more processors vehicles of the plurality of vehicles that can reach the given landmark in the first sub-region by the end of the first interval of the period of time comprises;

determining starting locations of the set of one or more vehicles of the plurality of vehicles that are currently in operation and are configured to move in order to reach the given landmark; and

based on the determined starting locations, determining vehicles of the plurality of vehicles that are currently in operation and can traverse a distance from the respective starting locations to the given landmark by the end of the first interval of the period of time,

wherein the vehicles of the plurality of vehicles comprise balloons within a data network operable to provide data communication via optical or radio-frequency (RF) links, and wherein determining the vehicles of the plurality of vehicles that can traverse the distance from the respective starting locations to the given landmark by the end of the one or more time intervals comprises;

receiving information indicative of an estimated wind direction and speed at given altitudes;

estimating a distance and direction that the balloons would travel based on the estimated wind direction and speed at the given altitudes; and

determining a sub-region of the plurality of sub-regions where the balloons would reside by traveling the estimated distance and direction.

2. 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.

3. The method of claim 1, wherein determining by the one or more processors vehicles of the plurality of vehicles that can reach the given landmark in the first sub-region by the end of the first interval of the period of time comprises determining a phase fleet plan and the method further comprises:

determining by the one or more processors vehicles of the plurality of vehicles that can reach the given landmark in the first sub-region by the end of the first interval of the period of time one or more time intervals based on the phase fleet plan of a subsequent time interval.

4. The method of claim 1, wherein a length of intervals of the plurality of time intervals increases over time.

5. The method of claim 1, wherein dividing, by the one or more processors, the region into the plurality of sub-regions comprises determining the size of sub-regions based on a length of the time interval so that as the length of the time interval increases, the size of sub-regions increase.

6. The method of claim 1, wherein dividing, by the one or more processors, the region into the plurality of sub-regions comprises determining increasingly coarse representations of the region over time.

7. The method of claim 1, wherein for each subsequent time interval a number of sub-regions for which the region is divided into decreases.

8. The method of claim 1, further comprising dividing the region such that the size of the sub-regions and a length between time intervals increase at related rates.

9. The method of claim 1, wherein determining by the one or more processors vehicles of the plurality of vehicles that can reach the given landmark in the first sub-region by the end of the first interval of the time period comprises determining a phase fleet plan and the method further comprises:

determining a first phase fleet plan for the region being divided into a first number of sub-regions; and

based on the first phase fleet plan, determining a second phase fleet plan for the region being divided into a second number of sub-regions more than the first number of sub-regions.

10. The method of claim 1, further comprising:

determining estimates of end-of-interval positions for vehicles of the plurality of vehicles for each of the one or more time intervals; and

using the estimates of the end-of-interval positions for the vehicles of the plurality of vehicles as estimates of initial interval positions for the vehicles for a subsequent time interval.

11. The method of claim 1, further comprising:

receiving information indicative of updates about the plurality of vehicles, wherein the information includes an updated location of one or more vehicles or an update in wind conditions of the region; and

based on the received information, regenerating the fleet plan and for the time intervals corresponding to the region divided into sub-regions having a size less than a threshold amount.

12. A 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 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 time intervals, and wherein an individual coverage requirement of the sequence of coverage requirements identifies a desired number of vehicles of a plurality of vehicles for each of the plurality of landmarks at a given time interval;

for one or more time intervals of the period of time, dividing the region into a plurality of sub-regions such that for a first interval of the period of time, a given landmark of the plurality of landmarks is located in a first sub-region having a first size, and for a second interval of the period of time subsequent to the first interval, the given landmark is located in a second sub-region encompassing the first sub-region but having a second size that is larger than the first size;

for the first interval of the period of time, determining vehicles of the plurality of vehicles that are able to reach the given landmark in the first sub-region by an end of the first interval of the period of time;

for the second interval of the period of time, determining vehicles of the plurality of vehicles that are able to reach the given landmark in the second sub-region by an end of the second interval of the period of time; and

based on the sequence of coverage requirements, generating a fleet plan for the time intervals based on the determined vehicles, wherein the generating occurs before any vehicle of the determined set of one or more vehicles travels to the given landmark, and wherein the fleet plan comprises instructions that cause at least one vehicle of the set of one or more vehicles to move in order to reach the given landmark;

wherein determining by the one or more processors vehicles of the plurality of vehicles that can reach the given landmark in the first sub-region by the end of the first interval of the period of time comprises;

determining starting locations of the set of one or more vehicles of the plurality of vehicles that are currently in operation and are configured to move in order to reach the given landmark; and

based on the determined starting locations, determining vehicles of the plurality of vehicles that are currently in operation and can traverse a distance from the respective starting locations to the given landmark by the end of the first interval of the period of time.

13. The computer readable storage medium of claim 12, wherein the vehicles of the plurality of vehicles comprise balloons within a data network operable to provide data communication via optical or radio-frequency (RF) links, and wherein determining vehicles of the plurality of vehicles that can reach the given landmark in the first sub-region by the end of the first interval of the period of time ene-comprises:

receiving information indicative of an estimated wind direction and speed at given altitudes;

estimating a distance and direction that the balloons would travel based on the estimated wind direction and speed at the given altitudes and the respective starting locations; and

determining a sub-region of the plurality of sub-regions where the balloons would reside by traveling the estimated distance and direction.

14. The computer readable storage medium of claim 12, wherein a length of intervals of the plurality of time intervals increases over time, and wherein for each subsequent time interval a number of sub-regions for which the region is divided into decreases, and the functions further comprise dividing the region such that the size of the sub-regions and the length between time intervals increase at related rates.

15. The computer readable storage medium of claim 12, wherein determining vehicles of the plurality of vehicles that can reach the given landmark in the given sub-region by the end of the one or more time intervals comprises determining a phase fleet plan and the functions further comprise:

determining a first phase fleet plan for the region being divided into a first number of sub-regions, and

based on the first phase fleet plan, determining a second phase fleet plan for the region being divided into a second number of sub-regions more than the first number of sub-regions.

16. 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 a sequence of coverage requirements 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 time intervals, and wherein an individual coverage requirement of the sequence of coverage requirements identifies a desired number of vehicles of a plurality of vehicles for each of the plurality of landmarks at a given time interval;

for one or more time intervals of the period of time, dividing the region into a plurality of sub-regions such that for a first interval of the period of time, a given landmark of the plurality of landmarks is located in a first sub-region having a first size, and for a second interval of the period of time subsequent to the first interval, the given landmark is located in a second sub-region encompassing the first sub-region but having a second size that is larger than the first size;

for the first interval of the period of time, determining vehicles of the plurality of vehicles that are able to reach the given landmark in the first sub-region by an end of the first interval of the period of time;

for the second interval of the period of time, determining vehicles of the plurality of vehicles that are able to reach the given landmark in the second sub-region by an end of the second interval of the period of time; and

based on the sequence of coverage requirements, generating a fleet plan for the time intervals based on the determined vehicles, wherein the generating occurs before any vehicle of the determined set of one or more vehicles travels to the given landmark, and wherein the fleet plan comprises instructions that cause at least one vehicle of the set of one or more vehicles to move in order to reach the given landmark;

wherein determining by the one or more processors vehicles of the plurality of vehicles that can reach the given landmark in the first sub-region by the end of the first interval of the period of time comprises;

determining starting locations of the set of one or more vehicles of the plurality of vehicles that are currently in operation and are configured to move in order to reach the given landmark; and

based on the determined starting locations, determining vehicles of the plurality of vehicles that are currently in operation and can traverse a distance from the respective starting locations to the given landmark by the end of the first interval of the Period of time.

17. The system of claim 16, 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, and wherein the functions further comprise:

providing instructions to one or more vehicles of the plurality of vehicles to operate according to the fleet plan.

18. The system of claim 16, wherein determining vehicles of the plurality of vehicles that can reach the given landmark in the first sub-region by the end of the first interval of the period of time comprises determining a phase fleet plan, and wherein the functions further comprise:

determining a first phase fleet plan for the region being divided into a first number of sub-regions; and

based on the first phase fleet plan, determining a second phase fleet plan for the region being divided into a second number of sub-regions more than the first number of sub-regions.