Behavior Tree — מבנה-בקרה שנולד במשחקים (Halo, BioShock) והגיע לרובוטיקה

רובוטיקה

הגדרה

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

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

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

המבנה מצרף שתי תכונות שקשה להשיג יחד. הראשונה היא תגובתיות — היכולת להגיב מהר לשינוי, להאט כשאדם נכנס למסלול. השנייה היא מודולריות: לפתח, לבדוק ולעשות שימוש חוזר ברכיב לחוד. בספר Behavior Trees in Robotics and AI: An Introduction מ-2018 מוצג היחס למבנים קודמים: ארכיטקטורת ההכפפה של רודני ברוקס, מסימני-ההיכר של בינה מלאכותית מגולמת, מתורגמת ישירות לעץ — כל בקר הופך לפעולה וצומת-בחירה יחיד מייצר עץ שקול.

המבנה התפתח בתעשיית המשחקים, כמנגנון ההחלטות של דמויות שאינן בשליטת השחקן, ומשם עבר לאקדמיה; הוא שימש ב-Halo, ב-BioShock וב-Spore. הוא הוצע כמסגרת-בקרה רב-משימתית לכלי-טיס בלתי-מאוישים ולרובוטים מורכבים, ובקרנגי מלון למניפולציה רובוטית. קבוצת KTH בנתה עליו את המערכת שלה בגמר תחרות האיסוף של אמזון ב-2015 וב-2016, ודיווחה שהמודולריות אפשרה לשלב יכולות של מתכנתים בעלי רקע שונה. עבור מערכת ההפעלה לרובוטים ROS פורסמה ספרייה בקוד פתוח שעלי-העץ בה נכתבים ב-C++ או בפייתון, אך שוחררה רק להפצות שהגיעו לסוף-חייהן. אותו מבנה מתוכנן-מראש הוא גם ההבדל מתכנון משימה ותנועה (TAMP), שבו המתכנן גוזר בעצמו גם את רצף תת-המשימות וגם את המסלולים שמבצעים אותן, מתוך הגאומטריה של הסצנה.