Methods and Systems for Determining Fleet Trajectories to Satisfy a Sequence of Coverage Requirements

• US 20140188377A1
• Filed: 12/29/2012
• Published: 07/03/2014
• Est. Priority Date: 12/29/2012
• Status: Active Grant

• Current Assignee: Loon, LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Bonawitz, Keith Allen, Treuille, Adrien
• Granted Patent: US 9,014,957 B2
• Time in Patent Office: Days
• US Class Current: 701/120
• CPC Class Codes: B64B 1/58 Arrangements or construction of gas-bags; Filling arrangements
• CPC Class Codes: B64B 1/60 Gas-bags surrounded by separate containers of inert gas
• CPC Class Codes: B64U 10/30 Lighter-than-air aircraft, e.g. aerostatic aircraft
• CPC Class Codes: B64U 2101/20 for use as communications relays, e.g. high-altitude platforms
• CPC Class Codes: B64U 2201/102 adapted for flying in formations
• CPC Class Codes: B64U 50/31 generated by photovoltaics
• 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: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem
• CPC Class Codes: G08G 1/20 Monitoring the location of vehicles belonging to a group, e.g. fleet of vehicles, countable or determined number of vehicles
• CPC Class Codes: G08G 1/202 Dispatching vehicles on the basis of a location, e.g. taxi dispatching
• 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
• 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

Methods and systems for determining trajectories for vehicles of a fleet of vehicles are provided. In one example, a method comprises receiving an initial location of one or more vehicles, and receiving a sequence of coverage requirements for a region and an associated period of time. The region may be divided into a plurality of landmarks and the period of time may be divided into a plurality of phases. The method also comprises determining for each of one or more phases and at least one respective landmark, a set of starting landmarks from which a vehicle could reach the respective landmark during the phase. The method further comprises determining which respective landmark that the vehicle should travel to during the one or more phases based on the sequence of coverage requirements and the set of starting landmarks for the one or more phases and the at least one respective landmark.

Claims

1. A method comprising:

receiving an initial location of one or more vehicles of a fleet of vehicles;

receiving a sequence of coverage requirements for a region and an associated period of time, wherein the region is divided into a plurality of landmarks and the period of time is divided into a plurality of phases, and wherein an individual coverage requirement is indicative of a desired number of vehicles for one or more of the plurality of landmarks at an end of a given phase;

determining, by a processor, for each of one or more phases and at least one respective landmark of the plurality of landmarks, a set of starting landmarks of the plurality of landmarks from which a vehicle could reach the respective landmark during the phase; and

based on the initial locations of the one or more vehicles, the sequence of coverage requirements, and the determined set of starting landmarks for the one or more phases and the at least one respective landmark, determining, by the processor, which respective landmark for the vehicle to travel to during the one or more phases.

2. The method of claim 1, further comprising instructing the vehicle to travel to the determined respective landmark during the one or more phases.

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

4. The method of claim 3, further comprising determining the set of starting landmarks of the plurality of landmarks from which a balloon could reach the respective landmark by following one or more estimated winds at one or more altitudes during the phase.

5. The method of claim 1, further comprising:

determining, by the processor, for each of the one or more phases and the at least one respective landmark of the plurality of landmarks, a minimum distance from the respective landmark that a vehicle starting from each additional landmark of the plurality of landmarks could reach during the phase; and

determining, by the processor, the set of starting landmarks for the phase and the respective landmark based on a comparison between minimum distances associated with the additional landmarks and a threshold distance.

6. The method of claim 5, further comprising determining, by the processor, which respective landmark for the vehicle to travel to during the one or more phases based on the minimum distances associated with the determined set of starting landmarks for the one or more phases and the at least one respective landmark.

7. The method of claim 1, further comprising:

determining, by the processor, for each of the one or more phases and the at least one respective landmark of the plurality of landmarks, a confidence measure that is indicative of whether a vehicle starting from each additional landmark of the plurality of landmarks could reach the respective landmark during the phase; and

determining, by the processor, the set of starting landmarks for the phase and the respective landmark based on a comparison between confidence measures associated with the additional landmarks and a confidence threshold.

8. The method of claim 7, further comprising determining, by the processor, which respective landmark for the vehicle to travel to during the one or more phases based on the confidence measures associated with the determined set of starting landmarks for the one or more phases and the at least one respective landmark.

