1. THE COMPLETE TITLE OF ONE (OR MORE) PAPER(S) PUBLISHED IN THE OPEN LITERATURE DESCRIBING THE WORK THAT THE AUTHOR CLAIMS DESCRIBE A
HUMAN-COMPETITIVE RESULT;
Evolved Extended Kalman Filter for first-order dynamical systems with unknown measurements noise covariance
https://doi.org/10.1016/j.asoc.2021.108174
2. THE NAME, COMPLETE PHYSICAL MAILING ADDRESS, E-MAIL ADDRESS, AND PHONE NUMBER AND PHONE NUMBER OF EACH AUTHOR OF EACH PAPER(S);
Leonardo Herrera
Mechanical and Aerospace Engineering Department, NPS, Monterey, CA, United States
leonardo.herrera@nps.edu
ORCID 0000-0001-8989-0617
Phone: +1 (831) 202-1543
M.C.Rodríguez-Liñán
Independent researcher, Toronto, M1L 0C7, ON, Canada
ORCID 0000-0002-3426-8676
Phone: +1 (647) 879 0681
Eddie Clemente
TecNM/I.T. Ensenada, Blvd. Tecnológico 150, Ex-ejido Chapultepec, Zip Code 22780, Ensenada, B.C., Mexico
eclemente@ite.edu.mx
ORCID 0000-0003-3195-9540
Phone: +52 (646) 1174821
Marlen Meza-Sánchez
Tecnm/I.T. Tijuana, Blvd. Industrial s/n, Cd Industrial, Zip Code 22430, Tijuana, B.C., Mexico
iliana.meza@tectijuana.edu.mx, marlen.meza.sanchez@gmail.com
ORCID 0000-0002-1853-5607
Phone: +52 (646) 1312888
Luis Monay-Arredondo, PhD student
TecNM/I.T. Tijuana, Blvd. Industrial s/n, Cd Industrial, Zip Code 22430, Tijuana, B.C., Mexico
luismonay@gmail.com
ORCID 0000-0001-6034-7020
Phone: +52 (646) 1985374
3. CORRESPONDING AUTHOR (I.E., THE AUTHOR TO WHOM NOTICES WILL BE SENT CONCERNING THE COMPETITION)
Marlen Meza-Sánchez
iliana.meza@tectijuana.edu.mx, marlen.meza.sanchez@gmail.com
4. THE ABSTRACT OF THE PAPER(S);
The present work focuses on an open problem in the design of Extended Kalman filters: the lack of knowledge of the measurement noise covariance.
A novel extension of the analytic behaviors framework, which integrates a theoretical formulation and evolutionary computing, has been introduced
as a design methodology for the construction of this unknown parameter. The proposed methodology is developed and applied for the design of
Evolved Extended Kalman Filters for nonlinear first-order dynamical systems. The proposed methodology applies an offline evolutionary synthesis
of analytic nonlinear functions, to be used as measurement noise covariance, aiming to minimize the Kalman criterion. The virtues of the methodology
are exemplified through a complex, highly nonlinear, first-order dynamical system, for which 2649 optimized replacements of the measurement noise
covariance are found. Under different scenarios, the performance of the Evolved Extended Kalman Filter with unknown measurement noise covariance
is compared with that of the conventional Extended Kalman Filter where the measurement noise covariance is known. The robustness of the Evolved
Extended Kalman Filter is demonstrated through numerical evaluation.
5. A LIST CONTAINING ONE OR MORE OF THE EIGHT LETTERS (A, B, C, D, E, F, G, OR H) THAT CORRESPOND TO THE CRITERIA (SEE ABOVE]) THAT THE AUTHOR CLAIMS THAT THE WORK SATISFIES;
(A) The result was patented as an invention in the past, is an improvement over a patented invention, or would qualify today as a patentable new invention.
(D) The result is publishable in its own right as a new scientific result independent of the fact that the result was mechanically created.
(E) The result is equal to or better than the most recent human-created solution to a long-standing problem for which there has been a succession of
increasingly better human-created solutions.
(G) The result solves a problem of indisputable difficulty in its field.
6. A STATEMENT STATING WHY THE RESULT SATISFIES THE CRITERIA THAT THE CONTESTANT CLAIMS (SEE EXAMPLES OF STATEMENTS OF HUMAN-COMPETITIVENESS AS A GUIDE TO AID IN CONSTRUCTING THIS PART OF THE SUBMISSION);
(A) The result was patented as an invention in the past, is an improvement over a patented invention, or would qualify today as a patentable new invention.
Our methodology qualifies as a patent since it is a new offline method that can be used in the design of sensing instruments, since it characterizes the
unknown covariance matrix, R, of the measurement's noise signals in Kalman filtering. GP is used to build nonlinear functions that replace this critical
tuning parameter, which affects the filter’s performance and its internal stability. Furthermore, as some companies patent particular functions, then,
the fittest nonlinear functions discovered by the GP that satisfy both the positive definiteness property and the Kalman criterion of optimality can be
individually patented for a particular system. Thus, from a single implementation and for a particular system, our method has the potential of producing
a large set of patents with the obtained nonlinear functions. Kalman filters are applied in autonomous navigation, aerospace, and industrial sensorless
control, to mention a few. The covariance matrix R of the measurements’ noise is critical for the tuning of Kalman Filters (KFs). If the positive
definiteness property is not satisfied, then the filter is unable to optimally estimate the real values of the system’s states and the estimated values
will be wrong. An inadequate selection of the covariance matrix R, even when fulfilling the positive definite condition, can lead to a poor performance
of the filter. Thus, given the relevance of the Kalman filters within a wide range of applications, providing solutions to the addressed problem is worth
a large portion of the global market size. Since the replacement functions found with GP only use intrinsic variables from the filter and the noisy
measurements of the system, its implementation is straightforward and does not require further adjustments. The introduction of the constructed functions
by the GP to tune an EKF gives rise to the Evolved EKF (EEKF). Numerical assessment demonstrates that this evolved version of the EKF is robust against
parametric uncertainties in the system, against initial condition uncertainties in the filter and the system, and against different noise amplitudes in
the measurements.
A preliminary search shows that our approach is new and can be applied to other patented alternatives. Some found active patents regarding Kalman
Filters and its implementation that can be related to our method are described next.
US20100036613A1 - Methods and systems for implementing an iterated extended kalman filter within a navigation system. Describes the structure of a
discrete version of the EKF where the covariance matrix value, R, is a parameter to be set. Our methodology can be used to set this value.
US20100027603A1 - System and method for automatic recovery and covariance adjustment in linear filters. It applies to any linear filter and a
“communications device [that] includes a time/frequency error measurement circuit that receives a data signal and measures the timing and frequency
errors for the purpose of adjusting the reception system to properly demodulate the data signal… The adjustment uses a multi-level state error
covariance matrix P for controlling/adapting the Kalman gain.” Such a multi-level adaptive system is denoted by a look-up table. It does not consider
any method for the measurement's covariance matrix R, addressed by our method.
US8027741B2 - System and method of improved kalman filtering for estimating the state of a dynamic system. Within this method, “A covariance matrix
associated with state variables of the observer is periodically checked for compliance with a specified condition, e.g., positive definiteness.
If the matrix deviates from the specified condition, the matrix is set to a specified value.” Thus, a default constant value is specified and the
positive-definite condition required for the stability of the filter is checked. Our approach can be an improvement of this patent.
US7209938B2 - Kalman filter with adaptive measurement variance estimator. A particular discrete quadratic function is proposed to estimate the
covariance value of the measurement. First, an “a priori estimate of the input measurement variance R[n] should be used in place of [the proposed]
{circumflex over (R)}[n].” Our method is an alternative to this particular function.
(D) The result is publishable in its own right as a new scientific result independent of the fact that the result was mechanically created.
The analysis of the nonlinear functions built with the GP demonstrates that a large set of them satisfies the positive definiteness property required
for the covariance matrix value to meet the internal stability of the filter. Thus, instead of deriving a single solution, a large set of optimally stable
solutions are constructed with our method. Internal stability is required for the filter to optimally estimate the real values of the system; without it,
the filter is unable to provide estimations correctly. In addition, a poorly estimated value of the measurements’ noise covariance matrix degrades the
performance of the filter. The use of the Kalman criterion (i.e. the minimization of estimation error variance) to guide the evolutionary process
guarantees the optimality of the nonlinear functions, built with GP, as replacements of the measurements’ noise covariance of the EKF. The use of the
functions constructed by the GP, as part of the filter, is theoretically feasible in the EKF; thus, optimal estimation of the real values of the
inaccessible variables of the system is guaranteed. The theory indicates that the EKF can not be outperformed since it is optimal, i.e., the best
according to its criteria. However, in simulation, as well as in practice, the theoretical assumptions made in the KF theory are not perfectly met
(e.g., white Gaussian noise with zero mean is not perfectly guaranteed). Hence, the EEKF, which uses the nonlinear functions built with GP, outperformed
the EKF in our comparison, since the functions were aimed to optimize the same KF criterion under non-strict KF theoretical assumptions. Thus,
independently from the fact that the replacement nonlinear functions were built with GP, the theoretical requirements for a proper design of EKFs are
met by a large set of them.
(E) The result is equal to or better than the most recent human-created solution to a long-standing problem for which there has been a succession of
increasingly better human-created solutions.
The performance of the proposed EEKF has been numerically tested against the original EKF design with known values of the measurements’ covariance matrix R.
The obtained results demonstrate that the EEKF has outperformed the EKF in the Kalman Criterion sense. This advantage is the result of an evolutionary
process that optimizes the same KF criterion under non-strict KF theoretical assumptions. Their performance has also been assessed in scenarios with
variations in the initial condition’s values for both the filter and the system, with uncertainty in the system's model, and with variations in noise
amplitude with respect to those used in the evolutionary process. As mentioned before, the theory indicates that the EKF can not be outperformed since
it is optimal. However, both in simulation and in practice, the theoretical assumptions made in the KF theory are not perfectly met (e.g., white Gaussian
noise with zero mean is not perfectly guaranteed). In addition, instead of proposing a single solution, a large set of theoretically feasible replacement
functions for the critical tuning parameter R is found with the GP implementation for a particular system. In contrast, the human-created solutions to
this issue can be summarized by patented alternatives with a single solution based on features, such as look-up tables, some particular functions,
recursive algorithms using the noisy measurements, and stability checking methods. A Kalman-related approach to a machine-produced solution found
in the literature is a patent application made by Apple Inc. where a machine learning model of a satellite-based positioning system is constructed and
fed to a traditional EKF (See application US 2020/0049837 A1, Feb 2020).
(G) The result solves a problem of indisputable difficulty in its field.
Since the publication of the Kalman Filter in the 1960s, the selection of the required noise covariance matrices that condition the performance of the
filter has been a long-standing problem. Incongruence in this selection leads to poor performance of the filter, as the noise in the measurements won't
be properly represented. As a consequence, optimality in the Kalman sense, which is the essence of the filter, is not guaranteed. This issue has been
addressed by proposing estimated values complying with the positive-definiteness property of the covariance matrices to guarantee the internal stability
of the filter. Active patents show many approaches, from using functions based on the output errors between the filter and the noisy measurements to
default selected values, and some methods to check the stability of the filter. Thus, our approach provides an offline method to build nonlinear functions,
based only on intrinsic variables of the filter and the noisy measurements, that outperform the original EKF design, since it adapts to non-perfect
zero-mean white Gaussian noise. Such constructed functions have been numerically assessed by introducing variations in the values of the initial condition
of the filter and system, by assuming uncertainty in the system's model, and by increasing the noise amplitudes in the measurements. Furthermore,
such features are demonstrated using a logistic map system, as a motivating example, since it possesses a rich variety of behaviors ranging from
stable fixed points to chaos.
7. A FULL CITATION OF THE PAPER (THAT IS, AUTHOR NAMES; PUBLICATION DATE; NAME OF JOURNAL, CONFERENCE, TECHNICAL REPORT, THESIS, BOOK, OR BOOK CHAPTER; NAME OF EDITORS, IF APPLICABLE, OF THE JOURNAL OR EDITED BOOK; PUBLISHER NAME; PUBLISHER CITY; PAGE NUMBERS, IF APPLICABLE);
Leonardo Herrera, M.C. Rodríguez-Liñán, Eddie Clemente, Marlen Meza-Sánchez, Luis Monay-Arredondo, Evolved Extended Kalman Filter for first-order
dynamical systems with unknown measurements noise covariance, Applied Soft Computing, Volume 115, 2022, 108174, ISSN 1568-4946,
https://doi.org/10.1016/j.asoc.2021.108174.
(https://www.sciencedirect.com/science/article/pii/S1568494621010280)
8. A STATEMENT EITHER THAT "ANY PRIZE MONEY, IF ANY, IS TO BE DIVIDED EQUALLY AMONG THE CO-AUTHORS" OR A SPECIFIC PERCENTAGE BREAKDOWN AS TO HOW THE
PRIZE MONEY, IF ANY, IS TO BE DIVIDED AMONG THE CO-AUTHORS;
Any prize money, if any, is to be divided equally among all the co-authors.
9. A STATEMENT STATING WHY THE AUTHORS EXPECT THAT THEIR ENTRY WOULD BE THE "BEST",
The Kalman Filter is one of the most important and common estimation algorithms, and it has played a key role in many science fields since its conception
by Rudolph Kalman in 1960. Kalman filtering has far outgrown NASA’s applications, where it stands out in the overwhelming success of the Lunar Landing
Program with the onboard navigation systems for the Apollo Command Module and the Apollo Lunar Excursion Module. It has also been applied in the
development of navigation systems for the Lockheed C-5A aircraft programs, using where inertial data and from several sensors, to produce estimates
of the aircraft’s states. Lockheed Missiles and Space Company used the Extended Kalman Filter to validate the performance of the Agena program in its
upper stage. Square-root Kalman filters have been applied to airborne applications by NASA. From there, the number of shuttles and robotic missions
using Kalman filtering techniques is countless. In particular, the Extended Kalman Filter is a powerful estimation technique applied to nonlinear systems.
From all the areas of application of Kalman filters, the most prominent are the aerospace and the defense industry, which, in the US, amounted to $874B
in total sales revenue, employing over 2 million workers, in 2020. It is hard to find open information about the defense industry, but according to
Defense Daily (https://www.defensedaily.com/defense-watch-356/), the certified US Air Force’s Global Positioning System Operational Control System
(GPS OCX) that provides precision navigation and timing (PNT) capabilities in a fully-hardened cyber environment that runs with Kalman filters.
According to Hays & Fatemi (https://www.jhuapl.edu/Content/techdigest/pdf/V35-N02/35-02-Hays.pdf), both from the Air and Missile Defense Sector from
the Johns Hopkins University Applied Physics Laboratory, Laurel, MD, the Extended Kalman Filter (EKF) is applied in the development of combat systems
based on air and missile defense systems. Toyota Motor Corp, Waymo, Honda, Apple, Tesla have patents that use Kalman Filters for the development of
positioning systems that can be used in autonomous cars. The autonomous cars market size in the US, in 2020, was $1.45B. Nowadays, we can also find
the Kalman Filter in industrial applications where it is required for the prediction of variables (see e.g. sensorless techniques for industrial robots),
for the estimation of variables that cannot be directly measured, and it can also be used to merge measurements from several sensors in onboard navigation
systems. Techniques based on state observers and Extended Kalman filters have been developed for sensorless rotor position estimation of Permanent Magnet
Synchronous Motor (PMSM) drives. For instance, sensorless controllers by Maxon for Brushless DC motors integrate observers and Kalman filters as estimation
methods in the control algorithm. The industrial robotics market, another important application of Kalman Filters, is expected to reach a global market
size of $214B by 2030, with key companies like Universal Robots A/S, part of Teradyne Inc., (Denmark), Kawasaki Heavy Industries (Japan) and Boston
Dynamics (USA) leading the way.
Bearing in mind the relevance of the addressed problem in Kalman Filtering, we believe that our work has several merits and contributions to the
state-of-the-art and to the development of practical and industrial applications,
a) We have proposed a novel method that applies GP for the construction of nonlinear functions as a solution of a long-standing problem, critical
for the performance of Kalman Filters: a replacement for the unknown covariance matrix value for the noise present in the system measurements.
Our approach considers their application to first-order nonlinear dynamical systems.
b) The method has the potential of being patentable since it addresses a long-standing open problem in the design of Kalman Filters within a large
global market size. Our preliminary search gave active patents from the United States Department of the Navy, Apple, Lockheed Martin Corp, Honeywell
International Inc, and North South Holdings Inc, that can be related with the addressed problem, where look-up tables, quadratic functions,
optimization techniques searching for constant values, and default estimated constant values are considered. Our method can be used for the design
of replacement functions that can also be individually patented for a particular nonlinear system.
f) The design of the method with GP is based on assumptions made in the KF theory. This feature provides a guided search for the evolutionary construction
of the nonlinear functions for the unknown measurements’ noise covariance. Thus, the GP requires a small set of runs and populations, in comparison with
the settings traditionally used in ML approaches.
g) The theoretical stability of the filter can be guaranteed since many of the found functions can be demonstrated to fulfill the positive definiteness
property required for the covariance matrix value. Therefore, the use of those functions is theoretically feasible in the EKF.
h) The methodology has been outlined for first-order dynamic nonlinear systems, where the Kalman criterion has been applied as the fitness function to be
optimized for the construction of the functions. Our methodology builds the nonlinear functions employing an evolutionary process based on GP. Thus,
optimal performance of the EKF, using the replacement functions for the unknown measurements’ noise covariance, is set by design. This feature leads
to the outperformance of the EKF with the functions evolved by the GP against the original EKF design, as the functions were aimed to optimize the same
KF criterion under non-strict theoretical KF assumptions.
c) Our paper demonstrates key practical advantages over existing human-made solutions. The found nonlinear functions are constructed using variables
from the filter and the noisy measurements of the system, which makes their implementation straightforward. The results presented for consideration
move from a theoretical problem of great importance, to applications where it can have a practical use. Numerical assessments demonstrate better performance
since the value of the constructed functions adapts better to the characteristics of the only available readings of the system (that is, the measurement’s
noisy signal).
d) The produced Evolved Extended Kalman Filters, constructed with the nonlinear functions built with GP, provide better performance than the original
design of the Extended Kalman Filter. This can be explained due to the theoretical conditions not being perfectly satisfied, since, experimentally,
or even in simulation, a White Gaussian Noise with zero mean is not truly accomplished.
e) Robustness of the Evolved Extended Kalman Filters generated with our method. Our approach has been numerically assessed in a logistic map system,
this being a nonlinear system, widely used in many research fields, with the feature of possessing a rich variety of behaviors, ranging from stable
fixed points to chaos. Our results demonstrate an optimal performance with the introduction of variations in the values of the initial condition of
the filter, with uncertainty in the system's model, and with variations in the noise amplitudes present in the measurements.
10. AN INDICATION OF THE GENERAL TYPE OF GENETIC OR EVOLUTIONARY COMPUTATION USED, SUCH AS GA (GENETIC ALGORITHMS), GP (GENETIC PROGRAMMING),
ES (EVOLUTION STRATEGIES), EP (EVOLUTIONARY PROGRAMMING), LCS (LEARNING CLASSIFIER SYSTEMS), GE (GRAMMATICAL EVOLUTION), GEP (GENE EXPRESSION PROGRAMMING),
DE (DIFFERENTIAL EVOLUTION), ETC.
GP (Genetic Programming)
11. THE DATE OF PUBLICATION OF EACH PAPER. IF THE DATE OF PUBLICATION IS NOT ON OR BEFORE THE DEADLINE FOR SUBMISSION, BUT INSTEAD, THE PAPER HAS BEEN
UNCONDITIONALLY ACCEPTED FOR PUBLICATION AND IS “IN PRESS” BY THE DEADLINE FOR THIS COMPETITION, THE ENTRY MUST INCLUDE A COPY OF THE DOCUMENTATION
ESTABLISHING THAT THE PAPER MEETS THE "IN PRESS" REQUIREMENT.
Publication date: JANUARY, 2022
Record of publication https://doi.org/10.1016/j.asoc.2021.108174:
Received 19 May 2021, Revised 9 October 2021, Accepted 10 November 2021,
Available online 5 December 2021, Version of Record 17 December 2021.