Methods and systems for performing fleet planning based on coarse estimates of regions
First Claim
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, andbased 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.
4 Assignments
0 Petitions
Accused Products
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.
75 Citations
18 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
-
-
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. - View Dependent Claims (13, 14, 15)
-
-
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. - View Dependent Claims (17, 18)
-
Specification