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

מאת בני גאמוס וצבר דולב

נפתח בדוגמה: נאמר שאנו רוצים להעריך, או בשפה מקצועית - לשערך, את מיקומו ואת מהירותו (ה"מצב") של טיל שאנו מטיסים (לעיתים נרצה לשערך מצב של כלי "זר" ואף עוין, אבל זה לפוסט אחר). ניתן להציע מודל מתמטי של תנועת הטיל, שיספק חיזוי של המצב לפי האפקטים הפיזיקליים שבחרנו למדל, למשל כבידה, גרר, מידות הטיל וכוחות שפעול שאנו שולטים בהם (כמו דחף במנוע). אך תמונה זו אינה מלאה: המודל הפיזיקלי של מערכת כה מורכבת אינו יכול להיות מדויק, ויש מגוון אפקטים שאין ביכולתנו להתחשב בהם - כמו משבי רוח פתאומיים. כאן באים לעזרתנו חיישנים: נאמר שעל הטיל יש GPS [1] שנותן מדידת מיקום, וחיישני תאוצה. כל אחת מהתצפיות האלו נותנת מידע חלקי על מצב המערכת (ה-GPS למשל לא נותן מדידת מהירות), ומכילה רעשי מדידה בעלי אופי שונה. אלו מספר נתונים שונים שעלינו להכריע ביניהם בזמן אמת ובמהרה (לא נרצה טיל שטס זמן רב בלי לדעת במהימנות היכן הוא נמצא). אגב, כיוון שהבעיה עלתה כבר בזמן פיתוח חללית "אפולו" בשנות ה-60, החישוב נדרש להיות מהיר ופשוט מספיק אפילו למחשבי התקופה. אך כיצד נחליט על אילו נתונים להסתמך? האם נחשב ממוצע בין כולם, או שחלקם עדיפים על אחרים? הישארו איתנו עוד קצת ונסביר.

מסנן קלמן פותח בשנות ה-60 על-ידי המהנדס ההונגרי-אמריקאי רודולף קלמן, שעבד על בעיית העקיבה אחר מיקומו של לוויין במסלול. זהו אחד מסיפורי ה"סינדרלה" במדע, שבהם תגלית גדולת ממדים אינה מתקבלת בהתחלה על-ידי הקהילה המדעית. קלמן נאלץ לפרסם את מאמרו הראשון בנושא במגזין בלתי מוכר יחסית בשם "עלון החברה המקסיקנית למתמטיקה" [2]. למזלו (ולמזלנו), מהנדסים בכירים בנאס"א דווקא הבינו את הפוטנציאל שברעיון, ומסנן קלמן יושם בליבת האלגוריתם של חללית אפולו [3]. יש המייחסים לקלמן את הציטוט הצנוע "בלעדיי לא היינו מגיעים לירח". השאר היסטוריה - מאז מסנן קלמן נמצא בשימוש נרחב במגוון תחומים.

מסנן קלמן הוא אלגוריתם המשתמש בשילוב של תצפיות (מדידות) ומודל מתמטי כדי לבצע שערוך מצב של מערכת, אשר מדויק יותר מכל אחד מהם בנפרד [4]. התהליך מורכב משני שלבים החוזרים על עצמם: שלב החיזוי ושלב העדכון. בשלב החיזוי, מסנן קלמן משתמש במודל המתמטי של המערכת כדי לבצע חיזוי של המצב הבא. בשלב העדכון, המסנן משווה את התחזית עם תצפיות שהתקבלו - בעיקר מדידות מחיישנים. כעת המסנן צריך להחליט עד כמה הוא "סומך" על התחזית לעומת התצפיות. העדכון הוא למעשה מעין ממוצע משוקלל בין החיזוי ובין התצפיות, כאשר המידה שבה הוא נסמך על זה או על זה תלויה במידע שניתן לו על הרעשים שלהם. בחזרה לדוגמת הטיל, אופי הרעשים של ה-GPS הופך אותו לאמין יותר במציאת מיקום, אבל פחות מדויק במציאת מהירויות ותאוצות; ואילו בחיישני התאוצה המצב הפוך בדיוק. בנוסף, אם ידוע שקליטת ה-GPS אינה טובה, אפשר להעלות את מדד הרעש של תצפית זו במסנן קלמן, כך שהוא יסתמך יותר על החיזוי של המודל או על חיישנים אחרים. אם הכול תוכנן היטב, נקבל שערוך מצב "חלק" יותר ומדויק יותר מאשר בכל אחד מרכיבי המערכת בפני עצמו. שילוב חכם כזה בין מספר חיישנים לקבלת תוצאה משופרת נקרא היתוך (sensor fusion). דוגמה נוספת מתחום הרכבים האוטונומיים אפשר למצוא פה [5].

שאלה מתבקשת היא כיצד מחליט מסנן קלמן על המשקלים בין המצבים השונים, והאם הוא בוחר את השקלול הטוב ביותר? ובכן, מסנן קלמן משקלל את החיזוי והתצפיות ונותן את השגיאה הקטנה ביותר בין המצב המשוערך לאמיתי (לכן הוא נקרא המשערך האופטימלי למערכות ליניאריות). היות שרוב הבעיות ההנדסיות אינן ליניאריות, נפוץ השימוש באלגוריתם דומה הנקרא מסנן קלמן מורחב (Extended Kalman Filter) - שלרוב מוכר בקיצורו EKF [6].

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

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

עריכה: שיר רוזנבלום-מן

מקורות לקריאה נוספת:

[1] על GPS במדע גדול, בקטנה

[2] המאמר המקורי של קלמן מ-1960 בכתב עת עלום שם

[3] מהנדס נאס"א סטנלי שמידט מספר על גילוי קלמן פילטר ושילובו בפרויקט אפולו

[4] מסנן קלמן, מתוך קורס SLAM המועבר על-ידי Cyrill Stachniss באוניברסיטת פרייבורג, גרמניה

[5] שימוש במסנן קלמן ברכבים אוטונומיים (בפרק המיקום)

[6] מסנן קלמן מורחב, מתוך קורס SLAM המועבר על-ידי Cyrill Stachniss באוניברסיטת פרייבורג, גרמניה