خانه > روباتیک > برنامه ريزي حرکت ربات (Motion Planning)

برنامه ريزي حرکت ربات (Motion Planning)


معرفي

بعضي از مهمترين چالش هايي كه در كنترل ربات مطرح مي شود، در زمينه motion planning قرار مي گيرند. هدف اصلي motion planning  كامپايل كردن(تفسير) زبان هاي سطح بالا به يك سري از حركت هاي سطح پايين اوليه (اصلي) است.

اولين كار براي ربات يافتن مسير است چه ربات فقط يك بازوي ربات يا يك ربات متحرك يا رباتي كه آزادانه هنگام برخورد به موانع از يك وضعيت به وضعيت ديگر تغيير مي كند باشد.

با مساله piano mover’s ، motion planning براي اختصاص تعداد زيادي از متغيرها در مساله، اجراي نرم افزار ها در محيط هاي گوناگون ، طراحي هاي مربوط به جراحي ، بررسي اتوماتيك طرح هاي يك كارخانه ، نقشه برداري محيط هاي ناشناخته ، كنترل محيط هاي متغير و طراحي دارو به كار مي رود.نرم افزار هاي جديد ، بررسي هاي جديد را بوجود مي آورند كه بايد در طراحي الگوريتم هاي motion planning در نظر گرفته شوند.

از وقتي كه وقايع در دنياي فيزيكي بر مبناي قانون هاي فيزيكي ، وضعيت هاي نامعلوم و محدوديت هاي هندسي هستند، طراحي و آناليز motion planning مسائل جديدي در زمينه هاي مكانيكي، تئوري كنترل، هندسه محاسباتي و علوم كامپيوتر را به وجود مي آورند. تاثير motion planning فراتر از كاربردهاي آشكارش در نرم افزار است.

اين كتاب درباره تئوري ها و كارهاي عملي robot motion planning  با يك ديد نرم افزاري و سيستمي بحث مي كند. براي تمركز بر روي بحث و نكات مهم در motion planning ، ابتدا نگاهي به چند مثال جالب مي اندازيم.

 

 

مساله piano mover’s

مساله piano mover’s يک مساله کلاسيک در طراحي مسير است.اين مساله شامل يک سري مانع مي باشد. فرض مي شود که موانع ساکن و کاملا شناخته شده اند و اجراي مسيرهاي طراحي شده دقيق است. به اين حالت طراحي offline  مي گويند. زيرا طراحي قبل از اجرا به پايان رسيده است. گونه هاي مختلف اين مساله , مساله sofa mover’s است که در آن يک ربات روي يک سطح بين چندين مانع مسطح حرکت مي کند, مساله ديگر مساله generalized mover’s است که در آن ربات ممکن است شامل قطعات متصل به هم سخت در اتصالات مانند بازوي ربات باشد. مشکل کليدي اين است که مطمئن شويم هيچ نقطه اي روي ربات با مانع برخورد نمي کند بنابرايم ما بايد موقعيت تمام نقاط روي ربات را مشخص کنيم اين حالت يک configuration(پيکره بندي) ربات است و configuration space فضاي همه پيکره بندي هايي است که ربات مي تواند به آنها دست يابد. مجموعه زواياي اتصالات در بازوي ربات با جهتيابي روي فرش روي يک سطح نمونه اي از پيکره بندي ها هستند. فضاي پيکره بندي معمولا اقليدسي نيست به اين معني که شبيه فضاي  ،n بعدي اقليدسي نيست. ابعاد يک فضاي پيکره بندي برابر است با تعداد متغير هاي مستقل آن پيکره بندي که با درجه آزادي عمل آن (degree of freedom=DOF) نيز نشان داده مي شود. DOF مساله Piano برابر 6 است: 3 تا براي نشان دادن موقعيت (x-y-z) و 3 تا براي نشان دادن جهتيابي ( roll-pitch-yaw). هدف مساله يافتن  يک منحني در فضاي پيکره بندي است که نقاط شروع و پايان را به هم وصل مي کند و مانع همه configuration space obstacles مي شود که با وجود مانع در فضا افزايش مي يابد.

 

 

Mini AERcam

