Hướng dẫn về bộ lọc Kalman
(kalmanfilter.net)- Bộ lọc Kalman là một thuật toán sử dụng đồng thời các phép đo cảm biến có nhiễu và một mô hình động lực học không hoàn hảo để ước lượng cả trạng thái hiện tại lẫn độ bất định của trạng thái kế tiếp
- Bài hướng dẫn dùng ví dụ theo dõi radar máy bay, đặt khoảng cách (r) và vận tốc (v) làm vector trạng thái, rồi lần lượt đi theo quá trình kết hợp giá trị dự đoán và giá trị đo bằng số liệu cụ thể
- Khi dùng giá trị đo ban đầu (10,000m), (200m/s) và khoảng thời gian lấy mẫu (5s), mô hình vận tốc không đổi dự đoán vị trí tiếp theo là (11,000m), đồng thời nhiễu đo (R) và nhiễu quá trình (Q) được phản ánh vào hiệp phương sai
- Giá trị đo thứ hai (11,020m), (202m/s) có độ bất định lớn hơn, nhưng độ lợi Kalman (K) sẽ kết hợp có trọng số giữa dự đoán và phép đo để tính trạng thái cập nhật thành (11,009.37m), (201.43m/s)
- Sau khởi tạo, vòng lặp dự đoán-cập nhật được lặp đi lặp lại, và trong triển khai thực tế còn cần cân nhắc công thức cập nhật hiệp phương sai ổn định như Joseph form cũng như cách xử lý các phép đo bất thường
Bài toán ước lượng mà bộ lọc Kalman giải quyết
- Bộ lọc Kalman là một thuật toán dùng để ước lượng và dự đoán trạng thái của hệ thống trong môi trường có bất định
- Dữ liệu cảm biến có nhiễu đo
- Các yếu tố bên ngoài chưa biết
- Sai khác giữa mô hình động lực học và chuyển động thực tế
- Nó được dùng trong theo dõi đối tượng, dẫn đường, robot học, điều khiển, phân tích thị trường tài chính, dự báo thời tiết, v.v.
- Nếu áp dụng vào ước lượng quỹ đạo chuột máy tính, nó có thể giảm nhiễu và bù rung tay để tạo ra đường di chuyển ổn định hơn
- Bài hướng dẫn được xây dựng để giúp hiểu bộ lọc Kalman bằng ví dụ số và diễn giải trực quan hơn là giải thích toán học phức tạp
- Nội dung cũng gồm cả ví dụ bộ lọc Kalman không theo dõi được vật thể trong tình huống thiết kế sai, cùng cách hiệu chỉnh nó
Lộ trình học
- Dự án này được cấu trúc để có thể học bộ lọc Kalman ở ba mức độ sâu khác nhau
- Tổng quan một trang: giải thích ý tưởng cốt lõi và các phương trình thiết yếu mà không suy diễn chi tiết, giả định người đọc có kiến thức cơ bản về thống kê và đại số tuyến tính
- Web tutorial miễn phí dựa trên ví dụ: xây dựng trực giác bằng ví dụ số và từng bước đi đến phần suy dẫn phương trình bộ lọc Kalman, đồng thời cho biết không cần kiến thức nền trước
- Kalman Filter from the Ground Up: gồm 14 ví dụ số được giải đầy đủ, đồ thị và bảng hiệu năng, Extended Kalman Filter, Unscented Kalman Filter, hợp nhất cảm biến và hướng dẫn triển khai
Nhu cầu dự đoán qua ví dụ theo dõi radar
- Trong radar theo dõi máy bay, máy bay là hệ thống, còn vị trí cần ước lượng là trạng thái hệ thống
- Radar hướng một chùm sóng hẹp về phía máy bay, nên để quyết định gửi chùm sóng tiếp theo đi đâu thì cần phải dự đoán vị trí tương lai
- Nếu dự đoán thất bại, chùm sóng có thể hướng sai và mất bám mục tiêu
- Cần có mô hình động lực học biểu diễn chuyển động của hệ thống theo thời gian
- Trong ví dụ một chiều đã được đơn giản hóa, giả định máy bay chuyển động trên một đường thẳng tiến lại gần hoặc rời xa radar
- Radar tính khoảng cách (r) từ thời gian truyền/nhận xung
- Vận tốc (v) cũng có thể được đo bằng hiệu ứng Doppler
- Nếu tại (t_0), khoảng cách (10,000m) và vận tốc (200m/s) được đo rất chính xác, với khoảng thời gian lấy mẫu (\Delta t=5s), và giả định vận tốc không đổi, thì vị trí tiếp theo là (11,000m)
- (\Delta r = v \cdot \Delta t)
- (r_{t_1}=10,000+200\cdot5=11,000m)
Nhiễu đo và nhiễu quá trình
- Các phép đo radar thực tế không hoàn toàn chính xác, nên ngay cả khi nhiều radar đo cùng một thời điểm thì chúng vẫn có thể cho ra giá trị hơi khác nhau
- Sự dao động này được biểu diễn bằng nhiễu đo
- Không chỉ cần tính giá trị ước lượng trạng thái mà còn phải tính xem ước lượng đó đáng tin đến mức nào
- Mô hình động lực học cũng không hoàn hảo
- Dù giả định máy bay chuyển động với vận tốc không đổi, chuyển động thực tế vẫn có thể khác đi vì các yếu tố bên ngoài như gió
- Những ảnh hưởng không dự đoán được này là nhiễu quá trình
- Bộ lọc Kalman đồng thời cung cấp ước lượng trạng thái hiện tại, dự đoán trạng thái tương lai và độ bất định của từng phần
- Đây là thuật toán tối ưu giúp giảm thiểu độ bất định của ước lượng trạng thái, với điều kiện hệ thống và nhiễu tuân theo các giả định của mô hình
Vector trạng thái và khởi tạo
- Trạng thái hệ thống trong ví dụ gồm khoảng cách (r) và vận tốc (v) của máy bay
[ \boldsymbol{x}= \begin{bmatrix} r\ v \end{bmatrix} ]
- Giá trị đo đầu tiên tại (t_0) như sau
[ \boldsymbol{z}_0= \begin{bmatrix} 10{,}000\ 200 \end{bmatrix} ]
- Vì phép đo có bất định, mỗi phép đo đều đi kèm độ bất định đo dưới dạng phương sai
- Độ lệch chuẩn đo khoảng cách: (4m)
- Độ lệch chuẩn đo vận tốc: (0.5m/s)
- Phương sai là bình phương của độ lệch chuẩn
[ \boldsymbol{R}_0= \begin{bmatrix} 16 & 0\ 0 & 0.25 \end{bmatrix} ]
- Trong ví dụ này giả định sai số đo khoảng cách và vận tốc không liên quan với nhau, nên các phần tử ngoài đường chéo của ma trận hiệp phương sai được đặt bằng 0
- Ở bước khởi tạo, vì giá trị đo và trạng thái hệ thống biểu diễn cùng các đại lượng vật lý (r), (v), nên có thể dùng phép đo đầu tiên làm giá trị ước lượng trạng thái ban đầu
[ \hat{\boldsymbol{x}}_{0,0}= \boldsymbol{z}_0= \begin{bmatrix} 10{,}000\ 200 \end{bmatrix} ]
- Cách này chỉ có thể dùng ở bước khởi tạo
Bước dự đoán: lan truyền trạng thái và hiệp phương sai
- Dự đoán dùng trạng thái hiện tại và ma trận chuyển trạng thái (\boldsymbol{F}) để tính trạng thái ở thời điểm tiếp theo
- Với mô hình vận tốc không đổi, dùng các công thức sau
[ v_1=v_0=v ]
[ r_1=r_0+v_0\Delta t ]
- Phương trình dự đoán trạng thái ở dạng ma trận như sau
[ \hat{\boldsymbol{x}}_{n+1,n}
\boldsymbol{F} \hat{\boldsymbol{x}}_{n,n} + \boldsymbol{G}\boldsymbol{u}_n ]
- (\boldsymbol{u}_n): biến đầu vào
- (\boldsymbol{G}): ma trận chuyển đầu vào
- Trong ví dụ đơn giản này không có đầu vào nên (\boldsymbol{u}_n=0)
- Khi (\Delta t=5s), ma trận chuyển trạng thái là như sau, và kết quả dự đoán là (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} ]
- Dự đoán hiệp phương sai không chỉ là (\boldsymbol{F}\boldsymbol{P}) mà dùng (\boldsymbol{F}\boldsymbol{P}\boldsymbol{F}^T)
[ \boldsymbol{P}_{n+1,n}
\boldsymbol{F} \boldsymbol{P}_{n,n} \boldsymbol{F}^T + \boldsymbol{Q} ]
- Nếu bỏ qua nhiễu quá trình, hiệp phương sai dự đoán là như sau
[ \boldsymbol{P}_{1,0}
\begin{bmatrix} 22.25 & 1.25\ 1.25 & 0.25 \end{bmatrix} ]
- Phương sai vận tốc vẫn giữ ở (0.25) do mô hình vận tốc không đổi
- Phương sai khoảng cách tăng từ (16) lên (22.25) vì bất định của vận tốc làm tăng bất định của khoảng cách theo thời gian
Phản ánh nhiễu quá trình
- Vì vận tốc thực của máy bay có thể chịu ảnh hưởng của các yếu tố bên ngoài không dự đoán được như gió, nên nhiễu quá trình (\boldsymbol{Q}) được cộng vào bước dự đoán hiệp phương sai
- Trong ví dụ, giả định độ lệch chuẩn của gia tốc ngẫu nhiên là (\sigma_a=0.2m/s^2)
- Phương sai là (\sigma_a^2=0.04m^2/s^4)
- Khi (\Delta t=5s), ma trận nhiễu quá trình là
[ \boldsymbol{Q}
\begin{bmatrix} 6.25 & 2.5\ 2.5 & 1 \end{bmatrix} ]
- Hiệp phương sai dự đoán sau khi cộng nhiễu quá trình là
[ \boldsymbol{P}_{1,0}
\begin{bmatrix} 28.5 & 3.75\ 3.75 & 1.25 \end{bmatrix} ]
Bước cập nhật: kết hợp có trọng số giữa dự đoán và phép đo
- Tại (t_1), giá trị đo thứ hai là
[ \boldsymbol{z}_1= \begin{bmatrix} 11{,}020\ 202 \end{bmatrix} ]
- Giả định phép đo này có độ bất định lớn hơn phép đo đầu tiên do một spike nhiễu mạnh làm tỷ lệ tín hiệu trên nhiễu thấp
- Độ lệch chuẩn khoảng cách: (6m)
- Độ lệch chuẩn vận tốc: (1.5m/s)
[ \boldsymbol{R}_1= \begin{bmatrix} 36 & 0\ 0 & 2.25 \end{bmatrix} ]
- Vì các phần tử đường chéo của hiệp phương sai dự đoán (\boldsymbol{P}_{1,0}) nhỏ hơn hiệp phương sai đo (\boldsymbol{R}_1), nên phía dự đoán có độ bất định thấp hơn
- Bộ lọc Kalman không chỉ dùng dự đoán hoặc chỉ dùng phép đo, mà kết hợp chúng bằng cách đặt trọng số lớn hơn cho phía có độ bất định thấp hơn
- Dạng trung bình có trọng số trong một chiều là như sau
[ \hat{x}_{1,1}
K_1 z_1 + (1-K_1)\hat{x}_{1,0} ]
- (\boldsymbol{K}) là độ lợi Kalman, xác định trọng số của phép đo và dự đoán sao cho độ bất định của ước lượng cập nhật là nhỏ nhất
Innovation, ma trận quan sát và độ lợi Kalman
- Phương trình cập nhật trạng thái có thể viết dưới dạng cộng thêm một hạng hiệu chỉnh vào giá trị dự đoán
[ \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}) là innovation hoặc residual, biểu diễn thông tin do phép đo mới cung cấp
- (\boldsymbol{H}) là ma trận quan sát hoặc ma trận đo, ánh xạ biến trạng thái sang các đại lượng vật lý thực sự được đo
- Trong ví dụ này, trạng thái và phép đo đều là khoảng cách và vận tốc nên (\boldsymbol{H}=\boldsymbol{I})
- Nói chung, giá trị đo và trạng thái có thể thuộc các miền vật lý khác nhau như trong trường hợp nhiệt kế kỹ thuật số
- Độ lợi Kalman đa biến là như sau
[ \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} ]
- Độ lợi Kalman được tính trong ví dụ là
[ \boldsymbol{K}_1= \begin{bmatrix} 0.4048 & 0.6377\ 0.0399 & 0.3144 \end{bmatrix} ]
- Việc tính ma trận nghịch đảo có thể thực hiện bằng
inv(A)trong MATLAB hoặcnumpy.linalg.inv(A)trong Python, nhưng trong triển khai thực tế thường tốt hơn nếu giải trực tiếp hệ tuyến tính nhưA\bhoặcnumpy.linalg.solve(A, b)thay vì dùng nghịch đảo tường minh
Kết quả cập nhật và sự giảm hiệp phương sai
- Innovation trong ví dụ này là
[ \boldsymbol{z}1-\hat{\boldsymbol{x}}{1,0}
\begin{bmatrix} 20\ 2 \end{bmatrix} ]
- Khi tính hạng hiệu chỉnh bằng độ lợi Kalman, ta được
[ \boldsymbol{K}_1 \begin{bmatrix} 20\ 2 \end{bmatrix}
\begin{bmatrix} 9.37\ 1.43 \end{bmatrix} ]
- Giá trị ước lượng trạng thái đã cập nhật là
[ \hat{\boldsymbol{x}}_{1,1}
\begin{bmatrix} 11{,}009.37\ 201.43 \end{bmatrix} ]
- Trong cập nhật hiệp phương sai đa biến, Joseph form ổn định về mặt số thường được dùng
[ \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 ]
- Công thức cập nhật hiệp phương sai đơn giản hóa cũng thường xuất hiện trong tài liệu
[ \boldsymbol{P}_{n,n}
(\boldsymbol{I}-\boldsymbol{K}n\boldsymbol{H}) \boldsymbol{P}{n,n-1} ]
- Trong số học chính xác, hai dạng này cho cùng một kết quả, nhưng trong triển khai trên máy tính thì Joseph form thường ổn định số tốt hơn
- Hiệp phương sai cập nhật được tính bằng công thức đơn giản hóa trong ví dụ là
[ \boldsymbol{P}_{1,1}
\begin{bmatrix} 14.57 & 1.43\ 1.43 & 0.71 \end{bmatrix} ]
- Các phần tử đường chéo của hiệp phương sai cập nhật thấp hơn hiệp phương sai dự đoán ((28.5, 1.25)) và hiệp phương sai đo ((36, 2.25))
- Thông tin mới dù có độ bất định cao vẫn làm giảm độ bất định của ước lượng, và về mặt lý thuyết thì không nên bỏ qua phép đo mới
- Trong triển khai thực tế, đôi khi cần loại bỏ các phép đo không đáng tin cậy; các phương pháp xử lý ngoại lệ được trình bày trong chương Outlier Treatment của cuốn sách
Dự đoán tiếp theo và vòng lặp lặp lại
- Bước dự đoán của Iteration 1 giống với Iteration 0, nhưng điểm bắt đầu đổi thành (\hat{\boldsymbol{x}}{1,1}) và (\boldsymbol{P}{1,1}) đã được cập nhật
- Kết quả dự đoán trạng thái là
[ \hat{\boldsymbol{x}}_{2,1}
\boldsymbol{F} \hat{\boldsymbol{x}}_{1,1}
\begin{bmatrix} 12{,}016.5\ 201.43 \end{bmatrix} ]
- Kết quả dự đoán hiệp phương sai là
[ \boldsymbol{P}_{2,1}
\begin{bmatrix} 52.86 & 7.47\ 7.47 & 1.71 \end{bmatrix} ]
- Khi thời gian trôi qua mà không có phép đo mới, độ bất định sẽ tự nhiên tăng lên nên phương sai lại tăng trong bước dự đoán
- Bất định của vận tốc tiếp tục làm tăng bất định của khoảng cách
- Vì vậy phương sai khoảng cách tăng nhanh hơn phương sai vận tốc
- Ví dụ này cho thấy ba bước của bộ lọc Kalman
- Khởi tạo: thực hiện một lần lúc bắt đầu
- Dự đoán: lan truyền trạng thái tiếp theo và độ bất định bằng mô hình động lực học
- Cập nhật: kết hợp phép đo mới và dự đoán bằng độ lợi Kalman
- Sau khởi tạo, bộ lọc Kalman tiếp tục hoạt động theo vòng lặp dự đoán-cập nhật
1 bình luận
Các ý kiến trên Hacker News
Tôi luôn nói rằng nếu học riêng bộ lọc Kalman thì thứ tự sẽ bị đảo ngược, nên rất dễ bỏ lỡ sự giác ngộ lớn mà các lý thuyết xung quanh mở ra
Để hiểu đúng, tốt nhất nên lần lượt xem phương pháp bình phương tối thiểu (hồi quy tuyến tính), bình phương tối thiểu đệ quy, rồi bộ lọc thông tin (một cách chính thức hóa khác của KF)
Khi đó bạn sẽ nhận ra KF chỉ là bình phương tối thiểu đệ quy được tái chính thức hóa để ưu tiên hiệu quả ở bước cập nhật
PDF này đưa ra một tổng quan ngắn gọn: http://ais.informatik.uni-freiburg.de/teaching/ws13/mapping/...
Dù vậy tôi vẫn có trí tò mò trí tuệ, nên cần một lộ trình để vừa giữ được sự tò mò vừa dần tiến tới hiểu biết
Đọc lại The Six (Not So) Easy Pieces tôi vẫn không hiểu, nhưng nó vẫn có giá trị; còn khi nghịch con mèo của Arnold, dù không có quy trình khoa học nghiêm ngặt, tôi vẫn có thể trải nghiệm bằng sự tò mò bản năng như một loài linh trưởng trần trụi những khái niệm vốn nằm sau cánh cửa mang tên bối cảnh
http://gerdbreitenbach.de/arnold_cat/cat.html
Trong một chiều, ta lấy phân phối tiên nghiệm từ dự đoán tuyến tính X'1 = X0*a + b, khi đó mean(X'1) = mean(X0)*a + b, var(X'1) = var(X0)*a^2, còn a và b biểu diễn động lực học được giả định
Hậu nghiệm Gauss là trung bình có trọng số theo độ chính xác giữa tiên nghiệm và quan sát, nên X1 = (1 - K)X'1 + YK, và K = (1/var(X'1))/(1/var(X'1) + 1/var(Y)), trong đó Y là quan sát Gauss
Lặp lại điều này thì thành bộ lọc Kalman; nếu hiểu tính tuyến tính của Gauss đa chiều thì việc tổng quát hóa sang đa chiều cũng trực quan
Tuy vậy, bản thân tính tuyến tính của Gauss đa chiều và hậu nghiệm Gauss có thể không phải nội dung dễ
Mỗi khi chủ đề này xuất hiện thì tài liệu này cũng được nhắc tới, và ngược lại cũng vậy: https://github.com/rlabbe/Kalman-and-Bayesian-Filters-in-Pyt...
Điểm dùng Jupyter notebook cũng rất tuyệt
Có vẻ vẫn chưa có công cụ tính toán ký hiệu dành cho phân phối xác suất
Ý tôi là một công cụ có thể, chẳng hạn, nhân hai hàm mật độ xác suất Gauss đa biến để thu được ma trận hiệp phương sai, hoặc khi định nghĩa mọi thành phần của bộ lọc Kalman (mô hình dự đoán và quá trình quan sát) thì trích ra các công thức cần thiết kiểu như lambdify của sympy
Tuy nhiên tôi không biết Sympy có xử lý được phân phối có điều kiện cần cho bộ lọc Kalman, tức hậu nghiệm Bayes, hay không
Dù sao nếu muốn nghịch bộ lọc Kalman bằng Sympy thì tốt hơn là trực tiếp xử lý trung bình và phương sai, hoặc ma trận hiệp phương sai
Tham khảo: https://reference.wolfram.com/language/howto/WorkWithStatist...
Và: https://reference.wolfram.com/language/ref/MultinormalDistri...
https://www.squiggle-language.com/docs
Nếu Q và R là hằng số, như thường thấy, gain sẽ nhanh chóng hội tụ và bộ lọc Kalman gần như giống một bộ lọc hàm mũ có thêm bước dự đoán
Với nhiều người, cách giải thích này dễ hiểu hơn nhiều và cũng khớp với cách dùng thực tế
Vì thường người ta chỉnh Q và R thủ công cho tới khi “trông ổn” rồi không thay đổi nữa
Hơn nữa, thay vì phải chỉnh nhiều giá trị như Q và R, chỉ cần chỉnh thủ công một gain duy nhất
Chỉ đơn giản là chỉnh cho tới khi kết quả trông hợp lý à? Nếu vậy tôi không hiểu nó hoạt động đúng ra sao ngay cả trong tình huống chưa hoàn toàn bị overfit
Ví dụ nếu theo dõi một con chim trong video thì có thể chọn một Q nào đó, nhưng thống kê nhiễu có thể thay đổi theo thời điểm trong ngày. Khi đó phải làm gì?
Bài liên quan: Kalman filter from the ground up - https://news.ycombinator.com/item?id=37879715 - tháng 10 năm 2023, 150 bình luận
Tôi cũng tò mò năm nào là phù hợp nhất để đưa vào tiêu đề trên
Bộ lọc Kalman nằm trong chủ đề tổng quát hơn là Optimization by Vector Space Methods của David G. Luenberger, John Wiley and Sons, Inc., New York, 1969
Chợt nghĩ đến điều này. Liệu các vụ việc chỉ có lời khai nhân chứng có thể được mã hóa thành vector theo cách nào đó rồi xử lý bằng bộ lọc Kalman để tăng cường giá trị chứng cứ của các quan sát không?
Tức là coi cả lời nói dối lẫn sự thiếu chính xác đều là “sai số”
Tôi đang nghĩ tới Phoenix lights hay UFO nói chung, ma, trải nghiệm cận tử, và những chuyện đời thường hơn như cáo buộc hiếp dâm
Tài liệu tốt nhất hầu như lúc nào cũng là cái này: https://github.com/rlabbe/Kalman-and-Bayesian-Filters-in-Pyt...
Ngay cả với người không dùng Python thì nó vẫn xuất sắc, và bao quát toàn bộ rất tốt
Có ai khác khi học chủ đề này đã xem bài giảng về bộ lọc Kalman của Michael van Biezem đeo nơ bướm không?
https://www.youtube.com/watch?v=CaCcOwJPytQ&list=PLX2gX-ftPV...
Một câu thật sự cần biết là đây: “Bộ lọc này được đặt theo tên Rudolf E. Kálmán (19 tháng 5 năm 1930–2 tháng 7 năm 2016). Năm 1960, Kálmán công bố bài báo nổi tiếng mô tả một lời giải đệ quy cho bài toán lọc tuyến tính dữ liệu rời rạc”