Estimation Algorithms for Non-Gaussian State-Space Models with Application to Positioning

Henri Nurminen

Estimation Algorithms for Non-Gaussian State-Space Models with Application to Positioning

Henri Nurminen

Tutkimustuotos: Väitöskirja › Collection of Articles

842 Lataukset (Pure)

Abstrakti

Tila-avaruusmalleilla mallinnetaan järjestelmiä, joilla on tuntema-
ton ajassa muuttuva tila sekä mitatattava ulostulo. Tilastollisissa tila-
avaruusmalleissa järjestelmän tilan muutos tunnetaan lukuunotta-
matta prosessikohinaksi kutsuttua satunnaista termiä, ja mittauk-
set sisältävät satunnaista mittauskohinaa. Kalmanin suodatin sekä
Rauchin Tungin ja Striebelin siloitin ovat yleisesti käytettyjä sulje-
tun muodon estimointialgoritmeja, jotka tuottavat tarkat bayesiläi-
set suodatus- ja siloitusjakaumat diskreettiaikaisille lineaarisille ti-
lastollisille tila-avaruusmalleille, joissa prosessi- ja mittauskohinat
noudattavat gaussisia jakaumia. Jos käsiteltyyn tila-avaruusmalliin
kuitenkin liittyy epälineaarisia funktioita tai epägaussisia kohinoita,
bayesiläisiä suodatus- ja siloitusjakaumia ei yleensä voida ratkais-
ta suljetun muodon algoritmeilla. Tässä väitöskirjassa tutkitaan ap-
proksimatiivista bayesiläistä aikasarjapäättelyä ja sen soveltamista
kahteen paikannusongelmaan, joissa gaussinen jakauma ei mallinna
riittävän hyvin kaikkea hyödyllistä tietoa tutkitun järjestelmän tilas-
tollisista ominaisuuksista: kartta-avusteinen sisätilapaikannus sekä
signaalin kulkuaikamittauksiin perustuva paikannus.
Sisätilakartan tuottamat liikerajoitteet voidaan liittää paikkaestimaat-
tiin käyttäen partikkelisuodattimeksi kutsuttua algoritmia. Partik-
kelisuodatin on Monte Carlo -algoritmi, joka soveltuu erityisesti ti-
lastollisille tila-avaruusmalleille, joissa bayesiläisen posteriorijakau-
man tiheysfunktio on niin monimutkainen, että sen approksimointi
tunnetuilla matalan parametridimension jakaumilla ei ole mielekäs-
tä. Kartta-avusteisessa sisätilapaikannuksessa reitit, jotka leikkaavat
seiniä tai kerrostasoja, saavat muita pienemmät todennäköisyydet.
Tässä väitöskirjassa esitetään parannuksia kolmeen eri partikkelisuo-
datusalgoritmiin, joita sovelletaan kartta-avusteiseen sisätilapaikan-

v

nukseen. Seinätörmayssuodattimessa painolliset satunnaisnäytteet
eli partikkelit liikkuvat inertiasensorimittausten mukaisesti, ja sei-
nään törmäävät partikkelit saavat pienet painot. Kun inertiasensori-
mittauksissa on paljon kohinaa, partikkeleita voidaan ohjata siten,
että seinätörmäysten määrä vähenee, jolloin suurempi osa partikke-
leista vaikuttaa estimaattiin. Kun inertiasensorimittauksia ei käytetä
lainkaan, sisätilakartta voidaan esittää graaﬁna, jonka kaarilla partik-
kelit liikkuvat ja joka on riittävän tiheä approksimoimaan odotetta-
vissa olevien reittien joukkoa.
Esimerkiksi laajan taajuuskaistan radioista (UWB, ultra-wideband)
tai paikannussatelliiteista saatavat radiosignaalin kulkuaikaan pe-
rustuvat etäisyysmittaukset taas voivat sisältää monipolkuheijastus-
ten ja suoran reitin estymisen aiheuttamia positiivismerkkisiä vir-
heitä, jotka ovat huomattavan suuria useimpiin mittausvirheisiin
verrattuna. Tässä väitöskirjassa esitetään laskennallisesti tehokkaita
bayesiläisen suodattimen ja siloittimen approksimaatioita tilastol-
lisille tila-avaruusmalleille, joissa mittauskohina noudattaa vinoa
t -jakaumaa. Vino t -jakauma on gaussisen jakauman laajennos, ja
sillä on kaksi lisäparametria, jotka vaikuttavat jakauman paksuhän-
täisyyteen ja vinouteen. Kun mittauskohinaa mallintava jakauma
oletetaan paksuhäntäiseksi, optimaalinen bayesiläinen algoritmi ei
ole herkkä yksittäisille suurille mittausvirheille, ja kun jakauma olete-
taan positiivisesti (tai negatiivisesti) vinoksi, algoritmit hyödyntävät
tietoa, että suurin osa suurista virheistä on positiivisia (tai negatiivi-
sia). Vino t -jakauma on siis gaussista jakaumaa joustavampi, ja sillä
voidaan mallintaa kulkuaikaan perustuvien mittausten virhejakau-
maa tarkemmin kuin gaussisella jakaumalla. Vinolla t -jakaumalla on
myös ehdollisesti gaussinen esitys, joka soveltuu suodatus- ja siloi-
tusposteriorien approksimointiin variaatio-Bayes-algoritmilla. Näin
ollen esitetyt algoritmit voivat olla laskennallisesti tehokkaampia
kuin Monte Carlo -algoritmit erityisesti tilan ollessa korkeaulotteinen.
Tässä väitöskirjassa näytetään, että vino-t -virhejakauman käyttö pa-
rantaa UWB-radioon perustuvan sisätilapaikannuksen tarkkuutta
sekä satelliittipohjaisen ulkopaikannuksen tarkkuutta kaupunkiym-
päristössä verrattuna laajennettuun Kalmanin suodattimeen. Vino-
t -suodatuksen laskennallinen vaativuus on suurempi mutta samaa
kertaluokkaa kuin laajennetun Kalmanin suodattimen.

