איך באמת נראית המפה שרובוט מחזיק
מפת רשת-תפוסה (Occupancy Grid Map) היא ייצוג של הסביבה כרשת תאים אחידה, שבה כל תא מחזיק הסתברות שיש בו מכשול — במקום ציור או סימון בינארי של קיר. קורא לא-טכני מדמיין בדרך-כלל שהרובוט מחזיק תוכנית-קומה מצוירת; מה שהוא באמת מחזיק הוא טבלה של מספרים.
ויקיפדיה מגדירה את מיפוי רשת-התפוסה כמשפחה של אלגוריתמים ברובוטיקה הסתברותית, לרובוטים ניידים, שמטפלים בבעיה של הפקת מפות מנתוני מדידה רועשים ובלתי-ודאיים. הרעיון הבסיסי הוא לייצג את המפה כשדה של משתנים אקראיים בינאריים במרווחים שווים, שכל אחד מהם מייצג נוכחות של מכשול באותו מקום בסביבה, ואלגוריתמי הרשת מחשבים אומדנים מקורבים של ההתפלגות המאוחרת שלהם. המפות הנפוצות ביותר הן דו-ממדיות, והן מתארות פרוסה אחת של העולם התלת-ממדי.
מורבק ואלפס, 1985: המפה הראשונה נבנתה מסונאר
רשתות תפוסה הוצעו לראשונה בידי הנס מורבק ואלברטו אלפס ב-1985, במאמר "High Resolution Maps from Wide Angle Sonar" של מכון הרובוטיקה באוניברסיטת קרנגי מלון. הרובוט שעליו נוסתה השיטה, Neptune, נשא טבעת של 24 מתמרי-על-קול מתוצרת Polaroid, לכל אחד אלומה רחבה בזווית של כ-30 מעלות.
המפה שהמאמר מתאר היא בדיוק מה ששמה אומר: מערך דו-ממדי של תאים בגודל אחיד, שכל אחד מחזיק ערך בטווח שבין מינוס אחד לאחד. ערך שקטן מאפס מייצג אזור שקרוב לוודאי ריק, אפס בדיוק מייצג תפוסה לא-ידועה, וערך גדול מאפס מייצג מקום שקרוב לוודאי תפוס. גודל התא בניסויים היה שישה אינץ', ומפה טיפוסית מנתה כ-3,000 תאים. קריאות מכמה חיישנים ומכמה עמדות שולבו זו בזו: מדידות שמסכימות שתא ריק מחזקות זו את זו, והאזור שמוסק כריק מכרסם באזור החשוד כתפוס ומחדד אותו.
הסדר הנכון מול SLAM: מה מניחים, ומתי
ההגדרה של מיפוי רשת-תפוסה כוללת הנחה מפורשת: שתנוחת הרובוט ידועה. במבט ראשון זו נשמעת כמו סתירה למיפוי ואיכון בו-זמניים, שכל קיומו נובע מכך שהמיקום דווקא אינו ידוע מראש — אבל אין כאן סתירה, אלא חלוקת עבודה בין שתי שאלות.
רשת-תפוסה עונה על שאלה ממוקדת אחת: בהינתן שידוע מהיכן נמדדה כל קריאה, כיצד לצבור את הקריאות למפה אחת? SLAM עונה על השאלה שמסביבה — כיצד לאמוד את המיקום ואת המפה יחד, כששניהם אינם ידועים. בפועל השתיים מורכבות זו על זו: אלגוריתם SLAM מפיק אומדן של מסלול הרובוט, ורשת-התפוסה היא לרוב הצורה שבה המפה שיוצאת ממנו נשמרת. ויקיפדיה מדגישה זאת גם בפרט טכני: נתוני הבקרה והאודומטריה אינם משתתפים כלל באלגוריתם רשת-התפוסה עצמו, מפני שהמסלול נחשב בו ידוע.
למה אי-אפשר לחשב את המפה כולה, ומה עושים במקום
הקושי החישובי הוא בממדיות. אם המפה מכילה 10,000 תאים — מפה קטנה יחסית — מספר המפות האפשריות שאפשר לייצג ברשת כזו הוא שתיים בחזקת 10,000, ולכן חישוב הסתברות מאוחרת לכל המפות האלה אינו בר-ביצוע. הגישה המקובלת מפרקת את הבעיה לבעיות קטנות: לאמוד בנפרד את ההסתברות של כל תא ותא, כשכל אחת מהן בעיה בינארית. ההתפלגות המאוחרת של המפה כולה מקורבת אז בפירוקה למכפלה של ההתפלגויות של התאים הבודדים, ובזכות הפירוק אפשר להריץ מסנן בייס בינארי לכל תא; מקובל לעשות זאת בייצוג לוג-יחסי-סיכוי של ההסתברות שהתא תפוס.
מה הפירוק הזה מפסיד
הפירוק נוח, אבל ויקיפדיה מציינת במפורש שהוא כן מאבד חלק מהמבנה של הבעיה: הוא אינו מאפשר לדגמן תלות בין תאים שכנים. במציאות קיר הוא רצף — אם תא מסוים תפוס, סביר יותר שגם שכנו תפוס — והנחת אי-התלות מוחקת בדיוק את המידע הזה.
המאמר המקורי נתקל בתופעה קרובה כבר בשטח. במפות גולמיות ברזולוציה של שישה אינץ', שנבנו מכמאה קריאות סונאר, התקבלו פסים צרים של תאים המסומנים כתפוסים, ומיקומם היחסי נע בכמה פיקסלים בין מפות שנוצרו בנפרד לאותו אזור. ההסבר שניתן: התדר-המרחבי-הגבוה במיקום הפסים הוא רעש, ורק התדרים הנמוכים נושאים מידע — והפתרון היה טשטוש מכוון של התאים התפוסים.
איך זה נראה בקוד של היום: ROS ומפות-עלות
הייצוג הזה חי היטב. ההודעה התקנית של מערכת ההפעלה לרובוטים לרשת דו-ממדית, nav_msgs/OccupancyGrid, מחזיקה את התאים במערך שטוח בסדר שורות, ומציינת שהערכים תלויים ביישום אך שנפוץ ש-0 מייצג לא-תפוס, 1 מייצג תפוס בוודאות, ומינוס אחד מייצג לא-ידוע.
בערמת הניווט Nav2 של ROS 2 נטענת מפת רשת-התפוסה כשכבה סטטית בתוך מפת-עלות רב-שכבתית, שמעליה שכבת מכשולים מנתוני החיישנים ושכבת ניפוח שמרחיבה אותם ברדיוס ניפוח כדי לשמור מרווחי בטיחות. התיעוד שם חושף עד כמה החוט נמשך: פרמטר בשם lethal_cost_threshold מוגדר כעלות המזערית במפת רשת-תפוסה כדי שתא ייחשב מכשול קטלני, וברירת-המחדל שלו היא 100; ופרמטר אחר קובע אם לפרש את המפה כשלושה ערכים בלבד — פנוי, תפוס ולא-ידוע — או לפי הערכים השמורים בה. שלוש המילים האלה הן בדיוק המטרה שמורבק ואלפס ניסחו כבר ב-1985: הם ציפו שהסונאר יספק מפות שאזוריהן מסווגים כריקים, תפוסים או לא-ידועים. הייצוג שבנו בפועל היה רצף ערכים ולא שלישייה בדידה, אבל אוצר-המילים שרד.