بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
الگوريتم جامع بهينه سازيِ مسير حرکت ربات در حضور موانع بر مبناي الگوريتم ژنتيک
چکيده
مبحث بهينه سازي مسير حرکت رباتهاي متحرک، امروزه جايگاه ويژهاي در بين محققان و تحليل گران علم رباتيک پيدا کرده است . در اين مقاله سعي شده روشي بر مبناي الگوريتم ژنتيک ، براي يافتن مسير بهينه حرکت يک ربات متحرک در يک محيط کاري با موانع استاتيک ارائه شود. بر اين اساس ابتدا محيط کاري ربات و موانع موجود در آن به روش تقسيم سلولي مدل ميشود. سپس با استفاده از الگوريتم جامعِ بهينه سازيِ طراحي شده، بهترين مسير هم از نظر مسافت طي شده و هم از نظر عدم برخورد با موانع موجود در محيط بدست ميآيد. و در نهايت مسير بدست آمده در اختيار سيستم هدايت ربات قرار ميگيرد.
کلمات کليدي :مسيريابي سراسري، موتورهاي جستجو، الگوريتم ژنتيک ، اجتناب از موانع .
١- مقدمه
ربات هاي متحرک، امروزه کاربردهاي وسـيعي يافتـه انـد. صـنايع مختلفـي از جمله صنايع هسته اي، تحقيقات فضـايي، صـنايع معـدني، صـنايع نظـامي و... حوزههاي بسيار وسيعي براي بکارگيري ربا هاي متحرک ايجاد کردهاند.
در اين ميان، مهمترين مبحثي که در ارتباط بـا ربـات مطـرح مـيشـود، بحث يافتن بهترين مسير بـراي حرکـت اسـت . مسـيريابي، مسـئله ي تعيـين مجموعه اي از حرکات است که بتواند يک ربـات را در حـداقل زمـان و بـدون برخورد با موانع ، از يک نقطه ي ابتدايي بـه نقطـه ي هـدف برسـاند [١]. البتـه يافتن بهترين مسير حرکت ، به عوامل مختلفي از جمله ماموريت تعريف شـده براي ربات، اطلاعاتي که از کل محيط کاري در اختيار ربـات قـرار مـيگيـرد، اطلاعاتي که خود ربات ميتواند از طريق سنسورهاي نصب شـده بـر روي آن از محيط اطراف خود دريافت کند و... بستگي دارد. لـذا، بـراي ورود بـه بحـث مسيريابي بهينه ربات، ابتدا بايد دقيقاً هدف کار مشخص شود. در برخي موارد، هدف اين است که ربات در يک محـيط ناشـناخته قـرار بگيرد، و فقط با استفاده از امکانات و تجهيزاتـي کـه بـر روي آن قـرار گرفتـه است در محيط حرکت کرده، و الگويي از محيط و موانع موجـود در آن تهيـه و ارائه نمايد [٢]. در اين شاخه ، که به تازگي مورد توجه قرارگرفته اسـت ، ربـات اطلاعي از مسير، و همچنين نوع، تعداد و نحوهي قرارگيري موانـع در محـيط کاري ندارد. اما يکي از پرکاربردترين مـوارد اسـتفاده از ربـاتهـاي متحـرک، زماني است که اطلاعات کلي در مورد محيط کاري ربات از جمله تعداد موانـع و نحوهي قرارگيري آنها، به نوعي در اختيار ربات و برنامه ي هوشمند آن قـرار مي گيرد. و وظيفه ي ربات اين است که به صـورت کـاملاً ايمـن ، يعنـي بـدون برخورد با موانع موجود در مسير، و حتيالامکان در حـداقل زمـان، از نقطـه ي شروع که در ابتـداي کـار در آن قـرار گرفتـه اسـت ، بـه نقطـه ي پايـاني کـه مختصات آن را در اختيار دارد، برود [٣,٤]. اين مبحث ، که تاکنون در مقـالات و تحقيقات مختلفي به آن پرداخته شده است ، خود به زير شاخه هـاي متنـوع- تري تقسيم ميشود. از جمله اينکه آيا ميتوان از ابعـاد ربـات در مقابـل ابعـاد موانع صرف نظر کرد؟ يا اينکه ربـات اطلاعـات مربـوط بـه محـيط را بـه چـه صورتي دريافت ميکند(از طريق دوربين و پردازش تصوير محيط ، يا از طريـق دريافت مختصات موانع بوسيله ي اپراتور و...)؟ و يا اينکه موانع محيط استاتيک هستند يا ديناميک ؟ در رابطه با هرکدام از اين موارد، تاکنون تحقيقات زيـادي به روشهاي گوناگون صورت گرفته است [١٢, ٦-٣].
مسيريابي را هم ميتوان قبل از حرکت ربات، و هم در حين حرکت ربات انجام داد. از اين منظر پاسخ هاي بدست آمده براي مسيريابي را ميتوان بـه دو گروه تقسيم بندي کرد: سراسري (استاتيک )، و محلـي (ديناميـک ). مسـيريابيِ سراسري نحوه و چگونگي حرکت را، قبل از شروع حرکت محاسـبه مـيکنـد.
اين شيوه هنگامي بکار ميرود که بخواهيم يک عملکرد حرکتي (مثلاً سرعت ) را بهينه نماييم ، يا ويژگي خاصي (نظير عدم برخورد با موانع ) را تضمين کنـيم .
در مسيريابي محلي، مسير هنگامي که ربات در حرکت است تعيـين مـيشـود.
اين راه حل عموماً در محيط هـاي ناشـناخته مـورد اسـتفاده قـرار مـيگيـرد و براساس اطلاعاتي است که از سنسورها بدست ميآيد [١٣].
در اين مقاله طرحي جديد بر مبناي الگوريتم ژنتيک براي يـافتن مسـير بهينه سراسريِ ربات، در محيطي که موانع آن استاتيک بوده و مشخصات آنها در اختيار ربات قرار دارد، ارائه ميشود. در اين راستا، ميتوان از ابعـاد ربـات در مقايسه با ابعاد موانع صرف نظر کرد و ربـات را بـه صـورت يـک ذره در نظـر گرفت [٦]. اما م توان اثرات مربوط به اين پيش فرض را، با بسط دادن موانـع موجود در محيط کاري، برطرف نمود. لذا اين فرض در کليت روش ارائه شـده خللي وارد نمي کند.
در ادامه ، در بخش دوم مدلي بر اساس تقسيم بندي سلولي براي فضـاي تکاشررييح ربمايشارواد.ه دخروابهخش د هوردمرتبابخش هزيسنوه مين دحروهنظير حگرکفتت ه شربدـاتعدرريحشـديهط و در بخش پنجم مسيريابيِ بهينه ي سراسري مورد بررسي قرار خواهد گرفت . در بخش ششم نتايج شبيه سازي انجام گرفته در محـيط MATLAB ارائـه خواهد شد و در نهايت در بخش هفتم نتيجه گيري ارائه خواهد شد.
٢- مدل فضاي کاري ربات
در اين بخش نحوه ي مدل کردن فضاي کاري ربات تشريح مي شود. همانگونه که قبلاً هم بيان شد، در اين مقاله فرض بر اين اسـت کـه ربـات مشخصـات مربوط به موانع و نحوهي قرارگيري آنها در محيط را ميداند. فرض کنيد يک دوربين ، تصويري از محيط در اختيار ربات قرار ميدهد . مي توانيم با استفاده از روشهاي پردازش تصوير موانع را شناسايي نماييم . براي اين کـه مختصـات دقيقي از کل محيط و موانع در اختيار داشته باشيم ، محيط را به صورت سلولي تقسيم بندي ميکنيم [٣]، [١١-٧] و هر سلول بوسيله مختصـات مرکـز آن شناخته ميشود. در اين شرايط مـيتـوان بـه راحتـي مختصـاتِ هـر نقطـه از محـيط ، و همچنين مختصات موانع را در اختيار داشت . ملاحظه ميشود که با اين روش ، اندازه موانع هر چقدر هم باشد، به راحتي در تقسيم بندي سلولي قرار گرفتـه و ميتوان مختصات سلولهاي تشکيل دهندهي آن را در اختيار ربـات قـرار داد.
ابعاد سلولها را ميتوان بسته به دقت مورد نياز در نظر گرفت . در اکثـر مواقـع ميتوانيم ابعاد سلولها را به گونه اي در نظر بگيـريم ، کـه شـرط صـرف نظـر کردن ابعاد ربات در برابر اندازه موانع برآورده شود. در شکل هاي(١) و (٢)، يک محيط کاري پس از سلول بندي نشان داده شده است .
شکل شماره (٢) را ميتوان بـه صـورت شـکل شـماره (٣) بـراي ربـات تعريف نمود. همانگونه که ملاحظه مي شود، بعضي از نقاطي که در مرز موانـع قرار دارند را، ميتوان هم به عنوان مانع در نظـر گرفـت ، و هـم بـا توجـه بـه حجمي از مانع که در آن سلول قرار دارد، از آن صرف نظر کرد. همانگونه کـه قبلاً هم اشاره شد براي افزايش دقت ، مي توان ابعاد سـلولهـا را کـوچکتر در نظر گرفت . همچنين براي در نظر گرفتن خطاي ناشي از صرفنظـر کـردن از ابعاد ربات، ميتوان با کوچک گرفتن ابعاد سلول ها، محدودهاي از اطراف موانع را به عنوان ناحيه ي امن در نظرگرفت که ربات حـق ورود بـه آنجـا را نداشـته باشد.
٣- نحوهي حرکت ربات در محيط
ربات، براي حرکت از يک سلول به سلول مجاور، مطابق شکل (٤) مي تواند در ٨ جهت حرکت کند. اين جهات حرکتي ربات در مقالات مختلفـي مثـل [١١]
مورد استفاده قرار گرفته است . اما در اينجا به منظور همگراييِ سريعتر به نقطه نهايي، فقط از جهت هاي حرکتيِ رو به جلو به سمت نقطه ي نهـايي (در اينجـا ١، ٢، ٣ و ٤) استفاده ميشود، مگر در مواقعي که با حرکت در ايـن جهـت هـا، ربات از محيط کاري خارج شده و يـا وارد يـک سـلول مـانع دار شـود. در ايـن صورت براي فرار از اين نقطه ي بن بست ، به صورت تصادفي يکـي از جهـت - هاي حرکتيِ رو به عقب ( در اينجا ٥، ٦ يا ٨ ) انتخاب خواهد شد.
ربات در طول حرکت ، اجازهي ورود به مربع هايي که مـانع در آنهـا قـرار دارد را ندارد، اما چون از اندازهي آن صرف نظر شده است ، ميتواند به صـورت شکل (٥) از بين موانع عبور کند.
شرايط بيان شده در شکل (٥) قطعاً در محل برخورد لبـه هـاي دو مـانع پديد خواهد آمد و باتوجه به محدودهي امني که گفتـه شـد، و همچنـين ابعـاد ربات، اجازهي چنين حرکتي خالي از اشکال است .
٤- تابع هزينه
حال که مدلِ محيط کاريِ ربات و مشخصات موانع موجـود در محـيط معلـوم است ، بايد مسيري تعيين شود که به واسطه ي آن ربات بتواند با کمترين هزينه و بدون عبور از سلول هاي مانع دار، خود را از نقطه ي شروع به نقطه ي نهـايي برساند. تابع هزينه اي که بايد مي نيمم شود، به صورت زير در نظر گرفته شـده است :
که در آن ، p1 متغير مربوط به طول مسير، يـا بـه عبـارت ديگـر تعـداد سلول هاي مسير از نقطه ي شروع تا نقطه ي نهايي است . p2 نيز متغير مربـوط به نرمي مسيرِ حرکت است . اگر ربات براي حرکـت از يـک سـلول بـه سـلول ديگر، جهت حرکت قبلي خود را حفظ نمايد، قاعدتاً هزينه ي کمتـري، نسـبت به زماني که ناچار به تعويض جهت حرکت شود، متحمل خواهد شد. تغييـرات مربوط به اين هزينه ها در متغير p2 ذخيره ميشود. p3 متغيري است که بـراي توسعه تابع هزينه توسط کاربر (در صورت نياز) در نظر گرفته شده است . k1 نيز ضرايب وزني هستند که بسته به نظر کاربر مـيتواننـد وزن هـر کدام از متغيرهاي هزينه را تغيير دهند. در اين مقاله ، اين ضـرايب بـه صـورت رابطه ي (٢) در نظر گرفته شدهاند :
٥- مسيريابي بهينه ي سراسري
روشي که در اين مقاله براي يافتن مسير بهينه مورد استفاده قرار گرفته اسـت ، روشي مبتني بر الگوريتم ژنتيک است . تفاوت روش ارائه شده در اين مقاله ، بـا ساير موارد مشابه در اين است که ، در شرايط عادي و تـا زمـاني کـه مسـير در نقطه ي بن بستي قرار نگيرد حرکت ربـات فقـط رو بـه سـوي نقطـه ي نهـايي خواهد بود، در نتيجه سرعت همگرايي به سمت مسير بهينه افزايش مييابد. از طرفي در اين روش براي تعيين جمعيت اوليه که توسط موتورهاي جستجو بـه صورت تصادفي انخاب ميشوند، فقط از مسيرهاي معتبر و بدون مانع اسـتفاده ميشود.
روال کار به اين صورت است که برنامه ي مسيريابي، ابتـدا بـا اسـتفاده از دو موتور جستجو (که جزئيات آنها در ادامه تشريح خواهد شد)، تعدادي مسـير نمونه را تعيين مينمايد. سپس ١٠ تا از بهترين مسيرها را انتخاب کـرده و بـه تابع بهينه سازي مي فرستد. تابع بهينه سازي نيز بهترين مسيري که شرط توقف الگوريتم را برآورده نمايد تعيين کرده و به خروجي برنامه ميفرسـتد. در ادامـه به بررسيِ جزئيات اين روش تشريح مي شود.
٥-١- موتورهاي جستجوي مسير
در اين روش، براي توليد مسيرهاي تصادفيِ اوليه (جمعيت اوليه ) از دو موتـور جستجو استفاده ميکنيم . اين موتورها مختصات سلولهاي موانع را به عنـوان ورودي گرفته ، و خروجي هر کدام از آنها، يک آرايه ي سلولي متشکل از ٤ جزء به صورت زير است :
که در آن :
x :يک آرايه ي ٢×n است که مختصات مسـير حرکـت از نقطـه ي شـروع تـا نقطه ي نهايي در آن قرار ميگيرد. انديسِ n تعداد سلولهايي است که مسـير تا رسيدن به نقطه ي نهايي از آنها عبور مينمايد. اين متغير، معادل کرومـوزومِ معرفِ هر مسير است .
P1 : متغيري است که تعداد سلولهاي مسير (n) در آن ذخيره ميشود.
P2 : متغير مربوط به هزينه ي نرمي مسير است .
p : يک بردار n×١ است که دنباله ي ذخيرهي جهت هاي حرکت است .
موتور اول، براي ايجاد يک مسير، از نقطه اي که به عنوان نقطه ي شروع در نظر گرفته شده است ، به صورت تصادفي جهتي را براي حرکت تعيين مي - کند. اگر با حرکت در جهت تعيين شده، مسير از محيط کاري خارج نشود و يـا وارد يک سلول مانع دار نشود، آن جهت و آن سـلول بـه عنـوان نقطـه ي دوم مسير به ترتيب در p و x ذخيره مي شوند. امـا اگـر جهـت تعيـين شـده مجـاز نباشد، يعني مسير از محيط کاري ربات خارج شود و يا وارد يک سلول مانع دار شود، جهتي ديگر به صورت تصادفي در نظر گرفته شـده و حرکـت در جهـت جديد صورت ميگيرد. در سلول جديد نيز، دوباره همين روند تکرار ميشود تـا در نهايت مسير به نقطه ي نهايي برسد. پس از تعيين مسير، تعداد سـلولهـاي تشکيل دهندهي مسير به عنوان هزينه ي طول مسير در متغيرِ p1 ذخيره مي - شود. همچنين در طي مسير، اگر در حرکت از يک سلول به سلول ديگر، جهت حرکت با جهت قبلي يکي باشد، مقدار ٠.٥ و در غير اينصورت مقـدار١ يـا ١.٥ (با توجه به ميزان زاويه ي چرخش ) به متغيرِ p2 که بيان کننده هزينه ي نرمي مسير است ، افزوده خواهد شد. و براي فرار از نقاط بن بست نيز، همان گونه که قبلاً بيان شد، از حرکت رو به عقب يا رو به پايين استفاده ميشـود. در نهايـت مختصات مسير توليد شده به همراه ساير مشخصات آن در يک آرايه ي سلولي ذخيره سازي ميشود. الگوريتم استفاده شده براي تعيين مسـير در موتـور اول، در جدول (١) نشان داده شده است .
در اين الگوريتم ، متغير Z متغير لازم براي فرار از گرفتار شـدن در نقـاط بن بست است .
تفاوت موتور جستجوي دوم ، با موتور جستجوي اول، در نحـوهي توليـد مسير است . به اين صورت که در اين موتور پس از انتخـاب اولـين جهـت بـه صورت تصادفي، جهت بعدي نيز به صورت پيش فرض همين جهـت انتخـاب ميشود، و اين روند ادامه مييابد تا هنگامي که مسير به يک سـلول نامناسـب برسد (خارج از محيط کاري و يا مانع دار). و اينجاسـت کـه جهـت بعـدي بـه صورت تصادفي و متفاوت با جهت قبلي در نظر گرفته مي شود. بعبارت ديگـر مسير تا رسيدن به يک سلول نامناسب ، جهت حرکت خود را حفظ ميکند. اين روند تاثير بسزايي در افزايش سرعت همگرايي، و همچنـين کـاهش هزينـه ي مربوط به نرميِ مسير خواهد داشت . خروجي اين موتور نيز، ماننـد موتـور اول، مختصات يک مسير به همراه ساير مشخصات آن خواهد بود. الگوريتم موتـور جستجوي دوم در جدول (٢) نشان داده شده است .
چرا از دو موتور جستجو استفاده ميشود؟
همانگونه که بيان شد، موتور دوم سـرعت همگرايـي بـالاتر و هزينـه ي کمتري ايجاد ميکند و عموماً هم مسيرهايي که توليـد مـينمايـد، بـه مسـير بهينه نزديکتر است . اما اين موتور، قدرت مانور بالاييِ ندارد. به عبـارت ديگـر تنوع و گوناگونيِ بالايي در مسيرهاي توليد شده توسط اين موتور وجود ندارد و خيلي از سلولهاي محيط کاري بلااستفاده بـاقي مـيماننـد. ايـن مشـ ل بـا استفاده از موتور اول حل ميشود. تنوع مسيرهاي بدسـت آمـده از موتـور اول بسيار بالاست و مانع از ناديده گرفته شـدن مسـيرهاي بهينـه احتمـالي ديگـر خواهد شد.
