אוניברסיטת תל אביב|בית הספר למדעי המחשב
פרופ’ דן הלפרין חי עם בן זוגו ובתו בתל אביב. בזמנו הפנוי אוהב לנגן ולהאזין למוזיקה.
רובוטים צריכים להיות מסוגלים לנוע עצמאית, לחוש ולשנות את הסביבה, וזאת מבלי להתנגש באובייקטים שנמצאים סביבם. ככל שהרובוטים רבים יותר, המשימות הללו הופכות מורכבות יותר. הרובוטים נדרשים להימנע מהתנגשות זה בזה, גם כשהם נדרשים לבצע פעילות יחד, כשהם קרובים מאוש זה לזה, למשל, כדי להרים חפץ כבד. כיום, השימוש בקבוצות של רובוטים הולך ונעשה נפוץ ונחוץ יותר, ולפיכך נדרשות שיטות שיגרמו להם לפעול יחדיו בתיאום וביעילות.
רובוטיקה מתבססת על מגוון תחומים, שאחד מהם הוא גיאומטריה חישובית – תחום במדעי המחשב שעוסק בפיתוח אלגוריתמים לפתרון בעיות גיאומטריות. למעט רובוטיקה, הוא מיושם בתחומים רבים נוספים ובהם ראייה ממוחשבת, מערכות מידע גיאוגרפיות והנדסה אזרחית (כך למשל אפשר לתכנן רישות יעיל של מבנים ושטחים במצלמות, משדרים ואנטנות.
“גיאומטריה חישובית התפתחה לצד המחקר ברובוטיקה והתחומים הללו משפיעים מאוד זה על זה. כך למשל, באמצעות אלגוריתמים גיאומטריים אפשר למפות שטחים, לחלקם לאזורים, להציב אובייקטים בנקודות אסטרטגיות ולקבל החלטות תנועה. ואם רוצים, למשל, שרובוט ינוע במסלול הקצר ביותר, ישיג את המטרה ויתרחק ממכשולים, בונים אלגוריתם גיאומטרי שמיתרגם לפקודות שמסייעות לו לעשות זאת”, מסביר פרופ’ דן הלפרין מבית הספר למדעי המחשב באוניברסיטת תל אביב.
פרופ’ הלפרין עוסק בגיאומטריה חישובית, מפתח אלגוריתמים גיאומטריים והיה שותף בפרויקט אירופי לייצור תוכנות למימושם (The Computational Geometry Algorithms Library – CGAL). באחד ממחקריו האחרונים, שזכה במענק מחקר מהקרן הלאומית למחקר, ואשר הוצג בכנס מרכזי ברובוטיקה ICRA) 2021) בסין, פיתח יחד עם צוותו ובשיתוף חוקרים מאוניברסיטת סטנפורד אלגוריתמים לקבוצות של רובוטים. לדבריו, “אנחנו יודעים לתכנן אלגוריתמים לרובוט בודד, שגורמים לו לנוע ביעילות, אבל קשה יותר לבנות אלגוריתמים שיגרמו לכמה רובוטים לנוע יחדיו באופן תקין, להיות מתואמים ולשתף פעולה. ככל שיש יותר רובוטים וככל שסביבת העבודה צפופה יותר (כשהרובוטים קרובים מאוד זה לזה ולמכשולים) – הקושי החישובי גדול יותר. אבל זה חיוני, כיוון שהשימוש בצי של רובוטים, ביישומים מסחריים ואזרחיים, הולך וגדל. כך למשל הוא מיושם במחסני ענק כמו אלה של אמזון, מפעלי תעשייה שונים, אזורי אסון, ו’להקות’ של רחפנים שמבקרות מבנים גדולים וגשרים ומגנות על שמורות טבע. באמצעות צי של רובוטים אפשרת להשיג מטרות הרבה יותר מהר, להיות יעילים וחסכוניים”.
האלגוריתמים הגיאומטריים שפיתחו פרופ’ הלפרין ותלמיד המחקר דרור דיין, בשיתוף עם פרופ’ מקרו פבונה מאוניבסיטת סטנפורד ופרופ’ קיריל סולוביי מהטכניון, הם מבוססי דגימה (דוגמים מצבי תנועה אפשריים של הרובוטים ומחליטים אם הם חוקיים. כלומר, אם הם מונעים מהרובוטים להתנגש במכשולים וזה בזה), ומתכננים תנועה משותפת של קבוצות רובוטים. ייחודם בכך שהם מבטיחים את איכות המסלולים של הרובוטים תוך שימוש במספר דגימות תנועה ידוע מראש.
“אנחנו יודעים בדיוק כמה דגימות צריך בשביל לקבל רמת אופטימליות מסוימת”, מסביר פרופ’ הלפרין. בעזרת האלגוריתמים בונים החוקרים מפת דרכים שמקרבת את כל התצורות החוקיות במסלול. מפה כזאת משורטטת לכל רובוט בנפרד ולאחר מכן כל המפות, של כל הרובוטים, נתפרות יחדיו. התפירה מאפשרת להניע את כל הרובוטים יחדיו, במקביל, בלי שייתקלו במכשולים וזה בזה. השיטה פועלת בכל ממד, וכך יעילה גם עבור רובוטים עם דרגות חופש תנועה רבות.
החוקרים יישמו את האלגוריתמים בתוכנה שמדמה פעולה של כמה רובוטים במקביל וגילו שגם במצבים צפופים הם מביאים לפתרונות אופטימליים כמעט. כך למשל הם הצליחו לנוע מנקודה לנקודה בחדר קטן מאוד (יחסית לגודלם ומספרם של הרובוטים) או להחליף מקומות מבלי להתנגש ביניהם ובמכשולים נוספים. לדברי פרופ’ הלפרין, “בניסויים השוואתיים עם השיטות העדכניות ביותר ברובוטיקה, ראינו כי השיטה החדשה היא היחידה שמתקרבת לפתרונות אופטימליים בסביבות צפופות. נדרשים אמנם עוד מחקרים שיבחנו אותה, אבל כבר כעת אפשר לראות שנקודת המוצא שלה טובה יותר מזו של השיטות הקיימות”.