Giải thích đơn giản về bộ lọc Kalman
(thekalmanfilter.com)- Bộ lọc Kalman là một thuật toán dùng trong dự đoán và điều khiển dựa trên cảm biến, tạo ra ước lượng trạng thái chính xác hơn theo thời gian thực từ các phép đo có nhiễu hoặc không chính xác
- Không chỉ đơn thuần làm mượt giá trị đo, nó còn có thể ước lượng cả các biến trạng thái như vị trí và vận tốc vốn khó quan sát trực tiếp
- Ví dụ theo dõi bằng radar cho thấy luồng xử lý nhận đầu vào là các phép đo vị trí 2D và hiệp phương sai, rồi ước lượng vị trí và vận tốc của vật thể dưới dạng vector trạng thái 4×1
- Sau khi khởi tạo trạng thái bằng hai phép đo đầu tiên, hệ thống lặp lại các bước dự đoán, tính Kalman Gain, rồi cập nhật trạng thái và hiệp phương sai sai số
- Bộ lọc chỉ giữ một lịch sử là giá trị ước lượng trạng thái hiện tại, nên cũng dễ triển khai trên thiết bị có ràng buộc bộ nhớ
Bức tranh tổng thể của bộ lọc Kalman
- Có thể xem bộ lọc Kalman như một hộp đen có đầu vào và đầu ra
- Đầu vào là các phép đo có nhiễu hoặc đôi khi không chính xác
- Đầu ra là các giá trị ước lượng có ít nhiễu hơn và chính xác hơn
- Giá trị ước lượng có thể là tham số trạng thái của hệ thống không được đo hoặc quan sát trực tiếp
- Nó được dùng để ước lượng với độ chính xác cao theo thời gian thực cả các tham số có thể quan sát và không thể quan sát
- Các giá trị ước lượng có độ chính xác cao được dùng cho dự đoán và ra quyết định chính xác
- Vì vậy nó thường được dùng trong robotics và các hệ thống thời gian thực cần thông tin đáng tin cậy
Vấn đề mà bộ lọc Kalman giải quyết
- Dựa trên các phép đo không chính xác hoặc có nhiễu, nó ước lượng trạng thái của biến, hoặc các biến khác khó quan sát trực tiếp, với độ chính xác cao hơn
- Một số ứng dụng tiêu biểu gồm:
- Theo dõi đối tượng: dùng vị trí đo được để ước lượng chính xác hơn vị trí và vận tốc của vật thể
- Ước lượng cân nặng bằng cân điện tử: ước lượng trọng lượng vật thể từ áp lực tác động lên bề mặt
- Dẫn đường, định vị và điều khiển: dùng cảm biến IMU để ước lượng vị trí, vận tốc, gia tốc và áp dụng vào điều khiển chuyển động tiếp theo
- Điểm mạnh của bộ lọc Kalman không chỉ là làm mượt phép đo mà là khả năng ước lượng các tham số hệ thống khó đo lường
- Trong hệ thống thời gian thực, các giá trị ước lượng chính xác hơn sẽ dẫn tới khả năng điều khiển và chức năng tốt hơn
Đầu vào và đầu ra của ví dụ theo dõi radar
- Ví dụ nói về tình huống theo dõi radar các máy bay và vật thể quanh sân bay
- Trạng thái quỹ đạo đầu ra được dùng để hiển thị cho các nhân viên điều hành kiểm soát không lưu giám sát vùng trời
- Radar xuất ra các phép đo vị trí x, y trong hệ tọa độ Descartes 2D
- Giá trị đo được biểu diễn bằng vector cột 2×1 z
- Ma trận phương sai-hiệp phương sai của phép đo được biểu diễn bằng R
- Mốc thời gian đo được biểu diễn bằng t
- Chỉ số dưới m biểu thị tham số đo, còn k biểu thị thứ tự phép đo
- Bộ lọc Kalman ước lượng vị trí và vận tốc của vật thể từ các phép đo radar
- Giá trị ước lượng được biểu diễn bằng vector cột 4×1 x
- Ma trận phương sai-hiệp phương sai của giá trị ước lượng được biểu diễn bằng ma trận 4×4 P
- Mốc thời gian của giá trị ước lượng trạng thái được ký hiệu là T
Bước 1: Khởi tạo trạng thái hệ thống
- Cách khởi tạo của bộ lọc Kalman thay đổi tùy ứng dụng
- Trong ví dụ theo dõi radar này, trạng thái hệ thống được khởi tạo bằng phép đo đầu tiên
- Dù phép đo đầu vào chỉ chứa thông tin vị trí, trạng thái hệ thống đầu ra lại chứa vị trí và vận tốc của vật thể
- Khi phép đo đầu tiên đi vào, thông tin duy nhất có thể biết là vị trí tại thời điểm đó
- Sau lần ước lượng đầu tiên, giá trị ước lượng trạng thái hệ thống được đặt bằng vị trí đầu vào
- Hiệp phương sai sai số của trạng thái hệ thống được đặt theo độ chính xác vị trí của phép đo đầu tiên
Bước 2: Khởi tạo lại trạng thái hệ thống
- Vì cần phép đo vị trí thứ hai để ước lượng vận tốc, giá trị ước lượng trạng thái hệ thống được khởi tạo lại
- Vận tốc được tính bằng xấp xỉ tuyến tính
- Vận tốc = quãng đường di chuyển / thời gian di chuyển
- Giá trị ước lượng trạng thái hệ thống đã cập nhật gồm vị trí của phép đo thứ hai và vận tốc đã tính
- Hiệp phương sai sai số trạng thái hệ thống đã cập nhật chứa độ chính xác vị trí của phép đo thứ hai và độ chính xác vận tốc xấp xỉ
- Giá trị xấp xỉ độ chính xác vận tốc có thể được điều chỉnh bằng tuning sau khi cho dữ liệu đi qua bộ lọc
- Trong ví dụ, hạng phương sai vận tốc được đặt là 10⁴
- Giá trị này biểu thị mức bất định lớn đối với giá trị trạng thái vận tốc
- Đơn vị vận tốc trong ví dụ là m/s
Xử lý lặp sau khi khởi tạo
- Hai bước đầu là quá trình khởi tạo và khởi tạo lại giá trị ước lượng hệ thống bằng một vài phép đo
- Cách khởi tạo có thể khác nhau tùy ứng dụng
- Mục tiêu là có được giá trị ước lượng trạng thái hệ thống để có thể cập nhật các phép đo tiếp theo bằng các phương trình của bộ lọc Kalman
- Ở các bước sau, phép đo mới sẽ được phản ánh vào bộ lọc và giá trị ước lượng trạng thái sẽ được cập nhật
Bước 3: Dự đoán giá trị ước lượng trạng thái hệ thống
- Khi phép đo thứ ba đi vào, giá trị ước lượng trạng thái hệ thống được lan truyền tiến về phía trước để căn chỉnh thời gian với phép đo
- Việc căn chỉnh này cần thiết để kết hợp phép đo với giá trị ước lượng trạng thái
- Quá trình dự đoán sử dụng mô hình hệ thống
- Trong ví dụ, mô hình chuyển động tuyến tính với vận tốc không đổi được dùng để xấp xỉ sự thay đổi vị trí của vật thể trong khoảng thời gian đó
- Mô hình vận tốc không đổi giả định gia tốc bằng 0
- Ma trận chuyển trạng thái biểu diễn phương trình chuyển động này
- Ma trận này được dùng để lan truyền đúng cách giá trị ước lượng trạng thái và ma trận hiệp phương sai sai số trạng thái
- Khi lan truyền giá trị ước lượng trạng thái tới một thời điểm tương lai, bất định của trạng thái tại thời điểm đó xuất hiện nên hiệp phương sai sai số sẽ tăng lên
Ma trận Q và ma trận H
- Ma trận Q biểu diễn nhiễu quá trình của mô hình hệ thống
- Mô hình hệ thống là một xấp xỉ
- Độ chính xác của mô hình thay đổi trong suốt vòng đời của trạng thái hệ thống
- Ma trận Q biểu diễn bất định này và được cộng thêm vào nhiễu trạng thái hiện có
- Trong ví dụ, gia tốc và giảm tốc thực tế góp phần tạo ra sai số này
- Ma trận H là ma trận trạng thái-đo lường, chuyển đổi giá trị ước lượng trạng thái hệ thống từ không gian trạng thái sang không gian đo lường
- Trong một số ứng dụng, đây là ma trận gồm các số 0 và 1
- Trong các ứng dụng dùng Extended Kalman Filter, nó được điền bằng các phương trình vi phân
- Phần giải thích liên quan được nối tiếp trong bài Extended Kalman Filters
- Ma trận H trong ví dụ này là một ma trận đơn giản giúp rút gọn giá trị ước lượng trạng thái và hiệp phương sai sai số để chỉ so sánh được các giá trị vị trí, thay vì toàn bộ vị trí và vận tốc
Bước 4: Tính Kalman Gain
- Bộ lọc Kalman tính Kalman Gain cho mỗi phép đo mới
- Kalman Gain quyết định mức độ ảnh hưởng của phép đo đầu vào lên giá trị ước lượng trạng thái hệ thống
- Nếu nhiễu của phép đo quá lớn, Kalman Gain sẽ tin tưởng giá trị ước lượng trạng thái hiện tại nhiều hơn là thông tin mới nhưng không chính xác
- Cách kết hợp có trọng số phù hợp giữa giá trị ước lượng hiện tại và thông tin đo mới để tạo ra giá trị ước lượng tối ưu là cốt lõi của thuật toán bộ lọc Kalman
Bước 5: Cập nhật trạng thái và hiệp phương sai sai số
- Bộ lọc Kalman dùng Kalman Gain để ước lượng trạng thái hệ thống và ma trận hiệp phương sai sai số tại thời điểm của phép đo đầu vào
- Kalman Gain được dùng để gán trọng số thích hợp cho phép đo trong hai phép tính
- Tính giá trị ước lượng trạng thái hệ thống mới
- Tính hiệp phương sai sai số của trạng thái hệ thống
- Giá trị ước lượng trạng thái đã tính là lịch sử trạng thái duy nhất mà bộ lọc Kalman duy trì
- Nhờ đặc tính này, bộ lọc Kalman có thể được triển khai ngay cả trên các thiết bị có ràng buộc bộ nhớ thấp
Tổng kết
- Bộ lọc Kalman là một quy trình tổng quát cho ước lượng trạng thái tối ưu
- Nó được dùng trong nhiều ứng dụng cần ước lượng chính xác
- Khi chia thành các bước nhỏ, cách hoạt động của bộ lọc Kalman trở nên bớt khó tiếp cận và dễ hiểu hơn
1 bình luận
Ý kiến trên Hacker News
Khi nói về bộ lọc Kalman, không thể thiếu liên kết tới tài liệu học tập tuyệt vời này. Đây là một cuốn sách viết dưới dạng tập hợp các notebook Jupyter: https://github.com/rlabbe/Kalman-and-Bayesian-Filters-in-Pyt...
Cuốn sách xem bộ lọc alpha-beta như một người em của bộ lọc Kalman đầy đủ. Gần đây trong công việc tôi cần một thứ tương tự nên đã đọc khá nhiều, rồi nhận ra rằng bộ lọc alpha-beta và họ Kalman tập trung mạnh vào dự đoán tương lai gần, trong khi thứ tôi thật sự cần lại là làm trơn dữ liệu quá khứ
Vì vậy tôi bắt đầu đọc về làm trơn hàm mũ kép, thấy nó có vẻ rất khớp với trường hợp sử dụng, và càng đào sâu thì càng nhận ra rốt cuộc nó chính là bộ lọc alpha-beta, chỉ khác tên biến
Tôi có cảm giác toàn bộ lĩnh vực toán học này nằm trên một vài lý thuyết nền tảng chung, nhưng các ngành khác nhau tiếp cận theo những cách khác nhau để đi tới cùng một hệ thống, khiến tên gọi và ký hiệu khác nhau che mờ điểm chung. Có lẽ ở trung tâm của những thứ như chuỗi lũy thừa, hằng số tự nhiên, gradient descent, bộ lọc, hệ thống phản hồi, lý thuyết hệ thống tổng quát có một lõi trực giác tương đối nhỏ; nếu nắm được nó thì rất nhiều mảng toán học sẽ kết nối với nhau một cách đẹp mắt
Không phải để tiết kiệm giấy hay để viết cho dễ. Gõ các chữ Hy Lạp có chỉ số trên/dưới trong LaTeX bằng bàn phím tiếng Anh không hề dễ hơn viết từ. Mục đích là truyền đạt cho người đọc một loại thông tin cụ thể mà khó truyền đạt bằng cách khác
Ký hiệu toán học trông giống chữ cái, nhưng về bản chất lại khá mang tính hình ảnh, nên những từ dài sẽ che mất bức hình đó
Nếu học nghiêm túc các môn điều khiển và tín hiệu/hệ thống, trực giác đó sẽ ngấm vào người, và bạn sẽ học toán cùng thuật ngữ mà không bị bám chặt vào một quy ước ký hiệu cụ thể. Trực giác thật sự là “mọi thứ đều là bộ lọc”, phần còn lại là phân tích và tổng hợp ý tưởng đó
Khi AI/ML lớn mạnh, các ý tưởng của lý thuyết điều khiển cổ điển cũng đang được kết hợp với học tăng cường
Vì thường thì Q và R được chỉnh tay “đến khi trông ổn” rồi không đổi nữa. Hơn nữa, thay vì chỉnh nhiều giá trị Q và R, chỉ cần chỉnh tay một hệ số khuếch đại
Nếu nhiễu của phép đo luôn như nhau thì theo thời gian nó sẽ hội tụ thành hằng số; nó đặc biệt hữu ích khi bạn có thể biết khá rõ độ chính xác đo lường nhưng độ chính xác đó lại thay đổi nhiều
Gần đây tôi được giao triển khai bộ lọc Kalman, và thật sự rất khó tìm được tài liệu tốt giải thích bằng ngôn ngữ mà một lập trình viên như tôi có thể hiểu. Sau khoảng một tháng học, tôi đã viết hai bài, có thể sẽ hữu ích với ai đó: https://www.splinter.com.au/2023/12/14/the-kalman-filter-for..., https://www.splinter.com.au/2023/12/15/the-kalman-filter-wit...
Từ góc nhìn lập trình viên, trớ trêu là chỉ sau khi tự triển khai tôi mới hiểu được phần toán. Có vẻ đây là kiểu học bằng cách xây lên trên những gì mình đã biết, và tôi tự hỏi liệu có thuật ngữ nào cho cách học này không
Tôi vẫn luôn nghĩ rằng toán học sẽ dễ học hơn nhiều nếu dùng tên biến mang tính mô tả. Ít nhất với một phương tiện tương tác như web thì cũng có thể thêm tooltip. Khi học toán, tôi dành 90% thời gian để tra cứu ký hiệu
Ngoài ra, ở đây khi nói chỉ số dưới “biểu thị thứ tự của phép đo”, tôi thấy hơi bối rối không biết đó là thứ tự nào. Có lẽ ý là chỉ mục. Dù cũng lâu rồi tôi chưa đụng đến bộ lọc Kalman
Toán học càng thuần túy thì phạm vi của hầu hết biến càng ngắn. Thông thường biến được định nghĩa ngay trước khi dùng, và phạm vi cũng không vượt ra ngoài chứng minh hoặc suy dẫn đó
Tuy nhiên, trong các lựa chọn của bài này cũng có những chỗ đơn giản là kỳ lạ. Ví dụ như dùng P đồng thời làm biến và chỉ mục, rồi dùng P cho ma trận hiệp phương sai dù ma trận độ chính xác chính là nghịch đảo đúng của ma trận hiệp phương sai
Phần khó chịu nhất trong các bài nghiên cứu chính là sự mơ hồ kiểu này. Bắt buộc phải làm rõ. Phải dùng mô tả tuyệt đối, không phải cách diễn đạt tương đối. Đừng nói “nhìn sang bên phải”. Tôi có thể đang nhìn sang bên trái
Nếu viết “sau khi xoay lăng kính, nón ánh sáng...” thì thiếu mất hướng xoay là hướng nào. Sang trái hay sang phải, theo phương ngang hay lên xuống, nhanh hay chậm. Trong đầu người viết, tất cả những yếu tố cốt lõi này đều đã hiện rõ, nhưng độc giả không thể đọc được suy nghĩ của họ
Chỉ số dưới “p” có lẽ là prediction, tức dự đoán. x_p ở thời điểm 3 là trạng thái được kỳ vọng tại thời điểm 4. Nhưng khi thời điểm 4 thực sự đến, ta sẽ phản ánh phép đo mới và tính x_4
Nói cho rõ, x_4 này khác với x_p đã tính ở thời điểm 3. Vì dự đoán luôn sai lệch một chút
Vấn đề là người mới bắt đầu vẫn chưa học được các khái niệm hoặc ký hiệu chuẩn của từng miền bài toán, nên nỗi đau khi nhập môn một chủ đề mới vẫn còn đó
Bộ lọc Kalman có thể là một trong những trường hợp đặc biệt trong toán học mà phiên bản đơn giản hóa bị đơn giản hóa quá mức đến nỗi gần như không còn thấy hình dạng ban đầu
Điều nó thực sự làm là lấy một phép đo, mô phỏng các trạng thái tương lai khả dĩ, rồi kết hợp thông tin này với phép đo tiếp theo và lặp lại
Ví dụ như chụp nhiều bức ảnh một quả bóng tennis, ước lượng vị trí và vận tốc từ bức đầu tiên, mô phỏng xem nó sẽ đi đâu, rồi so với bức ảnh kế tiếp để xem ước lượng nào gần sự thật hơn. Một cách cũ hơn có thể nghĩ đến là đo độ cao của mặt trời để tạo ra một đường các vị trí khả dĩ trên bản đồ, rồi so sánh với điểm mà ban đầu bạn nghĩ mình đang ở
Tất nhiên phép tính chính xác trên thực tế gần như bất khả thi. Vì vậy người ta đơn giản hóa bằng lấy mẫu. Nhưng vì vẫn khó, nên giả định phân phối phần nào gần với phân phối Gauss. Đơn giản hóa thêm nữa bằng cách giả định sự thay đổi của hệ thống là một biến đổi tuyến tính, ta có bộ lọc Kalman được bàn ở đây
Sẽ rất đáng ngạc nhiên nếu chỉ nhìn đại số tuyến tính mà có thể hiểu được chuyện gì thực sự đang xảy ra
Chính phần giải thích này lần đầu tiên cho tôi trực giác về chuyện gì thực sự đang diễn ra. Với tôi là người làm phía máy tính, ngay cả cái tên cũng khá dễ gây hiểu lầm. Vì nó không phải là bộ lọc theo nghĩa trong xử lý stream hay SQL
Bộ lọc Kalman cố ước lượng đầu vào ẩn đã tạo ra các phép đo. Để làm điều đó, nó lập bài toán
tối thiểu hóa [phép_đo_thực_tế - phép_đo_kỳ_vọng(x)]^2/s^2 theo x. Ở đâyslà sigma của nhiễuĐiều này xuất phát từ bài toán ước lượng trạng thái
tối đa hóa khả năng quan sát thấy phép_đo_thực_tế theo x. Vì trong hàm likelihood, hạng quan trọng chỉ là-([x-expected(x)]/s)^2. Cứ nhìn phần số mũ của phân phối chuẩn, hoặc thực ra là của bất kỳ phân phối mũ nàoVì
phép_đo_thực_tếlà hằng số, nếu hàmphép_đo_kỳ_vọnglà tuyến tính thì có thể giải ngay bằng tối ưu lồi. Lấy đạo hàm, đặt bằng 0 rồi giải sẽ ra bước cập nhật của bộ lọc KalmanNếu hàm là phi tuyến, thực chất ta tuyến tính hóa phương trình, tối thiểu hóa, rồi thực hiện một bước Newton-Raphson trả về nghiệm của “tuyến tính hóa giả” đó. Đây chỉ là giải tích và đại số tuyến tính trình độ đại học, chỉ là chẳng ai nói với bạn theo cách đó
Nhưng điều này cũng hoàn toàn sai. Đây là một kiểu hack từ thập niên 1960 nhằm cực đại hóa hàm likelihood bằng tuyến tính hóa đệ quy một bước như vậy. Do đọc sai cận dưới Cramér-Rao, nhiều thế hệ kỹ sư đã tin rằng nó là tối ưu, nhưng thực tế không phải vậy
Ngày nay tài nguyên tính toán đã nhiều hơn ít nhất 10.000 lần, và hiệu năng sẽ tốt hơn nếu thiết lập rồi giải các phương trình phi tuyến bằng nhiều bước Newton-Raphson, hoặc duy trì lịch sử đo dài và giải toàn bộ bó đó bằng nhiều bước Newton-Raphson, hoặc dùng biểu diễn hỗn hợp Gauss để chấp nhận các hàm đo đa đỉnh
Những điều này đã được nghiên cứu ước lượng trạng thái từ thập niên 1980 đến nay xử lý khá tốt, nhưng giáo trình thì vẫn như được khắc lên đá vào năm 1972
Cận dưới Cramér-Rao chỉ được định nghĩa khi mọi hàm likelihood của phép đo được tuyến tính hóa tại trạng thái thật, điều này chỉ có thể xảy ra tiệm cận trong một bó bảo toàn tất cả các phép đo, không thể xảy ra trước vô hạn thời gian và cũng không thể với bộ lọc đệ quy
Trong các bài giải thích trước đây, mình thấy bài này hay: https://www.bzarg.com/p/how-a-kalman-filter-works-in-picture..., https://news.ycombinator.com/item?id=13449229
Nếu thật sự cần bộ lọc Kalman, có lẽ bạn có thể đọc và hiểu bài này, trang Wikipedia, hoặc mã nguồn triển khai (https://github.com/LdDl/kalman-rs/blob/master/src/kalman/kal...)
Nhưng theo kinh nghiệm của tôi, gần như mọi người trên thế giới đều là người học bằng thị giác, học tốt nhất qua ví dụ. Vì vậy tôi ngạc nhiên khi phần tutorial ở giữa trang lại không đưa các con số ví dụ vào công thức. Có thể tôi đã bỏ sót, nhưng hình minh họa cũng chỉ bắt đầu sau cả một trang văn bản “bộ lọc Kalman là gì”, và ngay cả các hình đó cũng chỉ là thêm nhiều công thức
Chuyện này phổ biến đến mức đáng kinh ngạc. Ở dạng nhẹ hơn, vấn đề tương tự cũng xuất hiện trong các thư viện phần mềm không kèm ví dụ code
Điều khiến tôi thấy thấm là: khi kết hợp hai phân bố đo lường không chắc chắn, tức các phân bố có phương sai lớn, ta sẽ có một phép đo chắc chắn hơn, tức một phân bố hẹp hơn
Nếu lại kết hợp giá trị đo chắc chắn hơn này với giá trị đo tiếp theo, rồi lặp lại, thì đó chính là bộ lọc Kalman
Trong số các loạt video giải thích KF, cái này thật sự rất hay. Tôi hiểu nó còn tốt hơn tài liệu trong bài gốc: https://www.youtube.com/watch?v=CaCcOwJPytQ
Người cha quá cố của tôi đã dùng bộ lọc này thường xuyên trong suốt sự nghiệp, từ thời nó vừa mới được phát minh. Ông làm về radar và hệ thống dẫn đường tên lửa
Hãy nhắm mắt lại và thử đi loanh quanh một lúc. Sau khi tưởng tượng mình đang ở đâu rồi mở mắt ra, vị trí thực tế có khác với vị trí bạn nghĩ không?
Bước cuối cùng đó — dùng quan sát để cập nhật niềm tin về các biến trạng thái — chính là việc bộ lọc Kalman làm