מסנן חלקיקים
מסנן חלקיקים (באנגלית: Particle filter) הוא אלגוריתם גנטי סטטיסטי, המבוסס על מסנן בייסיאני, העושה שימוש בשיטת מונטה קרלו לשערוך מצב מערכת המשתנה בזמן. מסנן חלקיקים מיועד לשערך מצבי מערכתיים מסובכים שקשה לתאר אותם בצורה ניתוחית ומדויקת. משמש בתחום הרובוטיקה, ניווט וראייה ממוחשבת.
מצב המערכת מיוצג באמצעות אוסף מצבים דטרמיניסטיים אפשריים, קרי חלקיקים. אלו נקבעים מתוך המידע הזמין על המערכת, וכל חלקיק מקבל משקל בהתאם להתאמתו למידע הקיים. חלקיקים עם משקל גבוה יותר מייצגים מצב סביר יותר של המערכת.
על אף שהבסיס המתמטי פותח כבר בשנות ה-60 של המאה ה-20 עבור פתרון בעיות לא לינאריות מתחום מכניקת הזורמים, המונח "מסנן חלקיקים" ניתן לראשונה בשנת 1996 במאמר של דל מוראל.[1]
האלגוריתם משמש בין היתר לפתרון בעיות לא לינאריות ומודל מרקוב חבוי.
האלגוריתם משתמש רק במדידות החדשות ובמצב המערכת כפי שהתקבל מההערכה שלו, ללא התייחסות לערכים קודמים. לפיכך, קל ליישם את האלגוריתם במערכות זמן אמת.
אלגוריתם
פעולת האלגוריתם כוללת שני שלבים מרכזיים:
- חיזוי: הפעלת מודל חיזוי כדי לקבל הערכה של מצב המערכת טרום מדידה (א-פריורי).
- עדכון: עדכון ההערכה בעקבות התצפיות/מדידות שהתקבלו בפועל.
אלגוריתם מסנן חלקיקים הוא אלגוריתם רקורסיבי לאחר אתחול החלקיקים - חלקיקים מיוצגים על ידי נקודות אקראיות במרחב הסטוכסטי של המערכת, בכל מחזור מבצע[2]:
- קידום מצב החלקיקים - חיזוי המצב הבא של החלקיקים בהתאם למידע הקיים בפונקציית ההסתברות של המערכת, על בסיס מודל.
- מדידה - מידע עדכני המתקבל על מצב המערכת. לדוגמה: מדידות מחיישנים.
- הערכת משקלים - ניתן לחשב משקל עבור כל חלקיק, כך שמשקל גבוה מייצג התאמת גבוהה בין מצב המערכת המעודכן על בסיס המדידה למצב שמייצג החלקיק.
- עדכון מצב המערכת והערכת אי הוודאות.
- דגימה מחדש של החלקיקים (resample) - חלקיקים עם משקל גבוה ייווצרו מהם דגימות חלקיקים נוספים, וחלקיקים עם משקל נמוך ייווצרו מהם פחות חלקיקים או יוסרו מאוסף החלקיקים. ישנן מספר שיטות המתארות באילו תנאים נדרש לבצע דגימה מחדש וכיצד מתבצעת.[3]
ראו גם
קישורים חיצוניים
- אלגוריתמי ניווט ושיערוך מקום, קמפוס IL - פרק אחרון עוסק במסנן חלקיקים.
מסנן חלקיקים, סרטון באתר יוטיוב המסביר על מסנן חלקיקים עבור ניווט רובוטים, יולי 2020, בריאן דגלס (Brian douglas)
הערות שוליים
- ^ Del Moral, Pierre (1996). "Non Linear Filtering: Interacting Particle Solution" (PDF). Markov Processes and Related Fields. 2 (4): 555–580.
- ^ תיאור רצף הפעולות אלגוריתם מסנן חלקיקים, matlab
- ^ Resampling Methods for Particle Filtering: Classification, implementation, and strategies, IEEE, 2015
36815625מסנן חלקיקים