System and method for optimizing aircraft flight path
First Claim
1. A system for determining an optimal path for an aircraft to fly from position to a second position so that the aircraft heading at the second position is within preselected minimum and maximum heading limits, said system comprising:
- means for constructing a reference grid, the length of which is oriented along a first axis connecting said first and second positions so that said first axis corresponds to the centerline of the grid and the width of which corresponds to a preselected width along a second axis which is perpendicular to said first axis, said grid being divided into N number of ranks in succession between said first and second positions, said first position being at the center of the first rank and said second position being adjacent to the center of the Nth rank, each of said ranks spanning the entire width of said grid and being divided into a predetermined number of rectangular cells;
means for determining connected cells in said Nth rank, the connected cells in the Nth rank being those cells from which the aircraft can reach said second position within the preselected minimum and maximum heading limits without exceeding the maximum lateral acceleration allowed for the aircraft;
means for determining the cost of flying from each of the connected cells in the Nth rank to said second position based on a preselected cost function;
means for determining corresponding minimum and maximum heading limits at each of the connected cells in the Nth rank, said minimum and maximum heading limits representing a range of allowed headings for the aircraft at the corresponding connected cell which will enable the aircraft to reach the second position within the preselected minimum and maximum heading limits without exceeding the maximum lateral acceleration;
means for determining connected paths between each pair of adjacent ranks (i-1) and i in sequence beginning with i=N and ending with i=2, each of said connected paths representing a discrete connection between a specified cell in the (i-1)th rank and a specified connected cell in the ith rank whereby the aircraft can reach the specified cell in the ith rank within the corresponding heading limits from the specified cell in the (i-1)th rank without exceeding the maximum lateral acceleration, each of the cells in the (i-1)th rank from which the aircraft can reach at least one of the connected cells in the ith rank within the corresponding heading limits without exceeding the maximum lateral acceleration being a connected cell in the (i-1)th rank;
means for determining the cost of flying from the (i-1)th rank to the ith rank along each of said connected paths and for determining the minimum cost of flying from each of the connected cells in the (i-1)th rank to said second position based on a preselected cost function for each rank in sequence beginning with i=N and ending with i=2;
means for storing the corresponding path of minimum cost between each connected cell in the (i-1)th rank and the second position and the corresponding cost of said minimum cost path for each of the connected cells in the (i-1)th rank, for each rank in sequence beginning with i=N and ending with i=2;
means for determining corresponding minimum and maximum heading limits for each of the connected cells in the (i-1)th rank, for each rank in sequence beginning with i=N and ending with i=2, said heading limits representing a range of allowed headings for the aircraft at the corresponding connected cell in the (i-1)th rank which will enable the aircraft to reach a particular one of the connected cells in the ith rank within the corresponding heading limits without exceeding the maximum lateral acceleration, said particular connected cell in the ith rank being that cell which lies on the path of minimum cost between the corresponding connected cell in the (i-1)th rank and the second position;
means for determining particular ones of the connected cells in the second rank which the aircraft can reach from said first position within the corresponding heading limits without exceeding the maximum lateral acceleration;
means for determining the cost of flying from said first position to each of said particular connected cells and for determining the path of minimum cost of flying from said first position to said second position, said minimum cost path being the optimal flight path for the aircraft between said first and second positions; and
means for determining corresponding minimum and maximum heading limits at the first position, said heading limits representing a range of allowed headings for the aircraft at the first position which will enable the aircraft to reach the particular connected cell in the second rank which lies on the path of minimum cost between the first and second positions.
1 Assignment
0 Petitions
Accused Products
Abstract
A system and method for determining the optimal path for an aircraft to fly from a first position to a second position so that the aircraft heading at the second position is within preselected minimum and maximum heading limits. A two-dimensional reference grid is constructed so that the first position is in the center cell of the first rank of the grid and the second position is adjacent to the center cell of the last rank thereof. Dynamic programming techniques are used to determine the possible flight paths between the first and second positions and to select the path of minimum cost as the optimal path. The possible flight paths are constructed by identifying the possible connections between the last rank and the second postion and then between each pair of adjacent ranks, working backward from the last rank to the first position, which is located in the first rank. A possible connection is deemed to exist when the aircraft can fly from one point to a target point (e.g., between specified cells in adjacent ranks) and arrive at the target point within particular heading limits without exceeding the predetermined maximum lateral acceleration of the aircraft. Corresponding heading limits are determined for each "connected" cell in the grid, so that all possible flight paths are examined, consistent with the preselected heading limits at the second position (e.g., the target area) and the maximum lateral acceleration allowed for the aircraft.
129 Citations
10 Claims
-
1. A system for determining an optimal path for an aircraft to fly from position to a second position so that the aircraft heading at the second position is within preselected minimum and maximum heading limits, said system comprising:
-
means for constructing a reference grid, the length of which is oriented along a first axis connecting said first and second positions so that said first axis corresponds to the centerline of the grid and the width of which corresponds to a preselected width along a second axis which is perpendicular to said first axis, said grid being divided into N number of ranks in succession between said first and second positions, said first position being at the center of the first rank and said second position being adjacent to the center of the Nth rank, each of said ranks spanning the entire width of said grid and being divided into a predetermined number of rectangular cells; means for determining connected cells in said Nth rank, the connected cells in the Nth rank being those cells from which the aircraft can reach said second position within the preselected minimum and maximum heading limits without exceeding the maximum lateral acceleration allowed for the aircraft; means for determining the cost of flying from each of the connected cells in the Nth rank to said second position based on a preselected cost function; means for determining corresponding minimum and maximum heading limits at each of the connected cells in the Nth rank, said minimum and maximum heading limits representing a range of allowed headings for the aircraft at the corresponding connected cell which will enable the aircraft to reach the second position within the preselected minimum and maximum heading limits without exceeding the maximum lateral acceleration; means for determining connected paths between each pair of adjacent ranks (i-1) and i in sequence beginning with i=N and ending with i=2, each of said connected paths representing a discrete connection between a specified cell in the (i-1)th rank and a specified connected cell in the ith rank whereby the aircraft can reach the specified cell in the ith rank within the corresponding heading limits from the specified cell in the (i-1)th rank without exceeding the maximum lateral acceleration, each of the cells in the (i-1)th rank from which the aircraft can reach at least one of the connected cells in the ith rank within the corresponding heading limits without exceeding the maximum lateral acceleration being a connected cell in the (i-1)th rank; means for determining the cost of flying from the (i-1)th rank to the ith rank along each of said connected paths and for determining the minimum cost of flying from each of the connected cells in the (i-1)th rank to said second position based on a preselected cost function for each rank in sequence beginning with i=N and ending with i=2; means for storing the corresponding path of minimum cost between each connected cell in the (i-1)th rank and the second position and the corresponding cost of said minimum cost path for each of the connected cells in the (i-1)th rank, for each rank in sequence beginning with i=N and ending with i=2; means for determining corresponding minimum and maximum heading limits for each of the connected cells in the (i-1)th rank, for each rank in sequence beginning with i=N and ending with i=2, said heading limits representing a range of allowed headings for the aircraft at the corresponding connected cell in the (i-1)th rank which will enable the aircraft to reach a particular one of the connected cells in the ith rank within the corresponding heading limits without exceeding the maximum lateral acceleration, said particular connected cell in the ith rank being that cell which lies on the path of minimum cost between the corresponding connected cell in the (i-1)th rank and the second position; means for determining particular ones of the connected cells in the second rank which the aircraft can reach from said first position within the corresponding heading limits without exceeding the maximum lateral acceleration; means for determining the cost of flying from said first position to each of said particular connected cells and for determining the path of minimum cost of flying from said first position to said second position, said minimum cost path being the optimal flight path for the aircraft between said first and second positions; and means for determining corresponding minimum and maximum heading limits at the first position, said heading limits representing a range of allowed headings for the aircraft at the first position which will enable the aircraft to reach the particular connected cell in the second rank which lies on the path of minimum cost between the first and second positions. - View Dependent Claims (2, 3, 4)
-
-
5. A method for determining the optimal path for an aircraft to fly from a first position to a second position so that the aircraft heading at the second position is within preselected minimum and maximum heading limits, said method comprising the steps of:
-
constructing a referecne grid, the length of which is oriented along a first axis connecting said first and second positions so that the first axis corresponds to the centerline of the grid and the width of which corresponds to a preselected width along a second axis which is perpendicular to said first axis, said grid being divided into N number of ranks in succession between said first and second positions, said first position being at the center of the first rank and said second position being adjacent to the center of the Nth rank, each of said ranks spanning the entire width of said grid and being divided into a predetermined number of rectangular cells; determining connected cells in said Nth rank, the connected cells in the Nth rank being those cells from which the aircraft can reach said second position within the preselected minimum and maximum heading limits without exceeding the maximum lateral acceleration allowed for the aircraft; determining the cost of flying from each of the conencted cells in the Nth rank to said second position based on a preselected cost function; determining the corresponding heading limits at each of the connected cells in the Nth rank, said heading limits representing a range of allowed headings for the aircraft at the corresponding connected cell in the Nth rank from which the aircraft can reach the second position within the preselected minimum and maximum heading limits; and performing the following steps for each pair of adjacent ranks in sequence beginning with i=N and ending with i=2; determining connected paths between each pair of adjacent ranks (i-1) and i, each of said connected paths representing a discrete connection between a specified cell in the (i-1)th rank and a specified connected cell in the ith rank whereby the aircraft can reach the specified cell in the ith rank within the corresponding heading limits from the specified cell in the (i-1)th rank without exceeding the maximum lateral acceleration, each of the cells in the (i-1)th rank from which the aircraft can reach at least one of the connected cells in the ith rank within the corresponding heading limits without exceeding the maximum lateral acceleration being a connected cell in the (i-1)th rank; determining the cost of flying from the (i-1)th rank to the ith rank along each of said connected paths and determining the minimum cost of flying from each of the connected cells in the (i-1)th rank to said second position based on the preselected cost function; storing the corresponding path of minimum cost between each connected cell in the (i-1)th rank and the second position and the corresponding cost of said minimum cost path for each of the connected cells in the (i-1)th rank; and determining corresponding minimum and maximum heading limits for each of the connected cells in the (i-1)th rank, said heading limits representing a range of allowed headings for the aircraft at the corresponding connected cell in the (i-1)th rank which will enable the aircraft to reach a particular one of the connected cells in the ith rank with the corresponding heading limits without exceeding the maximum lateral acceleration, said particular connected cell in the ith rank being that cell which lies on the path of minimum cost between the corresponding connected cell in the (i-1)th rank and the second position. - View Dependent Claims (6, 7, 8, 9, 10)
-
Specification