9. The method of claim 1, further comprising:

determining, by the processor, for each of the one or more phases and at least one respective landmark of the plurality of landmarks, a cost value associated with a vehicle starting from each additional landmark of the plurality of landmarks and traveling to the respective landmark during the phase; and

determining, by the processor, the set of starting landmarks 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 3, further comprising determining the one or more estimated winds based on wind data received from one or more balloons.

11. The method of claim 1, further comprising determining which respective landmark for the vehicle to travel to during the one or more phases by minimizing a linear objective function.

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 an initial location of one or more vehicles of a fleet of vehicles;

receiving a sequence of coverage requirements for a region and an associated period of time, wherein the region is divided into a plurality of landmarks and the period of time is divided into a plurality of phases, and wherein an individual coverage requirement is indicative of a desired number of vehicles for one or more of the plurality of landmarks at an end of a given phase;

determining, for each of one or more phases and at least one respective landmark of the plurality of landmarks, a set of starting landmarks of the plurality of landmarks from which a vehicle could reach the respective landmark during the phase; and

based on the initial locations of the one or more vehicles, the sequence of coverage requirements, and the determined set of starting landmarks for the one or more phases and the at least one respective landmark, determining, which respective landmark for the vehicle to travel to during the one or more phases.

13. The computer-readable storage medium of claim 12, wherein the functions further comprise:

determining, for each of the one or more phases and the at least one respective landmark of the plurality of landmarks, a minimum distance from the respective landmark that a vehicle starting from each additional landmark of the plurality of landmarks could reach during the phase; and

determining the set of starting landmarks for the phase and the respective landmark based on a comparison between minimum distances associated with the additional landmarks and a threshold distance.

14. The computer-readable storage medium of claim 12, wherein the functions further comprise:

determining, for each of the one or more phases and the at least one respective landmark of the plurality of landmarks, a confidence measure that is indicative of whether a vehicle starting from each additional landmark of the plurality of landmarks could reach the respective landmark during the phase; and

determining the set of starting landmarks for the phase and the respective landmark based on a comparison between confidence measures associated with the additional landmarks and a confidence threshold.

15. The computer-readable storage medium of claim 12, wherein the functions further comprise:

determining, for each of the one or more phases and the at least one respective landmark of the plurality of landmarks, a cost value associated with a vehicle starting from each additional landmark of the plurality of landmarks and traveling to the respective landmark during the phase; and

determining, by the processor, the set of starting landmarks for the phase and the respective landmark based on a comparison between cost values associated with the additional landmarks and a cost threshold.

16. A system, comprising:

at least one processor; and

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

receiving an initial location of one or more vehicles of a fleet of vehicles;

receiving a sequence of coverage requirements for a region and an associated period of time, wherein the region is divided into a plurality of landmarks and the period of time is divided into a plurality of phases, and wherein an individual coverage requirement is indicative of a desired number of vehicles for one or more of the plurality of landmarks at an end of a given phase;

determining, for each of one or more phases and at least one respective landmark of the plurality of landmarks, a set of starting landmarks of the plurality of landmarks from which a vehicle could reach the respective landmark during the phase; and

based on the initial locations of the one or more vehicles, the sequence of coverage requirements, and the determined set of starting landmarks for the one or more phases and the at least one respective landmark, determining, which respective landmark for the vehicle to travel to during the one or more phases.

17. The system of claim 16, wherein the functions further comprise instructing the vehicle to travel to the determined respective landmark during the one or more phases.

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

19. The system of claim 18, wherein the functions further comprise:

determining, for each of the one or more phases and the at least one respective landmark of the plurality of landmarks, a minimum distance from the respective landmark that a balloon starting from each additional landmark of the plurality of landmarks could reach by following one or more predicted winds at one or more altitudes during the phase; and

determining, the set of starting landmarks for the phase and the respective landmark based on a comparison between minimum distances associated with the additional landmarks and a threshold distance.

20. The system of claim 19, wherein the functions further comprise determining which respective landmark for the balloon to travel to during the one or more phases based on the minimum distances associated with the determined set of starting landmarks for the one or more phases and the at least one respective landmark.