Methods and systems for performing flocking while executing a long-range fleet plan

• US 8,781,727 B1
• Filed: 01/15/2013
• Issued: 07/15/2014
• Est. Priority Date: 01/15/2013
• Status: Active Grant

• Current Assignee: Loon, LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Bonawitz, Keith Allen, Piponi, Dan
• Primary Examiner(s): Black, Thomas
• Assistant Examiner(s): PAIGE, TYLER D
• Application Number:
  US13/742,209
• Time in Patent Office: 546 Days
• Field of Search: 701/422, 701/410
• US Class Current: 701/422
• CPC Class Codes: G05D 1/104 involving a plurality of aircrafts, e.g. formation flying traffic control systems for aircraft G08G5/00

Abstract

Methods and systems for performing flocking while executing a fleet plan are provided. An example method includes receiving a sequence of coverage requirements for a region and an associated period of time, and determining a respective sequence of intended destinations for each of one or more vehicles of a fleet of vehicles to travel to over the period of time. Additionally, based on a determined sequence of intended destinations for a vehicle of the one or more vehicles and based on a desired spatial relationship between the vehicle and one or more neighboring vehicles for a given time period, a flocking-based direction of travel for the vehicle may be determined for the given time period.

Claims

1. A method comprising:

receiving a sequence of coverage requirements for a region and an associated period of time, wherein the region is characterized by a plurality of landmarks, and wherein individual coverage requirements of the sequence of coverage requirements indicate a desired number of vehicles for different landmarks of the plurality of landmarks at a respective time period within the period of time;

determining, by a processor, a respective sequence of intended destinations for each of one or more vehicles of a fleet of vehicles to travel to over the period of time to satisfy the sequence of coverage requirements; and

determining, by the processor, a flocking-based direction of travel for a vehicle of the one or more vehicles and a given time period based on;

(a) a determined sequence of intended destinations for the vehicle and (b) a desired spatial relationship between the vehicle and one or more neighboring vehicles for the given time period.

2. The method of claim 1, further comprising instructing the vehicle to travel in the flocking-based direction.

3. The method of claim 1, further comprising:

determining a target geographic distribution of vehicles for the given time period using a determined sequence of intended destinations for each of a plurality of vehicles of the fleet of vehicles; and

determining the desired spatial relationship between the vehicle and one or more neighboring vehicles for the given time period based on a location of the vehicle and a density of the target geographic distribution for the location.

4. The method of claim 3, wherein determining the target geographic distribution for the given time period using a determined sequence of intended destinations for each of a plurality of vehicles comprises:

determining a trajectory for each vehicle over the period of time using the determined sequence of intended destinations for the vehicle;

determining an estimated location of each vehicle for the given time period based on the determined trajectory for each vehicle; and

determining the target geographic distribution based on the estimated location of each vehicle for the given time period.

5. The method of claim 1, wherein the desired spatial relationship between the vehicle and one or more neighboring vehicles for the given time period comprises a desired minimum inter-vehicle distance between the vehicle and each of the one or more neighboring vehicles.

6. The method of claim 1, wherein the desired spatial relationship between the vehicle and one or more neighboring vehicles for the given time period comprises a desired minimum number of vehicles to be located within a threshold distance of the vehicle.

7. The method of claim 1, further comprising:

based on the determined sequence of intended destinations for the vehicle, determining a control policy for the vehicle, wherein the control policy for the vehicle indicates a direction of travel for the vehicle based on a location of the vehicle; and

determining the flocking-based direction of travel for the vehicle for the given time period based on the control policy for the vehicle and the desired spatial relationship between the vehicle and one or more neighboring vehicles for the given time period.

8. The method of claim 7, 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 links, and the method further comprises:

determining the control policy for the vehicle based on estimated winds at one or more altitudes that the vehicle could follow.

9. The method of claim 1, wherein the region is divided into a plurality of cells, and the method further comprises:

based on the determined sequence of intended destinations for the vehicle, determining respective fitness values for each cell of the plurality of cells, wherein a respective fitness value is based at least in part on a distance from an intended destination that the vehicle could reach by starting from a given cell of the plurality of cells;

