Systems, methods, and media for calculating an overbound distribution, from a base mixture distribution, that can be used with a solution-separation RAIM algorithm
An overbound distribution is calculated from a base mixture distribution. For a bounded region, the base distribution is lower-bound at an evaluation point with a second-order polynomial of the base distribution and upper-bound at the evaluation point with a first-order polynomial of a single distribution with a standard deviation value calculated from the base distribution. If the step size from the evaluation point to an intersection of the lower and upper bounds is less than a threshold, the standard deviation value can be iteratively increased until the step size exceeds the threshold. The process is performed for additional portions of the base distribution up to a critical value to determine a final adjusted standard deviation value for the single distribution that is tightly bound to the base distribution and that can be used by a solution algorithm to determine a solution (used to seed filter states for a navigation filter).
1 . A navigation system, comprising:
a module executed by a processor; and
for each of a plurality of different regions that define a base distribution that is a mixture of a plurality of components, the module when executed by the processor configured to:
identify a selected evaluation point of the base distribution;
lower-bound the base distribution at the selected evaluation point utilizing a second-order polynomial of the base distribution thereby defining a lower-bound function, wherein the second-order polynomial is determined utilizing a component mean value and a component standard deviation value for each of the plurality of components associated with the base distribution,
upper-bound the base distribution at the evaluation point utilizing a first-order polynomial of an overbound distribution thereby defining an upper-bound function, wherein the first-order polynomial is determined utilizing a selected mean value and a selected standard deviation value;
determine an intersection of the lower-bound function and the upper-bound function;
increment the selected standard deviation value to an incremented overbound standard deviation value when a step size from the selected evaluation point to the intersection is less than or equal to a threshold value; and
determine, for the base distribution, the overbound distribution based on the selected mean value and the incremented overbound standard deviation value.
2 . The navigation system of claim 1 , wherein the base distribution is a Gaussian mixture and the overbound distribution is a single Gaussian.
3 . The navigation system of claim 1 , wherein the selected mean value is a median of the base distribution.
4 . The navigation system of claim 1 , wherein the second-order polynomial includes (1) a first coefficient that is based on a first value of the base distribution at the selected evaluation point, (2) a second coefficient that is based on a second value of a first order derivative, of the base distribution, at the selected evaluation point, and (3) a third coefficient that is based on a minimum value of a second order derivative, of the base distribution, over a selected region of the base distribution from the selected evaluation point to a different evaluation point.
5 . The navigation system of claim 1 , wherein the first-order polynomial includes (1) a first coefficient that is based on a first value of the overbound distribution at the selected evaluation point, and (2) a second coefficient that is based on a second value of a first order derivative, of the overbound distribution, at the selected evaluation point.
6 . The navigation system of claim 1 , wherein the module when executed by the processor further configured to:
determine that the incremented overbound standard deviation value is valid when the step size from the evaluation point to the intersection is greater than the threshold value; and
determine that the overbound distribution overbounds the base distribution for a selected region of the base distribution defined by the step size.
7 . The navigation system of claim 1 , wherein the module when executed by the processor further configured to:
define a next evaluation point of the base distribution by adding the selected evaluation point to a minimum of (1) a predetermined maximum step size and (2) the step size from the selected evaluation point to the intersection.
8 . The navigation system of claim 1 , further comprising a filter configured to:
execute a solution algorithm; and
use the overbound distribution as an estimate of a filter state during execution of the solution algorithm.
9 . A method for determining an overbound distribution for a base distribution representing a mixture of a plurality of components, the method comprising:
for each of a plurality of different regions that define the base distribution:
identifying a selected evaluation point of the base distribution;
determining a second-order polynomial of the base distribution utilizing a component mean value and a component standard deviation value for each of the plurality of components associated with the base distribution;
lower-bounding the base distribution at the selected evaluation point utilizing the second-order polynomial thereby defining a lower-bound function;
determining a first-order polynomial of the overbound distribution utilizing a selected mean value and a selected standard deviation value;
upper-bounding the base distribution at the evaluation point utilizing the first-order polynomial thereby defining an upper-bound function;
determining an intersection of the lower-bound function and the upper-bound function;
incrementing the selected standard deviation value to an incremented overbound standard deviation value when a step size from the selected evaluation point to the intersection is less than or equal to a threshold value; and
determining, for the base distribution, the overbound distribution based on the selected mean value and the incremented overbound standard deviation value.
10 . The method of claim 9 , wherein the base distribution is a Gaussian mixture and the overbound distribution is a single Gaussian.
11 . The method of claim 9 , wherein the selected mean value is a median of the base distribution.
12 . The method of claim 9 , wherein the second-order polynomial includes (1) a first coefficient that is based on a first value of the base distribution at the selected evaluation point, (2) a second coefficient that is based on a second value of a first order derivative, of the base distribution, at the selected evaluation point, and (3) a third coefficient that is based on a minimum value of a second order derivative, of the base distribution, over a selected region of the base distribution from the selected evaluation point to a different evaluation point.
13 . The method of claim 9 , wherein the first-order polynomial includes (1) a first coefficient that is based on a first value of the overbound distribution at the selected evaluation point, and (2) a second coefficient that is based on a second value of a first order derivative, of the overbound distribution, at the selected evaluation point.
14 . The method of claim 9 , further comprising:
determining that the incremented overbound standard deviation value is valid when the step size from the evaluation point to the intersection is greater than the threshold value; and
determining that the overbound distribution overbounds the base distribution for a selected region of the base distribution defined by the step size.
15 . The method of claim 9 , further comprising:
defining a next evaluation point of the base distribution by adding the selected evaluation point to a minimum of (1) a predetermined maximum step size and (2) the step size from the selected evaluation point to the intersection.
16 . The method of claim 9 , further comprising:
executing a solution algorithm; and
using the overbound distribution as an estimate of a filter state during execution of the solution algorithm.
17 . A non-transitory computer readable medium having software encoded thereon, the software when executed by one or more computing devices operable to:
for each of a plurality of different regions that define a base distribution:
identify a selected evaluation point of the base distribution;
determine a second-order polynomial of the base distribution utilizing a component mean value and a component standard deviation value for each of a plurality of components associated with the base distribution;
lower-bound the base distribution at the selected evaluation point utilizing the second-order polynomial thereby defining a lower-bound function;
determine a first-order polynomial of an overbound distribution utilizing a selected mean value and a selected standard deviation value;
upper-bound the base distribution at the evaluation point utilizing the first-order polynomial thereby defining an upper-bound function;
determine an intersection of the lower-bound function and the upper-bound functon;
increment the selected standard deviation value to an incremented overbound standard deviation value when a step size from the selected evaluation point to the intersection is less than or equal to a threshold value; and
determine, for the base distribution, the overbound distribution based on the selected mean value and the incremented overbound standard deviation value; and
execute a solution algorithm that uses the overbound distribution in determining a solution.
18 . The non-transitory computer readable medium of claim 17 , wherein the base distribution is a Gaussian mixture and the overbound distribution is a single Gaussian.
19 . The non-transitory computer readable medium of claim 17 , wherein the selected mean value is a median of the base distribution.
20 . The non-transitory computer readable medium of claim 17 , wherein
the second-order polynomial includes (1) a first coefficient that is based on a first value of the base distribution at the selected evaluation point, (2) a second coefficient that is based on a second value of a first order derivative, of the base distribution, at the selected evaluation point, and (3) a third coefficient that is based on a minimum value of a second order derivative, of the base distribution, over a selected region of the base distribution from the selected evaluation point to a different evaluation point, and
the first-order polynomial includes (1) a fourth coefficient that is based on a first value of the overbound distribution at the selected evaluation point, and (2) a fifth coefficient that is based on a second value of a first order derivative, of the overbound distribution, at the selected evaluation point.