مرکز فضايي جانسون ناسا در حال توليد و توسعه Mini AERcam يا دوربين رباتيک خودگردان براي انجام وظايفي از قبيل بازرسي هاي فضايي است. اين وسيله يک ربات مجهز به 12 پشتيبان گاز سرد است که به آن اجازه فراهم کردن انرژي براي حرکت در هر جهتي را مي دهد. وقتي وسيله در حالت خودگردان ( اتوماتيک) قرار مي گيرد بايد توانايي هدايت در محيط هاي پيچيده ي 3بعدي را داشته باشد. به همين دليل اين مساله بسيار شبيه به مساله Piano mover’s است. ما نه تنها نياز به برنامه ريزي مسير حرکت براي ربات بلکه نياز به برنامه ريزي سرعت در طول مسير نيز داريم.اين موضوع trajectory (خط سير) ناميده مي شود و ورودي هاي پشتيبان به وسيله ي Dynamic ( حرکت) ربات تعيين مي

شکل 1.1

شوند. در مساله Piano mover’s نگراني ها فقط در مورد مسائل هندسه يا جنبش شناسي (Kinematic) بود.

 

 

Personal Transport Vehicle ( وسيله حمل و نقل شخصي(

يک وسيله حمل و نقل شخصي است که ممکن است به اصلي ترين وسيله براي حمل و نقل در محيط هاي شهري تبديل شود. جايي که اندازه , سرعت , آلودگي صوتي و آلودگي هوايي اتومبيل ها بسيار ناخوشايند است. يکي از اين وسيله ها CYCAB مي باشد. که يک وسيله حمل و نقل کوچک  است که توسط کنسرسيوم موسسه ها در فرانسه براي حمل و نقل حداکثر 2 نفر و سرعت 30 کيلومتر در ساعت طراحي شده است.يکي ديگر از اين وسيله ها Segway HT است که براي حمل يک شخص در سرعت 20 کيلومتر در ساعت طراحي شده است.

شکل 1.2

يکي از مسائلي که درباره ساده سازي کنترل وسايل نقليه در محيط هاي شلوغ مورد مطالعه قرار گرفته Automatic parallel parking است. راننده فرآيند parallel parking را انجام مي دهد و کامپيوتر روي دستگاه را مي توان از اين طريق کنترل کرد. سيستم هاي مشابهي به                                 زودي به طور اقتصادي در اتومبيل ها به کار خواهد رفت. در ظاهر اين مساله شبيه مساله Sofa mover’s است چون هر دو مساله شامل حرکت يک جسم روي يک سطح بين موانع است. تفاوت اين است که ماشين ها و وسايل نقليه بر خلاف Sofa (نيمکت) نمي توانند به طور لحظه اي از پهلو حرکت کنند.

 

 

(راهنماي موزه ها) Museum tour guides

شکل 1.3

در سال 1997 يک ربات متحرک به نام Rhino  به طور کاملا خودکار به عنوان يک راهنما در deutsches museum bonn  کار مي کرد. Rhino قابليت راهنمايي و هدايت بينندگان موزه را از يک غرفه به غرفه بعد با استفاده ار محاسبه مسير و با استفاده از نقشه ذخيره شده موزه فراهم مي نمود. چون يک مدل اجرايي دقيق در مساله piano movers با توجه به اين ويژگي ها غير واقعي است. Rhino مجبور بود مکان خود را با مقايسه

داده هاي دريافتي از حسگرها و نقشه ذخيره شده خود پيدا کند.

 

 

Planetary exploration(اکتشافات سياره اي)

شکل 1.4

يکي از موفق ترين و هيجان انگيز ترين دستاوردها در زمينه رباتيک, ربات متحرکي به نام sojourner بود که در 4  july 1997 در مريخ فرود آمد.sojouner  مانند پسر عموهاي موفق خود   spiri و opportunity بود که اين سيالات در ژانويه 2004 در مريخ فرود آمدند و تحول عظيمي را در علم داده ها به وجود آورده اند. در آينده ربات ها قادر خواهند بود مناطق وسيعي را زير پا گذاشته و بررسي کنند. از اين رو نياز به استقلال بيشتر خواهد داشت. علاوه بر قابليت جهت يابي بعضي ربات ها قادر خواهند بود که نقشه محيط را با استفاده از اطلاعاتي که از حسگرهاي خود به دست مي آورند توليد کنند.

بدون نقشه ربات نمي تواند موقعيت خود را تعيين کند و بدون اطلاع از موقعيت خود نمي تواند نقشه را تجزيه و تحليل کند.اين مساله اغلب با عنوان simultanecus localization & mappily يا به طور خلاصه SLAM  شناخته مي شود.

خنثي سازي مين

مناطق مين گذاري شده توسعه هاي اقتصادي را کاهش داده و صدمه و مرگ را هر ساله به دنبال دارد. در سال 1994 , 25 ميليون مين در سرتاسر جهان کاشته شد در حالي که فقط 100000 تا از آنها خنثي شده اند.

ربات ها نقش کليدي در خنثي سازي سريع و امن محيط دارند. قدم اول و اصلي يافتن مين است. در بحث خنثي سازي, ربات بايد با استفاده از حسگر هاي تشخيص مين همه نقاطي را که احتمال وجود مين در آن هست را بررسي کند. براي تحقق اين عمل ربات بايد داراي يک سري مسير دقيق براي عبور از مناطق خطرناک باشد. ربات نيازمند يک مسير ياب پوشش دهنده همه جا باشد تا بتواند حرکتي را که براي جستجوي همه نقاط لازم است انجام دهد. اگر مسيرياب , يافتن مسيري که بتواند همه نقاط را پوشش دهد , وقتي که يک مسير وجود دارد را تضمين کند,  مي گوييم اين مسير ياب(نقشه کش) complete (کامل) است.

عمل پوشش , کاربردهاي ديگري از قبيل پاک کردن کف اتاق , چمن زني  و برداشت محصول را دارد. در همه اين کاربردها ربات بايد همزمان مکان خود را تعيين کند تا پوشش کامل منطقه اطمينان حاصل فرمايد.

 

 

 

Fixed base robot arms in industry (بازوهاي ثابت ربات در صنعت)

شکل 1.5

در محيط هاي سازمان يافته بازوهاي ثابت وظايف گوناگوني از قبل سر هم کردن , جوشکاري و نقاشي(رنگ کردن) را انجام مي دهند.اين مساله چالش هاي تازه اي را به وجود مي آورد زيرا هميشه سطح ما يک سطح صاف نيست و ربات بايد احتمالأ درجه آزادي عمل خود  براي حرکت بازو هايش را هماهنگ کند تا بتواند بازوهاي خود را روي همه سطح حرکت دهد.

تأسيسات رباتيک صنعتي مشخصا توسط کارخانجات به کار مي روند بنابراين کمينه کردن زمان انجام يک کار از اهميت بالايي برخوردار است. نوع ديگر کارها ممکن است از نوع ديگري از کمينه سازي مانند کمينه سازي در مصرف سوخت و انرژي در ربات هاي سيار سود ببرند.

 

 

ربات هايي به شکل مار براي جستجوهاي شهري و عمليات نجات

وقتي ربات داراي آزادي عمل بيشتر در حرکات , بيش از نياز خود براي انجام يک کار باشد آن وقت ربات را redundant مي نامند.  وقتي ربات داراي آزادي عمل خيلي بالا در انجام حرکات خود باشد آن وقت به آن hyper redundant مي گويند.اين گونه ربات ها داراي فضاي پيکره بندي چند بعدي غير اقليدسي هستند. مکانيزم هاي hyper redundant شبيه خرطوم فيل يا مار هستند و مي توانند از آزادي عمل خود براي حرکت در مکانهاي تنگ براي دستيابي به مکانهايي که براي انسان و ماشين هاي موجود غير قابل دسترس اند استفاده کنند. اين ربات ها مي توانند براي جستجوهاي شهري و عمليات نجات مناسب باشند. اين ربات ها مي توانند در جاهايي که پيدا کردن محل صدمه ديدگان در زير آوار با سرعت هر چه بيشتر و امنيت بالا از اهميت ويژه اي برخوردار است, به کار روند.

 

 

 

 

شکل 1.6

 

 

کاراکترهاي ديجيتال

الگوريتم هاي مربوط به برنامه ريزي حرکت يا تفسير حسگرها فقط براي ربات ها نيستند. در صنعت سرگرمي برنامه ريزي حرکتي کاربردهاي گوناگوني در توليد حرکت براي کاراکترهاي ديجيتال دارد و راه ها را براي بازي هاي ويديويي انيميشن و محيط هاي ديجيتال بازتر مي کند.

طراحي دارو

مساله مهم در  طراحي دارو و مطاله بيماري ها , اين است که چگونه مي توان پروتيين ها را به پيکره بندي اوليه يا پايدار خود برد. با در نظر گرفتن اين موضوع که پروتيين مثل يک زنجير مصنوعي هستند. در طراحي داروهاي داروخانه اي پروتيين ها با مولکول هاي کوچکي ترکيب مي شوند  تا مجموعه اي را بوجود آورند که براي جلوگيري و درمان بيماري ها بسيار حياتي است. روش هاي motion planning براي آناليز حرکت پيچشي مولکول ها مورد استفاده قرار مي گيرد و امکان آزمايش خودکار دارو را قبل از ترکيب آن در ازمايشگاه فراهم مي کنند.

مرور کلي مسائل مربوط به motion planning

مثال هاي قبلي راه هاي مشخص کردن مسايل motion planning و الگوريتم آدرس دهي آن را نشان مي داد. بعضي مفاهيم را در اينجا شرح مي دهيم.

اهداف و کارها

مهمترين مشخصه يک برنامه ريزي حرکت ربات نحوه حل مسايل است. 4عمل مسير يابي , پوشش , تمرکز در محلي خاص و نقشه کشي را توضيح مي دهيم. مسير يابي مساله يافتن يک حرکت بدون برخورد براي سيستم ربات از يک وضعيت به وضعيت ديگر است. ربات مي تواند يک بازوي ربات باشد يا حتي يک موبايل يا هر چيز ديگري.

پوشش , مساله فرستادن يک سنسور يا ابزار به سراسر همه نقاط در فضا است. تمرکز در محلي خاص مساله استفاده از يک نقشه جهت تفسير حسگر هاي داده براي تعيين وضعيت ربات است. نقشه کشي مساله کشف و تشخيص يک محيط ناشناخته براي ساختن يک مدل که براي مسيريابي پوشش و تمرکز در محل خاص نيز مفيد است.

تمرکز در محلي خاص و نقشه کشي مي توانند با هم ترکيب شوند مثلSLAM .

ويژگي هاي ربات

شکل يک طراح حرکت مؤثر , بستگي زيادي به چگونگي انجام کار توسط ربات دارد. براي مثال ربات و محيط آن به درجه آزادي کار سيستم و وضعيت فضا بستگي دارد. وقتي وضعيت فضاي ربات را درک کنيم مي توانيم حرکت سريع و آزادانه ربات در همه جهات را در وضعيت فضاي خودش (در حالت نبود موانع) پيش بيني کنيم.

در نتيجه ربات را به عنوان يک گيرنده يا فرستنده امواج در جهات مناسب فرض مي کنيم.

در آخر رباتي که مدل مي شود از معادلات حرکت همراه با شتاب استفاده مي کند يا از معادلات پويا که البته با کنترل استفاده مي کند .

ويژگي هاي الگوريتم

بعد از اينکه هدف و سيستم ربات تعريف شد , ما مي توانيم بين الگوريتم هايي که مساله را حل مي کنند يکي را انتخاب کنيم. براي مثال آيا طراح مي تواند حرکتي را پيدا کند که در مواردي از قبيل طول , زمان اجرا و انرژي بهينه باشد؟ يا آيا يافتن يک راه حل که محدوديت ها را ارضا کند آسان است؟ علاوه بر کيفيت خروجي يک طراح , ما مي توانيم سوالاتي درباره پيچيدگي محاسبات يک طرح نيز مطرح کنيم.

اندازه ورودي مي تواند درجه آزادي سيستم ربات , ميزان حافظه مورد نياز براي توصيف ربات , موانع در محيط و …. باشد و پيچيدگي آن مي تواند در بهترين حالت يا حالت ميانگين تعريف شود. وقتي يک الگوريتم در زمان چند جمله اي براي مساله اي پيدا شود که قبلا فقط در زمان هاي نمايي حل مي شد نکات تازه و کليدي را درباره مساله به دست مي آورد.

وقتي برنامه ريزي و نقشه کشي complete(کامل) باشد به اين معني است که حتما راه حلي براي مساله motion planning پيدا مي کند.براي مساله motion planning وقتي درجه آزادي عمل افزايش مي يابد راه کامل ممکن است خود سرانه باشد. بنابراين ما مي توانيم شکل هاي ضعيف تري از کامل بودن را جستجو کنيم. يکي از اين شکل ها resolution completances است. اين بدان معني است که اگر راه حلي در يک تحليل  وجود داشته باشد طراحان آن را خواهند يافت. يکي ديگر از شکل هاي ضعيف کامل بودن probabilistic completeness است. اين بدان معنا است که احتمال يافتن يک راه حل (در صورتي که وجود داشته باشد) در بينهايت همگرا به 1 است.

کامل بودن و پيچيدگي محاسبات به طور طبيعي توسط يکديگر سبک و سنگين و مقايسه مي شوند. اگر ما خواستار motion plan بهينه يا کامل , از طراحان هستيم بايد از افزايش پيچيدگي محاسبات راضي باشيم.

ما مي گوييم يک طراح offline است اگر يک طرح را از قبل بر مبناي يک مدل شناخته شده در محيط طراحي کند و سپس اين طرح را به اجرا کننده بدهد. گوييم يک طراح online است اگر يک طرح را طراحي کند وقتي که ربات در حال اجرا است. تفاوت بين الگوريتم هاي offline و الگوريتم هاي بر مبناي سنسور online مي تواند قدري تيره باشد براي مثال اگر طراح offline بتواند به قدر کافي سريع اجرا شود مي تواند براي طراحي مداوم  وقتي داده هاي جديد حسگر, مدل محيط را بروز کند استفاده شود.

فرق اساسي در زمان محاسبه است و اغلب الگوريتم ها با اين معيار طراحي مي شوند. در اين کتاب ما درباره کنترل کننده هاي بازخوردي سطح پايين که نياز به پياده سازي واقعي  motion planningدارند بحث نخواهيم کرد اما فرض خواهيم کرد که آنها وجود دارند و در دسترسند.

مرور کلي اين کتاب

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

اين الگوريتم هاي ساده تضمين مي كند كه ربات به هدف خواهد رسيد اگر آن هدف قابل دستيابي باشد.

براي اينكه فراتر از ربات هاي نقطه اي بحث كنيم ، در فصل 3 فضاي پيكره بندي سيستم هاي بسيار معمول ربات را كه شامل بدنه هاي سخت و بازوهاي ربات هستند ، شرح مي دهيم.

پايه هاي رياضي در اين فصل به ما اجازه مي دهد تا مسائل عمومي مسير يابي از قبيل يافتن يک مسيردر فضاي پيکره بندي را مرور کنيم و ببنيم. ما مواردي از قبيل بعد(درجه آزادي عمل) توپولوژي و پارامترهاي فضاي پيکره بندي غير اقليدسي را مطالعه مي کنيم.

فصل4 يک سري از الگوريتم ها را که بر مبنايartificial potential function  ( توابع بالقوه مصنوعي) هستند توصيف مي کند. براي اين منظور ما يک منطقه بالقوه مصنوعي در فضاي پيکره بندي به وجود مي آوريم تا موانع را در آن دفع کنند و هدف را در آن , براي ربات , جذاب نشان دهيم. سپس ربات به سادگي شيب مربوط به پتانسيل مصنوعي را دنبال مي کند. براي برخي مسايل هدايت و راه يابي , اين امکان وجود دارد که يک محيط بالقوه طراحي کنيم تا مطمئن شويم که حرکت روي شيبها , ربات را هميشه به مقصد و هدف مي رساند.

اگر محاسبه برخي محيط هاي بالقوه سخت يا غير ممکن باشد مي توانيم به جاي آن از مواردي که محاسبه آن آسان تر است استفاده کنيم اما ممکن است اين  مورد يک ويژگي نامطلوب داشته باشد مکان هايي که ربات در آن ها گير مي کند (به دام مي افتد).در اين مورد ما مي توانيم به سادگي از منطقه بالقوه به منظور هدايت و راهنمايي طراحي هايي که بر مبناي جستجو کار مي کنند استفاده کنيم.

شيوه رياضي

هدف ما ارائه عناويني است که به خواننده کمک کند تا مفاهيم رياضي را عميقا درک کند. ما اغلب از سختي هاي رياضي جلوگيري مي کنيم و مطالب سخت رياضي را مطرح نمي کنيم اما در جايي که مساله به طور شهودي قابل فهم باشد. در بيشتر مسايل , اثبات تئوري در نظر گرفته نشده است براي بيشتر قسمت ها مفاهيم رياضي به همان اندازه که لازمند ارائه شده اند. در همه اين کتاب فرض شده که ربات ها در محيط هاي دو وجهييا سه بعدي  عمل مي کنند. بعضي اوقات محيط کاري را با W ذنشان مي دهيم. اين محيط کاري اغلب شامل موانعي است که با که i نشان دهنده iمين مانع است نشان مي دهيم.

Motion planning معمولا در محيط کاري اتفاق نمي افتد بلکه در در فضاي پيکره بندي Q (که فضاي C نيز ناميده ميشود) اتفاق مي افتد ما از R(q) براي نشان دادن نقاطي از فضاي محدود اشغال شده توسط ربات در پيکره بندي q استفاده مي کنيم.

در اين کتاب مابين path planning و motion planning تفاوت قائل هستيم. يکpath  يک منحني پيوسته در فضاي پيکره بندي است.

 

فصل 2

در اين فصل راجع به الگوريتم هايي صحبت مي شود که ربات هنگام حرکت کردن و برخورد به موانع از آنها استفاده مي کند تا راهي به سمت هدف پيدا کند.

Bug1 و Bug2 از اولين و ساده ترين الگوريتم هايي هستند که بر پايه سنسور مي باشند. يعني در اين الگوريتم ها ربات به عنوان يک نقطه در نظر گرفته مي شود که در يک صفحه عمل مي کند و داراي يک سنسور تماسي ( سنسوري با برد صفر ) است تا موانع را تشخيص دهد. وقتي ربات يک سنسور با برد غير صفر دارد, مي توان از الگوريتم  tangent bug براي پيدا کردن کوتاه ترين مسير به هدف استفاده مي کند.  الگوريتم هاي bug يا شبيه به bug خيلي ساده پياده سازي مي شوند. علاوه بر اين مي توانيم با يک آناليز ساده نشان دهيم که اين الگوريتم ها موفق عمل مي کنند.

اين الگوريتم ها از دو رفتار تبعيت مي کنند: حرکت روي خط مستقيم و دنبال کردن موانع.

 

 

الگوريتم Bug1

در اين الگوريتم ربات به سمت هدف حرکت مي کند مگر اينکه به يک مانع برخورد کند. در اين حالت مانع را دور مي زند تا زماني که رسيدن به هدف دوباره جايز باشد. در واقع الگوريتم Bug1 ايده حرکت به سوي هدف و دور زدن را فرمول بندي مي کند.

در اين الگوريتم فرض مي شود که ربات به صورت نقطه اي در محيط با موقعيت کامل (بدون خطا) است و مي تواند با استفاده از سنسور مرز موانع را در صورت تماس با آنها کشف کند. همچنين ربات مي تواند فاصله بين هر دو نقطه x و y را محاسبه کند و فرض بر اين است که فضاي حرکت محدود است.

يک نقطه شروع و يک نقطه هدف داريم. ربات حرکت خود را از نقطه شروع آغاز مي کند و بطور مستقيم به سمت هدف حرکت مي کند. يا به مقصد مي رسد يا به مانع برخورد مي کند. اگر به مانع برخورد کرد (که به اين نقطه  hit point يا نقطه برخورد مي گويند) , کل محيط مانع را طي مي کند تا به نقطه برخورد برسد. در واقع مانع را دور مي زند. در اين مسير نقطه اي را که کوتاهترين فاصله تا هدف را دارد, پيدا مي کند. به اين نقطه leave point (نقطه ترک) مي گويند. از نقطه برخورد يک بار ديگر دور مي زند تا به اين نقطه برسد و از اين نقطه دوباره خرکت مستقيم خود را به سمت هدف آغاز مي کند. ربات همين کار را تکرار مي کند تا به مقصد برسد يا اينکه تشخيص دهد رسيدن به مقصد غير ممکن است. اگر خطي که هدف و leave point را بهم وصل مي کند, مانع را تقسيم کند هيچ راهي به سمت هدف وجود ندارد.

شکل 2.1

الگوريتم Bug2

الگوريتم bug2 نيز مانند bug1 دو رفتار دارد: حرکت روي خط مستقيم و دنبال کردن موانع.

در اين الگوريتم نقطه شروع و هدف با خطي بهم متصلند  و ربات روي اين خط حرکت مي کند. اگر به مانعي برخورد کرد, روي مرز مانع حرکت مي کند تا به نقطه اي برسد که روي خطي که نقاط شروع وهدف را بهم وصل کرده است قرار دارد و به هدف نزديک تر است. سپس حرکت خود را به سمت هدف ادامه مي دهد.

در اينجا ديگر ربات همه مانع را دور نمي زند.

در اين الگوريتم اگر ربات بعد از حرکت روي مرزمانع به نقطه برخورد رسيد, يعني راهي به سوي هدف وجود ندارد.

شکل 2.2

 

 

در نگاه اول به نظر مي رسد که الگوريتم bug2 از bug1 کارآمدتر است چون مسير کوتاه تري را طي مي کند ولي هميشه اينگونه نيست. با يک سري محاسبات رياضي, براي بدست آوردن مسيري که در هر يک از اين الگوريتم ربات طي مي کند, مي توان نشان داد که در برخي موارد مسافتي که براي رسيدن به هدف طي مي شود در bug2 بيشتر از bug1 است.

Bug1 يک جستجوي کامل را براي يافتن کوتاه ترين مسير انجام مي دهد ولي bug2 از يک جستجوي فرصت طلبانه يا در واقع از الگوريتم هاي حريصانه استفاده مي کند.

 

شکل 2.3

 

شکل 2.3 نشان مي دهد که در برخي موارد الگوريتم bug1 از الگوريتم bug2 بهتر عمل مي کند.

 

 

 

 

 

 

 

 

 

 

فصل 3 (فقط برای مطالعه)

فضاي وضعيت (Configuration Space)

يکي از مهمترين موارد مورد نياز در برنامه ريزي حرکت, تعيين موقعيت تمام نقاط عامل است, چرا که بايد مشخص گردد که آيا عامل با موانع برخورد دارد يا نه. اين موضوع باعث طرح سوالاتي مي گردد: به چه مقدار اطلاعات به منظور مشخص کردن کامل موقعيت تمام نقاط عامل نياز است؟ اين اطلاعات چگونه بايد نشان داده شود؟هنگام پيدا کردن مسيري براي عامل, موانع به چه صورت بابيد در نظر گرفته شوند؟ و… هدف ما در اين قسمت پاسخ دادن به چنين سوالاتي مي باشد.

 

مشخص کردن وضعيت يک عامل(Specifying a Robot`s Configuration)

محيط محصوري که عامل در آن حرکت مي کند را فضاي کار مي ناميم. براي مثال يک بازوي مکانيکي فضاي کار موقعيت تمام نقاطي در محيط بسته است که اثرکننده (End Effector) به آن دسترسي دارد.

وضعيت يک عامل توصيفي است از موقعيت تک تک آن عامل. فضاي وضعيت (C-Space) يک عامل نيز فضاي تمام وضعيت هاي ممکن آن عامل است. بنابراين يک وضعيت از يک عامل در فضاي وضعيت تنها يک نقطه در آن فضا است. در اين پايان نامه از q براي نشان دادن وضعيت و از Q براي نشان دادن فضاي وضعيت استفاده مي شود. بعد فضاي وضعيت برابر است با بعد درجه آزادي عامل که در بخش هاي بعدي بيشتر به اين موضوع خواهيم پرداخت.

اگر يک ربات دايره اي در فضاي2 R‌ بدون چرخش (rotate) را نسبت به يک محور مختصات مرجع در نظر بگيريد, يک راه ساده براي مشخص کردن وضعيت ربات در نظر گرفتن مرکز آن است. اگر مرکز ربات (x,y) و شعاع دايره (r) را داشته باشيم, مي توانيم به راحتي از فرمول زير موقعيت تمام نقاط اشغال شده توسط ربات در محيط را بيابيم:

R(x,y)={(x,y)|(x-x)2+(y-y)2≤r2}

و به اين ترتيب تنها با دانستن مختصات مرکز ربات مي توان وضعيت آن را به طور کامل مشخص نمود.

فضاي کار و فضاي وضعيت دو مفهوم کاملا متفاوت هستند. براي واضح تر شدن اين دو مفهوم مثال زير را در نظر بگيريد :

يک بازوي مکانيکي دو مفصله همانند شکل 3.1 در نظر بگيريد.

 

شکل 3.1

 

فضاي کار اين ربات تمامي نقاطي است که توسط اثرکننده قابل دسترسي است. اين فضا در شکل 3.2 مشاهده مي شود. از آنجايي که هر نقطه در فضاي کار به دو صورت قابل دسترسي است (در حالت اول اثرکننده رو به پايين و در حالت دوم رو به بالا) بنابراين مختصات اثرکننده نشان دهنده وضعيت (Configuration) ربات نيست, چرا که از روي اين مختصات نمي توان به وضعيت کليه نقاط ربات پي برد.

اما براي تعريف فضاي وضعيت از زواياي مفصلي که در شکل 3.1 مشاهده مي شود مي توان استفاده کرد. هر زاويه  را مي توان به نقطه اي بر روي دايره واحد  مرتبط نمود.

وضعيت فضاي پيکربندي

اکنون که ما چگونگي تصميم گيري در باره ي اندازه گيري فضاي پيکر بندي را فهميديم, ما مي توانيم هندسه و وضعيت آن را که هر کدام نقش هاي اساسي در تحليل و توليد الگوريتم هاي طراحي حرکت بازي مي کنند, کشف کنيم.

 

شکل 10.3    سطح ليوان قهوه و جسم هلالي به لحاظ وضعيتي معادل هستند.

توپولوژي يکي از شاخه هاي رياضي است که ويژگي هاي اجسامي را بررسي مي کند که وقتي آن اجسام در معرض تغييرشکلهاي متصل از قبيل کشش و يا خميدگي قرار مي گيرند, تغيير نمي کنند. به همين خاطر گاهي اوقات توپولوژي به عنوان «هندسه ي صفحه ي لاستيکي» خوانده مي شود. وقتي صفحه در جهات مختلف کشيده مي شود, شکل چند ضلعي تغيير مي کند, در حالي که ويژگي هاي واقعي چند ضلعي تغيير نمي کنند. به عنوان مثال نقاطي که درون چندضلعي قرار دارند, به خاطر اينکه صفحه کشيده مي شود, به بيرون چند ضلعي حرکت نمي کنند. دو فضا از نظر توپولوژي با هم متفاوتند اگر براي تبديل يکي به ديگري نياز به copy و paste باشد. چون copy و paste تغيير شکل هاي متصلي نيستند. يکي از دلايلي که ما به توپولوژي فضاي پيکربندي توجه مي کنيم اين است که اين موضوع مي توانيد بر روي نمايش ما از فضا تاثير بگذارد. دليل ديگر اين است که اگر ما بتوانيم يک الگوريتم برنامه ريزي بر مبناي مسير را براي يکي از فضاهاي توپولوژيک استنتاج کنيم, سپس آن الگوريتم ممکن است که به فضاهايي که از نظر توپولوژيکي معادل هستند, انتقال يابد.

يک نگاشت   قاعده اي است که اجزا S را با اجزا مشابه در T جايگذاري مي کند. ما به ترتيب image مربوط به S را تحت  و preimage مربوط به T را با استفاده از  تعيين مي کنيم.

 

 

شکل 11.3

اگر  , آنگاه ما مي گوييم  surjective و يا onto مي باشد. اگر  هر جز مربوط به T را با جزء مشابه آن در S به ازاي هر  که شامل جزء بشتري در S است قرار دهد, آنگاه مي گوييم  , injective است. اگر  , injective باشد آنگاه هنگامي که  باشد براي  خواهيم داشت : . نقشه هايي که هم surjective و هم injective باشند به آنها مي گوييم bijective هستند. شکل 11.3 اين تعاريف را نشان مي دهد.يک نگاشت  , smooth خوانده مي شود اگر همه ي ماخوذات جزئي  خوش تعريف باشند.

اتصالات قابل تغيير

براي همه ي فضاهاي پيکربندي که تابه حال ديده ايم توانسته ايم به طور خاص يک پيکربندي با n پارامتر مشخص کنيم که n اندازه ي فضاي پيکربندي را تعيين مي کند. دليل اين که توانستيم اين کار را انجام دهيم اين بود که  اين فضاهاي پيکربندي همگي فضاهاي n-بعدي اقليدسي بودند. اين فضاها که manifold يا اتصالات نام دارند, يک موضوع مرکزي توپولوژي محسوب مي شوند.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

دسته‌ها:روباتیک
  1. هنوز دیدگاهی داده نشده است.
  1. No trackbacks yet.

پاسخی بگذارید

در پایین مشخصات خود را پر کنید یا برای ورود روی شمایل‌ها کلیک نمایید:

نشان‌وارهٔ وردپرس.کام

شما در حال بیان دیدگاه با حساب کاربری WordPress.com خود هستید. بیرون رفتن / تغییر دادن )

تصویر توییتر

شما در حال بیان دیدگاه با حساب کاربری Twitter خود هستید. بیرون رفتن / تغییر دادن )

عکس فیسبوک

شما در حال بیان دیدگاه با حساب کاربری Facebook خود هستید. بیرون رفتن / تغییر دادن )

عکس گوگل+

شما در حال بیان دیدگاه با حساب کاربری Google+ خود هستید. بیرون رفتن / تغییر دادن )

درحال اتصال به %s

%d وب‌نوشت‌نویس این را دوست دارند: