طراحی مسیر هولونومیک جهت عبور از گذرگاه های باریک و موانع مقعر به کمک الگوریتم درخت جستجوی سریع تصادفی حریص

یکی از بزرگترین چالش های پیش روی حوزه ربات های بدون سرنشین، مقوله خوداتکایی یا خودمختاری در انها می-باشد. هدف این مقاله پرداختن به مقوله طراحی مسیر جهت تحقق حداقل خودمختاری در ربات مدنظر می باشد. حجممحاسبات و زمان مورد نیاز برای طراحی مسیر با مرتبه ((O(n(۲ در فضاهای کاری با دیمانسیون بالا، تعداد زیاد موانع وقیدهای حرکتی متعدد افزایش مییابد. لذا در این مقاله روش درخت جستجو سریع تصادفی حریص مبتنی بر نمونهبرداری تدریجی افزایشی جهت حل مسئله طراحی مسیر پیشنهاد شده است. ماهیت تصادفی و یا به عبارتی کاملاحتمالاتی بودن روش پیشنهادی فرصت گسترش درخت جستجو در فضای کاری مد نظر با حداقل پیچیدگی محاسباتی رافراهم می آورد، همچنین با اعمال تابع هزینه در انتخاب گرههای والد در درخت جستجو امکان حریص شدن درخت نسبتبه روش استاندارد فراهم میگردد. جهت اعتبار سنجی و اعتبار بخشی به روش پیشنهادی دو سناریو تست متمایز تعریفمی گردد. در سناریو تست اول فضای کاری متشکل از چهار گذرگاه باریک می باشد و در سناریو تست دوم پنج گذرگاه هایباریک در کنار پنج مانع مقعر تشکیل دهنده فضای کاری خواهند بود. در روش های طراحی مسیر کامل متداول درگذرگاه های باریک حجم و زمان محاسبات طراحی مسیر بصورت چشمگیری افزایش می یابد، همچنین گذر از موانع مقعراحتمال قرار گرفتن الگوی طراحی مسیر در مینیم های محلی را افزایش میدهد. نتایج شبیه سازی ها نشان می دهد کهروش تصادفی حریص پیشنهادی در این مقاله به میزان قابل توجه حجم نمونه برداری جهت طراحی مسیر را نسبت بهروش درخت جستجوی سریع تصادفی استاندارد کاهش می دهد و همچنین در مینیم های محلی ناشی از موانع مقعر وگذرگاه های باریک نیز به دام نمی افتد.

کلیدواژه ها:

طراحی مسیر ، برخورد با مانع ، الگوریتم درخت جستجوی سریع تصادفی ، گذرگاه های باریک ، موانع مقعر