Homework #3

Tal Bereznitskey(060403144) & Yoav Vardi(060414562)

הגדרת הבעיה

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

קוד מקור

• source.zip
  q1.java היא התוכנית הראשית
• לצפייה בקבצי ה-JAVA
• room.java הקוד עבור ארבעה חדרים
• fitness.java פונקציית ה-Fitness עבור צמצום הקוד

בניית התשתיות

בשלב הראשון בנינו את התשתיות הדרושות עבור התיכנות הגנטי:

• העולם מורכב מ:
  1. חדר המוגדר ע"י קירות
  2. רובוט המיוצג ע"י גוף נקודתי במרחב החדר. לרובוט 12 סנסורים במרווחים של 30 מעלות
  3. תיבה - מוגדרת כמלבן במרחב החדר
  
  נתנו לרובוט יכולות לנוע במרחב החדר בלבד, ובנוסף, יכולת להזיז את התיבה באותו מרחב. פעולת ההזזה היא פשוטה, כלומר אינה מערבת שיקולים של כח זוויתי.
  בנוסף מימשנו אפשרות לתצוגה גרפית של העולם ושל תנועת העצמים בו.
  
• יצוג תוכנית LISP:
  בחרנו לממש את עצי התוכניות ב-JAVA בעזרת מימוש פשוט של עץ. קודקוד בעץ-תוכנית מורכב מטרמינל\פונקציה, ורשימה מקושרת של קודקודים המשמשים כפרמטרים לפונקציה, אם יש כאלה. הרצת העץ מתבצעת ע"י הפעלת פונקציית EVAL של הטרמינל\פונקציה שבקודקוד השורש, שגוררת הפעלה רקורסיבית של שאר העץ.

בשלב השני, עברנו למימוש מרכיבי התיכנות הגנטי:

• טרמינלים:
  הגדרנו 15 טרמינלים לפי מאמרו של קוזה: 12 סנסורים המחזירים את המרחק של הרובוט מהאובייקט הקרוב בכיוון מסויים. אובייקט יכול להיות קיר או תיבה אך הסנסור אינו מבדיל ביניהם.
  שלושת הטרמינלים הנוספים מייצגים את תנועת הרובוט בחדר:
  MF - זוז קדימה מטר אחד
  TR - פנה ימינה ב-30 מעלות
  TL - פנה שמאלה ב-30 מעלות
  כל הטרמינלים האלו מחזירים אפס ואין להם פרמטרים.
• פונקציות:
  הגדרנו ארבע פונקציות, שוב לפי מאמרו של קוזה. כל הפונקציות מחזירות ערך עשרוני, ויש להן מספר פרמטרים משתנה:
  (הערה: כאשר אנו מפעילים פונקציה, הכוונה היא שאנו מריצים את תת העץ שלה, ומחזירים את הערך)
  
  IFBMP - הפונקציה מחזיקה שני פרמטרים. בודקת האם הרובוט נמצא במצב "BUMP".
  אם כן, היא מפעילה את הפרמטר הראשון, אחרת, את השני. מצב "BUMP" מוגדר כמצב בו הרובוט נתקל באובייקט בפעם הראשונה.
  IFSTK - הפונקציה מחזיקה שני פרמטרים. בודקת האם הרובוט נמצא במצב "STUCK".
  אם כן, היא מפעילה את הפרמטר הראשון, אחרת, את השני. מצב "STUCK" מוגדר כמצב בו הרובוט ממשיך להתקל באובייקט.
  IFLTE - הפונקציה מחזיקה ארבעה פרמטרים. הפונקציה מבצעת השוואה בין הערכים החוזרים של הפרמטרים הראשון והשני. אם הפרמטר הראשון קטן או שווה לשני, יופעל הפרמטר השלישי. אחרת, יופעל הרביעי.
  PROGN2 - הפונקציה מחזיקה שני פרמטרים, מפעילה את הפרמטר הראשון ולאחר מכן מפעילה (ומחזירה) את הפרמטר השני.
• גנוטיפ:
  מיוצג ע"י עץ תוכנית המכיל תוכנית חוקית המהווה סדר הוראות עבור רובוט בחדר.
  על מנת לייצר גנוטיפ ראנדומלי נגדיר עבורו גובה עץ מקסימלי ואחת משתי שיטות הבנייה Grow או Full.
• אופרטורים גנטיים:
  סלקציה: השתמשנו בשיטת Fitness proportionate selection.
  פונקצית Fitness: הרובוט רץ מספר קבוע של צעדים על החדר לפי התוכנית שמכיל הגנוטיפ. בסיום הריצה, נמדד מרחק התיבה מהקיר.
  הפונקציה מחזירה (מרחק/1) ובכך מתעדפת מרחקים קצרים יותר.
  קרוס-אובר: מתבצע ע"י בחירת תת-עץ אקראי בכל אחד מהגנוטיפים והחלפה ביניהם. נשים לב שאנו שומרים על חוקיות העץ: מאחר והפונקציות\טרמינלים שומרים על סגירות, במובן שכולם מחזירים את אותו טיפוס החזרה (מספר עשרוני).
  מוטציה: בשלב זה, החלטנו לוותר על מימוש המוטציה מתוך מחשבה שהקרוס-אובר יוצר שונות גנטית רחבה מספיק. מעבר לכך, אופן מימוש הגנוטיפ גורם לכך שקרוס-אובר בין גנוטיפ לעצמו יוצר שני פרטים שונים בדומה למוטציה.
  אליטזם: מאחר והמימוש של עצים מועד למוטציה כתוצאה מקרוס-אובר, בחרנו שדור חדש יכלול תמיד את הפרט המתאים ביותר מהדור הקודם.

