یک روش ترکیبی مبتنی بر الگوریتم ژنتیک و الگوریتم شبیه سازی تبرید برای مسیریابی ربات سیار در محیطهای پیچیده در حضور موانع ثابت و متحرک

تعیین مسیر بهینه برای حرکت ربات سیار )متحرک( در محیط دارای موانع مختلف یک مسیله NP-Hard است. بنابراین الگوریتمهای کلاسیک کارایی چندانی برای حل این مسیله ندارند، و استفاده از الگوریتمهای تکاملی ضروری به نظر میرسد.در زمینه بهینهسازی مسیر حرکت ربات، کمتر به مسیله محیطهای پویا توجه شده است. درحالیکه در کاربردهای واقعی برای یک ربات کاوشگر یا رباتی که باید به سوی یک هدف در فضای کاری حرکت کند، ممکن است موانع ثابت یا متحرک وجودداشته باشد. بنابراین دراین تحقیق، یک الگوریتم ترکیبی برای مسیریابی بهینه ربات سیار در محیطهای پویا با حضور موانع ثابت و متحرک )استاتیک و دینامیک( ارایه میشود. در این روش، مسیریابی بهصورت سراسری و خارج از خط انجام میگردد.در روش پیشنهادی، در هر لحظه )هر گام از حرکت ربات(، برای تعیین گام بعدی حرکت ربات، یک گزینه از بین گزینههای موجود بهعنوان گام بعدی حرکت ربات انتخاب میگردد. در روش پیشنهادی، در ابتدا الگوریتم ژنتیک اجرا شده و یکجستجوی سراسری برای طراحی مسیر در فضای جستجو انجام میدهد. سپس الگوریتم شبیهسازی تبرید برای مسیر ارایهشده توسط الگوریتم ژنتیک اجرا میشود، با این هدف که جواب الگوریتم ژنتیک را بهبود دهیم. نتایج شبیهسازی بر روی 5 فضایکاری دوبعدی با تنوع چگالی موانع ثابت و متحرک و مقایسه با سایر روشهای موجود، توانایی روش پیشنهادی در یافتن مسیر بهینه را بهخوبی نشان میدهد.

Keywords:

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