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

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

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

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

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

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

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

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

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

ישנם כמה גורמים מרכזיים שיכולים להשפיע על הביצועים והדיוק של מערכות SLAM. אלו כוללים:

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

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

עריכה: סמדר רבן

מקורות והרחבות

[1] פוסט על רובוטים אוטונומיים

[2] פוסט על על בינה מלאכותית המסוגלת לתכנן תכניות

[3] פוסט בנושא *A -בקרוב!

[4] פוסט על לידאר

[5] פוסט על מסנן קלמן

[6] פוסט על תורת הגרפים