پایان نامه بهینهسازی مسیر ربات‌های هوشمند به کمک الگوریتم PSO
63 صفحه در قالب word
چکیده
مساله مسیریابی روبات‌ها یکی از پرکاربردترین مسائل مهندسی کنترل میباشد. هدف در این مساله یافتن مسیر به گونهای میباشد که با موانع برخوردی نداشته و مسیر کوتاهترین مسیر ممکن باشد. در سال‌های اخیر روشهای مختلفی برای بهینهسازی معرفی شده و مورد استفاده قرار گرفته‌اند. اغلب این روش ها منطبق بر جستجوی طبیعی و برگرفته از روش های موجود در طبیعت هستند. بهینهسازی یافتن بهترین جواب قابل قبول، با توجه به محدودیت‌ها و نیازهای موجود در مساله است. هدف از بهینهسازی تعیین متغیرهای طراحی است، به گونهای که تابع هدف کمینه یا بیشینه شود. بنابرین مهمترین نکته در حل یک مساله انتخاب تابع هدف مناسب است که در مساله مسیریابی روبات عدم عبور از مانع و طول مسیر به عنوان اهداف مدنظر قرار میگیرند.
با پیشرفت در تکنولوژی و صنعت رایانه به ویژه در دهه‌های اخیر، نرم افزارهای متعددی بوجود آمده‌اند که بهره برداری از روش های مختلف بهینهسازی را میسر میسازد. در این پایاننامه از الگوریتم ازدحام ذرات برای یافتن مسیر مناسب استفاده میشود سپس نشان داده میشود که با استفاده از الگوریتم ازدحام ذرات پرورشی میتوان به پاسخهای مناسبتری از جهت برخورد کمتر با موانع دست یافت.
فهرست
1-3- موضوع بهینهسازی و اهمیت آن. 3
1-4- بهینهسازی ازدحام ذرات.. 3
1-5- مروری بر سابقهمسیریابیربات‌های هوشمند. 4
مروری بر بهینهسازی ازدحام ذرات.. 9
2-1- تعریف بهینهسازی ازدحام ذرات.. 9
2-3- الگوریتم بهینه سازی ازدحام ذرات.. 11
2-3-2- مروری بر الگوریتم بهینهسازی ازدحام ذرات.. 12
2-3-3- مزایای بهینهسازی ازدحام ذرات نسبت به روشهای کلاسیک.. 15
2-3-4- مراحل پیاده سازی الگوریتم بهینهسازی ازدحام ذرات.. 16
2-3-5- برخی از نسخه های تغییر یافته بهینه سازی ازدحام ذرات.. 21
توضیح چند الگوریتم پرکاربرد. 29
3-1-2- ساختار الگوریتم‌های ژنتیکی. 30
3-1-4- عملگر انتخاب (Selection ): 31
3-1-5- عملگر آمیزش (Crossover ): 32
3-1-6- عملگر جهش (Mutation ): 34
3-1-7- روند کلی الگوریتم‌های ژنتیکی. 35
3-1-8- روند کلی بهینه سازی و حل مسائل در الگوریتم ژنتیک.. 36
3-1-10- برخی از کاربرد الگوریتم‌های ژنتیکی. 37
3-2- الگوریتم بهینهسازی کلونی مورچه 38
3-2-1- بهینهسازی مسائل به روش کلونی مورچه (ACO) 39
3-2-2- مورچه‌ها چگونه می‌توانند کوتاهترین مسیر را پیدا کنند؟ 40
3-3- الگوریتم زنبور عسل(BA) 44
3-3-1- آیات قرآن در رابطه با زنبور عسل. 44
3-3-3- معرفی الگوریتم زنبور عسل. 46
3-3-4- برخی کاربرد های الگوریتم زنبور عسل در مهندسی. 46
3-3-5- مراحل الگوریتم زنبور عسل. 47
3-3-6- کاربرد الگوریتم زنبور عسل در مقالات.. 47
3-3-7- مزایای و معایب استفاده از الگوریتم زنبور عسل. 47
مسیر یابی ربات با استفاده از الگوریتم بهینهسازی ازدحام ذرات.. 49
4-1- روش های توصیف معادله منحنی مسیر 49
4-2- پروژه مسیریابی به روش تبدیل منحنی به خطهای بهم پیوسته و با استفاده از تکنیک PSO.. 49
4-2-1- تعریف پارامترهای اولیه. 49
4-2-2- محاسبه مسیر بهینه با تکنیک PSO.. 51
فصل اوّل
مقدمه
1-1- تعریف ربات
در حالت کلی ربات به ماشینی اطلاق میشود که بتواند تمام و یا قسمتی از کار یا عملی که بطور طبیعی توسط یک انسان انجام میشود را انجام دهد[1].
امروزه با پیشرفت تکنولوژی در زمینه اتوماسیون صنعتی و همچنین فضانوردی نیاز به ربات‌ها بیش از پیش مورد توجه قرار گرفته است.حتی از ربات‌ها و مسیریابی دقیق آنها در علوم پزشکی و حتی در بیمارستانها نیز برای رسیدگی مداوم مریض استفاده میشود.ربات‌ها باید قادر باشند تا در محیط های گوناگون که غالبا غیر قابل پیش بینی نیز هستند و دارای موانع مختلف مثل صندلی،میز،دیوار،سنگ و... هستند،هوشمندانه عمل کنند وبدون برخورد به آنها، به وظایف مورد نظر رسیدگی کند.
شاید تفاسیری که از وظایف ربات‌هابازگوشد اغراق آمیز به نظر بیاید، ولی آنچه که در کشورهای پیشرفته در زمینه ربات‌ها صورت گرفته است بسیار فراتر از موارد ذکر شده است. در کشوری مثل ژاپن به کمک ربات‌هایی که اصطلاحا انسان‌نما گفته می‌شوند، در بعضی رستورانها و به عنوان خدمتکار مورد استفاده قرار میگیرند واینربات‌ها جدا از اینکه قادرند بدون هیچ اشتباهی غذا راتحویل مشتری دهند، این قدرت را نیز دارند که با مشتری صحبت و غذای مورد نظر مشتری را یادداشت نمایدوبدون شک این پیش پا افتاده ترین وظیفه ربات‌ها در برابر هزاران دستورالعملی است که برای آنها درنظر گرفته میشود.
به عنوان مثال دیگر در کمپانی بنز آلمان، از ربات‌ها در جوشکاری، برش و اتصالات داخلی خودرو وحتی آزمایشات کنترلی خودرواستفاده میشود که با وجود آنها هم هزینه برای کار فرما کاهش می یابد و هم از هر گونه خطای سهوی جلوگیری میشود.
پس با این مثال‌هایی که صورت گرفته است به نظر می‌رسد گفته بعضی از کارشناسان در مورد اینکه قرن بعد،قرن ربات‌هاست، زیاد هم عجیب نباشد.
1-2- تعریف مسیریابی
در میان مباحث مختلف مرتبط با ربات‌های متحرک مساله مسیریابی از اهمیتخاصی برخوردار میباشد. هدف از این مسئله یافتنمسیری است که ربات را از نقطه شروع به نقطه پایان برساند و با موانع موجود در محیط برخورد نداشته باشد. این موضوع از دیدگاه‌های مختلفی می‌تواند مورد بررسی قرار گیرد، به عنوان مثال موانع موجود در محیط می‌توانند ثابت و یا متحرک باشند. از دیدگاهدیگر بهینگی مسیر بدست آمده می‌تواند مورد بررسی قرار گیرد، معیار بهینگی با توجه به نوع مساله تعریف میشود، یافتنکوتاهترینمسیر ممکن، بدست آوردن مسیری که توسط ربات با حداکثر سرعت ممکن پیموده شود و یا ایجاد مسیری که حداکثر فاصله ممکن را از موانع داشته باشد، نمونه‌هایی از معیارهای مختلف بهینهسازی می‌باشند.
1-3- موضوع بهینهسازی و اهمیت آن
در سال‌های اخیر بهینهسازی جزء مهمترین مسائل پیش رو مهندسان، طراحان ومحققان بوده است. با گستردگی مسائل واهمّیت یافتن سرعت در پاسخ وهمچنین عدم کارآیی روشهای گذشته(کلاسیک)، بهینهسازی با الگوریتم‌های هوشمند مورد استقبال بیشتری قرار گرفت.اغلب این روش‌ها منطبق بر جستجوی طبیعی والهام گرفته از روشهای موجود در طبیعت میباشد.در این بین رشد قابل ملاحظه الگوریتم‌هایی نظیر الگوریتم بهینهسازی ازدحام ذرات[1]، الگوریتم وراثتی[2]، الگوریتم کلونی مورچه ها[3] و... غیرقابل انکار میباشد.
منظور از بهینهسازی که در قسمت قبل نیز اشاره شد،فرآیندی است که برای بهتر کردن چیزی دنبال میشود.فکر،ایدهوطرحی که توسط یک مهندس یا دانشمند مطرح میشود،طی فرآیند بهینهسازی بهبود و بهتر میشود.همچنین باید اشاره کرد که در طی فرآیند بهینهسازی باید کلیه شرایط تاثیرگذار بر روی پروژه، بطور کامل مد نظر گرفته شود.البته نباید فراموش شود که بهینهسازی ابزاری ریاضی است که برای یافتن پاسخ بسیاری از پرسش‌ها در خصوص چگونگی راه حل مسائل مختلف بکار می رود که البته در این پروژه به کمک نرم‌افزار متلب، بهینهسازی صورت گرفته است.
1-4- بهینهسازی ازدحام ذرات
بهینهسازی ازدحام ذرات یکی از جدیدترین روشهای جستجو است که در چند سال اخیر مورد توجه دانشجویان ومهندسان قرار گرفته است و در این پروژه نیز بدلیل سادگی وهمچنین بهبود در عملکرد فرآیند بهینهسازی،مورد استفاده قرار گرفته است.
1-4-1- تاریخچه تحقیق
روش بهینهسازی ازدحام ذرات،عضوی از روشهای هوش جمعی است که در سال1995 میلادی اولین بار توسط کندی[4] و ابرهارت[5] با شبیه‌سازی رفتار اجتماعی پرندگان و ماهی‌ها، به عنوان یک بهینه‌ساز معرفی گردید[2].در ابتدا الگوریتمبهینه سازی ازدحام ذرات[6]به منظور کشف الگوهای حاکم بر پروازهمزمان پرندگان و تغییر ناگهانی مسیرآنهاوتغییرشکل بهینه دسته بکار گرفته شد[3]. برای برخی از حیوانات که بصورت گروهی زندگی می‌کنند از جمله دسته‌های ماهی(دسته‌های پرندگان)،رفتارهای پیچیده‌ای به هنگام حرکت قابل مشاهده هستند این در حالی است که هرکدام از اعضای جمع به اطلاعات محدودی دسترسی دارند وفقط از موقعیت عده اندکی از همسایگانشان خبر دارند.
روش بهینهسازی ازدحام ذرات یک الگوریتم جستجوی اجتماعی است واساس آن بر تکرار جستجو در محیط مسئله توسط جمعیت تصادفی میباشد که در هر تکرار، تابع شایستگی مورد ارزیابی قرار میگیرد وسپس بهترین موقعیت تمام پرندگان (کلیه ذرات موجود)درآن نسل در دوحافظه(بهترین موقعیت محلی،بهترین موقعیت کلی)قرار می گیرند.سپسدر نسل بعد جمعیت جدیدی جایگزین جمعیت قبلی می‌شوند.در واقع حرکت پرندگان در این الگوریتم به دو عامل حرکت فردی وحرکت جمعی وابسته است.همانطور که در فصول بعد نیز اشاره میشود؛ حرکت پرندگان(ذرات) به دو عامل وابسته است که یکی عامل موقعیت ودیگری عامل سرعت میباشد.الگوریتمبهینه سازی ازدحام ذراتذاتا یک الگوریتمپیوسته است. برای حل مسائل گسسته،نسخه باینری آن نیز ارائه شد که در چند سال اخیر این نوعبهینه‌سازی ازدحام ذرات،با ارائه روش نوین آن دارای عملکرد بهتری گشته است که در فصل‌های بعد مزایای روش نوین باینری نسبت به روشهای سابق آن مورد بحث قرار خواهد گرفت.
1-5- مروری برسابقه مسیریابی ربات‌های هوشمند
بنا به گفته اورلساهین1،از متخصصان معروف در زمینه رباتیک، تعداد زیادی استراتژی خاص برای مسیریابیربات‌ها در زمینه‌های مختلف ربات‌های نقلیه ارائه شده است. بطور مثال فنگ وی ژینگ2،الگوریتمی برای هماهنگی بیشتر ربات‌های هوشمند در زیر آب در جهت تراکم، آرایش گروهی بهترو ازدحام بهینه‌ی ربات‌ها ارائه داده است.
بهینهسازی ازدحام ذرات بوسیله ذرات تعریف شده در سیستم فضای مسئله ودر جهت یافتن جواب بهینه، شروع به جستجو می کنند وبا توجه به فرمول‌های سرعت و مکان که قبلا اشاره شده است، جواب بهینه را می‌یابند. در هدایت یک ربات هوشمند، بمنظور رسیدن به مقصد نهایی،ربات باید از هرگونه برخورد با مانع و همچنین از خارج شدن محدوده مسئله جلوگیری کرد.در الگوریتممسیریابیربات‌ها باید به پارمترهایمکانی،تجسم موانع ونیز پیمودن مسیر حرکت بصورت پیوسته(از نقطه مبدا تا مقصد و بدون برخورد با موانع)توجه نمود.
آقای هاکر3 در مقاله‌ای در زمینه استرتژی جدید مسیریابی، که در سال 2008 میلادی ارائه کرد، استفاده از ماتریس و مسیریابی بر اساس اشغال خانه های ماتریس (بمنظور شبیه سازی بهتر مسیر) مورد توجه قرار داد که در آن منظور از ماتریس همان محدوده مسالهو خانه‌های ماتریسی همان نقاط موجود در فضای مساله میباشد. لذا با این ایده میتوان برای کلیه نقاط موجود درون مساله، مختصات ویژه‌ای در نظر گرفت و مکان لحظه به لحظه ربات را بخوبی مورد بررسی قرار داد. این نکته را نیز باید اشاره کرد که در دنیای حقیقی وجود موانع غیر قابل پیش بینی ملموس تر و دارای امکان پذیری بیشتر میباشد.البته آقای هاکر این ایده را در ارتباط با پروژه عملی دکتر راجا در( که سال 2011 .م در مقاله ای بیان شد) مورد محیطهای دینامیکی مسیریابی ربات ارائه داده بود.] 4 [
از مهندسان ایرانی نیز خانم مهندس احمدزاده و آقای قنواتی در سال 2012.م در مقاله‌ای که ارائه دادند، توانستند به روش مناسبی بمنظور مسیر یابی بهینه ربات‌های هوشمند در محیطهای غیرقابل پیش‌بینی دست یابند. این کار بوسیله وابستگی توابع محاسبه شده برای بهترین جمعی ومکانی (برای هر ذره) انجام شد. نتایج حاصله از این مقاله باعث اثراتی مثبت در مسیریابیربات‌ها درمحیطهای دینامیکی شد. [5]
قسمتی از تکنیکهای قدیمی در مسیریابی، مربوط به تکنیکهای هوشمند ذرات بوده است که در بسیاری از آنها تکنیک مورد نظر منحصرا بهینه سازی ازدحام ذراتبوده است. در همین راستا آقای کیانگژائو از مهندسان چینی ومتخصصین زمینه بهینهسازی ازدحام ذرات در مقاله علمی خود که درسال 2005 میلادی ارائه شد، بی‌نظمی موجود در جستجوی محلی ذرات سیستم در بهینه سازی ازدحام ذراترا تعریف و روشی در بهبود بی‌نظمی و همچنین سرعت همگرایی ارائه داد.دقیقا یک سال بعد از روش پیشنهادی آقای ژائو، آقای کای‌یو[7]، روشی مبنی بر اصلاح رویکرد بهینه سازی ازدحام ذراتدر مساله مسیریابی ارائه کرد که در آن هماهنگ شدن ذرات بهینه سازی ازدحام ذراتباعث جلوگیری از هرگونه مشکلی در جستجوهای سراسری ومحلی ذرات شد و این امر در تسریع سرعت همگرایی و رسیدن جواب بهینه بسیار سودمند بود.
اکثر روشهای موجود در مسیریابی، محیط در آن بصورت شناخته شده میباشد.گرچه در واقعیت محیطها غیر قابل پیش بینی هستند، ولی به کمک روشهای ساده و نیز تغییرات سادهدر برنامه کلی، می توان دید مناسبی نسبت به مسیر و موانع پیش رو داد.
در این پروژه با تعریف مساله در محیط ماتریسیوهمچنین در نظر گرفتن محدودیتهای مسیر، سعی شده است تا در محیط دوبعدی نرم افزار متلب، روند بهینه ی مسیر ربات‌های هوشمند را با کمکبهینه‌سازی ازدحام ذرات بهبود بخشید.
هدف اصلی در مسیریابی، حرکت از مبدا به مقصد بدون برخورد با موانع میباشد.همچنین مسیر موجود باید حتما بهینه باشد.تعریف بهینه در مسیریابی همان کمینه کردن مسیر و به عبارتی دیگر، بهترین مسیر ممکن بری رسیدن به مقصد میباشد.پس ربات‌ها بصورت یک گروه به کمک بهینهسازی ازدحام ذرات، شروع به جستجو مسیر برای رسیدن به مقصد می نماید.
پس با توجه به تعاریف صورت گرفته برای نوشتن یک مسیر صحیح برای ربات‌های هوشمند باید قوانین زیر را مد نظر داشت:
- نقطه آغاز و پایان حرکت باید معین گردد.
- ربات‌ها باید به مقصد نهایی حتما برسند.
- ربات‌ها نباید از محدوده ماتریسی خارج شوند.
- در هنگام حرکت و در طول مسیر هیچ برخوردی با موانع صورت نگیرد.
- در صورت عبور از محدوده ماتریس برای ربات‌ها قانون پنالتی منظور گردد. به عبارت دیگر تابع هزینه ای برای جریمه ی ربات‌ها منظور گردد تا در صورت تخلف جریمه،و در صورت حرکت صحیح تشویق صورت گیرد.
یک طرح ساده مسیرمسئله باعث حرکت از نقطه ی آغازین به پایانی میشود.غالبا این طرحها در روش بهینهسازی ازدحام ذرات بصورت تصادفی ایجاد می شوند. بدین معنا که، می توان آرایه ای تصادفی از حرکت ربات‌ها تولید وبدون در نظر گرفتن بهینهسازی و یا موانع موجود،طرح اولیه مسیر را به ربات‌هاداد.در مرحله بعد ربات‌ها با پیروی از فرمانده، سعی به بهینهسازی می‌نمایند.در مسائل رباتیک منظور از فرمانده، ربات پیشرو نسبت به سایر ربات‌هامی‌باشد.
1-6- روشهای مسیریابی
روشهای مسیریابی ربات‌های متحرک را میتوان به دو دسته کلی روشهای خارج خط و روی خط تقسیم نمود. در روش خارج خط (مسیریابی محلی) فرض بر آنست که شکل و موقعیتهندسی موانع موجود در محیط حرکت ربات مشخص است و بیشترروش‌های خارج خط محیط حرکت ربات توسط یک گراف مدل میشود و سپس نقاط شروع و پایان حرکت ربات به این گراف افزوده می‌شوند، در گام بعد توسط روشهای کلی جستجوی گراف میتوان مسیربهینه را که نقطه شروع را به نقطه پایان متصل می‌کند بدست آورد و سپس مسیر بدست آمده در گراف را توسط روشهای موجود به محیط حرکت ربات منتقل نمود. در روش مسیریابی روی خط (مسیریابی سراسری)هیچگونهاطلاعاتی در مورد وضعیت جغرافیایی محیط،شکل و موقعیت موانع اطراف خود را بصورت محل شناسایی می‌کند[1]. به عبارتی مسیریابی سراسری بر اساس اطلاعات دریافتی از محیط در ابتدای جستجو میباشد ومسیریابی محلی بر اساس اطلاعات دریافتی از سنسورها در حین حرکت ربات در محیط واقعی می‌باشدکه در این کلاس سنسورها مانع از برخوردربات‌ها با موانع پیشرو می‌شوند.
الگوریتم‌هایی که به منظور هدایت ربات توسط روش روی خط مورد استفاده قرار میگیرند عبارتند از: روشهای فازی، الگورتیم‌های ژنتیک، شبکه‌های عصبی و یا ترکیبی از روشهای مذکور، مزیت این روش آنست که هدایت ربات را در محیطهای ناشناخته از قبیل کرات فضایی و یا داخل لوله های نفتی که امکان تهیه نقشه کلی محیط وجود ندارد ممکن میسازد اما نقطه ضعف آنها را در مقایسه با روش های خارج خط کند بودن الگوریتم میباشد که این موضوع به دلیل زمان لازم جهت شناسایی محیط اطراف ربات میباشد .
بطور مثال در شکل (1-1)[6] ربات مسیر درست را تشخیص داده و هرچه تعداد برخورد کمتری با موانع داشته باشد، هوشمندتر است.
1-7- اهداف پروژه حاضر
در این پروژه با بکارگیری روش مبتنی بر یافتن نقاط شکست مسیر و الگوی بهینهسازی ازدحام ذرات سعی شده است تا مسیریابی ربات‌ها به کمک نرم افزار متلب،بهینه ودر جهت بهبودمسیر آن گام بلندی برداشته شود.
1-8- مرور مختصر فصل‌ها
درفصل دوم این پایان نامه بطور کامل کاربردهایبهینه سازی ازدحام ذراتپیوسته و همچنین مزایای آن نسبت به الگوریتم ژنتیک وسایرالگوریتم‌های موجود بیان میگردند همچنین در فصل سوم به توضیح چند الگوریتم پر کاربرد دیگر پرداخته و در فصل چهارم ساختار کلی بهینه سازی ازدحام ذراتگسسته وروش‌های جدید که درچند سال اخیر ابداع شده مورد بررسی قرار خواهند گرفت ودر انتها الگوریتم پروژه پایان نامه مطرح و مورد بحث و بررسی قرار میگیرد ارائه می‌گردد.
ممکن است هنگام انتقال از فایل ورد به داخل سایت بعضی متون به هم بریزد یا بعضی نمادها و اشکال درج نشود ولی در فایل دانلودی همه چیز مرتب و کامل است
متن کامل را می توانید در ادامه دانلود نمائید
چون فقط تکه هایی از متن برای نمونه در این صفحه درج شده است ولی در فایل دانلودی متن کامل همراه با تمام ضمائم (پیوست ها) با فرمت ورد word که قابل ویرایش و کپی کردن می باشند موجود است
پایان نامه بهینهسازی مسیر ربات‌های هوشمند به کمک الگوریتم PSO
