Bayesian FilteringOverview of Bayesian filtering with the Filtering Classes |
mail@michael-stevens.de |
Documentation generated by DoxygenFilter hierarchy |
Project Summary and Download
|
Bayesian Filtering is a probabilistic technique for data fusion. The technique combines a concise mathematical formulation of a system with observations of that system. Probabilities are used to represent the state of a system, likelihood functions to represent their relationships. In this form Bayesian inference can be applied and further related probabilities deduced. See Wikipedia for information on Probability theory, Bayes theorem, Bayesian Inference.
For discrete systems the Bayesian formulation results in a naturally iterative data fusion solution. For dynamic systems there is a class of solutions, discrete filters, that combine observed outputs of the system with the system's dynamic model. An estimator computes a estimate of the systems state with each observation of the system. Linear estimators such as the Kalman Filter are commonly applied.
Bayes++ is an open source library of C++ classes. These classes represent and implement a wide variety of numerical algorithms for Bayesian Filtering of discrete systems. The classes provide tested and consistent numerical methods and the class hierarchy explicitly represents the variety of filtering algorithms and system model types.
This is very simple example; for those who have never used the Bayesian Filtering Classes before. If you wish to see how simple it is to use Bayes++ then View the Source.
The example shows how two classes are created. The first is the prediction model, the second the observation model. In this example they represent a simple linear problem with only one state variable and constant model noises. A filter fuses the results of prediction and observation.
See the Bayesian Filtering classes for a description of the classes used and all three examples provided with Bayes++.
First download and extract Bayes++ and also the Boost library. Boost is used to provide compiler independence, and a common build system. Two Boost header libraries are used: uBLAS for linear algebra, and random for the PV and QuadCalib examples. The Boost headers can be placed anywhere relative to Bayes++, but it is easy if you follow this structure:
Using the Boost Build system version 2 is the best way to compile the
examples. Use the b2 (Boost jam) program to build Bayes++ in
a single step. The documentation in your
downloaded copy of Boost explains how to obtain and install the latest
version of the Boost Build system yourself. For everything to work execute b2
with the required toolset, and the location where you installed Boost.
To build Bayes++ and the examples with GCC simply execute: (Bayes++ should be the current directory)
b2 toolset=gcc link=static cxxflags=-Wno-unused-local-typedefs -sBOOST_ROOT="../boost_1_55_0"
OR for Visual C++ execute:
b2 toolset=msvc link=static -sBOOST_ROOT="../boost_1_55_0"
It is possible to work without the BOOST_ROOT variable by either creating a build_build.jam file in sourceDirectory (or above) or by setting it as an environment variable.
The executables for the three examples will be placed inside a directory hierarchy named target. Static libraries for debug and release builds of the BayesFilter library are placed in target/BayesFilter. The target directory and its subdirectories are created automatically.
For Visual C++ 2008 etc, you can also use the Bayes++.sln solution and the active configuration uBLAS Debug. The compiler options must be set so the Boost include files can be found. That is, the include path must contain the base directory of Boost. In this case the local boost directory. In VC7.1 you should do this by choosing the Tools/Options/Projects/VC++ Directories option.
Visual C++ 7.0 requires the use of Boost version 1_32_0. Visual C++ 7.1 (or later) requires Boost version 1_33_0 (or later).I
All Bayes++ source code files are copyright with the license conditions as given here. The copyright notice is that of the MIT license. This in no way restricts any commercial use you may wish to make using our source code. As long as you respect the copyright and license conditions, Michael Stevens and the Australian Centre for Field Robotics are happy to for you to use it in any way you wish.
Bayes++ the Bayesian Filtering Library
Copyright (c) 2003,2004,2005,2006,2011,2012,2014 Michael Stevens, Copyright (c) 2002 Michael Stevens and Australian Centre for Field Robotics
Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON INFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
SLAM is one of the most interesting problems in Bayesian filtering. It's structure implies that it cannot be correctly solved without using stochastic approach. This is due to mapped states being dependent on other mapped states and the localization state. This dependence also make the problem complex, therefore a simple approach such as representing all correlations is not tractable for large numbers of states.
Bayes++ has been used to implement various simple and some more advanced SLAM solutions. In particular a full implementation of FastSLAM has been implemented. This technique is described in the paper "FastSLAM : Factored Solution to the Simultaneous Localization and Mapping Problem", M. Montemerlo, S. Thrun S, D. Koller, B. Wegbreit, Proceedings of the AAAI National Conference on Artificial Intelligence 2002.
The Bayes++ implementation of FastSLAM and a very simple Kalman (full correlation) SLAM implementation is available as part of the most recent download.
These mathematical tools are particularly useful for visualising filtering results. However they are all rather slow, and it is very easy to produce very poorly implemented filters in their programming languages. Fortunately all these tools provide mechanisms for extension with external programs. Example interface code is provided in the Bayes++ GIT repository for Matlab.
Bayes++ only makes use of ISO standard C++. The source code uses moderately advance C++ constructs. It only makes restricted use of the C++ template system directly. However the Boost libraries used (in particular uBLAS) make extensive use of template techniques. Boost also includes many workarounds for compiler deficiencies. Therefore with few alterations Bayes++ should work with any modern C++ compiler supported by Boost.
Bayes++ is tested with: GCC 4.x, and VisualC++ 2008
Later versions of GCC 3.x and GCC 4.x should also run Bayes++ with ease. However GCC 3.3.0 is know to be incompatible with uBLAS and to produce incorrect code with -O2 optimization.
VisualC++ 7.1 often requires the /Zm option to be used so it can compile complex headers.
This releases is validated using the compilers and Boost versions listed above using the following tests.
Build system: Compatibility with Boost Build version 2.
Successfully complete build of default
libraries and examples.
Successfully complete build of
SLAM system.
Test examples: simpleExample, PV, QuadCalib
Compile debug
and release builds (using Boost Build version 2) :- with no errors
and no warnings.
Execution output :- Identical to expected
reference results.
Numerical tests: rtheta - Range angle observer.
A
non-linear range angle observer test. The observer moves in a 2
dimensional state space. Motion prediction occurs with a linear
model with additive noise. The two states are coupled both in the
model and in additive noise. Range and angle of a fixed target is
observed. The target is placed so discontinues angles are
observed.
Both the state and the observations have additional non
observed (singular) states. Model sizes, coupling parameters and
model types can be varied for additional tests. All schemes are
tested over 5 iterations of the model. The SIR scheme is
tested with 1000 samples.
Because the different numerical
implementations results are not expected to be identical between
Schemes. Therefore testing requires:
Regression testing :-
Changed in output for any Scheme from the previous
release.
Consistency testing :- Comparison of the output for
Scheme pairs know to produce numerically similar results.
SLAM test: testFastSLAM
Consistency testing :- Comparison
of FastSLAM result with 1,000,000 samples with Kalman SLAM.
Deviations of state and covariance expected to be approx 1/1000th.
Tested with Boost 1.63.0 and gcc-5.4.
Boost 'random' changed 'normal_distribution' definition changing random input for tests.
'rtheta' example requires quadmath library with gcc.
Tested with Boost 1.55.0 and gcc-4.8.
Document that b2 requires link=static option when compiling examples.
Recommend using cxxflags=-Wno-unused-local-typedefs for the GCC toolset, to avoid lots of warning text with GCC 4.8.
Renamed all classes which were previously named 'addative' to be called 'additive'.
Tested with Boost 1.49.0.
Cleanup comments in source.
Cleanup documentation and build files to make things build easily.
Support for and requires Boost 1_33_0.
The list of compilers for which Bayes++ is built and tested has been update.
New Documentation and support for Boost 1_32_0.
Sample covariances are now computed using the definition for the Maximum Likelihood (biased) estimate. This estimate simply devides by 1/n the number of samples, rather then 1/(n-1). See Sample Statistics in Wikipedia.
The list of compilers for which Bayes++ is built and tested has been update.
Corrects documentation and support for Boost Build (version 1).
SLAM has been updated from the current development version.
GCC 3.4 requires a couple of typename fixes to uBLAS (Boost_1_31_0 or earlier).
Bayes++ is tested with both Boost-1.30.2 and Boost_1_31_0.
Jens Mauer has been working hard on getting boost::random accepted as part of the future C++ standard library. To this end there have been substantial changes to its interface. The new library is now part of Boost_1_31_0. The Bayes++ examples make use of boost::random. So things migrate smoothly I have added a new "test/random.hpp" header which hides the interface changes.
The very excellent Boost Build system version 2 has advanced a great deal recently. Bayes++ is built with standard Boost Build system. Bayes++ has all the necessary "Jamfiles.v2" to be build with the Boost Build system.
The UD_scheme observe functions have had their numerical capabilities extended. It is now possible to work with singular (zero variance) covariance matrices.
The Unscented_scheme has additional function init_XX() and update_XX() to allow access to an Unscented state representation.
An error in SIR_kalman_schemes covariance calculation has been fixed. This error also effected the Fast_kalman_SLAM implementation. The error was significant for small small sizes.
For efficiency it is important to avoid creating temporary matrix and vector copies. Unless told otherwise it is not possible for uBLAS to determine if the same matrix or vector variable is specified on both the left and right hand side of an assignment operation. If such variable does appear it is said to be an alias. Because assignment involves more then one element, the presence of an alias requires that an assignment first compute a temporary result before the aliased variable is modified.
uBLAS's default behavior is to create such a temporary. If the assignment is know to be free of an alias this should be avoided. Previously such an optimized assignment was specified with the .assign() member functions. To improve the readability of code I have added a new syntax for assignment. Where no aliases of variable assigned to (lvalue) appears in the expression on the right hand side of the assignment use:
noalias(lvalue) = expression;
This new syntax is experimental but will probably be part of a future uBLAS release. At present the implementation introduces a small overhead on the supported compilers. This includes GCC 3.2.
Abstract filters and numeric schemes previously all had names ending in _filter. To make things simpler the naming has been changed to make a clear separation in what is a two level hierarchy.
Filters lie at the base of the hierarchy. Schemes are always derived from one of more filters. Filters represent abstract concepts, such as the statistics of state representation and model interface. Schemes are concrete implementations of a filter with all the numeric details and interfaces completed.
As part of this change the statistics of state representation have been made virtual base classes. This change is designed to allow multiple schemes combined together (using multiple inheritance) and share their representation. The change adds a little more work if you choose to derive from a scheme class. The constructors for the derived class must call the constructors for the virtual base classes directly.
Finally the CI algorithm has been implemented as a Scheme
in Bayes++. CI is interesting as it provides a weaker but more robust
fusion then traditional covariance based method such as the Kalman
filter. It estimates state and an upper bound of what its covariance
could be.
Actually only the matrix algebra associated with CI
has is included. The CI_filter scheme provides a virtual function
where the user must define the actual optimization algorithm to be
used.
The flexibility of the SIR_filter has been greatly improved. A new class Importance_resampler has been added. Whenever SIR_filter need to re-sample it uses and Importance_resampler parameter. Therefore by changing this parameter, different re-samplers can be used.
Two implementation are provided. The Standard_resampler and the Systematic_resampler. See the referenced publications for further discussion of these methods.
The matrix interface has been further improved. These improvement require uBLAS from boost_1_30_0. With this version there is experimental support for using uBLAS gappy matrices and vectors (sparse, compressed, coordinate).
The experimental support makes all of Bayes++ use a selected uBLAS storage type. Check matSupSub.hpp for macro's required to enable this. The algorithms used is Bayes++ are being upgraded to perform better with sparse types.
The mult_SPD products are no longer supported. They are replaced with the prod_SPD interface.
Copyright (c) 2003, 2004, 2005 Michael Stevens. This document is part of the Bayes++ library - see licensing section for copyright license details.