Methods and systems for determining fleet trajectories with phase-skipping to satisfy a sequence of coverage requirements

• US 8,849,571 B1
• Filed: 12/26/2012
• Issued: 09/30/2014
• Est. Priority Date: 12/26/2012
• Status: Active Grant

• Current Assignee: Loon, LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Bonawitz, Keith Allen, Rhodes, Bradley James
• Primary Examiner(s): Algahaim, Helal A
• Assistant Examiner(s): Wallace, Donald J
• Application Number:
  US13/726,697
• Time in Patent Office: 643 Days
• Field of Search: 701/120, 701/527
• US Class Current: 701/527
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem
• CPC Class Codes: G08G 1/202 Dispatching vehicles on the basis of a location, e.g. taxi dispatching
• CPC Class Codes: H04B 7/18504 Aircraft used as relay or high altitude atmospheric platform

Abstract

Methods and systems for determining trajectories for 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 method also comprises determining, for each of one or more phases, single-phase landmarks that a vehicle could travel to over the duration of the phase, and determining for at least one of the one or more phases, phase-skipping landmarks that a vehicle could travel to over the duration of multiple phases. The method further comprises determining which landmarks of the single-phase landmarks and phase-skipping landmarks that a vehicle should travel to based on the initial locations of the one or more vehicles and the sequence of coverage requirements.

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 of the fleet 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, single-phase landmarks of the plurality of landmarks that can be reached by a vehicle of the fleet of vehicles starting from the respective landmark and following a single-phase path, wherein a single-phase path includes a path that the vehicle can travel for a duration of a single phase;

determining, by the processor, for at least one respective phase of the one or more phases, phase-skipping landmarks of the plurality of landmarks that can be reached by the vehicle starting from a landmark of a set of landmarks associated with the respective phase and following a phase-skipping path, wherein a phase-skipping path includes a path that the vehicle can travel for a duration of two or more phases; and

based on the sequence of coverage requirements and the initial locations of the one or more vehicles, determining, by the processor, which landmarks of the single-phase landmarks and phase-skipping landmarks 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 landmarks during the one or more phases.

3. The method of claim 1, wherein the vehicle includes 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:

wherein a single-phase path includes a path that the balloon can travel by following one or more estimated winds at one or more altitudes for a duration of a single phase; and

wherein a phase-skipping path includes a path that the balloon can travel by following one or more estimated winds at one or more altitudes for a duration of two or more phases.

5. The method of claim 1, further comprising:

sequentially determining which landmarks of the single-phase landmarks and phase-skipping landmarks for the vehicle to travel to during the one or more phases; and

determining the set of landmarks associated with a given phase based at least in part on which landmarks that vehicles of the fleet of vehicles are arranged to leave from during a previous phase.

6. The method of claim 1, further comprising:

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

determining the phase-skipping landmarks for the landmark of the set of landmarks based on a minimum distance from each additional landmark of the plurality of landmarks that the vehicle starting from the landmark could reach by following a phase-skipping path.

7. The method of claim 6, further comprising determining which landmarks of the single-phase landmarks and phase-skipping landmarks for the vehicle to travel to during the one or more phases based on the minimum distances associated with the determined single-phase landmarks for the one or more phases and the at least one respective landmark.

8. The method of claim 1, further comprising:

determining the single-phase landmarks for the one or more phases and the at least one respective landmark based on confidence measures that are indicative of whether the vehicle starting from the respective landmark could reach each additional landmark of the plurality of landmarks during the phase; and

determining the phase-skipping landmarks for the landmark of the set of landmarks based on confidence measure that are indicative of whether the vehicle starting from the landmark could reach each additional landmark of the plurality of landmarks by following a phase-skipping path.

9. The method of claim 1, further comprising:

determining the single-phase landmarks for the one or more phases and the at least one respective landmark based on cost values associated with the vehicle traveling to each additional landmark of the plurality of landmarks during the phase; and

determining the phase-skipping landmarks for the landmark of the set of landmarks based on cost values associated with the vehicle traveling to each additional landmark of the plurality of landmarks by following a phase-skipping path.

10. The method of claim 1, further comprising determining which landmarks of the single-phase landmarks and phase-skipping landmarks for the vehicle to travel to during the one or more phases by minimizing a linear objective function.

11. 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 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 of the fleet 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, single-phase landmarks of the plurality of landmarks that can be reached by a vehicle of the fleet of vehicles starting from the respective landmark and following a single-phase path, wherein a single-phase path includes a path that the vehicle can travel for a duration of a single phase;

determining, for at least one respective phase of the one or more phases, phase-skipping landmarks of the plurality of landmarks that can be reached by the vehicle starting from a landmark of a set of landmarks associated with the respective phase and following a phase-skipping path, wherein a phase-skipping path includes a path that the vehicle can travel for a duration of two or more phases; and

based on the sequence of coverage requirements and the initial locations of the one or more vehicles, determining, which landmarks of the single-phase landmarks and phase-skipping landmarks for the vehicle to travel to during the one or more phases.

12. The non-transitory computer-readable storage medium of claim 11, wherein the vehicle includes a balloon within a data network that is operable to provide data communication via optical or radio-frequency (RF) links.

13. The non-transitory computer-readable storage medium of claim 12:

wherein a single-phase path includes a path that the balloon can travel by following one or more estimated winds at one or more altitudes for a duration of a single phase; and

wherein a phase-skipping path includes a path that the balloon can travel by following one or more estimated winds at one or more altitudes for a duration of two or more phases.

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

sequentially determining which landmarks of the single-phase landmarks and phase-skipping landmarks for the vehicle to travel to during the one or more phases; and

determining the set of landmarks associated with a given phase based at least in part on which landmarks that vehicles of the fleet of vehicles are arranged to leave from during a previous phase.

15. The non-transitory computer-readable storage medium of claim 11, wherein the functions further comprise determining which landmarks of the single-phase landmarks and phase-skipping landmarks for the vehicle to travel to during the one or more phases by minimizing a linear objective function.

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 of the fleet 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, single-phase landmarks of the plurality of landmarks that can be reached by a vehicle starting from the respective landmark and following a single-phase path, wherein a single-phase path includes a path that the vehicle can travel for a duration of a single phase;

determining, for at least one respective phase of the one or more phases, phase-skipping landmarks of the plurality of landmarks that can be reached by the vehicle starting from a landmark of a set of landmarks associated with the respective phase and following a phase-skipping path, wherein a phase-skipping path includes a path that the vehicle can travel for a duration of two or more phases; and

based on the sequence of coverage requirements and the initial locations of the one or more vehicles, determining, which landmarks of the single-phase landmarks and phase-skipping landmarks for a 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 landmark during the one or more phases.

18. The system of claim 16, wherein the vehicle includes 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 16, wherein the functions further comprise:

sequentially determining which landmarks of the single-phase landmarks and phase-skipping landmarks for the vehicle to travel to during the one or more phases; and

determining the set of landmarks associated with a given phase based at least in part on which landmarks that vehicles of the fleet of vehicles are arranged to leave from during a previous phase.

20. The system of claim 16, wherein the functions further comprise determining which landmarks of the single-phase landmarks and phase-skipping landmarks for the vehicle to travel to during the one or more phases by minimizing a linear objective function.