Methods and systems for determining altitudes for a vehicle to travel

• US 9,651,382 B1
• Filed: 09/15/2014
• Issued: 05/16/2017
• Est. Priority Date: 12/28/2012
• Status: Active Grant

• Current Assignee: Loon, LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Piponi, Dan P., Rhodes, Bradley
• Primary Examiner(s): Sweeney, Brian P
• Application Number:
  US14/486,829
• Time in Patent Office: 974 Days
• Field of Search: 701533, 701410, 701411, 701415, 701422, 701423, 701522, 701527
• CPC Class Codes: G01C 21/20 Instruments for performing navigational calculations G01C21/24, G01C21/26 take precedence
• CPC Class Codes: H04B 7/18504 Aircraft used as relay or high altitude atmospheric platform

Abstract

Methods and systems for determining altitudes for a vehicle to travel are provided. In one example, a method comprises receiving information indicating a desired location for a balloon and a time period for traveling to the desired location. A region may include the desired location, and the region can be divided into a plurality of cells. The method may include determining estimated cell locations that can be reached by the balloon over a time interval by following a wind at a given altitude. The method may also include assigning a cost value to each cell based on a proximity of the estimated cell locations to a cell including the desired location. The method may further include determining for each cell an altitude for the balloon to travel based on the assigned cost value, and storing information indicating the cost value and the altitude for the balloon to travel.

Claims

1. A method comprising:

receiving, by at least one processor communicatively linked to a vehicle, information indicative of a desired location within a region for the vehicle to reside, the region being divided into a plurality of cells;

determining, by the at least one processor, estimated cell locations that are able to be reached by the vehicle by following a wind at a given altitude;

assigning, by the at least one processor, a cost value to a given cell of the plurality of cells based on a proximity of the estimated cell locations to a cell that includes the desired location;

determining, by a navigation system communicatively linked to the at least one processor, an altitude for the vehicle to travel based on the assigned cost value for the given cell; and

controlling, by a buoyancy system communicatively linked to the at least one processor, the vehicle to travel at the determined altitude.

2. The method of claim 1,

wherein the information is further indicative of a desired time period for traveling to the desired location,

wherein determining estimated cell locations that are able to be reached by the vehicle by following a wind at a given altitude comprises:

determining estimated cell locations that are able to be reached by the vehicle over a time interval of the time period by following a wind at a given altitude, and

wherein assigning a cost value to a given cell of the plurality of cells based on a proximity of the estimated cell locations to a cell that includes the desired location comprises;

for the time interval, assigning a cost value to a given cell of the plurality of cells based on a proximity of the estimated cell locations to a cell that includes the desired location.

3. The method of claim 2, wherein determining an altitude for the vehicle to travel based on the assigned cost value for the given cell comprises:

for the time interval, determining an altitude for the vehicle to travel based on the assigned cost value for the given cell.

4. The method of claim 2, further comprising:

for the time interval, assigning a cost value to a given cell of the plurality of cells based on a given cost value assigned to the given cell for a subsequent time interval.

5. The method of claim 2, further comprising storing for the time interval information per cell indicative of the cost value and the altitude for the vehicle to travel.

6. The method of claim 2, wherein the time period is divided into a plurality of time intervals and the time interval is one of the plurality of time intervals, wherein the method further comprises:

generating a map for a last time interval of the plurality of time intervals; and

subsequently generating a map for each remaining time interval of the plurality of time intervals in reverse sequential order.

7. The method of claim 6, wherein a given map for a given time interval includes cost values based on cost values of a given map for a given subsequent time interval.

8. The method of claim 2,

determining, for each altitude of a plurality of altitudes, estimated cell locations that can be reached by the vehicle over the time interval of the time period by following a given wind at the given altitude;

for each altitude, assigning the cost value to the given cell of the plurality of cells based on the proximity of the estimated cell locations to the cell including the desired location and based on the given cost value of the cell for the subsequent time interval;

for the one or more cells, determining an altitude of the plurality of altitudes based on the cost value of the given cell; and

storing for the time interval and for the given cell in non-transitory data storage coupled to or in communication with the computing device information indicative of the determined altitude of the plurality of altitudes.

9. The method of claim 2, wherein the time period is divided into a plurality of time intervals and the time interval is one of the plurality of time intervals, wherein the method further comprises:

determining for each time interval of the plurality of time intervals information per cell indicative of a given cost value and an associated altitude for the vehicle to travel.

10. The method of claim 2, wherein assigning the cost value to the given cell of the plurality of cells comprises:

assigning a first cost value based on the proximity of the estimated cell locations to a cell including the desired location;

determining a given cost value of the given cell for the subsequent time interval; and

combining the first cost value and the given cost value of the given cell for the subsequent time interval so as to provide the cost value of the given cell for the time interval.

11. The method of claim 2, wherein the time period is divided into a plurality of time intervals and the time interval is one of the plurality of time intervals, wherein the method further comprises:

determining for each time interval of the plurality of time intervals a map including information per cell indicative of a given cost value and an associated altitude for the vehicle to travel;

receiving information indicative of a fleet of vehicles and associated cells for each vehicle representative of a location of each vehicle; and