Alkuperäiskieli	Englanti
Kustantaja	Tampere University of Technology
Sivumäärä	71
ISBN (elektroninen)	978-952-15-4029-5
ISBN (painettu)	978-952-15-4010-3
Tila	Julkaistu - 24 marrask. 2017
OKM-julkaisutyyppi	G5 Artikkeliväitöskirja

Julkaisusarja

Nimi	Tampere University of Technology. Publication
Vuosikerta	1499
ISSN (painettu)	1459-2045

Pääsy asiakirjaan

nurminen 1499
In reference to IEEE copyrighted material which is used with permission in this thesis, the IEEE does not endorse any of Tampere University of Technology's products or services. Internal or personal use of this material is permitted. If interested in reprinting/republishing IEEE copyrighted material for advertising or promotional purposes or for creating new collective works for resale or redistribution, please go to http://www.ieee.org/publications_standards/publications/rights/rights_link.html to learn how to obtain a License from RightsLink.
Final published version, 6,36 MB

http://urn.fi/URN:ISBN:978-952-15-4029-5

Siteeraa tätä

@book{0db3f8b2b09f439ea0a877013f98328c,

title = "Estimation Algorithms for Non-Gaussian State-Space Models with Application to Positioning",

abstract = "State-space models (SSMs) are used to model systems with hidden time-varying state and observable measurement output. In statistical SSMs, the state dynamics is assumed known up to a random term referred to as the process noise, and the measurements contain random measurement noise. Kalman ﬁlter (KF) and Rauch– Tung–Striebel smoother (RTSS) are widely-applied closed-form algorithms that provide the parameters of the exact Bayesian ﬁltering and smoothing distributions for discrete-time linear statistical SSMs where the process and measurement noises follow Gaussian distributions. However, when the SSM involves nonlinear functions and/or non-Gaussian noises, the Bayesian ﬁltering and smoothing distributions cannot in general be solved using closed-form algorithms. This thesis addresses approximate Bayesian time-series inference for two positioning-related problems where the assumption of Gaussian noises cannot capture all useful knowledge of the considered system{\textquoteright}s statistical properties: map-assisted indoor positioning and positioning using time-delay measurements. The motion constraints imposed by the indoor map are typically incorporated in the position estimate using the particle ﬁlter (PF) algorithm. The PF is a Monte Carlo algorithm especially suited for statistical SSMs where the Bayesian posterior distributions are too complicated to be adequately approximated using a well-known distribution family with a low-dimensional parameter space. In mapassisted indoor positioning, the trajectories that cross walls or ﬂoor levels get a low probability in the model. In this thesis, improvements to three different PF algorithms for map-assisted indoor positioning are proposed and compared. In the wall-collision PF, weighted random samples, also known as particles, are moved based on inertial sensor measurements, and the particles that collide with the walls are downweighted. When the inertial sensor measurements are very noisy, map information is used to guide the particles such that fewer particles collide with the walls, which implies that more particles contribute to the estimation. When no inertial sensor information is used, the particles are moved along the links of a graph that is dense enough to approximate the set of expected user paths. Time-delay based ranging measurements of e.g. ultra-wideband (UWB) and Global Navigation Satellite Systems (GNSSs) contain occasional positive measurement errors that are large relative to the majority of the errors due to multipath effects and denied line of sight. In this thesis, computationally efﬁcient approximate Bayesian ﬁlters and smoothers are proposed for statistical SSMs where the measurement noise follows a skew t -distribution, and the algorithms are applied to positioning using time-delay based ranging measurements. The skew t -distribution is an extension of the Gaussian distribution, which has two additional parameters that affect the heavytailedness and skewness of the distribution. When the measurement noise model is heavy-tailed, the optimal Bayesian algorithm is robust to occasional large measurement errors, and when the model is positively (or negatively) skewed, the algorithms account for the fact that most large errors are known to be positive (or negative). Therefore, the skew t -distribution is more ﬂexible than the Gaussian distribution and captures more statistical features of the error distributions of UWB and GNSS measurements. Furthermore, the skew t -distribution admits a conditionally Gaussian hierarchical form that enables approximating the ﬁltering and smoothing posteriors with Gaussian distributions using variational Bayes (VB) algorithms. The proposed algorithms can thus be computationally efﬁcient compared to Monte Carlo algorithms especially when the state is high-dimensional. It is shown in this thesis that the skew-t ﬁlter improves the accuracy of UWB based indoor positioning and GNSS based outdoor positioning in urban areas compared to the extended KF. The skew-t ﬁlter{\textquoteright}s computational burden is higher than that of the extended KF but of the same magnitude.",

keywords = "algorithm, non-Gaussian distributions, state-space models, nonlinear filtering, positioning",

author = "Henri Nurminen",

year = "2017",

month = nov,

day = "24",

language = "English",

isbn = "978-952-15-4010-3",

series = "Tampere University of Technology. Publication",

publisher = "Tampere University of Technology",

}

