מסנן קלמן

מסנן קלמן הוא אלגוריתם המבוסס על מסנן בייסיאני, המקבל כקלט סדרה של מדידות מורעשות של ערכים שונים המייצגים מצב של מערכת בזמן מסוים, ומספק הערכה סטטיסטית של מצב המערכת על סמך תוצאת המסנן בעבר.^[1] המסנן נקרא על שם רודולף קלמן, אחד ממפתחיו הבולטים.

למסנן יישומים רבים בטכנולוגיה. אחד היישומים העיקריים הוא בהנחיה, ניווט ובקרה של כלי רכב, במיוחד מטוסים, טילים או רכבי חלל. הוא מיושם רבות בעיבוד אותות ואקונומטריקה.

האלגוריתם מכיל מערכת משוואות והוא עובד בשני שלבים מרכזיים: ראשית, האלגוריתם מספק הערכה של מצב המערכת (כלומר, ערכי המדדים שלה) ושל ערכי אי הוודאות שלהם. בשלב השני, נקלטות התוצאות של המדידות הבאות (בדרך כלל כולל שגיאות מדידה מסוימות). תוצאות אלו מקבלות כל אחת משקל משלה והוא מעדכן באמצעותן את מצב המערכת. משקל כל תוצאה תלוי ברמת האמינות אותה מייחס האלגוריתם לאותה מדידה. המשקלים יכולים להשתנות במשך פעולת המסנן בהתאם לתוצאות המתקבלות בכל מדידה. כך למשל, במידה שמתקבל הפרש גבוה בין ההערכה לבין המדידה, המסנן עשוי להפחית את המשקל שהוא נותן להערכות הקודמות שלו ולהגביר את המשקל הניתן לתוצאה, ולהפך.

האלגוריתם משתמש רק במדידות החדשות ובמצב המערכת כפי שהתקבל מההערכה שלו, ללא התייחסות לערכים קודמים. לפיכך, קל ליישם את האלגוריתם במערכות זמן אמת.

על מנת לקבל תוצאות מיטביות, האלגוריתם נדרש לקבל הערכות נכונות בקשר לדיוק המשתנים המתקבלים. במידה ואין הערכה כזו, תוצאות המסנן תהיינה טובות פחות, אך עדיין טובות בהרבה משימוש בשיטות רגילות, כמו ממוצע נע.

במסנן נעשה שימוש גם במצב בו מעוניינים לאחד את אותה מדידה משני חיישנים שונים ובלתי תלויים לטובת ערך מדויק יותר מכל אחת משתי המדידות.

תיאור מתמטי של מסנן קלמן

פעולת מסנן קלמן כוללת שני שלבים:

חיזוי: הפעלת מודל חיזוי כדי לקבל הערכה של מצב המערכת טרום מדידה (א-פריורי).
עדכון: עדכון ההערכה בעקבות התצפיות/מדידות שהתקבלו בפועל.

נסמן:

${\hat {\mathbf {x} }}_{k\mid k}$ – הערכת מצב המערכת במצב ה-k בהינתן המצב ב-k המצבים שלפניו
$\mathbf {P} _{k\mid k}$ – הערכת אי-ודאות מצב המערכת. השונות המשותפת במצב ה-k בהינתן המצב ב-k המצבים שלפניו
$\mathbf {F} _{k}$ (לעיתים מסומן ב-Φ) מודל החיזוי המתאר כיצד מתפתחת המערכת במעבר משלב k-1 לשלב k (לפי מודל שמניח החוקר)
$\mathbf {u} _{k}$ – קלט מבוקר שמכניסים למערכת
$\mathbf {B} _{k}$ – איבר המתאר כיצד הקלט משפיע על המערכת (לפי מודל שמניח החוקר)
$\mathbf {Q} _{k}$ – רעש תהליך. השונות המשותפת של הרעש בתהליך הקידום של מצב המערכת
$\mathbf {z} _{k}$ – המדידות והתצפיות בשלב k
$\mathbf {R} _{k}$ – רעש מדידה. השונות המשותפת של הרעש שנוצר בתהליך המדידה. שגיאות מדידה, התפלגות תצפיות וכו'.
$\mathbf {H} _{k}$ – איבר המתאר את הקשר בין המדידה למצב המערכת.
בשלב העדכון אנו נשווה בין התוצאות שחוזה המערכת לבין התוצאות שנמדדו בפועל (תצפיות) ועל-פי זה נתקן את ההערכה.

חיזוי

הערכת מצב המערכת (א-פריורי)	${\hat {\mathbf {x} }}_{k\mid k-1}=\mathbf {F} _{k}{\hat {\mathbf {x} }}_{k-1\mid k-1}+\mathbf {B} _{k}\mathbf {u} _{k}$
הערכת אי ודאות השגיאה. שונות משותפת (א-פריורית)	$\mathbf {P} _{k\mid k-1}=\mathbf {F} _{k}\mathbf {P} _{k-1\mid k-1}\mathbf {F} _{k}^{\mathrm {T} }+\mathbf {Q} _{k}$

עדכון

