Methods and systems for determining fleet trajectories to satisfy a sequence of coverage requirements

• US 9,275,551 B2
• Filed: 03/22/2015
• Issued: 03/01/2016
• Est. Priority Date: 12/29/2012
• Status: Expired due to Fees

• Current Assignee: Loon, LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Bonawitz, Keith Allen, Treuille, Adrien
• Primary Examiner(s): Shaawat, Mussa A
• Assistant Examiner(s): WONG, YUEN H
• Application Number:
  US14/664,872
• Publication Number:
  US 20150194058A1
• Time in Patent Office: 345 Days
• US Class Current: 1/1
• 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 for controlling a fleet of vehicles to satisfy coverage requirements for a geographic region, comprising:

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

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

determining, by a processor, for each particular phase of one or more phases of the plurality of phases, possible routes that a vehicle of the fleet of vehicles located at one or more respective landmarks of the plurality of landmarks at a beginning of the particular phase follows to reach one or more additional landmarks of the plurality of landmarks by an end of the particular phase;

based on the initial locations of the one or more vehicles of the fleet of vehicles, the sequence of individual coverage requirements, and the determined possible routes, determining, by the processor, which landmark of the plurality of landmarks for the vehicle of the fleet of vehicles to travel to during a respective phase of the one or more phases; and

transmitting using one or more optical or radio-frequency (RF) links instructions to the vehicle of the fleet of vehicles to cause the vehicle to travel to the determined landmark during the respective phase.

2. The method of claim 1, wherein the vehicle comprises a balloon within a data network that is operable to provide data communication via optical or RF links.

3. The method of claim 2, further comprising determining the possible routes based on one or more estimated winds at one or more altitudes.

4. The method of claim 1, wherein the fleet of vehicles comprises a fleet of autonomous vehicles.

5. The method of claim 4, wherein the fleet of autonomous vehicles comprises a fleet of autonomous ground vehicles.

6. The method of claim 1, wherein determining possible routes that a vehicle located at one or more respective landmarks of the plurality of landmarks at a beginning of the particular phase follows to reach one or more additional landmarks of the plurality of landmarks by an end of the particular phase comprises determining, for each of the one or more respective landmarks, which of the one or more additional landmarks that the vehicle travels to within a threshold distance of when starting from the respective landmark and traveling during the particular phase.

7. The method of claim 1, wherein determining possible routes that a vehicle located at one or more respective landmarks of the plurality of landmarks at a beginning of the particular phase follows to reach one or more additional landmarks of the plurality of landmarks by an end of the particular phase comprises determining possible routes having an associated cost value that satisfies a cost threshold.

8. The method of claim 7, wherein the cost value associated with each possible route is indicative of an amount of power consumed by the vehicle over a duration of the possible route.

9. The method of claim 1, wherein determining possible routes that a vehicle located at one or more respective landmarks of the plurality of landmarks at a beginning of the particular phase follows to reach one or more additional landmarks of the plurality of landmarks by an end of the particular phase comprises determining possible routes having an associated confidence measure that satisfies a confidence threshold.

10. The method of claim 1, further comprising determining, based on the initial locations of the one or more vehicles of the fleet of vehicles, the sequence of individual coverage requirements, and the determined possible routes, a respective trajectory for each of multiple vehicles of the fleet of vehicles to follow during the plurality of phases to satisfy the sequence of coverage requirements.

11. The method of claim 1, wherein each individual coverage requirement of the sequence of individual coverage requirements comprises a goal distribution of the fleet of vehicles for an end of a given phase of the plurality of phases that is defined with respect to landmarks of the plurality of landmarks.

12. A non-transitory computer-readable storage medium having stored therein instructions, that when executed by the computing device, cause the computing device to perform functions for controlling a fleet of vehicles to satisfy coverage requirements for a geographic region, comprising:

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

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

determining for each particular phase of one or more phases of the plurality of phases, possible routes that a vehicle of the fleet of vehicles located at one or more respective landmarks of the plurality of landmarks at a beginning of the particular phase follows to reach one or more additional landmarks of the plurality of landmarks by an end of the particular phase;

based on the initial locations of the one or more vehicles of the fleet of vehicles, the sequence of individual coverage requirements, and the determined possible routes, determining which landmark of the plurality of landmarks for the vehicle of the fleet of vehicles to travel to during a respective phase of the one or more phases; and

transmitting using one or more optical or radio-frequency (RF) links instructions to the vehicle of the fleet of vehicles to cause the vehicle to travel to the determined landmark during the respective phase.

13. The non-transitory computer-readable medium of claim 12, wherein the fleet of vehicles comprises a fleet of autonomous vehicles.

14. The non-transitory computer-readable medium of claim 12, wherein determining possible routes that a vehicle located at one or more respective landmarks of the plurality of landmarks at a beginning of the particular phase follows to reach one or more additional landmarks of the plurality of landmarks by an end of the particular phase comprises determining, for each of the one or more respective landmarks, which of the one or more additional landmarks that the vehicle travels to within a threshold distance of when starting from the respective landmark and traveling during the particular phase.

15. The non-transitory computer-readable medium of claim 12, wherein the functions further comprise determining, based on the initial locations of the one or more vehicles of the fleet of vehicles, the sequence of individual coverage requirements, and the determined possible routes, a respective trajectory for each of multiple vehicles of the fleet of vehicles to follow during the plurality of phases to satisfy the sequence of coverage requirements.

16. A system for controlling a fleet of vehicles to satisfy coverage requirements for a geographic region, comprising:

at least one processor; and

a non-transitory 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 the fleet of vehicles,

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

determining for each particular phase of one or more phases of the plurality of phases, possible routes that a vehicle of the fleet of vehicles located at one or more respective landmarks of the plurality of landmarks at a beginning of the particular phase follows to reach one or more additional landmarks of the plurality of landmarks by an end of the particular phase,

based on the initial locations of the one or more vehicles of the fleet of vehicles, the sequence of individual coverage requirements, and the determined possible routes, determining which landmark of the plurality of landmarks for the vehicle of the fleet of vehicles to travel to during a respective phase of the one or more phases; and

transmitting using one or more optical or radio-frequency (RF) links instructions to the vehicle of the fleet of vehicles to cause the vehicle to travel to the determined landmark during the respective phase.

17. The system of claim 16, wherein the fleet of vehicles comprises a fleet of autonomous vehicles.

18. The system of claim 16, wherein determining possible routes that a vehicle located at one or more respective landmarks of the plurality of landmarks at a beginning of the particular phase follows to reach one or more additional landmarks of the plurality of landmarks by an end of the particular phase comprises determining, for each of the one or more respective landmarks, which of the one or more additional landmarks that the vehicle travels to within a threshold distance of when starting from the respective landmark and traveling during the particular phase.

19. The system of claim 16, wherein the functions further comprise determining, based on the initial locations of the one or more vehicles of the fleet of vehicles, the sequence of individual coverage requirements, and the determined possible routes, a respective trajectory for each of multiple vehicles of the fleet of vehicles to follow during the plurality of phases to satisfy the sequence of coverage requirements.