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

 ב"חידת ה-15" [1] המשימה שלנו היא לסדר 15 לוחיות, הממוספרות מ-1 עד 15, בתוך לוח של 4 על 4 משבצות שחסרה בו לוחית אחת. עלינו להביא את הלוחיות מסדר התחלתי נתון לסדר הנכון,

כשבכל צעד אנו מזיזים אחת הלוחיות אל המשבצת הריקה (ראו איור 1).

איור 1: חידת ה-15.

אנקדוטה מוכרת היא שבשנת 1880 הציע המתמטיקאי והשחמטאי סם לויד פרס למי שיצליח לפתור את החידה. לויד ידע היטב שעם הסידור ההתחלתי שהוא נתן, שבו הוחלפו רק הלוחיות 14 ו-ו15, אין לחידה פתרון [1].

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

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

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

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

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

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

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

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

נעיר שעל אף כמה קווי דמיון בעיית MAPF שונה מ"בעיית הסוכן הנוסע" [4] בכמה היבטים מהותיים, בראש ובראשונה בכך שהקושי שבה נובע מריבוי הסוכנים.

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

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

מקורות:

[1] על חידת ה-15
[2] מקל סלפי לכלבים. יש דבר כזה.
[3] על בעיות P ו-NP
[4] על בעיית הסוכן הנוסע