Kalman Filter yang Dijelaskan Secara Sederhana
(thekalmanfilter.com)- Kalman Filter adalah algoritme yang menghasilkan estimasi keadaan yang lebih akurat secara real-time dari pengukuran yang berisik atau tidak akurat, dan digunakan untuk prediksi serta kontrol berbasis sensor
- Ini bukan sekadar membuat pengukuran menjadi lebih halus, tetapi juga dapat mengestimasi variabel keadaan seperti posisi dan kecepatan yang sulit diamati secara langsung
- Contoh pelacakan radar menunjukkan alur yang menerima pengukuran posisi 2D dan kovarians sebagai input, lalu mengestimasi posisi dan kecepatan objek sebagai vektor keadaan 4×1
- Setelah menginisialisasi keadaan dengan dua pengukuran pertama, proses berikutnya mengulang prediksi, perhitungan Kalman Gain, serta pembaruan keadaan dan kovarians galat
- Riwayat yang dipertahankan filter hanyalah satu estimasi keadaan saat ini, sehingga mudah diimplementasikan bahkan pada perangkat dengan keterbatasan memori
Gambaran besar Kalman Filter
- Kalman Filter dapat dilihat seperti black box yang memiliki input dan output
- Inputnya adalah pengukuran yang berisik atau kadang tidak akurat
- Outputnya adalah estimasi yang lebih akurat dengan noise yang berkurang
- Estimasi tersebut dapat berupa parameter keadaan sistem yang sebenarnya tidak diukur atau tidak diamati
- Digunakan untuk mengestimasi parameter yang dapat diamati maupun yang tidak dapat diamati secara real-time dengan akurasi tinggi
- Estimasi berakurasi tinggi dimanfaatkan untuk prediksi dan pengambilan keputusan yang presisi
- Karena itu, Kalman Filter sering digunakan dalam robotika dan sistem real-time yang membutuhkan informasi tepercaya
Masalah yang diselesaikan Kalman Filter
- Berdasarkan pengukuran yang tidak akurat atau berisik, Kalman Filter mengestimasi keadaan suatu variabel, atau variabel lain yang sulit diamati secara langsung, dengan akurasi lebih tinggi
- Aplikasi umumnya antara lain:
- Pelacakan objek: menggunakan posisi yang diukur untuk mengestimasi posisi dan kecepatan objek dengan lebih akurat
- Estimasi berat pada timbangan digital: mengestimasi berat benda dari tekanan yang diberikan pada permukaan
- Pemanduan, navigasi, dan kontrol: mengestimasi posisi, kecepatan, dan percepatan dengan sensor IMU, lalu memanfaatkannya untuk mengontrol gerakan berikutnya
- Kekuatan Kalman Filter bukan pada penghalusan pengukuran itu sendiri, melainkan pada kemampuannya mengestimasi parameter sistem yang sulit diukur
- Dalam sistem real-time, estimasi yang semakin akurat menghasilkan kontrol dan fungsi yang lebih baik
Input dan output pada contoh pelacakan radar
- Contoh ini membahas situasi pelacakan radar untuk melacak pesawat dan objek di sekitar bandara
- Status track yang dihasilkan digunakan untuk ditampilkan kepada operator kontrol lalu lintas udara yang memantau wilayah udara
- Radar mengeluarkan pengukuran posisi x, y dalam sistem koordinat Kartesius 2D
- Pengukuran direpresentasikan sebagai vektor kolom 2×1 z
- Matriks varians-kovarians dari pengukuran direpresentasikan sebagai R
- Tag waktu pengukuran direpresentasikan sebagai t
- Subskrip m menunjukkan parameter pengukuran, sedangkan k menunjukkan urutan pengukuran
- Kalman Filter mengestimasi posisi dan kecepatan objek berdasarkan pengukuran radar
- Estimasi direpresentasikan sebagai vektor kolom 4×1 x
- Matriks varians-kovarians dari estimasi direpresentasikan sebagai matriks 4×4 P
- Tag waktu estimasi keadaan ditandai sebagai T
Langkah 1: Inisialisasi keadaan sistem
- Cara inisialisasi Kalman Filter berbeda-beda untuk tiap aplikasi
- Dalam contoh pelacakan radar ini, keadaan sistem diinisialisasi dengan pengukuran pertama
- Pengukuran input hanya berisi informasi posisi, tetapi keadaan sistem output berisi posisi dan kecepatan objek
- Saat pengukuran pertama masuk, informasi yang diketahui hanyalah posisi pada saat itu
- Setelah estimasi pertama, estimasi keadaan sistem ditetapkan ke posisi input
- Kovarians galat keadaan sistem ditetapkan berdasarkan akurasi posisi pengukuran pertama
Langkah 2: Reinisisialisasi keadaan sistem
- Karena estimasi kecepatan membutuhkan pengukuran posisi kedua, estimasi keadaan sistem diinisialisasi ulang
- Kecepatan dihitung dengan aproksimasi linear
- Kecepatan dihitung sebagai jarak tempuh / waktu yang diperlukan untuk menempuhnya
- Estimasi keadaan sistem yang diperbarui terdiri dari posisi pada pengukuran kedua dan kecepatan yang dihitung
- Kovarians galat keadaan sistem yang diperbarui berisi akurasi posisi pengukuran kedua dan akurasi kecepatan yang diaproksimasi
- Nilai aproksimasi akurasi kecepatan dapat disesuaikan melalui tuning setelah data dilewatkan ke filter
- Dalam contoh ini, komponen varians kecepatan ditetapkan ke 10⁴
- Nilai ini menunjukkan ketidakpastian besar terhadap nilai keadaan kecepatan
- Satuan kecepatan dalam contoh ini adalah m/s
Pemrosesan berulang setelah inisialisasi
- Dua langkah pertama adalah proses menginisialisasi dan menginisialisasi ulang estimasi sistem dengan beberapa pengukuran
- Cara inisialisasi dapat berbeda untuk tiap aplikasi
- Tujuannya adalah memiliki estimasi keadaan sistem yang dapat diperbarui dengan persamaan Kalman Filter menggunakan pengukuran berikutnya
- Pada langkah-langkah berikutnya, pengukuran baru dimasukkan ke filter dan estimasi keadaan diperbarui
Langkah 3: Prediksi estimasi keadaan sistem
- Ketika pengukuran ketiga masuk, estimasi keadaan sistem dipropagasikan ke depan agar selaras secara waktu dengan pengukuran
- Penyelarasan ini diperlukan untuk menggabungkan pengukuran dan estimasi keadaan
- Prediksi menggunakan model sistem
- Dalam contoh ini, model gerak linear berkecepatan konstan digunakan untuk mengaproksimasi perubahan posisi objek selama interval waktu
- Model kecepatan konstan mengasumsikan percepatan bernilai 0
- Matriks transisi keadaan merepresentasikan persamaan gerak ini
- Matriks ini digunakan untuk mempropagasikan estimasi keadaan dan matriks kovarians galat keadaan dengan tepat
- Ketika estimasi keadaan dipropagasikan ke titik waktu di masa depan, muncul ketidakpastian keadaan pada titik waktu tersebut, sehingga kovarians galat membesar
Matriks Q dan matriks H
- Matriks Q merepresentasikan process noise dari model sistem
- Model sistem adalah aproksimasi
- Selama masa hidup keadaan sistem, akurasi model dapat berubah-ubah
- Matriks Q merepresentasikan ketidakpastian ini dan ditambahkan ke noise keadaan yang sudah ada
- Dalam contoh ini, percepatan dan perlambatan nyata berkontribusi pada galat tersebut
- Matriks H adalah matriks keadaan-pengukuran, yang mengubah estimasi keadaan sistem dari ruang keadaan ke ruang pengukuran
- Dalam beberapa aplikasi, matriks ini terdiri dari 0 dan 1
- Pada aplikasi yang menggunakan Extended Kalman Filter, matriks ini diisi dengan persamaan diferensial
- Penjelasan terkait berlanjut di artikel Extended Kalman Filters
- Matriks H pada contoh ini adalah matriks sederhana yang mereduksi estimasi keadaan dan kovarians galat sehingga dapat dibandingkan hanya pada nilai posisi, bukan keseluruhan posisi dan kecepatan
Langkah 4: Menghitung Kalman Gain
- Kalman Filter menghitung Kalman Gain untuk setiap pengukuran baru
- Kalman Gain menentukan seberapa besar pengaruh pengukuran input terhadap estimasi keadaan sistem
- Jika noise pada pengukuran sangat besar, Kalman Gain membuat estimasi keadaan saat ini lebih dipercaya daripada informasi baru yang tidak akurat
- Inti algoritme Kalman Filter adalah membuat estimasi optimal dengan memberi bobot yang sesuai pada estimasi saat ini dan informasi pengukuran baru
Langkah 5: Memperbarui keadaan dan kovarians galat
- Kalman Filter menggunakan Kalman Gain untuk mengestimasi keadaan sistem dan matriks kovarians galat pada waktu pengukuran input
- Kalman Gain digunakan untuk memberi bobot yang sesuai pada pengukuran dalam dua perhitungan
- Perhitungan estimasi keadaan sistem baru
- Perhitungan kovarians galat keadaan sistem
- Estimasi keadaan yang dihitung adalah satu-satunya riwayat keadaan yang dipertahankan Kalman Filter
- Karena karakteristik ini, Kalman Filter dapat diimplementasikan bahkan pada perangkat dengan keterbatasan memori rendah
Ringkasan
- Kalman Filter adalah proses serbaguna untuk estimasi keadaan optimal
- Digunakan dalam berbagai aplikasi yang membutuhkan estimasi akurat
- Jika dibagi menjadi langkah-langkah kecil, cara kerja Kalman Filter dapat dilihat sebagai struktur yang lebih ringan dan mudah dipahami
1 komentar
Komentar Hacker News
Dalam pembahasan filter Kalman, rasanya tidak mungkin melewatkan tautan ke materi belajar yang luar biasa ini. Ini buku yang ditulis sebagai kumpulan notebook Jupyter: https://github.com/rlabbe/Kalman-and-Bayesian-Filters-in-Pyt...
Buku ini memperlakukan filter alfa-beta sebagai semacam adik dari filter Kalman yang sesungguhnya, dan setelah banyak membacanya karena belakangan saya butuh sesuatu yang mirip untuk pekerjaan, saya sadar bahwa filter alfa-beta dan keluarga Kalman sangat berfokus pada prediksi masa depan dekat, sementara yang sebenarnya saya butuhkan justru pemulusan data masa lalu
Jadi saya mulai membaca tentang pemulusan eksponensial ganda, dan itu tampak sangat cocok dengan kasus penggunaan saya, lalu semakin saya dalami, saya menyadari bahwa itu pada akhirnya hanyalah filter alfa-beta dengan nama variabel yang berbeda
Rasanya seluruh ranah matematika ini berdiri di atas beberapa teori dasar yang sama, tetapi ketika bidang-bidang berbeda mencapai sistem yang sama lewat pendekatan berbeda, nama dan notasinya berubah sehingga kesamaannya jadi tersembunyi. Terasa seperti ada inti intuisi yang relatif kecil di pusat hal-hal seperti deret pangkat, konstanta natural, penurunan gradien, filter, sistem umpan balik, dan teori sistem umum, dan kalau inti itu bisa ditangkap, banyak bagian matematika akan terhubung dengan indah
Itu bukan untuk menghemat kertas atau supaya lebih mudah ditulis. Dengan keyboard Inggris, menulis huruf Yunani bersuperskrip dan bersubskrip di LaTeX tidak lebih mudah daripada menulis kata. Itu dilakukan untuk menyampaikan jenis informasi tertentu kepada pembaca yang sulit disampaikan dengan cara lain
Notasi matematika memang tampak seperti tulisan, tetapi pada dasarnya merupakan notasi yang cukup visual, dan kata-kata panjang justru menutupi gambar itu
Jika mengikuti kuliah kontrol dan sinyal/sistem dengan baik, intuisi semacam itu akan tertanam, dan Anda akan mempelajari matematika serta istilahnya tanpa terpaku pada konvensi notasi tertentu. Intuisi yang sesungguhnya adalah “segala sesuatu adalah filter”, dan sisanya hanyalah pekerjaan menganalisis dan menyintesis ide itu
Seiring AI/ML membesar, ide-ide dari teori kontrol klasik juga mulai dipadukan dengan reinforcement learning
Biasanya Q dan R disetel manual sampai “terlihat bagus”, lalu tidak diubah lagi. Selain itu, alih-alih menyesuaikan banyak nilai di Q dan R, kita cukup menyetel satu gain secara manual
Jika noise pada pengukuran selalu sama, nilainya akan konvergen menjadi konstanta seiring waktu, dan itu baru terasa sangat berguna ketika akurasi pengukuran cukup diketahui tetapi banyak berubah
Saya baru-baru ini ditugaskan untuk mengimplementasikan filter Kalman, dan sangat sulit menemukan materi bagus yang menjelaskannya dalam bahasa yang bisa dipahami saya sebagai developer. Setelah belajar sekitar sebulan, saya menulis dua artikel, dan mungkin bisa membantu seseorang: https://www.splinter.com.au/2023/12/14/the-kalman-filter-for..., https://www.splinter.com.au/2023/12/15/the-kalman-filter-wit...
Dari sudut pandang developer, ironisnya saya baru benar-benar memahami matematikanya setelah mengimplementasikannya sendiri. Sepertinya ini cara belajar dengan membangun di atas hal-hal yang sudah dikenal, dan saya penasaran apakah ada istilah khusus untuk pendekatan seperti itu
Saya selalu berpikir matematika akan jauh lebih mudah dipelajari kalau memakai nama variabel yang deskriptif. Setidaknya di media interaktif seperti web, paling tidak bisa diberi tooltip. Saat belajar matematika, 90% waktu habis untuk mencari arti simbol
Saya juga bingung ketika subskrip di sini disebut “menunjukkan urutan pengukuran”, urutan yang dimaksud itu urutan apa. Mungkin maksudnya indeks. Sudah lama juga saya tidak menyentuh filter Kalman
Semakin murni matematikanya, biasanya cakupan variabel makin pendek. Umumnya variabel didefinisikan tepat sebelum dipakai, dan cakupannya tidak melampaui pembuktian atau penurunan itu sendiri
Meski begitu, ada juga pilihan dalam tulisan ini yang memang aneh. Misalnya memakai P sekaligus sebagai variabel dan indeks, lalu memakai P untuk matriks kovarians padahal matriks presisi adalah invers tepat dari matriks kovarians
Bagian paling menjengkelkan dari makalah riset memang ambiguitas seperti ini. Itu harus dibuat jelas. Harus memakai penjelasan absolut, bukan ungkapan relatif. Jangan menulis “lihat ke kanan”. Saya bisa saja sedang melihat ke kiri
Jika ditulis “setelah prisma diputar, kerucut cahaya...”, maka arah putarnya tidak disebutkan. Ke kiri atau ke kanan, horizontal atau atas-bawah, cepat atau lambat. Semua unsur penting ini tergambar jelas di kepala penulis, tetapi pembaca tidak bisa membaca pikirannya
Subskrip “p” mungkin berarti prediction, yaitu prediksi. x_p pada waktu 3 adalah keadaan yang diharapkan pada waktu 4. Tetapi ketika waktu 4 benar-benar tiba, kita menghitung x_4 dengan memasukkan pengukuran baru
Tepatnya, x_4 ini berbeda dari x_p yang dihitung pada waktu 3. Prediksi selalu sedikit meleset
Masalahnya adalah orang yang baru mulai belum menguasai konsep maupun notasi standar di tiap ranah masalah, sehingga rasa sakit saat masuk ke topik baru tetap ada
Filter Kalman mungkin salah satu kasus langka dalam matematika di mana versi yang disederhanakan terlalu disederhanakan sampai bentuk aslinya hampir tidak terlihat lagi
Yang sebenarnya dilakukan adalah mendapatkan satu pengukuran, lalu mensimulasikan kemungkinan keadaan-keadaan masa depan, kemudian menggabungkan informasi ini dengan pengukuran berikutnya, dan mengulanginya
Misalnya, ambil beberapa foto bola tenis dan dari foto pertama perkirakan posisi serta kecepatannya, lalu simulasikan ke mana ia akan bergerak dan bandingkan dengan foto berikutnya untuk melihat perkiraan mana yang lebih dekat dengan kebenaran. Dengan cara yang lebih kuno, kita juga bisa membayangkan mengukur ketinggian matahari untuk membuat garis lokasi yang mungkin di peta, lalu membandingkannya dengan titik tempat kita semula mengira diri kita berada
Tentu saja perhitungan yang tepat hampir mustahil dilakukan dalam praktik. Karena itu ia disederhanakan lewat sampling. Itu pun masih sulit, jadi diasumsikan distribusinya cukup dekat dengan distribusi Gaussian. Lalu disederhanakan lagi dengan mengasumsikan perubahan sistem adalah transformasi linear; hasilnya adalah filter Kalman yang dibahas di sini
Akan mengejutkan kalau seseorang bisa memahami apa yang sebenarnya terjadi hanya dari melihat aljabar linear
Penjelasan inilah yang untuk pertama kalinya memberi saya intuisi tentang apa yang sebenarnya sedang terjadi. Bagi saya yang berlatar belakang komputasi, namanya sendiri cukup menyesatkan. Ini bukan filter seperti dalam pemrosesan stream atau SQL
Filter Kalman mencoba memperkirakan masukan tersembunyi yang menghasilkan nilai pengukuran. Untuk itu ia membentuk masalah
meminimalkan [pengukuran_aktual - pengukuran_harapan(x)]^2/s^2 terhadap x. Di sinisadalah sigma dari noiseIni berasal dari masalah estimasi keadaan berupa
memaksimalkan likelihood melihat pengukuran_aktual terhadap x. Karena pada fungsi likelihood, suku pentingnya hanya-([x-expected(x)]/s)^2. Cukup lihat eksponen dari distribusi normal, atau sebenarnya hampir semua distribusi eksponensialKarena
pengukuran_aktualadalah konstanta, jika fungsipengukuran_harapanlinear maka ini langsung menjadi optimisasi cembung. Turunkan, samakan dengan 0, lalu selesaikan, dan keluarlah langkah pembaruan filter KalmanJika fungsinya non-linear, pada dasarnya kita melinearkan persamaan itu, meminimalkannya, lalu mengembalikan solusi dari “linearisasi palsu” tersebut, yaitu seperti melakukan satu langkah Newton-Raphson. Ini cuma kalkulus dan aljabar linear tingkat sarjana, hanya saja tidak ada yang menjelaskannya seperti itu
Namun ini juga bisa sepenuhnya keliru. Ini adalah hack dari tahun 1960-an untuk mencoba memaksimalkan fungsi likelihood dengan linearisasi rekursif satu langkah seperti ini. Karena salah membaca batas Cramér-Rao, beberapa generasi insinyur percaya ini optimal, padahal sebenarnya tidak
Sekarang sumber daya komputasi setidaknya 10.000 kali lebih besar, dan performa yang lebih baik bisa diperoleh dengan menyusun persamaan non-linear lalu menyelesaikannya dalam beberapa langkah Newton-Raphson, atau menyimpan riwayat pengukuran yang panjang dan menyelesaikan seluruh kumpulan itu dengan beberapa langkah Newton-Raphson, atau memakai representasi campuran Gaussian untuk mengakomodasi fungsi pengukuran multimodal
Hal-hal seperti ini telah dibahas dengan baik dalam riset estimasi keadaan sejak 1980-an sampai sekarang, tetapi buku teks masih terasa seperti dipahat di batu pada tahun 1972
Batas Cramér-Rao hanya terdefinisi ketika semua fungsi likelihood pengukuran dapat dilinearkan pada keadaan sebenarnya, yang hanya mungkin secara asimtotik pada kumpulan yang mempertahankan semua pengukuran, mustahil sebelum waktu tak hingga, dan juga mustahil dengan filter rekursif
Di antara penjelasan lama, tulisan ini bagus: https://www.bzarg.com/p/how-a-kalman-filter-works-in-picture..., https://news.ycombinator.com/item?id=13449229
Kalau benar-benar perlu Kalman filter, rasanya artikel ini, dokumen Wikipedia, atau source implementasinya (https://github.com/LdDl/kalman-rs/blob/master/src/kalman/kal...) cukup untuk dibaca dan dipahami
Tapi dari pengalaman saya, hampir semua orang di seluruh dunia belajar paling baik lewat contoh, yakni sebagai pembelajar visual. Karena itu cukup mengejutkan bahwa tutorial di tengah halaman tidak memasukkan angka contoh ke dalam rumus. Mungkin saya melewatkannya, tetapi gambar pun baru mulai muncul setelah satu halaman penuh teks “apa itu Kalman filter”, dan gambar itu sendiri malah berisi lebih banyak rumus
Hal seperti ini begitu sering terjadi sampai terasa mengejutkan. Dalam bentuk yang lebih ringan, masalah yang sama juga muncul pada library software yang tidak menyertakan contoh kode
Hal yang paling terasa buat saya adalah bahwa jika dua distribusi pengukuran yang tidak pasti, yaitu distribusi dengan varians besar, digabungkan, hasilnya menjadi pengukuran yang lebih pasti, yaitu distribusi yang lebih sempit
Jika nilai pengukuran yang lebih pasti ini digabungkan lagi dengan pengukuran berikutnya dan diulang terus, itulah Kalman filter
Di antara kumpulan video yang menjelaskan KF, yang ini benar-benar bagus. Saya memahaminya lebih baik daripada materi artikel aslinya: https://www.youtube.com/watch?v=CaCcOwJPytQ
Almarhum ayah saya sering menggunakan filter ini sepanjang kariernya, sejak masa ketika filter ini baru mulai ditemukan. Beliau bekerja dengan radar dan sistem pemandu misil
Coba pejamkan mata dan berjalan sebentar. Bayangkan posisi Anda, lalu buka mata—apakah posisi sebenarnya berbeda dari posisi yang Anda bayangkan?
Langkah terakhir itu, yaitu memperbarui keyakinan tentang variabel keadaan dengan menggunakan pengamatan, adalah apa yang dilakukan Kalman filter