نقشه برداری و مکان یابی همزمان به کمک الگوریتم ژنتیک

نقشه برداری و مکان یابی همزمان به کمک الگوریتم ژنتیک

اسلاید 1: نقشه‌برداري و مكان‌يابي همزمان به کمک الگوريتم ژنتيکعلي وحدت برنا جعفرپورGenetic Algorithm for Simultaneous Localization And Mapping (SLAM)

اسلاید 2: نقشه‌برداري و مكان‌يابي همزمان2 فهرست مطالب الگوريتم ژنتيکمسئله ي SLAM به عنوان يک مسئله ي بهينه سازيالگوريتم ژنتيک براي حل مسئله SLAMنتايجنتيجه گيري

اسلاید 3: نقشه‌برداري و مكان‌يابي همزمان3 1-الگوريتم ژنتيکمقدمهاجزاي الگوريتم ژنتيکنمايش : Representationارزيابي : Evaluationانتخاب والدين : Parent Selectionبازترکيبي : Recombinationجهش : Mutationانتخاب بازماندگان : Survivor Selectionپايان : Termination

اسلاید 4: نقشه‌برداري و مكان‌يابي همزمان4 مقدمه اي بر الگوريتم ژنتيکالهام گرفته از تکامل موجودات در طبيعت در طي زمان مي باشدتکامل در طبيعت را به صورت کامپيوتري شبيه سازي مي کند. براي اين کار عملگرهايي شبيه آنچه در طبيعت وجود دارد تعريف مي شود.اين الگوريتم براي مسائلي که داراي فضاي حالت بزرگ باشند کارايي مناسبي دارد.اين الگوريتم با يک جمعيت اوليه تصادفي شروع به کار مي کند و با توليد نسلهاي مختلف جوابها را بهبود مي بخشد.

اسلاید 5: نقشه‌برداري و مكان‌يابي همزمان5 Representation نمايشنمايش مسئله به شکلي که براي الگوريتم ژنتيک قابل حل باشد.هر فرد داراي دو شکل وجودي مي باشد : phenotype و genotype. به genotype کروموزوم هم مي گويند.a d c a a c b genotype:phenotype:

اسلاید 6: نقشه‌برداري و مكان‌يابي همزمان6 ارزيابيکيفيت و کارايي جوابي که جواب يک فرد جمعيت را نشان مي دهدبراي اين منظور تابعي طراحي مي شود که يک جواب را دريافت مي کند و کيفيت آن را به شکل يک عدد حقيقي بر مي گرداند

اسلاید 7: نقشه‌برداري و مكان‌يابي همزمان7 انتخاب والدينهمانند رفتار طبيعت براي انتخاب شايسته ترين موجودات براي زنده ماندن مي باشد.به هر فرد احتمالي نسبت مي دهد که در نسل بعدي الگوريتم ايفاي نقش کند.افراد با کارايي بيشتر شانس بيشتري براي زنده ماندن دارند. شانس افراد وابسته به کارايي آنها مي باشد.

اسلاید 8: نقشه‌برداري و مكان‌يابي همزمان8 بازترکيبيشبيه سازي جفت گيري در طبيعت مي باشد.در اين عمل دو جواب از بين جمعيت انتخاب مي شوند و از طريق آنها دو فرزند که داراي ژنهاي والدين به صورت ترکيبي مي باشند توليد مي شود.

اسلاید 9: نقشه‌برداري و مكان‌يابي همزمان9 جهش و انتخاب باز ماندگانهمانند جهش در طبيعت مي باشد.جهش در طبيعت عبارت است از توليد موجودات عجيب غريب مانند حيوانات 2 سر و غيرهجهش در اکثر موارد نا مطلوب است ولي مي تواند در مواردي باعث توليد ويژگي هاي مفيدي که در پدر و مادر موجود نيست بشودانتخاب بازماندگان عبارت است از انتخاب از بين فرزندان توليد شده براي تشکيل نسل بعد .

اسلاید 10: نقشه‌برداري و مكان‌يابي همزمان10 شبه کد الگوريتم ژنتيک

