reala10n/car-pathfinding-problem

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

תכנון מסלול עבור רכב אוטונומי בחנייה

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

תקציר המחקר

הבינה המלאכותית, ובפרט המכוניות האוטונומיות, הוא תחום רחב וחשוב מאוד שתופס תאוצה רבה בעשור האחרון, וחשיבותו ברורה מאליו. טכנולוגיות אלו גם שוות לא מעט כסף: נכון לרגע כתיבת שורות אלו, חברת ייצור ופיתוח הרכבים האוטונומיים המתקדמת בעולם טסלה שווה למעלה מ־640 מיליארד דולר, בעוד ששווין של חברות וותיקות בתחום כמו BMW או Mercedes-Benz עומד על 54 ו־79 מיליארד דולרים בלבד. גם חברת מובילאיי הישראלית, המפתחת מערכות ראיה ממחושבות ובינה מלאכותית למכוניות, נמכרה בשנת 2017 לחברת אינטל תמורת 15.3 מיליארד דולרים.

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

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

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

ההשוואה בין האלגוריתמים בוצעה על ידי שני פרמטרים – "זמן" ריצת האלגוריתם, ואורך הדרך שנמצאה (אם בכלל נמצאה דרך). תוצאות המחקר הראו כי לכאורה אלגוריתם ה־A* הוא האלגוריתם המתאים והמהיר ביותר לבעיה, שכן הדרך שנמצאה בעזרתו היא הדרך הקצרה ביותר, וגם "זמן" הריצה שלו טוב ביחסית לשאר האלגוריתמים. למרות זאת, אלגוריתם ה־ RRT(Rapidly-exploring Random Tree), שנפוץ ונהוג לשימוש בבעיות "צפופות" (עם מכשולים רבים) או בבעיות רב ממדיות דווקא כשל עם 48% הצלחה בלבד.

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

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

לעיון במחקר המלא לחץ כאן.

car-pathfinding-problem's Issues

Improving edges and nodes

Improve the edge and node algorithm: create a new container object and generate all of the edges in the graph. each time a new obstacle is created, make the check every edge and mark if it is legal or not.

Adding a graph to show every explored and queued point in the search

Create a main running class

Use the listdlg function to choose an algorithm, then enter the number of the obstacles using inputdlg, and mark the obstacles and start and end points on the graph using ginput function

Creating the configuration space

Solve the problem in a way more efficient way by creating a configuration space.

Questions that need answers:

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

In a queue object, the pulled list has duplicated values.