תוצאות ראשוניות

עם סיום בניית התשתיות החלטנו לבצע מספר הרצות ראשונות.

בנינו חדר כמתואר במאמרו של קוזה:

גודל החדר וגודל התיבה מסומנים בסרטוט, הרובוט ממוקם במרחק מטר מהקיר התחתון והימני. המרחק ההתחלתי של התיבה מהקיר הוא 7.5 מטר.

הגדרות הריצה:
קצב קרוס-אובר: 0.8
גודל אוכלוסיה: 100
גודל עץ התחלתי מקסימלי: 2
צעדים לכל רובוט: 300
מספר דורות: 20

התוצאות:

הגרף הבא מציג את נתוני ה-best fitness, average fitness ומרחק התיבה מהקיר לאורך הדורות:

מוצגות חמשת התוכניות הטובות (מתאימות) ביותר בחמישה דורות:

	הפרט המתאים ביותר בדור 0 S0
	הפרט המתאים ביותר בדור 3 (IFSTK (IFSTK (IFLTE TL0 S10 MF S4) (IFBMP S7 MF)) (IFLTE (IFBMP TR0 S5) (IFLTE S5 MF TR0 S5) (IFBMP S0 S4) (IFLTE S10 S1 S8 S0)))
	הפרט המתאים ביותר בדור 6 (PROGN2 (IFLTE (IFLTE (IFLTE TL0 S9 TR0 S8) (IFSTK (IFSTK (PROGN2 S8 TL0) (PROGN 2 S1 S4)) S8) S6 (PROGN2 S8 S2)) TL0 S5 MF) TR0)
	הפרט המתאים ביותר בדור 13 (PROGN2 (IFLTE (IFLTE (IFLTE S6 S9 TR0 S8) (IFSTK (IFSTK (PROGN2 S8 TL0) (PROGN2 S1 S4)) S8) S6 (PROGN2 S8 TL0)) TL0 S5 MF) TR0)
	הפרט המתאים ביותר בדור 19 ובכל הדורות (PROGN2 (IFLTE (IFLTE (IFLTE (IFLTE TL0 S9 TR0 S8) (IFSTK (IFSTK (PROGN2 S8 TL0) S8) S8) S6 (PROGN2 S8 S2)) S8 S6 (PROGN2 S8 (PROGN2 (IFLTE (IFLTE (PROGN2 (PROGN2 S1 S4) S4) (IFSTK (IFSTK (PROGN2 S5 TL0) (PROGN2 S1 S4)) S8) S6 (PROGN2 S8 (PROGN2 (IFLTE (IFLTE (IFLTE (IFLTE TL0 S9 TR0 S8) (IFSTK (IFSTK (PROGN2 S8 TL0) S8) S8) S6 (PROGN2 TR0 S4)) S8 S6 (PROGN2 S8 (PROGN2 (IFLTE (IFLTE (PROGN2 (PROGN2 S1 S4) S4) (IFSTK (IFSTK (PROGN2 S5 TL0) (PROGN2 S1 S4)) S8) S6 (PROGN2 S8 S2)) TL0 S5 MF) TR0))) TL0 S5 MF) TR0))) TL0 S5 MF) (IFLTE (IFLTE TL0 S9 TR0 S8) (IFSTK (IFSTK (PROGN2 S8 TL0) S8) S8) S6 (PROGN2 S8 S2))))) TL0 S5 MF) TR0)

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

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

1. את הבעיה הראשונה ניתן לפתור ע"י הגדלת מרחב החיפוש. לדוגמא הגדלת החדר, או הפיכת הבעיה לכללית יותר, ולא ספציפית לקונפיגורציית חדר מסוימת.
2. ניסינו לפתור את הבעיה במספר דרכים. ראשית הגדלנו את מספר הצעדים של הרובוט ל-600, צעד שעזר במקרים של רובוטים משוטטים, אך עדיין לא הבדיל בין תוכניות שלא גרמו לרובוט לזוז.
3. עוד רעיון היה הוספת הסנסור SS ע"פ המאמר של קוזה. סנסור זה מחזיר את המינימום של כל הסנסורים, ולכן אמור לתת לרובוט כלי נוסף לביצוע חישובים.
4. רעיון נוסף שניסינו, היה הוספת מרכיב נוסף לפונקציית הפיטנס, שתעדף רובוטים ע"פ המרחק המינימלי מן התיבה במהלך ריצתם. פתרון זה אמנם ייצר שוני בין פרטים שלא הזיזו את התיבה, אך עדיין לא פתר את הבעיה בצורה מספקת.
5. הפתרון האחרון עליו חשבנו היה הוספת מוטציות , מאחר ונראה כי קרוס-אובר בלבד אינו מספק את השונות הגנטית הדרושה כדי להגיע לפתרון.
   בהתחלה ניסינו להכניס מוטציה מסוג קרוס אובר עצמי של פרטים, ללא תוצאות טובות יותר.
   לבסוף, הגענו לפתרון מספק לבעיה בעזרת הוספת מוטציה של גידול עץ חדש מקודקוד רנדומלי. בשיטה זו המקרים בהם לא הגענו כלל לתוצאה כמעט ונעלמו.
   הרצה לדוגמא: קצב מוטציה 0.05, שאר הפרמטרים זהים:
   
   

הכללת הבעיה

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

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

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

זמן חישוב פונקצית ה-Fitness הוכפל פי 4 והפך את ריצת התוכנית לאיטית ביותר, לכן הוספנו יכולת Cache לפונקציה. שיפור זה קיצר את זמן הריצה באופן משמעותי.

הגדרות הריצה:
קצב קרוס-אובר: 0.8
קצב מוטציה: 0.05
גודל אוכלוסיה: 100
גודל עץ התחלתי מקסימלי: 2
צעדים לכל רובוט: 300
מספר דורות: 50

גרף הריצה:

מוצגות חמשת התוכניות הטובות (מתאימות) ביותר בחמישה דורות:

הפרט המתאים ביותר בדור 0:

S11

הפרט המתאים ביותר בדור 15:

(IFLTE S0 (PROGN2 (IFBMP S7 MF) (IFLTE S4 S9 S11 TR0)) TR0 (PROGN2 S10 (PROGN2 (PROGN2 S7 S11) (IFLTE S2 S4 S4 MF))))

הפרט המתאים ביותר בדור 23:

(IFSTK (IFLTE (IFLTE TL0 S9 S3 S7) (IFSTK S11 S8) (IFLTE (PROGN2 (PROGN2 S3 S6) (IFSTK (IFLTE (IFLTE TL0 S9 S4 S7) (IFSTK S11 S8) (IFLTE (PROGN2 (PROGN2 S3 S6) (IFSTK MF (PROGN2 S11 TR0))) TL0 S2 MF) S0) S7)) TL0 S2 S1) (IFSTK TL0 (IFBMP MF S4))) MF)

הפרט המתאים ביותר בדור 28:

(IFSTK (IFLTE MF (IFSTK S11 S8) (IFLTE (PROGN2 (PROGN2 S3 (IFBMP S1 S11)) (IFSTK (IFLTE (IFLTE TL0 S9 S4 S7) (IFSTK S11 S8) (IFLTE (PROGN2 (PROGN2 S3 S6) (IFSTK (IFBMP (IFBMP S5 MF) (IFSTK S4 S0)) (IFSTK TL0 S0))) TL0 S2 MF) S0) S7)) TL0 S2 S1) (IFSTK TL0 (IFBMP MF S4))) MF)

הפרט המתאים ביותר בדור 49:

(IFSTK (IFLTE MF (IFSTK S11 S8) (IFLTE (PROGN2 (PROGN2 S3 (IFBMP S1 S7)) (IFSTK (IFLTE (IFLTE TL0 S9 S4 S7) (IFSTK (IFSTK (IFLTE (IFLTE TL0 S9 S4 S7) (IFSTK S11 S8) (IFLTE (PROGN2 (PROGN2 S3 S6) (IFSTK (IFBMP (IFBMP S5 (IFLTE TL0 S9 S4 S7)) (IFSTK (PROGN2 (PROGN2 S3 (IFBMP S3 MF)) (IFSTK (IFLTE TL0 S9 S3 (IFLTE (IFLTE TL0 S9 S4 S7) (IFSTK S11 S8) TL0 S0)) S7)) S0)) (IFSTK S4 S0))) TL0 S2 MF) S0) S7) S8) TL0 S0) S7)) TL0 S2 S1) (IFSTK TL0 (IFBMP MF S4))) MF)

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

צמצום גודל התוכנית

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

הרצה של התוכנית בתנאים אלו הניבה את הגרף הבא:



ניתן לראות כי שיפורים בביצוע המשימה של הרובוט גררו עליות באורך התוכנית, שלאחר מכן הצטמצמו באיטיות לעבר תוכנית קצרה או "נקייה" יותר.
משחקים נוספים בפקטור הגודל הביאו אותנו לבחירה בפקטור הבא: (100\מספר הקודקודים)-4
בהרצה זו מצאנו את התוכנית הקצרה ביותר שלנו, שאורכה 15 קודקודים:

(PROGN2 (IFLTE (IFLTE MF S0 (IFSTK TR0 S0) S10) S3 S0 (PROGN2 S8 TR0)) S10)

סיכום

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

נקודות מעניינות:

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