Tutorial Kalman Filter
(kalmanfilter.net)- Kalman filter adalah algoritme yang menggunakan pengukuran sensor yang bercampur noise bersama model dinamis yang tidak sempurna untuk memperkirakan keadaan saat ini dan berikutnya, termasuk ketidakpastian keduanya
- Tutorial ini memakai contoh pelacakan pesawat dengan radar; jarak (r) dan kecepatan (v) dijadikan vektor keadaan, lalu proses menggabungkan prediksi dan pengukuran diikuti secara numerik
- Dengan nilai pengukuran awal (10,000m), (200m/s) dan interval sampling (5s), model kecepatan konstan memprediksi posisi berikutnya sebagai (11,000m); noise pengukuran (R) dan noise proses (Q) tercermin dalam kovarians
- Pengukuran kedua (11,020m), (202m/s) lebih tidak pasti, tetapi Kalman gain (K) menggabungkan prediksi dan pengukuran secara berbobot sehingga keadaan terbarui dihitung menjadi (11,009.37m), (201.43m/s)
- Setelah inisialisasi, loop prediksi-pembaruan diulang; dalam implementasi nyata, perlu dipertimbangkan juga rumus pembaruan kovarians yang stabil seperti Joseph form serta penanganan pengukuran anomali
Masalah estimasi yang diselesaikan Kalman filter
- Kalman filter adalah algoritme untuk memperkirakan dan memprediksi keadaan sistem dalam lingkungan yang mengandung ketidakpastian
- Data sensor dengan noise pengukuran
- Faktor eksternal yang tidak diketahui
- Perbedaan antara model dinamis dan gerakan nyata
- Digunakan untuk pelacakan objek, navigasi, robotika, kontrol, analisis pasar keuangan, prakiraan cuaca, dan sebagainya
- Jika diterapkan pada estimasi lintasan mouse komputer, algoritme ini dapat mengurangi noise dan mengoreksi getaran tangan sehingga menghasilkan jalur gerak yang lebih stabil
- Tutorial ini disusun agar Kalman filter dapat dipahami melalui contoh numerik dan penjelasan intuitif, bukan penjelasan matematika yang rumit
- Juga mencakup contoh ketika Kalman filter gagal melacak objek dengan baik dalam situasi yang dirancang keliru, serta cara mengoreksinya
Jalur pembelajaran
- Proyek ini disusun agar Kalman filter dapat dipelajari dalam tiga tingkat kedalaman
- Ikhtisar satu halaman: menjelaskan gagasan inti dan persamaan penting tanpa penurunan, dengan asumsi pengetahuan dasar statistik dan aljabar linear
- Tutorial web gratis berbasis contoh: membangun intuisi lewat contoh numerik dan membahas penurunan persamaan Kalman filter langkah demi langkah; disebutkan tidak memerlukan pengetahuan prasyarat
- Kalman Filter from the Ground Up: mencakup 14 contoh numerik dengan solusi lengkap, plot dan tabel performa, Extended Kalman Filter, Unscented Kalman Filter, fusi sensor, serta panduan implementasi
Kebutuhan prediksi lewat contoh pelacakan radar
- Pada radar yang melacak pesawat, pesawat adalah sistem, dan posisi yang harus diperkirakan adalah keadaan sistem
- Karena radar mengarahkan beam sempit ke arah pesawat, posisi masa depan harus diprediksi untuk menentukan ke mana beam berikutnya diarahkan
- Jika prediksi gagal, beam bisa mengarah ke arah yang salah dan pelacakan dapat hilang
- Diperlukan model dinamis yang menggambarkan pergerakan sistem terhadap waktu
- Dalam contoh 1 dimensi yang disederhanakan, diasumsikan pesawat bergerak dalam garis lurus mendekati atau menjauhi radar
- Radar menghitung jarak (r) dari waktu kirim-terima pulsa
- Kecepatan (v) juga dapat diukur melalui efek Doppler
- Jika pada (t_0) jarak (10,000m) dan kecepatan (200m/s) diukur dengan sangat akurat, interval sampling (\Delta t=5s), dan kecepatan diasumsikan konstan, maka posisi berikutnya adalah (11,000m)
- (\Delta r = v \cdot \Delta t)
- (r_{t_1}=10,000+200\cdot5=11,000m)
Noise pengukuran dan noise proses
- Pengukuran radar nyata tidak sepenuhnya presisi; beberapa radar yang mengukur pada saat yang sama pun dapat menghasilkan nilai yang sedikit berbeda
- Variasi ini dinyatakan sebagai noise pengukuran
- Selain nilai estimasi keadaan, perlu juga dihitung seberapa dapat dipercaya estimasi tersebut
- Model dinamis juga tidak sempurna
- Meski diasumsikan pesawat bergerak dengan kecepatan konstan, gerakan nyata dapat berubah karena faktor eksternal seperti angin
- Pengaruh yang tidak dapat diprediksi seperti ini adalah noise proses
- Kalman filter menyediakan estimasi keadaan saat ini, prediksi keadaan masa depan, serta ketidakpastian masing-masing
- Dengan syarat sistem dan noise mengikuti asumsi model, ini adalah algoritme optimal yang meminimalkan ketidakpastian estimasi keadaan
Vektor keadaan dan inisialisasi
- Keadaan sistem pada contoh ini terdiri dari jarak pesawat (r) dan kecepatan (v)
[ \boldsymbol{x}= \begin{bmatrix} r\ v \end{bmatrix} ]
- Pengukuran pertama pada (t_0) adalah sebagai berikut
[ \boldsymbol{z}_0= \begin{bmatrix} 10{,}000\ 200 \end{bmatrix} ]
- Karena pengukuran memiliki ketidakpastian, setiap pengukuran disertai ketidakpastian pengukuran dalam bentuk varians
- Simpangan baku pengukuran jarak: (4m)
- Simpangan baku pengukuran kecepatan: (0.5m/s)
- Varians adalah kuadrat dari simpangan baku
[ \boldsymbol{R}_0= \begin{bmatrix} 16 & 0\ 0 & 0.25 \end{bmatrix} ]
- Dalam contoh ini, galat pengukuran jarak dan kecepatan diasumsikan tidak saling terkait, sehingga elemen non-diagonal pada matriks kovarians dibuat 0
- Pada tahap inisialisasi, karena pengukuran dan keadaan sistem merepresentasikan besaran fisik yang sama, yaitu (r) dan (v), pengukuran pertama dapat digunakan sebagai estimasi keadaan awal
[ \hat{\boldsymbol{x}}_{0,0}= \boldsymbol{z}_0= \begin{bmatrix} 10{,}000\ 200 \end{bmatrix} ]
- Cara ini hanya dapat digunakan pada tahap inisialisasi
Tahap prediksi: propagasi keadaan dan kovarians
- Prediksi menghitung keadaan pada waktu berikutnya menggunakan keadaan saat ini dan matriks transisi keadaan (\boldsymbol{F})
- Pada model kecepatan konstan, digunakan rumus berikut
[ v_1=v_0=v ]
[ r_1=r_0+v_0\Delta t ]
- Rumus prediksi keadaan dalam bentuk matriks adalah sebagai berikut
[ \hat{\boldsymbol{x}}_{n+1,n}
\boldsymbol{F} \hat{\boldsymbol{x}}_{n,n} + \boldsymbol{G}\boldsymbol{u}_n ]
- (\boldsymbol{u}_n): variabel input
- (\boldsymbol{G}): matriks transisi input
- Pada contoh sederhana ini tidak ada input, sehingga (\boldsymbol{u}_n=0)
- Saat (\Delta t=5s), matriks transisi keadaan adalah sebagai berikut, dan hasil prediksinya adalah (11,000m), (200m/s)
[ \boldsymbol{F}= \begin{bmatrix} 1 & 5\ 0 & 1 \end{bmatrix} ]
[ \hat{\boldsymbol{x}}_{1,0}
\begin{bmatrix} 11{,}000\ 200 \end{bmatrix} ]
- Prediksi kovarians tidak menggunakan sekadar (\boldsymbol{F}\boldsymbol{P}), melainkan (\boldsymbol{F}\boldsymbol{P}\boldsymbol{F}^T)
[ \boldsymbol{P}_{n+1,n}
\boldsymbol{F} \boldsymbol{P}_{n,n} \boldsymbol{F}^T + \boldsymbol{Q} ]
- Jika noise proses dikecualikan, kovarians prediksi adalah sebagai berikut
[ \boldsymbol{P}_{1,0}
\begin{bmatrix} 22.25 & 1.25\ 1.25 & 0.25 \end{bmatrix} ]
- Varians kecepatan tetap (0.25) karena model kecepatan konstan
- Varians jarak meningkat dari (16) menjadi (22.25) karena ketidakpastian kecepatan memperbesar ketidakpastian jarak seiring waktu
Memasukkan noise proses
- Karena kecepatan pesawat nyata dapat dipengaruhi faktor eksternal yang tidak dapat diprediksi seperti angin, noise proses (\boldsymbol{Q}) ditambahkan ke prediksi kovarians
- Dalam contoh ini, simpangan baku percepatan acak diasumsikan (\sigma_a=0.2m/s^2)
- Variansnya adalah (\sigma_a^2=0.04m^2/s^4)
- Saat (\Delta t=5s), matriks noise proses adalah sebagai berikut
[ \boldsymbol{Q}
\begin{bmatrix} 6.25 & 2.5\ 2.5 & 1 \end{bmatrix} ]
- Kovarians prediksi setelah menambahkan noise proses adalah sebagai berikut
[ \boldsymbol{P}_{1,0}
\begin{bmatrix} 28.5 & 3.75\ 3.75 & 1.25 \end{bmatrix} ]
Tahap pembaruan: kombinasi berbobot prediksi dan pengukuran
- Pada (t_1), pengukuran kedua adalah sebagai berikut
[ \boldsymbol{z}_1= \begin{bmatrix} 11{,}020\ 202 \end{bmatrix} ]
- Pengukuran ini diasumsikan memiliki ketidakpastian lebih besar daripada pengukuran pertama karena lonjakan noise kuat menurunkan rasio signal-to-noise
- Simpangan baku jarak: (6m)
- Simpangan baku kecepatan: (1.5m/s)
[ \boldsymbol{R}_1= \begin{bmatrix} 36 & 0\ 0 & 2.25 \end{bmatrix} ]
- Elemen diagonal kovarians prediksi (\boldsymbol{P}_{1,0}) lebih kecil daripada kovarians pengukuran (\boldsymbol{R}_1), sehingga sisi prediksi memiliki ketidakpastian lebih rendah
- Kalman filter tidak hanya memakai prediksi atau hanya memakai pengukuran, tetapi menggabungkannya dengan memberikan bobot lebih besar pada sisi yang ketidakpastiannya lebih rendah
- Rata-rata berbobot dalam bentuk 1 dimensi adalah sebagai berikut
[ \hat{x}_{1,1}
K_1 z_1 + (1-K_1)\hat{x}_{1,0} ]
- (\boldsymbol{K}) adalah Kalman gain, yang menentukan bobot pengukuran dan prediksi agar ketidakpastian estimasi terbarui menjadi minimum
Inovasi, matriks observasi, dan Kalman gain
- Rumus pembaruan keadaan dapat ditulis dalam bentuk menambahkan suku koreksi pada nilai prediksi
[ \hat{\boldsymbol{x}}_{1,1}
\hat{\boldsymbol{x}}_{1,0} + \boldsymbol{K}_1 ( \boldsymbol{z}_1
\boldsymbol{H}\hat{\boldsymbol{x}}_{1,0} ) ]
- (\boldsymbol{z}1-\boldsymbol{H}\hat{\boldsymbol{x}}{1,0}) adalah inovasi (innovation) atau residual, yang merepresentasikan informasi yang diberikan pengukuran baru
- (\boldsymbol{H}) adalah matriks observasi atau matriks pengukuran, yang memetakan variabel keadaan ke besaran fisik yang benar-benar diukur
- Dalam contoh ini, keadaan dan pengukuran sama-sama jarak dan kecepatan, sehingga (\boldsymbol{H}=\boldsymbol{I})
- Secara umum, seperti pada termometer digital, pengukuran dan keadaan bisa berada di ranah fisik yang berbeda
- Kalman gain multivariat adalah sebagai berikut
[ \boldsymbol{K}_n
\boldsymbol{P}{n,n-1} \boldsymbol{H}^T ( \boldsymbol{H} \boldsymbol{P}{n,n-1} \boldsymbol{H}^T + \boldsymbol{R}_n )^{-1} ]
- Kalman gain yang dihitung pada contoh ini adalah sebagai berikut
[ \boldsymbol{K}_1= \begin{bmatrix} 0.4048 & 0.6377\ 0.0399 & 0.3144 \end{bmatrix} ]
- Perhitungan invers matriks dapat dilakukan dengan
inv(A)di MATLAB ataunumpy.linalg.inv(A)di Python, tetapi dalam implementasi nyata umumnya lebih baik menyelesaikan sistem linear secara langsung, sepertiA\bataunumpy.linalg.solve(A, b), daripada memakai invers eksplisit
Hasil pembaruan dan penurunan kovarians
- Inovasi pada contoh ini adalah sebagai berikut
[ \boldsymbol{z}1-\hat{\boldsymbol{x}}{1,0}
\begin{bmatrix} 20\ 2 \end{bmatrix} ]
- Jika suku koreksi dihitung dengan Kalman gain, hasilnya sebagai berikut
[ \boldsymbol{K}_1 \begin{bmatrix} 20\ 2 \end{bmatrix}
\begin{bmatrix} 9.37\ 1.43 \end{bmatrix} ]
- Estimasi keadaan terbarui adalah sebagai berikut
[ \hat{\boldsymbol{x}}_{1,1}
\begin{bmatrix} 11{,}009.37\ 201.43 \end{bmatrix} ]
- Untuk pembaruan kovarians multivariat, Joseph form yang stabil secara numerik sering digunakan
[ \boldsymbol{P}_{n,n}
(\boldsymbol{I}-\boldsymbol{K}n\boldsymbol{H}) \boldsymbol{P}{n,n-1} (\boldsymbol{I}-\boldsymbol{K}_n\boldsymbol{H})^T + \boldsymbol{K}_n \boldsymbol{R}_n \boldsymbol{K}_n^T ]
- Rumus pembaruan kovarians yang disederhanakan juga sering muncul dalam literatur
[ \boldsymbol{P}_{n,n}
(\boldsymbol{I}-\boldsymbol{K}n\boldsymbol{H}) \boldsymbol{P}{n,n-1} ]
- Dalam aritmetika eksak, kedua bentuk memberi hasil yang sama, tetapi dalam implementasi komputer Joseph form umumnya lebih stabil secara numerik
- Kovarians terbarui yang dihitung dengan rumus sederhana pada contoh ini adalah sebagai berikut
[ \boldsymbol{P}_{1,1}
\begin{bmatrix} 14.57 & 1.43\ 1.43 & 0.71 \end{bmatrix} ]
- Elemen diagonal kovarians terbarui lebih rendah daripada kovarians prediksi ((28.5, 1.25)) dan kovarians pengukuran ((36, 2.25))
- Informasi baru mengurangi ketidakpastian estimasi meski ketidakpastiannya tinggi, dan secara teori pengukuran baru tidak boleh diabaikan
- Dalam implementasi nyata, ada kalanya pengukuran yang tidak dapat dipercaya harus ditolak; metode penanganan outlier dibahas dalam bab Outlier Treatment pada buku
Prediksi berikutnya dan loop berulang
- Tahap prediksi pada Iteration 1 sama seperti Iteration 0, tetapi titik awalnya berubah menjadi (\hat{\boldsymbol{x}}{1,1}) dan (\boldsymbol{P}{1,1}) yang sudah diperbarui
- Hasil prediksi keadaan adalah sebagai berikut
[ \hat{\boldsymbol{x}}_{2,1}
\boldsymbol{F} \hat{\boldsymbol{x}}_{1,1}
\begin{bmatrix} 12{,}016.5\ 201.43 \end{bmatrix} ]
- Hasil prediksi kovarians adalah sebagai berikut
[ \boldsymbol{P}_{2,1}
\begin{bmatrix} 52.86 & 7.47\ 7.47 & 1.71 \end{bmatrix} ]
- Jika waktu berlalu tanpa pengukuran baru, ketidakpastian meningkat secara alami, sehingga varians kembali bertambah pada tahap prediksi
- Ketidakpastian kecepatan makin memperbesar ketidakpastian jarak
- Karena itu, varians jarak meningkat lebih cepat daripada varians kecepatan
- Contoh ini menunjukkan tiga tahap Kalman filter
- Inisialisasi: dilakukan sekali di awal
- Prediksi: mempropagasi keadaan berikutnya dan ketidakpastiannya dengan model dinamis
- Pembaruan: menggabungkan pengukuran baru dan prediksi dengan Kalman gain
- Setelah inisialisasi, Kalman filter terus bekerja sebagai loop prediksi-pembaruan
1 komentar
Komentar Hacker News
Saya selalu bilang bahwa mempelajari filter Kalman secara terpisah itu urutannya terbalik, sehingga mudah melewatkan pencerahan besar yang dibuka oleh teori-teori di sekitarnya
Untuk benar-benar memahaminya, sebaiknya melihat metode kuadrat terkecil (regresi linear), recursive least squares, lalu information filter (formulasi lain dari KF) secara berurutan
Dengan begitu, Anda akan menyadari bahwa KF hanyalah recursive least squares yang diformulasikan ulang untuk memprioritaskan efisiensi pada tahap pembaruan
PDF ini memberi gambaran ringkas: http://ais.informatik.uni-freiburg.de/teaching/ws13/mapping/...
Meski begitu, saya tetap punya rasa ingin tahu intelektual, jadi perlu jalur untuk terus menjaga rasa ingin tahu itu sambil perlahan bergerak menuju pemahaman
Membaca ulang The Six (Not So) Easy Pieces pun saya tetap tidak paham, tetapi masih terasa berharga; dan dengan bermain-main dengan kucing Arnold, saya bisa mengalami konsep-konsep yang semula berada di balik pintu bernama konteks, bermodalkan rasa ingin tahu seperti primata telanjang tanpa prosedur ilmiah yang ketat
http://gerdbreitenbach.de/arnold_cat/cat.html
Dalam 1 dimensi, dari prediksi linear X'1 = X0*a + b kita memperoleh distribusi prior, mean(X'1) = mean(X0)*a + b, var(X'1) = var(X0)*a^2, dengan a dan b merepresentasikan dinamika yang diasumsikan
Posterior Gaussian adalah rata-rata berbobot presisi dari prior dan observasi, sehingga X1 = (1 - K)X'1 + YK, dan K = (1/var(X'1))/(1/var(X'1) + 1/var(Y)), dengan Y sebagai observasi Gaussian
Jika ini diulang, jadilah filter Kalman; dan jika memahami linearitas Gaussian multidimensi, generalisasi ke banyak dimensi juga terasa intuitif
Namun, linearitas Gaussian multidimensi dan posterior Gaussian itu sendiri bisa saja bukan materi yang mudah
Setiap kali topik ini muncul, materi ini juga ikut muncul, dan sebaliknya: https://github.com/rlabbe/Kalman-and-Bayesian-Filters-in-Pyt...
Penggunaan Jupyter notebook juga sangat bagus
Sepertinya belum ada alat komputasi simbolik untuk distribusi probabilitas
Maksud saya, misalnya alat yang bisa mengalikan dua fungsi kepadatan probabilitas Gaussian multivariat untuk memperoleh matriks kovarians, atau ketika semua komponen filter Kalman (model prediksi dan proses observasi) didefinisikan, alat itu bisa mengeluarkan rumus yang diperlukan seperti
lambdifydi sympyNamun saya tidak tahu apakah Sympy bisa menangani distribusi bersyarat yang dibutuhkan filter Kalman, yaitu posterior Bayes
Bagaimanapun, jika ingin bermain-main dengan filter Kalman di Sympy, lebih baik menangani mean dan varians, atau matriks kovarians, secara langsung
Referensi: https://reference.wolfram.com/language/howto/WorkWithStatist...
Dan: https://reference.wolfram.com/language/ref/MultinormalDistri...
https://www.squiggle-language.com/docs
Jika Q dan R konstan, seperti yang biasanya terjadi, gain akan cepat konvergen sehingga filter Kalman menjadi hampir sama dengan filter eksponensial yang diberi tahap prediksi
Bagi banyak orang, penjelasan ini jauh lebih mudah dipahami dan juga cocok dengan cara penggunaannya di dunia nyata
Karena biasanya Q dan R disetel manual sampai “terlihat oke”, lalu tidak diubah lagi
Selain itu, alih-alih menyetel beberapa nilai seperti Q dan R, cukup menyetel satu gain secara manual
Apakah kita hanya menyetelnya sampai hasilnya tampak masuk akal? Kalau begitu, saya tidak tahu bagaimana ia bisa bekerja dengan benar bahkan dalam situasi yang tidak sepenuhnya overfit
Misalnya, jika melacak burung dalam video, mungkin kita bisa memilih suatu Q, tetapi statistik noise bisa berubah tergantung waktu. Dalam kondisi seperti itu harus bagaimana?
Artikel terkait: Kalman filter from the ground up - https://news.ycombinator.com/item?id=37879715 - Oktober 2023, 150 komentar
Saya juga penasaran tahun apa yang paling tepat untuk dimasukkan ke judul di atas
Filter Kalman tercakup dalam topik yang lebih umum, yaitu Optimization by Vector Space Methods karya David G. Luenberger, John Wiley and Sons, Inc., New York, 1969
Tiba-tiba terpikir begini. Bisakah kasus yang hanya memiliki kesaksian saksi mata dikodekan entah bagaimana sebagai vektor, lalu ditangani dengan filter Kalman untuk memperkuat nilai pembuktian dari observasi?
Caranya dengan memperlakukan kebohongan dan ketidakakuratan sama-sama sebagai “error”
Yang saya pikirkan adalah Phoenix lights atau UFO secara umum, hantu, pengalaman mendekati kematian, dan yang lebih sehari-hari seperti tuduhan pemerkosaan
Materi terbaik hampir selalu yang ini: https://github.com/rlabbe/Kalman-and-Bayesian-Filters-in-Pyt...
Tetap bagus meski Anda tidak memakai Python, dan benar-benar memberi tinjauan menyeluruh dengan sangat baik
Ada lagi yang saat belajar topik ini menonton kuliah filter Kalman dari Michael van Biezem yang memakai dasi kupu-kupu?
https://www.youtube.com/watch?v=CaCcOwJPytQ&list=PLX2gX-ftPV...
Satu kalimat yang benar-benar perlu diketahui adalah ini: “Filter ini dinamai dari Rudolf E. Kálmán (19 Mei 1930–2 Juli 2016). Pada 1960, Kálmán menerbitkan makalah terkenal yang menjelaskan solusi rekursif untuk masalah penyaringan linear data diskret”