I. חיפוש ופתרון בעיות

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

חיפוש בפועל: איך מגיעים מנקודה A לנקודה B

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

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

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

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

בפרק הזה נעסוק בשני סוגים עיקריים של בעיות:

•  חיפוש ותכנון בסביבה סטטית עם "סוכן אחד" בלבד.

•  משחקים תחרותיים עם שני “סוכנים”.

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

בעיית צעצוע: התרנגולת שחוצה את הנהר

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

• ? שועל

• ? תרנגולת

• ? שק מזון לתרנגולות

אבל יש בעיה:

• אם השועל נשאר לבד עם התרנגולת – הוא יאכל אותה.

• אם התרנגולת נשארת לבד עם שק האוכל – היא תאכל את כולו.

שני התסריטים האלה אינם רצויים, כמובן.

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

איך אפשר להעביר את שלושת המטענים לצד השני – בלי שיקרה נזק בדרך?

? גרסה קלה של חידת הסירה

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

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

• ? הרובוט

• ⛵ הסירה

• ? השועל

• ? התרנגולת

• ? שק האוכל

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

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

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

מצבי חידת חציית הנהר

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

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

לכן אפשר לפסול את המצבים הבאים:

•קררק

•קררר

•רקקר

•רקקק

•קררר

•ררקק

(אפשר לבדוק כל אחד מהם אם רוצים לוודא את ההיגיון.)

לאחר סינון המצבים האסורים, נשארנו עם 10 מצבים חוקיים בלבד.

כעת נעבור לשלב הבא:

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

כעת נצייר את המעברים האפשריים בין המצבים.

אפשר היה לצייר חצים עם כיוון – שמצביעים ממצב אחד לאחר – אבל בחידה הזו המעברים הם סימטריים:

אם הרובוט יכול לשוט ממצב קקקק למצב רקרר,

אז הוא גם יכול באותה מידה לחזור מהמצב רקרר אל קקקק.

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

מתוך המצב ההתחלתי קקקק, אפשר לעבור אל ארבעה מצבים חוקיים אחרים:

•רקרק

•רקרר

•ררקר

•רררק

לאחר מכן, נשלים את שאר המעברים האפשריים בין המצבים.

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

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

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

החלק שנשאר הוא טכני לגמרי:

למצוא מסלול חוקי מהמצב ההתחלתי קקקק למצב הסופי רררר. דוגמה למסלול פתרון באיור הבא (שלא צורף כאן) מסומן מסלול כזה:

1. קקקק ← רררק

הרובוט לוקח את השועל והתרנגולת לצד השני.

2. רררק ← קרקק

הרובוט מחזיר את התרנגולת בחזרה לצד הקרוב.

3. קרקק ← רררר

הרובוט לוקח את התרנגולת ואת שק האוכל אל הצד הרחוק.

וזהו – כולם עברו בשלום!

מרחב מצבים, מעברים ועלויות

כדי לנסח בעיית תכנון באופן פורמלי, אנחנו משתמשים במונחים כמו: מרחב מצבים, מעברים, ו-עלויות.

? מונחי מפתח

מרחב המצבים (State Space)

מרחב המצבים הוא אוסף כל המצבים האפשריים. בחידת חציית הנהר, מרחב המצבים כלל עשרה מצבים מותרים – מקקקק ועד רררר (מצבים כמו קררר נפסלו לפי כללי החידה, ולכן לא נכללים במרחב.) בדוגמה של ניווט ממקום A למקום B – מרחב המצבים יכול להיות למשל אוסף של נקודות ציון לפי קואורדינטות (x,y) שאפשר להגיע אליהן מנקודת המוצא. אפשר גם להגדיר סט מוגבל של מיקומים – למשל כתובות רחוב – כדי לצמצם את מספר המצבים האפשריים.

מעברים (Transitions)

מעברים הם תנועות מותרות ממצב אחד לאחר – לדוגמה: מעבר מ־קקקק ל־רקרק. חשוב להבין שמעברים נחשבים רק אם הם מבוצעים בפעולה אחת בודדת. אם נדרש רצף של שלבים (למשל A → C → D → B) – אז זה כבר לא מעבר, אלא מסלול (path).

עלויות (Costs)

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