לשחרר את הפקק – אלגוריתם חדש מאפשר לרמזורים ללמוד לשתף פעולה וחוסך לכולנו זמן בפקקים // ד״ר איל טייטלר

בשיתוף עמותת מדע גדול בקטנה

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

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

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

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

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

אם כך, כיצד ניתן לתאם בין הצמתים ברשת במצב שבו כל צומת חש רק את סביבתו הקרובה?

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

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

במחקרנו [3] הצענו גישה חדשה: במקום לשדר מידע רב וללמוד לחזות את התנהגות הצמתים השכנים,

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

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

 

אך לא כל הנוצץ ירוק הוא: היינו מצפים  שגל ירוק יווצר באופן ספונטני בלי שנתכנן אותו, כדי לאפשר לתנועה לזרום ביעילות, אך הדבר לא קרה עדיין. לבקרים מבוזרים, גם בעלי מנגנוני סנכרון, יש קושי לייצר תכונות כאלו. הסיבה נעוצה באופן פיזורם של החיישנים בכבישים. החיישנים נמצאים בדרך כלל בסביבת הרמזור, וחשים את מה שקורה במרחק סביר ממנו. בין צמתים, לעומת זאת, יש ״אזור מת״ – אזור מרוחק מכל אחד מהצמתים,  שלא נאספים נתונים  לגביו.  במציאות קורה שבקר מדווח של שיירת רכבים שיוצאת מצומת אחד לשני,  אך כאשר השיירה יוצאת מסביבת הצומת ומגיעה לאזור המת, בפועל היא נעלמת מחיישני המערכת. היעלמות זו גורמת לצמתים להפסיק לא לדווח על השיירה בשפה שלהם, וכתוצאה מכך הצומת הבא “יופתע” כאשר היא תגיע אליו, ויציג לה אור אדום במקום לתת לה גל ירוק. פתרון אינטואיטיבי הוא לאפשר למערכת לזכור את השיירה גם כשהיא באזור המת. בהתאם לכך, בעבודת המשך [4] הצמתים למדו שפה אשר מתארת לא רק מה שקורה כרגע, אלא גם מה שקרה בעבר הלא מאד רחוק.,בכך נוסף למעשה רכיב זיכרון, ונוצרו גלים ירוקים באופן ספונטני לחלוטין.

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

ארגון המדענים הישראלים בחו”ל ScienceAbroad הוא ארגון ללא כוונות רווח, הפועל מאז 2006 לשמירת קשר עם חוקרים ישראלים בעולם והשבת המוחות לישראל. ScienceAbroad הוא קהילה בינלאומית עבור יותר מ-6000 חוקרים ישראלים ב-300 קמפוסים ברחבי העולם. הארגון מפעיל כ 50 מרכזים בצפון אמריקה, אירופה ואוסטרליה ו- 11 תחומים מקוונים המנוהלים על ידי מדענים מתנדבים. הארגון מעניק כלים, מפתח קשרים ופותח דלתות למדענים ישראלים המבקשים לשוב לישראל על מנת שיביאו עימם את הידע, הכישרון, הניסיון והקשרים שצברו לאקדמיה ולתעשיה כמנוע צמיחה לישראל.

 

מקורות

  1. פוסט קודם של מדע גדול בקטנה על למידה מחיזוקים
  2. למידה מחיזוקים מבוזרת בתחבורה
  3. המאמר הראשון שעליו מתבססת הכתבה

 

 

*********************************************

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

ספר לי קצת על עצמך?

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

 

מה היו השיקולים לצאת לחו״ל?

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

 

איך בחרת את המקום לפוסט?

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

 

מה אתה אוהב לעשות כשאתה לא עוסק במחקר ?

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

 

מה היא  החוויה הכי משמעותית  בתקופת הפוסט ?

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

 

יש לך טיפ שהיית רוצה לחלוק עם אלו שמתכוונים לצאת לפוסט?

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

 

איך סיינס אברוד תרומה לתקופתך בפוסט, בייחוד גם שלקחת על עצמך את ניהול קהילת טורונטו?

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

 

כתבות דומות

קריאה לגיוס חוקרים בכירים למרכז החדשנות של הגליל (GIL)

קריאה לגיוס חוקרים בכירים למרכז החדשנות של הגליל (GIL) כחלק מהאוניברסיטה החדשה...

מוסד שמואל נאמן למחקר מדיניות לאומית הקים צוות משימה לאיסוף נתונים על חרם אקדמי על מוסדות ואנשים מישראל

מוסד שמואל נאמן למחקר מדיניות לאומית הקים צוות משימה שתפקידו לאסוף נתונים...

ד”ר נתנאל לויפר, זוכה בתחרות בכנס ה-Falling Walls שהתקיים בברלין

ד”ר נתנאל לויפר הוא חוקר בתחומי הביולוגיה החישובית בפקולטה לרפואה באוניברסיטה העברית,...

מחקר חדש העוסק במוטיבציה של רופאים לחזור לישראל אחרי פלושיפ בחו”ל

השבוע התפרסם המחקר הגדול ביותר שנעשה עד כה על אוכלוסיית הרופאים בהשתלמות...

יש לך דוקטורט, או עד שנה לסיומו? זה הזמן להוביל את השינוי

ננפתחה ההרשמה להגשת מועמדות למחזור ט”ו של תוכנית ממשק – ממדע למדיניות,...

סדרת מפגשים חדשה של המרכז לבריאות, משפט ואתיקה באוניברסיטת חיפה! לשנת תשפ”ה (2024/25)

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

לשחרר את הפקק – אלגוריתם חדש מאפשר לרמזורים ללמוד לשתף פעולה וחוסך לכולנו זמן בפקקים // ד״ר איל טייטלר

בשיתוף עמותת מדע גדול בקטנה למערכות הרמזורים יש תפקיד קריטי בקביעת הזמן...

🔆 הרשמה לוועידה השנתית ה-52 למדע ולסביבה 🌍

26-25 בספטמבר 2024, אוניברסיטת בן גוריון בנגב ️ לאתר הוועידה, לצפייה בתוכנייה ולהרשמה קוד...

הסיבים שמגנים על המושבה // ד״ר אלעד ארד

בשיתוף עמותת מדע גדול בקטנה ביופילם הוא צבר חיידקים שמתאגדים יחד במבנה...