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

פוסט אורח מאת ד"ר ד״ר איל טייטלר, בשיתוף עמותת סיינס אברוד

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[1] פוסט קודם על למידה מחיזוקים – מדע גדול, בקטנה

[2] למידה מחיזוקים מבוזרת בתחבורה

[3] המאמר הראשון שעליו מתבססת הכתבה

[4] המאמר השני שעליו מתבססת הכתבה