הבעיה: רובוט בסביבה מלאה חפצים
תכנון משימה ותנועה (TAMP) הוא תכנון לרובוט שצריך להחליט גם מה לעשות ובאיזה סדר וגם איך להזיז את עצמו ואת החפצים, כששתי ההחלטות תלויות זו בזו. זו אינה הרחבה של תכנון תנועה אלא בעיה בפני עצמה, וכך היא מוגדרת בסקירת-המחקר המרכזית בתחום — "Integrated Task and Motion Planning" מאת קיילן ריד גארט ועמיתיו, שהתקבלה ל-Annual Review of Control, Robotics, and Autonomous Systems כרך 4 ופורסמה ב-2021.
בסביבות מובנות כמו מפעל אפשר לפרט התנהגות ישירות בידי אדם, אבל חלק מהיישומים המסקרנים ביותר הם דווקא בסביבות אנושיות לא-מובנות — בתים, בתי-חולים ואתרי בנייה. שם תינתן לרובוט מטרה מוגדרת, למשל לבשל ארוחה ולהגיש אותה לדייר מבוגר, אבל הפעולות הדרושות ישתנו מאוד לפי מצב הסביבה: ייתכן שיצטרך לפתוח ארונות ולהוציא מהם חפצים רק כדי להגיע לקערה.
למה אי-אפשר פשוט להרחיב תכנון תנועה
תכנון תנועה לבדו פותר בעיה צרה יותר: כיצד להעביר את הרובוט ממצב אחד לאחר בלי להתנגש בעצמים שבעולם. הוא נוסח בידי תומאס לוזאנו-פרס כחיפוש מסלולים במרחב-התצורות של הרובוט, מרחב שממדיו מייצגים את המפרקים הניתנים לשליטה, והשיטות היעילות ביותר לפתרונו מבוססות על דגימה או על אופטימיזציה עם אילוצים.
מה שהרובוט אינו יכול לעשות בעזרתו הוא לשנות את העולם. ברגע שהוא צריך להרים חפצים ולהניח אותם, התכנון חייב להביא בחשבון את מצב העולם כולו. הניסיון להרחיב ישירות את שיטות תכנון-התנועה למצב הזה נכשל אלגוריתמית: מצב העולם, כשרואים בו מערכת קינמטית אחת, הוא תת-מופעל מאוד — מכל תצורה, את רוב דרגות-החופש אי-אפשר לשנות כרצוננו. הרובוט יכול לשנות את מיקומו של עצם רק על-ידי כך שיזוז אליו וייגע בו.
מאין מגיע החלק הבדיד: המבנה המודאלי של המרחב
כאן נמצא ההסבר לכך שהבעיה בדידה ורציפה בעת ובעונה אחת, והוא פיזי ולא סמלי. עבודות של אלאמי, ברניצקי והאוזר ועמיתיהם הראו שלמרחב-התצורות של העולם יש מבנה מודאלי חשוב: בהתאם למקום שבו מונחים העצמים ולאופן שבו הם נאחזים, השינויים החוקיים בעולם שייכים למוד אחר, כלומר לתת-יריעה אפשרית אחרת של המרחב השלם. אפשר לעבור בין מודים רק בנקודות החיתוך שבין המרחב האפשרי של המוד הנוכחי לזה של המוד החדש, וחיתוך כזה הוא בדרך-כלל תת-מרחב נמוך-ממד עוד יותר.
מן הסיבות האלה נכון לראות את התכנון כבעיית חיפוש היברידית בדידה-רציפה: רצף סופי של טיפוסי-מוד בדידים — אילו עצמים להרים ולהניח — יחד עם פרמטרי-מוד רציפים ועם מסלולי תנועה בתוך כל מוד. החלק הבדיד אינו רק הפשטה סמלית שנכפית מבחוץ — הוא מעוגן גם במעברים פיזיים ממשיים.
הדוגמה שמסבירה למה אי-אפשר להפריד
הדוגמה שהמאמר בוחר כדי להראות זאת היא מטבח. המטרה: להניח סיר מסוים על אחת מלהבות הכיריים. מתכנן שמתעלם מההיבטים הגאומטריים עשוי לבחור שלד-תוכנית ברמה גבוהה — לנוע כשהיד פנויה, להרים את הסיר, לנוע כשהוא אוחז בו, ולהניח אותו. לשלד יש נעלמים שטרם נקבעו: תצורות של הרובוט, תנוחת-אחיזה, תנוחות-הנחה ומסלולים. אבל ייתכן שאין שום קבוצת ערכים שמקיימת את האילוצים שהשלד מטיל: קומקום, למשל, עשוי לתפוס את הלהבה המבוקשת ולמנוע כל הנחה בטוחה של הסיר. אז דרוש שלד חדש — קודם להזיז את הקומקום, ורק אחר-כך להניח את הסיר. זה שינוי בתוכנית שברמה הגבוהה שנכפה על-ידי הגאומטריה שברמה הנמוכה.
שלושה תחומים, ואף אחד מהם לבדו אינו מספיק
התקציר של הסקירה קובע זאת בלשון חד-משמעית: בעיות תכנון משימה ותנועה מכילות רכיבים של תכנון-משימה בדיד, של תכנון מתמטי בדיד-רציף, ושל תכנון תנועה רציף — ולכן אי-אפשר לטפל בהן ביעילות באף אחד מהתחומים האלה ישירות. הדרישה הקריטית לכלליות אינה נמצאת באף אחד משני הקצוות אלא ביניהם: רובד ביניים שבו נבחרים פרמטרי-המוד הממשיים, כיצד לאחוז בעצם והיכן להניח אותו, והם שקובעים אילו תנועות רציפות חוקיות במערכת. המאמר מציין שמחלקת הבעיות הזו קשה חישובית בתאוריה ודורשת תחכום אלגוריתמי בפועל.
איך פותרים, ומה נשאר פתוח
רבות מהגישות לתכנון משימה ותנועה נראות בסקירה כשילוב בין חיפוש על מבני-תוכנית בדידים — שלדים, כלומר תוכניות מוגדרות-חלקית — לבין סיפוק אילוצים על פרמטרי-פעולה מעורבים שהמבנה הבדיד מייצר. דוגמה קונקרטית היא PDDLStream, שפורסמה בכנס ICAPS ב-2020 בידי קיילן ריד גארט, תומאס לוזאנו-פרס ולסלי פאק קלבלינג: היא מרחיבה את שפת-התיאור PDDL כך שתתמוך במפרט הצהרתי לפרוצדורות שדוגמות ערכים מספקים — אילוצי קינמטיקה, התנגשות, נראות ותנועה — ומתייחסת למימוש שלהן כאל קופסה שחורה.
הסקירה מגבילה את עצמה במפורש: היא מניחה פעולות דטרמיניסטיות, ידיעה מלאה של מצב העולם, וגופים קשיחים בעלי צורה ידועה, ומסמנת כסוגיות פתוחות את ההרחבה לאי-ודאות, לעצמים מתעוותים, לנוזלים, לדינמיקה, לזמן ולסוכנים אחרים. השאלה הקריטית שהיא מעלה היא מאין באים בכלל המודלים האלה, ותשובתה מפנה ללמידת מכונה: למידת מודלים, למידת הכוונה לחיפוש, ולמידת הכוונה לדגימה.