מבוא לבינה מלאכותית — מרחב למידה אישי

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

בעיית התכנון: הגדרה פורמלית

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

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

מצב התחלתי (Initial State): המצב שבו העולם נמצא בתחילת תהליך התכנון.

מצב יעד (Goal State): אוסף של עובדות שצריכות להיות נכונות בסיום התוכנית. התוכנית נחשבת מוצלחת אם היא מגיעה למצב שבו כל עובדות היעד מתקיימות.

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

ייצוג פעולות: מודל STRIPS

מודל STRIPS (STanford Research Institute Problem Solver) הוא אחד מהפורמליזמים הנפוצים והבסיסיים ביותר לייצוג פעולות בבעיות תכנון. הוא מאפשר לתאר פעולות בצורה פשוטה וברורה, ומקל על בניית אלגוריתמי תכנון.

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

מרכיבי פעולת STRIPS:

תנאים מוקדמים (Preconditions): קבוצת עובדות שחייבות להיות נכונות במצב הנוכחי כדי שניתן יהיה לבצע את הפעולה. אם תנאי כלשהו אינו מתקיים, הפעולה אינה חוקית.
רשימת הוספה (Add List): קבוצת עובדות שהופכות לנכונות לאחר ביצוע הפעולה. עובדות אלו מתווספות למצב העולם.
רשימת מחיקה (Delete List): קבוצת עובדות שהופכות ללא נכונות לאחר ביצוע הפעולה. עובדות אלו נמחקות ממצב העולם.

דוגמה לפעולת STRIPS: נניח פעולה של 'העברת בלוק A מ-X ל-Y'.

שם הפעולה: Move(A, X, Y)
תנאים מוקדמים:
- On(A, X) - בלוק A נמצא על X
- Clear(A) - בלוק A פנוי (אין עליו כלום)
- Clear(Y) - מקום Y פנוי
רשימת הוספה:
- On(A, Y) - בלוק A נמצא על Y
- Clear(X) - מקום X פנוי
רשימת מחיקה:
- On(A, X) - בלוק A כבר לא על X
- Clear(Y) - מקום Y כבר לא פנוי

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

גישות לתכנון: מרחב מצבים מול מרחב פעולות

קיימות שתי גישות עיקריות לפתרון בעיות תכנון, הנבדלות באופן שבו הן מגדירות את מרחב החיפוש:

תכנון מרחב מצבים (State-Space Planning)

גישה זו רואה את בעיית התכנון כבעיית חיפוש במרחב המצבים האפשריים של העולם. הצמתים בגרף החיפוש הם מצבי עולם, והקשתות הן פעולות המעבירות ממצב אחד למשנהו. החיפוש מתבצע קדימה מהמצב ההתחלתי לעבר מצב היעד (forward search) או אחורה ממצב היעד למצב ההתחלתי (backward search). אלגוריתמים כמו BFS, DFS, A* יכולים לשמש כאן, אך יש צורך בפונקציה היוריסטית מתאימה לבעיות תכנון.

תכנון מרחב פעולות (Plan-Space Planning)

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

אתגרים ויישומים

תכנון בבינה מלאכותית מתמודד עם מספר אתגרים משמעותיים:

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

למרות האתגרים, לתכנון יישומים רבים וחשובים:

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

שאלות לדיון

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

נקודות לתשובת מודל

הבדל בין חיפוש לתכנון: חיפוש מוצא נתיב בגרף נתון; תכנון בונה את הנתיב (רצף פעולות) על בסיס הגדרות פעולות דינמיות. תכנון נדרש כאשר פעולות משנות את העולם ותנאי המעבר אינם קבועים מראש.
מודל STRIPS: הגדרה ברורה של מצב התחלתי (עובדות), מצב יעד (עובדות שצריכות להתקיים), ופעולות הכוללות תנאים מוקדמים, רשימת הוספה ורשימת מחיקה. דוגמה עקבית וברורה.
השוואת גישות:
- מרחב מצבים: חיפוש קדימה/אחורה במצבי עולם. יתרון: פשוט להבנה, משתמש באלגוריתמי חיפוש מוכרים. חיסרון: מרחב מצבים ענק, מחויב לסדר ליניארי מוקדם.
- מרחב פעולות: בניית תוכנית חלקית, פתרון בעיות. יתרון: גמישות בסדר הפעולות (סדר חלקי), יכולת להתמקד רק בחלקים הרלוונטיים של הבעיה. חיסרון: מורכב יותר ליישום.
התמודדות עם מרחב מצבים ענק:
- שימוש בהיוריסטיקות חזקות (למשל, היוריסטיקות מבוססות רלקסציה).
- פירוק בעיות תכנון לבעיות משנה קטנות יותר.
- שימוש בתכנון היררכי (Hierarchical Planning).
- שימוש בתכנון בסדר חלקי (Partial-Order Planning) שמפחית את הצורך לבחון סדרים ליניאריים רבים.

מצאתם טעות או שחסר משהו?