Reverse iteration of planning data for system control

• US 9,201,426 B1
• Filed: 02/19/2014
• Issued: 12/01/2015
• Est. Priority Date: 02/19/2014
• Status: Expired due to Fees

• Current Assignee: Loon, LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Bonawitz, Keith Allen
• Primary Examiner(s): Cheung, Calvin
• Assistant Examiner(s): Martinez Borrero, Luis A.
• Application Number:
  US14/183,771
• Time in Patent Office: 650 Days
• Field of Search: 701/3, 701/2, 701/25, 701/26, 701/42, 701/24, 701/50, 701/22, 701/48, 701/70, 701/93, 701/466, 706/20, 706/23, 706/15, 706/27, 706/16
• US Class Current: 1/1
• 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: G05D 1/105 specially adapted for unpowered flight, e.g. glider, parachuting, forced landing parachutes per se B64D17/00

Abstract

Methods and systems for reverse-iterating a backward planner determining trajectories for vehicles of a fleet of vehicles are provided. In one example an iterator configured for recursively determining the contingency tables at successive time steps in a computational iteration order from a target time to an initial time is caused to reverse-generate the contingency tables in an order from the initial time to the target time. Reverse-generation is caused by recursively: (i) subdividing a sequence of time steps by a factor of at least two into successively smaller sub-sequences, (ii) iterating in a computational iteration order over each recursively subdivided sub-sequence, and (iii) generating a contingency table closest in time to the initial time for the recursive iteration over each recursively subdivided sub-sequence.

Claims

1. A method for planning balloon flight states configured to cause at least one balloon to fly substantially along a predicted path, the method comprising:

at a system including one or more processors, receiving a specification for N time steps at which to compute N corresponding contingency tables of contingent balloon flight states for the at least one balloon, wherein the N time steps define a sequence of time steps in a range between an initial time and a target time;

by an iterator implemented by at least one of the one or more processors, reverse-accessing the N contingency tables in an order from the initial time to the target time, wherein the iterator is configured for recursively determining the contingency tables at successive time steps in a computational iteration order from the target time to the initial time;

for the at least one balloon, determining a sequence of planned balloon flight states from the reverse-accessed contingency tables, ordered from the initial time to the target time, corresponding to a predicted balloon flight trajectory that is within a threshold of a quantitative flight-plan objective; and

causing the at least one balloon to execute at least one flight command from the determined sequence of planned balloon flight states, to cause the at least one balloon to attempt to follow at least a portion of the predicted flight trajectory,

wherein reverse-accessing the N contingency tables in the order from the initial time to the target time is achieved in O(N log₂ N) iterations using memory for O(log₂ N) contingency tables, and comprises;

recursively (i) subdividing the sequence of time steps by a factor of at least two into successively smaller sub-sequences, (ii) iterating in the computational iteration order over each recursively subdivided sub-sequence, and (iii) accessing a contingency table closest in time to the initial time for the recursive iteration over each recursively subdivided sub-sequence.

2. The method of claim 1, wherein receiving the specification for N time steps comprises receiving the initial time, the target time, and a time-step size, and wherein N is determined as a difference between the initial time and the target time divided by the time-step size.

3. The method of claim 1, wherein each of the contingent balloon flight states comprises a latitude state variable, a longitude state variable, an altitude state variable, and a battery level state variable, wherein the contingency tables include at each of the N time steps one or more contingent balloon flight states each having a contingent flight action and a respective target location for the at least one balloon that is predicted to be reachable at the target time by a sequence of contingent balloon flight states at intervening time steps, and wherein each of the one or more contingent balloon flight states at each of the N time steps is assigned a respective score based on a distance between its respective target location and a goal location for the at least one balloon, the goal location being the same for all of the one or more contingent balloon flight states of the at least one balloon, and score increasing inversely to distance between target location and goal location.

4. The method of claim 3, wherein determining the sequence of planned balloon flight states from the reverse-accessed contingency tables comprises determining a sequence of planned flight actions to execute at each of the N time steps by choosing one contingent flight action from each of the N time steps such that a predicted target location for the sequence of planned flight actions is closest to the goal location.

5. The method of claim 4, wherein determining the sequence of planned flight actions to execute at each of the N time steps by choosing one contingent flight action from each of the N time steps such that the predicted target location for the sequence of planned flight actions is closest to the goal location comprises:

simulating one or more balloon flight trajectories by simulating execution of each of one or more sequences of contingent flight actions, each of the one or more sequences of contingent flight actions including one contingent flight action from each of the N time steps and being ordered from the initial time to the target time; and

determining a particular sequence of contingent flight actions from among the one or more sequences of contingent flight actions for which a simulated target location is closest to the goal location.

6. The method of claim 3, wherein the contingent flight action for each of the one or more contingent flight states is one of three action commands to execute at a specified time, the three action commands being increase balloon altitude, decrease balloon altitude, and maintain balloon altitude.

7. The method of claim 3, wherein the initial time is chronologically earlier than the target time, wherein the at least one balloon is projected to be at the goal location at the target time, and wherein recursively determining the contingency tables at successive time steps in a computational iteration order from the target time to the initial time comprises recursively determining in backward chronological order at least one backward sequence of contingent balloon flight states from the goal location at the target time to an initial contingent balloon flight state at the initial time.

8. 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 for planning balloon flight states configured to cause at least one balloon to fly substantially along a predicted path, the functions comprising:

receiving a specification for N time steps at which to compute N corresponding contingency tables of contingent balloon flight states for the at least one balloon, wherein the N time steps define a sequence of time steps in a range between an initial time and a target time;

reverse-accessing the N contingency tables in an order from the initial time to the target time by using an iterator function configured for recursively determining the contingency tables at successive time steps in a computational iteration order from the target time to the initial time;

for the at least one balloon, determining a sequence of planned balloon flight states from the reverse-accessed contingency tables, ordered from the initial time to the target time, corresponding to a predicted balloon flight trajectory that is within a threshold of a quantitative flight-plan objective; and

causing the at least one balloon to execute at least one flight command from the determined sequence of planned balloon flight states, to cause the at least one balloon to attempt to follow at least a portion of the predicted flight trajectory,

wherein reverse-accessing the N contingency tables in the order from the initial time to the target time is achieved in O(N log₂ N) iterations using memory for O(log₂ N) contingency tables, and comprises;

recursively (i) subdividing the sequence of time steps by a factor of at least two into successively smaller sub-sequences, (ii) iterating in the computational iteration order over each recursively subdivided sub-sequence, and (iii) accessing a contingency table closest in time to the initial time for the recursive iteration over each recursively subdivided sub-sequence.

9. The non-transitory computer-readable storage medium of claim 8, wherein receiving the specification for N time steps comprises receiving the initial time, the target time, and a time-step size, and wherein N is determined as a difference between the initial time and the target time divided by the time-step size.

10. The non-transitory computer-readable storage medium of claim 8, wherein each of the contingent balloon flight states comprises a latitude state variable, a longitude state variable, an altitude state variable, and a battery level state variable, wherein the contingency tables include at each of the N time steps one or more contingent balloon flight states each having a contingent flight action and a respective target location for the at least one balloon that is predicted to be reachable at the target time by a sequence of contingent balloon flight states at intervening time steps, and wherein each of the one or more contingent balloon flight states at each of the N time steps is assigned a respective score based on a distance between its respective target location and a goal location for the at least one balloon, the goal location being the same for all of the one or more contingent balloon flight states of the at least one balloon, and score increasing inversely to distance between target location and goal location.

11. The non-transitory computer-readable storage medium of claim 10, wherein determining the sequence of planned balloon flight states from the reverse-accessed contingency tables comprises determining a sequence of planned flight actions to execute at each of the N time steps by choosing one contingent flight action from each of the N time steps such that a predicted target location for the sequence of planned flight actions is closest to the goal location.

12. The non-transitory computer-readable storage medium of claim 11, wherein determining the sequence of planned flight actions to execute at each of the N time steps by choosing one contingent flight action from each of the N time steps such that the predicted target location for the sequence of planned flight actions is closest to the goal location comprises:

simulating one or more balloon flight trajectories by simulating execution of each of one or more sequences of contingent flight actions, each of the one or more sequences of contingent flight actions including one contingent flight action from each of the N time steps and being ordered from the initial time to the target time; and

determining a particular sequence of contingent flight actions from among the one or more sequences of contingent flight actions for which a simulated target location is closest to the goal location.

