بخشی از مقاله
چکیده
روشهای بسیاری برای مسیریابی ربات با شناخت همزمان مکان و نقشه استفاده شده است، FASTSLAM2.0 که بر پایه ی توزیع ذرات می باشد، یکی از این روشها است و دقت بسیار خوبی نسبت به سایر روشها دارا می باشد، این روش برپایه ی فیلترهای کالمن و زنجیرهی مارکوف میباشد. روشهای بر پایه ی توزیع ذرات از مجموعه مراحلی تشکیل شده اند، براساس شبیه سازیهای انجام شده محاسبه ی وزن ذرات و بروزرسانی نقشه بیشترین زمان را دارا می باشند.
برای کاهش زمان بروزرسانی نقشه از ساختارهای دادهای همچون درخت جستوجوی دودویی استفاده شده است و برای محاسبه ی وزن با توجه به آنکه ذرات موجود در توزیع ذرات و نشانه های مسیر دو مشخصه ی محاسبه ی وزن می باشند و از طرف دیگر با توجه به شرط استقلال در نشانه ها و ذرات در FAST SLAM2.0 ، استفاده نمودن از پردازنده های موازی می تواند مقدار زمان را از واحد ثانیه به میلی و یا میکرو ثانیه تبدیل کند.
در این نوشتار سعی شده است با بیان کلی روش FASTSLAM2.0 و مراحل انجام آن، مقایسه ای میان سرعت انجام محاسبه ی وزن در یک دوره در پردازنده ی مرکزی و پردازنده ی گرافیکی انجام شود و با نتایج به دست آمده با پژوهشی مشابه مقایسه شود. برای بروز رسانی نقشه نیز مقایسه ای میان درخت جستوجوی دودویی و استفاده از فیلترهای کالمن توسعه یافته انجام شده است.
-1مقدمه
حل مسئله مکان یابی در صورت داشتن نقشه بسیار ساده می باشد. همینطور تولید نقشه در صورتی که موقعیت ربات دانسته شود بسیار ساده است. در حالت اول همانند آن است که فردی نقشهای در دست دارد و با استفاده از آن مکان خود را می یابد و در حالت دوم نیز بیان تولید نقشه میباشد که در واقع نقشه شامل مجموعهای از مکانها و مختصات ها می باشد. اما حل این دو مسئله به طور همزمان یعنی شناخت هم زمان مکان و نقشه کاری دشوار به نظر می آید. به این مسئله ی شناخت همزمان مکان و نقشه SLAM1 اطلاق می شود.
اولین تلاشها برای حل این مسئله به [1] و [2] باز می گردد. روش های متنوعی برای حل این مسئله ارائه شده است، روش هایی از قبیل گام شماری2،روشEKF SLAM3 که درآن نقشه، توسط تعدادی نشانه4 توصیف می شود .در روش های مونت کارلو5 دنباله ای یا همان فیلترهای ذرهای[3]6، استفاده از تعدادی ذره و محاسبه ی وزن ذرات باعث استفاده در مدل های غیر خطی نیز گردید.
در [4] برای اولین بار استفاده از تکنیک Rao-Blackwellization در بکارگیری فیلتر ذرهای برای حل مسئله SLAM پیشنهاد شد. در این روش از فیلتر ذرهای استفادهشد و از همه مهمتر تخمین نشانه ها به یکدیگر وابسته نبوده و مستقل از یکدیگر انجام میگیرد. اولین الگوریتم SLAM بر اساس این روش، موسوم به [5] FAST SLAM است. الگوریتم های زیادی بر اساس ساختار FAST SLAM پیشنهاد شده که [6] ،[7] و تنها نمونه هایی از آن ها می باشند.
در [8] نسخه ی بهبود یافته ی الگوریتم با نام FASTSLAM2.0 ارائه شد که در آن از توزیع پیشنهادی موسوم به توزیع پیشنهادی بهینه استفاده شده است. این توزیع اولین بار در [9] معرفی شده و برخلاف توزیع پیشنهادی ساده از اطلاعات اندازه گیری استفاده شده است. روش مورد نظر این پژوهش، روشFAST SLAM2.0 میباشد که به نسبت سایر روشهای مسیریابی SLAM در اثر اطلاعات اندازه گیری زمان کنونی، دقیق تر می باشد.
بردار حالت در مسئله SLAM و در مسیرهایینسبتاً کوتاه، به دلیل اضافه شدن نشانه ها در طی حرکت ربات به نقشه و بردار حالت، به راحتی ممکن است شامل هزاران درایه شود که به معنی افزایش هزینه های محاسباتی، افزایش زمان پردازش و کاهش سرعت پردازش شده است
-2پردازنده های تصویری
استفاده از روشهای مسیریابی براساس فیلترهای ذرهای بسیار وقتگیر می باشد که همین امر باعث آهسته انجام شدن مسیریابی میشود .شرط استقلال گفته شده در روشهای مسیریابی FAST SLAM و FAST SLAM2.0 میتواند یکی از چالشهای جدید برای افزایش سرعت باشد، این چالش جدید استفاده از پردازنده های موازی مانند پردازندهی تصویری7 می باشد. نمونه های استفاده از GPU در مسائل رباتیک را در [10] و [11] میتوان دید. GPU براساس مدل پردازشیSIMT8 میباشد که در[12]بیان شده است
در لایهی نرمافزارِ SIMT ، میلیونها نخ9 برنامهریزی میشود. کوچکترین واحد اجرایی در GPU نخ می باشد. پس از اختصاص فرآیند مورد اجرا از پردازنده ی مرکزی10 به GPU و تخصیص مقدار حافظه ی مورد نیاز ، GPU در مد کرنل فرآیند را توسط مجموعهای نخها به نام وارپ11 انجام می دهد. مجموعه نخهایی که کرنل را اجرا می کنند، گرید12 نام دارد. برای آنکه اجرا تمام نخهای گرید با محدودیتهای سخت افزاری ممکن است، گرید توسط برنامه نویس به چندین بلاک نخ تقسیم میشود. شکل 1 سلسله مراتب اجرا در GPU را نشان میدهد. هر بلاک تا سقف 1024 نخ، تشکیل شدهاست و تعداد 65536*65536 نخ در یک بلاک وجود دارد. شماره ی هر نخ نیز از رابطه ی - - 1 محاسبه می شود.
شکل: 1 سلسله مراتب اجرا در GPU
-3ملزومات مسیریابی
در این قسمت پیش نیازهای مورد نیاز برای فهم هرچه بهتر مراحل روشFAST SLAM2.0 بیان خواهد شد. این پیش نیازها جهت آشنایی با مفاهیم زنجیره ی مارکوف، فیلترهای کالمن و قوانین مونت کارلو می باشد.
-1-3 پیش بینی و اندازه گیری
در هر گام اندیس حالت های ربات به صورت St و اندیس توابع کنترلی برای ربات به صورت Ut و اندیس اندازه گیری نشانه ها به صورت Zt می باشد. معادلات فضای حالت احتمالی در هر ذره از رابطه - 2 - و - 3 - به دست می آید.
رابطه ی - 2 - بیان کنندهی پیش بینی حالت و رابطه ی - - 3 بیان کننده ی اندازه گیری است. دررابطه ی - - 2 پیش بینی هر حالت ربات در هر گام وابسته به حالت لحظه ی قبل تر ربات می باشد و در رابطه ی - - 3 نیز اندازه گیری و بروز رسانی فاصله در هر حالت از تأثیر حالت قبل در حالت جدید و اندازه گیری حالت قبل خواهدبود. [13] می توان این روابط - 2 - و - 3 - را با زنجیره ی مارکوف شکل - 2 - نشان داد.
