بخشی از مقاله
کاربرد مقایسه ای منطق فازی و الگوریتم ژنتیک جهت ناوبری هوشمند ربات متحرک در محیط های ناشناختهء پویا در حضور موانع ثابت و متحرک
چکیده
در سال های اخیر، مباحث مرتبط با علوم رباتیک، به یکی از زمینه های تحقیقاتی و در حال گسترش تبدیل شده است. در این میان ربات های هوشمند، از مقبولیت بسیاری برخوردار شده اند؛ اما کنترل و ناوبری1 این وسیله ها بسیار دشوار بوده و عدم برخورد با موانع2 ثابت و متحرک و اجتناب از آنها، به جهت مسیریابی3 ایمن و مطمئن، از نیازهای اساسی این سیستمها به شمار می رود. یک ربات متحرک باید در زمانی معین به هدف های تعیین شده برسد و ممکن است معیارهایی مانند: سرعت، امنیت، شناخت محیط و غیره را نیز در طول مسیر، بهینه کند. ربات باید در هر گام، موقعیت مکانی خود نسبت به اهداف را تعیین کرده و استراتژی کنترلی مناسب را برای رسیدن به اهداف، صادر نماید. همچنین کسب اطالعات در خصوص محیط نیز برای دوری از موانع، طراحی مسیر بهینه4 و اکتشاف محیط، ضروری است و ایجاد ارتباط هوشمندانه بین ادراک و عمل که مستلزم بهره گیری از الگوریتم های مناسب از جمله الگوریتم ژنتیک5 و منطق فازی6 -کنترل کننده فازی- نیز به منظور مدیریت کنترل و ناوبری مورد نیاز می باشد.
در این پژوهش برای حل مسئله ناوبری هوشمند ربات متحرک در محیط ناشناختهء پویا -شرایط در هر لحظه متغیر و موانع در حال حرکت می باشند- و انتخاب مسیر بهینه، از روش های الگوریتم ژنتیک و منطق فازی بصورت مقایسه ای استفاده می شود. چراکه با استفاده از این روش ها، ربات متحرک می تواند در محیط های پویا و ناشناخته، مسیر بهینه را تا هدف طی نماید.
کلمات کلیدی: کنترل و ناوبری هوشمند، اجتناب از موانع، مسیریابی بهینه، الگوریتم ژنتیک، منطق فازی.
.1 مقدمه
ربات ها برای انجام عملیات در محیط های واقعی -ناشناخته-، باید قادر باشند اهداف تعیین شده را با وجود بروز تغییرات احتمالی و پیش بینی نشده محیط، دنبال کنند. محیط های واقعی به ندرت قابل پیش بینی یا کامالً شناخته شده اند؛ بنابراین ایجاد یک مسیر حرکتی دقیق، قبل از حرکت در چنین محیط هایی، عموماً کاربردی نخواهد بود.[1] در حالت کلی، می توان مسئله طرح ریزی مسیر حرکت ربات را به دو زیر مسئله تجزیه نمود:[2]
1
-1 تعقیب هدف:1 زیرا مسیرهای کوتاه به هدف را نمی توان تنها با استفاده از اطالعات محلی بدست آورد؛ در نتیجه توپولوژی -مکان شناسی- فضا، در یافتن مسیرهای مناسب به هدف، مهم است.
-2 پرهیز از موانع: 2 اغلب تنها با استفاده از اطالعات محلی حل می شود، یعنی ربات ابتدا می بایست موانع را احساس کند تا بتواند از آنها دوری نماید. ربات در محیط هائی حرکت می کند کهغالباً ناشناخته هستند، از این رو نمی توان ربات را برای انجام کارهای از پیش دانسته برنامه ریزی نمود. این ربات باید به حسگرهای دقیقی مجهز باشد تا بتواند محیط را شناسائی و از برخورد با اشیاء جلوگیری نماید.
بطور کلی می توان راه حل های ارائه شده برای مسائل طرح ریزی مسیریابی و حرکت ربات را در قالب دو زیر مجموعه "روش های کالسیک"3 و "روش های اکتشافی"4 دسته بندی نمود:[2]
• روش های کالسیک: این روش ها در کل از ترکیب چندین روش کلی حاصل می شوند که عبارتند از: روش نقشه راه5، تجزیه سلولی6، روش میدان های پتانسیل مصنوعی7 و برنامه نویسی ریاضی.8 اغلب مسائل طرح ریزی مسیریابی و حرکت ربات با
این روش ها قابل حل اند. در روش نقشه راه، یک فضای پیکربندی9 آزاد -فضای پیکربندی، مجموعه ای از تمام پیکربندی هایی است که ربات می تواند به آن ها دست یابد و فضای پیکر بندی آزاد، آن مجموعه از پیکربندی هایی است که تداخلی با موانع ندارند. بُعد این فضا با تعداد درجات آزادی10 ربات مشخص می شود- وجود دارد که در آن حرکات مجاز با شبکه ای از خطوط یک بعدی نشان داده می شود. جستجو برای راه حل به این شبکه محدود می شود که مسئله طرح ریزی مسیریابی و حرکت ربات را به یک مسئله جستجوی گرافی11 تبدیل می کند. متداول ترین روش گراف آشکاری12 است. در این روش شبکه ای از خطوط، یک ویژگی از اشیاء را که معموال رئوس چند ضلعی هستند را به هم متصل می کنند. از میان این شبکه یک مسیر بدون مانع یافت می شود. در روش الگوریتم تجزیه سلولی، فضای پیکربندی آزاد به مجموعه ای از سلول های ساده تجزیه شده و ارتباط بین سلول های مجاور محاسبه می گردد. سپس یک مسیر بدون برخورد با اتصال سلول های شروع و هدف با توالی از سلول های مرتبط به هم، بین پیکربندی های شروع و هدف ایجاد می شود. در روش میدان های پتانسیل مصنوعی، مبنای کار استفاده از یک میدان پتانسیل مصنوعی است که این میدان از یک نیروی دافعه قوی در مجاورت موانع و یک نیروی جاذبه تولید شده در موقعیت هدف تشکیل می شود. ادغام این دو نیرو یک میدان پتانسیل ایجاد می کند که اطالعاتی درباره محیط می دهد. با استفاده از این اطالعات، می توان مسیری را پیدا کرد که ربات را به موقعیت هدف با پرهیز از موانع هدایت می کند. در روش برنامه ریزی ریاضی، مسئله طرح ریزی مسیریابی و حرکت ربات به یک مسئله بهینه سازی ریاضی تبدیل می شود که در نهایت یک منحنی بین پیکربندی های شروع و هدف از طریق
کمینه کردن یک کمیت اسکالر13 خاص حاصل می شود.
• روش های اکتشافی: روش های اکتشافی شامل روش های تجزیه سرعت مسیر14، روش دسترسی15، روش احتمالی16، روش دیاگرام سرعت نسبی.17
2
در روش های کالسیک، مشکالتی نظیر پیچیدگی های محاسباتی در ابعاد باالتر فضای پیکربندی و همچنین مشکل پیچیدگی زماان باال را دارند. بعالوه برخی از راه حل ها مانند روش میدان های پتانسیل مصنوعی، محلی هستند کاه ممکان اسات رباات را در نقااط مینیمم محلی1 -نقاط مینیمم محلی نقاطی هستند که از نقاط مینیمم اصلی کمی بزرگتر بوده و در نزدیکی مسیر حرکت قرار دارند- گرفتار کند.[3] از این رو روش های مدرن اکتشافی برای بهبود عملکرد آنها پیشنهاد شده است.
.2 تئوری و پیشینه تحقیق
بسیاری از روش های مسیریابی قید شده در قسمت قبلی،غالباً در وضعیت هایی که یک مانع مسیر ربات به هدف را مسدود کرده انعطاف پذیری کافی را ندارند -استفاده از توابع از پیش تعریف شده- و دارای مشکالت مربوط به پیچیدگی زمان باال هستند.
در این پژوهش سعی شده است تا با بکارگیری روش های مدرنی همچون روش منطق فازی -چرا که برای مسیریابی ربات در محیطهای ناشناخته در حضور موانع ثابت و متحرک، بدون شناخت از موقعیت و تابع حرکت موانع و بصورت لحظه ای و گره به گره باید سراغ روشهای مسیریابی لحظهای 2 برویم- و همچنین روش الگوریتم ژنتیک -چراکه الگوریتم ژنتیک با یک مجموعه از مقادیر متغیرهای تصمیمگیری که هر دسته از آنها -معادل با یک کروموزوم- میتواند جواب ممکن برای طرح باشد، کار جستجو را -به طور موازی- انجام میدهد؛ حال آنکه روشهای دیگر فقط با یک دسته از متغیرهای تصمیمگیری که فقط یک جواب ممکن برای طراحی هستند، به کار جستجو ادامه میدهند- ؛ و با توجه به عدم قطعیت اطالعات ورودی، مسئله طرح ریزی مسیریابی و حرکت ربات را بصورت بهینه و هوشمند طرح ریزی نمود. همچنین در مورد فضای پیکربندی یک ربات متحرک3 نیز موارد زیر قابل توجه است:[15,4]
• برای یک ربات متحرک رسم بر این است که آنرا بصورت هولومنیک4 فرض کنیم. در اینصورت ربات را میتوان بصورت یک نقطه در نظر گرفت.
• در نتیجه فضای موقعیت را میتوان بصورت دو بعدی با محورهای x,y نشان داد.
• در این حالت اشیاء موجود در محیط باندازه شعاع ربات، بزرگ میشوند تا فرض نقطه ای بودن ربات نیز درست باشد.
در شکل -1- فضای موقعیت یک ربات متحرک دو بعدی نمایش داده شده است.
شکل :1 فضای موقعیت یک ربات متحرک دو بعدی[4]
-1-2 بکارگیری منطق فازی جهت ناوبری هوشمند ربات متحرک در محیط های ناشناختهء پویا واژه فازی در فرهنگ لغت اکسفورد بصورت مبهم، گنگ، نادقیق، گیج، مغشوش، درهم و نامشخص تعریف شده است.[5] در این متن دو نوع توجیه برای تئوری سیستم های فازی وجود دارد:[5]
• توجیه اول: دنیای واقعی ما بسیار پیچیده تر از آن است که بتوان یک توصیف و تعریف دقیق برای آن بدست آورد بنابراین باید یک توصیف تقریبی یا همان فازی که قابل قبول، تجزیه و تحلیل باشد برای یک مدل معرفی شود.
3
• توجیه دوم: ما به فرضیه ای نیاز داریم که بتوان دانش بشری را به شکل سیستماتیک فرموله کرده و آنرا به همراه سایر مدلهای ریاضی در سیستم های مهندسی قرار دهد.
در منطق فازی با مقادیری غیر قطعی و تقریبی کار میکنیم؛ محدودهای از احتماالت که ممکن است اتفاق بیافتند.[6] وقتی سیستم فازی به عنوان کنترل کننده مورد استفاده قرار می گیرد، به آن کنترل کننده فازی اطالق می شود. در شکل -2- ساختار یک کنترل کننده فازی نمایش داده شده است.
شکل :2 ساختار کنترل کننده فازی[6]
در این قسمت برای مسیریابی ربات در محیطهای ناشناخته در حضور موانع ثابت و متحرک، بدون شناخت از موقعیت و تابع حرکت موانع و بصورت گره به گره، باید به سراغ روشهای مسیریابی لحظهای1 برویم. منطق فازی کارایی بسیار مناسبی در مسیریابی لحظهای و گره به گره 2 دارد.[6] مسیریابی از نقطه اولیه به صورت گره به گره انجام میشود تا زمانی که ربات به نقطه هدف برسد. با این روش در هر لحظه، گره بعدی با توجه به 8 گزینه -در این پژوهش مسیر حرکت بصورت 8 تایی در نظر گرفته شده است- موجود با استفاده از منطق فازی مطابق شکل -3- انتخاب میشود.
شکل :3 مسیرهای حرکتی موجود جهت حرکت به سمت گره های جدید[6]
ورودیهای فازی که در اینجا برای مسیریابی در نظر گرفته می شود عبارت اند از :
• اختالف زاویه گره های بعدی تا هدف
• فاصله گره های بعدی تا نزدیکترین مانع
الزم به ذکر است که در هر لحظه در هر گره ای که ربات در آن موقعیت قرار گرفته باشد، فقط تا شعاع خاصی که بورد حسگرهای ربات3 تعیین میکند، از موقعیت موانع اطالع خواهد داشت.[14,7] مثال اگر بورد حسگرها 30 سانتی متر باشد -در داخل برنامه شبیه سازی نیز بطور فرضی این شعاع 30 سانتیمتر در نظر گرفته شده است-، در هر لحظه ربات از موقعیت موانع تا شعاع 30 سانتی متری در اطراف خود با خبر است.
در هر لحظه ادامه مسیریابی و انتخاب گره بعدی از بین 8 گزینه موجود صورت می گیرد - البته الزم به توضیح است که می توان گزینه های انتخابی را تا 16 حالت و یا حتی تعداد بیشتری نیز در نظر گرفت-. برای هر کدام از این 8 گره، یک ضریب اولویت انتخاب
4
شدن به عنوان گره بعدی -با استفاده از منطق فازی- بدست میآید. پس از اجرای منطق فازی -انجام عمل فازی سازی- به ازای ورودیهای هر گره، یک خروجی که بیانگر اولویت انتخاب شدن آن گره است، ایجاد میشود. در نهایت گره بعدی گره ای است که بیشترین ضریب اولویت را داشته باشد. مراحل کلی مسیریابی گره به گره با استفاده از منطق فازی به صورت شکل -4- صورت می گیرد.
شکل :4 مراحل کلی مسیریابی بهینه تا تولید خروجی، توسط منطق فازی[7]
-1-1-2 فازی سازی ورودی ها انتخاب مسیر با منطق فازی به صورت گره به گره و لحظه ای است و در واقع منطق فازی به تعداد گره های میانی مسیر اجرا
می شود.[8] در طراحی این سیستم از دو ورودی فازی برای تعیین مسیر استفاده شده است: یکی اختالف زاویه تا هدف و دیگری فاصله تا نزدیکترین مانع، که در هر ورودی 5 تابع عضویت برای فازی سازی1 استفاده شده است -توابع عضویت در این جا بصورت فرضی در نظر گرفته شده است-. مطابق شکل های -5- و -6- توابع عضویت فازی برای ورودی زاویه و ورودی فاصله قابل مشاهده است.
شکل :5 توابع عضویت برای فازی سازی ورودی اول : اختالف شکل :6 توابع عضویت برای فازی سازی ورودی دوم : فاصله تا
زاویه گره بعدی نسبت به هدف[8] نزدیکترین مانع[8]
الزم به ذکر است که در هر لحظه ورودی های غیر فازی به ازای 8 گره بعدی ابتدا در بازه صفر تا یک نرمالیزه2 میشوند و سپس فرآیند فازی سازی انجام میشود. در این سیستم برای خروجی نیز از 5 تابع عضویت بصورت زیر -بطور فرضی- استفاده شده است:[8]
5
به عبارتی در هر تکرار ورودی های غیر فازی اختالف زاویه تا هدف و فاصله تا نزدیکترین مانع ابتدا در یک بازه [0,1] نرمالیزه شده و سپس تعلق فازی به توابع مختلف فازی تعیین میگردد.
در این سیستم انتخاب گره بعدی نیز با استفاده از منطق فازی انجام شده است. به این صورت که در هر موقعیت مکانی از فضای شبکه بندی محیط کاری، هرچه اختالف زاویه یک گره تا هدف کمتر باشد و گره فاصله بیشتری تا نزدیکترین مانع داشته باشد، اولویت فازی1 بیشتری برای انتخاب به عنوان گره بعدی در مسیر را دارد. به عبارت دیگر ضریب اولویت باالتری را نسبت به سایر گره ها کسب میکند.[8] به طور کلی فرآیند بدین صورت است که در ابتدا برای هر گره در هر لحظه فاصله از نزدیکترین موانع موجود و اختالف زاویه تا هدف سنجیده می شود و در بازه [0,1] نرمالیزه میشوند. در مرحله بعد، برای هر گره ورودی های نرمالیزه شده غیرفازی از نزدیکترین موانع موجود و اختالف زاویه تا هدف با استفاده از توابع عضویت فازی مربوطه، تحت فازی شدن قرار می گیرند. توابع عضویت برای خروجی فازی نیز بصورت شکل -7- است.
شکل :7 توابع عضویت برای خروجی فازی -ضریب اولویت انتخاب شدن گره-[8]
-2-1-2 جدول قوانین فازی همانطور که گفته شد انتخاب گره بعدی در مسیر با استفاده از منطق فازی صورت می گیرد. جدول قوانین فازی برای انتخاب گره
بعدی در مسیریابی لحظهای به صورت گره به گره در جدول مخصوص آن تنظیم شده است. در این جدول به طور کلی هرچه فاصله تا نزدیکترین مانع زیادتر باشد و از طرفی اختالف زاویه نسبت به هدف کمتر باشد آن گره اولویت بیشتری برای انتخاب شدن به عنوان گره بعدی را در مسیر حرکت دارا است. همان طور که شرح داده شده است برای تعیین خروجی فازی به ازای هر گره جدول قوانین فازی بصورت جدول -1- است که در آن تمامی قوانین به صورت قانون AND -بصورت فرضی- در نظر گرفته شده اند. در مرحله بعد شکل خروجی فازی را می توان از روش Multiple ممدانی یا Max-Min بدست آورد. در این مرحله بر اساس ورودیهای فازی مربوط به گره، یک یا چند قانون طبق جدول شماره -1- اجرا میگردد.
جدول :1 جدول قوانین فازی برای انتخاب گره بعدی در مسیریابی لحظهای گره به گره با استفاده از منطق فازی[8]
فاصله تا نزدیکترین مانع اختالف زاویه نسبت به هدف خروجی : اولویت انتخاب نود بعدی
-3-1-2 غیر فازی سازی خروجی و تعیین ضریب اولویت نهایی تا اینجا فقط به پروسه فازی سازی پرداخته شد. بعد از اینکه عملیات فازی روی سیستم انجام شد در نهایت باید یک جواب قطعی
بدست آوریم. برای رسیدن به یک جواب قطعی از پروسه غیرفازی سازی1 استفاده می شود. جهت غیر فازی سازی، معموال یکی از دو روش نمایش داده شده در شکل -8- -مرکز ثقل2 -شکل سمت راست- و روش میانگین وزنی3 -شکل سمت چپ و مورد استفاده در این پژوهش-- استفاده می شود.[9]
شکل :8 روش مرکز ثقل و روش میانگین وزنی جهت انجام عملیات غیر فازی سازی[9]
در نهایت پس از تعیین خروجی های غیر فازی نهایی به ازای 8 گزینه موجود، گزینهای که حداکثر خروجی غیر فازی را داشته باشد بعنوان گره بعدی در مسیر انتخاب می شود. فرآیند فوق تا زمانی ادامه پیدا می کند که ربات به هدف رسیده باشد و در آنجا کار به پایان خواهد رسید. مراحل تشکیل مسیر بهینه با استفاده از منطق فازی -با داشتن مختصات نقطه ابتدا و انتهای مشخص- و نحوه مواجه شدن با موانع ثابت و متحرک نیز بصورت شکل -9- می باشد.
8
شکل :9 مسیریابی به روش منطق فازی در محیط کامال پیچیده با حضور موانع ثابت و متحرک -با طول مسیر 73877615 سانتی متر-
-2-2 بکارگیری الگوریتم ژنتیک جهت ناوبری هوشمند ربات متحرک در محیط های ناشناختهء پویا محدوده کاری الگوریتم ژنتیک بسیار وسیع می باشد و هر روز با پیشرفت روزافزون علوم و تکنولوژی اساتفاده از ایان روش در بهیناه
سازی و حل مسائل بسیار گسترش یافته است. الگوریتم ژنتیک یکی از زیر مجموعه هاای محاسابات تکااملی1 مای باشاد کاه رابطاه مستقیمی با مبحث هوش مصنوعی2 دارد. در واقع الگوریتم ژنتیک یکی از زیر مجموعه های هوش مصنوعی می باشد.[10]
الگوریتم ژنتیک را میتوان یک روش جستجوی کلی نامید که از قوانین تکامل بیولوژیک طبیعی3 تقلید میکند. الگوریتم ژنتیاک برروی یکسری از جوابهای مسئله به امید بدست آوردن جوابهای بهتر قانون بقای بهترین را اعمال می کند. در هر نسال4 باه کماک فرآیند انتخابی متناسب با ارزش جوابها و تولید مثل جواب های انتخاب شده به کمک عملگرهایی که از ژنتیک طبیعی تقلید شاده-اند، تقریبهای بهتری از جواب نهایی بدست میآید. این فرایند باعث می شود که نسلهای جدید با شرایط مساله سازگارتر باشد.[10]
برای مسیریابی ربات در محیطهای ناشناخته و در حضور موانع ثابت و متحرک، بدون شناخت از موقعیت و تاابع حرکات مواناع، می توان از الگوریتم ژنتیک نیز کمک گرفت و با توجه به این که طول مسیر متغیر است، می توان از ساختار کروموزوم متغیر 5 استفاده نمود -با توجه به اینکه مسیر های مختلف طول متغیری دارند از ساختار کروموزوم با طول متغیر استفاده شده است-.[11]
برای مسیریابی حرکت ربات با توجه به اینکه طول مسیر متغیر است، از ساختار کروموزوم با طول متغیر استفاده شده است. بدین صورت که هر ژن شماره یک گره میانی را در طول مسیر -مسیر تعیین شده توسط هر کروموزوم- بیان میکند. به عبارت دیگر همیشه ژن اول بیانگر نقطه اولیه و ژن آخر بیانگر نقطه هدف است.
در ابتدا یک جمعیت اولیه تصادفی 6 از کروموزومها ایجاد میشود. پس از ارزیابی راه حل های تولید شده در هر تکرار، تعدادی از بهترین کروموزومها به عنوان والدین برای تولید نسل بعدی انتخاب میشوند. سپس فرآیند ترکیب و جهش بر روی کروموزومهای والدین، باعث ایجاد کروموزوم های نسل بعدی میشوند. فرآیند فوق تا جایی که شرط خاتمه ارضاء شده باشد ادامه مییابد. مراحل انجام مسیریابی تا تولید خروجی نیز بصورت شکل -10- انجام خواهد پذیرفت.
