- Karena pengukuran posisi dan kecepatan di dunia nyata selalu berfluktuasi, filter Kalman dapat dipahami sebagai cara menggabungkan beberapa sumber informasi yang tidak sempurna untuk menghasilkan estimasi keadaan yang lebih dapat dipercaya
- Dalam contoh posisi kapal, model berupa kecepatan mesin 10 m/s meleset karena angin dan ombak, sementara sensor seperti GPS juga tidak selalu akurat karena noise atau gangguan
- Kode contoh menunjukkan intuisi filter Kalman dengan 1000 penumpang yang masing-masing membuat estimasi berbasis kecepatan dan pengukuran sensor, lalu menggabungkan keduanya dengan rata-rata tertimbang
- Keandalan sumber informasi dihitung dari varians nilai-nilai pengukurannya; sumber yang fluktuasinya besar lebih sedikit dipercaya, sedangkan yang konsisten diberi bobot lebih besar menggunakan
1/variance
- Saat sensor normal, nilai sensor lebih diikuti; pada bagian yang berfluktuasi seperti
t=3 dan t=6, pengaruhnya otomatis berkurang sehingga estimasi yang lebih stabil tetap dipertahankan
Situasi ketika filter Kalman dibutuhkan
- Filter Kalman dapat dilihat seperti corong yang memadatkan beberapa sumber informasi yang noisy menjadi satu nilai statistik yang lebih akurat
- Secara matematis, ini terkait dengan aljabar linear, teori probabilitas, dan kalkulus, tetapi di sini fokusnya adalah intuisi, bukan teori lengkap
- Asumsikan sebuah kapal berangkat dari pelabuhan
x=0, bergerak dalam satu dimensi, dan mesinnya memberikan kecepatan konstan 10 m/s
- Di dunia ideal, posisi setelah 2 detik adalah
2 * 10 = 20m, tetapi di dunia nyata kecepatan dan posisi tidak terjaga persis karena mesin, angin, dan ombak
- Karena itu, sulit memastikan posisi kapal sebenarnya hanya dengan rumus posisi
Sensor juga tidak sempurna
- Jika ada sensor seperti GPS, posisi pada waktu tertentu bisa diukur langsung, tetapi nilai pengukuran sensor juga tidak selalu akurat
- GPS bisa memberikan nilai yang dekat dengan posisi sebenarnya pada detik ke-3, seperti 29.998 m atau 30.002 m, tetapi sangat jarang bisa juga menyimpang jauh seperti 100 m
- Di area tanpa cakupan satelit, sensor GPS pada dasarnya bisa tidak berfungsi
- Jika sensor tidak pernah offline dan bisa mengukur nilai yang diinginkan dengan presisi arbitrer, filter Kalman tidak diperlukan
- Filter Kalman dapat menggabungkan berbagai sumber informasi seperti estimasi posisi berbasis kecepatan, estimasi GPS, radar, dan sonar untuk memperkirakan posisi dengan lebih akurat
Estimasi posisi lewat kode
- Contoh ini mengasumsikan ada 1000 penumpang di kapal, dan setiap penumpang memiliki perangkat GPS sendiri
- Setiap penumpang terlebih dahulu memperkirakan posisi baru dengan menambahkan kecepatan dan variasi faktor eksternal ke posisi sebelumnya
from random import gauss
def new_position(last):
velocity = 10
wind = gauss(0, 2)
wave = gauss(0, 0.1)
return last + velocity + wind + wave
gauss menghasilkan nilai acak positif atau negatif, dan parameter kedua menunjukkan besar variasinya
- Karena efek angin dan ombak tidak dapat diukur langsung, dalam contoh ini noise dimodelkan sebagai bilangan acak dengan rata-rata 0 dan simpangan baku
2 serta 0.1
- Pada tahap kedua, sensor menambahkan noise sensor ke posisi sebenarnya lalu mengembalikan nilai pengukuran
def sensor(t):
if t == 3:
# oops, passing through a thunderstorm. GPS fluctuating!
sensor_noise = gauss(5, 10)
elif t == 6:
# uh-oh, satellite unavailable!
sensor_noise = gauss(-5, 10)
else:
sensor_noise = gauss(0, 1)
return true_position[t] + sensor_noise
- Pada
t=3, situasi dimodelkan sebagai GPS yang berfluktuasi karena badai petir; pada t=6, satelit tidak tersedia
- Bahkan pada waktu yang sama, nilai pengukuran sensor bisa berbeda untuk tiap penumpang
Jalur pergerakan sebenarnya dan rata-rata sederhana
- Posisi sebenarnya kapal diberikan oleh daftar berikut
true_position = [0, 9, 19.2, 28, 38.1, 48.5, 57.2, 66.2, 77.5, 85, 95.2]
- Kapal berangkat dari pelabuhan
x=0, lalu berada di 9 m setelah 1 detik, 19.2 m setelah 2 detik, dan selanjutnya bergerak seperti nilai-nilai dalam daftar
- Tujuan penumpang adalah memprediksi posisi tiap detik seakurat mungkin dari nilai pengukuran yang noisy dan tidak dapat sepenuhnya dipercaya
- Jika pada
t=1 estimasi berbasis kecepatan dari satu penumpang adalah 9.37 dan pengukuran sensor adalah 8.98, maka rata-rata sederhananya adalah 9.17
- Ketika posisi sebenarnya 9 m, rata-rata sederhana ini punya galat lebih kecil dibanding estimasi kecepatan, tetapi lebih buruk dibanding pengukuran sensor pada contoh tersebut
Rata-rata tertimbang dan keandalan
- Metode yang lebih baik daripada rata-rata sederhana adalah menggunakan rata-rata tertimbang
def combine(A, B, trustA, trustB):
total_trust = trustA + trustB
return (A * trustA + B * trustB) / total_trust
combine(9.37, 8.98, 10, 1) lebih mempercayai estimasi kecepatan, sehingga hasilnya 9.33, dekat dengan 9.37
combine(9.37, 8.98, 1, 10) lebih mempercayai pengukuran sensor, sehingga hasilnya 9.01, dekat dengan 8.98
- Rata-rata tertimbang berbasis keandalan ini adalah intuisi inti filter Kalman, sekaligus pusat gaya dalam menggabungkan data
- Sumber informasi mana yang lebih dipercaya ditentukan oleh varians
- Sumber informasi yang kesimpulannya banyak berfluktuasi kurang dipercaya
- Sumber informasi yang kesimpulannya konsisten lebih dipercaya
- Jika dari 10 stasiun radio, 4 mengatakan hujan dan 6 mengatakan cerah, sementara dari 10 situs web, 9 mengatakan hujan, maka pihak situs web memiliki varians lebih rendah sehingga bisa lebih dipercaya
Tahap update
- Update keseluruhan membuat estimasi berbasis kecepatan dan pengukuran sensor untuk setiap penumpang, lalu menghitung keandalan dari varians kedua kumpulan pengukuran tersebut
from statistics import variance
def update(t, last):
velocity_updates = []
sensor_updates = []
for p in range(1000):
velocity_updates.append(new_position(last[p]))
sensor_updates.append(sensor(t))
fluctuation_velocity = variance(velocity_updates)
fluctuation_sensor = variance(sensor_updates)
trust_velocity = 1 / fluctuation_velocity
trust_sensor = 1 / fluctuation_sensor
combined = []
for p in range(1000):
combined.append(combine(
A=velocity_updates[p],
B=sensor_updates[p],
trustA=trust_velocity,
trustB=trust_sensor
))
return sensor_updates, velocity_updates, combined
- Karena semakin besar varians semakin rendah keandalannya, digunakan
1/variance
- Setiap penumpang memperbarui posisinya masing-masing secara terpisah
- Setelah pembaruan posisi semua penumpang selesai, estimasi posisi sebenarnya kapal dapat disimpulkan dari rata-rata posisi para penumpang
Cara membaca hasil
- Fungsi
update_plot menyimpan posisi sebenarnya, estimasi sensor, estimasi kecepatan, dan estimasi gabungan pada tiap waktu untuk membuat plot
- Loop utama terus memperbarui estimasi posisi pada tiap waktu menggunakan estimasi terbaik yang saat ini dimiliki para penumpang
- Pada plot, envelope di sekitar garis menunjukkan ketidakpastian; semakin lebar, semakin besar ketidakpastian terhadap angka tersebut
- Pada rentang
t=0.75 hingga t=1 ketika sensor berfungsi normal, estimasi posisi gabungan lebih baik daripada hanya memakai estimasi kecepatan, tetapi bisa lebih buruk daripada hanya memakai pengukuran sensor
- Pada rentang
t=2 hingga t=4 ketika sensor rusak, estimasi gabungan menunjukkan hasil yang lebih baik daripada hanya memakai pengukuran sensor yang rusak
- Pada rentang
t=4 hingga t=5 ketika sensor pulih, filter Kalman mulai kembali lebih menyukai sensor
Lampiran: gauss dan varians
gauss(0, 0.1) dan gauss(0, 2), yang merupakan normal distribution function, terutama menghasilkan nilai acak di sekitar 0
- Parameter kedua, yaitu simpangan baku, mengontrol seberapa besar nilai pengukuran berfluktuasi
gauss(0, 0.1) kemungkinan besar menghasilkan nilai kecil di sekitar 0 seperti 0.06, -0.07, 0.02
gauss(0, 2) kemungkinan besar menghasilkan nilai yang tersebar lebih lebar seperti 1.05, -1.06, 1.29, -1.72
- Dalam kode contoh, diasumsikan angin berubah lebih besar, sedangkan gelombang air berubah lebih kecil
- Varians adalah ukuran konsistensi; jika konsistensi tinggi, varians rendah, dan jika konsistensi rendah, varians tinggi
- Distribusi dengan simpangan baku 2 memiliki varians 4, sedangkan distribusi dengan simpangan baku 0.1 memiliki varians 0.01
1 komentar
Opini Hacker News
Tulisannya menarik dibaca, tetapi implementasinya keliru. Kesalahan terbesarnya adalah ketidakpastian tidak dipropagasikan sepanjang sumbu waktu, sehingga galatnya diremehkan
Ini juga terlihat pada grafik: rentang galat seharusnya mencakup keadaan sebenarnya pada sebagian besar waktu, tetapi pada hasilnya tidak demikian
Bukan penumpang yang menambahkan noise ke nilai estimasi; dari sudut pandang penumpang, jika keadaan pada waktu k diberikan, nilai harapan keadaan pada waktu k+1 hanyalah
position_k+1 = position_k + velocity * Delta_t. Ada noise pada dinamika sebenarnya, dan filter merefleksikannya dengan menambahkannya ke kovarians estimasiAlasan kodenya tidak langsung rusak adalah karena dengan 1.000 penumpang, ia mengambil banyak sampel dinamika lalu menghitung varians hasilnya secara numerik; ini cukup berbeda dari cara yang biasanya dilakukan dalam praktik
Selain itu, GPS dipengaruhi cuaca adalah kesalahpahaman umum, dan kenyataannya tidak demikian. Definisi konsistensi yang dipakai dalam tulisan itu juga tidak standar. Dalam teori estimasi, mengatakan sebuah estimator konsisten berarti estimasinya konvergen ke nilai sebenarnya seiring bertambahnya data
Bagus karena penjelasannya dibuat mudah untuk pembaca umum, tetapi beberapa kesalahpahaman tampaknya menimbulkan masalah. Saya mahasiswa pascasarjana teori estimasi, jadi kalau dibahas lebih jauh saya mungkin bisa membantu
Sampai-sampai saya jadi bertanya-tanya mengapa di kuliah pemrosesan sinyal universitas Kalman Filter tidak diajarkan sesederhana ini. Konsep matematika memang tepat diajarkan secara matematis, tetapi bagi orang yang kurang pengetahuan latar, itu menimbulkan kehilangan informasi
Dulu saya pernah mengajarkan transformasi kosinus diskret dan transformasi wavelet dengan berfokus pada gambar; cara memberi intuisi terlebih dahulu daripada ketelitian formal selalu lebih berhasil dibanding urutan sebaliknya
Ada beberapa kemungkinan alasan profesor tidak memberi intuisi terlebih dahulu. Bisa jadi sang profesor sendiri lebih punya keahlian mendalam dalam angka dan manipulasi persamaan daripada intuisi; bisa jadi kemampuan mengajar tidak diberi imbalan sehingga waktu untuk menjelaskan secara intuitif lebih baik dipakai untuk proposal hibah riset atau mengelola mahasiswa doktoral; dan bisa juga setelah memahami matematikanya, penjelasan intuitif justru terasa seperti “jalan yang sulit”, sehingga otak menolak kembali ke sana
Menurut saya alasan ketiga khususnya yang paling besar. Ini juga melampaui pendidikan matematika, yaitu perbedaan antara keahlian dan kemampuan mengajar. Kalau ingin belajar drive golf, mungkin lebih baik belajar dari orang yang mulai dari 100 yard lalu secara konsisten bisa memukul 300 yard, daripada dari orang yang memukul paling jauh
Sebagai peringatan umum bagi orang yang ingin mengimplementasikan Kalman Filter, untuk cara menangani ketidakstabilan numerik, ada baiknya membaca beberapa halaman awal https://www.stat.berkeley.edu/~brill/Stat248/kalmanfiltering...
Dalam praktik, meski melakukan itu, saya jarang melihat artefak numerik yang mencolok, tetapi ini solusi yang cukup menarik
Sebagai pelengkap tulisan ini, kalau ingin pengantar yang lebih menyeluruh dan matematis ke keluarga Kalman Filter, saya sangat merekomendasikan buku ini: https://github.com/rlabbe/Kalman-and-Bayesian-Filters-in-Pyt...
Buku ini ditulis oleh software engineer yang harus mengimplementasikan Kalman Filter untuk pekerjaan, sehingga cara memotivasi dan menyampaikan konsepnya mungkin cocok untuk kalangan pembaca ini. Ditulis sebagai notebook Jupyter interaktif, sehingga Anda bisa meng-clone repositorinya dan menjalankannya sendiri sambil mengikuti
Karena dimulai dari filter sederhana, lalu secara bertahap memperbaikinya dengan memasukkan aturan Bayes dan memperluasnya ke distribusi probabilitas, buku ini menyediakan jalur masuk yang landai menuju Kalman Filter
Ada satu aspek yang terlewat. Saat mengambil rata-rata tertimbang dari prediksi dan pengukuran, bobot Kalman Filter dapat berubah seiring waktu. Kalau tidak, menurut saya ia akan disebut dengan nama lain
Contoh mengukur nilai yang berubah perlahan dengan satu sensor itu bagus. Misalnya pada indikator bahan bakar, dalam skala detik sebaiknya diasumsikan tidak ada perubahan, tetapi pengukurannya bisa mengandung noise seperti bahan bakar yang berguncang di dalam tangki
Dalam kasus ini, Kalman Filter tampak seperti filter lolos-rendah orde pertama dengan gain yang meluruh secara eksponensial. Frekuensi cut-off-nya berubah, sehingga level awal bisa ditemukan cepat dalam beberapa detik, lalu setelah itu noise bisa diabaikan dengan frekuensi cut-off yang sangat rendah seperti 0,01 Hz
Artikel yang bagus tentang alat yang penting
Sepemahaman saya, Linear Kalman Filter adalah solusi optimal untuk masalah linear, dan relatif mudah dipahami serta diimplementasikan. Namun sebagian besar penerapan yang pernah saya lihat bersifat non-linear
Extended Kalman Filter dan Unscented Kalman Filter jauh lebih sulit dipahami dan diimplementasikan, dan materi serta pustakanya juga lebih sedikit dan kurang berguna
Misalnya, saat menangani perangkat AHRS/GNSS CAN untuk UAV kecil, Extended Kalman Filter yang saya lihat di PX4 atau Ardupilot sangat kompleks dan punya banyak parameter. Jadi pendekatan yang dimulai dari prinsip dasar quaternion, lalu sedikit demi sedikit mengoreksi solusi gyro ke arah “atas” dari akselerometer dan vektor inklinasi dari magnetometer terasa lebih sederhana
Jika magnitudo akselerasi sangat berbeda dari 1G atau vektor medan magnet sangat berbeda dari kekuatan medan magnet bumi lokal, bobot pembaruan sensor tersebut diturunkan atau dilewati, dan gyro dibiarkan berjalan apa adanya. Mungkin besar kemungkinan EKF adalah jawaban yang benar, tetapi saya menyerah untuk membuatnya dalam bentuk yang mudah dipahami, dibuat, disetel, dan didiagnosis
Namun pada quadrotor, kesulitan besarnya adalah rotasi. Model linear Kalman Filter mengasumsikan semuanya berada di ruang Euclidean, tetapi rotasi berada di atas manifold. Dalam kasus quaternion, manifold ini adalah himpunan unit quaternion
Jika EKF diterapkan secara naif untuk mengestimasi quaternion, hasilnya tidak lagi menjadi unit quaternion dan estimasinya rusak. Ada metode-metode yang dikenal luas untuk menangani kendala manifold ini, tetapi persamaannya termasuk yang paling buruk rupa di antara yang pernah saya tuangkan ke dalam kode
Sebagai contoh sederhana, kita bisa memikirkan keadaan
(x, y)yang karena hukum fisika harus selalu berada di lingkaran satuan. Dinamika sebenarnyaf(x, y)menghasilkan titik baru di atas lingkaran, tetapi dinamika aproksimasi hasil linearisasinya tidak menjamin tetap berada di lingkaran satuan, sehingga bisa menghasilkan keadaan non-fisik atau estimasi keadaan EKF yang tidak validOpsi yang layak dilihat antara lain ForneyLab.jl, Infer.net, Gen.jl, dan Pyro
Namun ada banyak cara menggunakan Kalman Filter, dan tergantung dari mana memulainya, menangani transformasi non-linear dengan benar bisa menjadi sangat merepotkan
Saya punya rabun jauh dan astigmatisme, dan ketika menutup satu mata lalu melihat sesuatu seperti jam dinding, saya menyadari bahwa masing-masing mata menghasilkan citra yang terdistorsi secara berbeda. Kedua mata memang sedikit berbeda
Namun saat melihat jam dengan kedua mata, citranya jauh lebih jelas, dan lebih baik daripada melihat dengan salah satu mata saja. Skenario dalam artikel tentang 1000 penumpang kapal yang melaporkan koordinat GPS masing-masing mengingatkan saya pada fenomena ini
Sepertinya otak juga banyak menggunakan algoritma cerdas seperti Kalman Filter
Apakah benar memahami Kalman Filter sebagai sesuatu yang memberikan estimasi nilai dari observasi berisik yang lebih baik daripada rata-rata sederhana?
Misalnya jika mengukur sesuatu 3 kali dan hasilnya 7, 8, 9, kita akan menduga nilai sebenarnya 8; apakah Kalman Filter akan memberikan estimasi yang berbeda?
Kalman Filter secara tradisional digunakan untuk mengestimasi sesuatu yang bergerak seiring waktu. Bayangkan seseorang dalam video, atau semacam random walk
Jika diasumsikan ada hubungan seperti kecepatan dan arah saat ini antara dua titik waktu atau pengukuran berurutan, informasi dari model gerak dan informasi dari model pengukuran yang berisik dapat digabungkan untuk mengestimasi posisi atau nilai, atau bahkan seluruh riwayat pergerakan, dengan lebih baik
Jika model geraknya salah secara bermakna, estimasinya tidak akan membaik. Banyak metode lanjutan setelahnya berfokus memasukkan model gerak yang lebih canggih, seperti selip roda dalam robotika
Misalnya ketika mengukur sebuah konstanta, model dasarnya bisa berupa konstanta dengan ketidakpastian awal, misalnya distribusi Gaussian dengan simpangan baku, serta pengukuran yang juga memiliki derau Gaussian dan simpangan baku. Ketidakpastian awal di sekitar konstanta yang ingin diestimasi dan ketidakpastian pengukurannya bisa disetel
Dalam contoh ini, Kalman Filter tidak berperilaku seperti rata-rata. Jika pengukurannya bagus, yaitu ketidakpastiannya rendah, ia akan cepat konvergen; jika pengukurannya buruk, estimasinya akan berfluktuasi dan butuh lebih lama untuk konvergen
Dan tidak benar bahwa Kalman Filter hanya dipakai untuk benda bergerak. Ia juga selalu digunakan untuk estimasi konstanta, hanya saja lebih terkenal pada objek bergerak
Kalman Filter menangani kasus ketika sampel-sampel berkorelasi karena suatu dinamika linear. Nilai pengukuran juga tidak harus berupa objek yang diminati itu sendiri; bisa berupa fungsi linear dari objek tersebut yang ditambah derau Gaussian
Karena itu, pengetahuan bahwa kita melihat 7 pada pengukuran pertama mengubah probabilitas melihat 8 pada pengukuran kedua. Jika hanya mengambil rata-rata sampel seperti di atas, umumnya tidak akan konvergen ke nilai rata-rata sebenarnya
Apa yang akan dihasilkan dalam contoh itu bergantung pada model yang tepat. Bahkan dalam skenario paling sederhana yang bisa dibayangkan, seperti dalam Bayes, kita harus menentukan akan mulai dari nilai harapan apa
Jika ekspresi itu dienkode sebagai model Gaussian linear, jadilah Kalman Filter
Teks singkat lain yang memberi saya pencerahan saat memahami Kalman Filter adalah catatan John D. Cook: https://www.johndcook.com/blog/applied-kalman-filtering/
Pemodelan sistem tradisional berbasis kalkulus dan persamaan diferensial menganggap tidak ada ketidakpastian dalam data dan semuanya tercakup dalam model sistem, sedangkan estimator berbasis data memandang bahwa “semuanya ada di dalam data” dan sepenuhnya mengabaikan model proses fisik yang menghasilkan data.
Keindahan Kalman Filter terletak pada penggabungan kedua pendekatan ini.
Ada juga tulisan lain dengan visualisasi yang bagus: https://www.bzarg.com/p/how-a-kalman-filter-works-in-picture...
Tulisan ini sudah tiga kali muncul di HN.