برنامه‌ریزی حرکت

برنامه‌ریزی حرکت (نام دیگر ، «مشکل ناوبری»، مسئله «حرکت دهنده پیانو»)اصطلاحی است که در رباتیک به فرایند جزئی‌سازی کاری، درقالب حرکت‌های جداگانه و گسسته اطلاق می‌شود.
به عنوان مثال، هدایت رباتی سیار در داخل یک ساختمان به سمت هدفی دور را، در حالی که باید از دیوارها بدون برخورد عبور کند و مراقب پایین افتادن از پله‌ها باشد، درنظر بگیرید. الگوریتم برنامه‌ریزی حرکت این وظایف جداگانه را به عنوان ورودی می‌گیرد، فرمان سرعت و چرخش چرخ‌ها را تولید می‌کند و به ربات ارسال می‌کند. الگوریتم‌های برنامه‌ریزی حرکت ربات ممکن است با تعداد بیشتری از مفاصل (به عنوان مثال بازوهای صنعتی)، وظایفی پیچیده‌تر (به عنوان مثال دستکاری اشیاء)، محدودیت‌های مختلف (به عنوان مثال یک ماشین که فقط به جلو می‌تواند برود)، و عدم قطعیت (به عنوان مثال مدل ناقص محیط یا ربات) روبرو باشند.
برنامه‌ریزی حرکت دارای کاربردهای رباتیکی زیادی از قبیل خودمختاری، خودکارسازی، نرم‌افزار طراحی به وسیله کامپیوتر و نیز برنامه‌های کاربردی در زمینه‌های دیگر مانند پویانمایی شخصیت‌های دیجیتال، طراحی معماری، جراحی رباتیک و مطالعه مولکول‌های زیستی می‌باشد.
مفاهیم
نمونه‌ای از فضای کاری.
فضای پیکربندی رباتی به اندازه نقطه. سفید= C free ، خاکستری=C obs
فضای پیکربندی رباتی با حرکات مستطیل شکل (به رنگ قرمز). سفید= C free ، خاکستری= C obs ، خاکستری تیره = اشیاء، خاکستری روشن = فضایی که ربات ممکن است در آن با اشیاء برخورد.
نمونه‌ای از مسیر معتبر.
نمونه‌ای از مسیر نامعتبر.
نمونه‌ای از نقشه راه.
مسئله‌ی اصلی برنامه‌ریزی حرکت، تولید یک حرکت مداوم است که پیکربندی شروع S را به پیکربندی هدف G متصل کند، در حالی که از برخورد با موانع شناخته شده اجتناب کند. هندسه‌ی ربات و موانع، در فضای کاری ۲ یا ۳ بعدی تعریف می‌شود. در حالی که حرکت، بعنوان یک مسیر (احتمالا در ابعاد بالاتر) در فضای پیکربندی تعریف می‌شود.
فضای پیکربندی
یک پیکربندی، مکان روبات را تشریح می‌کند و فضای پیکربندی C، مجموعه تمام پیکربندی‌های ممکن آن(تمام نقاطی که روبات امکان دستیابی به آنها را دارد)می‌باشد.
برای مثال :
اگر ربات یک نقطه(بااندازه صفر) در صفحه ۲ بعدی باشد(فضای کار)،C یک صفحه می‌باشد و پیکربندی می‌تواند با استفاده از دو پارامتر(x،y) بیان شود.
اگر ربات شی‌ای ۲بعدی باشد و بتواند حرکت و چرخش کند، فضای کار هنوز ۲ بعدی محسوب می‌شود با این حال،C گروه اقلیدسی خاصی به شرح زیر است: (که (S0(2 یک گروه متعامد خاص، از حرکتهای دوبعدی می‌باشد)واین پیکربندی می‌تواند با 3 پارامتر (x, y, ) نمایش داده شود.
اگر ربات جسمی 3 بعدی باشد که می‌تواند حرکت و چرخش کند، فضای کار 3 بعدی است.اما C گروه اقلیدسی خاصی به شرح زیر است:
و برای توصیف پیکربندی به 6 پارامتر احتیاج است:(x, y, z):برای توصیف حرکت و (, , ):برای زوایای اویلری.
اگر ربات با پایه ثابت با N مفصل پیچیده(بدون حلقه‌های بسته)باشد، آنگاه C، از N بعد خواهد بود.
فضای آزاد
به مجموعه‌ای از پیکربندی‌ها که از برخورد با موانع جلوگیری میکنند، فضای خالی(C free )می گوییم.
مکمل C free را C، موانع یا منطقه‌های ممنوعه، می‌نامیم.
اغلب محاسبه شکل C free بسیار دشوار است، با این حال، آزمایش اینکه آیا یک پیکربندی داده شده در C free می‌باشد یا نه، کارآمد می‌باشد. ابتدا با استفاده از کینماتیک به جلو، موقعیت هندسه ربات تعیین می‌شود و نمایانگر برخورد، برخورد موقعیت هندسی ربات با محیط را بررسی می‌کند.
فضای هدف
فضای هدف یک زیر فضا از فضای آزاد است که ما می‌خواهیم ربات به آن جا برود. در برنامه‌ریزی حرکت جهانی (عمومی) فضای هدف مشاهده پذیر است. در حالی که در برنامه زیر حرکت محلی ممکن است فضای هدف مشاهده نشود. جهت حل مشکلات ناشی از مشاهده ناپذیری، چندین فضای هدف مجازی به نام فضای زیر هدف فرض می‌شود که در محل مشاهده پذیر واقع شده‌اند (پیرمامون ربات).
الگوریتم‌ها
مسائلی با ابعاد پایین، بوسیله الگوریتم‌های مبتنی بر شبکه، که این الگوریتم‌ها با استفاده از متصور شدن شبکه‌ای بر بالای فضای پیکربندی انجام می‌شوند، قابل حل هستند.این مسائل همچنین با استفاده از الگوریتم‌های هندسی که شکل و همبندی سی را محاسبه می‌کنند، قابل حل هستند.
برنامه‌ریزی حرکت دقیق برای سیستم‌هایی با ابعاد بالاتر، تحت محدودیت‌ها و موانعی پیچیده، از لحاظ محاسباتی، مسئله‌ای رام نشدنی است. الگوریتم‌های میدان پتانسیل کارآمد هستند، اما این الگوریتم‌ها در کمترین مقدارهای ممکن محلی(local minima)، ناکارآمد هستند.الگوریتم‌های مبتنی برنمونه‌گیری از مشکل افتادن در مینیمم‌های محلی اجتناب می‌کنند و بسیاری از مسائل را نسبتا سریع حل می‌کنند. با این حال، این الگوریتم‌ها قادر به تعیین این که هیچ راهی وجود ندارد نیستند، اما می‌توانند احتمال شکست در یافتن راه را محاسبه کنند که با سپری شدن زمان بیشتر، احتمال شکست را به صفر کاهش می‌دهند.
در حال حاضرالگوریتم‌های مبتنی بر نمونه گیری به روزترین و بهترین الگوریتم‌های برنامه ریزی حرکت برای فضاهایی با ابعاد بالا می‌باشند و حتی برای مسائلی با ده‌ها یا صدها بعد، قابل پیاده سازی می‌باشند (مانند: بازوهای رباتیکی، مولکول‌های زیستی، انیمیشن کاراکترهای دیجیتال، روبات‌های دارای پا وغیره).
جستجوی شبکه‌ای
الگوریتم‌های مبتنی بر شبکه معمولا شبکه‌ای را به صورت فرضی روی فضای پیکربندی قرار می‌دهند و فرض می‌کنند که هر پیکربندی با نقطه‌ای از نقاط شبکه مشخص می‌شود. در هر نقطه از این شبکه، ربات اجازه حرکت به نقطه مجاور را دارد به طوریکه خط بین نقطه شروع و پایان داخل C free باشد(این مسئله با استفاده از تشخیص برخورد، آزمایش می‌شود). مجموعه‌ی این اعمال به همراه الگوریتم‌های جستجو(مانند A*) می‌توانند مسیری از مبدا به سمت هدف را بیابند.
این روش‌ها نیاز به تفکیک شبکه‌ای دارند. جستجو با شبکه‌های ضخیم‌تر، سریع‌تر می‌شود، اما در این حالت الگوریتم موفق به پیدا کردن مسیر از میان بخش‌های باریک C free نمی‌شود.علاوه بر این، تعداد نقاط روی شبکه، در ابعاد فضای پیکربندی، رشد نمایی دارد که آنها را برای مسائلی با ابعاد بالا ناکارآمد می‌کند.
روش‌های سنتی مبتنی بر شبکه، مسیرهایی تولید می‌کنند که جهت تغییرات مسیر آنها محدود به مضاربی از زاویه‌ی اولیه‌ی داده شده می‌باشد.این روش‌ها اغلب منجر به ایجاد مسیرهایی می‌شوند که به طور جزئی بهینه هستند(solution suboptimal).هر کدام از روش‌های برنامه ریزی مسیر مبتنی بر زاویه، بدون اینکه مسیرشان را محدود به اضلاع شبکه کنند، مسیرهای کوتاه‌تری را با انتشار دادن اطلاعات در امتداد اضلاع شبکه پیدا می‌کنند.
روش‌های مبتنی بر شبکه اغلب نیاز به جستجوی مداوم دارند، به عنوان مثال، زمانی که شناخت روبات از فضای پیکربندی تغییر کند یا خود فضای پیکربندی با پیدا کردن مسیرهایی تغییر کند.
الگوریتم‌های جستجوی افزایشی اکتشافی، با استفاده از تجربه سایر مسائل مشابه برنامه‌ریزی مسیر-که قبلا حل شده‌اند- با سرعت بالایی حرکت را برای مورد فعلی، برنامه‌ریزی می‌کنند.
الگوریتم‌های هندسی
این الگوریتم‌ها مبتنی بر یکی از 2 حالت زیر می‌باشند:
- نمایش ربات در میان موانع چند ضلعی
گراف قابل رویت بودن
تجزیه المانی
- تعریف اشیا در میان موانع
جمع مینکوسکی
الگوریتم‌های پاداش محور
در الگوریتم‌های پاداش محور فرض می‌شود ربات در هر حالت (موقعیت و حالت درونی) می‌تواند بین اعمال (حرکت) مختلف انتخاب کند. اگر چه نتیجه عمل به طور دقیق مشخص نیست. به عبارت دیگر درآمد پاره‌ای مبتنی بر تصادف و پاره مبتنی بر انتخاب ربات است. ربات وقتی به هدف می‌رسد پاداش مثبت دریافت می‌کند و وقتی به مانع برخورد می‌کند پاداش منفی می‌گیرد. این سری از الگوریتم‌ها درصدد یافتن مسیری هستند که مجمموع پاداش‌های آتی را بیشینه نماید. فرایند‌های تصمیم گیری مارکوف یک چارچوب ریاضی بسیار معروف است که در بسیاری از الگوریتم‌های پاداش محور استفاده می‌شود. مزیت استفاده از فرایند‌های تصمیم گیری مارکوف نسبت به سایر الگوریتم‌های پاداش محور این است که مسیر بهینه را مشخص می‌کند. عیب فرایند‌های تصمیم گیری مارکوف این است که ربات را به انتخاب عمل در بین مجموعه‌ای متناهی از اعمال محدود می‌کند و بنابراین مسیر نرم (هموار) نیست. فرایند‌های تصمیم گیری مارکوف فازی یک بسط (توسعه) بر فرایند‌های تصمیم گیری مارکوف است که با کمک سیستم‌های استنتاج فازی مسیر را هموار می‌کند
میدان‌های پتانسیل
یک روش برای برنامه ریزی حرکت، فرض کردن ربات به عنوان نقطه‌ای داخل میدانهای پتانسیل است. این روش کشش به سمت هدف و دافعه از موانع را با هم نرکیب میکند. خط سیر نهایی، خروجی به عنوان مسیر مدنظر میباشد. این روش با توجه به اینکه خط سیر با محاسبه کمی بدست می‌آید، مفید واقع می‌شود.اگرچه، این الگوریتم‌ها می‌توانند در مینیمم‌های محلی میدانهای پتانسیل به دام بیفتند و موفق به پیدا کردن مسیر نشوند. میدان پتانسیل می‌تواند به طور مستقیم از یک فرمول ریاضی (مانند میدان الکترواستاتیک) یا به کمک مجموعه‌ای از قوانین زبانی به دست آید
الگوریتم‌های مبتنی بر نمونه گیری
الگوریتم‌های مبتنی بر نمونه گیری، فضای پیکربندی را با نقشه راهی از پیکربندی‌های از قبل نمونه گیری شده، نمایش می‌دهند.یک الگوریتم ابتدایی، N پیکره بندی را در فضای C نمونه گیری می‌کند و آن‌ها را در C free ، برای استفاده به عنوان نمونه شاخص نگه می‌دارند. سپس نقشه راه به گونه‌ای ساخته می‌شود که دو شاخص P و Q را، درصورتیکه بخش PQ کاملا درون C free باشد، بهم متصل می‌کند. آنگاه الگوریتم تشخیص دهنده برخورد ،C free را برای وجود برخورد بازبینی می‌کند. برای پیدا کردن مسیری که S و G را بهم متصل میکند، آنها نیر به نقشه راه، افزوده می‌شوند. اگر مسیر نقشه راه، بتواند G و S را بهم مرتبط کند، برنامه ریزی حرکت، موفق بوده است و و این مسیر را برمی گرداند. اگر جواب مثبتی پیدا نشود یا نمونه برداری کافی نیست یا راهی وجود ندارد.
این الگوریتم‌ها درفضای پیکربندی با ابعاد بالا بسیار خوب کار می‌کنند، چرا که بر خلاف الگوریتم‌های ترکیبیاتی، زمان اجرای آنها بطور توانی، وابسته به ابعادفضای پیکره بندی C نیست و همچنین دارای پیاده سازی اساسا ساده‌تری نیز می‌باشند.این الگوریتم‌ها از نظر احتمالی کامل هستند یعنی احتمال یافتن راه حل مسئله توسط این الگوریتم‌ها با گذر زمان به ۱ نزدیک می‌شود. با این حال، آنها نمی‌توانند عدم وجود راه حل برای مسئله را تعیین نمایند.
اثبات شده است که با داشتن موقعیت‌های میدان دید در C free ، هنگامیکه تعداد پیکربندی‌های N افزایش می‌یابد، احتمال ابنکه الگوریتم ذکر شده راه حلی را بیابد، به طور توانی به ۱ نزدیک می‌شود.
میدان دید بطور صریح وابسته به ابعاد C نمی‌باشد.یعنی ممکن است که فضایی در ابعاد بالا با میدان دید خوب یا در ابعاد پایین با میدان دیدی ضعیف داشت. نتایج تجربی روش‌های مبتنی بر نمونه گیری، نشان می‌دهند که فضاهایی که بطور معمول، بیشتر دیده میشوند، میدان دید خوبی نیز دارند.
بازدهی و پیچیدگی
به یک برنامه ریز حرکت در صورتی کامل گفته می‌شود که همیشه زمانیکه مسیری درحالت کلی وجود دارد، یک مسیر ممکن را به درستی تولید کند. بیشتر الگوریتمهای کامل، مبتنی بر هندسه هستند. کارایی برنامه ریزهای کامل توسط نظریه پیچیدگی محاسباتی ارزیابی می‌شود.
کامل بودن از لحاظ تفکیک پذیری عامل دیگری است، بدین سان که اگر تفکیک پذیری شبکه‌ای که درنظر گرفته شده، به اندازه کافی ظریف باشد، یافتن مسیر توسط برنامه ریز حرکت، تضمین می‌شود.بیشتر برنامه ریزهایی که از لحاظ تفکیک پذیری کاملند، مبتنی بر شبکه می‌باشند. پیچیدگی محاسباتی این گونه برنامه ریزها وابسته به تعداد نقاط شبکه‌ای است که برای الگوریتم آن درنظر گرفته شده است.که این پیچیدگی
(O(1/h d خواهد بود که h تفکیک پذیری(طول یکی از اضلاع سلول شبکه) و d بعد فضای پیکر بندی می‌باشد.
کامل بودن احتمالاتی نیز ویژگی دیگری است بدین سان که احتمال اینکه برنامه ریز نتواند مسیری را پیدا کند(با اینکه مسیری وجود داشته)، درحالیکه کار بیشتری درحال انجام است، بطور مجانبی به صفر نزدیک میشود.کارایی برنامه ریزی که این ویژگی را دارد، با استفاده از میزان همگرایی، اندازه گیری می‌شود.
برنامه ریزهای ناکامل همواره مسیری ممکن(وقتی مسیری وجود دارد) را تولید نمی‌کنند. اما گاهی برنامه ریزهای ناکامل نیز در عمل بسیار خوب عمل میکنند.
کاربرد‌ها
Robot navigation
خودکارسازی
The driverless car
Robotic surgery
Digital character animation
تاشدگی پروتئین
Safety and accessibility in computer-aided architectural design
مرتبط
برنامه ریزی دینامیک جنبشی (Kinodynamic planning)
مسئله کوهنوردی (Mountain climbing problem)
مانع سرعتی (Velocity obstacle)