توضیحات
پروژه متلب مسیریابی گروه ربات متحرک با استفاده از الگوریتم مورچگان(ACO)
یکی از چالش های بنیادی و اساسی برای ربات های متحرک که امروزه به طور ویژه مورد توجه و مطالعه محققین قرار گرفته است برنامه ریزی برای شناسایی مسیر می باشد. مسیریابی گروه ربات ها شامل، برنامه ریزی مسیریابی هر ربات، با در نظر گرفتن عدم برخورد ربات ها در فضای حرکتی آنها همراه با درنظرگرفتن کمترین حجم محاسبات مورد نیاز است. در سال های اخیر الگوریتم های تکاملی و اکتشافی به طور گستردهای در حالت توسعه و تکامل بوده و از آنها به عنوان ابزار جستجو و بهینه سازی استفاده شده است. در این پروژه با رویکردی جدید مبتنی بر الگوریتم بهینه سازی مورچگان مسئله برنامه ریزی برای شناسایی مسیر برای گروه ربات ها(multi-robot navigation ) حل شده است.
علم رباتیک:
رباتیک شاخه ای از فناوری است که به طراحی، ساخت، کاربرد ربات ها و همچنین سیستم های کامپیوتری مرتبط با کنترل و پردازش اطلاعات ربات ها می پردازد. این فناوری ها با ماشین های مکانیزه شده که می توانند در فرآیندهای تولید و یا محیط های خطرناک جایگزین انسان شوند و یا تداعی کننده رفتار انسان باشند سروکار دارد. بسیاری از ربات های امروزی از طبیعت الهام گرفته شده اند. مفهوم و خلق ماشین هایی که بتوانند به صورت خود مختار عمل کنند، به زمان های قدیم باز می گردد اما تحقیقات پیرامون عملکرد و ظرفیت های استفاده از ربات ها تا اواخر قرن ۲۰ میلادی به طور عمده ای گسترش نیافتند.
در صنایع گوناگون امروز، ماشین ها و ربات ها نقش ویژه ای داشته و کارخانه های بزرگ به سمت تمام مکانیزه شدن، اتوماسیون و مهم تر از همه خودمختاری پیش می روند. به همین دلیل، در کشورهای صنعتی کمتر کارخانه مهمی را می توان یافت که در آن از ربات استفاده نشود. پیش بینی می شود که رباتیک یکی از ده صنعت برتر آینده باشد. نیاز امروز صنایع ایجاب می کند که بسیاری از امور توسط ربات ها و با حداقل دخالت انسان (و یا حتی بدون دخالت نیروی انسانی) انجام پذیرد. در صنعت، گاهی اوقات نیاز است که کارهایی صورت پذیرد که انسان به هیچ وجه توانایی انجامش را ندارد. در این موارد ربات ها می توانند بهترین راه حل و مددرسان آدمی باشند. همچنین، کارخانه ها برای افزایش سرعت، کیفیت، دقت و هزینهی پایین تر به سمت رباتیکی کردن تمامی قسمت های کارخانه پیش می روند و در بعضی از قسمت ها که برای انسان خطرناک است، مانند جوشکاری و رنگ پاشی و سموم شیمیایی و … ناچار به استفاده از ربات می شوند.
به طور اجمالی می توان گفت، مزایای به کار گیری ربات ها در بخش صنعت عبارت است از: افزایش بهره وری، افزایش تولید، بهبود کیفیت کار، افزایش دقت، جلوگیری از اتلاف نیروی انسانی، افزایش سرعت، کاهش هزینه، کاهش ضایعات، چند منظوره بودن، هوشمند بودن، عدم خستگی و… علاوه بر صنعت، از دیگر زمینه های کاربرد ربات می توان موارد پزشکی، آموزشی، سرگرمی، امدادرسانی و نظامی را نام برد.
حرکت گروهی موجودات در طبیعت:
حرکت دسته ای یا توده ای ارگانیسم ها را می توان در طبیعت، در بسیاری از موجودات زنده همانند باکتری ها، زنبور ها، پرندگان، مورچه ها و پستانداران، یافت.
چنین رفتاری می تواند ناشی از ساز و کارهای متفاوتی باشد. به عنوان مثال، موجودات منفرد به صورت مستقیم و بی درنگ به نشانه های محیطی محل، مانند تجمع مواد غذایی با توزیع بعضی مواد شیمیایی که ممکن است توسط موجودات منفرد دیگری ایجاد شده باشند واکنش می دهند. این واکنش جذب شدن توسط مواد شیمیایی نامیده می شود. این مکانیزم توسط بسیاری از ارگانیسم ها، مانند باکتری ها یا حشرات مورد استفاده قرار میگیرد. به عنوان مثال مورچه هایی که پشت سر هم صف های طولانی ایجاد کرده اند یا زنبورهای عسل که به صورت خوشه ای قرار گرفته و پرواز می کند. در مثالی دیگر، موجودات منفرد ممکن است به طور مستقیم به موجودات دیگر(بیشتر در حالاتی که نشانه هایی درباره ترک فعالیت های این موجودات به چشم می رسد) عکس العمل نشان دهند. این حرکت رفتار در بعضی ارگانیسم های با مراتب بالاتر مانند ماهی ها، پرنده ها یا گله های پستانداران وجود دارد. این رفتار دسته ای، به علت فوایدی که در آن وجود دارد، مانند فرار از دست شکارچی ها یا افزایش شانس پیدا کردن غذا، تکامل پیدا کرده است.
شکل مهاجرت گروهی پرندگان.
شکل همکاری مورچه ها در حمل طعمه
گروه ربات ها:
حرکت گروهي موجودات مختلف، محققان را به فکر استفاده از گروه های رباتی، به جاییک ربات برای انجام عملیات های مختلف رهنمون داده است. با نظر به این که اهدافی همچون بالا بردن سرعت اجرای عملیات و کاهش هزینه ها همواره جز موارد اصلی در طراحی و ساخت ربات ها هستند، یکی از بهترین راه ها برای رسیدن به اهداف مذکور، استفاده از چندین ربات ساده و با توانایی های کمتر به جاییک ربات با توانایی های بالا است.
استفاده از یک گروه ربات مزایای مختلفی نسبت به استفاده از یک ربات به تنهایی دارد که می توان به موارد زیر اشاره کرد.
- جبران کمبود توانایی های یک ربات (عامل) به صورت منفرد.
ممکن است امکان نصب تمامی امکانات مورد نظر را بر روی یک ربات مقدور نباشد. بنابراین میتوان هریک از تجهیزات را بر روی یک ربات قرار داد. بدین ترتیب هر ربات مسئولیتی مستقل بر عهده خواهد داشت. به طور مثال می توان حسگرها را بر روییک ربات قرار داده و دوربین را بر روی رباتی دیگر و به همین ترتیب، باقی موارد را بر روی ربات های دیگر نصب نمود. در صورتی که امکان استفاده از ربات با اندازه بزرگ مقدور نباشد، این مشکل حل خواهد شد. مهم ترین برتری های سیستم های رباتیک چند عامله نسبت به تک عامله علاوه بر مورد فوق عبارت اند از:
- افزایش بهره وری و سرعت انجام کار
- افزایش گستردگی عملکرد تیم رباتی.
- امکان ادامه عملیات گروه در هنگام رخ داد خرابی برای یک عامل
- کاهش هزینه های ناشی اتفاقات غیر مترقبه و خرابی های احتمالی
- صرفه جویی در مصرف انرژی.
کاربردهای رباتیک چند عامله:
از رباتیک چند عامله(تیم های رباتی) در زمینه های زیادی می توان استفاده کرد. مهم ترین کاربردهای این فناوری در ادامه مورد بررسی قرار گرفته است:
صنایع خودروسازی:
از ربات ها به طور گسترده در خط تولید صنایع خودروسازی استفاده می شود. در این خطوط ربات ها با همکاری یکدیگر، کار های جوشکاری، سوراخ کاری، برش کارت و مونتاژ قطعات قسمت های مختلف خودرو را انجام می دهند.
شکل خط تولید خودکار خودرو.
انجام عملیات جستجو در محیط وسیع:
به طور يقين استفاده از چند ربات جهت جستجو شی با هدف خاصی در یک فضای گسترده نسبت به یک ربات زمان کمتری می برد. شکل زیر نمونه ای از این کاربرد را نشان می دهد.
شکل عملیات جستجوی توسط چند ربات.
حفاظت فیزیکی محیط:
از یک تیم ربات می توان جهت حفاظت از یک محیط استفاده کرد. به عنوان مثال با نصب دوربین بر روی چند ربات و گشت زنی در محیط مورد نظر می توان ورود و خروج افراد یا حیوانات را کنترل کرد.
شکل یک ربات در حال گشت زنی در محدوده ساحلی.
امداد و نجات:
از یک تیم ربات می توان جهت کمک به مصدومانی که کمک رسانی به آنها دشوار است، حمل مصدومان، جابجایی اشیاء در حوادث مختلف مانند سیل، زلزله، آتش سوزی استفاده کرد.
شکل جستجوی یک تیم رباتی برای پیدا کردن مصدومان.
شکل کمک رسانی تیم ربات به یک مصدوم.
عبور از موانع:
یکی دیگر از کاربردهای تیم ربات عبور از مناطق بسیار ناهموار است. در محیط های بسیار ناهموار ربات ها با اتصال و کمک به یکدیگر می توانند از موانع مختلف عبور کنند.
شکل عبور از موانع و کمک ربات ها به یکدیگر.
مسابقات ربوو کاپ:
واژه روبوکاپ برگرفته از کلمات ربات فوتبالیست و جام جهانی است که عنوان مسابقاتی بین المللی در زمینه دانش رباتیک و هوش مصنوعی است که به صورت سالیانه توسط فدراسیون بین المللی روبوکاپ برگزار می شود.
نمونه ای از ربات مورد استفاده در سیستم های چند عامله:
نمونه های مختلفی ربات برای سیستم های چند عامله وجود دارد که هر کدام ویژگی خود را دارد. به عنوان مثال ربات متحرک خپرا، رباتی باشکلی استوانه ای و دارای سنسورهای مختلف در اطراف خود می باشد و قابلیت نصب دوربین و بازو را دارد. فرمان کنترل کننده به دو چرخ ربات اعمال می شود و بدین طریق حرکت و هدایت ربات میسر می گردد.
شکل نمونه های مختلف ربات خپرا برای سیستم های چند عامله.
مسیریابی ربات متحرک:
هدف از مسیریابی ربات متحرک یافتن مسیری عاری از برخورد در محیطی با وجود اشیاء است. این مسیر با برآورده کردن ضوابط بهینه سازی خاصی از موقعیت اولیه معینی آغاز شده و به نقطه ی پایانی مورد نظر ختم می شود. مسیریابی ربات متحرك یکی از مهم ترین مسائل ناوبری ربات است. روش های مسیریابی ربات ها را می توان بر اساس موقعیت های مختلفی دسته بندی کرد. مساله مسیریابی بر اساس محیطی که ربات در آن قرار گرفته است به دو شکل زیر تقسیم می شود:
١. مسیریابی در محیط ایستا که فقط دارای اشیاء ثابت است.
- مسیریابی در محیط پویا که دارای اشياء ثابت و متحرک است.
هر کدام از این دو دسته را بر اساس اطلاعات ربات در باره ی محیط پیرامونش می توان به دو زیر گروه تقسیم کرد:
١. مسیریابی ربات با داشتن اطلاعات کامل از محیط که ربات محل اشياء را قبل از شروع به حرکت می داند. در این حالت می توان مسیر ربات را به طور کلی بهینه کرد زیرا تمام محیط شناخته شده است.
- مسیریابی ربات در محیط ناشناخته یا نیمه شناسایی شده که در این روش ربات با استفاده از حسگرها اطلاعات اندازه و شکل اشیاء و محیطی که در آن قرار گرفته را می سنجد و سپس از این اطلاعات برای مسیریابی استفاده می کند.
در شکل زیر نمودار دسته بندی روش های مسیریابی ربات مشاهده می شود.
شکل انواع روش های مسیریابی.
مسیریابی چندین ربات:
تحقیق بر روی ربات های متحرک تا به امروز بر روی حرکت امن ربات در محیط متمرکز شده بوده است. وظیفه ربات های متحرک به طور کلی به مسیریابی و یا دوری از موانع برای یک ربات با رسیدن به یک هدف خاص محدود شده است. در کاربردهای دنیای واقعی تعداد بیشتری ربات باید بتوانند اطلاعات محیط کاری ناشناخته و مأموریت های پیچیده را به اشتراک بگذارند. به همین دلیل باید بین ربات ها همبستگی وجود داشته باشد.
بهینه سازی :
مبحث بهینه سازی در بسیاری از علوم از جمله رباتیک کاربرد فروان دارد. هدف از بهینه سازی یافتن بهترین جواب قابل قبول، با توجه به محدودیت ها و نیازهای مسئله است. الگوریتم های فراابتکاری یا فراتکاملی یا فراکتشافی نوعی از الگوریتم های تصادفی هستند که برای یافتن پاسخ بهینه به کار می روند.
الگوریتم کلونی مورچگان(ACO)
الگوریتم کلونی مورچگان(ant colony optimization به اختصار ACO) زیر مجموعه الگوریتم های فراابتکاری بر پایه جمعیت می باشد. این الگوریتم از موفق ترین و سازمان یافته ترین تکنیک های الگوریتمی براساس رفتار مورچه ها می باشد و موفقیت آنها توسط طیف گسترده ای از مسائل مختلف که از این تکنیک استفاده نموده اند، اثبات شده است.
مورچه ها رفتار اجتماعی پیچیده ای را از خود نشان می دهند که مدت ها است توجه انسان را به سمت خود جلب کرده است. یکی از بارزترین رفتارهای قابل مشاهده، تشکیلاتی است که در اصطلاح مسیرهای تردد مورچه ها نامیده می شود. تعداد قابل توجهی از محققان به مطالعه جزئیات رفتار مورچه ها می پردازند. یکی از جالب ترین الگوهای رفتاری نشان داده شده توسط مورچه ها، توانایی آنها در پیدا کردن کوتاه ترین مسیر می باشد.
زیست شناسان به طور تجربی نشان داده اند که این عمل با استفاده از ارتباطی بر اساس فرمون که یک ماده شیمایی بوده است و مورچه ها می توانند آن را بر روی زمین به جا گذاشته و همچنین آن را حس کنند، امکانپذیر می باشد. این همان الگوی رفتاری است که دانشمندان کامپیوتر از آن برای توسعه الگوریتم ها در حل مسائل بهینه سازی الهام گرفته اند. اولین تلاش ها در این جهت در اوایل دهه ۹۰ ظاهر شد و از آن زمان به بعد، این ایده و ایده های مشابه محققان زیادی را به سوی خود جلب نمود و نتیجه حاصل از این تلاش های تحقیقاتی، منجر به ظهور تکنیکی تحت عنوان روش بهینه سازی مبتنی بر کلونی مورچگان گردید.
الگوریتم کلونی مورچگان و هوش تجمعی:
الگوریتم کلونی مورچگان زیر مجموعه هوش تجمعی می باشد.
هوش تجمعی هوشی است حاصل از یک جمعیت که تک تک اعضا به تنهایی نمی توانند این هوش را به وجود آورند. برای مثال فرض کنید گروهی به دنبال گنج می گردند. هر یک از اعضای گروه یک فلزیاب و یک بی سیم دارد که می تواند مکان و وضعیت کار خود را به همسایگان نزدیک خود اطلاع بدهد. بنابراین هر یک متوجه می شوند آیا همسایگانشان به گنج نزدیک هستند یا نیستند. پس اگر همسایه ای به گنج نزدیک تر بود می توان به طرف او حرکت کرد. با چنین کاری شانس برای رسیدن به گنج بیشتر می شود و همچنین گنج زودتر از زمانی که یک نفر باشد، پیدا می شود. این یک نمونه ساده از رفتار جمعی و گروهی است که افراد برای رسیدن به یک هدف نهایی همکاری می کنند. این روش کارامدتر از زمانی است که افراد جداگانه فعالیت کنند. ازدحام یا گروه را می توان به صورت مجموعه ای سازمان یافته از گماشته ها یا موجوداتی تعریف کرد که با یکدیگر همکاری میکنند. در کاربردهای محاسباتی، هوش ازدحامی از موجودات یا گماشته هایی مانند مورچه ها، زنبورها، موریانه ها، ماهی ها، پرندگان، و یا حتی چکه های آب در رودخانه، الگو برداری می شود. در این نوع اجتماعات هر یک از موجودات یا گماشته ها ساختار تستبأ ساده ای دارند ولی رفتار گروهی آنها پیچیده به نظر می رسد. رفتار کلی یک تجمع، به گونه ی غیر خطی از ترکیب رفتارهای تک تک اجتماع بدست می آید. یا به زبانی دیگر،یک رابطه ی بسیار پیچیده میان رفتار گروهی و رفتار فردییک اجتماع وجود دارد. رفتار گروهی، تنها وابسته به رفتار فردی افراد اجتماع نیست بلکه به چگونگی عمل متقابل و تعامل میان افراد نیز وابسته است. عمل متقابل بین افراد، تجربه افراد در باره پیرامون را افزایش می دهد و مایة پیشرفت اجتماع میشود.
اصلی ترین عامل در هوش ازدحامی جمعیت می باشد، در واقع باید جمعیتی وجود داشته باشد، همچنین بین اعضاء جمعیت همکاری باشد. شرط لازم برای وجود همکاری ارتباط است و شرط لازم برای وجود ارتباط تبادل اطلاعات می باشد. برای تبادل اطلاعات یک جریان اطلاعاتی لازم است در واقع مسیری برای انتقال اطلاعات باید طراحی شود. در هر جامعه ای برای همکاری اصولی و صحيح، «خود ترتیبی» لازم است. خود ترتیبی یعنی اعضای جمعیت به قواعدی پایبند باشند که خود لازمه وجود همکاری بین اعضا جمعیت می باشد. اگر جریان اطلاعاتی و خود ترتیبی در جامعه ای وجود داشته باشد، حتما در آن جامعه هوش ازدحامی وجود دارد.
یکی از مظاهر جالب هوش ازدحامی مغز ما می باشد. مغز ما مجموعه ای از میلیاردها سلول عصبی تشکیل شده است که هیچ کدام به تنهایی قابلیتی ندارند. ولی از گردهمایی این سلول های عصبی در مغز، سبب می شود که مغز ما از قوی ترین ابر کامپیوترها نیز قوی تر شود.
مورچه ها با همکاری یکدیگر، کوتاه ترین مسیر را میان لانه و منابع غذایی پیدا می کنند. هر کدام از مورچه ها، به تنهایی قادر به انجام چنین کاری نیستند، اما با همکاری و پیروی از چند اصل ساده، بهترین راه را پیدا می کنند.
الگوریتم بهینه سازی مورچه ها که در سال ۱۹۹۲ توسط مارکو دوریگو و در رساله دکتری وی مطرح شد، یکی از بارزترین نمونه ها برای روش های هوش جمعی است. این الگوریتم از روی رفتار جمعی مورچه ها الهام گرفته شده است. این الگوریتم جزء روش های هوش محاسباتی، زیر مجموعه هوش ازدحامی طبقه بندی می شود. شکل زیر نمونه ای از رفتار جمعی مورچه ها در طبیعت را نشان می دهد.
شکل نمونه ای از رفتار جمعی مورچه ها در طبیعت.
آنچه بنیان فکری الگوریتم مورچگان بر آن بنا شده است را می توان به سادگی و در یک جمله بیان نمود، مورچه ها در بین موانع و محدودیت های موجود در طبیعت همیشه از بین راه های متفاوت برای رسیدن به غذا، بهینه ترین راه را انتخاب می کنند.
رفتار مورچه ها برای پیدا کردن کوتاه ترین مسیر بین غذا و لانه توسط گاس، زیست شناس و حشره شناس، مورد ارزیابی و بررسی قرار گرفت. مورچه ها در مسیر خود ماده شیمیایی به نام فرومون ترشح می کنند.
همانطور که در شکل زیرنشان داده شده است مورچه ها وقتی سر دو راهی مسیر کوتاه تر و طولانی تر قرار می گیرند، بر اساس میزان فرومون استشمام از هر مسیر، یک انتخاب مسیر احتمالی انجام می دهند. به این ترتیب احتمال انتخاب مسیرهای دارای فرمون زیاد، به تدریج افزایش می یابد. بعد از مدتی، اکثر مورچه ها کوتاه ترین شاخه را انتخاب می کنند و این احتمال با افزایش تفاوت طول مسیرها، افزایش می یابد.
شکل رفتار مورچه ها در آزمایش گاس.
مورچه هایی که ابتدا برای یافتن غذا شروع به حرکت می کنند نمی توانند الزاما کوتاه ترین مسیر را انتخاب کنند. انتخاب مسیرهای جدید می تواند منجر به یافتن مسیرهای کوتاه تر بشود و درنهایت منتهی به یافتن کوتاه ترین مسیر می شود. فرومون به تدریج تبخیر می شود. این یکی از ضروریات پویا بودن الگوریتم است. انتقال از مسیرهای کوتاه به مسیرهای کوتاه تر بدون تبخیر فرومون در مسیرهای قدیمی امکان پذیر نخواهد بود.
این الگوریتم به دلیل رفتار پویا می تواند در صورت وقوع خرابی در مسیر، با یافتن مسیر جایگزین با آن مقابله کند. همچنین اگر تغییر در مسیر ایجاد شود الگوریتم خود را با تغییرات هماهنگ می کند. برای مثال اگر سنگی در مسیر مورچه ها قرار داده شود، مورچه ها آن را دور زده و مسیر کوتاه جدیدی را در کنار آن پیدا می کنند.
شکل مقابله مورچه ها هنگام وجود مانع در مسیر.
مزیت های الگوریتم مورچگان(ACO):
تبخیرشدن فرومون و احتمال تصادف به مورچه ها امکان پیدا کردن کوتاه ترین مسیر را می دهند. این دو ویژگی باعث ایجاد انعطاف در حل هر گونه مسئله بهینه سازی می شوند. همچنین این بهینه سازی بر گرفته از طبیعت می باشد و همانطور که بیان شد، مورچه ها با استفاده از فرومون، قادر به پیدا کردن کوتاه ترین مسیر هستند.
کاربردهای الگوریتم مورچگان:
الگوریتم کلونی مورچگان، کاربردهای فراوانی در مسائل مختلف اشاره کرد.
- مسیریابی
- تخصیص
- زمان بندی
- زیر مجموعه
- یادگیری ماشین
- مسیریابی شبکه
- کوتاه ترین ابر توالی مشترک.
در این پروژه مسیریابی گروه ربات ها (multi-robots) در محیط پویا با استفاده از الگوریتم مورچگان(ACO) در نرم افزار متلب انجام شده است.
