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

Patent metadata

Field	Value
Publication number	US-9424752-B1
Application number	US-201213727071-A
Country	US
Kind code	B1
Filing date	Dec 26, 2012
Priority date	Dec 26, 2012
Publication date	Aug 23, 2016
Grant date	Aug 23, 2016

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.

First claim

What is claimed is:

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;
fo

Assignees

• Bonawitz Keith
• Google Inc

Inventors

• Bonawitz Keith

Classifications

• H04B7/18504

  Aircraft used as relay or high altitude atmospheric platform · CPC title

• G08G1/202

  Dispatching vehicles on the basis of a location, e.g. taxi dispatching · CPC title

• G01C21/20 Primary

  Instruments for performing navigational calculations (G01C21/24, G01C21/26 take precedence) · CPC title

• G08G5/76

  for monitoring atmospheric conditions · CPC title

• G08G5/57

  for unmanned aircraft · CPC title