TY - BOOK

T1 - Estimation Algorithms for Non-Gaussian State-Space Models with Application to Positioning

AU - Nurminen, Henri

PY - 2017/11/24

Y1 - 2017/11/24

N2 - State-space models (SSMs) are used to model systems with hidden time-varying state and observable measurement output. In statistical SSMs, the state dynamics is assumed known up to a random term referred to as the process noise, and the measurements contain random measurement noise. Kalman ﬁlter (KF) and Rauch– Tung–Striebel smoother (RTSS) are widely-applied closed-form algorithms that provide the parameters of the exact Bayesian ﬁltering and smoothing distributions for discrete-time linear statistical SSMs where the process and measurement noises follow Gaussian distributions. However, when the SSM involves nonlinear functions and/or non-Gaussian noises, the Bayesian ﬁltering and smoothing distributions cannot in general be solved using closed-form algorithms. This thesis addresses approximate Bayesian time-series inference for two positioning-related problems where the assumption of Gaussian noises cannot capture all useful knowledge of the considered system’s statistical properties: map-assisted indoor positioning and positioning using time-delay measurements. The motion constraints imposed by the indoor map are typically incorporated in the position estimate using the particle ﬁlter (PF) algorithm. The PF is a Monte Carlo algorithm especially suited for statistical SSMs where the Bayesian posterior distributions are too complicated to be adequately approximated using a well-known distribution family with a low-dimensional parameter space. In mapassisted indoor positioning, the trajectories that cross walls or ﬂoor levels get a low probability in the model. In this thesis, improvements to three different PF algorithms for map-assisted indoor positioning are proposed and compared. In the wall-collision PF, weighted random samples, also known as particles, are moved based on inertial sensor measurements, and the particles that collide with the walls are downweighted. When the inertial sensor measurements are very noisy, map information is used to guide the particles such that fewer particles collide with the walls, which implies that more particles contribute to the estimation. When no inertial sensor information is used, the particles are moved along the links of a graph that is dense enough to approximate the set of expected user paths. Time-delay based ranging measurements of e.g. ultra-wideband (UWB) and Global Navigation Satellite Systems (GNSSs) contain occasional positive measurement errors that are large relative to the majority of the errors due to multipath effects and denied line of sight. In this thesis, computationally efﬁcient approximate Bayesian ﬁlters and smoothers are proposed for statistical SSMs where the measurement noise follows a skew t -distribution, and the algorithms are applied to positioning using time-delay based ranging measurements. The skew t -distribution is an extension of the Gaussian distribution, which has two additional parameters that affect the heavytailedness and skewness of the distribution. When the measurement noise model is heavy-tailed, the optimal Bayesian algorithm is robust to occasional large measurement errors, and when the model is positively (or negatively) skewed, the algorithms account for the fact that most large errors are known to be positive (or negative). Therefore, the skew t -distribution is more ﬂexible than the Gaussian distribution and captures more statistical features of the error distributions of UWB and GNSS measurements. Furthermore, the skew t -distribution admits a conditionally Gaussian hierarchical form that enables approximating the ﬁltering and smoothing posteriors with Gaussian distributions using variational Bayes (VB) algorithms. The proposed algorithms can thus be computationally efﬁcient compared to Monte Carlo algorithms especially when the state is high-dimensional. It is shown in this thesis that the skew-t ﬁlter improves the accuracy of UWB based indoor positioning and GNSS based outdoor positioning in urban areas compared to the extended KF. The skew-t ﬁlter’s computational burden is higher than that of the extended KF but of the same magnitude.

