מיפוי ואיכון בו-זמניים (SLAM)

מהי הבעיה: לדעת איפה אתה, בלי מפה מוכנה מראש

מיפוי ואיכון בו-זמניים (SLAM) היא המשימה שבה רובוט בונה מפה של סביבה לא-מוכרת ובה-בעת מאתר את מיקומו שלו בתוך אותה מפה שהוא בונה. ראשי-התיבות מייצגים Simultaneous Localization and Mapping.

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

משפחות האלגוריתמים: מסנן קלמן, מסנן חלקיקים ו-GraphSLAM

התפתחו כמה משפחות פתרון. מסנן קלמן המורחב (EKF-SLAM) היה השיטה המקובלת בשנות ה-90 ותחילת שנות ה-2000, עד שהוצג FastSLAM — מאמר של מייקל מונטמרלו, סבסטיאן תרון, דפנה קולר ובן וגברייט מ-2002. מסנן חלקיקים מייצג את אי-הוודאות באמצעות אוסף השערות מתחרות, שכל אחת מהן מציעה מיקום אחר, וההשערות המוצלחות שורדות. GraphSLAM מנסח את הבעיה כגרף של אילוצים ופותר אותה כבעיית אופטימיזציה, וגישות של כיוונון-אלומות מעריכות יחדיו את מסלול הרובוט ואת מיקומי נקודות-הציון; שיטה כזו משמשת ב-ARCore של גוגל.

חיישנים: לידאר מול חזותי, ועוד

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

לולאת סגירה (Loop Closure): לזהות מקום שכבר ביקרת בו

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

מערכת מוכרת שממחישה את כל התהליך הזה בפועל היא ORB-SLAM, שפרסמו ראול מור-ארטל, חוסה מונטיאל וחואן טרדוס ב-2015 בכתב-העת IEEE Transactions on Robotics: מערכת SLAM חד-מצלמתית (מונוקולרית) בזמן-אמת שמשתמשת באותו סוג מאפיין — ORB — לכל שלבי הצנרת: מעקב, מיפוי, מיקום-מחדש (relocalization) וסגירת-לולאה, כדי לאפשר סגירת-לולאה גם על בסיסי-קו רחבים (wide baseline) ואתחול אוטומטי מלא. אסטרטגיית "שרידת-המתאימים-ביותר" שלה בוחרת אילו נקודות ומסגרות-מפתח (keyframes) לשמור, כך שהמפה נשארת קומפקטית וגדלה רק כשתוכן-הסצנה משתנה בפועל — מה שמאפשר הפעלה ממושכת (lifelong operation). המערכת הוערכה על 27 רצפים ממאגרי-נתונים פופולריים והשיגה, לפי הכותבים, ביצועים חסרי-תקדים ביחס לשיטות SLAM מונוקולריות מתקדמות אחרות מאותה תקופה. קוד-המקור שלה שוחרר בפומבי, והמערכת שימשה בסיס לגרסאות מאוחרות יותר.

היסטוריה: מסמית' וצ'יזמן ועד אתגרי DARPA

היסטורית, העבודה של סמית' וצ'יזמן על ייצוג אי-ודאות מרחבית מ-1986 נחשבת ליסוד, ובראשית שנות ה-90 הובילה קבוצתו של יו דורנט-וייט את התחום — כולל מאמר משותף עם ג'ון לאונרד מ-1991 שהציג בניית-מפה ואיכון בו-זמניים לרובוט נייד עצמאי. ראשי-התיבות SLAM עצמם נטבעו במאמר "Localization of Autonomous Guided Vehicles", שהופיע לראשונה ב-ISR ב-1995. אתגרי DARPA של שנות ה-2000, ובהם הרכבים Stanley ו-Junior בהנהגת סבסטיאן תרון שזכו וסיימו שנייה בהתאמה באתגרי ה-Grand וה-Urban, הביאו לתחום תשומת-לב עולמית.

השימושים: ממכשירי מציאות-מדומה ועד שואבי-אבק ביתיים

השימוש נפוץ הרבה יותר משנדמה: משקפי מציאות-מדומה, רכב אוטונומי, רחפן, כלי-שיט תת-ימי ורכב-נחיתה פלנטרי. גם בבית — שואב-האבק Neato XV-11, שיצא ב-2010, היה מן הראשונים שהחליפו תנועה אקראית בניקוי בשורות ישרות בעזרת מיפוי לייזר. גרסאות מודרניות של SLAM חזותי משמשות גם במשקפי מציאות-מדומה למעקב-מיקום בלי צורך בעוגני-חיישנים חיצוניים.