سایت درس:
http://gamma.cs.unc.edu/courses/planning-f07/
مرجع درس: LaValle's Book on Planning Algorithms
دانلود کتاب درس و ...
http://planning.cs.uiuc.edu/
ارائه‌ی مورد علاقه‌ی من: Visibility based Motion Planning (Georgi Tsankov , October 10, 2007)
Coverage Planning (Jamie Snape, October 15, 2007)
http://msl.cs.uiuc.edu/~lavalle/papers/TovMurLav07.pdf
http://en.wikipedia.org/wiki/Motion_planning
http://en.wikipedia.org/wiki/Any-angle_path_planning
ویکیپدیا:
http://en.wikipedia.org/wiki/Motion_planning
الگوریتم‌ها:
http://www.mpi-inf.mpg.de/departments/d1/teaching/ss10/Seminar_CGGC/Slides/06_Bazhenova_RMP.pdf
GNT:
http://www.robotoloco.com/wk/papers/TovGuiLav04.pdf
من برای حل سوال ۳ یک راه حلی مثل این مقاله نوشته بودم (از نظر اینکه فاصله دورترین نقطه تا دایره را گرفتم شبیه‌اند). یعنی گفته بودم که دورترین نقطه از P را در جهتی که قطر فعلی توپ محیطی را به دست آورده‌ایم حساب می‌کنیم و فاصله‌ی این نقطه تا دایره طبق عرض جهتی از اپسیلون برابر در هر جهت کمتره.
*روش دو برابر کردن معمولی
تقریب عرض جهتی:
دو نقطه‌ی اول را s و t می‌نامیم. هر بار یک نقطه جدید می‌آید (p) عرض این سه نقطه را حساب می‌کنیم و اگر نقطه جدید از دو برابر نقطه قبلی دورتر بود نقطه جدید را جایگزین قبلی می‌کنیم.
اثبات آن مشابه اثبات الگوریتمی است که دورترین نقطه از یک نقطه را می‌گرفت و سپس دورترین نقطه را از این پاره‌خط به دست می‌آورد. (تقریب ۳) به جز این از نامساوی مثلث استفاده شده است. هر بار به دلیل دوبرابر کردن تقریب نصف می‌شود پس یک تصاعد هندسی با ضریب ۱/۲ داریم.
*روش قبل را با استفاده از توری و دیاگرام ورونوی گسسته حل می‌کنیم. (مینیمم و ماکسیمم نقاط را نگه می‌داریم.)
در ادامه مقاله ایده‌ی الگوریتم ترکیبی قطر (رند کردن جهتی و توری) هم آمده که با دیاگرام ورونوی گسسته برای محاسبه دورترین نقطه به زمان بهتری برای قطر رسیده است.
با استفاده از این روش یک راه کلی ساختن هسته ارائه داده است که یک الگوریتم افزایشی روی تعداد ابعاد است (مثل دیاگرام ورونوی گسسته) که هر بار با استفاده از توری نقاط را روی راستای دورترین دو نقطه تصویر می‌کند. (یعنی قطر فعلی). حداکثر میزان تغییرات مثل قبل به دلیل نصف شدن محدود است.
*بهبود الگوریتم با روش merge and reduce
(با روش رند کردن جهتی اپسیلون-کرنل ساخته می‌شود.)
*روش افزایشی
هر بار یک نقطه را اضافه می‌کنیم و توپ محیطی را حساب می‌کنیم تا شامل همه نقاط شود. این کار را با استفاده از این نکته که هر نقطه جدید حتما روی محیط می‌افتد انجام می‌دهیم.
حالا باید ضریب تقریب آن را به دست بیاوریم. دایره جواب بهینه را در نظر می‌گیریم. فاصله‌ی مرکز دایره i-ام تا نقطه i-ام برابر شعاع دایره i-ام است و اگر آن را امتداد دهیم قسمت دیگر حداکثر سه برابر این قسمت است. می‌دانیم طول وتر از قطر کمتر است پس از اینجا ضریب تقریب ۳/۲ به دست می‌آید.
؟؟ چرا سه نقطه‌ی pi,ci,c(i-1) هم‌خط اند؟
*روش تکراری
یک نقطه دلخواه بر می‌داریم و به مجموعه Q اضافه می‌کنیم. دایره محیطی Q را به دست می‌آوریم و دورترین نقطه به آن از بین نقاط اولیه (به مرکز دایره) را به Q اضافه می‌کنیم و این کار را ادامه می‌دهیم تا توپ شامل همه‌ی نقاط شود.
عمرمون بر فناست اگه اینها رو ندونیم! :)
http://stellar.mit.edu/S/course/6/fa07/6.895/courseMaterial/topics/topic1/lectureNotes/lec13/lec13.pdf
http://stellar.mit.edu/S/course/6/fa07/6.895/courseMaterial/topics/topic1/lectureNotes/lec16/lec16.pdf
http://stellar.mit.edu/S/course/6/fa07/6.895/courseMaterial/topics/topic1/lectureNotes/lec18/lec18.pdf
http://stellar.mit.edu/S/course/6/fa07/6.895/courseMaterial/topics/topic1/lectureNotes/lec15/lec15.pdf
مرجع:
http://stellar.mit.edu/S/course/6/fa07/6.895/materials.html
دلیل اینکه در هندسه محاسباتی پیشرفته است روش‌های merge and reduce و مثل آن است که در این درس آمده است.
http://www.stanford.edu/class/cs224w/index.html
(اولش هندسه محاسباتی مقدماتی هم دارد. شما از بقیه اش بخونید!)
http://people.csail.mit.edu/indyk/6.838/
