مسیریابی از میان موانع جابه جاشونده

Abstract

مسئله برنامه­ریزی حرکت با موانع جابه‌جاشونده، (NAMO)3، عبارت از یافتن مسیرهایی بدون تصادم برای روبات است؛ این در حالی است که روبات برای یافتن یک مسیر، می­تواند برخی موانع را جابه­جا کند. NAMOیکمسئله NP-Complete و در زمره مسائلی از مسیریابی حرکت روبات قرار می­گیرد که دارای محیط­های متغیر هستند. در این حوزه یک برنامه بهینه برای روبات می­تواند با توجه به فاکتورهای مختلف هم­چون طول مسیرهای انتقال و جابه­جایی، تعداد اجسام جابه‌جاشونده، تعداد دفعات جابه­جایی اجسام و زمان تعیین شود. در این مقاله با استفاده از مفاهیمی هم­چون گراف دید نگار4،و عمق نفوذ5، الگوریتم بازگشتی ارائه شده قادر است مسائل مختلف NAMO را در زمان معقولی حل کند. هم‏چنین به‌کارگیری الگوریتم پیشنهادی برای حل برخی مسائل موجود در ادبیات، موجب کاهش چشمگیر تعداد اجسام جابه­جا شده و تعداد دفعات جابه­جایی اجسام جابه‌جاشونده شده است.