מנווטים את דרכנו אל העתיד
אתם מכירים את האנשים האלה, כאשר הם מטיילים בעיר חדשה הם לוקחים מפה, יוצאים ברגל ומתחילים פשוט לטייל בעיר?
במאמר זה נלמד כיצד מתרגמים את מה שאנחנו עושים בראש באופן כמעט בלתי מודע לאלגוריתם חכם שיכול לנווט מערכת אוטונומית על-בסיס מידע מהחיישנים.
אני אישית תמיד אהבתי להכיר ככה מקומות חדשים, וככל שהתעמקתי בעולם של הניווט הממוחשב, יצא לי לחשוב על איך משהו שאני לוקח כמובן מאליו למעשה מסתיר מאחוריו אלגוריתמים שלמים.
בסופו של דבר, אני בונה מפה ומנווט בה ע"י עיבוד נתונים מחיישנים (העיניים שלי שמבצעות עיבוד תמונה), או במצבים יותר מתקדמים, אני גם בונה את המפה תוך כדי התקדמות וכך מסנכרן איפה אני נמצא על המפה (SLAM).
בפוסט הזה נראה איך מתרגמים את מה שאנחנו עושים בראש באופן כמעט בלתי מודע לאלגוריתם חכם שיכול לנווט מערכת אוטונומית על-בסיס מידע מהחיישנים.
תיארתי למעשה שלושה אתגרי ניווט:
- תכנון מסלול אופטימלי לנווט על גבי מפה ידועה
- בניית מפה תוך כדי התקדמות
- בניית מפה וגם מיקום עצמי (localization) על גביה תוך כדי התקדמות
לפני שנצלול, אציין שבנקודה הזאת אנו מקבלים את המידע מאלגוריתם ה-perception, שעשה עבורנו את היתוך הנתונים, נתן תוויות לאובייקטים סביבנו והגדיר את הסביבה שלנו.
אתגר ראשון: מיקום עצמי על גבי מפה ידועה
במצב הזה יש לי היכרות מוקדמת עם הסביבה, כלומר, אני מטייל עם מפה מאוד מדויקת של המקום בו אני נמצא ואני יכול לזהות קירות ועצמים.
למעשה, המשימה שלי היא למקם את עצמי בסביבה הזאת. כשאנחנו כבני אדם עושים את זה, אנחנו משתמשים בעיניים לאמוד את המרחק מגופים מסוימים, ומשתמשים בנקודות ציון בשביל למקם את עצמנו נכון בתוך המפה. הרובוט יעבוד בצורה דומה.
הוא יקבל מידע על המרחק מהגופים באמצעות Lidar או מצלמה, וכך גם ימפה את הסביבה וימקם אובייקטים ואת עצמו ביחס אליהם. ההבדל הוא שפה ייעשה שימוש בשיטות חישוב מסוימות, למשל particle filter, או monte-carlo localization algorithm.
כמובן שבצורה דומה, גם רכב יכול לנווט בחוץ בצורה כללית באמצעות מפה מה-GPS ומידע אינרציאלי מה-IMU, אבל במצב כזה יחסר לו המידע המדויק לגבי אובייקטים בסביבה – ולכן נרצה גם יכולות של מיפוי בנוסף למידע שאנו מקבלים.
אתגר שני: מיפוי – איך אני בונה את הסביבה שלי?
בתרחיש הזה, הגעתי למשל לברצלונה, יצאתי החוצה והתחלתי לטייל. אין לי מפה, אבל אני הולך במסלול ידוע מראש ואוסף נקודות ציון תוך כדי שאני הולך (La Sagrada Familia, La Boqueria Mercado, etc.).
באופן דומה, אני ארצה שגם לרובוט שלי תהיה היכולת לבנות מפה על בסיס מדידות ותצפיות.
ארצה לקחת את המדידות מהחיישנים של הרובוט ולתרגם אותם למפות תפוסה, כאשר אפשר להסתכל על מפות דו-ממדיות או תלת-ממדיות, כתלות ביישום הנדרש. את המפה אוכל גם לבנות באמצעות מידע מה-Lidar או מהמצלמה, כאשר אני מניח שאני יודע מראש את המסלול והאוריינטציה של הרובוט.
בפועל, זהו מצב מאוד אידיאלי ונדיר במציאות. לרוב אני ארצה גם לבנות את המפה וגם למקם את הרובוט בתוכה.
אתגר שלישי: SLAM – Simultaneous Localization and Mapping
זוהי הדרך שבה אנחנו מתארים אנשים שיש להם חוש התמצאות טוב ויודעים להסתדר בלי מפה במקום חדש. הם יצאו החוצה, שמו לב לנקודות ציון בסביבה וגם מיקמו את עצמם ביחס אליהם ("ה-La Sagrada Familia הייתה ממערב למלון").
באלגוריתם SLAM אני אוסף מהחיישנים מידע לגבי הסביבה ומידע אינרציאלי, שומר הכל בזכרון, ואז כאשר אני חוזר לנקודת ציון מוכרת, אני יודע למקם במדויק את המקומות שהייתי בהם ויכול ליישר את כל המפה שבניתי כדי לקבל מפה מדויקת יותר.
התהליך הזה מאוד נפוץ בתחום המערכות האוטונומיות, כי לרוב לא תהיה מפה של הסביבה ברמת דיוק גבוהה, וגם אם תהיה, נרצה שהמערכת תהיה רובסטית לשינויים בסביבה.
ל-MATLAB יש לא מעט יכולות בתחום של ניווט מערכות אוטונומיות, ואני מאוד ממליץ לראות את הסרטון הזה (16 דקות) לקבלת מידע נוסף.
ועוד בכלל לא דיברנו על הבקרה שתדאג שנעקוב אחרי המסלול כמו שצריך…
אבל זה, ידידיי, סיפור לפעם אחרת 😊