determining for each time interval of the plurality of time intervals a respective altitude for each vehicle of the fleet of vehicles to travel based on the map for each time interval.

12. The method of claim 1, wherein the vehicle includes a balloon within a data network and is operable to provide data communication via optical or radio-frequency (RF) links.

13. The method of claim 1, wherein a given cost value of cells increases as the proximity of the cells to the cell including the desired location decreases.

14. The method of claim 1, wherein controlling the vehicle to travel at the determined altitude comprises controlling the vehicle to travel at the determined altitude while the vehicle is within a portion of the region designated as the given cell associated with the determined altitude.

15. The method of claim 1, wherein a given cost value is based also on an amount of time for the vehicle to reach the desired location.

16. The method of claim 1, further comprising:

determining, for each altitude of a plurality of altitudes, estimated cell locations that can be reached by the vehicle by following a given wind at the given altitude;

for each altitude, assigning the cost value to the one or more cells of the plurality of cells based on the proximity of the estimated cell locations to the cell including the desired location;

for the one or more cells, determining an altitude of the plurality of altitudes based on the cost value of the cell; and

storing for the time interval and for the one or more cells information indicative of the determined altitude of the plurality of altitudes.

17. The method of claim 1, wherein determining estimated cell locations that are able to be reached by the vehicle by following the wind at the given altitude comprises:

receiving information indicative of an estimated wind direction and speed at the given altitude;

estimating a distance and direction that the vehicle would travel based on the estimated wind direction and speed at the given altitude; and

determining a given cell of the plurality of cells where the vehicle would reside by traveling the estimated distance and direction.

18. The method of claim 17, further comprising:

receiving information indicative of estimated wind directions and speeds at a plurality of altitudes;

estimating distances and directions that the vehicle would travel based on the estimated wind directions and speeds at each of the plurality of altitudes;

determining cells of the plurality of cells where the vehicle would reside by traveling the estimated distances and directions;

assigning cost values to one or more of the cells of the plurality of cells based on a proximity of the cells to the desired location; and

selecting a respective altitude of the plurality of altitudes which results in the vehicle traveling to a respective cell based on a cost value of the respective cell.

19. The method of claim 1, further comprising determining a path for the vehicle to travel to the desired location based on selections of respective altitudes for the vehicle to travel within cells of the plurality of cells.

20. The method of claim 1, wherein determining the estimated cell locations that are able to be reached by the vehicle by following the wind at the given altitude comprises:

receiving, from a given vehicle residing at the given altitude, information indicative of an estimated wind direction and speed at the given altitude; and

estimating a distance and direction that the vehicle would travel based on the estimated wind direction and speed at the given altitude.

21. The method of claim 1, wherein one or more of the at least one processor, the navigation system, and the buoyancy system are included as part of the vehicle.

22. The method of claim 1, wherein one or more of the at least one processor, the navigation system, and the buoyancy system are at a location remote from the vehicle.

23. A system, comprising:

a navigation system;

a buoyancy system;

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, by the at least one processor, information indicative of a desired location within a region for a vehicle to reside, the region being divided into a plurality of cells;

determining, by the at least one processor, estimated cell locations that are able to be reached by the vehicle by following a wind at a given altitude;

assigning, by the at least one processor, a cost value to a given cell of the plurality of cells based on a proximity of the estimated cell locations to a cell that includes the desired location;

determining, by the navigation system, an altitude for the vehicle to travel based on the assigned cost value for the given cell; and

controlling, by the buoyancy system, the vehicle to travel at the determined altitude.

24. The system of claim 23,

wherein the information is further indicative of a desired time period for traveling to the desired location,

wherein determining estimated cell locations that are able to be reached by the vehicle by following a wind at a given altitude comprises:

determining estimated cell locations that are able to be reached by the vehicle over a time interval of the time period by following a wind at a given altitude, and

wherein assigning a cost value to a given cell of the plurality of cells based on a proximity of the estimated cell locations to a cell that includes the desired location comprises;

for the time interval, assigning a cost value to a given cell of the plurality of cells based on a proximity of the estimated cell locations to a cell that includes the desired location.

25. The system of claim 24, wherein determining an altitude for the vehicle to travel based on the assigned cost value for the given cell comprises:

for the time interval, determining an altitude for the vehicle to travel based on the assigned cost value for the given cell.

26. The system of claim 24, wherein the functions further comprise:

for the time interval, assigning a cost value to a given cell of the plurality of cells based on a given cost value assigned to the given cell for a subsequent time interval.

27. The system of claim 24, wherein the time period is divided into a plurality of time intervals and the time interval is one of the plurality of time intervals, wherein the functions further comprise:

determining for each time interval of the plurality of time intervals a map including information per cell indicative of a given cost value and an associated altitude for the vehicle to travel;

receiving information indicative of a fleet of vehicles and associated cells for each vehicle representative of a location of each vehicle;

determining for each time interval of the plurality of time intervals a respective altitude for each vehicle of the fleet of vehicles to travel based on the map for each time interval; and

providing a respective instruction to each vehicle of the fleet of vehicles to travel at the respective altitude for the given time interval and while the vehicle is within a portion of the region designated as a given cell associated with the respective altitude.