اسلاید 11: نقشه‌برداري و مكان‌يابي همزمان11 شرايط مسئلهمسير بدست آمده توسط ادومتري و اطلاعات سنسور فاصله که به ازاي هر 10cm حرکت ربات ثبت شده است.اطلاعات مسير حرت ربات به شکل مي باشند. طول مسير طي شده در حرکت j ام و زاويه حرکت j ام مي باشد که توسط ادومتري بدست آمده است.مي دانيم اين مقاديري که با توجه به ادومتري بدست آمده داراي خطا مي باشد. هدف که پيدا کردن مسير طي شده ي بهينه اي است که بهترين نقشه را براي ما توليد کند.

اسلاید 12: نقشه‌برداري و مكان‌يابي همزمان12 2-مسئله ي SLAM به عنوان يک مسئله ي بهينه سازيهدف پيدا کردن بهترين مسير اصلاح شده است که مي توان با توجه به مسير موجود براي ربات يافت که بهترين نقشه ي موجود را براي ما توليد.بهترين نقشه ي موجود نقشه اي است که کمترين ميزان تابع معيار تعريف شده را توليد کند.تابع معيار مسير طي شده و اطلاعات سنسور فاصله را دريافت مي کند و با توجه به آنها نقشه را مي سازد.در واقع مسير نقشه را مي سازد و نقشه مسير را اصلاح مي کند

اسلاید 13: نقشه‌برداري و مكان‌يابي همزمان13 3-الگوريتم ژنتيک براي حل مسئله SLAMبايد اجزاي ذکر شده در الگوريتم ژنتيک را براي اين منظور تعريف کنيم.نمايش : همانطور که گفتيم اطلاعات موجود ادومتري به صورت مي باشد. کروموزومها را به صورت اصلاحاتي که روي داده هاي ادومتري اعمال شود در نظر گرفته مي شود. چون N عدد بسيار بزرگي مي باشد داده هاي ادومتري را به M قسمت مساوي که داراي اصلاحات يکسان مي باشند تقسيم مي کنيم. (M<<N)

اسلاید 14: نقشه‌برداري و مكان‌يابي همزمان14 الگوريتم ژنتيک براي حل مسئله SLAMدر مثال مورد بررسي ربات 150 متر حرکت داشته است. تصحيحات بر روي حرکتهاي 3 متري انجام مي شود. بنابر اين M=50 . براي توليد اوليه ي اتفاقي موارد زير در نظر گرفته مي شود :

اسلاید 15: نقشه‌برداري و مكان‌يابي همزمان15 الگوريتم ژنتيک براي حل مسئله SLAM2. ارزيابي : براي اين منظور تابعي تعريف شده است که با توجه به طلاعات ادومتري و اطلاعات سنسور نقشه را بر اساس روش occupancy grid مي سازد. براي هر سلول i شبکه 2 مقدار occi و empi محاسبه مي شود که به ترتيب نشان دهندهي تعدد دفعاتي مي باشند که سنسور فاصله آنها را فضاي آزاد يا مانع تشخيص داده است.بعد از توليد نقشه به کمک متغير هاي occ و emp 2 معيار کارايي به طور جداگانه محاسبه و با يکديگر جمع مي شوند.

اسلاید 16: نقشه‌برداري و مكان‌يابي همزمان16 الگوريتم ژنتيک براي حل مسئله SLAMاطلاعات بدست آمده توسط ادومتري و سنسور فاصله

اسلاید 17: نقشه‌برداري و مكان‌يابي همزمان17 الگوريتم ژنتيک براي حل مسئله SLAM1. معيار سازگاري : ميزان سازگاري اطلاعات سنسور فاصله براي سلولهاي مختلف نقشه : هر چه اين مقدار کمتر باشد به اين معني است که اطلاعاتي که سنسور در مکانهاي مختلف به ما داده تطابق بيشتري با يکديگر دارند.2. معيار فشردگي : مربعي به دور کل نقشه ي بدست آمده (نقاطي که occ آنها صفر مي باشد) کشيده مي شود و مساحت آن به عنوان معيار فشردگي به کار مي رود

اسلاید 18: نقشه‌برداري و مكان‌يابي همزمان18 الگوريتم ژنتيک براي حل مسئله SLAMنقشه ي بدست آمده فقط توسط معيار سازگاري

اسلاید 19: نقشه‌برداري و مكان‌يابي همزمان19 الگوريتم ژنتيک براي حل مسئله SLAMهمانطور که ديديم استفاده از معيار سازگاري به عنوان تنها معيار ارزيابي کارايي به جاي حل ناسازگاري ها از آنها اجتناب مي کند.براي اين منظور متغيري به نام w معرفي کرده اند که نشان دهنده ي ارزش نسبي دو معيار ذکر شده مي باشد و کارايي نهايي به اين شکل محاسبه مي شود : F = MC1 + wMC2