determining the flocking-based direction of travel for the vehicle for the given time period based on the determined fitness values and the desired spatial relationship between the vehicle and one or more neighboring vehicles for the given time period.

10. The method of claim 9, further comprising determining the flocking-based direction of travel for the vehicle for the given time period based at least in part on a direction to a cell having a minimum fitness value and on the desired spatial relationship between the vehicle and one or more neighboring vehicles for the given time period.

11. 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 links.

12. The method of claim 1, wherein determining a respective sequence of intended destinations for each of one or more vehicles of a fleet of vehicles to travel to over the period of time to satisfy the sequence of coverage requirements comprises:

determining for each of one or more phases during the period of time, a number of vehicles to travel between one or more respective landmarks of the plurality of landmarks and one or more additional landmarks of the plurality of landmarks during the phase to satisfy the sequence of coverage requirements; and

determining the respective sequence of intended destinations for each of the one or more vehicles of the fleet of vehicles to travel to over the period of time based on the determined number of vehicles for the one or more phases.

13. 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 a sequence of coverage requirements for a region and an associated period of time, wherein the region is characterized by a plurality of landmarks, and wherein individual coverage requirements of the sequence of coverage requirements indicate a desired number of vehicles for different landmarks of the plurality of landmarks at a respective time period within the period of time;

determining a respective sequence of intended destinations for each of one or more vehicles of a fleet of vehicles to travel to over the period of time to satisfy the sequence of coverage requirements; and

determining a flocking-based direction of travel for a vehicle of the one or more vehicles and a given time period based on;

(a) a determined sequence of intended destinations for the vehicle and (b) a desired spatial relationship between the vehicle and one or more neighboring vehicles for the given time period.

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

determining a target geographic distribution of vehicles for the given time period using the determined sequence of intended destinations for each of a plurality of vehicles of the fleet of vehicles; and

determining the desired spatial relationship between the vehicle and one or more neighboring vehicles for the given time period based on a location of the vehicle and a density of the target geographic distribution for the location.

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

based on the determined sequence of intended destinations for the vehicle, determining a control policy for the vehicle, wherein the control policy for the vehicle indicates a direction of travel for the vehicle based on a location of the vehicle; and

determining the flocking-based direction of travel for the vehicle for the given time period based on the control policy for the vehicle and the desired spatial relationship between the vehicle and one or more neighboring vehicles for the given time period.

16. The non-transitory computer-readable storage medium of claim 13, wherein the desired spatial relationship between the vehicle and one or more neighboring vehicles for the given time period comprises one or more of:

a desired minimum inter-balloon distance between the vehicle and each of the one or more neighboring vehicles; and

a desired minimum number of vehicles to be located within a threshold distance of the vehicle.

17. 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 a sequence of coverage requirements for a region and an associated period of time, wherein the region is characterized by a plurality of landmarks, and wherein individual coverage requirements of the sequence of coverage requirements indicate a desired number of vehicles for different landmarks of the plurality of landmarks at a respective time period within the period of time;

determining a respective sequence of intended destinations for each of one or more vehicles of a fleet of vehicles to travel to over the period of time to satisfy the sequence of coverage requirements; and

determining a flocking-based direction of travel for a vehicle of the one or more vehicles for the and a given time period based on;

(a) a determined sequence of intended destinations vehicle and (b) a desired spatial relationship between the vehicle and one or more neighboring vehicles for the given time period.

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

determining a target geographic distribution of vehicles for the given time period using the determined sequence of intended destinations for each of a plurality of vehicles of the fleet of vehicles; and

determining the desired spatial relationship between the vehicle and one or more neighboring vehicles for the given time period based on a location of the vehicle and a density of the target geographic distribution for the location.

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

based on the determined sequence of intended destinations for the vehicle, determining a control policy for the vehicle, wherein the control policy for the vehicle indicates a direction of travel for the vehicle based on a location of the vehicle; and

determining the flocking-based direction of travel for the vehicle for the given time period based on the control policy for the vehicle and the desired spatial relationship between the vehicle and one or more neighboring vehicles for the given time period.

20. The system of claim 17, 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 links.