מקרה פרטי של רובוט נקודתי

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

נתבונן במקרא פרטי של רובוט – רובוט נקודה.
ואז נצטרך לפתור בעיית תכנון תנועה של נקודה ב Cfree (R, S),במקרא הזה Configuration Space Work Space זהים.
כדי לעשות זאת נבנה מבנה נתונים שישמור את ההצגה של Cfree (R, S), ואז בעזרת מבנה נתונים זה נוכל למצוא מסלול בין שני נקודות כלשהם(נק' מוצא ונק' סיום). ואז נוכל להשתמש מס' רב במבנה נתונים זה כדי למצוא מסלולים עבור רובוט.
כדי להקל על היצוג של מבנה נתונים נוסיף מלבן B שיהיה מכשול נוסף של שטח אינסופי מחוץ ל-B. כאשר B מספיק גדול ומכיל את כל המכשולים. ואז נקבל ש- Cfree (R, S)שווה ל-
Cfree (R, S) = B \ Cforb (R, S).

ואז אבנה מבנה נתונים בצורה הבא:
1. נבנה מפת טרפזים – T(E), כאשר E היא קבוצת כל סגמנטים של המכשולים.
ניתן לעשות זאת ב O(nlogn) expected time. כאשר n מספר הסגמנטים.
2. נזרוק את הטרפזים הנמצאים בתוך המכשולים. זה ניתן לעשות בזמן O(n). ונקבל מפת טרפזים של Cfree (R, S) – ונקרא לה T(Cfree (R, S)).
אחרי זה נבנה גרף מישורי, Road Map – המבוסס על מפה T(Cfree (R, S))..
נעשה זאת בדרך הבא:
1. ניצור צומת במרכז כל הטרפז מתוך T(Cfree (R, S)).
2. ניצור צומת באמצע של כל קו אנכי בתוך T(Cfree (R, S)).
3. ניצור קשתות המקשרות בין הצמתים באמצע של טרפז לבין צמתים(לכל היותר 4) הנמצאים על הסגמנטים האנכים של אותו טרפז.
בנית Road Mapתיקח O(n) זמן ע"י DCEL של T(Cfree (R, S)).
האלגוריתם למציאת מבלול תנועה עבור רובוט נקודה
ועכשיו כדי לענות על שאלת תכנון תנועה לרובוט נקודתי, בהינתן pstart וpgoal.
1. נמצא טרפזים שבהם נק' אלו מוכלים.
2. נקשר בין מרכזי הטרפזים לבין הנקודות אלו בקווים ישרים.
3. נחפש מסלול בין שני מרכזי טרפזים אלו בעזרת BFS – אלגוריתם לחיפוש מסלולים בתוך גרפים מישוריים, בעל סיבוכיות ליניארית בגודל הגרף.
ברור שאלגוריתם הנ"ל נכון, כיוון שאם קיים מסלול ללא מכשולים אז האלגוריתם ימצא את הטרפזים בהם נמצאות נקודות אלו. מסלול ביניהם עובר דרך מס' טרפזים שכנים, ולכן יש להם אנך משותף שבמרכזו בנינו צומת של הגרף ולכן יש מסלול גם בגרף שבנינו ולכן BFS ימצא את המסלול
וכל מסלול שאלגוריתם מדווח יהיה מסלול חוקי - ללא מכשולים. ניתן לראות את אופן עבודת האלגוריתם בתמונה למטה.

ננתח את סיבוכיות האלגוריתם לבניית מבנה נתונים ולמציאת מסלול עבור הרובוט:
זמן בנית מפת טרפזים – T(E) : Expected O(nlogn)
זמן בניה של Road Map – O(n).
ולכן סה"כ סיבוכיות לבניית מבנה נתונים שלנו תהיה O(nlogn) expected time.
ולמצוא מסלול מנק' pstart וpgoal כלשהם, בעזרת BFS יעלה O(n), כיוון שגרף מישורי שאנו נבנה - Road Map בעל O(n) צמתים והוא גרף מישורי.

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