13. The non-transitory computer-readable storage medium of claim 10, wherein the contingent flight action for each of the one or more contingent flight states is one of three action commands to execute at a specified time, the three action commands being increase balloon altitude, decrease balloon altitude, and maintain balloon altitude.

14. The non-transitory computer-readable storage medium of claim 10, wherein the initial time is chronologically earlier than the target time, wherein the at least one balloon is projected to be at the goal location at the target time, and wherein recursively determining the contingency tables at successive time steps in a computational iteration order from the target time to the initial time comprises recursively determining in backward chronological order at least one backward sequence of contingent balloon flight states from the goal location at the target time to an initial contingent balloon flight state at the initial time.

15. A system for planning balloon flight states configured to cause at least one balloon to fly substantially along a predicted path, the 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 specification for N time steps at which to compute N corresponding contingency tables of contingent balloon flight states for the at least one balloon, wherein the N time steps define a sequence of time steps in a range between an initial time and a target time;

reverse-accessing the N contingency tables in an order from the initial time to the target time by using an iterator function configured for recursively determining the contingency tables at successive time steps in a computational iteration order from the target time to the initial time;

for the at least one balloon, determining a sequence of planned balloon flight states from the reverse-accessed contingency tables, ordered from the initial time to the target time, corresponding to a predicted balloon flight trajectory that is within a threshold of a quantitative flight-plan objective; and

causing the at least one balloon to execute at least one flight command from the determined sequence of planned balloon flight states, to cause the at least one balloon to attempt to follow at least a portion of the predicted flight trajectory,

wherein reverse-accessing the N contingency tables in the order from the initial time to the target time is achieved in O(N log₂ N) iterations using memory for O(log₂ N) contingency tables, and comprises;

recursively (i) subdividing the sequence of time steps by a factor of at least two into successively smaller sub-sequences, (ii) iterating in the computational iteration order over each recursively subdivided sub-sequence, and (iii) accessing a contingency table closest in time to the initial time for the recursive iteration over each recursively subdivided sub-sequence.

16. The system of claim 15, wherein receiving the specification for N time steps comprises receiving the initial time, the target time, and a time-step size, and wherein N is determined as a difference between the initial time and the target time divided by the time-step size.

17. The system of claim 15, wherein each of the contingent balloon flight states comprises a latitude state variable, a longitude state variable, an altitude state variable, and a battery level state variable, wherein the contingency tables include at each of the N time steps one or more contingent balloon flight states each having a contingent flight action and a respective target location for the at least one balloon that is predicted to be reachable at the target time by a sequence of contingent balloon flight states at intervening time steps, and wherein each of the one or more contingent balloon flight states at each of the N time steps is assigned a respective score based on a distance between its respective target location and a goal location for the at least one balloon, the goal location being the same for all of the one or more contingent balloon flight states of the at least one balloon, and score increasing inversely to distance between target location and goal location.

18. The system of claim 17, wherein determining the sequence of planned balloon flight states from the reverse-accessed contingency tables comprises determining a sequence of planned flight actions to execute at each of the N time steps by choosing one contingent flight action from each of the N time steps such that a predicted target location for the sequence of planned flight actions is closest to the goal location.

19. The system of claim 18, wherein determining the sequence of planned flight actions to execute at each of the N time steps by choosing one contingent flight action from each of the N time steps such that the predicted target location for the sequence of planned flight actions is closest to the goal location comprises:

simulating one or more balloon flight trajectories by simulating execution of each of one or more sequences of contingent flight actions, each of the one or more sequences of contingent flight actions including one contingent flight action from each of the N time steps and being ordered from the initial time to the target time; and

determining a particular sequence of contingent flight actions from among the one or more sequences of contingent flight actions for which a simulated target location is closest to the goal location.

20. The system of claim 15, wherein the contingent flight action for each of the one or more contingent flight states is one of three action commands to execute at a specified time, the three action commands being increase balloon altitude, decrease balloon altitude, and maintain balloon altitude.

21. The system of claim 15, wherein the initial time is chronologically earlier than the target time, wherein the at least one balloon is projected to be at the goal location at the target time, and wherein recursively determining the contingency tables at successive time steps in a computational iteration order from the target time to the initial time comprises recursively determining in backward chronological order at least one backward sequence of contingent balloon flight states from the goal location at the target time to an initial contingent balloon flight state at the initial time.