חישוב ההפרש בין התצפיות לתחזית	${\tilde {\mathbf {y} }}_{k}=\mathbf {z} _{k}-\mathbf {H} _{k}{\hat {\mathbf {x} }}_{k\mid k-1}$
חישוב אי הוודאות (השונות המשותפת)	$\mathbf {S} _{k}=\mathbf {R} _{k}+\mathbf {H} _{k}\mathbf {P} _{k\mid k-1}\mathbf {H} _{k}^{\mathrm {T} }$
חישוב הגבר קלמן מיטבי (optimal Kalman gain)	$\mathbf {K} _{k}=\mathbf {P} _{k\mid k-1}\mathbf {H} _{k}^{\mathrm {T} }\mathbf {S} _{k}^{-1}$
עדכון מצב המערכת (פוסטריורי)	${\hat {\mathbf {x} }}_{k\mid k}={\hat {\mathbf {x} }}_{k\mid k-1}+\mathbf {K} _{k}{\tilde {\mathbf {y} }}_{k}$
עדכון הערכת אי הוודאות (שונות משותפת) (פוסטריורי)	$\mathbf {P} _{k\|k}=(\mathbf {I} -\mathbf {K} _{k}\mathbf {H} _{k})\mathbf {P} _{k\|k-1}(\mathbf {I} -\mathbf {K} _{k}\mathbf {H} _{k})^{T}+\mathbf {K} _{k}\mathbf {R} _{k}\mathbf {K} _{k}^{T}=(\mathbf {I} -\mathbf {K} _{k}\mathbf {H} _{k})\mathbf {P} _{k\|k-1}$
ההתאמה בין המדידות להערכה המעודכנת	${\tilde {\mathbf {y} }}_{k\mid k}=\mathbf {z} _{k}-\mathbf {H} _{k}{\hat {\mathbf {x} }}_{k\mid k}$

התאמות למסנן קלמן

האלגוריתם המקורי של מסנן קלמן מתאים להנחות יסוד מסוימות, למשל מודל החיזוי צריך להיות ליניארי, הרעש מוגדר גאוסיאני ועוד התניות כפי שמפורט לעיל. לצורך פתרון של מערכות פיזיקליות שאינן עונות על הנחות היסוד פותחו "מסנני קלמן" מתקדמים.

Extended Kalman Filter (EKF) - מסנן קלמן מקורב ליניארית

מסנן זה טוב למקרים בהם מודל החיזוי f(x) אינו מהצורה הליניארית Fx, אך קירוב שלו מסדר ראשון הוא "מספיק טוב". לביצוע קירוב מסדר ראשון גוזרים את מודל החיזוי f ומקבלים מודל חיזוי לינארי מהצורה הרצויה Fx (כאשר F משתנה בכל צעד זמן לפי הנגזרת של f)^[2].

Optimized Kalman Filter (OKF) - מסנן קלמן מיועל

השימוש במסנן קלמן מחייב קביעה של המטריצות $\mathbf {Q} _{k}$ ו- $\mathbf {R} _{k}$ . מקובל להתייחס למטריצות אלה כמייצגות של השונות המשותפת של רעש התהליך ורעש המדידה, בהתאמה. לפיכך, מקובל לשערכן בכלים סטטיסטיים לשערוך שונות משותפת. עם זאת, כאשר המערכת אינה מקיימת את הנחות המודל של מסנן קלמן, משמעות הרעש כבר אינה מוגדרת היטב. במקרה זה, OKF נמנע מלהגביל את $\mathbf {Q} _{k}$ ו- $\mathbf {R} _{k}$ כמייצגים של הרעש, ובמקום זאת מתייחס אליהם כאל פרמטרים כלליים של המסנן. בגישה זו, ניתן להשתמש בכלים מקובלים באופטימיזציה כדי לייעל פרמטרים אלה ישירות לטובת המטרה הסופית - שערוך מיטבי של מצב המערכת. היתרון המרכזי בגישה זו הוא השימוש בלמידה מנתונים לצורך "פיצוי" על פערים בהנחות המודל. תכונה זו מאפשרת התמודדות עם הפרות שונות של הנחות המודל (כגון לינאריות, רעש לבן, ואתחול נורמלי) גם כאשר אינן ידועות למשתמש.^[3]

שימושים

ניתן להשתמש באלגוריתם למערכות הגנה אווירית כגון כיפת ברזל כאשר מתגלה איום על ידי מכ"ם, המיקום והמהירות ההתחלתיים של הרקטה או הפגז הנכנסים נמדדים. מדידות אלו רועשות מטבען בשל אופי זיהוי המכ"ם והסביבה. מסנן קלמן משמש להערכת המצב (מיקום, מהירות ואולי תאוצה) של הקליע בהתבסס על מדידות ראשוניות אלו. לאחר מכן ניתן לחזות את המהירות העתידיים של הקליע בשלבי הזמן הבאים.

שימוש נוסף הוא במערכות מיפוי רובוטי.

קישורים חיצוניים

מדיה וקבצים בנושא מסנן קלמן בוויקישיתוף

פילטר קלמן, דף שער בספרייה הלאומית
מסנן קלמן, באתר MathWorld (באנגלית)

A New Approach to Linear Filtering and Prediction Problems, by R. E. Kalman, 1960
Kalman and Bayesian Filters in Python. Open source Kalman filtering textbook.
How a Kalman filter works, in pictures. Illuminates the Kalman filter with pictures and colors

^ Rudolf E. Kálmán, A New Approach to Linear Filtering and Prediction Problems
^ Brian D. O. Anderson, John B. Moore, Optimal Filtering, Courier Corporation, 2005-01-05, ISBN 978-0-486-43938-9. (באנגלית)
^ Ido Greenberg, Netanel Yannay, Shie Mannor, Optimization or Architecture: How to Hack Kalman Filtering, Advances in Neural Information Processing Systems 36, 2023-12-15, עמ' 50482–50505

[1] Rudolf E. Kálmán, A New Approach to Linear Filtering and Prediction Problems

[2] Brian D. O. Anderson, John B. Moore, Optimal Filtering, Courier Corporation, 2005-01-05, ISBN 978-0-486-43938-9. (באנגלית)

[3] Ido Greenberg, Netanel Yannay, Shie Mannor, Optimization or Architecture: How to Hack Kalman Filtering, Advances in Neural Information Processing Systems 36, 2023-12-15, עמ' 50482–50505

[1]

[2]

[3]