עמוד ראשי/בינה מלאכותית/המשך/תכנון תנועה/אלגוריתם תכנון תנועה

אלגוריתם תכנון תנועה

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

כשלב ראשון נביעה את משפט הבא:
משפט 7: יהיה R רובוט קמור בעל סיבוכיות קבוע, הנע בין קבוצת מכשולים פוליגונים זרים בפנים שלהם בעלי סה"כ n קשתות. אזי סיבוכיות של Cfree (R, S) יהיה O(n).
הוכחה: קודם כל נשלש את כל את כל המכשולים, ונקבל קבוצה של O(n) משולשים זרים בפנים שלהם.
ואז Cfree(R, S) יהיה משלים של איחוד של C-obstacle של משולשים אלו יוצר את ה-Cforb (R, S), כאשר כמו שראינו קודם C-obstacle של משולשPi נתון ע"י Pi ? (-R). וכיוון שרובוט בעל סיבוכיות קבוע אזי C-obstacle גם כן בעלי סיבוכיות קבוע, ולפי משפט 3, C-obstacle יוצרים קבוצה של פסדודיסקים, ולפי משפט 4 נוכל להסיק שהאיחוד שלהם יהיה O(n). ולכן כיוון שניתן לראות את Cfree (R, S) כמשלים של האיחוד של כל ה- C-obstacle.

ולכן כדי לחשב את Cfree (R, S) יהיה מספיק לחשב את Cforb (R, S). וכמו שקבר ראינו
n n
Cforb = U CPi = U (Pi ? (-R(0,0))
I=1 I=1

כאשר Pi זהו משולשים שהתקבלו משילוש של מכשולים מקבוצה S. ו- CPi זהו C-obstacle של משולש Pi
ועכשיו כדי למצוא את Cforb (R, S) נשתמש באלגוריתם לחישוב של Minkowski Sum של שני פוליגונים קמורים, בעזרתו נמצא את Minkowski Sum של R ושל כ"א מהמשולשים שקיבלנו ע"י שילוש של מכשולים. ואז נשאר רק לאחד אותם, נעשה את זה בעזרת אלגוריתם הבא:

אלגוריתם למציאת איחוד של Cforb:
האלגוריתם מבוסס על שיטה הפרד ומשול. ז"א נחשב את האיחוד ברקורסיה, ע"י חלוקת קבוצת המכשולים לשניים בכל צד של רקורסיה ואחוד של תוצאות הרקורסיה. ולכן הפעולה העיקרית במהלך הרקורסיה היא חישוב של איחוד של שני Cforb, האיחוד ניתן לחישוב בזמן O(nlogn), כאשר שני ה-Cforb מוצגים כ DCEL, ואז נשתמש באלגוריתם למציאת overlay של שני מפות, שרץ O(nlogn) זמן.
סיבוכיות האלגוריתם היא:
T(n) = T(n/2) + T(n/2) + O(nlogn), בגלל שכ"א מ- Cforbבעל סיבוכיות O(n), זה נובע ממשפט 7, וכיוון שהאיחוד של Cforb זהו איחוד של Minkowski Sum גם הוא בעל סיבוכיות O(n).
ולכן סיבוכיות היא O(nlog2n).

בעזרת האלגוריתם והמשפט האחרון נוכל להוכיח משפט הבא:
משפט 8: ניתן לחשב את ה - Cfree (R, S), כאשר R-רובוט קמור, ו-S קבוצת מכשולים פוליגונים בעלי סה"כ n צמתים בזמן O(nlog2n).
הוכחה: כדי למצוא את Cfree (R, S) נמצא את Cforb בעזרת אלגוריתם האחרון, ואז נימצא את המשלים.
אנו יודעים שפוליגון עם m צמתים ניתן לשילוש בזמן O(mlogm), ולכן שילוש של כל המכשולים ניתן לבצעה בזמן:
t t
? mi logmi ? ? mi logn = nlogn
I=1 I=1
כאשר mi זהו גודל של מכשול Pi.
חישוב של C-obstacle של כ"א מהמשולשים האלו לוקח סה"כ זמן ליניארי.
ואלגוריתם הקודם לחישוב איחוד של Cforb לוקח זמן O(nlog2n).
מציאת המשלים נעשה בזמן לינארי.
ולכן סה"כ סיבוכיות של מציאת Cfree (R, S) לוקח סכום של כל הזמנים האלו והוא O(nlog2n).

הראנו כרגע אלגוריתם למציאת Cfree (R, S) ע"י מציאת Cforb בזמן O(nlog2n). ומכאן ניתן להשתמש באלגוריתם לפתרון בעיית תכנון תנועה עבור רובוט נקודתי, ז"א נבנה מפת טרפזים עבור Cfree (R, S), נבנה גם road map ונמצא בה מסלול בין שני נקודות הרצויות בזמן O(n) בדיוק כמו קודם.
מזה נובע משפט הבא:

משפט 9: יהיה R רובוט קמור בעל סיבוכיות קבוע, הנע ע"י טרנספורמציות בין קבוצת מכשולים פוליגונים זרים בפנים שלהם בעלי סה"כ n קשתות. נוכל לבנות מבנה נתונים בזמן O(nlog2n) expected שיאפשר לנו למצוא מסלול ללא מכשולים בין שני נקודות(התחלה וסיום) בשביל R בזמן O(n).
הוכחה: נובעת ממה שרשום לעיל.
סיבוכיות: למצוא את Cfree לוקח O(nlog2n).זמן, למצוא את מפת טרפזים(וכתוצאה מזה לבנות את road map) לוקח O(nlogn) expected (O(n2) worst case ), ולכן בניית מבנה נתונים תיקח O(nlog2n) expected. ועבור שאילתה נבצע אותם פעולות כמו עבור רובוט יחידה ולכן זמן ביצוע של שאילתה יהיה O(n).

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