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

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

Keywords:

برنامه ریزی حرکت روبات , الگوریتم ژنتیک , مثلث بندی دلونی , درخت کاوش تصادفی سریع