اسلاید 20: نقشه‌برداري و مكان‌يابي همزمان20 الگوريتم ژنتيک براي حل مسئله SLAM3. انتخاب والدين : 2 برابر تعداد افراد جمعيت والدين براي توليد نسل بعد از طريق بازترکيبي احتياج است.براي اين منظور شايستگي افراد را با توجه به تابع معيار انتخاب مي کنيم. براي اين منظور براي فرد i مقدار ei را به اين شکل توليد مي کنيم : مقدار e بهترين و بدترين فرد را برابر با emin و emax قرار مي دهيم..5) =(emax=1.5 emin و کارايي بقيه ي افراد را با توجه به اين دو مقدار درون يابي خطي مي کنيم. اگر بخش غير کسري 1 بود يک نسخه براي بازترکيبي انتخاب مي شود. بقيه ي والدين با احتمالي متناسب با بخش کسري انتخاب مي شوند.4. جهش : هر بعد جواب با احتمال کم 0.005 عددي به صورت اتفاقي تغيير مي کند.

اسلاید 21: نقشه‌برداري و مكان‌يابي همزمان21 الگوريتم ژنتيک براي حل مسئله SLAM5. انتخاب بازماندگان : در اين مورد توضيحي داده نشده است.6. پايان : الگوريتم بعد از 150 نسل پايان مي يابد

اسلاید 22: نقشه‌برداري و مكان‌يابي همزمان22 نتايج فقط سازگاري سازگاري و فشردگي

اسلاید 23: نقشه‌برداري و مكان‌يابي همزمان23 نتيجه گيريبه گفته ي نويسندگان مقاليه توليد هر نسل الگوريتم ژنتيک بر روي يک کامپيوتر PII 200 حدود 50 ثانيه زمان مي برد. بنابر اين هر بار اجراي کامل آن زماني در حدود 5/2 ساعت زمان لازم دارد.اين زمان بالا الگوريتم را به روشي offline تبديل مي کند. در اين روش فرض شده است که ربات فاصله ي زيادي را بدون اينکه بداند کجاست طي کرده است.نسخه هاي سريعتر يا موازي مي تواند اين روش را کاربردي کند.

اسلاید 24: نقشه‌برداري و مكان‌يابي همزمان24 نتيجه گيريمزيت اين روش در نظر نگرفتن شرايط خاصي در محيط و ربات مي باشد.مزيت ديگر آن پارامتر هاي کم براي تنظيم مي باشد. تنها پارامتر w نياز به تعيين شدن دارد

اسلاید 25: نقشه‌برداري و مكان‌يابي همزمان25 جمع بندي و نتيجه گيري در ابتدا مکان يابي و نقشه برداري بصورت مجزا يادآوري شد، سپس روش هاي آماري براي مکان يابي و نقشه برداري همزمان مورد بررسي قرار گرفت. ديديم که روش هاي آماري تنها روش هايي هستند که مي توانند همه فضاي احتمالات نقشه و وضعيت روبات را بررسي کنند و ضمنا انواع نويزها را مدل کرده و عدم قطعيت را نيز در محاسبات در نظر مي گيردتمام روشها وابستگي بالايي به خطاي اوليه دارند. خطاي زياد در تصور اوليه ي ربات از موقعيت خويش مي توانند خطاهاي بسيار بزرگي توليد کند

اسلاید 26: نقشه‌برداري و مكان‌يابي همزمان26 جمع بندي و نتيجه گيريفيلتر کالمن همگرايي بالايي دارد ولي بار محاسباتي آن بالا مي باشد. مزيت آن realtime بودن و افزايشي بودن آن است.روش EM همگرايي پاييني دارد ولي براي توليد نقشه هايي که داراي حلقه هاي بزرگ مي باشند بسيار مفيد مي باشد و از تمام الگوريتم هاي بر پايه ي فيلتر کالمن در اين مورد بهتر عمل مي کندمي توان با ترکيب الگوريتمهاي مختلف الگوريتمهاي جديدي بدست آورد که مزاياي آنها را با هم داشته باشد.

اسلاید 27: نقشه‌برداري و مكان‌يابي همزمان27 با تشکر!