مسيريابي روبات متحرك با استفاده از روشي جديد مبتني بر الگوريتم ژنتيك با طول آرايه متغير

Mobile Robot Path Planning Using a New GA-based Method with Variable Chromosome Length

يكي از شاخه‌هاي مهم تحقيقاتي در علم روباتيك، برنامه‌ريزي حركت روبات است كه هدف آن يافتن مسيري بهينه از نقطه شروع به هدف و عاري از تصادم با موانع موجود در محيط روبات است. چنين مسيله اي در برنامه ريزي مسير وسايل نقليه هوشمند و AGV-ها نيز مطرح مي شود. از آنجا كه ثابت شده است اين مسيله از نوع NP-Hard مي‌باشد، الگوريتم‌هاي بهينه سازي سنتي موفقيت زيادي در حل آن كسب نكرده‌اند. در نتيجه، براي حل اين مسايل روش هاي ابتكاري مختلفي توسعه داده شده كه در اين ميان، روش الگوريتم ژنتيك به عنوان يكي از روشهاي تكاملي مبتني بر جمعيت با روندي افزايشي مورد استفاده قرار گرفته است. در اين مقاله، جهت رفع كاستي‌هاي روش‌هاي ژنتيك موجود مانند ثابت بودن طول رشته جواب و محدوديت هاي عملگرهاي جهش و تعويض، يك الگوريتم ژنتيك جديد براي حل مسيله برنامه‌ريزي حركت روبات‌هاي متحرك در شرايط غيربهنگام با داشتن اطلاعات فضاي جهاني روبات ارايه شده است، كه در آن پس از مثلث بندي فضاي روبات به روش Delaunay، دسته جواب هايي با روش درخت كاوش تصادفي سريع (RRT) ايجاد شده و هموارسازي مي شوند كه طول رشته جواب ها بر خلاف الگوريتم هاي ارايه شده در ادبيات متغير است. سپس با استفاده از عملگرهاي جديد جهش، تعويض و حذف، اين جواب ها بهبود داده مي شوند كه در هر سه عملگر، مثلث بندي ايجاد شده نقشي كليدي ايفا مي كند. شبيه سازي گسترده الگوريتم نشان داده است كه طول مسيرهاي به دست آمده با الگوريتم جديد به طور متوسط در حدود 25% نسبت به جواب هاي به دست آمده از روش RRT محض كوتاه تر مي‌باشند.