AB - State-space models (SSMs) are used to model systems with hidden time-varying state and observable measurement output. In statistical SSMs, the state dynamics is assumed known up to a random term referred to as the process noise, and the measurements contain random measurement noise. Kalman ﬁlter (KF) and Rauch– Tung–Striebel smoother (RTSS) are widely-applied closed-form algorithms that provide the parameters of the exact Bayesian ﬁltering and smoothing distributions for discrete-time linear statistical SSMs where the process and measurement noises follow Gaussian distributions. However, when the SSM involves nonlinear functions and/or non-Gaussian noises, the Bayesian ﬁltering and smoothing distributions cannot in general be solved using closed-form algorithms. This thesis addresses approximate Bayesian time-series inference for two positioning-related problems where the assumption of Gaussian noises cannot capture all useful knowledge of the considered system’s statistical properties: map-assisted indoor positioning and positioning using time-delay measurements. The motion constraints imposed by the indoor map are typically incorporated in the position estimate using the particle ﬁlter (PF) algorithm. The PF is a Monte Carlo algorithm especially suited for statistical SSMs where the Bayesian posterior distributions are too complicated to be adequately approximated using a well-known distribution family with a low-dimensional parameter space. In mapassisted indoor positioning, the trajectories that cross walls or ﬂoor levels get a low probability in the model. In this thesis, improvements to three different PF algorithms for map-assisted indoor positioning are proposed and compared. In the wall-collision PF, weighted random samples, also known as particles, are moved based on inertial sensor measurements, and the particles that collide with the walls are downweighted. When the inertial sensor measurements are very noisy, map information is used to guide the particles such that fewer particles collide with the walls, which implies that more particles contribute to the estimation. When no inertial sensor information is used, the particles are moved along the links of a graph that is dense enough to approximate the set of expected user paths. Time-delay based ranging measurements of e.g. ultra-wideband (UWB) and Global Navigation Satellite Systems (GNSSs) contain occasional positive measurement errors that are large relative to the majority of the errors due to multipath effects and denied line of sight. In this thesis, computationally efﬁcient approximate Bayesian ﬁlters and smoothers are proposed for statistical SSMs where the measurement noise follows a skew t -distribution, and the algorithms are applied to positioning using time-delay based ranging measurements. The skew t -distribution is an extension of the Gaussian distribution, which has two additional parameters that affect the heavytailedness and skewness of the distribution. When the measurement noise model is heavy-tailed, the optimal Bayesian algorithm is robust to occasional large measurement errors, and when the model is positively (or negatively) skewed, the algorithms account for the fact that most large errors are known to be positive (or negative). Therefore, the skew t -distribution is more ﬂexible than the Gaussian distribution and captures more statistical features of the error distributions of UWB and GNSS measurements. Furthermore, the skew t -distribution admits a conditionally Gaussian hierarchical form that enables approximating the ﬁltering and smoothing posteriors with Gaussian distributions using variational Bayes (VB) algorithms. The proposed algorithms can thus be computationally efﬁcient compared to Monte Carlo algorithms especially when the state is high-dimensional. It is shown in this thesis that the skew-t ﬁlter improves the accuracy of UWB based indoor positioning and GNSS based outdoor positioning in urban areas compared to the extended KF. The skew-t ﬁlter’s computational burden is higher than that of the extended KF but of the same magnitude.

KW - algorithm

KW - non-Gaussian distributions

KW - state-space models

KW - nonlinear filtering

KW - positioning

M3 - Doctoral thesis

SN - 978-952-15-4010-3

T3 - Tampere University of Technology. Publication

BT - Estimation Algorithms for Non-Gaussian State-Space Models with Application to Positioning

PB - Tampere University of Technology

ER -

Estimation Algorithms for Non-Gaussian State-Space Models with Application to Positioning

Abstrakti

Julkaisusarja

Pääsy asiakirjaan

Sormenjälki

Siteeraa tätä