بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
رهيابي ربات متحرک در حضور موانع بر اساس الگوريتم غذايابي باکتري
خلاصه : در اين مقاله ، روشي براي رهيابي ربات در محيطي ناشناخته پويا بر پايه ي روش بهينه سازي غذايابي باکتري پيشنهاد ميشود. ابتدا مسأله ي مسيريابي ربات به يک مسأله ي مينيمم کردن تبديل مي شود. سپس يک تابع هدف ، بر پايه ي مکان هدف و موانع در محيط تعريف مي شود. در هر بار تکرار الگوريتم ، بهترين نقطه انتخاب ميشود و ربات به ترتيب به سمت اين نقاط بهينه حرکت مي کند. محيط براي ربات کاملاً ناشناخته است و ربات با سنسورهاي خود تا شعاع محدودي قادر به شناسايي محيط است . موانع موجود در مسير ربات ميتوانند ثابت يا متحرک باشند.
ربات ها و محيط با استفاده از نرم افزار وباتز شبيه سازي شده اند تا قوانين و شرايط موجود در دنياي واقعي بر مسأله حاکم شود. مشاهدات و تجربه هاي به دست آمده از سيستم شبيه سازي شده نشان داد که با استفاده از اين روش ، ربات بدون برخوردي با موانع ، مسيري بهينه تا هدف را مي پيمايد
کلمات کليدي: رهيابي، الگوريتم غذايابي باکتري، اجتناب از موانع ، BFA
١ - مقدمه
رهيابي يا ناوبري رباتهاي متحرک يک مساله ي اساسي در علم رباتيک است ، الگوريتم هاي رهيابي رباتها به سه دسته رهيابي در محيط ساختار يافته (شناخته شده )، رهيابي در محيط نيمه ساختار يافته و رهيابي در محيط ساختارنيافته تقسيم مي شود، هر کدام از اين دسته ها خود مي توانند استاتيکي يا ديناميکي باشند[٣]. در رهيابي در محيط ساختار نيافته و ناشناخته است اصطلاحا رهيابي محلي صورت مي گيرد، لذا شناخت محيط بوسيله سنسورها انجام مي گيرد اما در رهيابي محيط ساختار يافته است ، محل موانع و ربات و هدف مشخص است و رهيابي جهاني است [٤].
در اين طرح به رهيابي يک ربات در حضور موانع بوسيله الگوريتم بهينه سازي غذايابي باکتري پرداخته مي شود، و ربات به وسيله آن در کوتاهترين زمان ممکن و کوتاهترين مسير خود را از موانع دور و به هدف مي رساند.
الگوريتم غذايابي باکتري داراي سرعت خوبي در بين الگوريتمهاي بهينه سازي است .
اهدافي که در اين مقاله دنبال مي گردد عبارت است از:
• ارائه روشي براي مسيريابي ربات متحرک درون محيط به نحوي که کوتاهترين مسير ممکن را با کمترين زمان بپيمايد.
• ربات در بين راه بايد از موانع عبور و از آنها اجتناب کند.
• شبيه سازي روش ارائه شده با نرم افزار شبيه ساز رباتها Webots
٢ – مروري بر کارهاي پيشين
محققين بسياري روشهاي مختلف رهيابي و حرکت در محيط هاي ديناميک و استاتيک ارائه کرده اند، از جمله رهيابي ربات متحرک همه جهته سريع به روش دايره مرزي[١] که در محيط پويا جوابگو مساله رهيابي است ولي اشکال آن وابسته بودن به اندازه موانع است ،رهيابي ربات متحرک درون محيط ديناميک ساختمان به روش q-learning [٢]، رهيابي ربات متحرک بر اساس نقشه راه [٥]. رهيابي فازي درون ساختمان [٦]. رهيابي ربات درون محيط ساختار يافته با استفاده از کنترل شبکه عصبي [٧]. رهيابي ربات متحرک درون ساختمان با استفاده از ديد تک رنگ [٨]. رهيابي بر اساس ميدان پتانسيل درون محيط استاتيک که بر اساس جذب هدف و دفع موانع کار مي کند اما داراي مشکل مينيمم محلي است [٩].
در زمينه طراحي مسير ربات بوسيله الگوريتم باکتري نيز مقاله اي نوشته شده است [١٠] در اين مقاله موانع را ثابت و دايره اي فرض کرده است و از سنسور نيز استفاده نکرده است بلکه جاي موانع را از قبل معلوم مي داند.
٣- معرفي الگوريتم غذايابي باکتري
ايده الگوريتم غذايابي باکتري [ ١١ ] بر اين واقعيت استوار است که در طبيعت ، جانداران با روش غذايابي ضعيف احتمال انقراض بيشتري نسبت به جانداراني با استراتژي غذايابي موفق دارند .پس از نسلهاي زياد، جانداران و روشهاي غذايابي ضعيف نابود شده و يا به حالتهاي بهتر تغيير شکل مي دهند. باکتري E-coli که در روده انسان زندگي مي کند، روش غذايابي دارد که بر چهار مرحله استوار است .اين چهار مرحله عبارتند از : حرکت ١ عملکرد گروهي٢ توليد مثل ٣ و حذف و پراکندگي
1-3 حرکت
در این مرحله باکتري ها شروع به جنبش و شنا مي کنند .در واقع بسته به چرخش دم باکتري، باکتري جست و خيز کرده و شروع به حرکت در مسيري مي کند) .جنبش .(اگر در مسير جديد مقدار غذا بهتر بود باکتري شروع به شنا در همان مسير مي کند(شنا)
فرض کنيد مي خواهيم مقدار مينيمم را پيدا کنيم .
فرض کنيد مکان باکتري و نشان دهنده مقدار غذا در مکان باشد. فرض کنيد و ، به ترتيب به اين معني باشند که باکتري در مکان داراي غذاي خوب ، خنثي و بد باشد. براي انجام جنبش يک بردار با طول واحد به نام توليد مي شود اين بردار براي تعريف جهت جديد حرکت باکتري بعد از انجام جنبش به کار مي رود. مکان جديد باکتري به صورت زير تعريف مي شود.
که در آن نشان دهنده مکان باکتري iام در مرحله حرکت jام ، توليد مثل k ام و نابودي و پخش lام مي باشد (C)i اندازه حرکت باکتري در جهت حرکت مي باشد. اگر اندازه در کمتر از اندازه آن در باشد، آنگاه يک گام حرکت ديگر به اندازه در جهت انجام مي شود و باکتري شروع به شنا کردن در جهت مي کند .اين شنا کردن تا زماني که اندازه کاهش مي يابد و حداکثر تا ماکز يمم تعداد مراحل مجاز شنا کردن Ns ادامه مي يابد .اين نشان دهنده اين مي باشد که باکتري تا زماني که در جهت حرکت خود محيط بهتري از لحاظ غذا بيابد به حرکت در همان جهت ادامه خواهد داد.
٣-٢ عملکرد گروهي
وقتي که يک باکتري مسير بهتري براي غذا پيدا مي کند ديگر باکتري ها را به سمت خود جذب کرده و باکتري ها سر يعتر به محل غذاي اصلي مي رسند .عملکرد دسته جمعي سبب حرکت گروهي باکتري ها به سمت غذا مي شود. اگر را مجموعه مکان هاي باکتري ها فرض کنيم ، عملکرد دسته جمعي به صورت رابطه ٢ مدل مي شود:
که بسته به حرکت همه باکتريها، تابعي وابسته به زمان بوده و به مقدار تابع هز ينه افزوده مي شود. بنابراين باکتريها شروع به تلاش براي پيدا کردن غذا نموده ، از مکانهاي بي غذا فرار کرده و در همان حين يکديگر را جذب مي کنند و در عين حال نيز بيش از حد به هم نزديک نمي شوند S تعداد کل باکتريها بوده و p تعداد پارامترهايي است که بايد بهينه شوند و به عنوان مختصات مکان باکتري در فضاي p بعدي محسوب مي شوند. ضرايبي هستند که بايد مقدار مناسبي براي آنها بسته به مسئله مورد نظر انتخاب شود.
٣-٣ توليد مثل
نصف تعداد باکتريها که غذاي خوبي پيدا نکردهاند نابود شده و نصف ديگر شامل باکتريهاي سالم هر يک به دو باکتري تقسيم شده که در همان مکان قبلي باکتري قرار مي گيرند .اين عمل تعداد جمعيت باکتريها را ثابت نگه مي دارد.
٣-٤ حذف و پراکندگي
زندگي جمعيت باکتري ها به مرور با مصرف غذا و يا ناگهاني در اثر موارد ديگر دچار تغيير مي شود. حوادث مي توانند موجب کشته شدن اوسيات پرمانکجندره به شبدرن هم باکختوررين هامرشحولنه د .حاريکن ت ع بمه ل ساگمرت چه غذدار باابتشددا، مامماکمن ي تواند تاثير مثبتي هم برآن داشته باشد .زيرا پراکندگي باکتريها ممکن است آنها ر ا در مکانهايي نزديک به منابع غذايي خوب قرار دهد. مرحله حذف و پراکندگي از به دام افتادن باکتري ها در نقطه بهينه محلي جلوگيري مي کند. در هر مرحله حذف و پراکندگي هر باکتري موجود در جمعيت با احتمال در معرض حذف و پراکندگي قرار مي گيرد. براي ثابت نگه داشتن تعداد باکتريها، اگر يک باکتري نابود شود، باکتري جديدي را به صورت رندوم در محدوده فضاي جستجو قرار مي دهيم . الگوريتم مذکور به صورت کد در ضميمه مقاله آمده است .
٥ –سينماتيک ومدل ربات چمرو
ربات مورد استفاده در اين مقاله يک ربات دو چرخ با رانش تفاضلي به نام چمرو است که آن را نيز ساخته ايم . اين ربات عملهاي، حرکت به جلو، چرخش به راست ، چرخش به چپ رامي تواند انجام دهد. اين ربات ١٦ سنسور مادون قرمز اطراف خود دارد، اين سنسورها براي حس کردن موانع ناشناخته احتمالي اطراف ربات است . . در شکل (١) ربات چمرو با اندازه ها نشان داده شده است . همچنين شکل (٢) تصويري از ربات ساخته شده را نشان مي دهد.
سينماتيک ربات بر اساس معادلات (٣ و ٤) محاسبه مي شود:
در اين معادلات v سرعت خطي مرکز ربات به سمت جلو است و سرعتهاي مطلق ربات در راستاي محورهاي جهاني است و سرعت دوراني کل ربات است که با ωبرابر است . ωr سرعت دوراني چرخ راست و ωl سرعت دوراني چرخ چپ است . θ زايه جهت گيري ربات نسبت به محور شمال است (محورy). اين متغيرها در شکل (٢) نشان داده شده ا ند.
حرکت ربات به دو حالت تقسيم مي شود: ساختار يافته يا شناخته شده براي هنگامي که تنها موانع ممکن ديوارهاي ثابت هستند و حالت ساختار نيافته يا ناشناخته براي زماني که موانع ثابت و متحرکي با اندازه هاي مختلف در محيط وجود داشته باشد.
براي حرکت ربات به سمت يک نقطه مشخص با دانستن مکان نقطه هدف و ربات از زواياي شکل (٤) استفاده مي شود. θ زاويه جهت گيري ربات نسبت به محور شمال است ، φ زاويه خط ربات -هدف با محور شمال و زاويه اختلاف اين دو زاويه است . ربات در هر گام زماني از رابطه (٥) استفاده مي کند و سعي مي کند زاويه را نزديک صفر برساند، اگر اين زاويه مثبت بود، ربات سمت چپ مي چرخد و اگر منفي بود سمت راست مي چرخد.
هنگامي که ربات با رابطه (٣)در راستاي نقطه هدف جاري قرار گرفت ،
به سمت آن حرکت مي کند
