תכנון תנועה (Motion Planning)

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

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

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

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

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